diff options
Diffstat (limited to 'externals/g3dlite/G3D.lib/source/MeshAlgAdjacency.cpp')
| -rw-r--r-- | externals/g3dlite/G3D.lib/source/MeshAlgAdjacency.cpp | 729 |
1 files changed, 0 insertions, 729 deletions
diff --git a/externals/g3dlite/G3D.lib/source/MeshAlgAdjacency.cpp b/externals/g3dlite/G3D.lib/source/MeshAlgAdjacency.cpp deleted file mode 100644 index a8b35f32c86..00000000000 --- a/externals/g3dlite/G3D.lib/source/MeshAlgAdjacency.cpp +++ /dev/null @@ -1,729 +0,0 @@ -/** - @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 |