Panda3D

eggMesher.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 eggMesher.cxx
10 * @author drose
11 * @date 2005-03-13
12 */
13
14 #include "eggMesher.h"
15 #include "eggMesherFanMaker.h"
16 #include "eggPolygon.h"
17 #include "eggCompositePrimitive.h"
18 #include "eggTriangleStrip.h"
19 #include "eggTriangleFan.h"
20 #include "eggGroup.h"
21 #include "config_egg.h"
22 #include "eggGroupNode.h"
23 #include "dcast.h"
24 #include "thread.h"
25
26 #include <stdlib.h>
27
28 /**
29 *
30 */
31 EggMesher::
32 EggMesher() {
33 _vertex_pool = nullptr;
34 _strip_index = 0;
35 }
36
37 /**
38 * Accepts an EggGroupNode, which contains a set of EggPrimitives--typically,
39 * triangles and quads--as children. Removes these primitives and replaces
40 * them with (mostly) equivalent EggTriangleStrips and EggTriangleFans where
41 * possible.
42 *
43 * If flat_shaded is true, then odd-length triangle strips, and triangle fans
44 * of any length, are not permitted (because these can't be rotated when
45 * required to move the colored vertex of each triangle to the first or last
46 * position).
47 */
48 void EggMesher::
49 mesh(EggGroupNode *group, bool flat_shaded) {
50 _flat_shaded = flat_shaded;
51
52 // Create a temporary node to hold the children of group that aren't
53 // involved in the meshing, as well as the newly-generate triangle strips.
54 PT(EggGroupNode) output_children = new EggGroupNode;
55
56 // And another to hold the children that will be processed next time.
57 PT(EggGroupNode) next_children = new EggGroupNode;
58 PT(EggGroupNode) this_children = group;
59
60 // Only primitives that share a common vertex pool can be meshed together.
61 // Thus, pull out the primitives with the same vertex pool in groups.
62 while (this_children->size() != 0) {
63 clear();
64
65 // Add each polygon in the group to the mesh pool.
66 while (!this_children->empty()) {
67 PT(EggNode) child = this_children->get_first_child();
68 this_children->remove_child(child);
69
70 if (child->is_of_type(EggPolygon::get_class_type())) {
71 EggPolygon *poly = DCAST(EggPolygon, child);
72
73 if (_vertex_pool == nullptr) {
74 _vertex_pool = poly->get_pool();
75 add_polygon(poly, EggMesherStrip::MO_user);
76
77 } else if (_vertex_pool == poly->get_pool()) {
78 add_polygon(poly, EggMesherStrip::MO_user);
79
80 } else {
81 // A different vertex pool; save this one for the next pass.
82 next_children->add_child(poly);
83 }
84
85 } else {
86 // If it's not a polygon of any kind, just output it unchanged.
87 output_children->add_child(child);
88 }
89 }
90
91 do_mesh();
92
93 Strips::iterator si;
94 for (si = _done.begin(); si != _done.end(); ++si) {
95 PT(EggPrimitive) egg_prim = get_prim(*si);
96 if (egg_prim != nullptr) {
97 output_children->add_child(egg_prim);
98 }
99 }
100
101 this_children = next_children;
102 next_children = new EggGroupNode;
103 }
104
105 // Now copy the newly-meshed primitives back to the group.
106 group->clear();
107 group->steal_children(*output_children);
108
109 clear();
110 }
111
112 /**
113 *
114 */
115 void EggMesher::
116 write(std::ostream &out) const {
117 /*
118 out << _edges.size() << " edges:\n";
119 copy(_edges.begin(), _edges.end(), ostream_iterator<Edge>(out, "\n"));
120 */
121
122 out << _verts.size() << " verts:\n";
123 Verts::const_iterator vi;
124
125 for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
126 int v = (*vi).first;
127 const EdgePtrs &edges = (*vi).second;
128 out << v << " shares " << count_vert_edges(edges) << " edges:\n";
129 EdgePtrs::const_iterator ei;
130 for (ei = edges.begin(); ei != edges.end(); ++ei) {
131 if (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty()) {
132 out << " " << **ei << "\n";
133 }
134 }
135 }
136
137 Strips::const_iterator si;
138 out << _tris.size() << " tris:\n";
139 for (si = _tris.begin(); si != _tris.end(); ++si) {
140 out << (*si) << "\n";
141 }
142
143 out << _quads.size() << " quads:\n";
144 for (si = _quads.begin(); si != _quads.end(); ++si) {
145 out << (*si) << "\n";
146 }
147
148 out << _strips.size() << " strips:\n";
149 for (si = _strips.begin(); si != _strips.end(); ++si) {
150 out << (*si) << "\n";
151 }
152 }
153
154 /**
155 * Empties the pool of meshable primitives and resets to an initial state.
156 */
157 void EggMesher::
158 clear() {
159 _tris.clear();
160 _quads.clear();
161 _strips.clear();
162 _dead.clear();
163 _done.clear();
164 _verts.clear();
165 _edges.clear();
166 _strip_index = 0;
167 _vertex_pool = nullptr;
168 _color_sheets.clear();
169 }
170
171 /**
172 * Adds a single polygon into the pool of available primitives for meshing.
173 */
174 bool EggMesher::
175 add_polygon(const EggPolygon *egg_poly, EggMesherStrip::MesherOrigin origin) {
176 CPT(EggPolygon) this_poly = egg_poly;
177 if (this_poly->size() != 3) {
178 // If we have a higher-order or concave polygon, triangulate it
179 // automatically.
180
181 // We'll keep quads, unless they're concave.
182 bool convex_also = (this_poly->size() != 4);
183
184 PT(EggGroupNode) temp_group = new EggGroupNode;
185 bool result = this_poly->triangulate_into(temp_group, convex_also);
186 EggGroupNode::iterator ci;
187 if (temp_group->size() != 1) {
188 for (ci = temp_group->begin(); ci != temp_group->end(); ++ci) {
189 add_polygon(DCAST(EggPolygon, *ci), EggMesherStrip::MO_user);
190 }
191 return result;
192 }
193
194 // Convert just the one polygon we got out of the group. Don't recurse,
195 // since it might be the same polygon we sent in.
196 ci = temp_group->begin();
197 this_poly = DCAST(EggPolygon, *ci);
198 }
199
200 if (_vertex_pool == nullptr) {
201 _vertex_pool = this_poly->get_pool();
202 } else {
203 nassertr(_vertex_pool == this_poly->get_pool(), false);
204 }
205
206 // Define an initial strip (probably of length 1) for the prim.
207 EggMesherStrip temp_strip(this_poly, _strip_index++, _vertex_pool,
208 _flat_shaded);
209 Strips &list = choose_strip_list(temp_strip);
210 list.push_back(temp_strip);
211 EggMesherStrip &strip = list.back();
212 strip._origin = origin;
213
214 int i;
215 int num_verts = this_poly->size();
216
217 int *vptrs = (int *)alloca(num_verts * sizeof(int));
218 EdgePtrs **eptrs = (EdgePtrs **)alloca(num_verts * sizeof(EdgePtrs *));
219
220 // Get the common vertex pointers for the primitive's vertices.
221 for (i = 0; i < num_verts; i++) {
222 Verts::value_type v(this_poly->get_vertex(i)->get_index(), EdgePtrs());
223 Verts::iterator n = _verts.insert(v).first;
224
225 vptrs[i] = (*n).first;
226 eptrs[i] = &(*n).second;
227
228 strip._verts.push_back(vptrs[i]);
229 }
230
231 // Now identify the common edges.
232 for (i = 0; i < num_verts; i++) {
233 // Define an inner and outer edge. A polygon shares an edge with a
234 // neighbor only when one of its inner edges matches a neighbor's outer
235 // edge (and vice-versa).
236 EggMesherEdge inner(vptrs[i], vptrs[(i+1) % num_verts]);
237 EggMesherEdge outer(vptrs[(i+1) % num_verts], vptrs[i]);
238
239 // Add it to the list and get its common pointer.
240 EggMesherEdge &inner_ref = (EggMesherEdge &)*_edges.insert(inner).first;
241 EggMesherEdge &outer_ref = (EggMesherEdge &)*_edges.insert(outer).first;
242
243 // Tell the edges about each other.
244 inner_ref._opposite = &outer_ref;
245 outer_ref._opposite = &inner_ref;
246
247 // Associate the common edge to the strip.
248 strip._edges.push_back(&inner_ref);
249
250 // Associate the strip, as well as the original prim, to the edge.
251 outer_ref._strips.push_back(&strip);
252
253 // Associate the common edge with the vertices that share it.
254 // EggMesherEdge *edge_ptr = inner_ref.common_ptr();
255 eptrs[i]->insert(&outer_ref);
256 eptrs[(i+1) % num_verts]->insert(&outer_ref);
257 }
258
259 return true;
260 }
261
262 /**
263 * Performs the meshing process on the set of primitives that have been added
264 * via add_prim(), leaving the result in _done.
265 */
266 void EggMesher::
267 do_mesh() {
268 if (egg_consider_fans && !_flat_shaded) {
269 find_fans();
270 }
271
272 // First, we try to make all the best quads we can.
273 if (egg_retesselate_coplanar) {
274 make_quads();
275 }
276
277 // Then, we do the rest of the tris.
278 mesh_list(_tris);
279
280 if (egg_show_quads) {
281 // If we're showing quads, we shouldn't do any more meshing.
282 Strips::iterator si;
283 for (si = _quads.begin(); si != _quads.end(); ++si) {
284 if ((*si)._status == EggMesherStrip::MS_alive) {
285 (*si)._status = EggMesherStrip::MS_done;
286 }
287 }
288 for (si = _strips.begin(); si != _strips.end(); ++si) {
289 if ((*si)._status == EggMesherStrip::MS_alive) {
290 (*si)._status = EggMesherStrip::MS_done;
291 }
292 }
293 }
294
295 // Then, build quads into sheets where possible.
296 build_sheets();
297
298 // Pick up any quads that might have been left behind.
299 mesh_list(_quads);
300
301 // Finally, do the longer strips.
302 mesh_list(_strips);
303
304 Thread::consider_yield();
305 }
306
307 /**
308 * Creates an EggPrimitive that represents the result of the meshed
309 * EggMesherStrip object.
310 */
311 PT(EggPrimitive) EggMesher::
312 get_prim(EggMesherStrip &strip) {
313 EggMesherStrip::PrimType orig_type = strip._type;
314 PT(EggPrimitive) egg_prim = strip.make_prim(_vertex_pool);
315
316 if (egg_show_tstrips) {
317 // If we have egg_show_tstrips on, it means we need to color every
318 // primitive according to which, if any, tristrip it is in.
319
320 LColor color1, color2;
321
322 if (egg_prim->is_of_type(EggTriangleStrip::get_class_type()) ||
323 egg_prim->is_of_type(EggTriangleFan::get_class_type())) {
324 make_random_color(color2);
325 color1 = (color2 * 0.8); // somewhat darker.
326
327 } else {
328 // not-a-tristrip.
329 color1.set(0.85, 0.85, 0.85, 1.0);
330 color2.set(0.85, 0.85, 0.85, 1.0);
331 }
332
333 // Now color1 and color2 indicate the color for the first triangle and the
334 // rest of the primitive, respectively.
335 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
336 EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
337 int num_components = egg_comp->get_num_components();
338 if (num_components > 0) {
339 egg_comp->get_component(0)->set_color(color1);
340 for (int i = 1; i < num_components; i++) {
341 egg_comp->get_component(i)->set_color(color2);
342 }
343 }
344 } else {
345 egg_prim->set_color(color1);
346 }
347
348 int num_verts = egg_prim->size();
349 for (int i = 0; i < num_verts; i++) {
350 egg_prim->get_vertex(i)->clear_color();
351 }
352
353 } else if (egg_show_qsheets) {
354 // egg_show_qsheets means to color every primitive according to which, if
355 // any, quadsheet it is in. This is a bit easier, because the entire
356 // primitive gets the same color.
357
358 // Is this a quadsheet?
359 LColor color1;
360 if (strip._row_id < 0) {
361 // Yep! Assign a new color, if it doesn't already have one.
362 ColorSheetMap::iterator ci = _color_sheets.find(strip._row_id);
363
364 if (ci == _color_sheets.end()) {
365 make_random_color(color1);
366 _color_sheets[strip._row_id] = color1;
367 } else {
368 color1 = (*ci).second;
369 }
370 }
371
372 // Now color1 is the color we want to assign to the whole primitive.
373 egg_prim->set_color(color1);
374 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
375 EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
376 int num_components = egg_comp->get_num_components();
377 for (int i = 0; i < num_components; i++) {
378 egg_comp->get_component(i)->clear_color();
379 }
380 }
381 int num_verts = egg_prim->size();
382 for (int i = 0; i < num_verts; i++) {
383 egg_prim->get_vertex(i)->clear_color();
384 }
385
386 } else if (egg_show_quads) {
387 // egg_show_quads means to show the assembling of tris into quads and
388 // fans.
389
390 // We use the following color convention:
391
392 // white: unchanged; as supplied by user. dark blue: quads made in the
393 // initial pass. These are more certain. light blue: quads made in the
394 // second pass. These are less certain. very light blue: quadstrips.
395 // These are unlikely to appear. random shades of red: triangles and
396 // tristrips. green: fans and retesselated fan polygons.
397
398 // We need a handful of entries.
399 LColor white(0.85, 0.85, 0.85, 1.0);
400 LColor dark_blue(0.0, 0.0, 0.75, 1.0);
401 LColor light_blue(0.4, 0.4, 0.8, 1.0);
402 LColor very_light_blue(0.6, 0.6, 1.0, 1.0);
403 LColor green(0.2, 0.8, 0.2, 1.0);
404
405 LColor color1;
406 if (strip._origin == EggMesherStrip::MO_user) {
407 color1 = white;
408 } else if (strip._origin == EggMesherStrip::MO_firstquad) {
409 color1 = dark_blue;
410 } else if (strip._origin == EggMesherStrip::MO_fanpoly) {
411 color1 = green;
412 } else {
413 switch (orig_type) {
414 case EggMesherStrip::PT_quad:
415 color1 = light_blue;
416 break;
417
418 case EggMesherStrip::PT_quadstrip:
419 color1 = very_light_blue;
420 break;
421
422 case EggMesherStrip::PT_tristrip:
423 make_random_color(color1);
424 // Make it a shade of red.
425 if (color1[0] < color1[1]) {
426 PN_stdfloat t = color1[0];
427 color1[0] = color1[1];
428 color1[1] = t;
429 }
430 color1[2] = color1[1];
431 break;
432
433 case EggMesherStrip::PT_trifan:
434 make_random_color(color1);
435 // Make it a shade of green.
436 if (color1[0] > color1[1]) {
437 PN_stdfloat t = color1[0];
438 color1[0] = color1[1];
439 color1[1] = t;
440 }
441 color1[2] = color1[0];
442 break;
443
444 default:
445 color1 = white;
446 }
447 }
448
449 // Now color1 is the color we want to assign to the whole primitive.
450 egg_prim->set_color(color1);
451 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
452 EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
453 int num_components = egg_comp->get_num_components();
454 for (int i = 0; i < num_components; i++) {
455 egg_comp->get_component(i)->clear_color();
456 }
457 }
458 int num_verts = egg_prim->size();
459 for (int i = 0; i < num_verts; i++) {
460 egg_prim->get_vertex(i)->clear_color();
461 }
462 }
463
464 return egg_prim;
465 }
466
467 /**
468 * Returns the number of edges in the list that are used by at least one
469 * EggMesherStrip object.
470 */
471 int EggMesher::
472 count_vert_edges(const EdgePtrs &edges) const {
473 int count = 0;
474 EdgePtrs::const_iterator ei;
475 for (ei = edges.begin(); ei != edges.end(); ++ei) {
476 count += (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty());
477 }
478 return count;
479 }
480
481 /**
482 * Selects which of several strip lists on the EggMesher class the indicated
483 * EggMesherStrip should be added to.
484 */
485 plist<EggMesherStrip> &EggMesher::
486 choose_strip_list(const EggMesherStrip &strip) {
487 switch (strip._status) {
488 case EggMesherStrip::MS_done:
489 return _done;
490
491 case EggMesherStrip::MS_dead:
492 return _dead;
493
494 case EggMesherStrip::MS_alive:
495 switch (strip._type) {
496 case EggMesherStrip::PT_tri:
497 return _tris;
498
499 case EggMesherStrip::PT_quad:
500 return _quads;
501
502 default:
503 return _strips;
504 }
505
506 default:
507 egg_cat.fatal() << "Invalid strip status!\n";
508 abort();
509 }
510
511 return _strips; // Unreachable; this is just to make the compiler happy.
512 }
513
514 /**
515 * Attempts to locate large quadsheets in the polygon soup. A quadsheet is
516 * defined as a uniform rectangular mesh of quads joined at the corners.
517 *
518 * Sheets like this are commonly output by modeling packages, especially
519 * uniform tesselators, and they are trivially converted into a row of
520 * triangle strips.
521 */
522 void EggMesher::
523 build_sheets() {
524 int first_row_id = 1;
525
526 // First, move all the quads to our own internal list.
527 Strips pre_sheeted;
528 pre_sheeted.splice(pre_sheeted.end(), _quads);
529
530 while (!pre_sheeted.empty()) {
531 // Pick the first quad on the list.
532
533 Strips::iterator best = pre_sheeted.begin();
534
535 // If the row_id is negative, we've already built a sheet out of this
536 // quad. Leave it alone. We also need to leave it be if it has no
537 // available edges.
538 if ((*best)._row_id >= 0 &&
539 (*best)._status == EggMesherStrip::MS_alive &&
540 !(*best)._edges.empty()) {
541 // There are two possible sheets we could make from this quad, in two
542 // different orientations. Measure them both and figure out which one
543 // is best.
544
545 const EggMesherEdge *edge_a = (*best)._edges.front();
546 const EggMesherEdge *edge_b = (*best).find_adjacent_edge(edge_a);
547
548 int num_prims_a = 0;
549 int num_rows_a = 0;
550 int first_row_id_a = first_row_id;
551 (*best).measure_sheet(edge_a, true, num_prims_a, num_rows_a,
552 first_row_id_a, 0, 0);
553 first_row_id += num_rows_a;
554 double avg_length_a = (double)num_prims_a / (double)num_rows_a;
555
556 int num_prims_b = 0;
557 int num_rows_b = 0;
558 int first_row_id_b = first_row_id;
559 double avg_length_b;
560 if (edge_b != nullptr) {
561 (*best).measure_sheet(edge_b, true, num_prims_b, num_rows_b,
562 first_row_id_b, 0, 0);
563 first_row_id += num_rows_b;
564 avg_length_b = (double)num_prims_b / (double)num_rows_b;
565 }
566
567 // Which sheet is better?
568 if (edge_b != nullptr && avg_length_b >= avg_length_a) {
569 // Sheet b. That's easy.
570 (*best).cut_sheet(first_row_id_b, true, _vertex_pool);
571
572 } else {
573 // Nope, sheet a is better. This is a bit of a nuisance because we've
574 // unfortunately wiped out the information we stored when we measured
575 // sheet a. We'll have to do it again.
576
577 num_prims_a = 0;
578 num_rows_a = 0;
579 first_row_id_a = first_row_id;
580 (*best).measure_sheet(edge_a, true, num_prims_a, num_rows_a,
581 first_row_id_a, 0, 0);
582 first_row_id += num_rows_a;
583
584 // Now we can cut it.
585 (*best).cut_sheet(first_row_id_a, true, _vertex_pool);
586 }
587 }
588
589 // Now put it somewhere. We'll never see this quad again in
590 // build_sheets().
591 Strips &list = choose_strip_list(*best);
592 list.splice(list.end(), pre_sheeted, best);
593 }
594 }
595
596 /**
597 * Looks for cases of multiple polygons all sharing a common vertex, and
598 * replaces these with a single fan.
599 *
600 * This step is performed before detecting triangle strips. We have to be
601 * careful: if we are too aggressive in detecting fans, we may ruin the
602 * ability to build good triangle strips, and we may thereby end up with a
603 * less-than-optimal solution.
604 */
605 void EggMesher::
606 find_fans() {
607 PT(EggGroupNode) unrolled_tris = new EggGroup;
608
609 // Consider all vertices. Any vertex with over a certain number of edges
610 // connected to it is eligible to become a fan.
611
612 Verts::iterator vi;
613
614 for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
615 EdgePtrs &edges = (*vi).second;
616
617 // 14 is the magic number of edges. 12 edges or fewer are likely to be
618 // found on nearly every vertex in a quadsheet (six edges times two, one
619 // each way). We don't want to waste time fanning out each vertex of a
620 // quadsheet, and we don't want to break up the quadsheets anyway. We
621 // bump this up to 14 because some quadsheets are defined with triangles
622 // flipped here and there.
623 if (edges.size() > 6) {
624 int v = (*vi).first;
625
626 // Build up a list of far fan edges.
627 typedef pvector<EggMesherFanMaker> FanMakers;
628 FanMakers fans;
629
630 EdgePtrs::iterator ei;
631 EggMesherEdge::Strips::iterator si;
632 for (ei = edges.begin(); ei != edges.end(); ++ei) {
633 for (si = (*ei)->_strips.begin();
634 si != (*ei)->_strips.end();
635 ++si) {
636 EggMesherStrip *strip = *si;
637 if (strip->_type == EggMesherStrip::PT_tri) {
638 EggMesherFanMaker fan(v, strip, this);
639 if (!fan._edges.empty()) {
640 fans.push_back(fan);
641 }
642 }
643 }
644 }
645
646 // Sort the fans list by edge pointers, and remove duplicates.
647 sort(fans.begin(), fans.end());
648 fans.erase(unique(fans.begin(), fans.end()),
649 fans.end());
650
651 FanMakers::iterator fi, fi2;
652
653 // Now pull out connected edges.
654 bool joined_any;
655 do {
656 joined_any = false;
657 for (fi = fans.begin(); fi != fans.end(); ++fi) {
658 if (!(*fi).is_empty()) {
659 fi2 = fi;
660 for (++fi2; fi2 != fans.end(); ++fi2) {
661 if (!(*fi2).is_empty()) {
662 joined_any = (*fi).join(*fi2);
663 }
664 }
665 }
666 }
667 } while (joined_any);
668
669 for (fi = fans.begin(); fi != fans.end(); ++fi) {
670 if ((*fi).is_valid()) {
671 (*fi).build(unrolled_tris);
672 }
673 }
674 }
675 }
676
677 // Finally, add back in the triangles we might have produced by unrolling
678 // some of the fans. We can't add these back in safely until we're done
679 // traversing all the vertices and primitives we had in the first place
680 // (since adding them will affect the edge lists).
681 EggGroupNode::iterator ti;
682 for (ti = unrolled_tris->begin(); ti != unrolled_tris->end(); ++ti) {
683 add_polygon(DCAST(EggPolygon, (*ti)), EggMesherStrip::MO_fanpoly);
684 }
685 }
686
687 /**
688 * Attempts to join up each single tri to its neighbor, to reconstruct a
689 * pattern of quads, suitable for making into quadsheets or at least
690 * quadstrips.
691 *
692 * Quads have some nice properties that make them easy to manipulate when
693 * meshing. We will ultimately convert the quadsheets and quadstrips into
694 * tristrips, but it's easier to work with them first while they're quads.
695 */
696 void EggMesher::
697 make_quads() {
698 // Ideally, we want to match tris across their hypotenuse to make a pattern
699 // of quads. (This assumes that we are working with a triangulated mesh
700 // pattern, of course. If we have some other pattern of tris, all bets are
701 // off and it doesn't really matter anyway.)
702
703 // First, we'll find all the tris that have no doubt about their ideal mate,
704 // and pair them up right away. The others we'll get to later. This way,
705 // the uncertain matches won't pollute the quad alignment for everyone else.
706
707 typedef std::pair<EggMesherStrip *, EggMesherStrip *> Pair;
708 typedef std::pair<Pair, EggMesherEdge *> Matched;
709 typedef pvector<Matched> SoulMates;
710
711 SoulMates soulmates;
712
713 EggMesherStrip *tri, *mate, *mate2;
714 EggMesherEdge *common_edge, *common_edge2;
715
716 Strips::iterator si;
717 for (si = _tris.begin(); si != _tris.end(); ++si) {
718 tri = &(*si);
719
720 if (tri->_status == EggMesherStrip::MS_alive) {
721 if (tri->find_ideal_mate(mate, common_edge, _vertex_pool)) {
722 // Does our chosen mate want us too?
723 if (mate->_type == EggMesherStrip::PT_tri &&
724 mate->_status == EggMesherStrip::MS_alive &&
725 mate->find_ideal_mate(mate2, common_edge2, _vertex_pool) &&
726 mate2 == tri) {
727 // Hooray!
728 soulmates.push_back(Matched(Pair(tri, mate), common_edge));
729 // We'll temporarily mark the two tris as paired.
730 tri->_status = EggMesherStrip::MS_paired;
731 mate->_status = EggMesherStrip::MS_paired;
732 }
733 }
734 }
735 }
736
737 // Now that we've found all the tris that are sure about each other, mate
738 // them.
739 SoulMates::iterator mi;
740 for (mi = soulmates.begin(); mi != soulmates.end(); ++mi) {
741 tri = (*mi).first.first;
742 mate = (*mi).first.second;
743 common_edge = (*mi).second;
744
745 nassertv(tri->_status == EggMesherStrip::MS_paired);
746 nassertv(mate->_status == EggMesherStrip::MS_paired);
747 tri->_status = EggMesherStrip::MS_alive;
748 mate->_status = EggMesherStrip::MS_alive;
749
750 EggMesherStrip::mate_pieces(common_edge, *tri, *mate, _vertex_pool);
751 tri->_origin = EggMesherStrip::MO_firstquad;
752 }
753
754 // Now move all the strips off the tri list that no longer belong.
755 Strips::iterator next;
756 si = _tris.begin();
757 while (si != _tris.end()) {
758 next = si;
759 ++next;
760
761 Strips &list = choose_strip_list(*si);
762 if (&list != &_tris) {
763 list.splice(list.end(), _tris, si);
764 }
765
766 si = next;
767 }
768 }
769
770 /**
771 * Processes all of the strips on the indicated list.
772 */
773 void EggMesher::
774 mesh_list(Strips &strips) {
775 while (!strips.empty()) {
776 // Pick the first strip on the list.
777
778 Strips::iterator best = strips.begin();
779
780 if ((*best)._status == EggMesherStrip::MS_alive) {
781 (*best).mate(_vertex_pool);
782 }
783
784 // Put the strip back on the end of whichever list it wants. This might
785 // be the same list, if the strip is still alive, or it might be _done or
786 // _dead.
787 Strips &list = choose_strip_list(*best);
788 list.splice(list.end(), strips, best);
789 }
790 }
791
792 /**
793 * Chooses a reasonable random color.
794 */
795 void EggMesher::
796 make_random_color(LColor &color) {
797 LVector3 rgb;
798 PN_stdfloat len;
799 do {
800 for (int i = 0; i < 3; i++) {
801 rgb[i] = (double)rand() / (double)RAND_MAX;
802 }
803 len = length(rgb);
804
805 // Repeat until we have a color that's not too dark or too light.
806 } while (len < .1 || len > 1.5);
807
808 color.set(rgb[0], rgb[1], rgb[2],
809 0.25 + 0.75 * (double)rand() / (double)RAND_MAX);
810 }
EggCompositePrimitive
The base class for primitives such as triangle strips and triangle fans, which include several compon...
Definition: eggCompositePrimitive.h:26
EggCompositePrimitive::get_num_components
get_num_components
Returns the number of individual component triangles within the composite.
Definition: eggCompositePrimitive.h:38
EggCompositePrimitive::get_component
get_component
Returns the attributes for the nth component triangle.
Definition: eggCompositePrimitive.h:38
EggGroupNode
A base class for nodes in the hierarchy that are not leaf nodes.
Definition: eggGroupNode.h:46
EggGroupNode::steal_children
void steal_children(EggGroupNode &other)
Moves all the children from the other node to this one.
Definition: eggGroupNode.cxx:278
EggGroup
The main glue of the egg hierarchy, this corresponds to the <Group>, <Instance>, and <Joint> type nod...
Definition: eggGroup.h:34
EggMesherEdge
Represents one edge of a triangle, as used by the EggMesher to discover connected triangles.
Definition: eggMesherEdge.h:29
EggMesherFanMaker
This class is used by EggMesher::find_fans() to attempt to make an EggTriangleFan out of the polygons...
Definition: eggMesherFanMaker.h:34
EggMesherStrip
Represents a triangle strip or quad strip in progress, as assembled by the mesher.
Definition: eggMesherStrip.h:30
EggMesherStrip::find_ideal_mate
bool find_ideal_mate(EggMesherStrip *&mate, EggMesherEdge *&common_edge, const EggVertexPool *vertex_pool)
Searches our neighbors for the most suitable mate.
Definition: eggMesherStrip.cxx:427
EggMesherStrip::mate_pieces
static bool mate_pieces(EggMesherEdge *common_edge, EggMesherStrip &front, EggMesherStrip &back, const EggVertexPool *vertex_pool)
Connects two pieces of arbitrary type, if possible.
Definition: eggMesherStrip.cxx:459
EggMesher::mesh
void mesh(EggGroupNode *group, bool flat_shaded)
Accepts an EggGroupNode, which contains a set of EggPrimitives–typically, triangles and quads–as chil...
Definition: eggMesher.cxx:49
EggNode
A base class for things that may be directly added into the egg hierarchy.
Definition: eggNode.h:36
EggPolygon
A single polygon.
Definition: eggPolygon.h:24
EggPrimitive
A base class for any of a number of kinds of geometry primitives: polygons, point lights,...
Definition: eggPrimitive.h:49
EggPrimitive::get_pool
get_pool
Returns the vertex pool associated with the vertices of the primitive, or NULL if the primitive has n...
Definition: eggPrimitive.h:192
Thread::consider_yield
static void consider_yield()
Possibly suspends the current thread for the rest of the current epoch, if it has run for enough this...
Definition: thread.I:212
plist< EggMesherStrip >
pvector
This is our own Panda specialization on the default STL vector.
Definition: pvector.h:42
config_egg.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
dcast.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
eggCompositePrimitive.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
eggGroupNode.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
eggGroup.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
eggMesherFanMaker.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PT
PT(EggPrimitive) EggMesher
Creates an EggPrimitive that represents the result of the meshed EggMesherStrip object.
Definition: eggMesher.cxx:311
eggMesher.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
eggPolygon.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
eggTriangleFan.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
eggTriangleStrip.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
thread.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.