Indexed mesh algorithms. More...

Classes
class	Edge
	Oriented, indexed edge. More...

class	Face
	Oriented, indexed triangle. More...

class	Geometry
	Convenient for passing around the per-vertex data that changes under animation. More...

class	Vertex
	Adjacency information for a vertex. More...

Static Public Member Functions
static void	computeAdjacency (const Array< Vector3 > &vertexGeometry, const Array< int > &indexArray, Array< Face > &faceArray, Array< Edge > &edgeArray, Array< Vertex > &vertexArray)
	Given a set of vertices and a set of indices for traversing them to create triangles, computes other mesh properties. More...

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

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)
	Computes some basic mesh statistics including: min, max mean and median, edge lengths; and min, mean, median, and max face area. More...

static void	computeBounds (const Array< Vector3 > &vertex, class AABox &box, class Sphere &sphere)
	Computes a conservative, near-optimal axis aligned bounding box and sphere. More...

static void	computeBounds (const Array< Vector3 > &vertex, const Array< int > &index, class AABox &box, class Sphere &sphere)
	Computes bounds for a subset of the vertices. More...

static void	computeFaceNormals (const Array< Vector3 > &vertexArray, const Array< Face > &faceArray, Array< Vector3 > &faceNormals, bool normalize=true)
	Computes face normals only. More...

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)
	Vertex normals are weighted by the area of adjacent faces. More...

static void	computeNormals (Geometry &geometry, const Array< int > &indexArray)
	Computes unit length normals in place using the other computeNormals methods. More...

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)
	Computes tangent and binormal vectors, which provide a (mostly) consistent parameterization over the surface for effects like bump mapping. More...

static void	computeWeld (const Array< Vector3 > &oldVertexPositions, Array< Vector3 > &newVertexPositions, Array< int > &toNew, Array< int > &toOld, float radius=(0.00002f))
	Welds nearby and colocated elements of the oldVertexArray together so that newVertexArray contains no vertices within radius of one another. More...

static int	countBoundaryEdges (const Array< Edge > &edgeArray)
	Counts the number of edges (in an edge array returned from MeshAlg::computeAdjacency) that have only one adjacent face. More...

static void	createIndexArray (int n, Array< int > &array, int start=0, int run=1, int skip=0)
	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. More...

static void	debugCheckConsistency (const Array< Face > &faceArray, const Array< Edge > &edgeArray, const Array< Vertex > &vertexArray)
	In debug mode, asserts that the adjacency references between the face, edge, and vertex array are consistent. More...

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 shared_ptr< Image1 > &elevation=shared_ptr< Image1 >())
	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. More...

static void	identifyBackfaces (const Array< Vector3 > &vertexArray, const Array< Face > &faceArray, const Vector4 &P, Array< bool > &backface)
	Classifies each face as a backface or a front face relative to the observer point P (which is at infinity when P.w = 0). More...

static void	identifyBackfaces (const Array< Vector3 > &vertexArray, const Array< Face > &faceArray, const Vector4 &P, Array< bool > &backface, const Array< Vector3 > &faceNormals)
	A faster version of identifyBackfaces for the case where face normals have already been computed. More...

static void	identifyFeatureEdges (const Array< Vector3 > &vertexArray, const Array< Edge > &edgeArray, const Array< Face > &faceArray, const Array< Vector3 > &faceNormalArray, Array< bool > &feature, float creaseAngle=2.1f)
	Flags border (only one face, edge of the mesh), ridge (sharp convex), and valley (sharp concave) edges. More...

template<class IndexType >
static void	toIndexedTriList (const Array< IndexType > &inIndices, PrimitiveType inType, Array< IndexType > &outIndices)
	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. More...

static void	weldAdjacency (const Array< Vector3 > &originalGeometry, Array< Face > &faceArray, Array< Edge > &edgeArray, Array< Vertex > &vertexArray, float radius=(0.00002f))
	Modifies the face, edge, and vertex arrays in place so that colocated (within radius) vertices are treated as identical. More...

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

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 Function Documentation

◆ computeAdjacency() [1/2]

static 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

◆ computeAdjacency() [2/2]

static 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

◆ computeAreaStatistics()

static 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

◆ computeBounds() [1/2]

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

Referenced Code: 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.

◆ computeBounds() [2/2]

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

◆ computeFaceNormals()

static 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

◆ computeNormals() [1/3]

static 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:

◆ computeNormals() [2/3]

static 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

◆ computeNormals() [3/3]

static 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

◆ computeTangentSpaceBasis()

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

Referenced Code: Max McGuire

◆ computeWeld()

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

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

◆ countBoundaryEdges()

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

◆ createIndexArray()

static 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]

◆ debugCheckConsistency()

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

◆ findEdgeIndex()

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.

◆ generateGrid()

static 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 shared_ptr< Image1 > &	elevation = `shared_ptr< Image1 >()`
	)

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-nullptr, values from this image are used as elevations. Apply an xform to adjust the scale

◆ identifyBackfaces() [1/2]

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

◆ identifyBackfaces() [2/2]

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

◆ identifyFeatureEdges()

static void G3D::MeshAlg::identifyFeatureEdges	(	const Array< Vector3 > &	vertexArray,
		const Array< Edge > &	edgeArray,
		const Array< Face > &	faceArray,
		const Array< Vector3 > &	faceNormalArray,
		Array< bool > &	feature,
		float	creaseAngle = `2.1f`
	)

static

Flags border (only one face, edge of the mesh), ridge (sharp convex), and valley (sharp concave) edges.

Parameters

creaseAngle Interior or exterior angles sharper than this (in radians) between adjacent faces are considered creases (corners). Default is 120 degrees, which is slightly wider than the angles in a dodecahedron.

◆ toIndexedTriList()

template<class IndexType >

static void G3D::MeshAlg::toIndexedTriList	(	const Array< IndexType > &	inIndices,
		PrimitiveType	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.

◆ weldAdjacency()

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

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

Classes

Static Public Member Functions

Static Protected Member Functions

Detailed Description

Member Function Documentation

◆ computeAdjacency() [1/2]

◆ computeAdjacency() [2/2]

◆ computeAreaStatistics()

◆ computeBounds() [1/2]

◆ computeBounds() [2/2]

◆ computeFaceNormals()

◆ computeNormals() [1/3]

◆ computeNormals() [2/3]

◆ computeNormals() [3/3]

◆ computeTangentSpaceBasis()

◆ computeWeld()

◆ countBoundaryEdges()

◆ createIndexArray()

◆ debugCheckConsistency()

◆ findEdgeIndex()

◆ generateGrid()

◆ identifyBackfaces() [1/2]

◆ identifyBackfaces() [2/2]

◆ identifyFeatureEdges()

◆ toIndexedTriList()

◆ weldAdjacency()