Developer Documentation
Triangulator.hh
1 /*===========================================================================*\
2 * *
3 * OpenFlipper *
4 * Copyright (c) 2001-2015, RWTH-Aachen University *
5 * Department of Computer Graphics and Multimedia *
6 * All rights reserved. *
7 * www.openflipper.org *
8 * *
9 *---------------------------------------------------------------------------*
10 * This file is part of OpenFlipper. *
11 *---------------------------------------------------------------------------*
12 * *
13 * Redistribution and use in source and binary forms, with or without *
14 * modification, are permitted provided that the following conditions *
15 * are met: *
16 * *
17 * 1. Redistributions of source code must retain the above copyright notice, *
18 * this list of conditions and the following disclaimer. *
19 * *
20 * 2. Redistributions in binary form must reproduce the above copyright *
21 * notice, this list of conditions and the following disclaimer in the *
22 * documentation and/or other materials provided with the distribution. *
23 * *
24 * 3. Neither the name of the copyright holder nor the names of its *
25 * contributors may be used to endorse or promote products derived from *
26 * this software without specific prior written permission. *
27 * *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39 * *
40 \*===========================================================================*/
41 
42 /*===========================================================================*\
43 * *
44 * $Revision: 21022 $ *
45 * $Author: moebius $ *
46 * $Date: 2015-07-17 08:23:03 +0200 (Fri, 17 Jul 2015) $ *
47 * *
48 \*===========================================================================*/
49 
50 
51 #ifndef ACG_TRIANGULATOR_HH
52 #define ACG_TRIANGULATOR_HH
53 
54 
55 
56 #include <ACG/Math/VectorT.hh>
57 #include <ACG/Config/ACGDefines.hh>
58 
59 #include <vector>
60 #include <list>
61 
62 
63 namespace ACG{
64 
65 
66 
67 class ACGDLLEXPORT Triangulator
68 {
69 public:
74  Triangulator(const std::vector<Vec3f>& _pos);
75 
78  virtual ~Triangulator();
79 
83  int numTriangles() const { return numTris_; }
84 
90  int index(int _i) const { return tris_[_i]; }
91 
96  const std::vector<int>& indices() const { return tris_; }
97 
102  bool convex() const { return convex_; }
103 
109  int numReflexVertices() const { return numReflexVertices_; }
110 
117  bool isReflexVertex(int _i) const;
118 
123  bool success() const { return !status_; }
124 
125 
126 private:
127 
128  void initVertexList();
129 
130  // ear clipping algorithm in O(n^2)
131  int earClippingN2();
132 
133  // ear clipping algorithm in O(n^3)
134  int earClippingN3();
135 
136 
137  // disable assignment operator
138  Triangulator& operator=(const Triangulator&){ return *this; }
139 
140 
141  float triangleAreaSign(const Vec2f& v0, const Vec2f& v1, const Vec2f& v2) const;
142  float distancePointToSegmentSq(const Vec2f& v0, const Vec2f& v1, const Vec2f& pt) const;
143 
144  // test if vertex v1 is reflex in triangle v0-v1-v2 (inner angle at v1 is greater than 180 deg)
145  bool isReflexVertex(const Vec2f& v0, const Vec2f& v1, const Vec2f& v2) const;
146 
147 
148 
149  bool pointInTriangle(const Vec2f& v0, const Vec2f& v1, const Vec2f& v2, const Vec2f& pt) const;
150 
151 
152  struct RingVertex
153  {
154  RingVertex() {}
155 
156  RingVertex(int i, bool r, const Vec2f& x, RingVertex* p, RingVertex* n)
157  : id(i), reflex(r), pos(x), prev(p), next(n) { }
158 
159  int id;
160  bool reflex;
161  Vec2f pos;
162 
163  RingVertex* prev;
164  RingVertex* next;
165  };
166 
167 
168  bool updateReflexVertex(RingVertex* v);
169  void addEar(RingVertex* _earTip);
170 
171 
172  const int polySize_;
173  int numRemaningVertices_;
174  int numTris_;
175  int numReflexVertices_;
176 
177  int status_;
178  bool convex_;
179 
180 
181  std::vector<Vec2f> pos_;
182 
183  std::vector<RingVertex> vertices_;
184  std::list<RingVertex*> reflexVertices_;
185 
186  std::vector<int> tris_;
187 
188 };
189 
190 
191 
192 
193 //=============================================================================
194 }
195 
196 
197 //=============================================================================
198 #endif // ACG_TRIANGULATOR_HH defined
199 //=============================================================================
const std::vector< int > & indices() const
Get local index buffer.
Definition: Triangulator.hh:96
int numTriangles() const
Get number of triangles.
Definition: Triangulator.hh:83
int index(int _i) const
Get local vertex index.
Definition: Triangulator.hh:90
Namespace providing different geometric functions concerning angles.
Definition: DBSCANT.cc:51
bool convex() const
Is the polygon convex?
bool success() const
Check if the triangulation was successful.
int numReflexVertices() const
Get number of reflex vertices.