Steve’s Blog

Just another compsci weblog

Archive for the 'Computer Graphics' Category

Ray Tracer: Part I

It has been quite a while since I posted on here, but I haven’t had a great deal of free time lately. Since I’m graduating in May, I’m trying to get applications in for grad school which means I have to figure out a) what I want to do and b) where I want to go. And that’s aside from taking the general GRE and studying for the CS GRE.

But anyway, I’m taking a computer graphics course this semester, the final project of which is a ray tracer. And I’ve always wanted to write one so I decided to get a head start on the project. I’ll be writing here as I refine pieces of the code that are post-worthy.

The obvious place to begin is with ray-geometry intersection code. I’ll skip ray-sphere intersections since you can find information on it everywhere. More interesting, in my opinion, is a ray-convex polyhedron intersection, mostly because many programs (Q3Radiant, Hammer) save level data in that format (which are then compiled into BSPs – more on spatial partitioning soon).

So how do we test collisions against convex polyhedra? Simple! Err, sorta. Actually, the method I use is one that I read from an article, Quake 3 Collision Detection, which I used long before I understood how it works. So I’m going to try to explain it as best I can, and provide a much cleaner version of the code.

Convex Polyhedra

First of all, what is a convex polyhedra? Lets define it simply as a set of planes in 3-space which form a closed volume. Lets look at a 2d example:

We begin with one plane, represented by the black line. The flag coming off of the plane is the normal and the area behind it is the volume, shaded in gray. Then we add a second plane, however the intersection of the two volumes is still infinite. Finally a third is added. The intersection of the volumes behind the three planes gives us a closed, finite volume, which will be the volume of the polyhedron (just imagine it in 3d). Note that we are not storing any vertex, edge, or face information; only a list of planes.

Ray-Polyhedron intersection

The basic idea is that we test each plane to see if the ray intersects with it. There are three cases that we need to consider: 1) the ray starts outside of the polyhedron and intersects with its volume, 2) the ray starts outside the polyhedron and doesn’t intersect with its volume, and 3) the ray starts inside the polyhedron.

How can we differentiate between these three cases while we’re intersecting each plane? First we determine which side of the plane the ray starts on. If the ray starts in front of the plane (the side in which the plane normal points), then we’ll call it a front intersection, otherwise we’ll call it a back intersection. Here are illustrations of the most frequent scenarios:

In the first picture, we can see two of the front intersections that the ray makes, colored in blue. The second picture shows two back intersections, colored in green. Finally, the third picture shows a ray that does not intersect with a volume. Note that while the ray does not intersect the volume, it does intersect the planes.

Notice how in the first picture, the front intersection that lies furthest from the origin of the ray also lies on the surface of the volume. In the second, the back intersection which is closest to the origin of the ray lies on the surface of the volume. When we loop through each plane, we want to remember the furthest front intersection and the closest back intersection. After all the planes have been iterated over, we compare the furthest front intersection with the closest back intersection. If the furthest front intersection is farther than the closest back intersection, the we have the scenario in image C, and there is no intersection. If there are no front intersections at all, the ray starts inside the polyhedron. Otherwise, we can simply return the furthest front intersection as point of intersection.


I believe this method has a few advantages over storing a list of vertices and faces, including space requirements. A polyhedron needs only to store a list of planes, and a plane can be stored as a normal, and the distance of the plane to the origin (4 floating point number total). On the other hand, storing a list of faces means storing three or more vertices per face as well as normal information. I also think this method is faster than doing intersections against a face and then testing to see whether or not that point lies within the face, but I could be wrong.


Doesn’t support concave polyhedra.


You’ll notice that in the code, the class for a convex polyhedron is simply called a brush. This name is taken from some of the editors I mentioned above, where they got the name I have no idea but its a lot shorter than polyhedron. The Intersect method returns a struct that contains a variable called raydistance, which is set to infinity if there is no intersection. It has a different meaning than when the method is called with a line segment: it returns a number 0 < x < 1 such that x * ( line.start – line.end ) + line.start is the point of intersection. It may seem strange to include a method to intersect with a line segment in a ray tracer, but it will later replace the ray method when I post about kd-trees.

Also, this is the biggest bottleneck of the ray tracer. If anyone can see any possible optimizations, let me know.

Point.h | Plane.h | Plane.cpp | Brush.h | Brush.cpp

No comments