G3D::MeshAlg Class Reference

#include <MeshAlg.h>

Classes
class	Edge
class	Face
class	Geometry
class	Vertex

Public Types
typedef PrimitiveType	Primitive

Static Public Member Functions
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)
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)

Static Protected Member Functions
static int	findEdgeIndex (const Array< Vector3 > &vertexArray, Array< Edge > &geometricEdgeArray, int i0, int i1, int f, double area)

Static Private Member Functions
static void	weldBoundaryEdges (Array< Face > &faceArray, Array< Edge > &edgeArray, Array< Vertex > &vertexArray)

Detailed Description

Indexed mesh algorithms. You have to build your own mesh class.

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.

See also

G3D::ArticulatedModel, G3D::IFSModel

Member Typedef Documentation

typedef PrimitiveType G3D::MeshAlg::Primitive

Deprecated:

Member Function Documentation

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

static

Given a set of vertices and a set of indices for traversing them to create triangles, computes other mesh properties.

Colocated vertices are treated as separate. To have colocated vertices collapsed (necessary for many algorithms, like shadowing), weld the mesh before computing adjacency.

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.

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.

Parameters

vertexGeometry	Vertex positions to use when deciding colocation.
indexArray	Order to traverse vertices to make triangles
faceArray	Output
edgeArray	Output. Sorted so that boundary edges are at the end of the array.
vertexArray	Output

 {

 MeshEdgeTable edgeTable;

 edgeArray.clear();
 vertexArray.clear();
 faceArray.clear();
 
 // Face normals
 Array<Vector3> faceNormal;
 faceNormal.resize(indexArray.size() / 3);
 faceArray.resize(faceNormal.size());

 // This array has the same size as the vertex array
 vertexArray.resize(vertexGeometry.size());

 edgeTable.resize(vertexArray.size());

 // Iterate through the triangle list
 for (int q = 0, f = 0; q < indexArray.size(); ++f, q += 3) {

 Vector3 vertex[3];
 MeshAlg::Face& face = faceArray[f];

 // 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
 const Vector3& N = (vertex[1] - vertex[0]).cross(vertex[2] - vertex[0]);
 faceNormal[f] = 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]];

 if (i0 < i1) {
 // The edge was directed in the same manner as in the face
 edgeTable.insert(i0, i1, f);
 } else {
 // The edge was directed in the opposite manner as in the face
 edgeTable.insert(i1, i0, ~f);
 }
 }
 }

 // For each edge in the edge table, create an edge in the edge array.
 // Collapse every 2 edges from adjacent faces.

 MeshEdgeTable::Iterator cur = edgeTable.begin();

 Array<Edge> tempEdgeArray;
 while (cur.isValid()) {
 MeshEdgeTable::FaceIndexArray& faceIndexArray = cur.faceIndex();

 // 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.
 float 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];
 float 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] = cur.i0();
 edge.vertexIndex[1] = cur.i1();

 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;
 newIndex.resize(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);
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void G3D::MeshAlg::computeAdjacency ( const Array< Vector3 > &  vertexArray, const Array< int > &  indexArray, Array< Face > &  faceArray, Array< Edge > &  edgeArray, Array< Array< int > > &  facesAdjacentToVertex  )

static

Deprecated:

Use the other version of computeAdjacency, which takes Array<Vertex>.

Parameters

facesAdjacentToVertex

Output adjacentFaceArray[v] is an array of indices for faces touching vertex index v

 {

 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) {
 const SmallArray<int, 6>& src = vertexArray[v].faceIndex;
 Array<int>& dst = adjacentFaceArray[v];
 dst.resize(src.size());
 for (int f = 0; f < dst.size(); ++f) {
 dst[f] = src[f];
 }
 }
}

Here is the call graph for this function:

void G3D::MeshAlg::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  )

static

Computes some basic mesh statistics including: min, max mean and median, edge lengths; and min, mean, median, and max face area.

Parameters

vertexArray	Vertex positions to use when deciding colocation.
indexArray	Order to traverse vertices to make triangles
minEdgeLength	Minimum edge length
meanEdgeLength	Mean edge length
medianEdgeLength	Median edge length
maxEdgeLength	Max edge length
minFaceArea	Minimum face area
meanFaceArea	Mean face area
medianFaceArea	Median face area
maxFaceArea	Max face area

 {

 debugAssert(indexArray.size() % 3 == 0);
 
 Array<double> area;
 area.resize(indexArray.size() / 3);
 Array<double> magnitude;
 magnitude.resize(indexArray.size());

 for (int i = 0; i < indexArray.size(); i += 3) {
 const Vector3& v0 = vertexArray[indexArray[i]];
 const Vector3& v1 = vertexArray[indexArray[i + 1]];
 const Vector3& v2 = vertexArray[indexArray[i + 2]];

 area[i / 3] = (v1 - v0).cross(v2 - v0).magnitude() / 2.0;
 magnitude[i] = (v1 - v0).magnitude();
 magnitude[i + 1] = (v2 - v1).magnitude();
 magnitude[i + 2] = (v0 - v2).magnitude();
 }

 area.sort();
 magnitude.sort();

 minEdgeLength = max(0.0, magnitude[0]);
 maxEdgeLength = max(0.0, magnitude.last());
 medianEdgeLength = max(0.0, magnitude[magnitude.size() / 2]);
 meanEdgeLength = 0;
 for (int i = 0; i < magnitude.size(); ++i) {
 meanEdgeLength += magnitude[i];
 }
 meanEdgeLength /= magnitude.size();

 minFaceArea = max(0.0, area[0]);
 maxFaceArea = max(0.0, area.last());
 medianFaceArea = max(0.0, area[area.size() / 2]);
 meanFaceArea = 0;
 for (int i = 0; i < area.size(); ++i) {
 meanFaceArea += area[i];
 }
 meanFaceArea /= area.size();


 // Make sure round-off hasn't pushed values less than zero
 meanFaceArea = max(0.0, meanFaceArea);
 meanEdgeLength = max(0.0, meanEdgeLength);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void G3D::MeshAlg::computeBounds ( const Array< Vector3 > &  vertex, class AABox &  box, class Sphere &  sphere  )

static

Computes a conservative, near-optimal axis aligned bounding box and sphere.

[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.

 {

 Vector3 xmin, xmax, ymin, ymax, zmin, zmax;

 // FIRST PASS: find 6 minima/maxima points
 xmin.x = ymin.y = zmin.z = finf();
 xmax.x = ymax.y = zmax.z = -finf();

 for (int v = 0; v < vertexArray.size(); ++v) {
 const Vector3& vertex = vertexArray[v];

 if (vertex.x < xmin.x) {
 xmin = vertex;
 }

 if (vertex.x > xmax.x) {
 xmax = vertex;
 }

 if (vertex.y < ymin.y) {
 ymin = vertex;
 }

 if (vertex.y > ymax.y) {
 ymax = vertex;
 }

 if (vertex.z < zmin.z) {
 zmin = vertex;
 }

 if (vertex.z > zmax.z) {
 zmax = vertex;
 }
 }

 // Set points dia1 & dia2 to the maximally separated pair
 Vector3 dia1 = xmin; 
 Vector3 dia2 = xmax;
 {
 // Set xspan = distance between the 2 points xmin & xmax (squared)
 float xspan = (xmax - xmin).squaredMagnitude();

 // Same for y & z spans
 float yspan = (ymax - ymin).squaredMagnitude();
 float zspan = (zmax - zmin).squaredMagnitude();
 
 float maxspan = xspan;

 if (yspan > maxspan) {
 maxspan = yspan;
 dia1 = ymin;
 dia2 = ymax;
 }

 if (zspan > maxspan) {
 maxspan = zspan;
 dia1 = zmin;
 dia2 = zmax;
 }
 }


 // dia1, dia2 is a diameter of initial sphere

 // calc initial center
 Vector3 center = (dia1 + dia2) / 2.0;

 // calculate initial radius^2 and radius 
 Vector3 d = dia2 - sphere.center;

 float radSq = d.squaredMagnitude();
 float rad = sqrt(radSq);

 // SECOND PASS: increment current sphere
 float old_to_p, old_to_new;

 for (int v = 0; v < vertexArray.size(); ++v) {
 const Vector3& vertex = vertexArray[v];

 d = vertex - center;

 float old_to_p_sq = d.squaredMagnitude();

 // do r^2 test first 
 if (old_to_p_sq > radSq) {
 // this point is outside of current sphere
 old_to_p = sqrt(old_to_p_sq);

 // calc radius of new sphere
 rad = (rad + old_to_p) / 2.0f;

 // for next r^2 compare
 radSq = rad * rad; 
 old_to_new = old_to_p - rad;

 // calc center of new sphere
 center = (rad * center + old_to_new * vertex) / old_to_p;
 } 
 }

 const Vector3 min(xmin.x, ymin.y, zmin.z);
 const Vector3 max(xmax.x, ymax.y, zmax.z);

 box = AABox(min, max);

 const float boxRadSq = (max - min).squaredMagnitude() * 0.25f;

 if (boxRadSq >= radSq){
 if (isNaN(center.x) || ! isFinite(rad)) {
 sphere = Sphere(Vector3::zero(), finf());
 } else {
 sphere = Sphere(center, rad);
 }
 } else {
 sphere = Sphere((max + min) * 0.5f, sqrt(boxRadSq));
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void G3D::MeshAlg::computeBounds ( const Array< Vector3 > &  vertex, const Array< int > &  index, class AABox &  box, class Sphere &  sphere  )

static

Computes bounds for a subset of the vertices. It is ok if vertices appear more than once in the index array.

 {

 // Makes a copy so as to re-use the existing computebounds code
 Array<Vector3> newArray;
 newArray.resize(indexArray.size());
 for (int i = 0; i < indexArray.size(); ++i) {
 newArray[i] = vertexArray[indexArray[i]];
 }
 computeBounds(newArray, box, sphere);
}

Here is the call graph for this function:

void G3D::MeshAlg::computeFaceNormals ( const Array< Vector3 > &  vertexArray, const Array< Face > &  faceArray, Array< Vector3 > &  faceNormals, bool  normalize = true  )

static

Computes face normals only. Significantly faster (especially if normalize is false) than computeNormals.

See also

weld

 {

 faceNormals.resize(faceArray.size());

 for (int f = 0; f < faceArray.size(); ++f) {
 const MeshAlg::Face& face = faceArray[f];

 const Vector3& v0 = vertexArray[face.vertexIndex[0]];
 const Vector3& v1 = vertexArray[face.vertexIndex[1]];
 const Vector3& v2 = vertexArray[face.vertexIndex[2]];
 
 faceNormals[f] = (v1 - v0).cross(v2 - v0);
 }

 if (normalize) {
 for (int f = 0; f < faceArray.size(); ++f) {
 faceNormals[f] = faceNormals[f].direction();
 }
 }
}

Here is the call graph for this function:

void G3D::MeshAlg::computeNormals ( const Array< Vector3 > &  vertexArray, const Array< Face > &  faceArray, const Array< Array< int > > &  adjacentFaceArray, Array< Vector3 > &  vertexNormalArray, Array< Vector3 > &  faceNormalArray  )

static

Deprecated:

 {

 // Construct a fake vertex array for backwards compatibility
 Array<Vertex> fakeVertexArray;
 fakeVertexArray.resize(adjacentFaceArray.size());

 for (int v = 0; v < adjacentFaceArray.size(); ++v) {
 fakeVertexArray[v].faceIndex.resize(adjacentFaceArray[v].size());
 for (int i = 0; i < fakeVertexArray[v].faceIndex.size(); ++i) {
 fakeVertexArray[v].faceIndex[i] = adjacentFaceArray[v][i];
 }
 // We leave out the edges because they aren't used to compute normals
 }

 computeNormals(vertexGeometry, faceArray, fakeVertexArray, 
 vertexNormalArray, faceNormalArray);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void G3D::MeshAlg::computeNormals ( const Array< Vector3 > &  vertexGeometry, const Array< Face > &  faceArray, const Array< Vertex > &  vertexArray, Array< Vector3 > &  vertexNormalArray, Array< Vector3 > &  faceNormalArray  )

static

Vertex normals are weighted by the area of adjacent faces. Nelson Max showed this is superior to uniform weighting for general meshes in jgt.

Parameters

vertexNormalArray	Output. Unit length
faceNormalArray	Output. Degenerate faces produce zero magnitude normals. Unit length

See also

weld

 {

 // Face normals (not unit length)
 faceNormalArray.resize(faceArray.size());
 for (int f = 0; f < faceArray.size(); ++f) {
 const Face& face = faceArray[f];

 Vector3 vertex[3];
 for (int j = 0; j < 3; ++j) {
 vertex[j] = vertexGeometry[face.vertexIndex[j]];
 debugAssert(vertex[j].isFinite());
 }

 faceNormalArray[f] = (vertex[1] - vertex[0]).cross(vertex[2] - vertex[0]);
# ifdef G3D_DEBUG
 const Vector3& N = faceNormalArray[f];
 debugAssert(N.isFinite());
# endif
 }

 // Per-vertex normals, computed by averaging
 vertexNormalArray.resize(vertexGeometry.size());
 for (int v = 0; v < vertexNormalArray.size(); ++v) {
 Vector3 sum = Vector3::zero();
 for (int k = 0; k < vertexArray[v].faceIndex.size(); ++k) {
 const int f = vertexArray[v].faceIndex[k];
 sum += faceNormalArray[f];
 }
 vertexNormalArray[v] = sum.directionOrZero();
# ifdef G3D_DEBUG
 const Vector3& N = vertexNormalArray[v];
 debugAssert(N.isUnit() || N.isZero());
# endif
 }


 for (int f = 0; f < faceArray.size(); ++f) {
 faceNormalArray[f] = faceNormalArray[f].directionOrZero();
# ifdef G3D_DEBUG
 const Vector3& N = faceNormalArray[f];
 debugAssert(N.isUnit() || N.isZero());
# endif
 }

}

Here is the call graph for this function:

void G3D::MeshAlg::computeNormals ( Geometry &  geometry, const Array< int > &  indexArray  )

static

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 also

weld

 {

 Array<Face> faceArray;
 Array<Vertex> vertexArray;
 Array<Edge> edgeArray;
 Array<Vector3> faceNormalArray;

 computeAdjacency(geometry.vertexArray, indexArray, faceArray, edgeArray, vertexArray);

 computeNormals(geometry.vertexArray, faceArray, vertexArray, 
 geometry.normalArray, faceNormalArray);
}

Here is the call graph for this function:

void G3D::MeshAlg::computeTangentSpaceBasis ( const Array< Vector3 > &  vertexArray, const Array< Vector2 > &  texCoordArray, const Array< Vector3 > &  vertexNormalArray, const Array< Face > &  faceArray, Array< Vector3 > &  tangent, Array< Vector3 > &  binormal  )

static

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.

[Max] McGuire

 {

 debugAssertM(faceArray.size() != 0, "Unable to calculate valid tangent space without faces.");

 tangent.resize(vertexArray.size());
 binormal.resize(vertexArray.size());

 // Zero the output arrays.
 System::memset(tangent.getCArray(), 0, sizeof(Vector3) * tangent.size());
 System::memset(binormal.getCArray(), 0, sizeof(Vector3) * binormal.size());

 // Iterate over faces, computing the tangent vectors for each 
 // vertex. Accumulate those into the tangent and binormal arrays
 // and then orthonormalize at the end.

 for (int f = 0; f < faceArray.size(); ++f) {
 const Face& face = faceArray[f];

 const int i0 = face.vertexIndex[0];
 const int i1 = face.vertexIndex[1];
 const int i2 = face.vertexIndex[2];
 
 const Vector3& v0 = vertexArray[i0];
 const Vector3& v1 = vertexArray[i1];
 const Vector3& v2 = vertexArray[i2];

 const Vector2& t0 = texCoordArray[i0];
 const Vector2& t1 = texCoordArray[i1];
 const Vector2& t2 = texCoordArray[i2];

 // See http://www.terathon.com/code/tangent.html for a derivation of the following code

 // vertex edges
 Vector3 ve1 = v1 - v0;
 Vector3 ve2 = v2 - v0;

 // texture edges
 Vector2 te1 = t1 - t0;
 Vector2 te2 = t2 - t0;

 Vector3 n(ve1.cross(ve2).direction());
 Vector3 t, b;
 
 float r = te1.x * te2.y - te1.y * te2.x;
 if (r == 0.0) {
 // degenerate case
 if (! n.isFinite() || n.isZero()) {
 n = Vector3::unitY();
 }
 n.getTangents(t, b);
 } else {
 r = 1.0f / r; 
 t = (te2.y * ve1 - te1.y * ve2) * r;
 b = (te2.x * ve1 - te1.x * ve2) * r; 
 }

 for (int v = 0; v < 3; ++v) {
 int i = face.vertexIndex[v];
 tangent[i] += t;
 binormal[i] += b;
 }
 }

 // Normalize the basis vectors
 for (int v = 0; v < vertexArray.size(); ++v) {
 // Remove the component parallel to the normal
 const Vector3& N = vertexNormalArray[v];
 Vector3& T = tangent[v];
 Vector3& B = binormal[v];

 debugAssertM(N.isUnit() || N.isZero(), "Input normals must have unit length");

 T -= T.dot(N) * N;
 B -= B.dot(N) * N;

 // Normalize
 T = T.directionOrZero();
 B = B.directionOrZero();
 }
}

Here is the call graph for this function:

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

static

Welds nearby and colocated elements of the oldVertexArray together so that newVertexArray contains no vertices within radius 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:

oldVertexArray[toOld[ni]] == newVertexArray[ni]
oldVertexArray[oi] == newVertexArray[toNew[ni]]

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.

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

See also G3D::MeshAlg::weldAdjacency.

[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.

 {

 shared_ptr<_internal::Welder> welder = shared_ptr<_internal::Welder> (new _internal::Welder(oldVertexArray, newVertexArray, toNew, toOld, radius));
 welder->weld();
}

Here is the caller graph for this function:

int G3D::MeshAlg::countBoundaryEdges ( const Array< Edge > &  edgeArray )

static

Counts the number of edges (in an edge array returned from MeshAlg::computeAdjacency) that have only one adjacent face.

 {
 int b = 0;

 for (int i = 0; i < edgeArray.size(); ++i) {
 if ((edgeArray[i].faceIndex[0] == MeshAlg::Face::NONE) !=
 (edgeArray[i].faceIndex[1] == MeshAlg::Face::NONE)) {
 ++b;
 }
 }

 return b;
}

Here is the call graph for this function:

void G3D::MeshAlg::createIndexArray ( int  n, Array< int > &  array, int  start = 0, int  run = 1, int  skip = 0  )

static

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:

  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]

 {
 debugAssert(skip >= 0);
 debugAssert(run >= 0);

 array.resize(n);
 if (skip == 0) {
 for (int i = 0; i < n; ++i) {
 array[i] = start + i;
 }
 } else {
 int rcount = 0;
 int j = start;
 for (int i = 0; i < n; ++i) {
 array[i] = j;

 ++j;
 ++rcount;

 if (rcount == run) {
 rcount = 0;
 j += skip;
 }
 }
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void G3D::MeshAlg::debugCheckConsistency ( const Array< Face > &  faceArray, const Array< Edge > &  edgeArray, const Array< Vertex > &  vertexArray  )

static

In debug mode, asserts that the adjacency references between the face, edge, and vertex array are consistent.

 {

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

Here is the call graph for this function:

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

staticprotected

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.

Parameters

vertexArray	Vertex positions to use when deciding colocation.
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.

void G3D::MeshAlg::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()  )

static

Generates a unit square in the X-Z plane composed of a grid of wCells x hCells squares on the unit interval and then transforms it by xform.

Parameters

vertex	Output vertices
texCoord	Output texture coordinates
index	Output triangle list indices
textureScale	Lower-right texture coordinate
spaceCentered	If true, the coordinates generated are centered at the origin before the transformation.
twoSided	If true, matching top and bottom planes are generated.
elevation	If non-NULL, values from this image are used as elevations. Apply an xform to adjust the scale

 {
 
 vertex.fastClear();
 texCoord.fastClear();
 index.fastClear();

 // Generate vertices 
 for (int z = 0; z <= hCells; ++z) {
 for (int x = 0; x <= wCells; ++x) {
 Vector3 v(x / (float)wCells, 0, z / (float)hCells);

 Vector2 t = v.xz() * textureScale;

 texCoord.append(t);

 if (height) {
 v.y = height->nearest(v.x * (height->width() - 1), v.z * (height->height() - 1)).value;
 }
 if (spaceCentered) {
 v -= Vector3(0.5f, 0, 0.5f);
 }
 v = xform.pointToWorldSpace(v);
 vertex.append(v);
 }
 }

 // Generate indices
 for (int z = 0; z < hCells; ++z) {
 for (int x = 0; x < wCells; ++x) {
 int A = x + z * (wCells + 1);
 int B = A + 1;
 int C = A + (wCells + 1);
 int D = C + 1;

 // A B
 // *-----*
 // | \ |
 // | \ |
 // *-----*
 // C D

 index.append(A, D, B);
 index.append(A, C, D);
 }
 }

 if (twoSided) {
 // The index array needs to have reversed winding for the bottom
 // and offset by the original number of vertices
 Array<int> ti = index;
 ti.reverse();
 for (int i = 0; i < ti.size(); ++i) {
 ti[i] += vertex.size();
 }
 index.append(ti);

 // Duplicate the arrays
 vertex.append(Array<Vector3>(vertex));
 texCoord.append(Array<Vector2>(texCoord));
 }
}

Here is the call graph for this function:

void G3D::MeshAlg::identifyBackfaces ( const Array< Vector3 > &  vertexArray, const Array< Face > &  faceArray, const Vector4 &  P, Array< bool > &  backface  )

static

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.

 {

 Vector3 P = HP.xyz();

 backface.resize(faceArray.size());

 if (fuzzyEq(HP.w, 0.0f)) {
 // Infinite case
 for (int f = faceArray.size() - 1; f >= 0; --f) {
 const MeshAlg::Face& face = faceArray[f];

 const Vector3& v0 = vertexArray[face.vertexIndex[0]];
 const Vector3& v1 = vertexArray[face.vertexIndex[1]];
 const Vector3& v2 = vertexArray[face.vertexIndex[2]];
 
 const Vector3 N = (v1 - v0).cross(v2 - v0);

 backface[f] = N.dot(P) < 0;
 }
 } else {
 // Finite case
 for (int f = faceArray.size() - 1; f >= 0; --f) {
 const MeshAlg::Face& face = faceArray[f];

 const Vector3& v0 = vertexArray[face.vertexIndex[0]];
 const Vector3& v1 = vertexArray[face.vertexIndex[1]];
 const Vector3& v2 = vertexArray[face.vertexIndex[2]];
 
 const Vector3 N = (v1 - v0).cross(v2 - v0);

 backface[f] = N.dot(P - v0) < 0;
 }
 }
}

Here is the call graph for this function:

void G3D::MeshAlg::identifyBackfaces ( const Array< Vector3 > &  vertexArray, const Array< Face > &  faceArray, const Vector4 &  P, Array< bool > &  backface, const Array< Vector3 > &  faceNormals  )

static

A faster version of identifyBackfaces for the case where face normals have already been computed

 {

 Vector3 P = HP.xyz();

 backface.resize(faceArray.size());

 if (fuzzyEq(HP.w, 0.0f)) {
 // Infinite case
 for (int f = faceArray.size() - 1; f >= 0; --f) {
 const Vector3& N = faceNormals[f];
 backface[f] = N.dot(P) < 0;
 }
 } else {
 // Finite case
 for (int f = faceArray.size() - 1; f >= 0; --f) {
 const MeshAlg::Face& face = faceArray[f]; 
 const Vector3& v0 = vertexArray[face.vertexIndex[0]];
 const Vector3& N = faceNormals[f];

 backface[f] = N.dot(P - v0) < 0;
 }
 }
}

Here is the call graph for this function:

template<class IndexType >

static void G3D::MeshAlg::toIndexedTriList ( const Array< IndexType > &  inIndices, MeshAlg::Primitive  inType, Array< IndexType > &  outIndices  )

inlinestatic

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.

 {

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

Here is the call graph for this function:

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

static

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.

Parameters

faceArray	Mutated in place. Size is maintained (degenerate faces are not removed).
edgeArray	Mutated in place. May shrink if boundary edges are welded together.
vertexArray	Mutated in place. Size is maintained (duplicate vertices contain no adjacency info).

 {

 // Num vertices
 const int n = originalGeometry.size();

 // canonical[v] = first occurance of any vertex near oldVertexArray[v]
 Array<int> canonical;
 canonical.resize(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);
 }
}

Here is the call graph for this function:

void G3D::MeshAlg::weldBoundaryEdges ( Array< Face > &  faceArray, Array< Edge > &  edgeArray, Array< Vertex > &  vertexArray  )

staticprivate

Helper for weldAdjacency

 {

 // 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;
 newEdgeIndex.resize(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];
 }
 }
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

---

The documentation for this class was generated from the following files:

• dep/g3dlite/include/G3D/MeshAlg.h
• dep/g3dlite/source/MeshAlg.cpp
• dep/g3dlite/source/MeshAlgAdjacency.cpp
• dep/g3dlite/source/MeshAlgWeld.cpp