Recursive Ray Tracing

Adding real recursion to the mix (and not just basic shadow rays) gives the added benefit of effects like transmission and reflection.  By building off our phong model, we were able to recursively reflect a ray up to a given cutoff depth and modify the final color with a "reflective" float between zero and one.  Reflections is one area of 3D graphics where a ray traced model really excels.  With just a few more lines of code we were able to get results like those shown in the picture.

Ray Tracing with Phong Shading

Phong shading is very popular, supported by most graphics libraries by default, and can be implemented very easily and efficiently. That's because the model rests on a relatively simple equation. Compare this to my last post on Ray Tracing (which had no lighting model at all) and you'll see the difference is quite profound.

The polygonal floor just uses a procedural shader that verifies the row and column of the intersection point.  Hopefully we'll get around to real texture mapping some time in the future.

Update on Polygon RayCasting

My previous post on 2D Polygon Raycasting had an error at the very end of it. It turns out that it is much more useful to return the surface normal of the object which is hit and not the reflection off this normal. Finding the reflection after wards is extremely easy to find later if you still need it by merely reflecting the ray direction off this normal. However, finding the edge normal given a resulting reflection and a ray direction is much more annoying to calculate.

The final code then turns out to be the following:

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];
                        normal = Vector2.Normalize(RightPerp(edge));
                        // no reflection here
                    }
                }
            }
            return crossings > 0 && crossings % 2 == 0;
        }

A Glimpse At Shape Tesselation

Tessellation, sometimes referred to as triangulation, is an important concept in computer graphics that subdivides triangles for finer detail. I plan to write up a full post on this later. For now, here's some pictures of an old assignment I completed last quarter. You can see support for the cube,
cone, cylinder, and sphere.

A Trip Down Memory Lane

 

 

An old project I made freshmen year in a group of 4 aspiring developers. Not bad for beginners with a mere 10 weeks of time from start to finish.

Game Engines -- Not For The Squeamish

Game engines are a beautiful area of study and have always been an interest of mine. Currently, as an independent study I am writing a full 2D game engine on top of XNA. It's a lot of work, I like it, and I'm happy to be pursuing such a challenge. However, in most cases you shouldn't be writing game engines. There is a lot of general purpose code lying around out there that hasn't been used in any meaningful implementation ever. If you are looking to write your first game, going into it with the idea that you will write an engine first is very misguided for a number of reasons. For a post which nicely summarizes why see ScientificNinja's thoughts on the matter.

Write Games, Not Engines

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.