Contents User Forum Source Index APIs by Task APIs by Level Data

G3D::MeshAlg

G3D::MeshAlg Class Reference

Indexed mesh algorithms. More...

#include <MeshAlg.h>

List of all members.

Public Types

enum Primitive {
LINES, LINE_STRIP, TRIANGLES, TRIANGLE_STRIP,
TRIANGLE_FAN, QUADS, QUAD_STRIP, POINTS
}

Static Public Member Functions

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

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

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 computeBounds (const Array< Vector3 > &vertex, const Array< int > &index, class Box &box, class Sphere &sphere)

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

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

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

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

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

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 computeWeld (const Array< Vector3 > &oldVertexPositions, Array< Vector3 > &newVertexPositions, Array< int > &toNew, Array< int > &toOld, double radius=G3D::fuzzyEpsilon)

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 debugCheckConsistency (const Array< Face > &faceArray, const Array< Edge > &edgeArray, const Array< Vertex > &vertexArray)

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

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

template<class IndexType>

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

static void weldAdjacency (const Array< Vector3 > &originalGeometry, Array< Face > &faceArray, Array< Edge > &edgeArray, Array< Vertex > &vertexArray, double radius=G3D::fuzzyEpsilon)

Static Protected Member Functions

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

Classes

class Edge

Oriented, indexed edge. More...

class Face

Oriented, indexed triangle. More...

class Geometry

Convenient for passing around the data that changes under animation. More...

class Vertex

Adjacency information for a vertex. 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.

Member Enumeration Documentation

enum G3D::MeshAlg::Primitive

Enumerator:

LINES
LINE_STRIP
TRIANGLES
TRIANGLE_STRIP
TRIANGLE_FAN
QUADS
QUAD_STRIP
POINTS

Member Function Documentation

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

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

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:

	vertexGeometry	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

static void G3D::MeshAlg::computeBounds	(	const Array< Vector3 > &	vertex,
		const Array< int > &	index,
		class Box &	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.

static void G3D::MeshAlg::computeBounds	(	const Array< Vector3 > &	vertex,
		class Box &	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.

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.

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.

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

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:

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

static void G3D::MeshAlg::computeWeld	(	const Array< Vector3 > &	oldVertexPositions,
		Array< Vector3 > &	newVertexPositions,
		Array< int > &	toNew,
		Array< int > &	toOld,
		double	radius = `G3D::fuzzyEpsilon`
	)			`[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.

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

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.

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]

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.

static int G3D::MeshAlg::findEdgeIndex	(	const Array< Vector3 > &	vertexArray,
		Array< Edge > &	geometricEdgeArray,
		int	i0,
		int	i1,
		int	f,
		double	area
	)			`[static, 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.

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.

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.

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.

template<class IndexType>

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

Converts quadlist (QUADS), tristrip(TRIANGLE_STRIP), and quadstrip (QUAD_STRIP)indices into triangle list (TRIANGLES) indices.

static void G3D::MeshAlg::weldAdjacency	(	const Array< Vector3 > &	originalGeometry,
		Array< Face > &	faceArray,
		Array< Edge > &	edgeArray,
		Array< Vertex > &	vertexArray,
		double	radius = `G3D::fuzzyEpsilon`
	)			`[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.

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

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

MeshAlg.h

Generated on Thu Aug 2 11:40:47 2007 for G3D by

1.5.2

Hosted by