The TriMesh class

1. Introduction

The TriMesh class represents a triangular mesh, together with:

• information about its vertices and faces
• per-vertex properties such as normals and colors
• global per-mesh properties like bounding boxes
• some connectivity information such as neighboring vertices

The library also contains code for

• .ply file I/O
• computing various per-vertex and per-mesh properties
• a random collection of utility functions often useful when manipulating or displaying meshes

The primary design considerations were ease of coding and space and time efficiency.

2. Quick Introduction

#include "trimesh.h"

	// Read a mesh
	TriMesh *mymesh = TriMesh::ReadPly("somefile.ply");
	if (!mymesh) {
		printf("Couldn't read mesh!\n");
		exit(1);
	}

	// If the mesh had triangle strips, unpack them into individual triangles
	if (mymesh->tstrips) {
		mymesh->need_faces();
		mymesh->free_tstrips();
	}

	// Print out some facts about vertices and faces
	printf("The mesh has %d vertices and %d triangles\n",
		mymesh->numvertices, mymesh->numfaces);
	printf("The coordinates of the 17th vertex are %f %f %f\n",
		mymesh->vertices[17][0], mymesh->vertices[17][1], mymesh->vertices[17][2]);
	printf("The 23rd face consists of vertices %d, %d, and %d\n",
		mymesh->faces[23][0], mymesh->faces[23][1], mymesh->faces[23][2]);
	if (mymesh->colors) {
		printf("The color of the 31st face is %d, %d, %d\n",
			mymesh->colors[31][0], mymesh->colors[31][1], mymesh->colors[31][2]);
	} else {
		printf("The mesh does not have per-vertex color\n");
	}


	// Print out some stats
	mymesh->need_bbox();
	printf("The mesh has X ranging from %f to %f, Y from %f to %f, and Z from %f to %f\n",
		mymesh->bbox->xmin, mymesh->bbox->xmax,
		mymesh->bbox->ymin, mymesh->bbox->ymax,
		mymesh->bbox->zmin, mymesh->bbox->zmax);
	printf("The average edge length of the mesh is %f\n", mymesh->meanedgelength());


	// Write out the file
	mymesh->WritePly("someotherfile.ply");

3. Members

The TriMesh class contains the following member data:

• numvertices contains the number of vertices in the mesh.
• vertices is an array of all the vertex coordinates. themesh->vertices[23] is a pointer-to-float that points to the three coordinates of the 24th vertex, and themesh->vertices[23][1] is the y coordinate of that vertex.
• numfaces is the number of triangles in the mesh.
• faces is an array of faces. For each face, there are three integers, representing the indices of the three vertices that make up that triangle. That is, themesh->faces[34] is a pointer-to-int that points to the three indices of the 35th face, themesh->faces[34][2] is the index of the third triangle of that face, and themesh->vertices[themesh->faces[34][2]][0] is the x coordinate of that vertex.
• colors is an array of per-vertex colors, accessed in the same way as vertices. It is present only if the mesh has per-vertex colors; otherwise, colors will be NULL. The type of a color is a triple of unsigned chars, so the range of each color component is 0 through 255.
• confidences is an array of per-vertex confidence values (e.g. as assigned by VRIP). As with colors, this is only present if the input mesh actually had per-vertex confidences. Confidences are represented as floats.
• normals is an array of per-vertex normal vectors. It is only available after you call themesh->need_normals(). It is accessed in exactly the same way as the vertices array.
• bbox is a pointer to a bounding box structure containing the elements xmin, xmax, xlen, ymin, ymax, ylen, zmin, zmax, zlen. Call need_bbox() before use...
• bsphere is a pointer to a bounding sphere structure containing the elements center and r, where center is a point that lies at the center of the bounding sphere, and r is the radius. Call need_bsphere() to use these.
• neighbors is a list of lists of neighboring (i.e. connected by an edge) vertices. themesh->neighbors[i][j] is the jth neighbor of vertex i. themesh->numneighbors[i] is the number of neighbors vertex i has. Also available are minneighbors and maxneighbors, which just contain the minimum and maximum number of neighbors of all the vertices in the mesh. As usual, call need_neighbors() to generate all of these.
• adjacentfaces is a list of lists of faces adjacent to each vertex. That is, themesh->adjacentfaces[i][j] is the index of the jth triangle that touches vertex i. numadjacentfaces[], need_adjacentfaces(), minadjacentfaces, and maxadjacentfaces also exist.
• tstrips is a list of triangle strips, and tstripdatalen tells how long this list is. The triangle strips themselves are stored as vertex indices separated by the value -1. You can cause triangle strips to be built with the need_tstrips() command. If you have triangle strips but not faces, you can unpack the triangle strips with the need_faces() command.

The class contains the following member functions:

• As mentioned before, the functions need_normals(), need_bbox(), need_bsphere(), need_neighbors(), need_adjacentfaces(), and need_faces() cause the specified quantities to be computed. There are also need_colors() and need_confidences() functions that just allocate space for these quantities if they were not present,
• For each need_* function there is a corresponding free_* function that frees the storage associated with those quantities.
• There are functions named minedgelength(), maxedgelength(), rmsedgelength(), meanedgelength(), and medianedgelength(), that return the minimum, maximum, root-mean-square, average, and median edge lengths for the mesh. The latter three functions take an optional boolean parameter (defaults to true) that specifies whether an approximation to the desired quantity will be computed by taking a random sample of ten thousand edges.
• The function RemoveVertices(const vector<bool> &toremove) takes as an argument a vector of bools of length numvertices, where toremove[i] specifies whether the i-th vertex should be removed. Note that removing vertices also removes their associated normals, colors, and confidences, and renumbers faces correctly.
• The function RemoveFaces(const vector<bool> &toremove) is exactly analogous, but removes faces.
• The function RemoveUnusedVertices() simply removes vertices that are not referenced by any face. It's often a good idea to follow RemoveFaces() by a call to RemoveUnusedVertices().

4. File input and output

• The static member function TriMesh::ReadPly(const char *plyfile) reads the .ply file named by its argument. It returns a pointer to a TriMesh if it succeeds, else it returns NULL. Note that only a very restricted subset of .ply files is supported - only binary big endian files with vertices and either faces or tristrips. If you need more generalized ply I/O routines, look in http://graphics.stanford.edu/software/zippack/.
• The member function WritePly(const char *plyfile) writes a mesh to a .ply file. Colors and confidences, if present, are saved. Triangle strips are written if they are present, else faces are written. No other per-vertex or per-mesh quantities are written.
• The function IsPlyFile(const char *plyfile) simply reads the header of the given file and guesses whether it is a .ply file.

5. triutil.h

triutil.h> contains a random collection of occasionally-useful utility functions. Most of the functions are templatized, so they can accept arguments of any type (OK, at least float and double...). The functions are:

• sqr(x) and cube(x) return the square and cube of x.
• Dot(x,y) returns the dot product of two 3-vectors
• Len(x) and Len2(x) return the length and the squared length of a 3-vector.
• Dist(x,y) and Dist2(x,y) return the distance and squared distance between two 3-vectors.
• CrossProd(x,y,z) sets z to be the cross product of x and y.
• FindNormal(p1,p2,p3,n) sets n to be the normal of a triangle with vertices at points p1, p2, and p3. Note that it is not necessarily unit-length.
• Normalize(v) normalizes 3-vector v (i.e. makes it unit length).
• MMult(M1,M2,Mout) sets Mout to be the product of 4x4 matrices M1 and M2. All matrices are in OpenGL (column-major) order.
• Project(P,M,V,vert,coord,zoffset=0) is a replacement for gluProject(), with an optional additional z offset.
• FastProjectPrecompute(F,P,M,V,zoffset=0) sets F to be a matrix that can be used by FastProject (below) to accomplish the same thing as Project.
• FastProject(F,vert,coord) uses F computed by FastProjectPrecompute to do the same thing as gluProject(), but faster.
• FastProject(F,x,y,z,xout,yout,zout) is just another way of calling FastProject, specifying the coordinates explicitly as separate parameters.
• FastProjectNoZ does the same thing as FastProject, but does not compute the Z coordinate, so is even faster.
• FastInvert(matrix) inverts the given 4x4 matrix. It assumes that the matrix represents a rigid-body (just rotation+translation) transformation and will give incorrect results otherwise.
• TriBoundingSphere(p1,p2,p3,cent,r) computes the center and radius of a sphere that encloses the triangle with vertices p1, p2, and p3.
• QNorm(q) normalizes a quaternion
• QCompose(q1,q2,q3) composes the quaternions q1 and q2, and sets q3 to the result.
• RotAndAxis2Q(rot,rotaxis,q) computes a quaternion from a rotation and an axis.
• Q2RotAndAxis(q,rot,rotaxis) is the reverse of the above.
• Mouse2TrackballPos(x,y,pos) takes normalized (-1..1) mouse coordinates and returns a position on a virtual trackball
• Mouse2Q(x1,y1,x2,y2,q) takes normalized mouse positions (x1,y1) and (x2,y2) and sets q to be the quaternion representing a rotation achieved by dragging the mouse from (x1,y1) to (x2,y2).
• QRotate(x,q) applies the rotation represented by quaternion q to point x.

6. Sample source

Source code to the following demo programs is provided:

• plycat just reads in a .ply file and dumps its vertices and faces as ASCII.
• plymunge reads a mesh and performs various trivial changes. Run plymunge -h for details.
• plyv is a very bare-bones OpenGL-based viewer for .ply files.