Fast Triangulations

This is a project involving triangulations and ray-tracing and is a continuation of the 2D ray-tracing project.

Ray-tracing can be used to make beautifully rich and clear images but at a very big cost. It can take too much resources and time to generate these images. Imagine a 1000x1000 pixel image being generated through ray-tracer. Even if the ray-tracer was optimised fully, it would still take 1000000 rays to generate one image (or frame of animation).

I have always been interested in speeding ray tracing up. So I have been experimenting with a way of take random sample rays instead of a full array of rays, and using these random rays to generate a picture in time. So instead of speeding up the way rays hit objects, I am attempting to speed up the final render of the image so that the colors that are returned through a random set of rays can be used to construct an image. I have chosen triangulation to best handle this process. And as an experiment, this has resulted in some interesting images and animations.


[screenshot of triangulation taken from random rays of two spheres intersecting]

Note, that this project is still in progress and far from complete. This project started as a ray tracing implementation and has turned into an image filter or shader that can be used in many applications, such as triangulations of images, and even mapping 3D objects in real time.

Delaunay triangulation provides a very fast and easy way to create triangulations given points. The algorithm I used implemented an incremental version using Lawson’s Incremental Insertion Algorithm (which is actually really hard to find on the Internet). Lawson's is perfect for what we need, and we can even speed up the algorithm because we don't even need a perfect Delaunay triangulation, but maybe 80% of triangles are Delaunay (This is just an excuse to say that my algorithm for creating Delaunay triangulations sucks, but is fast).

Why do we want Delaunay triangles? Well if try to create a triangulation ourselves with a given set of random points, by say trisecting every existing triangle a points lands on then the triangles start to look too long and slim since almost every triangle lies within another triangle. Delaunay triangles look nice and make shading between vertices smooth.


[Delaunay triangles with circumcircles]

These triangles hold the property that each triangles circumcircle (circle created from the three vertices of a triangle) only contain its own vertices and no other vertices of any other neighbouring triangles. For a better definition see the wikipedia entry here. If a triangle isn't Delaunay we can flip an edge and if needed flip neighbour edges, until triangles are Delaunay.


[Delaunay before and after flip]

So the Lawson's Algorithm I used is as follows:

  1. Locate the triangle containing the insertion site
  2. Trisect the triangle and add all the edges involved in a queue
  3. While the queue is not empty, perform an in-circle test on each queue.pop:
    • If the edge fails, flip it and add its four neighbour edges back onto the queue
    • Else try the next edge in the queue

This is guaranteed to to terminate, but it can take long (although for random points the expected number of flips is O(1)) so I ruined the algorithm by only performing the test on the first neighbours and since my data sets don't use edges and only neighbouring triangles, I had to modify my algorithm for this.

One of the largest problems with this algorithm is the "#1 Locate the triangle containing the insertion site". Straight forward insertions can result in O(n) search for searching every triangle. I implemented a slightly better approach which seems to improve by more than half expected (more like O(n/4) maybe. This approach runs an insertion test on each edge of a triangle by checking the dot product to the normal of the edge, if the point is outside of that edge, then we try a connecting triangle that is opposite of that edge. This really helps if you use good data structures for accessing your triangles. Here is the data structure I used for the triangles:
struct TRIANGLE { VECTOR* v[3]; // vertices TRIANGLE* n[3]; // neighbour triangles int e[3]; // neighbour vertex that is opposite this triangle }; As you might have noticed, I don't use edges, but we can determine the edges from the 3 vertices. I store the neighbouring triangle in the array n if it is opposite to v. So for example, n[1] is the triangle opposite to the vertex v[1]. Also the e[1] contains the index of the neighbouring triangle's neighbour of this triangle (really... how can you possibly understand this gibberish). For example, n[2]->n[ e[2] ] == this triangle. Using this dataset for triangles, we can quickly trisect, flip, and perform circle-tests, and also search through neighbouring triangles fast(er). Of course, even after using a neighbour search algorithm for searching for the insertion triangle is still slow. A better approach would be to use spatial indexing such as binary trees (which is a pain to implement and maintain on a changing triangulation), or even Quad trees.

Here is the code for my circle-test, which I created from finding the determinant:

BOOL circleTest( x1, y1, x2, y2, x3, y3, VERTEX v ) float pxs = v->x * v->x; float pys = v->y * v->y; float a = x1 - v->x; float b = y1 - v->y; float c = (x1 * x1 - pxs) + (y1 * y1 - pys); float d = x2 - v->x; float e = y2 - v->y; float f = (x2 * x2 - pxs) + (y2 * y2 - pys); float g = x3 - v->x; float h = y3 - v->y; float i = (x3 * x3 - pxs) + (y3 * y3 - pys); float det = a*e*i - a*f*h + b*f*g - b*d*i + c*d*h - c*e*g; return det > 0;

Here is a small triangulation I produced from random points and colours:


[First Triangulation produced]

This is a sample of lines used to draw the triangulation from intersecting spheres. Note that somewhere the lines were offset because lines use two vertices and triangles use three.


[Triangulation in lines]

And here is a final image resulting from ray-traced intersecting spheres


[Final triangulation]

Where do we go from here?

Its not perfect. The triangle search is still very slow, but this can be improved with better spatial indexing techniques. Triangles against edges look horrible. Triangles that contain dramatically different coloured vertices should provide information to help provide where the next random vertex should be fired. The closer the triangles are to the edges of the sphere, the more clear the sphere will look when rendered. So I shouldn't have an equally distributed set of random locations, but more random locations closer to edges (or dramatic colour variances).

I would also like to take this project further in making it the graphics engine for a game, but this might be a ways off. Some other interesting things from this might be too attempt to create 3D scanners implemented from this from images or movies. Ideally a ray-tracer could utilize this and it wouldn't depend on how fast the computer ran, because a faster computer should be able to produce better images but a slower computer could still render the scene in real-time but in less quality.