MeshAlg.h

Go to the documentation of this file.

#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_WINDOWS
// Turn off "conditional expression is constant" warning; MSVC generates this
// for debug assertions in inlined methods.
#pragma warning( push )
#pragma warning (disable : 4127)
#endif

namespace G3D {

class MeshAlg {
public:

 typedef PrimitiveType Primitive;

 class Vertex {
 public:
 Vertex() {}

 SmallArray<int, 6> edgeIndex;

 inline bool inEdge(int e) const {
 return edgeIndex.contains(~e) || edgeIndex.contains(e);
 }

 SmallArray<int, 6> faceIndex;

 inline bool inFace(int f) const {
 debugAssert(f >= 0);
 return faceIndex.contains(f);
 }
 };


 class Face {
 public:
 Face();

 static const int NONE;


 int vertexIndex[3];

 inline bool containsVertex(int v) const {
 return contains(vertexIndex, 3, v);
 }

 // 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);
 }

 inline bool containsDirectedEdge(int e) const {
 return contains(edgeIndex, 3, e);
 }
 };


 class Edge {
 public:
 Edge();

 int vertexIndex[2];
 
 inline bool containsVertex(int v) const {
 return contains(vertexIndex, 2, v);
 }

 int faceIndex[2];
 
 inline bool inFace(int f) const {
 return contains(faceIndex, 2, f);
 }

 inline bool boundary() const {
 return (faceIndex[0] == Face::NONE) ||
 (faceIndex[1] == Face::NONE);
 }

 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;
 }
 };
 

 class Geometry {
 public: 
 Array<Vector3> vertexArray;

 Array<Vector3> normalArray;

 Geometry& operator=(const Geometry& src);

 void clear() {
 vertexArray.clear();
 normalArray.clear();
 }
 };

 static void computeAdjacency(
 const Array<Vector3>& vertexGeometry,
 const Array<int>& indexArray,
 Array<Face>& faceArray,
 Array<Edge>& edgeArray,
 Array<Vertex>& vertexArray);

 static void computeAdjacency(
 const Array<Vector3>& vertexArray,
 const Array<int>& indexArray,
 Array<Face>& faceArray,
 Array<Edge>& edgeArray,
 Array< Array<int> >& facesAdjacentToVertex);

 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:

 static void weldBoundaryEdges(
 Array<Face>& faceArray,
 Array<Edge>& edgeArray,
 Array<Vertex>& vertexArray);

public:

 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);

 static void computeNormals(
 const Array<Vector3>& vertexArray,
 const Array<Face>& faceArray,
 const Array< Array<int> >& adjacentFaceArray,
 Array<Vector3>& vertexNormalArray,
 Array<Vector3>& faceNormalArray);

 static void computeNormals(
 const Array<Vector3>& vertexGeometry,
 const Array<Face>& faceArray,
 const Array<Vertex>& vertexArray,
 Array<Vector3>& vertexNormalArray,
 Array<Vector3>& faceNormalArray);

 static void computeNormals(
 Geometry& geometry,
 const Array<int>& indexArray);

 static void computeFaceNormals(
 const Array<Vector3>& vertexArray,
 const Array<Face>& faceArray,
 Array<Vector3>& faceNormals,
 bool normalize = true);

 static void identifyBackfaces(
 const Array<Vector3>& vertexArray,
 const Array<Face>& faceArray,
 const Vector4& P,
 Array<bool>& backface);

 static void identifyBackfaces(
 const Array<Vector3>& vertexArray,
 const Array<Face>& faceArray,
 const Vector4& P,
 Array<bool>& backface,
 const Array<Vector3>& faceNormals);

 static void computeWeld(
 const Array<Vector3>& oldVertexPositions,
 Array<Vector3>& newVertexPositions,
 Array<int>& toNew,
 Array<int>& toOld,
 float radius = fuzzyEpsilon32);

 static void weldAdjacency(
 const Array<Vector3>& originalGeometry,
 Array<Face>& faceArray,
 Array<Edge>& edgeArray,
 Array<Vertex>& vertexArray,
 float radius = fuzzyEpsilon32);


 static int countBoundaryEdges(const Array<Edge>& edgeArray);


 static void createIndexArray(
 int n, 
 Array<int>& array,
 int start = 0,
 int run = 1,
 int skip = 0);

 static void computeBounds(const Array<Vector3>& vertex, class AABox& box, class Sphere& sphere);

 static void computeBounds(const Array<Vector3>& vertex, const Array<int>& index, class AABox& box, class Sphere& sphere);
 
 static void debugCheckConsistency(
 const Array<Face>& faceArray,
 const Array<Edge>& edgeArray,
 const Array<Vertex>& vertexArray);

 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 = Image1::Ref());

 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:

 static int findEdgeIndex(
 const Array<Vector3>& vertexArray,
 Array<Edge>& geometricEdgeArray,
 int i0, int i1, int f, double area);
};
}


#ifdef G3D_WINDOWS
#pragma warning( pop )
#endif

#endif