Nick's blog, University of Warwick

July 02, 2008

Wine for Windows?!

Writing about web page http://sourceforge.net/project/showfiles.php?group_id=6241&package_id=112520

Probably nothing new to a lot of people, but I just spotted that the wine website has binary downloads for Windows.

Admittedly I can think of a couple of uses for this, but that doesn't really take away from the initial "wtf?" I got when I found out.

I wonder if it runs cygwin... :-)

(For anyone wondering what I'm blathering about, wine is a compatibility layer used for running Windows programs on Unix - or in this case, running Windows programs on Windows)

: 02 Jul 2008 15:09 | Tags: Cygwin Unix Windows Wine Wtf | Comments (4) | Close comments | Report a problem

February 11, 2008

Raytracing: Intersection with a sphere

Follow-up to Raytracing: Intersection with a plane from Nick's blog

Last time I went through intersection of a ray with a plane. Plane’s are all well and good, but you can’t have a ray tracer without spheres everywhere :-)

This article’s another maths-heavy one I’m afraid – more vectors and dot products, this time with a quadratic equation thrown in at the end. Enjoy.

Equation for our ray:

$P = O + Dt$

(P is the position, O is the origin of the ray, D is the direction of the ray, t is the parametric variable)

Equation for a sphere:

$(x - C_x)^2 + (y - C_y)^2 + (z - C_z)^2 = r^2$

(x, y and z represent points around the surface of the sphere, C is the centre of the sphere, r is the radius of the sphere)

As with the plane intersection in the previous article, we solve the equations simultaneously, setting P = (x,y,z).

First we’ll rewrite the sphere equation in vector form. Summing the squares of the x, y and z components is the same as the dot product.

$(P - C) \cdot (P - C) = r^2$

Now substitute in the equation for our ray:

$(O + Dt - C) \cdot (O + Dt - C) = r^2$

We’re trying to solve for t, so let’s break up the above equation using the distributivity of the dot product:

$(O + Dt - C) \cdot O + (O + Dt - C) \cdot Dt + (O + Dt - C) \cdot (-C)= r^2$

Now extract the Dt terms:

$(O - C) \cdot O + (O - C) \cdot Dt + (O - C) \cdot (-C) + (Dt) \cdot O + (Dt) \cdot (Dt) + (Dt) \cdot(-C) = r^2$

Collect like terms:

$(O - C) \cdot O + 2(O - C) \cdot Dt + (O - C) \cdot (-C) + (Dt) \cdot (Dt) = r^2$

Now if we take the scalar t outside of the dot products, and move the r squared to the left hand side we get:

$(O - C) \cdot O + (O - C) \cdot (-C) + t(2(O - C) \cdot D) + t^2(D \cdot D) - r^2 = 0$

Which we can solve using the quadratic formula

Where
$a = D \cdot D = 1 \\ b = 2(O - C) \cdot D \\ c = (O-C) \cdot O + (O-C) \cdot (-C) - r^2 = (O-C) \cdot (O-C) - r^2$

This is where I notice that I’ve reused “C” as a variable name – don’t get confused between “C” for centre” and the “c” in the quadratic formula.

Here I’ve also simplified A and C. A is always 1 in this case, as the direction of our ray “D” is normalised. I’ve also combined C into a single dot product.

Here’s the quadratic formula, which we can simplify by removing the “a” multiplicand.

$t = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\ = \frac{-b \pm \sqrt{b^2 - 4c}}{2}$

The rest is just a case of plugging in your values.

In order to solve this, you should check the value of the determinant (the bit inside the square root). If it’s < 0 then we have no real solutions, and therefore no intersections.

If the determinant is >= 0, then you need to check both solutions to the equation(-b + ... and -b – ...). We want the closest (lowest value) positive solution. A -ve value means the intersection is behind the ray. Also, if you have one +ve and one -ve solution, then your ray has been cast from inside the sphere.

One final thing worth noting is that there are special methods used to compute quadratic solutions which help to reduce the effect of rounding errors.

Ok, well hope that makes sense. Let me know if you have any questions or comments. Next post will probably cover lighting, so you can actually get planes and spheres in colour!

: 11 Feb 2008 14:26 | Tags: Intersection Ray Raytracing Sphere | Comments (9) | Close comments | Report a problem

February 01, 2008

Raytracing: Intersection with a plane

Follow-up to Raytracing: A (Very) Brief Introduction from Nick's blog

Last time I mentioned that rays are cast from the eye point. This isn’t much good of course unless you can tell what the ray collides with. So here’s an idea of how to check for the intersection of a ray and a flat plane.

Representing our objects

Here’s the mathsy bit. If you’ve covered vectors before, then I think it should be reasonably easy to follow. Let me know if you have any questions or spot any mistakes.

The Ray

We can represent our ray with an origin, and a direction. Both of these are 3-dimensional vectors. It will come in handy later if our direction is normalised (has a length of 1).

We can then represent the path the ray takes as a parametric equation in t.

$P%7E%3D%7EO%7E%2B%7EDt$

(P is the position, O is the origin, and D is the direction).

Because our direction vector is normalised, t is also the distance the ray has traveled from the origin.

The Plane

Representing a plane is a little less intuitive, but we can do it using a (3D) vector to represent the normal to the plane, as well as a value to represent the distance to the origin (in the direction of the normal). Note: this is the distance to the origin at (0,0,0) rather than the origin of the ray mentioned above.

e.g. if we look down the Z-axis from 0 in the positive direction, we could represent a wall 10 units away with a plane with a normal of (0,0,-1) and a distance of 10.

The general equation for a plane is:

$ax%7E%2B%7Eby%7E%2B%7Ecz%7E%2B%7Ed%7E%3D%7E0$

Where a, b and c are the x, y and z components of the normal, and d is the distance to the origin. To make the later equations more concise, we’ll rewrite the plane equation in vector form as:

$P%7E%5Ccdot%7EN%7E%3D%7E-d$

(P is the position, N is the normal, and d is the distance from the origin. Also the dot is the dot product)

The Maths

As we’ve already established, t is the distance the ray has travelled from the origin. What we want to do now is find out how far the ray has travelled if/when it intersects our plane. We can do this by solving the ray and plane equations simultaneously.

Starting with the plane equation:
$P%7E%5Ccdot%7EN%7E%3D%7E-d$

Substitute in the ray equation:

$%28O%2BDt%29%7E%5Ccdot%7EN%7E%3D%7E-d$

The dot product is distributive, so we can do this:

$O%7E%5Ccdot%7EN%7E%2B%7E%28Dt%29%7E%5Ccdot%7EN%7E%3D%7E-d$

The dot product also lets us take multiplied scalar arguments outside the brackets like so:

$O%7E%5Ccdot%7EN%7E%2B%7Et%28D%7E%5Ccdot%7EN%29%7E%3D%7E-d$

Now shuffle it around a bit…

$t%28D%7E%5Ccdot%7EN%29%7E%3D%7E-d%7E-%7EO%7E%5Ccdot%7EN$

A bit more…

$t%7E%3D%7E%5Cfrac%7B-d%7E-%7EO%7E%5Ccdot%7EN%7D%7BD%7E%5Ccdot%7EN%7D$

Super! Now we have the distance the ray has travelled when it hits the plane. We can plug this value back into the ray equation to get the intersection point in 3D coordinates too.

If the ray doesn’t hit the plane then both the numerator and denominator of the above equation are 0.

If you’d implemented what I’ve said so far, you would probably have a screen with half white (for the intersection hits) and half black (for the misses). So what we need now is some colour, or a slightly more interesting primitive to draw.

So, next time I’ll probably cover intersection with a sphere or how to colour your object with some simple lighting equations. Any preferences? I’ll probably do them both anyway.

: 01 Feb 2008 19:49 | Tags: Raytracing | Comments (6) | Close comments | Report a problem

January 29, 2008

Raytracing: A (Very) Brief Introduction

I’ve recently started writing a basic ray tracer, and thought I’d write a bit about how they work.

The basic idea of ray tracing is to generate a 2D image (or series of images) from a 3D scene by simulating how rays of light travel.

One important difference here is that instead of simulating rays cast from a light source and eventually hitting the eye/camera, a ray tracer will generally cast rays backwards from the eye, taking information from light sources at the end. This means we don’t have to simulate all the rays coming from each light source, most of which we don’t see (i.e. they don’t hit the eye).

Rays are cast from the eye though a plane, which represents our render target, with one ray for each pixel of the render target.

The ray tracer then determines the (nearest) intersection of the ray with the scene geometry. From here we can cast secondary rays to simulate reflection, refraction, etc. Also rays can be cast directly to the light sources in the scene. These rays (which may in turn spawn other rays) are all combined to give a colour for the ray. This colour is then applied to the pixel that the ray was cast through.

That just about covers my basic introduction. I intend to write a few more articles on this, the next of which will probably cover how to determine intersections between rays and geometry. Bring your maths hats.

: 29 Jan 2008 13:24 | Tags: Raytracing | Comments (20) | Close comments | Report a problem