QEM_ProgMesh.cpp

// QEM_ProgMesh.cpp : Implementation for the ProgMesh class, and some related classes.
//
// Author: Matt Loper
// $Revision: 1.4 $
// $Date: 2002/05/15 08:28:12 $


#include "../common/standard.h"
#include "Matrix.h"

#include "QEM_Quadric.h"
#include "QEM_ProgMesh.h"
  
 
using namespace QEM;

void ProgMesh::recalculateCosts()
{
    int nFaces = faces.size();
    
    // Calculate a quadric for each face...
    for (int i = 0; i < nFaces; i++)
    {
        Face &f = faces[i];
        f.assertValid(i);
        Quadric q = f.calculateQuadric(i, vertices);
        
        //...and add that quadric to the quadrics of each of its three vertices
        f.getVertex(0, vertices, i).quadric += q;
        f.getVertex(1, vertices, i).quadric += q;
        f.getVertex(2, vertices, i).quadric += q;
        
        if (i%40 == 0) 
        {
//            glutSetWindowTitle (fmtString("Calculating quadrics, %.2f%% done.", (float)100 * i / nFaces));
        }
    }
    
    // For each of our edges...
//    glutSetWindowTitle (fmtString("Calculating edge costs..."));
    for (EdgePtr iter = edges.begin(); iter != edges.end(); iter++)
    {
        Edge &e = *iter;
        
        VertexQuadric v1 = vertices[e.getV1()];
        VertexQuadric v2 = vertices[e.getV2()];
        
        // ...sum up the quadrics of our neighboring vertices...
        Quadric sum = v1.quadric + v2.quadric;
        
        // and try to get an optimum point. If the quadric doesn't specify an
        // optimum, then take an average of the two points
        Vertex v;
        if (!sum.getOptimumPoint (v))
            v = (v1 + v2) / 2.;
        
        e.setCachedCost(sum.getCost(v));
    }
    
//    glutSetWindowTitle (fmtString("Sorting..."));
    
    // see Edge::operator<
    edges.sort(&vertices);
    
//    glutSetWindowTitle (fmtString("Done..."));
//    glutPostRedisplay();
}

EdgePtr ProgMesh::addEdge (int faceIndex, int /* 0, 1, or 2 */ whichEdge, int vertexIndex1, int vertexIndex2)
{
        VertexPairEdgeMap::iterator i;
        i = vertexPairEdgeMap.find (VertexPair (vertexIndex2, vertexIndex1));   

        // if this edge has a sister edge that's been added already....
        if (i != vertexPairEdgeMap.end())
        {
                int index = (*i).second;
                Face &f = faces[index/3];
                Edge &e = f.getEdge(index%3);
                e.setFace2(faceIndex,whichEdge);

                vertexPairEdgeMap.erase (i);

                return faces[index/3].getEdgePtr(index%3);
        }
        else // insert ourselves into the map
        {
                Edge newEdge(faceIndex, whichEdge, vertexIndex1, vertexIndex2);
                edges.push_front (newEdge);
                vertexPairEdgeMap[VertexPair(vertexIndex1,vertexIndex2)] = newEdge.edgeIndexFirst();
                return edges.begin();
        }
}

std::pair<int, int> findCommon(int a, int b, int c, int d)
{
        int af = a/3;
        int bf = b/3;
        int cf = c/3;
        int df = d/3;


    if (a == b || c == d)
    {
        throw "findCommon(): degeneracy occurred. No further collapses allowed. (1)";
    }
    if (af == bf || cf == df)
    {
        throw "findCommon(): degeneracy occurred. No further collapses allowed. (2)";
    }

        if (af == cf)
                a = d;
        else if (af == df)
                a = c;
        else if (bf == cf)
                b = d;
        else if (bf == df)
                b = c;
        else
    {
                throw "findCommon(): degeneracy occurred. No further collapses allowed.";
    }

        std::pair<int,int> rtn(a,b);
        rtn.first = a;
        rtn.second = b;

        return rtn;
}

bool ProgMesh::willDegenerate (EdgePtr e1, EdgePtr e2) const
{
        Edge &edge1 = *e1;
        Edge &edge2 = *e2;
/*
 * If one of the edges is a border, we know it won't degenerate
 */ 
        if (edge1.isBorder() || edge2.isBorder())
                return false;

        std::pair<int,int> p = findCommon(
                edge1.edgeIndexFirst(), 
                edge1.edgeIndexSecond(),
                edge2.edgeIndexFirst(), 
                edge2.edgeIndexSecond());
                
        int firstIndex = p.first/3;
        int secondIndex = p.second/3;
        
        int v1, v2, v3, v4, v5, v6;
        v1 = faces[firstIndex].getVertexIndex(0, firstIndex);
        v2 = faces[firstIndex].getVertexIndex(1, firstIndex);
        v3 = faces[firstIndex].getVertexIndex(2, firstIndex);
        v4 = faces[secondIndex].getVertexIndex(0, secondIndex);
        v5 = faces[secondIndex].getVertexIndex(1, secondIndex);
        v6 = faces[secondIndex].getVertexIndex(2, secondIndex);
        
        int n = 0;
        if (v1 == v4 || v1 == v5 || v1 == v6) n++;
        if (v2 == v4 || v2 == v5 || v2 == v6) n++;
        if (v3 == v4 || v3 == v5 || v3 == v6) n++;
        
        if (n > 1)
                return true;
        return false;
}


EdgePtr ProgMesh::consolidateEdges (EdgePtr e1, EdgePtr e2, int deadFaceIndex)
{
        Edge &edge1 = *e1;
        Edge &edge2 = *e2;
    
    if (!edge1.isBorder() &&
        edge1.edgeIndexFirst()/3 == edge1.edgeIndexSecond()/3)
    {
        return edges.end();
    }

    if (!edge2.isBorder() && 
        edge2.edgeIndexFirst()/3 == edge2.edgeIndexSecond()/3)
    {
        return edges.end();
    }
    
/*
 * If we're in a manifold neighborhood, we have some work to do.
 */ 
        if (!edge1.isBorder() && !edge2.isBorder())
        {
        
                // the two edges given to us have a face in common:
                // the dead face.  We want one edge, with the two
                // still-alive faces attached to it
                std::pair<int,int> p = findCommon(
                        edge1.edgeIndexFirst(), 
                        edge1.edgeIndexSecond(),
                        edge2.edgeIndexFirst(), 
                        edge2.edgeIndexSecond());


#if 0
        int v1, v2, v3, v4, v5, v6;
                int firstIndex = p.first/3;
                int secondIndex = p.second/3;
                v1 = faces[firstIndex].getVertexIndex(0, firstIndex);
                v2 = faces[firstIndex].getVertexIndex(1, firstIndex);
                v3 = faces[firstIndex].getVertexIndex(2, firstIndex);
                v4 = faces[secondIndex].getVertexIndex(0, secondIndex);
                v5 = faces[secondIndex].getVertexIndex(1, secondIndex);
                v6 = faces[secondIndex].getVertexIndex(2, secondIndex);

                int n = 0;
                if (v1 == v4 || v1 == v5 || v1 == v6) n++;
                if (v2 == v4 || v2 == v5 || v2 == v6) n++;
                if (v3 == v4 || v3 == v5 || v3 == v6) n++;
#endif

                edge1.setFace1 (p.first/3, p.first%3);
                edge1.setFace2 (p.second/3, p.second%3);

                faces[p.first/3].setEdge(p.first%3, e1);
                faces[p.second/3].setEdge(p.second%3,e1);

        edges.erase (e2);
                return e1;

        }
        // if both edges are borders, then they'll collapse
        // to nothing, and they should both just be deleted
        if (edge1.isBorder() && edge2.isBorder())
        {
                edges.erase (e1);
                edges.erase (e2);
                return edges.end();
        }

        if (edge1.isBorder())
        {
                return consolidateEdges (e2, e1, deadFaceIndex);
        }

        assert (!edge1.isBorder());
        assert (edge1.hasFirstNeighbor());

/*
 * If our second edge is a border, we need to do three things...
 */
        if (edge2.isBorder())
        {
                // (1) Erase the second edge
                edges.erase (e2);

                // (2) Edge1 points to two faces. Find the one that
                // points to the dead face.
                if (edge1.faceIndexFirst() == deadFaceIndex)
                {
                        assert (edge1.faceIndexSecond() != deadFaceIndex);
                        // (3) Turn edge1 into a border, by removing
                        // our reference to its face
                        edge1.removeFace1();
                }
                else if (edge1.faceIndexSecond() == deadFaceIndex)
                {
                        assert (edge1.faceIndexFirst() != deadFaceIndex);
                        // (3) Turn edge1 into a border, by removing
                        // our reference to its face
                        edge1.removeFace2();
                }
                else 
                        assert(!"ProgMesh::consolidateEdges(): one of the edges passed in isn't attached to a dead face");
                return e1;
        }
    else
        throw ("ProgMesh::consolidateEdges(): shouldn't ever get here!");

    return edges.end();
}



Vertex ProgMesh::getOptimumPointForEdge (Edge &edge)
{       
        Vertex optimumPoint;
        Quadric q = 
                vertices[edge.getV1()].quadric +
                vertices[edge.getV2()].quadric;

        if (!q.getOptimumPoint(optimumPoint))
        {
                VertexQuadric &v1 = vertices[edge.getV1()];
                VertexQuadric &v2 = vertices[edge.getV2()];
                optimumPoint = (v1 + v2) / 2.;
        }
    return optimumPoint;
}

void ProgMesh::reportProgress (char *str)
{

}

        
int ProgMesh::addOptimumPoint(Edge &deadEdge)
{
        Vertex optimumPoint = getOptimumPointForEdge (deadEdge);
        VertexQuadric v(
                optimumPoint[0], 
                optimumPoint[1], 
                optimumPoint[2]);

        v.quadric = vertices[deadEdge.getV1()].quadric + vertices[deadEdge.getV2()].quadric;

        vertices.push_back (v);

        int newVertexIndex = vertices.size() - 1;
        return newVertexIndex;
}



void ProgMesh::doCollapse(int finalPolygonCount)
{
    int n = 0;
    int originalPolyCount = getNumFacesTotal();
    int numToRemove = originalPolyCount - finalPolygonCount;

    reportProgress ("Collapsing...");
    
    while (faces.getNumFacesVisible() > finalPolygonCount)
    {
        doOneCollapse();
        
        n++;
        if (n % 60 == 0)
        {
            int numRemoved = originalPolyCount - faces.getNumFacesVisible();
            float percentRemoved = 100 * (float)numRemoved / numToRemove;
            
            reportProgress (fmtString ("Collapsing %.2lf%% done. %d faces, %d vertices, %d edges", 
                percentRemoved,
                faces.getNumFacesVisible(), 
                vertices.size(), 
                edges.size()));
//            glutPostRedisplay();
        }
    }
}



void ProgMesh::doOneCollapse()
{
        if (edges.empty())
                return; // nothing to collapse

/* 
 * Get the first edge from our edgelist, and calculate its optimum vertex
 */
        EdgePtr deadEdgePtr = edges.begin();
        Edge &deadEdge = *deadEdgePtr;
        int newVertexIndex = addOptimumPoint (deadEdge);

    int oldV1 = deadEdge.getV1();
    int oldV2 = deadEdge.getV2();

    if (oldV1 == oldV2)
        MTRACE("warning: collapsing degenerate edge; both vertices have index %d", oldV1);
/* 
 * Our soon-to-be-collapsed edge has two adjacent faces, which will
 * also collapse.  We can't just delete those adjacent faces, because
 * that would create holes in the mesh.  Instead, we have to sew two
 * of its edges together (the two that aren't the dead edge.  Here, we
 * just get the other two edges.  
 */
        EdgePair pairsToSew1; 
        EdgePair pairsToSew2; 

    // if our dead edge has a first neighbor...
    if (deadEdge.hasFirstNeighbor())
        {
                // ...that neighbor has two other edges. Get those edges.
                pairsToSew1 = faces[deadEdge.faceIndexFirst()].getOtherTwoEdges (deadEdgePtr);
        if (*pairsToSew1.first == *pairsToSew1.second)
        {
            (*pairsToSew1.first).printDebugString();
            (*pairsToSew1.second).printDebugString();
        }
                assert (pairsToSew1.first != pairsToSew1.second);
                assert (faces.faceIsVisible (deadEdge.faceIndexFirst()));
        }       

    // same thing, for second neighbor
    if (deadEdge.hasSecondNeighbor())
        { 
                pairsToSew2 = faces[deadEdge.faceIndexSecond()].getOtherTwoEdges (edges.begin());
        if (*pairsToSew2.first == *pairsToSew2.second)
        {
            (*pairsToSew2.first).printDebugString();
            (*pairsToSew2.second).printDebugString();
        }
                assert (pairsToSew2.first != pairsToSew2.second);
                assert (faces.faceIsVisible (deadEdge.faceIndexSecond()));
        }
/* 
 * Usually, collapses result in two dead faces. But if we're trying to
 * collapse a tetrahedron, we might end up with a non-manifold
 * surface, which we can't handle.  So here, we ask each of our dead
 * faces: "Are you part of a tetrahedron?" If they answer yes, then we
 * put off the collapse.  
 */

    if (deadEdge.hasFirstNeighbor())
    {
        if (willDegenerate(pairsToSew1.first, pairsToSew1.second))
        {
            deadEdge.setCachedCost (deadEdge.getCachedCost() + 10);
            edges.sort (&vertices);
            MTRACE("ProgMesh::doOneCollapse(): degeneracy averted\n");
            return;
        }
    }    

    if (deadEdge.hasSecondNeighbor())
    {
        if (willDegenerate(pairsToSew2.first, pairsToSew2.second))
        {
            deadEdge.setCachedCost (deadEdge.getCachedCost() + 10);
            edges.sort (&vertices);
            MTRACE("ProgMesh::doOneCollapse(): degeneracy averted\n");
            return;
        }
    }
/* 
 * When an edge collapses to an optimum point, two vertices die, and a
 * new one is born. Anything that pointed to the old vertices, now has
 * to point to the new one. Face::swapVertexIndex recursively
 * propagates the changes to the surrounding faces. (Note: our primary
 * bottleneck is is the incremental sorting routing in
 * Face::swapVertexIndex) 
 */
    if (deadEdge.hasFirstNeighbor())
        faces.swapVertexIndex (oldV1, oldV2, newVertexIndex, deadEdge.faceIndexFirst(), edges);

    if (deadEdge.hasSecondNeighbor())
        faces.swapVertexIndex (oldV1, oldV2, newVertexIndex, deadEdge.faceIndexSecond(), edges);
/*
 * Update edge <--> face connectivity, part 2
 */
    if (deadEdge.hasFirstNeighbor())
    {
                consolidateEdges (pairsToSew1.first, pairsToSew1.second, deadEdge.faceIndexFirst());
    }
        
        if (deadEdge.hasSecondNeighbor())
    {
                consolidateEdges (pairsToSew2.first, pairsToSew2.second, deadEdge.faceIndexSecond());
    }

    if (deadEdge.hasFirstNeighbor())
    {
        faces.hideFace (deadEdge.faceIndexFirst());
    }
        
        if (deadEdge.hasSecondNeighbor())
    {
        faces.hideFace (deadEdge.faceIndexSecond());
    }

    // finally, we pop the dead edge off the edge list
    edges.pop_front(); 

    // hand-sorting is performed in FaceArray::swapVertexIndex, so
    // there's no need to do a full sort here
    // edges.sort(&vertices, &faces);
}



void ProgMesh::clear() 
{
        faces.clear();
        edges.clear();
        vertices.clear();
        vertexPairEdgeMap.clear();
}



void ProgMesh::draw() const
{
        int numFaces = faces.size();

        for (int i = 0; i < numFaces; i++)
        {
                if (!faces.faceIsVisible(i))
                        continue;

                faces[i].draw(i, vertices, &colorMap);
        }       

#if 0 // little ball, to help us see where collapses take place
    if (vertices.size() > 0)
    {
        glPushMatrix();
            glTranslatef(
                vertices[vertices.size()-1][0],
                vertices[vertices.size()-1][1],
                vertices[vertices.size()-1][2]);
            glutSolidSphere(.01, 20, 20);
        glPopMatrix();
    }
#endif

}


void ProgMesh::presize (int nTriangles, int nVertices) 
{
        faces.reserve (nTriangles);
        vertices.reserve (nVertices);
}

void ProgMesh::addFace (int v1, int v2, int v3) 
{ 
        if (v1 == v2 || v2 == v3 || v1 == v3)
                throw RuntimeError("ProgMesh::addFace(): degenerate faces not accepted.");


    // this is only here to throw an exception, if we've
    // received a degenerate face.
    this->vertices[v1].getUnitLengthNormalWith(
        vertices[v2], vertices[v3]);

    int faceIndex = faces.size();

        EdgePtr e1 = addEdge (faceIndex, 0, v1, v2);
        EdgePtr e2 = addEdge (faceIndex, 1, v2, v3);
        EdgePtr e3 = addEdge (faceIndex, 2, v3, v1);
        Face newFace (e1,e2,e3);

        faces.push_back (newFace);
}



int ProgMesh::addVertex (mfloat x, mfloat y, mfloat z)
{
        VertexQuadric v(x,y,z);
        vertices.push_back (v);
        return (vertices.size() - 1);
}



int ProgMesh::addVertexWithColor (mfloat x, mfloat y, mfloat z, const RgbByte &color)
{
    int index = addVertex(x,y,z);

    colorMap[index] = color;

    return index;
}

---