diff options
Diffstat (limited to 'externals/g3dlite/G3D/MeshAlg.h')
| -rw-r--r-- | externals/g3dlite/G3D/MeshAlg.h | 683 |
1 files changed, 0 insertions, 683 deletions
diff --git a/externals/g3dlite/G3D/MeshAlg.h b/externals/g3dlite/G3D/MeshAlg.h deleted file mode 100644 index 1decea10105..00000000000 --- a/externals/g3dlite/G3D/MeshAlg.h +++ /dev/null @@ -1,683 +0,0 @@ -/** - @file MeshAlg.h - - Indexed Mesh algorithms. - - @maintainer Morgan McGuire, http://graphics.cs.williams.edu - - @created 2003-09-14 - @edited 2010-01-18 -*/ - -#ifndef G3D_MeshAlg_h -#define G3D_MeshAlg_h - -#include "G3D/platform.h" -#include "G3D/Array.h" -#include "G3D/Vector3.h" -#include "G3D/CoordinateFrame.h" -#include "G3D/SmallArray.h" -#include "G3D/constants.h" -#include "G3D/Image1.h" - -#ifdef G3D_WIN32 -// Turn off "conditional expression is constant" warning; MSVC generates this -// for debug assertions in inlined methods. -#pragma warning (disable : 4127) -#endif - -namespace G3D { - -/** - Indexed <B>mesh alg</B>orithms. You have to build your own mesh class. - <P> - No mesh class is provided with G3D because there isn't an "ideal" - mesh format-- one application needs keyframed animation, another - skeletal animation, a third texture coordinates, a fourth - cannot precompute information, etc. Instead of compromising, this - class implements the hard parts of mesh computation and you can write - your own ideal mesh class on top of it. - - \sa G3D::ArticulatedModel, G3D::IFSModel - */ -class MeshAlg { -public: - - /** \deprecated */ - typedef PrimitiveType Primitive; - - /** Adjacency information for a vertex. - Does not contain the vertex position or normal, - which are stored in the MeshAlg::Geometry object. - <CODE>Vertex</CODE>s must be stored in an array - parallel to (indexed in the same way as) - MeshAlg::Geometry::vertexArray. - */ - class Vertex { - public: - Vertex() {} - - /** - Array of edges adjacent to this vertex. - Let e = edgeIndex[i]. - edge[(e >= 0) ? e : ~e].vertexIndex[0] == this - vertex index. - - Edges may be listed multiple times if they are - degenerate. - */ - SmallArray<int, 6> edgeIndex; - - /** - Returns true if e or ~e is in the edgeIndex list. - */ - inline bool inEdge(int e) const { - return edgeIndex.contains(~e) || edgeIndex.contains(e); - } - - /** - Array of faces containing this vertex. Faces - may be listed multiple times if they are degenerate. - */ - SmallArray<int, 6> faceIndex; - - inline bool inFace(int f) const { - debugAssert(f >= 0); - return faceIndex.contains(f); - } - }; - - - /** - Oriented, indexed triangle. - */ - class Face { - public: - Face(); - - /** - Used by Edge::faceIndex to indicate a missing face. - This is a large negative value. - */ - static const int NONE; - - - /** - Vertices in the face in counter-clockwise order. - Degenerate faces may include the same vertex multiple times. - */ - int vertexIndex[3]; - - inline bool containsVertex(int v) const { - return contains(vertexIndex, 3, v); - } - - /** - Edge indices in counter-clockwise order. Edges are - undirected, so it is important to know which way - each edge is pointing in a face. This is encoded - using negative indices. - - If <CODE>edgeIndex[i] >= 0</CODE> then this face - contains the directed edge - between vertex indices - <CODE>edgeArray[face.edgeIndex[i]].vertexIndex[0]</CODE> - and - <CODE>edgeArray[face.edgeIndex[i]].vertexIndex[1]</CODE>. - - If <CODE>edgeIndex[i] < 0</CODE> then - <CODE>~edgeIndex[i]</CODE> (i.e. the two's - complement of) is used and this face contains the directed - edge between vertex indices - <CODE>edgeArray[~face.edgeIndex[i]].vertexIndex[0]</CODE> - and - <CODE>edgeArray[~face.edgeIndex[i]].vertexIndex[1]</CODE>. - - Degenerate faces may include the same edge multiple times. - */ - // Temporarily takes on the value Face::NONE during adjacency - // computation to indicate an edge that has not yet been assigned. - int edgeIndex[3]; - - inline bool containsEdge(int e) const { - if (e < 0) { - e = ~e; - } - return contains(edgeIndex, 3, e) || contains(edgeIndex, 3, ~e); - } - - /** Contains the forward edge e if e >= 0 and the backward edge - ~e otherwise. */ - inline bool containsDirectedEdge(int e) const { - return contains(edgeIndex, 3, e); - } - }; - - - /** Oriented, indexed edge */ - class Edge { - public: - Edge(); - - /** Degenerate edges may include the same vertex times. */ - int vertexIndex[2]; - - inline bool containsVertex(int v) const { - return contains(vertexIndex, 2, v); - } - - /** - The edge is directed <B>forward</B> in face 0 - <B>backward</B> in face 1. Face index of MeshAlg::Face::NONE - indicates a boundary (a.k.a. crack, broken) edge. - */ - int faceIndex[2]; - - /** Returns true if f is contained in the faceIndex array in either slot. - To see if it is forward in that face, just check edge.faceIndex[0] == f.*/ - inline bool inFace(int f) const { - return contains(faceIndex, 2, f); - } - - /** - Returns true if either faceIndex is NONE. - */ - inline bool boundary() const { - return (faceIndex[0] == Face::NONE) || - (faceIndex[1] == Face::NONE); - } - - /** - Returns the reversed edge. - */ - inline Edge reverse() const { - Edge e; - e.vertexIndex[0] = vertexIndex[1]; - e.vertexIndex[1] = vertexIndex[0]; - e.faceIndex[0] = faceIndex[1]; - e.faceIndex[1] = faceIndex[0]; - return e; - } - }; - - - /** - Convenient for passing around the per-vertex data that changes under - animation. The faces and edges are needed to interpret - these values. - */ - class Geometry { - public: - /** Vertex positions */ - Array<Vector3> vertexArray; - - /** Vertex normals */ - Array<Vector3> normalArray; - - /** - Assignment is optimized using SSE. - */ - Geometry& operator=(const Geometry& src); - - void clear() { - vertexArray.clear(); - normalArray.clear(); - } - }; - - /** - Given a set of vertices and a set of indices for traversing them - to create triangles, computes other mesh properties. - - <B>Colocated vertices are treated as separate.</B> To have - colocated vertices collapsed (necessary for many algorithms, - like shadowing), weld the mesh before computing adjacency. - - <I>Recent change: In version 6.00, colocated vertices were automatically - welded by this routine and degenerate faces and edges were removed. That - is no longer the case.</I> - - Where two faces meet, there are two opposite directed edges. These - are collapsed into a single bidirectional edge in the edgeArray. - If four faces meet exactly at the same edge, that edge will appear - twice in the array, and so on. If an edge is a boundary of the mesh - (i.e. if the edge has only one adjacent face) it will appear in the - array with one face index set to MeshAlg::Face::NONE. - - @param vertexGeometry %Vertex positions to use when deciding colocation. - @param indexArray Order to traverse vertices to make triangles - @param faceArray <I>Output</I> - @param edgeArray <I>Output</I>. Sorted so that boundary edges are at the end of the array. - @param vertexArray <I>Output</I> - */ - static void computeAdjacency( - const Array<Vector3>& vertexGeometry, - const Array<int>& indexArray, - Array<Face>& faceArray, - Array<Edge>& edgeArray, - Array<Vertex>& vertexArray); - - /** - @deprecated Use the other version of computeAdjacency, which takes Array<Vertex>. - @param facesAdjacentToVertex <I>Output</I> adjacentFaceArray[v] is an array of - indices for faces touching vertex index v - */ - static void computeAdjacency( - const Array<Vector3>& vertexArray, - const Array<int>& indexArray, - Array<Face>& faceArray, - Array<Edge>& edgeArray, - Array< Array<int> >& facesAdjacentToVertex); - - /** - Computes some basic mesh statistics including: min, max mean and median, - edge lengths; and min, mean, median, and max face area. - - @param vertexArray %Vertex positions to use when deciding colocation. - @param indexArray Order to traverse vertices to make triangles - @param minEdgeLength Minimum edge length - @param meanEdgeLength Mean edge length - @param medianEdgeLength Median edge length - @param maxEdgeLength Max edge length - @param minFaceArea Minimum face area - @param meanFaceArea Mean face area - @param medianFaceArea Median face area - @param maxFaceArea Max face area - */ - static void computeAreaStatistics( - const Array<Vector3>& vertexArray, - const Array<int>& indexArray, - double& minEdgeLength, - double& meanEdgeLength, - double& medianEdgeLength, - double& maxEdgeLength, - double& minFaceArea, - double& meanFaceArea, - double& medianFaceArea, - double& maxFaceArea); - -private: - - /** Helper for weldAdjacency */ - static void weldBoundaryEdges( - Array<Face>& faceArray, - Array<Edge>& edgeArray, - Array<Vertex>& vertexArray); - -public: - - /** - Computes tangent and binormal vectors, - which provide a (mostly) consistent - parameterization over the surface for - effects like bump mapping. In the resulting coordinate frame, - T = x (varies with texture s coordinate), B = y (varies with negative texture t coordinate), - and N = z for a right-handed coordinate frame. If a billboard is vertical on the screen - in view of the camera, the tangent space matches the camera's coordinate frame. - - The vertex, texCoord, tangent, and binormal - arrays are parallel arrays. - - The resulting tangent and binormal might not be exactly - perpendicular to each other. They are guaranteed to - be perpendicular to the normal. - - @cite Max McGuire - */ - static void computeTangentSpaceBasis( - const Array<Vector3>& vertexArray, - const Array<Vector2>& texCoordArray, - const Array<Vector3>& vertexNormalArray, - const Array<Face>& faceArray, - Array<Vector3>& tangent, - Array<Vector3>& binormal); - - /** @deprecated */ - static void computeNormals( - const Array<Vector3>& vertexArray, - const Array<Face>& faceArray, - const Array< Array<int> >& adjacentFaceArray, - Array<Vector3>& vertexNormalArray, - Array<Vector3>& faceNormalArray); - - /** - Vertex normals are weighted by the area of adjacent faces. - Nelson Max showed this is superior to uniform weighting for - general meshes in jgt. - - @param vertexNormalArray Output. Unit length - @param faceNormalArray Output. Degenerate faces produce zero magnitude normals. Unit length - @see weld - */ - static void computeNormals( - const Array<Vector3>& vertexGeometry, - const Array<Face>& faceArray, - const Array<Vertex>& vertexArray, - Array<Vector3>& vertexNormalArray, - Array<Vector3>& faceNormalArray); - - /** Computes unit length normals in place using the other computeNormals methods. - If you already have a face array use another method; it will be faster. - @see weld*/ - static void computeNormals( - Geometry& geometry, - const Array<int>& indexArray); - - /** - Computes face normals only. Significantly faster (especially if - normalize is false) than computeNormals. - @see weld - */ - static void computeFaceNormals( - const Array<Vector3>& vertexArray, - const Array<Face>& faceArray, - Array<Vector3>& faceNormals, - bool normalize = true); - - /** - Classifies each face as a backface or a front face relative - to the observer point P (which is at infinity when P.w = 0). - A face with normal exactly perpendicular to the observer vector - may be classified as either a front or a back face arbitrarily. - */ - static void identifyBackfaces( - const Array<Vector3>& vertexArray, - const Array<Face>& faceArray, - const Vector4& P, - Array<bool>& backface); - - /** A faster version of identifyBackfaces for the case where - face normals have already been computed */ - static void identifyBackfaces( - const Array<Vector3>& vertexArray, - const Array<Face>& faceArray, - const Vector4& P, - Array<bool>& backface, - const Array<Vector3>& faceNormals); - - /** - Welds nearby and colocated elements of the <I>oldVertexArray</I> together so that - <I>newVertexArray</I> contains no vertices within <I>radius</I> of one another. - Every vertex in newVertexPositions also appears in oldVertexPositions. - This is useful for downsampling meshes and welding cracks created by artist errors - or numerical imprecision. - - The two integer arrays map indices back and forth between the arrays according to: - <PRE> - oldVertexArray[toOld[ni]] == newVertexArray[ni] - oldVertexArray[oi] == newVertexArray[toNew[ni]] - </PRE> - - Note that newVertexPositions is never longer than oldVertexPositions - and is shorter when vertices are welded. - - Welding with a large radius will effectively compute a lower level of detail for - the mesh. - - The welding method runs in roughly linear time in the length of oldVertexArray-- - a uniform spatial grid is used to achieve nearly constant time vertex collapses - for uniformly distributed vertices. - - It is sometimes desirable to keep the original vertex ordering but - identify the unique vertices. The following code computes - array canonical s.t. canonical[v] = first occurance of - a vertex near oldVertexPositions[v] in oldVertexPositions. - - <PRE> - Array<int> canonical(oldVertexPositions.size()), toNew, toOld; - computeWeld(oldVertexPositions, Array<Vector3>(), toNew, toOld, radius); - for (int v = 0; v < canonical.size(); ++v) { - canonical[v] = toOld[toNew[v]]; - } - </PRE> - - See also G3D::MeshAlg::weldAdjacency. - - @cite The method is that described as the 'Grouper' in Baum, Mann, Smith, and Winget, - Making Radiosity Usable: Automatic Preprocessing and Meshing Techniques for - the Generation of Accurate Radiosity Solutions, Computer Graphics vol 25, no 4, July 1991. - - @deprecated Use weld. - */ - static void computeWeld( - const Array<Vector3>& oldVertexPositions, - Array<Vector3>& newVertexPositions, - Array<int>& toNew, - Array<int>& toOld, - double radius = fuzzyEpsilon); - - /** - Modifies the face, edge, and vertex arrays in place so that - colocated (within radius) vertices are treated as identical. - Note that the vertexArray and corresponding geometry will - contain elements that are no longer used. In the vertexArray, - these elements are initialized to MeshAlg::Vertex() but not - removed (because removal would change the indexing). - - This is a good preprocessing step for algorithms that are only - concerned with the shape of a mesh (e.g. cartoon rendering, fur, shadows) - and not the indexing of the vertices. - - Use this method when you have already computed adjacency information - and want to collapse colocated vertices within that data without - disturbing the actual mesh vertices or indexing scheme. - - If you have not computed adjacency already, use MeshAlg::computeWeld - instead and compute adjacency information after welding. - - @deprecated Use weld. - - @param faceArray Mutated in place. Size is maintained (degenerate - faces are <b>not</B> removed). - @param edgeArray Mutated in place. May shrink if boundary edges - are welded together. - @param vertexArray Mutated in place. Size is maintained (duplicate - vertices contain no adjacency info). - */ - static void weldAdjacency( - const Array<Vector3>& originalGeometry, - Array<Face>& faceArray, - Array<Edge>& edgeArray, - Array<Vertex>& vertexArray, - double radius = fuzzyEpsilon); - - - /** - Counts the number of edges (in an edge array returned from - MeshAlg::computeAdjacency) that have only one adjacent face. - */ - static int countBoundaryEdges(const Array<Edge>& edgeArray); - - - /** - Generates an array of integers from start to start + n - 1 that have run numbers - in series then omit the next skip before the next run. Useful for turning - a triangle list into an indexed face set. - - Example: - <PRE> - createIndexArray(10, x); - // x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] - - createIndexArray(5, x, 2); - // x = [2, 3, 4, 5, 6, 7] - - createIndexArray(6, x, 0, 2, 1); - // x = [0, 1, 3, 4, 6, 7] - </PRE> - */ - static void createIndexArray( - int n, - Array<int>& array, - int start = 0, - int run = 1, - int skip = 0); - - /** - Computes a conservative, near-optimal axis aligned bounding box and sphere. - - @cite The bounding sphere uses the method from J. Ritter. An effcient bounding sphere. In Andrew S. Glassner, editor, Graphics Gems. Academic Press, Boston, MA, 1990. - - */ - static void computeBounds(const Array<Vector3>& vertex, class AABox& box, class Sphere& sphere); - - /** Computes bounds for a subset of the vertices. It is ok if vertices appear more than once in the index array. */ - static void computeBounds(const Array<Vector3>& vertex, const Array<int>& index, class AABox& box, class Sphere& sphere); - - /** - In debug mode, asserts that the adjacency references between the - face, edge, and vertex array are consistent. - */ - static void debugCheckConsistency( - const Array<Face>& faceArray, - const Array<Edge>& edgeArray, - const Array<Vertex>& vertexArray); - - /** - Generates a unit square in the X-Z plane composed of a grid of wCells x hCells - squares and then transforms it by xform. - - @param vertex Output vertices - @param texCoord Output texture coordinates - @param index Output triangle list indices - @param textureScale Lower-right texture coordinate - @param spaceCentered If true, the coordinates generated are centered at the origin before the transformation. - @param twoSided If true, matching top and bottom planes are generated. - \param elevation If non-NULL, values from this image are used as elevations. Apply an \a xform to adjust the scale - */ - static void generateGrid( - Array<Vector3>& vertex, - Array<Vector2>& texCoord, - Array<int>& index, - int wCells = 10, - int hCells = 10, - const Vector2& textureScale = Vector2(1,1), - bool spaceCentered = true, - bool twoSided = true, - const CoordinateFrame& xform = CoordinateFrame(), - const Image1::Ref& elevation = NULL); - - /** Converts quadlist (QUADS), - triangle fan (TRIANGLE_FAN), - tristrip(TRIANGLE_STRIP), and quadstrip (QUAD_STRIP) indices into - triangle list (TRIANGLES) indices and appends them to outIndices. */ - template<class IndexType> - static void toIndexedTriList( - const Array<IndexType>& inIndices, - MeshAlg::Primitive inType, - Array<IndexType>& outIndices) { - - debugAssert( - inType == PrimitiveType::TRIANGLE_STRIP || - inType == PrimitiveType::TRIANGLE_FAN || - inType == PrimitiveType::QUADS || - inType == PrimitiveType::QUAD_STRIP); - - const int inSize = inIndices.size(); - - switch(inType) { - case PrimitiveType::TRIANGLE_FAN: - { - debugAssert(inSize >= 3); - - int N = outIndices.size(); - outIndices.resize(N + (inSize - 2) * 3); - - for (IndexType i = 1, outIndex = N; i <= (inSize - 2); ++i, outIndex += 3) { - outIndices[outIndex] = inIndices[0]; - outIndices[outIndex + 1] = inIndices[i]; - outIndices[outIndex + 2] = inIndices[i + 1]; - } - - break; - } - - case PrimitiveType::TRIANGLE_STRIP: - { - debugAssert(inSize >= 3); - - int N = outIndices.size(); - outIndices.resize(N + (inSize - 2) * 3); - - bool atEven = false; - for (IndexType i = 0, outIndex = N; i <= (inSize - 2); ++i, outIndex += 3) { - if (atEven) { - outIndices[outIndex] = inIndices[i + 1]; - outIndices[outIndex + 1] = inIndices[i]; - outIndices[outIndex + 2] = inIndices[i + 2]; - atEven = false; - } else { - outIndices[outIndex] = inIndices[i]; - outIndices[outIndex + 1] = inIndices[i + 1]; - outIndices[outIndex + 2] = inIndices[i + 2]; - atEven = true; - } - } - - break; - } - - case PrimitiveType::QUADS: - { - debugAssert(inIndices.size() >= 4); - - int N = outIndices.size(); - outIndices.resize(N + (inSize / 4) * 3); - - for (IndexType i = 0, outIndex = N; i <= (inSize - 4); i += 4, outIndex += 6) { - outIndices[outIndex] = inIndices[i]; - outIndices[outIndex + 1] = inIndices[i + 1]; - outIndices[outIndex + 2] = inIndices[i + 3]; - outIndices[outIndex + 3] = inIndices[i + 1]; - outIndices[outIndex + 4] = inIndices[i + 2]; - outIndices[outIndex + 5] = inIndices[i + 3]; - } - - break; - } - - case PrimitiveType::QUAD_STRIP: - { - debugAssert(inIndices.size() >= 4); - - int N = outIndices.size(); - outIndices.resize(N + (inSize - 2) * 3); - - for (IndexType i = 0, outIndex = N; i <= (inSize - 2); i += 2, outIndex += 6) { - outIndices[outIndex] = inIndices[i]; - outIndices[outIndex + 1] = inIndices[i + 1]; - outIndices[outIndex + 2] = inIndices[i + 2]; - outIndices[outIndex + 3] = inIndices[i + 2]; - outIndices[outIndex + 4] = inIndices[i + 1]; - outIndices[outIndex + 5] = inIndices[i + 3]; - } - break; - } - default: - alwaysAssertM(false, "Illegal argument"); - } - } - -protected: - - /** - Helper for computeAdjacency. If a directed edge with index e already - exists from i0 to i1 then e is returned. If a directed edge with index e - already exists from i1 to i0, ~e is returned (the complement) and - edgeArray[e] is set to f. Otherwise, a new edge is created from i0 to i1 - with first face index f and its index is returned. - - @param vertexArray Vertex positions to use when deciding colocation. - - @param area Area of face f. When multiple edges of the same direction - are found between the same vertices (usually because of degenerate edges) - the face with larger area is kept in the edge table. - */ - static int findEdgeIndex( - const Array<Vector3>& vertexArray, - Array<Edge>& geometricEdgeArray, - int i0, int i1, int f, double area); -}; -} -#endif - |