Isolation

This part of the project is an implementation of an algorithm that measures how isolated some regions are in a triangle mesh.

We define dist(A,S) from triangle A to set of triangles S as 1+min(n), such that there exists a triangle B in S and a series of triangles T1, T2, T3 ... Tn and such that consecutive elements in the ordered list (A, T1, T2, T3 .. Tn, B) touch. In other words, dist(A, S) returns the length of the minimum path when hopping along the mesh from one triangle to another.

We define I(A) of triangle A as the sum of dist(A,B) over all triangles B

Once again, this portion of the project was implemented mostly in the TMesh class. There is 1 new important function (calculating isolation regions takes place in the drawSelf() method and therefore isn't mentioned here):

Here's the code for the calculateIsolation() method.

void TMesh::calculateIsolation()
{
    unsigned int numCorners = numTriangles * 3;
    maxIsolation = 0;
    minIsolation = 9999999;
    if (isolation != NULL)
        delete []isolation;
    isolation = new unsigned int[numCorners];
    for (unsigned int cc = 0; cc < numCorners; cc++)
		isolation[cc] = 0;
    
    for (unsigned int c = 0; c < numCorners; c += 3)
    {
        // Isolation is the sum of:
        //    the number of triangles in each level of the rings
        //    multiplied by the level number
        calculateRings(c);
        for (unsigned int ii = 0; ii < rings.size(); ii++)
        {
            isolation[c] += rings[ii].size() * ii;
        }
        // Find the max and min isolation so we can scale the color values to [0,1]
        if (isolation[c] > maxIsolation)
            maxIsolation = isolation[c];
        if (isolation[c] < minIsolation)
            minIsolation = isolation[c];
		
		// Isolation for each corner on this triangle is the same
		// We could just store isolation once per triangle, but storing
		// it for each corner makes us have to rewrite less of the drawing
		// method, and memory is cheap  :-)
		isolation[n(c)] = isolation[c];
		isolation[p(c)] = isolation[c];
		if ((c % 50) == 0) cout << "Corner number: " << c << endl;
    }
}

The isolation measure is an extremely slow calculation. The algorithmic complexity of calculateRings is O(n^2), where n is the number corners in the triangle mesh. This makes the algorithmic complexity of the isolation measue O(n^3), which isn't a horrible asymptotic complexity, but in real life we often deal with very large triangle meshes and the constant inner loop cost can be significant. This algorithm is completely unbearable to run on my laptop (i.e. takes 8-9 hours to process a reasonable triangle mesh), and even takes several minutes to run on my desktop as well.

Because of how slow this routine runs, it was obvious that I would need some way to cache the data so that I didn't have to recalculate it each time I ran the program. So, the program writes out a file each time it successfully calculates the isolation for every triangle. This file is practically a straight dump of the contents of the isolation table, but allows us to skip the isolation step when we're debugging. Loading the file for even large triangle meshes only takes roughly 1-10 ms.

	A demonstration of the isolation measure on the dresser model. The top picture shows the raw isolation data, where the red regions are those which have the highest isolation measure. The second picture is a demonstration of selection of isolation regions based on the r/10 criteria. Notice that the r/10 criteria was only successful is finding two regions, both on the back of the dresser model (see the bottom left and upper left corners of the picture, triangles in red). The third picture shows what r/5 criteria would produce, which now includes the front drawer of the dresser as well.
	A demonstration of the isolation measure on the chair model. Once again, the top pictures is the raw isolation measurements, normalized from green to red. The middle picture shows a red region found by r/10 criteria. Since it is the only region found, the entire mesh is considered in the same isolation region, and therefore r/10 is a bad choice here. The third picture is r/5 which isolates the legs and the back of the chair pretty well.
	A demonstration of the rings using the coolness model. On the r/10 picture, only a few of the triangles in the back of the model were found, and only one region was found. Using r/5, however, we also found the inside back of the model, which is useful in separating the model into several isolated regions.
	A demonstration of the rings using the fingers model. Here, the model was specifically made to test the isolation method. This is also an example where r/10 actually outperforms r/5 since the regions found in r/5 start to overlap, thereby reducing the number of total regions. Using r/10 correctly finds the 4 desired isolation regions, whereas using r/5 only finds the two major regions.

Separating the meshes into isolation regions was pretty successful, though it took a few attempt at different r/x values before the proper x was found. Using r/10 was unsuccessful in most cases, since it failed to find regions unless they were really isolated. Maybe on more complicated, arbitrary meshes, r/10 would work. But it would still be my recommendation to leave that parameter up to the user.