6491 and 7491 PROJECTS Alexander Powell 

Surface NeighborhoodsCS6491: Computer GraphicsAlexander Powell  [ alex at powelltown dot com ] October 21, 2003 Description This part of the project implements a couple of triangle mesh algorithms which help us understand the neighborhood makeup of each of our triangles in our models. The Algorithms (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 nbhd(k,S) as the set of triangles { B: dist(B,S) <= k }. We define ring(k,S) as the set of triangles { B: dist(B,S) = k }. We define grow(S) as the union of S with { B: dist(B,S) = 1 }. Implementation detailsOnce again, this portion of the project was implemented mostly in the TMesh class. There are 3 new important functions:
Here's some code for the calculateRings() method. The calculateNeighborhood() function uses this same method to find adjacent vertices to the current border of triangles. Its not too efficient, but it works, and for reasonably small meshes, it works fast enough. void TMesh::calculateRings(int c) { unsigned int numCorners = numTriangles * 3; unsigned int numCounted = 0; bool counted[numCorners]; for (unsigned int cc = 0; cc < numCorners; cc++) counted[cc] = false; std::deque<unsigned int> cur; cur.push_back(c); counted[c] = true; counted[n(c)] = true; counted[p(c)] = true; numCounted += 3; rings.clear(); rings.push_back(cur); while (numCounted < numCorners) { std::deque<unsigned int> lastRing; unsigned int lastRingNum = rings.size()  1; lastRing = rings[lastRingNum]; cur.clear(); for (unsigned int ii = 0; ii < numCorners; ii++) { if ((counted[ii] == false) && // We haven't placed this corner into any bins yet (isSharedVertex(ii, lastRing))) // This vertex also occurs on our previous border { // Add this triangle to the current ring number cur.push_back(ii); // Mark this triangle as being counted already so we don't bother with it again counted[ii] = true; counted[n(ii)] = true; counted[p(ii)] = true; numCounted += 3; } } rings.push_back(cur); } }Results: Algorithmic Complexity/Speed These functions seem to run pretty slow on my laptop, but run quite fast (roughly 10 times as fast) on my PC at home. I'd say for reasonably fast computers (and reasonably small meshes), this bruteforce method is good enough. Both the neighborhoods and rings methods run in O(n^2), which means that with each successive subdivision, the algorithm takes 16 times as long to run. In my tests, the results were consistently within only a small percentage of slowing down 16 times each subdivision, demonstrating that the majority of time spent is in the inner loops. Times on my laptop were roughly 20 seconds to calculate both neighborhoods and rings for meshes of 1500 triangles. Results: Pictures 

