Panda3D
 All Classes Functions Variables Enumerations
eggPolygon.cxx
1 // Filename: eggPolygon.cxx
2 // Created by: drose (16Jan99)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #include "eggPolygon.h"
16 #include "eggGroupNode.h"
17 #include "plane.h"
18 
19 #include "indent.h"
20 
21 #include <algorithm>
22 
23 TypeHandle EggPolygon::_type_handle;
24 
25 
26 ////////////////////////////////////////////////////////////////////
27 // Function: EggPolygon::cleanup
28 // Access: Published, Virtual
29 // Description: Cleans up modeling errors in whatever context this
30 // makes sense. For instance, for a polygon, this calls
31 // remove_doubled_verts(true). For a point, it calls
32 // remove_nonunique_verts(). Returns true if the
33 // primitive is valid, or false if it is degenerate.
34 ////////////////////////////////////////////////////////////////////
35 bool EggPolygon::
38 
39  // Use calculate_normal() to determine if the polygon is degenerate.
40  LNormald normal;
41  return calculate_normal(normal);
42 }
43 
44 ////////////////////////////////////////////////////////////////////
45 // Function: EggPolygon::calculate_normal
46 // Access: Published
47 // Description: Calculates the true polygon normal--the vector
48 // pointing out of the front of the polygon--based on
49 // the vertices. This does not return or change the
50 // polygon's normal as set via set_normal().
51 //
52 // The return value is true if the normal is computed
53 // correctly, or false if the polygon is degenerate and
54 // does not have at least three noncollinear vertices.
55 ////////////////////////////////////////////////////////////////////
56 bool EggPolygon::
57 calculate_normal(LNormald &result, CoordinateSystem cs) const {
58  result = LNormald::zero();
59 
60  // Project the polygon into each of the three major planes and
61  // calculate the area of each 2-d projection. This becomes the
62  // polygon normal. This works because the ratio between these
63  // different areas corresponds to the angle at which the polygon is
64  // tilted toward each plane.
65  size_t num_verts = size();
66  for (size_t i = 0; i < num_verts; i++) {
67  LVertexd p0 = get_vertex(i)->get_pos3();
68  LVertexd p1 = get_vertex((i + 1) % num_verts)->get_pos3();
69  result[0] += p0[1] * p1[2] - p0[2] * p1[1];
70  result[1] += p0[2] * p1[0] - p0[0] * p1[2];
71  result[2] += p0[0] * p1[1] - p0[1] * p1[0];
72  }
73 
74  if (!result.normalize()) {
75  // The polygon is degenerate: it has zero area in each plane.
76  return false;
77  }
78 
79  if (cs == CS_default) {
80  cs = get_default_coordinate_system();
81  }
82  if (cs == CS_zup_left || cs == CS_yup_left) {
83  // In a left-handed coordinate system, we must flip the result.
84  result = -result;
85  }
86  return true;
87 }
88 
89 ////////////////////////////////////////////////////////////////////
90 // Function: EggPolygon::is_planar
91 // Access: Published
92 // Description: Returns true if all of the polygon's vertices lie
93 // within the same plane, false otherwise.
94 ////////////////////////////////////////////////////////////////////
95 bool EggPolygon::
96 is_planar() const {
97  if (size() <= 3) {
98  // If we don't have more than three vertices, we can't be
99  // non-planar.
100  return true;
101  }
102 
103  LNormald normal;
104  if (!calculate_normal(normal)) {
105  // A degenerate polygon--all of the vertices are within one line,
106  // or all in the same point--is technically planar. Not sure if
107  // this is a useful return value or not.
108  return true;
109  }
110 
111  // There should be at least one vertex (actually, at least three)
112  // since we have already shown that the polygon is nondegenerate.
113  nassertr(!empty(), false);
114 
115  // Create a plane perpendicular to the polygon's normal, containing
116  // the first vertex.
117  const_iterator vi = begin();
118  LVecBase3d first_point = (*vi)->get_pos3();
119  LPlaned plane(normal, first_point);
120 
121  // And check that all of the remaining vertices are sufficiently
122  // close to the plane.
123  ++vi;
124  while (vi != end()) {
125  LVecBase3d this_point = (*vi)->get_pos3();
126  if (!this_point.almost_equal(first_point)) {
127  double dist = plane.dist_to_plane(this_point);
128  double tol = dist / length(this_point - first_point);
129  if (!IS_THRESHOLD_ZERO(tol, 0.0001)) {
130  // Nope, too far away--the polygon is nonplanar.
131  return false;
132  }
133  }
134  ++vi;
135  }
136 
137  // All vertices are close enough to pass.
138  return true;
139 }
140 
141 ////////////////////////////////////////////////////////////////////
142 // Function: EggPolygon::triangulate_in_place
143 // Access: Published
144 // Description: Subdivides the polygon into triangles and adds those
145 // triangles to the parent group node in place of the
146 // original polygon. Returns a pointer to the original
147 // polygon, which is likely about to be destructed.
148 //
149 // If convex_also is true, both concave and convex
150 // polygons will be subdivided into triangles;
151 // otherwise, only concave polygons will be subdivided,
152 // and convex polygons will be copied unchanged into the
153 // container.
154 ////////////////////////////////////////////////////////////////////
156 triangulate_in_place(bool convex_also) {
157  EggGroupNode *parent = get_parent();
158  nassertr(parent != (EggGroupNode *)NULL, this);
159 
160  PT(EggPolygon) save_me = this;
161  parent->remove_child(this);
162  triangulate_poly(parent, convex_also);
163 
164  return save_me;
165 }
166 
167 ////////////////////////////////////////////////////////////////////
168 // Function: EggPolygon::write
169 // Access: Published, Virtual
170 // Description: Writes the polygon to the indicated output stream in
171 // Egg format.
172 ////////////////////////////////////////////////////////////////////
173 void EggPolygon::
174 write(ostream &out, int indent_level) const {
175  write_header(out, indent_level, "<Polygon>");
176  write_body(out, indent_level+2);
177  indent(out, indent_level) << "}\n";
178 }
179 
180 ////////////////////////////////////////////////////////////////////
181 // Function: EggPolygon::decomp_concave
182 // Access: Private
183 // Description: Decomposes a concave polygon into triangles. Returns
184 // true if successful, false if the polygon is
185 // self-intersecting.
186 ////////////////////////////////////////////////////////////////////
187 bool EggPolygon::
188 decomp_concave(EggGroupNode *container, int asum, int x, int y) const {
189 #define VX(p, c) p->coord[c]
190 
191  struct DecompVtx {
192  int index;
193  LPoint3d coord;
194  struct DecompVtx *next;
195  };
196 
197  DecompVtx *p0, *p1, *p2, *t0, *vert;
198  DecompVtx *m[3];
199  double xmin, xmax, ymin, ymax;
200  int i, init, csum, chek;
201  double a[3], b[3], c[3], s[3];
202 
203  int num_verts = size();
204  nassertr(num_verts >= 3, false);
205 
206  /* Make linked list of verts */
207  vert = (DecompVtx *) alloca(sizeof(DecompVtx));
208  vert->index = 0;
209  vert->coord = get_vertex(0)->get_pos3();
210  p1 = vert;
211 
212  for (i = 1; i < num_verts; i++) {
213  p0 = (DecompVtx *) alloca(sizeof(DecompVtx));
214  p0->index = i;
215  p0->coord = get_vertex(i)->get_pos3();
216  // There shouldn't be two consecutive identical vertices. If
217  // there are, skip one.
218  if (!(p0->coord == p1->coord)) {
219  p1->next = p0;
220  p1 = p0;
221  }
222  }
223  p1->next = vert;
224 
225  p0 = vert;
226  p1 = p0->next;
227  p2 = p1->next;
228  m[0] = p0;
229  m[1] = p1;
230  m[2] = p2;
231  chek = 0;
232 
233  while (p0 != p2->next) {
234  /* Polygon is self-intersecting so punt */
235  if (chek &&
236  m[0] == p0 &&
237  m[1] == p1 &&
238  m[2] == p2) {
239 
240  return false;
241  }
242 
243  chek = 1;
244 
245  a[0] = VX(p1, y) - VX(p2, y);
246  b[0] = VX(p2, x) - VX(p1, x);
247  a[2] = VX(p0, y) - VX(p1, y);
248  b[2] = VX(p1, x) - VX(p0, x);
249 
250  csum = ((b[0] * a[2] - b[2] * a[0] >= 0.0) ? 1 : 0);
251 
252  if (csum ^ asum) {
253  /* current angle is concave */
254  p0 = p1;
255  p1 = p2;
256  p2 = p2->next;
257 
258  } else {
259  /* current angle is convex */
260  xmin = (VX(p0, x) < VX(p1, x)) ? VX(p0, x) : VX(p1, x);
261  if (xmin > VX(p2, x))
262  xmin = VX(p2, x);
263 
264  xmax = (VX(p0, x) > VX(p1, x)) ? VX(p0, x) : VX(p1, x);
265  if (xmax < VX(p2, x))
266  xmax = VX(p2, x);
267 
268  ymin = (VX(p0, y) < VX(p1, y)) ? VX(p0, y) : VX(p1, y);
269  if (ymin > VX(p2, y))
270  ymin = VX(p2, y);
271 
272  ymax = (VX(p0, y) > VX(p1, y)) ? VX(p0, y) : VX(p1, y);
273  if (ymax < VX(p2, y))
274  ymax = VX(p2, y);
275 
276  for (init = 1, t0 = p2->next; t0 != p0; t0 = t0->next) {
277  if (VX(t0, x) >= xmin && VX(t0, x) <= xmax &&
278  VX(t0, y) >= ymin && VX(t0, y) <= ymax) {
279  if (init) {
280  a[1] = VX(p2, y) - VX(p0, y);
281  b[1] = VX(p0, x) - VX(p2, x);
282  init = 0;
283  c[0] = VX(p1, x) * VX(p2, y) - VX(p2, x) * VX(p1, y);
284  c[1] = VX(p2, x) * VX(p0, y) - VX(p0, x) * VX(p2, y);
285  c[2] = VX(p0, x) * VX(p1, y) - VX(p1, x) * VX(p0, y);
286  }
287 
288  s[0] = a[0] * VX(t0, x) + b[0] * VX(t0, y) + c[0];
289  s[1] = a[1] * VX(t0, x) + b[1] * VX(t0, y) + c[1];
290  s[2] = a[2] * VX(t0, x) + b[2] * VX(t0, y) + c[2];
291 
292  if (asum) {
293  if (s[0] >= 0.0 && s[1] >= 0.0 && s[2] >= 0.0)
294  break;
295  } else {
296  if (s[0] <= 0.0 && s[1] <= 0.0 && s[2] <= 0.0)
297  break;
298  }
299  }
300  }
301 
302  if (t0 != p0) {
303  p0 = p1;
304  p1 = p2;
305  p2 = p2->next;
306  } else {
307 
308  // Here's a triangle to output.
309  PT(EggPolygon) triangle = new EggPolygon(*this);
310  triangle->clear();
311  triangle->add_vertex(get_vertex(p0->index));
312  triangle->add_vertex(get_vertex(p1->index));
313  triangle->add_vertex(get_vertex(p2->index));
314 
315  if (triangle->cleanup()) {
316  container->add_child(triangle.p());
317  }
318 
319  p0->next = p1->next;
320  p1 = p2;
321  p2 = p2->next;
322 
323  m[0] = p0;
324  m[1] = p1;
325  m[2] = p2;
326  chek = 0;
327  }
328  }
329  }
330 
331  // One more triangle to output.
332  PT(EggPolygon) triangle = new EggPolygon(*this);
333  triangle->clear();
334  triangle->add_vertex(get_vertex(p0->index));
335  triangle->add_vertex(get_vertex(p1->index));
336  triangle->add_vertex(get_vertex(p2->index));
337 
338  if (triangle->cleanup()) {
339  container->add_child(triangle.p());
340  }
341 
342  return true;
343 }
344 
345 
346 ////////////////////////////////////////////////////////////////////
347 // Function: EggPolygon::triangulate_poly
348 // Access: Private
349 // Description: Breaks a (possibly concave) higher-order polygon into
350 // a series of constituent triangles. Fills the
351 // container up with EggPolygons that represent the
352 // triangles. Returns true if successful, false on
353 // failure.
354 //
355 // If convex_also is true, both concave and convex
356 // polygons will be subdivided into triangles;
357 // otherwise, only concave polygons will be subdivided,
358 // and convex polygons will be copied unchanged into the
359 // container.
360 //
361 // It is assumed that the EggPolygon is not already a
362 // child of any other group when this function is
363 // called.
364 ////////////////////////////////////////////////////////////////////
365 bool EggPolygon::
366 triangulate_poly(EggGroupNode *container, bool convex_also) {
367  LPoint3d p0, p1, as;
368  double dx1, dy1, dx2, dy2, max;
369  int i, flag, asum, csum, index, x, y, v0, v1, v, even;
370 
371  if (!cleanup()) {
372  return false;
373  }
374 
375  // First see if the polygon is already a triangle
376  int num_verts = size();
377  if (num_verts == 3) {
378  container->add_child(this);
379 
380  return true;
381 
382  } else if (num_verts < 3) {
383  // Or if it's a degenerate polygon.
384  return false;
385  }
386 
387  // calculate signed areas
388  as[0] = 0.0;
389  as[1] = 0.0;
390  as[2] = 0.0;
391 
392  for (i = 0; i < num_verts; i++) {
393  p0 = get_vertex(i)->get_pos3();
394  p1 = get_vertex((i + 1) % num_verts)->get_pos3();
395  as[0] += p0[0] * p1[1] - p0[1] * p1[0];
396  as[1] += p0[0] * p1[2] - p0[2] * p1[0];
397  as[2] += p0[1] * p1[2] - p0[2] * p1[1];
398  }
399 
400  /* select largest signed area */
401  max = 0.0;
402  index = 0;
403  flag = 0;
404  for (i = 0; i < 3; i++) {
405  if (as[i] >= 0.0) {
406  if (as[i] > max) {
407  max = as[i];
408  index = i;
409  flag = 1;
410  }
411  } else {
412  as[i] = -as[i];
413  if (as[i] > max) {
414  max = as[i];
415  index = i;
416  flag = 0;
417  }
418  }
419  }
420 
421  /* pointer offsets */
422  switch (index) {
423  case 0:
424  x = 0;
425  y = 1;
426  break;
427 
428  case 1:
429  x = 0;
430  y = 2;
431  break;
432 
433  default: // case 2
434  x = 1;
435  y = 2;
436  break;
437  }
438 
439  /* concave check */
440  p0 = get_vertex(0)->get_pos3();
441  p1 = get_vertex(1)->get_pos3();
442  dx1 = p1[x] - p0[x];
443  dy1 = p1[y] - p0[y];
444  p0 = p1;
445  p1 = get_vertex(2)->get_pos3();
446 
447  dx2 = p1[x] - p0[x];
448  dy2 = p1[y] - p0[y];
449  asum = ((dx1 * dy2 - dx2 * dy1 >= 0.0) ? 1 : 0);
450 
451  for (i = 0; i < num_verts - 1; i++) {
452  p0 = p1;
453  p1 = get_vertex((i+3) % num_verts)->get_pos3();
454 
455  dx1 = dx2;
456  dy1 = dy2;
457  dx2 = p1[x] - p0[x];
458  dy2 = p1[y] - p0[y];
459  csum = ((dx1 * dy2 - dx2 * dy1 >= 0.0) ? 1 : 0);
460 
461  if (csum ^ asum) {
462  // It's a concave polygon. This is a little harder.
463  return decomp_concave(container, flag, x, y);
464  }
465  }
466 
467  // It's a convex polygon.
468  if (!convex_also) {
469  // Make sure that it's also coplanar. If it's not, we should
470  // triangulate it anyway.
471  if (is_planar()) {
472  container->add_child(this);
473  return true;
474  }
475  }
476 
477  v0 = 0;
478  v1 = 1;
479  v = num_verts - 1;
480 
481  even = 1;
482 
483  /*
484  * Convert to triangles only. Do not fan out from a single vertex
485  * but zigzag into triangle strip.
486  */
487  for (i = 0; i < num_verts - 2; i++) {
488  if (even) {
489  PT(EggPolygon) triangle = new EggPolygon(*this);
490  triangle->clear();
491  triangle->add_vertex(get_vertex(v0));
492  triangle->add_vertex(get_vertex(v1));
493  triangle->add_vertex(get_vertex(v));
494 
495  if (triangle->cleanup()) {
496  container->add_child(triangle.p());
497  }
498 
499  v0 = v1;
500  v1 = v;
501  v = v0 + 1;
502  } else {
503  PT(EggPolygon) triangle = new EggPolygon(*this);
504  triangle->clear();
505  triangle->add_vertex(get_vertex(v1));
506  triangle->add_vertex(get_vertex(v0));
507  triangle->add_vertex(get_vertex(v));
508 
509  if (triangle->cleanup()) {
510  container->add_child(triangle.p());
511  }
512 
513  v0 = v1;
514  v1 = v;
515  v = v0 - 1;
516  }
517 
518  even = !even;
519  }
520 
521  return true;
522 }
A base class for nodes in the hierarchy that are not leaf nodes.
Definition: eggGroupNode.h:51
void clear()
Removes all of the vertices from the primitive.
Definition: eggPrimitive.I:432
LVertexd get_pos3() const
Valid if get_num_dimensions() returns 3 or 4.
Definition: eggVertex.I:160
bool almost_equal(const LVecBase3d &other, double threshold) const
Returns true if two vectors are memberwise equal within a specified tolerance.
Definition: lvecBase3.h:2614
static const LVector3d & zero()
Returns a zero-length vector.
Definition: lvector3.h:915
virtual bool cleanup()
Cleans up modeling errors in whatever context this makes sense.
Definition: eggPolygon.cxx:36
bool is_planar() const
Returns true if all of the polygon&#39;s vertices lie within the same plane, false otherwise.
Definition: eggPolygon.cxx:96
bool normalize()
Normalizes the vector in place.
Definition: lvecBase3.h:2132
This is the base class for all three-component vectors and points.
Definition: lvecBase3.h:1455
A single polygon.
Definition: eggPolygon.h:26
This is a three-component vector distance (as opposed to a three-component point, which represents a ...
Definition: lvector3.h:746
This is a three-component point in space (as opposed to a three-component vector, which represents a ...
Definition: lpoint3.h:531
EggNode * add_child(EggNode *node)
Adds the indicated child to the group and returns it.
bool calculate_normal(LNormald &result, CoordinateSystem cs=CS_default) const
Calculates the true polygon normal–the vector pointing out of the front of the polygon–based on the v...
Definition: eggPolygon.cxx:57
void remove_doubled_verts(bool closed)
Certain kinds of primitives, particularly polygons, don&#39;t like to have the same vertex repeated conse...
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:85
EggVertex * get_vertex(int index) const
Returns a particular index based on its index number.
Definition: eggPrimitive.I:466
EggVertex * add_vertex(EggVertex *vertex)
Adds the indicated vertex to the end of the primitive&#39;s list of vertices, and returns it...