1 /*=========================================================================
3 Program: Visualization Toolkit
4 Module: $RCSfile: vtkDelaunay3D.h,v $
6 Date: $Date: 2002/02/01 06:30:45 $
7 Version: $Revision: 1.1.1.1 $
10 Copyright (c) 1993-1998 Ken Martin, Will Schroeder, Bill Lorensen.
12 This software is copyrighted by Ken Martin, Will Schroeder and Bill Lorensen.
13 The following terms apply to all files associated with the software unless
14 explicitly disclaimed in individual files. This copyright specifically does
15 not apply to the related textbook "The Visualization Toolkit" ISBN
16 013199837-4 published by Prentice Hall which is covered by its own copyright.
18 The authors hereby grant permission to use, copy, and distribute this
19 software and its documentation for any purpose, provided that existing
20 copyright notices are retained in all copies and that this notice is included
21 verbatim in any distributions. Additionally, the authors grant permission to
22 modify this software and its documentation for any purpose, provided that
23 such modifications are not distributed without the explicit consent of the
24 authors and that existing copyright notices are retained in all copies. Some
25 of the algorithms implemented by this software are patented, observe all
26 applicable patent law.
28 IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
29 DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
30 OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY DERIVATIVES THEREOF,
31 EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING,
34 BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
35 PARTICULAR PURPOSE, AND NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN
36 "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
37 MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
40 =========================================================================*/
41 // .NAME vtkDelaunay3D - create 3D Delaunay triangulation of input points
42 // .SECTION Description
43 // vtkDelaunay3D is a filter that constructs a 3D Delaunay
44 // triangulation from a list of input points. These points may be
45 // represented by any dataset of type vtkPointSet and subclasses. The
46 // output of the filter is an unstructured grid dataset. Usually the
47 // output is a tetrahedral mesh, but if a non-zero alpha distance
48 // value is specified (called the "alpha" value), then only tetrahedra,
49 // triangles, edges, and vertices lying within the alpha radius are
50 // output. In other words, non-zero alpha values may result in arbitrary
51 // combinations of tetrahedra, triangles, lines, and vertices. (The notion
52 // of alpha value is derived from Edelsbrunner's work on "alpha shapes".)
54 // The 3D Delaunay triangulation is defined as the triangulation that
55 // satisfies the Delaunay criterion for n-dimensional simplexes (in
56 // this case n=3 and the simplexes are tetrahedra). This criterion
57 // states that a circumsphere of each simplex in a triangulation
58 // contains only the n+1 defining points of the simplex. (See text for
59 // more information.) While in two dimensions this translates into an
60 // "optimal" triangulation, this is not true in 3D, since a measurement
61 // for optimality in 3D is not agreed on.
63 // Delaunay triangulations are used to build topological structures
64 // from unorganized (or unstructured) points. The input to this filter
65 // is a list of points specified in 3D. (If you wish to create 2D
66 // triangulations see vtkDelaunay2D.) The output is an unstructured grid.
68 // The Delaunay triangulation can be numerically sensitive. To prevent
69 // problems, try to avoid injecting points that will result in
70 // triangles with bad aspect ratios (1000:1 or greater). In practice
71 // this means inserting points that are "widely dispersed", and
72 // enables smooth transition of triangle sizes throughout the
73 // mesh. (You may even want to add extra points to create a better
74 // point distribution.) If numerical problems are present, you will
75 // see a warning message to this effect at the end of the
76 // triangulation process.
79 // Points arranged on a regular lattice (termed degenerate cases) can be
80 // triangulated in more than one way (at least according to the Delaunay
81 // criterion). The choice of triangulation (as implemented by
82 // this algorithm) depends on the order of the input points. The first four
83 // points will form a tetrahedron; other degenerate points (relative to this
84 // initial tetrahedron) will not break it.
86 // Points that are coincident (or nearly so) may be discarded by the
87 // algorithm. This is because the Delaunay triangulation requires
88 // unique input points. You can control the definition of coincidence
89 // with the "Tolerance" instance variable.
91 // The output of the Delaunay triangulation is supposedly a convex hull. In
92 // certain cases this implementation may not generate the convex hull. This
93 // behavior can be controlled by the Offset instance variable. Offset is a
94 // multiplier used to control the size of the initial triangulation. The
95 // larger the offset value, the more likely you will generate a convex hull;
96 // and the more likely you are to see numerical problems.
98 // The implementation of this algorithm varies from the 2D Delaunay
99 // algorithm (i.e., vtkDelaunay2D) in an important way. When points are
100 // injected into the triangulation, the search for the enclosing tetrahedron
101 // is quite different. In the 3D case, the closest previously inserted point
102 // point is found, and then the connected tetrahedra are searched to find
103 // the containing one. (In 2D, a "walk" towards the enclosing triangle is
104 // performed.) If the triangulation is Delaunay, then an
107 // vtkDelaunay2D vtkGaussianSplatter vtkUnstructuredGrid
109 #ifndef __vtkDelaunay3D_h
110 #define __vtkDelaunay3D_h
112 #include "vtkPointSetFilter.h"
113 #include "vtkUnstructuredGrid.h"
115 class vtkSphereArray;
117 class VTK_EXPORT vtkDelaunay3D : public vtkPointSetFilter
122 static vtkDelaunay3D *New() {return new vtkDelaunay3D;};
123 const char *GetClassName() {return "vtkDelaunay3D";};
124 void PrintSelf(ostream& os, vtkIndent indent);
127 // Specify alpha (or distance) value to control output of this filter.
128 // For a non-zero alpha value, only edges or triangles contained within
129 // a sphere centered at mesh vertices will be output. Otherwise, only
130 // triangles will be output.
131 vtkSetClampMacro(Alpha,float,0.0,VTK_LARGE_FLOAT);
132 vtkGetMacro(Alpha,float);
135 // Specify a tolerance to control discarding of closely spaced points.
136 // This tolerance is specified as a fraction of the diagonal length of
137 // the bounding box of the points.
138 vtkSetClampMacro(Tolerance,float,0.0,1.0);
139 vtkGetMacro(Tolerance,float);
142 // Specify a multiplier to control the size of the initial, bounding
143 // Delaunay triangulation.
144 vtkSetClampMacro(Offset,float,2.5,VTK_LARGE_FLOAT);
145 vtkGetMacro(Offset,float);
148 // Boolean controls whether bounding triangulation points (and associated
149 // triangles) are included in the output. (These are introduced as an
150 // initial triangulation to begin the triangulation process. This feature
151 // is nice for debugging output.)
152 vtkSetMacro(BoundingTriangulation,int);
153 vtkGetMacro(BoundingTriangulation,int);
154 vtkBooleanMacro(BoundingTriangulation,int);
157 // Get the output of this filter.
158 vtkUnstructuredGrid *GetOutput() {return (vtkUnstructuredGrid *)this->Output;};
160 // Use different object for locating "coincident" vertices
161 void SetLocator(vtkPointLocator *locator);
162 void SetLocator(vtkPointLocator& locator) {this->SetLocator(&locator);};
163 vtkGetObjectMacro(Locator,vtkPointLocator);
166 // Create default locator. Used to create one when none is specified. The
167 // locator is used to eliminate "coincident" points.
168 void CreateDefaultLocator();
170 // Methods available to other objects for forming and manipulating
172 vtkUnstructuredGrid *InitPointInsertion(float center[3], float length,
173 int numPts, vtkPoints* &pts);
174 vtkUnstructuredGrid *InitPointInsertion(int numPtsToInsert, int numTetra,
175 vtkPoints &boundingTetraPts, float bounds[6],
177 void InsertPoint(vtkUnstructuredGrid *Mesh, vtkPoints *points,
178 int id, float x[3], vtkIdList& holeTetras);
180 unsigned long int GetMTime();
187 int BoundingTriangulation;
190 vtkPointLocator *Locator; //help locate points faster
191 int SelfCreatedLocator;
193 vtkSphereArray *Spheres; //used to keep track of circumspheres
194 int InSphere(float x[3], int tetraId);
195 void InsertSphere(vtkUnstructuredGrid *Mesh, vtkPoints *pts, int tetraId);
197 int NumberOfDuplicatePoints; //keep track of bad data
198 int NumberOfDegeneracies;
200 int FindEnclosingFaces(float x[3], int tetra, vtkUnstructuredGrid *Mesh,
201 vtkPoints *points, float tol,
202 vtkIdList &tetras, vtkIdList &faces,
203 vtkPointLocator *Locator);
205 int FindTetra(float x[3], int ptIds[4], float p[4][3],
206 int tetra, vtkUnstructuredGrid *Mesh,
207 vtkPoints *points, float tol, int depth);