openscenegraph
DelaunayTriangulator
Go to the documentation of this file.
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 *
3 * This library is open source and may be redistributed and/or modified under
4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
5 * (at your option) any later version. The full license is in LICENSE file
6 * included with this distribution, and on the openscenegraph.org website.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * OpenSceneGraph Public License for more details.
12*/
13
14#ifndef OSGUTIL_DELAUNAYTRIANGULATOR_
15#define OSGUTIL_DELAUNAYTRIANGULATOR_
16
17#include <list>
18
19#include <osg/ref_ptr>
20#include <osg/Array>
21#include <osg/Referenced>
22#include <osg/CopyOp>
23#include <osg/PrimitiveSet>
24#include <osg/Geometry>
25
26#include <osgUtil/Export>
27
28namespace osgUtil
29{
30
31/** DelaunayTriangulator: Utility class that triangulates an irregular network of sample points.
32 Just create a DelaunayTriangulator, assign it the sample point array and call
33 its triangulate() method to start the triangulation. Then you can obtain the
34 generated primitive by calling the getTriangles() method.
35
36 Add DelaunayConstraints (or derived class) to control the triangulation edges.
37*/
38class OSGUTIL_EXPORT DelaunayConstraint: public osg::Geometry {
39 // controls the edges in a Delaunay triangulation.
40 // constraints can be linear (with width), areal (contains an area)
41 // uses: to replace part of a terrain with an alternative textured model (roads, lakes).
42 // the primitive sets in this are either LINE_LOOP or LINE_STRIP
43public:
44 DelaunayConstraint() { }
45
46 /** Each primitiveset is a list of vertices which may be closed by joining up to its start
47 * to make a loop. Constraints should be simple lines, not crossing themselves.
48 * Constraints which cross other constraints can cause difficulties - see the example
49 * for methods of dealing with them. */
50
51 /** collect up indices of triangle from delaunay triangles.
52 * The delaunay triangles inside the DelaunayConstraint area can be used to fill
53 * the area or generate geometry that terrain follows the area in some way.
54 * These triangles can form a canopy or a field. */
55 void addtriangle(int i1, int i2, int i3);
56
57 /** Get the filling primitive. One:
58 * triangulate must have bneen called and
59 * two: triangle list is filled when
60 * DelaunayTriangulator::removeInternalTriangles is called.
61 * These return the triangles removed from the delaunay triangulation by
62 * DelaunayTriangulator::removeInternalTriangles. */
63 inline const osg::DrawElementsUInt *getTriangles() const { return prim_tris_.get(); }
64
65 inline osg::DrawElementsUInt *getTriangles() { return prim_tris_.get(); }
66
67 /** Call BEFORE makeDrawable to reorder points to make optimised set
68 */
69 osg::Vec3Array *getPoints(const osg::Vec3Array *points);
70
71 /** converts simple list of triangles into a drawarray.
72 */
73 osg::DrawElementsUInt *makeDrawable();
74
75 /** Add vertices and constraint loops from dco
76 * Can be used to generate extra vertices where dco crosses 'this' using
77 * osgUtil::Tessellator to insert overlap vertices.
78 */
79 void merge(DelaunayConstraint *dco);
80
81 /** remove from line the vertices that are inside dco
82 */
83 void removeVerticesInside(const DelaunayConstraint *dco);
84
85 /** return winding number as a float of loop around testpoint; may use multiple loops
86 * does not reject points on the edge or very very close to the edge */
87 float windingNumber(const osg::Vec3 &testpoint) const ;
88
89 /** true if testpoint is internal (or external) to constraint. */
90 virtual bool contains(const osg::Vec3 &testpoint) const;
91 virtual bool outside(const osg::Vec3 &testpoint) const;
92
93 /** Tessellate the constraint loops so that the crossing points are interpolated
94 * and added to the constraints for the triangulation. */
95 void handleOverlaps(void);
96
97protected:
98 virtual ~DelaunayConstraint();
99
100 typedef std::vector< int* > trilist; // array of indices in points array defining triangles
101
102 trilist _interiorTris; // list of triangles that fits the area.
103
104 osg::ref_ptr<osg::DrawElementsUInt> prim_tris_; // returns a PrimitiveSet to draw the interior of this DC
105};
106
107
108class OSGUTIL_EXPORT DelaunayTriangulator: public osg::Referenced {
109public:
110
111 DelaunayTriangulator();
112 explicit DelaunayTriangulator(osg::Vec3Array *points, osg::Vec3Array *normals = 0);
113 DelaunayTriangulator(const DelaunayTriangulator &copy, const osg::CopyOp &copyop = osg::CopyOp::SHALLOW_COPY);
114
115 typedef std::vector< osg::ref_ptr<DelaunayConstraint> > linelist;
116
117 /** Set the input point array. */
118 inline void setInputPointArray(osg::Vec3Array* points) { points_ = points; }
119
120 /** Get the const input point array. */
121 inline const osg::Vec3Array* getInputPointArray() const { return points_.get(); }
122
123 /** Get the input point array. */
124 inline osg::Vec3Array* getInputPointArray() { return points_.get(); }
125
126
127 /** Set the output normal array (optional). */
128 inline void setOutputNormalArray(osg::Vec3Array* normals) { normals_ = normals; }
129
130 /** Get the const output normal array (optional). */
131 inline const osg::Vec3Array *getOutputNormalArray() const { return normals_.get(); }
132
133 /** Get the output normal array (optional). */
134 inline osg::Vec3Array *getOutputNormalArray() { return normals_.get(); }
135
136
137 /** Add an input constraint loop.
138 ** the edges of the loop will constrain the triangulation.
139 ** if remove!=0, the internal triangles of the constraint will be removed;
140 ** the user may the replace the constraint line with an equivalent geometry.
141 ** GWM July 2005 */
142 void addInputConstraint(DelaunayConstraint *dc) { constraint_lines.push_back(dc); }
143
144
145 /** Start triangulation. */
146 bool triangulate();
147
148 /** Get the generated primitive (call triangulate() first). */
149 inline const osg::DrawElementsUInt *getTriangles() const { return prim_tris_.get(); }
150
151 /** Get the generated primitive (call triangulate() first). */
152 inline osg::DrawElementsUInt *getTriangles() { return prim_tris_.get(); }
153
154 /** remove the triangles internal to the constraint loops.
155 * (Line strips cannot remove any internal triangles). */
156 void removeInternalTriangles(DelaunayConstraint *constraint);
157
158
159protected:
160 virtual ~DelaunayTriangulator();
161 DelaunayTriangulator &operator=(const DelaunayTriangulator &) { return *this; }
162 int getindex(const osg::Vec3 &pt,const osg::Vec3Array *points);
163
164private:
165 osg::ref_ptr<osg::Vec3Array> points_;
166 osg::ref_ptr<osg::Vec3Array> normals_;
167 osg::ref_ptr<osg::DrawElementsUInt> prim_tris_;
168
169 // GWM these lines provide required edges in the triangulated shape.
170 linelist constraint_lines;
171
172 void _uniqueifyPoints();
173};
174
175// INLINE METHODS
176
177
178
179}
180
181#endif
182