To view this content, you need to install Java from java.com

CS3451, Summer 2006, Project 3
Triangle Mesh
Catherine Herrington, Email: catherine@polter.net
Submitted June 15, 2006. Source code: Tmeshs. p3d
Built with Processing
Data files: mesh.vts, mesh1.vts, mesh2.vts.



Reversed Triangles

The mesh.vts data file, containing the vertices and triangles for a torus, has the orientation of triangle 0 reversed.

The mesh1.vts data file, containing a torus with additional triangles with reversed orientation, has triangles 0, 4, 10, 17, and 29 reversed.

The mesh2.vts data file, containing the torus and a cube within a cube, has triangles 3, 4, 44, 45, 46, and 47 reversed.

To change between the different data files, press the 'm' key.

int sign (vec U, vec V, vec W)

This procedure determines the mixed product for the three vectors. This procedure is similar to the cw (clockwise) procedure. The If the mixed value is close to zero, then 0 is returned. By returning zero, it is know if the vectors might be coplanar. Otherwise, if the value is positive, then the triangle is clockwise and a 1 is returned. If the value is negative, then the triangle is counterclockwise and a -1 is returned.


void swap(int i)

This procedure reverses the orientation of a triangle composed of points A, B, and C by swaping vertices B and C.


boolean rayHitTriangle(pt P, vec T, pt A, pt B, pt C)

This procedure has been replaced by rayHitTriangleEdge. Point P is the center of the triangle that has its orientation in question.
Vector T is the normal of this triangle.
Points A, B, and C are the points of the triangle that we are trying to determine if T will hit.


Vector PA is the vector from P to A.
Vector PB is the vector from P to B.
Vector PC is the vector from P to C.


Boolean sP determines if PA, PB, and PC are clockwise or counter-clockwise by calling cw()
Boolean sA determines if T, PB, and PC are clockwise or counter-clockwise by calling cw().
Boolean sB determines if PA, T, and PC are clockwise or counter-clockwise by calling cw().
Boolean sC determines if PA, PB, and T are clockwise or counter-clockwise by calling cw().


If sP, sA, sB, and sC have the same value, then the ray (from point P and vector T) hits the triangle (A,B,C).


int rayHitTriangleEdge(pt P, vec T, pt A, pt B, pt C)

This procedure is similar to the rayHitTriangle procedure except that this procedure attempts to avoid rays that hit a vertex or edge.

Integer iP determines if PA, PB, and PC are clockwise, counter-clockwise, or coplanar by calling sign()
Integer iA determines if T, PB, and PC are clockwise, counter-clockwise, or coplanar by calling sign().
Integer iB determines if PA, T, and PC are clockwise, counter-clockwise, or coplanar by calling sign().
Integer iC determines if PA, PB, and T are clockwise, counter-clockwise, or coplanar by calling sign().


If iP, iA, iB, and iC have the same value, then the ray (from point P and vector T) possibly hits the triangle (A,B,C).


void orientTriangles()

This procedure has been replaced by orientTrianglesEdges. For each triangle, we determine if it hits any other triangle by calling rayHitTriangle with the following parameters:
Point pCenter is the center of the triangle that has its orientation in question.
Vector vNormal is the normal of this triangle.
Points G[V[3*j]], G[V[3*j+1]], and G[V[3*j+2]] are the points of the triangle that we are trying to determine if vNormal will hit.


If it is determined that the ray hits the triangle, then the number hits is used to determine if the orientation is correct (# of hits are even) or if the orientation is incorrect (# of hits are odd). If the orientation is incorrect, that the swap() procedure is called for that triangle to reverse the orientation and the color for the triangle is specified as magenta.

This procdure will fail when:
The procedure orientTrianglesEdges attempts to resolve the case in which the ray goes through edges or vertices.


void orientTrianglesEdges()

This procedure is similar to the orientTriangles procedure except that this procedure attempts to avoid rays that hit a vertex or edge. This procedure orients the triangles before the o-table is constructed. For each triangle, we determine if it hits any other triangle by calling rayHitTriangleEdge. If rayHitTriangleEdge determines that the values could be coplanar, then a new point pCenter is selected (by calling triOffCenter) and a new vector vNormal is selected (by calling triOffNormal) and rayHitTriangleEdge is called again.

If it is determined that the ray hits the triangle, then the number hits is used to determine if the orientation is correct (# of hits are even) or if the orientation is incorrect (# of hits are odd). If the orientation is incorrect, that the swap() procedure is called for that triangle to reverse the orientation and the color for the triangle is specified as magenta.


vec triOffNormal(int i)

Instead of using points A, B, and C of a triangle to determine the Normal vector, this procedure uses a different point A' for point A to compute a Normal that is slightly off than the original. This procedure determines the center point of the triangle ctrPt and creates a new point A' that is midway between A and ctrPt.


pt triOffCenter(int i)

Instead of using points A, B, and C of a triangle to determine the center point, this procedure uses a different point A' for point A to compute a center point that is slightly off than the original. This procedure determines the center point of the triangle ctrPt and creates a new point A' that is midway between A and ctrPt.


void shell()

This procedure calls the Visit procedure to visit every adjacent triangle in the mesh that has not been assigned a color. When a shell has been completed, the color table will be searched for the next triangle that has not been assigned a color. A new color will be specified for the next shell and the Visit procedure will be called to visit all of the adjacent triangles in the new shell. This procedure is called after the O-table has been constructed. In mesh2.vts, three shells have been identified and colored. One of the shells is contained inside of the cube.


void Visit(int c, int iColor)

This procedure visits every adjacent triangle in the mesh that has not been assigned a color. This is accomplished by marking each triangle with a specified color. If the triangle to the right of the current corner has not been marked, perform a recursive call and visit the corner to the right. If the triangle to the left of the current corner has not been marked, perform a recursive call and visit the corner to the left. This procedure will visit every triangle in a shell.