6491 and 7491 PROJECTS
Alexander Powell

Surface Neighborhoods

CS6491: Computer Graphics
Alexander Powell - [ alex at powelltown dot com ]
October 21, 2003


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 details

Once again, this portion of the project was implemented mostly in the TMesh class. There are 3 new important functions:

void calculateRings(int c)

Takes in an integer, which is a corner number that specifies which triangle we're calculating rings around. Places the results into the variable rings, which is a deque of a deque. The structure of rings is such that when indexed @ 0, returns a list of corners of the triangle specified by c, and when indexed > 0, returns the list of corners on the triangles specified by the ring number around the original triangle.

void calculateNeighborhood(unsigned int k)

Takes in an unsigned integer k, which determines how far into the neighborhood we should look (see k in the definition of nbhd(k,S) above). Creates an array called nbhd which contains the colors (ranging from 0 to 1) of each of the triangles, based on how many neighbors it has.

bool isSharedVertex(int c, deque border)

Takes in a corner number c and a list of border triangles and determines if c shares a vertex location with any of the triangles in border. This function is used as a helper function to both calculateNeighborhood() and calculateRings().


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;
    counted[c] = true;
    counted[n(c)] = true;
    counted[p(c)] = true;
    numCounted += 3;
    while (numCounted < numCorners)
        std::deque<unsigned int> lastRing;
        unsigned int lastRingNum = rings.size() - 1;
        lastRing = rings[lastRingNum];
        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

                // 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;
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 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.

Results: Pictures

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.

about me