51 #include "Triangulator.hh"
62 : polySize_(_pos.size()), numRemaningVertices_(_pos.size()), numTris_(0),
63 numReflexVertices_(0),
64 status_(-1), convex_(false)
78 numRemaningVertices_ = 0;
90 Vec3f n(0.0f, 0.0f, 0.0f);
92 for (
int i = 0; i < polySize_; ++i)
94 int next = (i + 1) % polySize_;
96 Vec3f a = _pos[i] - _pos[next];
97 Vec3f b = _pos[i] + _pos[next];
105 pos_.resize(polySize_);
107 Vec3f axis[3] = {
Vec3f(1.0f, 0.0f, 0.0f),
Vec3f(0.0f, 1.0f, 0.0f), n };
113 while (std::abs(axis[0] | axis[2]) > 0.95f || (axis[0].sqrnorm() < 0.001f))
115 for (
int i = 0; i < 3; ++i)
116 axis[0][i] =
float(rand()) / float(RAND_MAX) * 2.0f - 1.0f;
122 axis[0] = axis[0] - axis[2] * (axis[0] | axis[2]);
124 axis[1] = axis[2] % axis[0];
127 for (
int i = 0; i < polySize_; ++i)
130 pos_[i][0] = axis[0] | _pos[i];
131 pos_[i][1] = axis[1] | _pos[i];
136 int reflexVertexID = 0;
138 for (
int i = 0; i < polySize_; ++i)
141 if (
isReflexVertex(pos_[i], pos_[(i + 1) % polySize_], pos_[(i + 2) % polySize_]))
143 ++numReflexVertices_;
144 reflexVertexID = (i + 1) % polySize_;
148 convex_ = !numReflexVertices_;
151 if (numReflexVertices_ <= 1)
154 numTris_ = polySize_ - 2;
155 tris_.resize(numTris_ * 3);
156 numRemaningVertices_ = 0;
159 for (
int i = 0; i < numTris_; ++i)
161 tris_[i * 3] = reflexVertexID;
162 tris_[i * 3 + 1] = (reflexVertexID + i + 1) % polySize_;
163 tris_[i * 3 + 2] = (reflexVertexID + i + 2) % polySize_;
194 return u[0] * v[1] - u[1] * v[0] < 0.0f;
199 int p = (i + polySize_ - 1) % polySize_;
200 int n = (i + 1) % polySize_;
205 float Triangulator::triangleAreaSign(
const Vec2f& v0,
const Vec2f& v1,
const Vec2f& v2)
const
208 return (v0[0] - v2[0]) * (v1[1] - v2[1]) - (v1[0] - v2[0]) * (v0[1] - v2[1]);
211 float Triangulator::distancePointToSegmentSq(
const Vec2f& v0,
const Vec2f& v1,
const Vec2f& pt)
const
213 Vec2f segment = v1 - v0;
215 float dp = vec | segment;
218 return vec.sqrnorm();
220 float segSq = segment.sqrnorm();
224 return vec.sqrnorm() - dp * dp * segSq;
227 return vec.sqrnorm();
230 bool Triangulator::pointInTriangle(
const Vec2f& v0,
const Vec2f& v1,
const Vec2f& v2,
const Vec2f& pt)
const
239 return triangleAreaSign(pt, v0, v1) >= 0.0f &&
240 triangleAreaSign(pt, v1, v2) >= 0.0f &&
241 triangleAreaSign(pt, v2, v0) >= 0.0f;
281 void Triangulator::initVertexList()
283 vertices_.resize(polySize_);
284 reflexVertices_.clear();
285 for (
int i = 0; i < polySize_; ++i)
287 int p = (i + polySize_ - 1) % polySize_;
288 int n = (i + 1) % polySize_;
290 vertices_[i] = RingVertex(i,
isReflexVertex(pos_[p], pos_[i], pos_[n]), pos_[i], &vertices_[p], &vertices_[n]);
292 if (vertices_[i].reflex)
293 reflexVertices_.push_back(&vertices_[i]);
299 int Triangulator::earClippingN3()
309 tris_.resize((polySize_ - 2) * 3);
311 int numIterations = 0;
312 RingVertex* firstVertex = &vertices_[0];
314 while (numTris_ < polySize_ - 2)
317 bool hasEars =
false;
319 RingVertex* curVertex = firstVertex;
322 curVertex->reflex =
isReflexVertex(curVertex->prev->pos, curVertex->pos, curVertex->next->pos);
324 if (!curVertex->reflex)
330 for (RingVertex* r = curVertex->next->next; r != curVertex->prev; r = r->next)
332 if (pointInTriangle(curVertex->prev->pos, curVertex->pos, curVertex->next->pos, r->pos))
344 tris_[numTris_ * 3] = curVertex->prev->id;
345 tris_[numTris_ * 3 + 1] = curVertex->id;
346 tris_[numTris_ * 3 + 2] = curVertex->next->id;
350 curVertex->prev->next = curVertex->next;
351 curVertex->next->prev = curVertex->prev;
357 curVertex = curVertex->next;
359 }
while (curVertex != firstVertex);
361 firstVertex = firstVertex->next;
364 if (!hasEars && (numTris_ + 2 < polySize_))
366 for (RingVertex* iteratorVertex = firstVertex->next; iteratorVertex != firstVertex->prev; iteratorVertex = iteratorVertex->next)
368 tris_[numTris_ * 3] = firstVertex->id;
369 tris_[numTris_ * 3 + 1] = iteratorVertex->id;
370 tris_[numTris_ * 3 + 2] = iteratorVertex->next->id;
374 assert(numTris_ == polySize_ - 2);
383 int Triangulator::earClippingN2()
396 numRemaningVertices_ = polySize_;
397 int numIterations = 0;
399 tris_.resize((polySize_ - 2) * 3);
401 RingVertex* curVertex = &vertices_[0];
402 while (numRemaningVertices_ > 3)
407 if (!curVertex->reflex)
411 for (std::list<RingVertex*>::iterator it = reflexVertices_.begin(); isEar && it != reflexVertices_.end(); ++it)
414 if (*it == curVertex->prev || *it == curVertex->next)
418 if (pointInTriangle(curVertex->prev->pos, curVertex->pos, curVertex->next->pos, (*it)->pos))
434 if (numTries > numRemaningVertices_)
445 curVertex = curVertex->next;
451 if (numRemaningVertices_ == 3)
453 tris_[numTris_ * 3 + 0] = curVertex->prev->id;
454 tris_[numTris_ * 3 + 1] = curVertex->id;
455 tris_[numTris_ * 3 + 2] = curVertex->next->id;
463 bool Triangulator::updateReflexVertex(RingVertex* v)
472 reflexVertices_.remove(v);
478 void Triangulator::addEar(RingVertex* _earTip)
481 tris_[numTris_ * 3 + 0] = _earTip->prev->id;
482 tris_[numTris_ * 3 + 1] = _earTip->id;
483 tris_[numTris_ * 3 + 2] = _earTip->next->id;
486 _earTip->prev->next = _earTip->next;
487 _earTip->next->prev = _earTip->prev;
490 updateReflexVertex(_earTip->prev);
491 updateReflexVertex(_earTip->next);
493 --numRemaningVertices_;
Namespace providing different geometric functions concerning angles.
virtual ~Triangulator()
Destructor.
VectorT< float, 3 > Vec3f
bool isReflexVertex(int _i) const
Check if a vertex is reflex.
Triangulator(const std::vector< Vec3f > &_pos)
Execute the triangulation algorithm on a polygon.