INTERFACE Triangulation; (* Triangulated tridimensional meshes for automatic topology visualization. This interface contain essentially procedures created by J. Stolfi and R. Marcone (see the copyright and authorship futher down), modified extensively by L. Lozada for the tridimensional case. *) IMPORT Map3D, Random, R3, LR4, Wr; (* === Elements of tetrahedron === *) PROCEDURE TetraNegVertices(a: Handle): ARRAY [0..3] OF Vertex; (* The vertices of the tetrahedron "Pneg(a)", namely the origins of a, nextE(a), prevE(a), Flip(nextE(prevF(a))). *) PROCEDURE TetraPosVertices(a: Handle): ARRAY [0..3] OF Vertex; (* The vertices of the tetrahedron "Ppos(a)", namely the origins of of a, nextE(a), prevE(a), Flip(nextE(nextF(a))). *) PROCEDURE TetraNegPosVertices(a: Handle): ARRAY [0..4] OF Vertex; (* The vertices of the tetrahedra "Pneg(a)" and "PposP(a)", namely the origins of a, nextE(a), prevE(a), prevE(prevF(a)), prevE(nextF(a)). *) PROCEDURE TetraNegFaces(a: Handle): ARRAY [0..3] OF Face; (* The four faces of the tetrahedron "Pneg(a)", namely the faces of a, Flip(prevF(a)), Flip(prevF(nextE(a))), and Flip(prevF(prevE(a))). *) PROCEDURE TetraNegEdges(a: Handle): ARRAY [0..5] OF Edge; (* The six edges of the tetrahedron "Pneg(a)". *) PROCEDURE FaceEdges(a: Handle): ARRAY [0..2] OF Edge; (* The three edges of the (triangular) face of "a". *) PROCEDURE FaceVertices(a: Handle): ARRAY [0..2] OF Vertex; (* The three vertices of the (triangular) face of "a". *) (* === CONSTRUCTION TOOLS === *) PROCEDURE MakeTriangle(): Handle; (* Returns a map with a single triangular face, three vertices, three edges. The map has one cell but the cell record is NIL. *) PROCEDURE MakeTetraTopo(nx, ny: CARDINAL): ARRAY [0..7] OF Handle; (* Builds a topological tetrahedron subdivided radialy. The number of tetrahedra cells is "nx" by "ny". Returns the corners fes handles (8). *) PROCEDURE EmphasizeTetrahedron(a, b: Handle; n: CARDINAL); (* Emphasizes the original elements of a tetrahedron produced by the MakeTetraTopo(order,order) procedure. *) PROCEDURE Glue( a,b : Handle; n: CARDINAL; setorg: BOOLEAN := TRUE; ) : Handle; (* Glue two topological tetrahedra, by identification the "n" triangular facets on the topological boundary of tetrahedra. The traversal of the topological boundary will be realized by Quad- Edge's functions reducided to functions FaceEdge.The identification of triangular facets will be done by the "meld" procedure, removing the handles fes on the chain "b" and updating the relations between vertices and cells. If SetOrg = TRUE then the SetAllOrgs is executed. *) (* === GLOBAL PROCEDURES === *) (* PROCEDURE DegreeOfFaceEdges(a: Handle) : CARDINAL ; (* Return the number of handles fes with the same origin that handle "a". *) PROCEDURE Edgeswso(READONLY a: Handle) : REF ARRAY OF Handle ; (* Return one handle fe for each edge incident to the origin of p. "a". *) *) PROCEDURE DegreeOfVertex(a: Handle) : CARDINAL ; (* Compute the degree of vertex that is Org(a) (i.e. the number of component edges incident to vertex). *) TYPE AdjacencyMatrix = ARRAY OF ARRAY OF BOOLEAN; PROCEDURE MakeAdjacencyMatrix(READONLY top: Topology): REF AdjacencyMatrix; (* Builds the adjacency matrix for the topology "top". *) PROCEDURE TriviallyIsomorphic(READONLY ta, tb: Topology): BOOLEAN; (* True iff "ta" and "tb" are topologically isomorphic, with the trivial isomorphism (that is, if elements with same index have the same topological relationship in both). *) PROCEDURE GetVariableVertices( READONLY top: Topology; VAR vr: ARRAY OF BOOLEAN; ); (* Sets "vr[v] := TRUE" for every vertex "v" that is not fixed. *) PROCEDURE FaceCross(a: Handle; READONLY c: Coords): LR4.T; (* A vector approximately perpendicular to component face of handle "a", this vector is computing by the mean of two perpendicular vectors (with orientation topological consistent) for two tetrahedrons inci- dents in this face. Returns the unit vector if the face has atributte "exists=FALSE". *) PROCEDURE FaceNormal(a: Handle; READONLY c: Coords): LR4.T; (* Normal of component face of "a"; same as "LR4.Dir(FaceCross(a, c))". Returns an arbitrary unit vector if the face has zero area. *) PROCEDURE PolyCross(a: Handle; READONLY c: Coords): LR4.T; (* A vector approximately perpendicular to Pneg of handle "a". Returns the unit vector if the cell has atributte "exists=FALSE". *) PROCEDURE PolyNormal(a: Handle; READONLY c: Coords): LR4.T; (* Normal of "Pneg(a)"; same as "LR4.Dir(PolyCross(a, c))". Returns an arbitrary unit vector if the face has zero area *) PROCEDURE EdgeCross(a: Handle; READONLY c: Coords): LR4.T; (* A vector approximately perpendicular to component edge of handle "a", this vector is computing by the mean of perpendicular vectors (with orientation topological consistent) to all tetrahedrons incidents in this edge. Returns the unit vector if the edge has atributte "exists=FALSE". *) PROCEDURE EdgeNormal(a: Handle; READONLY c: Coords): LR4.T; (* Normal of component edge of "a"; same as "LR4.Dir(EdgeCross(a, c))". Returns an arbitrary unit vector if the edge has zero lenght. *) PROCEDURE TetraBarycenter(a: Handle; READONLY c: Coords): LR4.T; (* The barycenter of the negative tetrahedron of handle "a". *) PROCEDURE VertexCross(a: Handle; READONLY c: Coords; READONLY top: Topology): LR4.T; (* A vector approximately orthogonal to the Org(a), whose length is proportional the volume of the cell defined by the "existing" neighbors of "Org(a)". *) PROCEDURE VertexNormal(a: Handle; READONLY c: Coords; READONLY top: Topology): LR4.T; (* Estimated normal at Org(a), considering only neighbors that exist; same as "LR4.Dir(VertexCross(a, c))". Returns an arbitrary unit vector if "VertexCross(a, c)" is zero. *) TYPE Quadp = ARRAY [0..3] OF Handle; Quadv = ARRAY [0..3] OF Vertex; Triv = ARRAY [0..2] OF Vertex; Trip = ARRAY [0..2] OF Handle; <* OBSOLETE *> PROCEDURE NeighborVertex( a: Handle; READONLY top: Topology; ): REF ARRAY OF Vertex; (* Neighbor vertices of "OrgV(a)" in a triangulation. *) (* === GEOMETRIC TOOLS === *) PROCEDURE StarOfVertex(a: Handle; READONLY top: Topology): REF ARRAY OF Quadv; (* Return the vertex set that conform every tetrahedron belonging to star of OrgV(a). The vertex set is sorted such as, the first element is OrgV(a), the second is OrgV(nextE(a)), the third OrgV(prevE(a)) and the las element is OrgV(prevE(prevF(a))). *) PROCEDURE NumberPolyOfStar(quadv: REF ARRAY OF Quadv): CARDINAL; (* Return the number of cells that belong to star of OrgV(a). *) PROCEDURE ComputeAllVertexNormals(READONLY top: Topology; READONLY c: Coords ): REF ARRAY OF LR4.T; (* Returns a vector with the result of VertexNormal applied to each vertex of "top". *) PROCEDURE ComputeAllEdgeNormals(READONLY top: Topology; READONLY c: Coords ): REF ARRAY OF LR4.T; (* Returns a vector with the result of EdgeNormal applied to each edge of "top". *) PROCEDURE ComputeAllFaceNormals(READONLY top: Topology; READONLY c: Coords ): REF ARRAY OF LR4.T; (* Returns a vector with the result of Face Normal applied to each face of "top". *) PROCEDURE ComputeAllCellNormals(READONLY top: Topology; READONLY c: Coords ): REF ARRAY OF LR4.T; (* Returns a vector with the result of PolyNormal applied to each polyhe- dron of "top". *) END Triangulation. (**************************************************************************) (* *) (* Copyright (C) 2000 Universidade Estadual de Campinas (UNICAMP) *) (* *) (* Authors: *) (* L. P. Lozada & J. Stolfi - UNICAMP *) (* *) (* This file can be freely used, distributed, and modified, provided that *) (* this copyright and authorship notice is included in every copy or *) (* derived version. *) (* *) (* DISCLAIMER: This software is offered ``as is'', without any guarantee *) (* as to fitness for any particular purpose. Neither the copyright *) (* holder nor the authors or their employers can be held responsible *) (* for any damages that may result from its use. *) (* *) (**************************************************************************)