Introducing SRT

A few weeks ago I finished an early version of a ray tracer written in completely standard ANSI C.  I undertook this small project for a number of reasons.  It dawned on me that most of the work I had been doing involved an environment with an IDE and an object oriented language.  While this isn't an inherently bad thing, it is healthy to stay proficient in as many paradigms as possible.  Therefore, I decided I was going to do a project in straight C with MinGW and Notepad++ to remind myself that you can do everything without polymorphism, inheritance, and encapsulation.  The end goal was a simple raytracer with an interface that mimicked Open GL.  Since I decided to use SDL for software pixel operations I decided to call the project SRT, for "SDL Ray Tracer."  The acronym is just as viable for "Simple Ray Tracer."  Feel free to browse the project in its early form on Google Code at the link below.  Hopefully the project will be seen on GitHub someday too.

Browse SRT on GitHub

Browse SRT on Google Code

Basic features of SRT include the following:

• Raycasting support for multiple shapes, including spheres, 3D planar polygons, and oriented bounding boxes (OBBs)
• Support for typical 3D transformations, vector, and matrix operations.  The "Projection" and "ModelView" matrices can be translated, rotated, and scaled.
• Material and lighting support, with full RGBA channels for ambient, diffuse, and specular colors.  Materials also include scalar values for reflectivity and transmission (transparency).  Phong illumination included by default.
• Optional support for super sampling, control over recursive depth and other parameters for scene lighting.
• Although only tested on Windows, should support all the platforms and resolutions that SDL supports.
• Typedefs and macros provide support for single or double floating point precision, and assertions which can be omitted from "release" code.
• Future releases will hopefully support multiple light sources, orthographic projections, manipulation of the matrix stack, texture mapping, and thread support.

A typical program for SRT might resemble the following.  Note the resemblance to a typical Open GL program.

-- Init Function --
srtCreateWindow(800, 600, "SRT: SDL Ray Tracer");
srtPerspective(45.0, 800.0 / 600.0, 1.0);

-- Draw Function--
/* clear buffer */
srtClearColor3(0.05f, 0.05f, 0.05f);
srtClear();
srtBeginScene();

/* move camera 4.5 units backs */
srtMatrixMode(SRT_PROJECTION);
srtTranslate(0.0, 0.0, 4.5);

/* load identity modelview */
srtMatrixMode(SRT_MODELVIEW);
srtLoadIdentity();

/* setup a light */
srtLightAmbient4(0.065f, 0.065f, 0.065f, 0.15f);
srtLightDiffuse4(0.35, 0.35, 0.35, 0.35);
srtLightSpecular4(0.25, 0.25, 0.25, 0.85);
srtLightPosition3(-1.0, 1.1, -0.75);

/* setup a material */
srtMatAmbient4(1.0, 0.0, 0.0, 1.0);
srtMatDiffuse4(0.45, 0.45, 0.45, 0.75);
srtMatSpecular4(0.3, 0.3, 0.3, 0.35);
srtMatShininess(2.8);
srtMatReflectivity(0.45);

/* sphere: x, y, z, radius */
srtCreateSphere4(1.1, -0.85, -4.5, 0.65);

/* finish the scene */
srtEndScene();
srtPaintBuffer();
srtFlip();

2D Polygon - Raycasting

Synopsis
Ever write a 2D game that supported convex polygons? Ever struggle to find good sources for ray casting onto polygons in 2D space?

Ironically, in 3D you'll find a number of different sources for Ray-Polygon intersection. Unless BSP trees are in use it usually involves some procedure resembling the following:

1) Derive a plane for the polygon, generally using the surface normal.
2) Find the intersection point of the ray and the plane (if any)
3) See if the polygon contains the point. There are a number of ways to do this, most notably using a binary search and seeing if the new point constructs a CCW triangle.

In 2D, the test can't really work this way. Instead we need to test the ray against each segment of the polygon. You might assume that if any intersection with a segment is found, we can conclude there is a valid intersection. However, this is not the case. There are two reasons we can't do an "early out" test in which the algorithm terminates with a true result if just one of the segments is intersected by the ray.

1) If a polygon contains the ray origin, there is no intersection. A usual PolygonContainsPoint() implementation can serve as a reasonably fast prerequisite test. However, it would be faster if we used the ray casting algorithm. If you read up on the algorithm you'll see it involves casting onto every segment and counting the number of crossings. With an even number, we can conclude the origin is outside the polygon, otherwise it resides inside of it.
2) When ray casting against a polygon we'll usually want far more information than just a boolean result. We'll usually want the distance of the ray, the contact point, and the normal of the ray intersection. In all these cases, we'll always want the closest intersection point. To definitively find it we'll need to test against every segment anyways. Running a contains method won't result in twice as many iterations (since it uses a binary search), but it will result in more than just one sweep of the polygon.

Ray-Segment Test

The ray segment test in 2D can be solved parametrically, as explained here. First we check if the ray direction and the segment are parallel, in which case we can quickly cancel out the possibility of a collision*. Then we solve for s and t. S must be a value between 0 and 1 to lie on the segment. T must be between zero (or some other user defined min value) and the max t value.

* This is false for collinear segments and rays. I have not found a clean and efficient way to deal with this case. If you have a suggestion, comment below. Using distance checks will work, but is an ugly way to check if a point is within the range of tmax. The normal in this case would probably have to be the ray direction reflected off the vertex normal.

And of course, the code for the test. Please note that LeftPerp(v) = (v.Y, -v.X). The special equals call simply checks if the value is within epsilon distance from zero. Please note that Epsilon is rarely the most appropriate tolerance value, but what is varies widely depending on your units and scaling and I found it was sufficient towards understanding the algorithm itself.  Still: numerical robustness matters!

public static bool RayIntersectsSegment(Ray ray, Vector2 pt0, Vector2 pt1, float tmax, out float t) {
    Vector2 seg = pt1 - pt0;
    Vector2 segPerp = LeftPerp(seg);
    float perpDotd = Vector2.Dot(ray.Direction, segPerp);
    if (Equals(perpDotd, 0.0f, float.Epsilon))
    {
        t = float.MaxValue;
        return false;
    }

    Vector2 d = pt0 - ray.Origin;

    t = Vector2.Dot(segPerp, d) / perpDotd;
    float s = Vector2.Dot(LeftPerp(ray.Direction), d) / perpDotd;

    return t >= 0.0f && t <= tmax && s >= 0.0f && s <= 1.0f;
}

Ray-Polygon Test
The final ray polygon test brings all of this together in a relatively simple way. As we iterate through the polygon we test every edge. If there is an intersection we increment the number of crossings. If the distance is less than the current minimum distance we now have a new closest intersection, and we proceed to calculate the normals and contact point for this edge. If the number of crossings is even and greater than zero at the end of the test, a true result is returned and the current distance, contact point, and normal are used.

Contact point shown in light green, ray reflection normal in purple

Update: The purple line above is actually drawing the reflection of the ray off the normal, not the edge normal itself.  The below code has been corrected to return the edge normal.  In practice, it is much more useful than the reflection (which can always be calculated afterwards using the normal if you need it).

public static bool RayCast(Ray ray, Polygon polygon, float tmax, out float t, out Vector2 pt, out Vector2 normal)
        {
            t = float.MaxValue;
            pt = ray.Origin;
            normal = ray.Direction;
            
            // temp holder for segment distance
            float distance;
            int crossings = 0;

            for (int j = polygon.NumVertices - 1, i = 0; i < polygon.NumVertices; j = i, i++)
            {
                if (RayIntersectsSegment(ray, polygon.v[j], polygon.v[i], float.MaxValue, out distance))
                {
                    crossings++;
                    if (distance < t && distance <= tmax)
                    {
                        t = distance;
                        pt = ray.GetPoint(t);

                        Vector2 edge = polygon.v[j] - polygon.v[i];
                        // We would use LeftPerp() if the polygon was
                        // in clock wise order
                        normal = Vector2.Normalize(RightPerp(edge));
                    }
                }
            }
            return crossings > 0 && crossings % 2 == 0;
        }

In this implementation, it is assumed that the polygon is a convex array of vertices in Counter Clockwise Order. This is why we reflect off the right perpendicular of the edge. If your implementation uses Clockwise polygons you'll want to use LeftPerp() instead. Here's a reference of the helper functions:

public static Vector2 LeftPerp(Vector2 v)
        {
            return new Vector2(v.Y, -v.X);
        }

        public static Vector2 RightPerp(Vector2 v)
        {
            return new Vector2(-v.Y, v.X);
        }

Happy raycasting!

Ray Tracing

For my Computer Graphics class this quarter I've been tasked with building a relatively robust ray tracer. This has involved math for transformations, setting up an image plane, ray-casting onto certain shapes, and much, much more. The requirements for the project build up as we progress throughout the quarter. Here's our latest early checkpoint with no lighting and no recursive ray casting.

It's worth noting that super sampling is used in the screenshot on the right. Super sampling basically involves casting multiple, close but still marginally displaced rays, and averaging the results. Click here to see the scene without super sampling enabled.

Our next checkpoint will involve implementing Phong shading. I'll try to post screenshots and give tips on the implementation when it is finished.