---

MeshJoin.cc

Go to the documentation of this file.

/*
    File:       MeshJoin.cc

    Notes:      Requires triangles to share a single vertex array
                
                Calling conventions: 
                    Call Init() with the number of vertices in the model
                    Call StartGroup() for each surface group
                    Call AddTriangle for all faces in that group
                    Call EndGroup() when done.
                    Repeat the last 3 calls as necessary.

    Author:     Andrew Willmott

    Notes:      
*/

#include "MeshJoin.h"

#define MJ_DBG if (0) cerr

static Int tNextEdge3[3] = { 1, 2, 0 };
static Int tNextEdge4[4] = { 1, 2, 3, 0 };

Void MeshJoin::Init(Int numVertices)
{
    vertexFaces = new FacePtr[numVertices];
    vertexEdges = new Edge[numVertices];
    SELF.numVertices = numVertices;
    surfaceVertices = numVertices;
}

Void MeshJoin::StartGroup()
{
    Int     i;

    for (i = 0; i < numVertices; i++)
        vertexFaces[i] = 0;
    for (i = 0; i < numVertices; i++)
        vertexEdges[i] = 0;
}

Bool MeshJoin::EdgesMatch(
        FacePtr face1,
        Edge    edge1,
        FacePtr face2,
        Edge    edge2
    )
{
    return(
        // shared vertex?
        (face1->index[edge1] == face2->index[edge2])
        // same normal?
        && (dot(face1->Normal(), face2->Normal()) > 0.1)
        // same material?
        && (face1->Reflectance() == face2->Reflectance())
    );
}


Void MeshJoin::AddTriangle(Face *addFace)
{
    Int     i, j, k;
    Int     n = addFace->Sides();
    Int     *nextEdge;
    FacePtr curFace, *curFacePtr;
    Edge    curEdge, *curEdgePtr;
    Int     vIndex;
    Bool    match[4];
    
    if (addFace->IsTri())
        nextEdge = tNextEdge3;
    else
        nextEdge = tNextEdge4;

    /*
        Each vertex has a list of unmatched incident edges
        (where unmatched means that we haven't found a neighbouring
        triangle along that edge.)
        When we add a triangle, we first check to see whether
        an edge is present in this list. If it is, we remove it,
        and connect the two faces along that edge. If it is not,
        we add it to the list.
    */
    
    // for all vertices...

    for (i = 0; i < n; i++)
    {
        j = nextEdge[i];    // next vertex
        k = nextEdge[j];

        addFace->clrIdx[i] = addFace->index[i];
        
        MJ_DBG << "vertex " << j << " = " << addFace->index[j] << endl;

        // Check outgoing edge against the vertex's 
        // edge list.
        
        // we will be looking at vertex j
        // incident edge is (i)->(j), outgoing edge is (j)->(k)

        vIndex = addFace->index[j];
        
        // we first check the edge list at vertex (j) and try
        // to locate an edge which starts from vertex (i).
        
        curFacePtr = &vertexFaces[vIndex];
        curEdgePtr = &vertexEdges[vIndex];
        curFace = *curFacePtr;
        curEdge = *curEdgePtr;
                
        match[j] = false;

        while (curFace)
        {
            // Do we have an edge match?
            MJ_DBG << "checking edge to vertex " << curFace->index[curEdge]
                    << endl;
            
            if (EdgesMatch(curFace, curEdge, addFace, k))
            {
                MJ_DBG << "matched." << endl;

                // Yes! remove curEdge from the list
                *curFacePtr = curFace->nbFace[curEdge];
                *curEdgePtr = curFace->nbEdge[curEdge];
                
                // connect the two triangles that share this edge
                addFace->nbFace[j] = curFace;
                addFace->nbEdge[j] = curEdge;
                curFace->nbFace[curEdge] = addFace;
                curFace->nbEdge[curEdge] = j;
                
                Assert(addFace->index[j] == curFace->index[nextEdge[curEdge]], 
                       "1st vertices");
                Assert(addFace->index[k] == curFace->index[curEdge], 
                       "2nd vertices");
                
                // and quit.
                match[j] = true;
                break;
            }

            MJ_DBG << "didn't match." << endl;

            // If not, move on to next edge...
            curFacePtr = &curFace->nbFace[curEdge];
            curEdgePtr = &curFace->nbEdge[curEdge];
            curFace = *curFacePtr;
            curEdge = *curEdgePtr;
        }
        
        // If there was no match, we add the incoming edge to the vertex's
        // edge list.
    }
    
    for (i = 0; i < n; i++)
    {
        j = nextEdge[i];    // next vertex

        if (!match[i])
        {
            vIndex = addFace->index[j];

            MJ_DBG << "adding unmatched edge " << i << " to list." << endl;
            // set this edge to point to first member of the list...
            addFace->nbFace[i] = vertexFaces[vIndex];
            addFace->nbEdge[i] = vertexEdges[vIndex];

            // then set the start of the list to point to this edge
            vertexFaces[vIndex] = addFace;
            vertexEdges[vIndex] = i;
        }
    }
}

Void MeshJoin::SetFaceChainVertices(Face *f, Int edge, Int i)
// Sets the colour index to i of all faces connected to f around
// the point at the end of 'edge'.
{
    if (!f)
        return;
        
    Int ccwEdge;

    // find the next face around the point
    if (f->IsTri())
        ccwEdge = tNextEdge3[edge];
    else
        ccwEdge = tNextEdge4[edge];
    
    f->clrIdx[ccwEdge] = i;
    
    SetFaceChainVertices(f->nbFace[ccwEdge], f->nbEdge[ccwEdge], i);
}

Void MeshJoin::EndGroup()
{
    Int     i, n;
    FacePtr curFace, nextFace;
    Edge    curEdge, nextEdge;
    
    // Finally, we pass through the vertex face lists again, and
    // set the neighbour fields of all unmatched edges to 0,
    // to mark that they're not connected to anything.
    // (We have to do this because we've been using these fields
    // to help store the unconnected edge list.)

    // For vertices that share several disconnected faces (i.e., there
    // is a surface discontinuity adjacent to the edge), we must make
    // sure that each disconnected segment has its own colour/normal
    // corresponding to that vertex. Otherwise we end up using the
    // same colour for two faces that share a vertex but are not
    // continuous.

    for (i = 0; i < numVertices; i++)
    // Cycle through the remaining unmatched edges.
    {
        // head of the edge list for this vertex
        curFace = vertexFaces[i];
        curEdge = vertexEdges[i];
                
        while (curFace)
        {
            // Store next edge...
            nextFace = curFace->nbFace[curEdge];
            nextEdge = curFace->nbEdge[curEdge];

            // clear nbFace pointer
            curFace->nbFace[curEdge] = 0;

            // move on to next edge in the list
            curFace = nextFace;
            curEdge = nextEdge;

            // Fill in a new colour index for all faces connected to this edge
            // around this vertex.
            // (Need to do this for all unmatched edges but the first one,
            // which retains its original setting.)
            if (curFace)
                SetFaceChainVertices(curFace, curEdge, surfaceVertices++);
        }
    }
}

Int MeshJoin::Finished()
{
    delete[] vertexFaces;
    delete[] vertexEdges;
    return(surfaceVertices);
}

---