HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_Tetrahedralize.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_Tetrahedralize.h (UT Library, C++)
7  *
8  * COMMENTS:
9  *
10  * This calculates the 3D Delaunay triangulation (tetrahedralization)
11  * of the input points. Note that it does not support constrained
12  * triangulation or refinement. This implementation closely follows:
13  * Ledoux, Hugo. "Computing the 3D Voronoi Diagram Robustly:
14  * An Easy Explanation."
15  * Proceedings 4th International Symposium on Voronoi Diagrams in
16  * Science and Engineering.
17  * Pontypridd, Wales, UK. 2007. pp. 117-129
18  * http://www.gdmc.nl/ledoux/pdfs/_07isvd.pdf
19  *
20  * It uses Schewchuk's geometric predicates as provided in
21  * UT_GeometryPredicate.h to ensure robustness when the
22  * points are in degenerate positions.
23  */
24 
25 
26 #ifndef __UT_Tetrahedralize_h
27 #define __UT_Tetrahedralize_h
28 
29 #include "UT_API.h"
30 #include "UT_Array.h"
31 #include "UT_Vector3.h"
32 #include "UT_Interrupt.h"
33 
34 class UT_TetTetrahedron;
36 
39 
40 /// The UT_TetVertex class contains the position of the vertex, a data
41 /// parameter for use by calling code, and a list of the Tetrahedra
42 /// containing this vertex.
43 /// Note that this tetrahedron list will not be valid until after a
44 /// call to tetrahedralization completes successfully.
46 {
47 public:
48  UT_TetVertex(const UT_Vector3 &p, void *data = NULL);
49 
50  void addTet(UT_TetTetrahedron *t);
51  /// Calculates the vertices that share an edge with this one
52  /// in one or more tetrahedra.
53  void incidentVertices(UT_TetVertexArray &incident) const;
54 
55  const UT_Vector3 &getPos() const {return myPos;}
56 
57  /// A data parameter that can be used for arbitrary purposes by
58  /// calling code.
59  void setData(void *d) {myData = d;}
60  void *data() const {return myData;}
61 private:
62  UT_Vector3 myPos;
63  void *myData;
65 };
66 
67 /// The UT_TetFace struct is a simple container class to hold UT_TetVertex
68 /// objects, and represents the triangular faces of a tetrahedron.
69 /// They are created on the fly during the tetrahedralization
70 /// process, and are not stored by any other objects.
72 {
74  a(NULL), b(NULL), c(NULL) {}
76  a(a_), b(b_), c(c_) {}
77  bool hasVertex(const UT_TetVertex *v) const {return a == v || b == v || c == v;}
78  UT_TetVertex *a, *b, *c;
79 };
80 
81 /// The UT_TetTetrahedron class is the primary structure in the
82 /// tetrahedralization process.
83 /// It holds pointers to its four vertex objects, as well as to any
84 /// adjacent tetrahedra.
85 /// The convention is that a particular adjacent tetrahedra is stored
86 /// with the same index as the face to which it is adjacent and the
87 /// vertex from which it is opposite.
88 /// In other words, adjacent(i) is adjacent to face(i), which is opposite
89 /// vertex(i).
90 ///
91 /// Several of the member functions are related to maintaining the
92 /// adjacency relationships during the tetrahedralization process.
93 /// They are called only from the various flip?? functions.
94 ///
95 /// This class also holds a visited flag that is used to stop iterating
96 /// during walks through adjacent tetrahedra in the walk function and
97 /// the tetrahedralization function. This is faster than using something
98 /// like hboost::unordered_set to keep track of visited tetrahedra at the
99 /// expense of a small amount of memory.
101 {
102 public:
104 
105  /// Calls UT_TetVertex::addTet on each of its vertices.
106  void addToVertices();
107 
108  /// Updates the adjacency information for the face opposite vertex v.
109  void setAdjacentOppositeVertex(const UT_TetVertex *v,
110  UT_TetTetrahedron *tet);
111  UT_TetTetrahedron *adjacentOppositeVertex(const UT_TetVertex *v) const;
112 
113  /// Updates the adjacency information for the face opposite vertex v, and
114  /// (if non-NULL) also updates the provided tetrahedron's adjacency to
115  /// point to this tetrahedron.
116  void updateAdjacency(const UT_TetVertex *v, UT_TetTetrahedron *tet);
117 
118  /// Returns the tetrahedron adjacent to this one at the given face.
119  UT_TetTetrahedron *adjacentAtFace(const UT_TetFace &f) const;
120 
121  /// Returns whether a particular tetrahedron is adjacent to this one.
122  bool hasAdjacent(const UT_TetTetrahedron *tAdj) const;
123 
124  /// Clears out any adjaceny pointers set to provided tetrahedron.
125  void clearAdjacency(UT_TetTetrahedron* tAdj);
126 
127  /// Tests for the existence of a given face, vertex, any of a set of
128  /// vertices.
129  bool hasFace(const UT_TetFace &f) const;
130  bool hasVertex(UT_TetVertex* v) const;
131  bool hasAnyVertex(const UT_TetVertexArray &verts) const;
132 
133  bool vertexInside(const UT_TetVertex *v) const;
134 
135  /// Diagnostic function - should always return true when tet is
136  /// locally delaunay with tetrahedralization.
137  bool delaunay() const;
138 
139  /// Returns the first vertex in this that is not in provided tetrahedron.
140  UT_TetVertex *distinctVertex(const UT_TetTetrahedron *tAdj) const;
141 
142  /// Returns the first vertex in this that is not in the provided face.
143  UT_TetVertex *distinctVertex(const UT_TetFace &f) const;
144 
145  /// Unchecked access to vertices,
146  UT_TetVertex *vertex(unsigned int i) const {return myVerts[i];}
147  /// Unchecked access to adjacent tetrahedra,
148  UT_TetTetrahedron *adjacent(unsigned int i) const {return myAdjacent[i];}
149  /// Returns face such that face(i) is opposite from vertex(i) and
150  /// adjacent to adjacent(i).
151  UT_TetFace face(unsigned int i) const;
152 
153  /// Visited flag.
154  void setVisited(bool b) {myVisited = b;}
155  bool visited() const {return myVisited;}
156 private:
157  UT_TetVertex *myVerts[4];
158  UT_TetTetrahedron *myAdjacent[4];
159  bool myVisited;
160 };
161 
162 /// The tetrahedralization function. The input is an array of pointers to
163 /// UT_TetVertex objects; the output is a list of pointers to UT_TetTetrahedron
164 /// objects. The caller is responsible for deleting the UT_TetTetrahedron
165 /// objects (and probably the UT_TetVertex objects, depending on how they were
166 /// created).
167 /// The boss parameter allows the caller to provide a UT_Interrupt object
168 /// to poll for interrupts and update with progress. The interruptInterval
169 /// is the number of points processed between calls to
170 /// UT_Interrupt::opinterrupt.
171 ///
172 /// This function returns false if the tetrahedralization fails, meaning the
173 /// tetrahedralization is in an invalid state, although that really, really
174 /// should not happen. Note that duplicate points are degenerate and will
175 /// not be inserted into the tetrahedralization, but this does not indicate
176 /// a failure condition.
177 UT_API bool
178 UTtetrahedralize( const UT_TetVertexArray &verts,
179  UT_TetTetrahedronArray &tets);
180 #endif
void setVisited(bool b)
Visited flag.
void setData(void *d)
const GLdouble * v
Definition: glcorearb.h:836
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
UT_TetFace(UT_TetVertex *a_, UT_TetVertex *b_, UT_TetVertex *c_)
#define UT_API
Definition: UT_API.h:12
png_uint_32 i
Definition: png.h:2877
GLfloat f
Definition: glcorearb.h:1925
UT_Array< UT_TetTetrahedron * > UT_TetTetrahedronArray
UT_TetVertex * vertex(unsigned int i) const
Unchecked access to vertices,.
UT_TetTetrahedron * adjacent(unsigned int i) const
Unchecked access to adjacent tetrahedra,.
GLboolean * data
Definition: glcorearb.h:130
UT_API bool UTtetrahedralize(const UT_TetVertexArray &verts, UT_TetTetrahedronArray &tets)
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
const UT_Vector3 & getPos() const
bool visited() const
bool hasVertex(const UT_TetVertex *v) const
void * data() const
UT_Array< UT_TetVertex * > UT_TetVertexArray
UT_TetVertex * c