Triangulator.hh 6.92 KB
Newer Older
Jan Möbius's avatar
Jan Möbius committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*===========================================================================*\
*                                                                           *
*                              OpenFlipper                                  *
*           Copyright (c) 2001-2015, RWTH-Aachen University                 *
*           Department of Computer Graphics and Multimedia                  *
*                          All rights reserved.                             *
*                            www.openflipper.org                            *
*                                                                           *
*---------------------------------------------------------------------------*
* This file is part of OpenFlipper.                                         *
*---------------------------------------------------------------------------*
*                                                                           *
* Redistribution and use in source and binary forms, with or without        *
* modification, are permitted provided that the following conditions        *
* are met:                                                                  *
*                                                                           *
* 1. Redistributions of source code must retain the above copyright notice, *
*    this list of conditions and the following disclaimer.                  *
*                                                                           *
* 2. Redistributions in binary form must reproduce the above copyright      *
*    notice, this list of conditions and the following disclaimer in the    *
*    documentation and/or other materials provided with the distribution.   *
*                                                                           *
* 3. Neither the name of the copyright holder nor the names of its          *
*    contributors may be used to endorse or promote products derived from   *
*    this software without specific prior written permission.               *
*                                                                           *
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS       *
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A           *
* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,  *
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,       *
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR        *
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF    *
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING      *
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS        *
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.              *
*                                                                           *
\*===========================================================================*/

/*===========================================================================*\
*                                                                           *
*   $Revision: 21022 $                                                       *
*   $Author: moebius $                                                      *
*   $Date: 2015-07-17 08:23:03 +0200 (Fri, 17 Jul 2015) $                   *
*                                                                           *
\*===========================================================================*/


#ifndef ACG_TRIANGULATOR_HH
#define ACG_TRIANGULATOR_HH



#include <ACG/Math/VectorT.hh>
#include <ACG/Config/ACGDefines.hh>

#include <vector>
#include <list>


namespace ACG{



class ACGDLLEXPORT Triangulator
{
public:
Christopher Tenter's avatar
Christopher Tenter committed
70
71
72
73
  /** \brief Execute the triangulation algorithm on a polygon
   *
   * @param _pos polygon vertex positions (ccw)
  */
Jan Möbius's avatar
Jan Möbius committed
74
75
  Triangulator(const std::vector<Vec3f>& _pos);

Christopher Tenter's avatar
Christopher Tenter committed
76
77
78
  /** \brief Destructor
  */
  virtual ~Triangulator();
Jan Möbius's avatar
Jan Möbius committed
79

Christopher Tenter's avatar
Christopher Tenter committed
80
81
82
  /** \brief Get number of triangles
   * @return number of triangles after triangulation
  */
83
  size_t numTriangles() const { return numTris_; }
Jan Möbius's avatar
Jan Möbius committed
84

Christopher Tenter's avatar
Christopher Tenter committed
85
86
87
88
89
90
91
92
93
94
95
96
  /** \brief Get local vertex index 
   *
   * @param _i index to index buffer in range [0, .., numTris*3 - 1]
   * @return vertex index in range [0, .., _pos.size()-1], where _pos is the input vector of positions as passed to the constructor
  */
  int index(int _i) const { return tris_[_i]; }

  /** \brief Get local index buffer
  *
  * @return index buffer
  */
  const std::vector<int>& indices() const { return tris_; }
Jan Möbius's avatar
Jan Möbius committed
97

Christopher Tenter's avatar
Christopher Tenter committed
98
99
100
101
  /** \brief Is the polygon convex?
  *
  * @return convex true or false
  */
Jan Möbius's avatar
Jan Möbius committed
102
  bool convex() const { return convex_; }
Christopher Tenter's avatar
Christopher Tenter committed
103
104
105
106
107
108

  /** \brief Get number of reflex vertices
  *
  * A reflex vertex is a vertex with an inner angle larger than 180 deg.
  * @return number of reflex vertices
  */
109
  size_t numReflexVertices() const { return numReflexVertices_; }
Jan Möbius's avatar
Jan Möbius committed
110

Christopher Tenter's avatar
Christopher Tenter committed
111
112
113
114
115
116
117
118
119
120
121
122
  /** \brief Check if a vertex is reflex
  *
  * A reflex vertex is a vertex with an inner angle larger than 180 deg.
  * @param _i local vertex index in range [0, .., _pos.size()-1]
  * @return reflex vertex true or false
  */
  bool isReflexVertex(int _i) const;

  /** \brief Check if the triangulation was successful
  *
  * @return success true or false
  */
Jan Möbius's avatar
Jan Möbius committed
123
  bool success() const { return ok_; }
Jan Möbius's avatar
Jan Möbius committed
124
125
126
127
128
129
130
131
132
133
134
135
136


private:

  void initVertexList();

  // ear clipping algorithm in O(n^2)
  int earClippingN2();

  // ear clipping algorithm in O(n^3)
  int earClippingN3();


137
138
  // disable implicit assignment operator
  Triangulator& operator=(const Triangulator&) = delete;
Jan Möbius's avatar
Jan Möbius committed
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171


  float triangleAreaSign(const Vec2f& v0, const Vec2f& v1, const Vec2f& v2) const;
  float distancePointToSegmentSq(const Vec2f& v0, const Vec2f& v1, const Vec2f& pt) const;

  // test if vertex v1 is reflex in triangle v0-v1-v2  (inner angle at v1 is greater than 180 deg)
  bool isReflexVertex(const Vec2f& v0, const Vec2f& v1, const Vec2f& v2) const;



  bool pointInTriangle(const Vec2f& v0, const Vec2f& v1, const Vec2f& v2, const Vec2f& pt) const;


  struct RingVertex
  {
    RingVertex() {}

    RingVertex(int i, bool r, const Vec2f& x, RingVertex* p, RingVertex* n)
      : id(i), reflex(r), pos(x), prev(p), next(n) {  }

    int id;
    bool reflex;
    Vec2f pos;

    RingVertex* prev;
    RingVertex* next;
  };


  bool updateReflexVertex(RingVertex* v);
  void addEar(RingVertex* _earTip);


Jan Möbius's avatar
Jan Möbius committed
172
173
174
175
  const size_t polySize_;
  size_t numRemaningVertices_;
  size_t numTris_;
  size_t numReflexVertices_;
Jan Möbius's avatar
Jan Möbius committed
176

Jan Möbius's avatar
Jan Möbius committed
177
  bool ok_;
Jan Möbius's avatar
Jan Möbius committed
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
  bool convex_;


  std::vector<Vec2f> pos_;

  std::vector<RingVertex> vertices_;
  std::list<RingVertex*> reflexVertices_;

  std::vector<int> tris_;

};




//=============================================================================
}


//=============================================================================
#endif // ACG_TRIANGULATOR_HH defined
Jan Möbius's avatar
Jan Möbius committed
199
//=============================================================================