Surface Neighborhoods

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.

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 }.

Once 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);
    }
}

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 brute-force 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.

	A demonstration of the rings using the dresser model
	A demonstration of the rings using the random model
	A demonstration of the rings using the twospheres model
	A demonstration of the rings using the squares model
	A look at the effects of changing k when calculating the neighborhoods. For most models, it seems that changing the value of k slightly doesn't make much difference. It is simply an assessment of the local properties of a triangle, and a change in locality won't make much of a difference unless there are singular vertices around.
	A look at the effects of subdividing a mesh and recalculating the neighborhoods. Subdivision keeps singular vertices as singular vertices, and so the local neighborhood becomes more defined when we subdivide.