Panda3D

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