Merge

--HG--
branch : trunk

1 files changed, 729 insertions, 0 deletions

diff --git a/externals/g3dlite/G3D.lib/source/MeshAlgAdjacency.cpp b/externals/g3dlite/G3D.lib/source/MeshAlgAdjacency.cpp
new file mode 100644
index 00000000000..a8b35f32c86
--- /dev/null
+++ b/externals/g3dlite/G3D.lib/source/MeshAlgAdjacency.cpp
@@ -0,0 +1,729 @@
+/**
+  @file MeshAlgAdjacency.cpp
+
+  @maintainer Morgan McGuire, matrix@graphics3d.com
+  @created 2003-09-14
+  @edited  2005-02-24
+
+  Copyright 2000-2003, Morgan McGuire.
+  All rights reserved.
+
+ */
+
+#include "G3D/Table.h"
+#include "G3D/MeshAlg.h"
+#include "G3D/Set.h"
+
+
+namespace G3D {
+
+/**
+ A half [i.e. directed] edge.
+ */
+class MeshDirectedEdgeKey {
+public:
+
+    /** vertexIndex[0] <= vertexIndex[1] */
+    int     vertexIndex[2];
+
+    MeshDirectedEdgeKey() {}
+    
+    MeshDirectedEdgeKey(
+        const int        i0,
+        const int        i1) {
+
+        if (i0 <= i1) {
+            vertexIndex[0] = i0;
+            vertexIndex[1] = i1;
+        } else {
+            vertexIndex[0] = i1;
+            vertexIndex[1] = i0;
+        }
+    }
+
+
+    bool operator==(const MeshDirectedEdgeKey& e2) const {
+        for (int i = 0; i < 2; ++i) {
+            if (vertexIndex[i] != e2.vertexIndex[i]) {
+                return false;
+            }
+        }
+        return true;
+    }
+};
+
+}
+
+template<> struct HashTrait<G3D::MeshDirectedEdgeKey> {
+    static size_t hashCode(const G3D::MeshDirectedEdgeKey& key) { 
+        return key.vertexIndex[0] + (key.vertexIndex[1] << 16);
+    }
+};
+
+namespace G3D {
+
+/**
+ A hashtable mapping edges to lists of indices for
+ faces.  This is used instead of Table because of the
+ special logic in insert.
+
+ Used only for MeshAlg::computeAdjacency.
+
+ In the face lists, index <I>f</I> >= 0 indicates that
+ <I>f</I> contains the edge as a forward edge.  Index <I>f</I> < 0 
+ indicates that ~<I>f</I> contains the edge as a backward edge.
+ */
+class MeshEdgeTable {
+public:
+    typedef Table<MeshDirectedEdgeKey, Array<int> > ET;
+
+private:
+    
+    ET                   table;
+
+public:
+    
+    /**
+     Clears the table.
+     */
+    void clear() {
+        table.clear();
+    }
+    
+    /**
+     Inserts the faceIndex into the edge's face list.
+     The index may be a negative number indicating a backface.
+     */
+    void insert(const MeshDirectedEdgeKey& edge, int faceIndex) {
+        
+        // debugAssertM((table.size() > 20) && (table.debugGetLoad() < 0.5 || table.debugGetNumBuckets() < 20),
+        //    "MeshEdgeTable is using a poor hash function.");
+
+        if (! table.containsKey(edge)) {
+            // First time
+            Array<int> x(1);
+            x[0] = faceIndex;
+            table.set(edge, x);
+        } else {
+            table[edge].append(faceIndex);
+        }
+    }
+
+    /**
+     Returns the face list for a given edge
+     */
+    const Array<int>& get(const MeshDirectedEdgeKey& edge) {
+        return table[edge];
+    }
+
+    ET::Iterator begin() {
+        return table.begin();
+    }
+
+    const ET::Iterator end() const {
+        return table.end();
+    }
+
+};
+
+
+/**
+ edgeTable[edgeKey] is a list of faces containing
+ 
+ Used and cleared by MeshModel::computeAdjacency()
+ */
+static MeshEdgeTable            edgeTable;
+
+/**
+ Assigns the edge index into the next unassigned edge
+ index.  The edge index may be negative, indicating
+ a reverse edge.
+ */
+static void assignEdgeIndex(MeshAlg::Face& face, int e) {
+    for (int i = 0; i < 3; ++i) {
+        if (face.edgeIndex[i] == MeshAlg::Face::NONE) {
+            face.edgeIndex[i] = e;
+            return;
+        }
+    }
+
+    debugAssertM(false, "Face has already been assigned 3 edges");
+}
+
+
+void MeshAlg::computeAdjacency(
+    const Array<Vector3>&   vertexGeometry,
+    const Array<int>&       indexArray,
+    Array<Face>&            faceArray,
+    Array<Edge>&            edgeArray,
+    Array< Array<int> >&    adjacentFaceArray) {
+
+    Array<Vertex> vertexArray;
+
+    computeAdjacency(vertexGeometry, indexArray, faceArray, edgeArray, vertexArray);
+
+    // Convert the vertexArray into adjacentFaceArray
+    adjacentFaceArray.clear();
+    adjacentFaceArray.resize(vertexArray.size());
+    for (int v = 0; v < adjacentFaceArray.size(); ++v) {
+        adjacentFaceArray[v] = vertexArray[v].faceIndex;
+    }
+}
+
+
+void MeshAlg::computeAdjacency(
+    const Array<Vector3>&   vertexGeometry,
+    const Array<int>&       indexArray,
+    Array<Face>&            faceArray,
+    Array<Edge>&            edgeArray,
+    Array<Vertex>&          vertexArray) {
+    
+    edgeArray.clear();
+    vertexArray.clear();
+    faceArray.clear();
+    edgeTable.clear();
+    
+    // Face normals
+    Array<Vector3> faceNormal;
+
+    // This array has the same size as the vertex array
+    vertexArray.resize(vertexGeometry.size());
+
+    // Iterate through the triangle list
+    for (int q = 0; q < indexArray.size(); q += 3) {
+
+        Vector3 vertex[3];
+        int f = faceArray.size();
+        MeshAlg::Face& face = faceArray.next();
+
+        // Construct the face
+        for (int j = 0; j < 3; ++j) {
+            int v = indexArray[q + j];
+            face.vertexIndex[j] = v;
+            face.edgeIndex[j]   = Face::NONE;
+
+            // Store back pointers in the vertices
+            vertexArray[v].faceIndex.append(f);
+
+            // We'll need these vertices to find the face normal
+            vertex[j]           = vertexGeometry[v];
+        }
+
+        // Compute the face normal
+        Vector3 N = (vertex[1] - vertex[0]).cross(vertex[2] - vertex[0]);
+        faceNormal.append(N.directionOrZero());
+
+        static const int nextIndex[] = {1, 2, 0};
+
+        // Add each edge to the edge table.
+        for (int j = 0; j < 3; ++j) {
+            const int      i0 = indexArray[q + j];
+            const int      i1 = indexArray[q + nextIndex[j]];
+
+            const MeshDirectedEdgeKey edge(i0, i1);
+
+            if (i0 == edge.vertexIndex[0]) {
+                // The edge was directed in the same manner as in the face
+                edgeTable.insert(edge, f);
+            } else {
+                // The edge was directed in the opposite manner as in the face
+                edgeTable.insert(edge, ~f);
+            }
+        }
+    }
+    
+    // For each edge in the edge table, create an edge in the edge array.
+    // Collapse every 2 edges from adjacent faces.
+
+    MeshEdgeTable::ET::Iterator cur = edgeTable.begin();
+    MeshEdgeTable::ET::Iterator end = edgeTable.end();
+
+    Array<Edge> tempEdgeArray;
+    while (cur != end) {
+        MeshDirectedEdgeKey&  edgeKey        = cur->key; 
+        Array<int>&           faceIndexArray = cur->value;
+
+        // Process this edge
+        while (faceIndexArray.size() > 0) {
+
+            // Remove the last index
+            int f0 = faceIndexArray.pop();
+
+            // Find the normal to that face
+            const Vector3& n0 = faceNormal[(f0 >= 0) ? f0 : ~f0];
+
+            bool found = false;
+
+            // We try to find the matching face with the closest
+            // normal.  This ensures that we don't introduce a lot
+            // of artificial ridges into flat parts of a mesh.
+            double ndotn = -2;
+            int f1 = -1, i1 = -1;
+            
+            // Try to Find the face with the matching edge
+            for (int i = faceIndexArray.size() - 1; i >= 0; --i) {
+                int f = faceIndexArray[i];
+
+                if ((f >= 0) != (f0 >= 0)) {
+                    // This face contains the oppositely oriented edge
+                    // and has not been assigned too many edges
+
+                    const Vector3& n1 = faceNormal[(f >= 0) ? f : ~f];
+                    double d = n1.dot(n0);
+
+                    if (found) {
+                        // We previously found a good face; see if this
+                        // one is better.
+                        if (d > ndotn) {
+                            // This face is better.
+                            ndotn = d;
+                            f1    = f;
+                            i1    = i;
+                        }
+                    } else {
+                        // This is the first face we've found
+                        found = true;
+                        ndotn = d;
+                        f1    = f;
+                        i1    = i;
+                    }
+                }
+            }
+
+            // Create the new edge
+            int e = tempEdgeArray.size();
+            Edge& edge = tempEdgeArray.next();
+            
+            edge.vertexIndex[0] = edgeKey.vertexIndex[0];
+            edge.vertexIndex[1] = edgeKey.vertexIndex[1];
+
+            if (f0 >= 0) {
+                edge.faceIndex[0] = f0;
+                edge.faceIndex[1] = Face::NONE;
+                assignEdgeIndex(faceArray[f0], e); 
+            } else {
+                // The face indices above are two's complemented.
+                // this code restores them to regular indices.
+                debugAssert((~f0) >= 0);
+                edge.faceIndex[1] = ~f0;
+                edge.faceIndex[0] = Face::NONE;
+
+                // The edge index *does* need to be inverted, however.
+                assignEdgeIndex(faceArray[~f0], ~e); 
+            }
+
+            if (found) {
+                // We found a matching face; remove both
+                // faces from the active list.
+                faceIndexArray.fastRemove(i1);
+
+                if (f1 >= 0) {
+                    edge.faceIndex[0] = f1;
+                    assignEdgeIndex(faceArray[f1], e); 
+                } else {
+                    edge.faceIndex[1] = ~f1;
+                    assignEdgeIndex(faceArray[~f1], ~e); 
+                }
+            }
+        }
+
+        ++cur;
+    }
+
+    edgeTable.clear();
+
+    // Move boundary edges to the end of the list and then
+    // clean up the face references into them
+    {
+        // Map old edge indices to new edge indices
+        Array<int> newIndex(tempEdgeArray.size());
+
+
+        // Index of the start and end of the edge array
+        int i = 0;
+        int j = tempEdgeArray.size() - 1;
+
+        edgeArray.resize(tempEdgeArray.size());
+        for (int e = 0; e < tempEdgeArray.size(); ++e) {
+            if (tempEdgeArray[e].boundary()) {
+                newIndex[e] = j;
+                --j;
+            } else {
+                newIndex[e] = i;
+                ++i;
+            }
+            edgeArray[newIndex[e]] = tempEdgeArray[e];
+        }
+
+        debugAssertM(i == j + 1, "Counting from front and back of array did not match");
+
+        // Fix the faces
+        for (int f = 0; f < faceArray.size(); ++f) {
+            Face& face = faceArray[f];
+            for (int q = 0; q < 3; ++q) {
+                int e = face.edgeIndex[q];
+                if (e < 0) {
+                    // Backwards edge; twiddle before and after conversion
+                    face.edgeIndex[q] = ~newIndex[~e];
+                } else {
+                    // Regular edge; remap the index
+                    face.edgeIndex[q] = newIndex[e];
+                }
+            }
+        }
+    }
+
+    // Now order the edge indices inside the faces correctly.
+    for (int f = 0; f < faceArray.size(); ++f) {
+        Face& face = faceArray[f];
+        int e0 = face.edgeIndex[0];
+        int e1 = face.edgeIndex[1];
+        int e2 = face.edgeIndex[2];
+
+        // e0 will always remain first.  The only 
+        // question is whether e1 and e2 should be swapped.
+    
+        // See if e1 begins at the vertex where e1 ends.
+        const int e0End = (e0 < 0) ? 
+            edgeArray[~e0].vertexIndex[0] :
+            edgeArray[e0].vertexIndex[1];
+
+        const int e1Begin = (e1 < 0) ? 
+            edgeArray[~e1].vertexIndex[1] :
+            edgeArray[e1].vertexIndex[0];
+
+        if (e0End != e1Begin) {
+            // We must swap e1 and e2
+            face.edgeIndex[1] = e2;
+            face.edgeIndex[2] = e1;
+        }
+    }
+
+    // Fill out the edge adjacency information in the vertex array
+    for (int e = 0; e < edgeArray.size(); ++e) {
+        const Edge& edge = edgeArray[e];
+        vertexArray[edge.vertexIndex[0]].edgeIndex.append(e);
+        vertexArray[edge.vertexIndex[1]].edgeIndex.append(~e);
+    }
+}
+
+
+void MeshAlg::weldBoundaryEdges(
+    Array<Face>&       faceArray,
+    Array<Edge>&       edgeArray,
+    Array<Vertex>&     vertexArray) {
+
+    // Copy over the original edge array
+    Array<Edge> oldEdgeArray = edgeArray;
+
+    // newEdgeIndex[e] is the new index of the old edge with index e
+    // Note that newEdgeIndex[e] might be negative, indicating that
+    // the edge switched direction between the arrays.
+    Array<int> newEdgeIndex(edgeArray.size());
+    edgeArray.resize(0);
+
+    // boundaryEdgeIndices[v_low] is an array of the indices of 
+    // all boundary edges whose lower vertex is v_low.
+    Table<int, Array<int> > boundaryEdgeIndices;
+
+    // Copy over non-boundary edges to the new array
+    for (int e = 0; e < oldEdgeArray.size(); ++e) {
+        if (oldEdgeArray[e].boundary()) {
+
+            // Add to the boundary table
+            const int v_low = iMin(oldEdgeArray[e].vertexIndex[0], oldEdgeArray[e].vertexIndex[1]);
+            if (! boundaryEdgeIndices.containsKey(v_low)) {
+                boundaryEdgeIndices.set(v_low, Array<int>());
+            }
+            boundaryEdgeIndices[v_low].append(e);
+
+            // We'll fill out newEdgeIndex[e] later, when we find pairs
+
+        } else {
+
+            // Copy the edge to the new array
+            newEdgeIndex[e] = edgeArray.size();
+            edgeArray.append(oldEdgeArray[e]);
+
+        }
+    }
+
+
+    // Remove all edges from the table that have pairs.
+    Table<int, Array<int> >::Iterator cur = boundaryEdgeIndices.begin();
+    Table<int, Array<int> >::Iterator end = boundaryEdgeIndices.end();
+    while (cur != end) {
+        Array<int>&     boundaryEdge = cur->value;
+
+        for (int i = 0; i < boundaryEdge.size(); ++i) {
+            int ei = boundaryEdge[i];
+            const Edge& edgei = oldEdgeArray[ei];
+
+            for (int j = i + 1; j < boundaryEdge.size(); ++j) {
+                int ej = boundaryEdge[j];
+                const Edge& edgej = oldEdgeArray[ej];
+
+                // See if edge ei is the reverse (match) of edge ej.
+
+                // True if the edges match
+                bool match = false;
+
+                // True if edgej's vertex indices are reversed from
+                // edgei's (usually true).
+                bool reversej = false;
+                
+                int u = edgei.vertexIndex[0];
+                int v = edgei.vertexIndex[1];
+
+                if (edgei.faceIndex[0] != Face::NONE) {
+                    //        verts|faces
+                    // edgei = [u v A /]
+
+                    if (edgej.faceIndex[0] != Face::NONE) {
+                        if ((edgej.vertexIndex[0] == v) && (edgej.vertexIndex[1] == u)) {
+                            // This is the most common of the four cases
+
+                            // edgej = [v u B /]
+                            match = true;
+                            reversej = true;
+                        }
+                    } else {
+                        if ((edgej.vertexIndex[0] == u) && (edgej.vertexIndex[1] == v)) {
+                            // edgej = [u v / B]
+                            match = true;
+                        }
+                    }
+                } else {
+                    // edgei = [u v / A]
+                    if (edgej.faceIndex[0] != Face::NONE) {
+                        if ((edgej.vertexIndex[0] == u) && (edgej.vertexIndex[1] == v)) {
+                            // edgej = [u v B /]
+                            match = true;
+                        }
+                    } else {
+                        if ((edgej.vertexIndex[0] == v) && (edgej.vertexIndex[1] == u)) {
+                            // edgej = [v u / B]
+                            match = true;
+                            reversej = true;
+                        }
+                    }
+                }
+
+                if (match) {
+                    // ei and ej can be paired as a single edge
+                    int e = edgeArray.size();
+                    Edge& edge = edgeArray.next();
+
+                    // Follow the direction of edgei.
+                    edge = edgei;
+                    newEdgeIndex[ei] = e;
+
+                    // Insert the face index for edgej.
+                    int fj = edgej.faceIndex[0];
+                    if (fj == Face::NONE) {
+                        fj = edgej.faceIndex[1];
+                    }
+                    
+                    if (edge.faceIndex[0] == Face::NONE) {
+                        edge.faceIndex[0] = fj;
+                    } else {
+                        edge.faceIndex[1] = fj;
+                    }
+                    
+                    if (reversej) {
+                        // The new edge is backwards of the old edge for ej
+                        newEdgeIndex[ej] = ~e;
+                    } else {
+                        newEdgeIndex[ej] = e;
+                    }
+
+                    // Remove both ei and ej from being candidates for future pairing.
+                    // Remove ej first since it comes later in the list (removing
+                    // ei would decrease the index of ej to j - 1).
+                    boundaryEdge.fastRemove(j);
+                    boundaryEdge.fastRemove(i);
+
+                    // Re-process element i, which is now a new edge index
+                    --i;
+
+                    // Jump out of the j for-loop
+                    break;
+                }
+            }
+        }
+        ++cur;
+    }
+
+    // Anything remaining in the table is a real boundary edge; just copy it to
+    // the end of the array.
+    cur = boundaryEdgeIndices.begin();
+    end = boundaryEdgeIndices.end();
+    while (cur != end) {
+        Array<int>&     boundaryEdge = cur->value;
+
+        for (int b = 0; b < boundaryEdge.size(); ++b) {
+            const int e = boundaryEdge[b];
+
+            newEdgeIndex[e] = edgeArray.size();
+            edgeArray.append(oldEdgeArray[e]);
+        }
+
+        ++cur;
+    }
+
+    // Finally, fix up edge indices in the face and vertex arrays
+    for (int f = 0; f < faceArray.size(); ++f) {
+        Face& face = faceArray[f];
+        for (int i = 0; i < 3; ++i) {
+            int e = face.edgeIndex[i];
+
+            if (e < 0) {
+                face.edgeIndex[i] = ~newEdgeIndex[~e];
+            } else {
+                face.edgeIndex[i] = newEdgeIndex[e];
+            }
+        }
+    }
+
+    for (int v = 0; v < vertexArray.size(); ++v) {
+        Vertex& vertex = vertexArray[v];
+        for (int i = 0; i < vertex.edgeIndex.size(); ++i) {
+            int e = vertex.edgeIndex[i];
+
+            if (e < 0) {
+                vertex.edgeIndex[i] = ~newEdgeIndex[~e];
+            } else {
+                vertex.edgeIndex[i] = newEdgeIndex[e];
+            }
+        }
+    }
+}
+
+
+void MeshAlg::weldAdjacency(
+    const Array<Vector3>& originalGeometry,
+    Array<Face>&          faceArray,
+    Array<Edge>&          edgeArray,
+    Array<Vertex>&        vertexArray,
+    double                radius) {
+
+    // Num vertices
+    const int n = originalGeometry.size();
+
+    // canonical[v] = first occurance of any vertex near oldVertexArray[v]
+    Array<int> canonical(n);
+
+    Array<int> toNew, toOld;
+    // Throw away the new vertex array
+    Array<Vector3> dummy;
+    computeWeld(originalGeometry, dummy, toNew, toOld, radius);
+
+    for (int v = 0; v < canonical.size(); ++v) {
+        // Round-trip through the toNew/toOld process.  This will give
+        // us the original vertex.
+        canonical[v] = toOld[toNew[v]];
+    }
+
+    // Destroy vertexArray (we reconstruct it below)
+    vertexArray.clear();
+    vertexArray.resize(n);
+
+    bool hasBoundaryEdges = false;
+
+    // Fix edge vertex indices
+    for (int e = 0; e < edgeArray.size(); ++e) {
+        Edge& edge = edgeArray[e];
+
+        const int v0 = canonical[edge.vertexIndex[0]];
+        const int v1 = canonical[edge.vertexIndex[1]];
+
+        edge.vertexIndex[0] = v0;
+        edge.vertexIndex[1] = v1;
+
+        vertexArray[v0].edgeIndex.append(e);
+        vertexArray[v1].edgeIndex.append(~e);
+
+        hasBoundaryEdges = hasBoundaryEdges || edge.boundary();
+    }
+
+    // Fix face vertex indices
+    for (int f = 0; f < faceArray.size(); ++f) {
+        Face& face = faceArray[f];
+        for (int i = 0; i < 3; ++i) {
+            const int v = canonical[face.vertexIndex[i]];
+
+            face.vertexIndex[i] = v;
+
+            // Add the back pointer
+            vertexArray[v].faceIndex.append(f);
+        }
+    }
+
+    if (hasBoundaryEdges) {
+        // As a result of the welding, some of the boundary edges at
+        // the end of the array may now have mates and no longer be
+        // boundaries.  Try to pair these up.
+
+        weldBoundaryEdges(faceArray, edgeArray, vertexArray);
+    }
+}
+
+
+void MeshAlg::debugCheckConsistency(
+    const Array<Face>&      faceArray,
+    const Array<Edge>&      edgeArray,
+    const Array<Vertex>&    vertexArray) {
+
+#ifdef _DEBUG
+    for (int v = 0; v < vertexArray.size(); ++v) {
+        const MeshAlg::Vertex& vertex = vertexArray[v];
+
+        for (int i = 0; i < vertex.edgeIndex.size(); ++i) {
+            const int e = vertex.edgeIndex[i];
+            debugAssert(edgeArray[(e >= 0) ? e : ~e].containsVertex(v));
+        }
+
+        for (int i = 0; i < vertex.faceIndex.size(); ++i) {
+            const int f = vertex.faceIndex[i];
+            debugAssert(faceArray[f].containsVertex(v));
+        }
+
+    }
+
+    for (int e = 0; e < edgeArray.size(); ++e) {
+        const MeshAlg::Edge& edge = edgeArray[e];
+
+        for (int i = 0; i < 2; ++i) {
+            debugAssert((edge.faceIndex[i] == MeshAlg::Face::NONE) ||
+                faceArray[edge.faceIndex[i]].containsEdge(e));
+
+            debugAssert(vertexArray[edge.vertexIndex[i]].inEdge(e));
+        }        
+    }
+
+    // Every face's edge must be on that face
+    for (int f = 0; f < faceArray.size(); ++f) {
+        const MeshAlg::Face& face = faceArray[f];
+        for (int i = 0; i < 3; ++i) {
+            int e = face.edgeIndex[i];
+            int ei = (e >= 0) ? e : ~e;
+            debugAssert(edgeArray[ei].inFace(f));
+
+            // Make sure the edge is oriented appropriately 
+            if (e >= 0) {
+                debugAssert(edgeArray[ei].faceIndex[0] == (int)f);
+            } else {
+                debugAssert(edgeArray[ei].faceIndex[1] == (int)f);
+            }
+
+            debugAssert(vertexArray[face.vertexIndex[i]].inFace(f));
+        }
+    }
+#else
+    (void)faceArray;
+    (void)edgeArray;
+    (void)vertexArray;
+#endif // _DEBUG
+}
+
+} // G3D namespace