COVISE Core
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros
Triangulate.h
Go to the documentation of this file.
1 /* This file is part of COVISE.
2 
3  You can use it under the terms of the GNU Lesser General Public License
4  version 2.1 or later, see lgpl-2.1.txt.
5 
6  * License: LGPL 2+ */
7 
8 #include <vector>
9 
10 static const float EPSILON = 0.0000000001f;
11 
12 typedef struct
13 {
14  float x;
15  float y;
16  int index;
17 } tr_vertex;
18 
19 typedef std::vector<tr_vertex> tr_vertexVector;
20 
21 typedef std::vector<int> tr_intVector;
22 
24 {
25 public:
26  // triangulate a contour/polygon, places results in STL vector
27  // as series of triangles.
28  static bool Process(const tr_vertexVector &contour,
30  {
31  /* allocate and initialize list of Vertices in polygon */
32 
33  int n = (int)contour.size();
34  if (n < 3)
35  return false;
36 
37  int *V = new int[n];
38 
39  /* we want a counter-clockwise polygon in V */
40 
41  if (0.0f < Area(contour))
42  for (int v = 0; v < n; v++)
43  V[v] = v;
44  else
45  for (int v = 0; v < n; v++)
46  V[v] = (n - 1) - v;
47 
48  int nv = n;
49 
50  /* remove nv-2 Vertices, creating 1 triangle every time */
51  int count = 2 * nv; /* error detection */
52 
53  for (int m = 0, v = nv - 1; nv > 2;)
54  {
55  /* if we loop, it is probably a non-simple polygon */
56  if (0 >= (count--))
57  {
58  //** Triangulate: ERROR - probable bad polygon!
59  return false;
60  }
61 
62  /* three consecutive vertices in current polygon, <u,v,w> */
63  int u = v;
64  if (nv <= u)
65  u = 0; /* previous */
66  v = u + 1;
67  if (nv <= v)
68  v = 0; /* new v */
69  int w = v + 1;
70  if (nv <= w)
71  w = 0; /* next */
72 
73  if (Snip(contour, u, v, w, nv, V))
74  {
75  int a, b, c, s, t;
76 
77  /* true names of the vertices */
78  a = V[u];
79  b = V[v];
80  c = V[w];
81 
82  /* output Triangle */
83  result.push_back(contour[a].index);
84  result.push_back(contour[b].index);
85  result.push_back(contour[c].index);
86 
87  m++;
88 
89  /* remove v from remaining polygon */
90  for (s = v, t = v + 1; t < nv; s++, t++)
91  V[s] = V[t];
92  nv--;
93 
94  /* resest error detection counter */
95  count = 2 * nv;
96  }
97  }
98 
99  delete[] V;
100 
101  return true;
102  };
103 
104  // compute area of a contour/polygon
105  static float Area(const tr_vertexVector &contour)
106  {
107 
108  int n = (int)contour.size();
109 
110  float A = 0.0f;
111 
112  for (int p = n - 1, q = 0; q < n; p = q++)
113  {
114  A += contour[p].x * contour[q].y - contour[q].x * contour[p].y;
115  }
116  return A * 0.5f;
117  };
118 
119  // decide if point Px/Py is inside triangle defined by
120  // (Ax,Ay) (Bx,By) (Cx,Cy)
121  static bool InsideTriangle(float Ax, float Ay,
122  float Bx, float By,
123  float Cx, float Cy,
124  float Px, float Py)
125  {
126  float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
127  float cCROSSap, bCROSScp, aCROSSbp;
128 
129  ax = Cx - Bx;
130  ay = Cy - By;
131  bx = Ax - Cx;
132  by = Ay - Cy;
133  cx = Bx - Ax;
134  cy = By - Ay;
135  apx = Px - Ax;
136  apy = Py - Ay;
137  bpx = Px - Bx;
138  bpy = Py - By;
139  cpx = Px - Cx;
140  cpy = Py - Cy;
141 
142  aCROSSbp = ax * bpy - ay * bpx;
143  cCROSSap = cx * apy - cy * apx;
144  bCROSScp = bx * cpy - by * cpx;
145 
146  return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
147  };
148 
149 private:
150  static bool Snip(const tr_vertexVector &contour, int u, int v, int w, int n, int *V)
151  {
152  int p;
153  float Ax, Ay, Bx, By, Cx, Cy, Px, Py;
154 
155  Ax = contour[V[u]].x;
156  Ay = contour[V[u]].y;
157 
158  Bx = contour[V[v]].x;
159  By = contour[V[v]].y;
160 
161  Cx = contour[V[w]].x;
162  Cy = contour[V[w]].y;
163 
164  if (EPSILON > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax))))
165  return false;
166 
167  for (p = 0; p < n; p++)
168  {
169  if ((p == u) || (p == v) || (p == w))
170  continue;
171  Px = contour[V[p]].x;
172  Py = contour[V[p]].y;
173  if (InsideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py))
174  return false;
175  }
176 
177  return true;
178  };
179 };
GLdouble GLdouble GLdouble GLdouble q
Definition: khronos-glext.h:6465
GLdouble n
Definition: khronos-glext.h:8447
GLboolean GLboolean GLboolean b
Definition: khronos-glext.h:6895
Definition: Triangulate.h:23
GLdouble s
Definition: khronos-glext.h:6441
Definition: Triangulate.h:12
GLuint GLuint GLsizei count
Definition: khronos-glext.h:6343
static bool Snip(const tr_vertexVector &contour, int u, int v, int w, int n, int *V)
Definition: Triangulate.h:150
float y
Definition: Triangulate.h:15
const GLdouble * v
Definition: khronos-glext.h:6442
const GLubyte * c
Definition: khronos-glext.h:9864
GLfloat GLfloat p
Definition: khronos-glext.h:9861
GLboolean GLboolean GLboolean GLboolean a
Definition: khronos-glext.h:6895
static bool InsideTriangle(float Ax, float Ay, float Bx, float By, float Cx, float Cy, float Px, float Py)
Definition: Triangulate.h:121
GLubyte GLubyte GLubyte GLubyte w
Definition: khronos-glext.h:6793
std::vector< tr_vertex > tr_vertexVector
Definition: Triangulate.h:19
const GLfloat * m
Definition: khronos-glext.h:12117
static const float EPSILON
Definition: Triangulate.h:10
GLuint index
Definition: khronos-glext.h:6722
GLuint64EXT * result
Definition: khronos-glext.h:12573
std::vector< int > tr_intVector
Definition: Triangulate.h:21
static bool Process(const tr_vertexVector &contour, tr_intVector &result)
Definition: Triangulate.h:28
int index
Definition: Triangulate.h:16
GLdouble GLdouble t
Definition: khronos-glext.h:6449
GLfloat f
Definition: khronos-glext.h:8258
static float Area(const tr_vertexVector &contour)
Definition: Triangulate.h:105
float x
Definition: Triangulate.h:14
GLbyte by
Definition: khronos-glext.h:9725