root/OpenSceneGraph/trunk/include/osgUtil/DelaunayTriangulator @ 13041

Revision 13041, 6.9 kB (checked in by robert, 2 years ago)

Ran script to remove trailing spaces and tabs

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
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 contraints 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
Note: See TracBrowser for help on using the browser.