6491 and 7491 PROJECTS Alexander Powell 

IsolationCS6491: Computer GraphicsAlexander Powell  [ alex at powelltown dot com ] November 25, 2003 Description This part of the project is an implementation of an algorithm that measures how isolated some regions are in a triangle mesh. The Algorithm (slightly paraphrased from the class webpage)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 Implementation detailsOnce 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; } }Results: Algorithmic Complexity/Speed 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 89 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 110 ms. Results: PicturesSeparating 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.


