33 _vertex_pool =
nullptr;
50 _flat_shaded = flat_shaded;
62 while (this_children->size() != 0) {
66 while (!this_children->empty()) {
67 PT(
EggNode) child = this_children->get_first_child();
68 this_children->remove_child(child);
70 if (child->is_of_type(EggPolygon::get_class_type())) {
73 if (_vertex_pool ==
nullptr) {
75 add_polygon(poly, EggMesherStrip::MO_user);
77 }
else if (_vertex_pool == poly->
get_pool()) {
78 add_polygon(poly, EggMesherStrip::MO_user);
82 next_children->add_child(poly);
87 output_children->add_child(child);
94 for (si = _done.begin(); si != _done.end(); ++si) {
96 if (egg_prim !=
nullptr) {
97 output_children->add_child(egg_prim);
101 this_children = next_children;
116 write(std::ostream &out)
const {
122 out << _verts.size() <<
" verts:\n";
123 Verts::const_iterator vi;
125 for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
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";
137 Strips::const_iterator si;
138 out << _tris.size() <<
" tris:\n";
139 for (si = _tris.begin(); si != _tris.end(); ++si) {
140 out << (*si) <<
"\n";
143 out << _quads.size() <<
" quads:\n";
144 for (si = _quads.begin(); si != _quads.end(); ++si) {
145 out << (*si) <<
"\n";
148 out << _strips.size() <<
" strips:\n";
149 for (si = _strips.begin(); si != _strips.end(); ++si) {
150 out << (*si) <<
"\n";
167 _vertex_pool =
nullptr;
168 _color_sheets.clear();
175 add_polygon(
const EggPolygon *egg_poly, EggMesherStrip::MesherOrigin origin) {
177 if (this_poly->size() != 3) {
182 bool convex_also = (this_poly->size() != 4);
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);
196 ci = temp_group->begin();
200 if (_vertex_pool ==
nullptr) {
201 _vertex_pool = this_poly->get_pool();
203 nassertr(_vertex_pool == this_poly->get_pool(),
false);
207 EggMesherStrip temp_strip(this_poly, _strip_index++, _vertex_pool,
209 Strips &list = choose_strip_list(temp_strip);
210 list.push_back(temp_strip);
212 strip._origin = origin;
215 int num_verts = this_poly->size();
217 int *vptrs = (
int *)alloca(num_verts *
sizeof(
int));
218 EdgePtrs **eptrs = (EdgePtrs **)alloca(num_verts *
sizeof(EdgePtrs *));
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;
225 vptrs[i] = (*n).first;
226 eptrs[i] = &(*n).second;
228 strip._verts.push_back(vptrs[i]);
232 for (i = 0; i < num_verts; i++) {
244 inner_ref._opposite = &outer_ref;
245 outer_ref._opposite = &inner_ref;
248 strip._edges.push_back(&inner_ref);
251 outer_ref._strips.push_back(&strip);
255 eptrs[i]->insert(&outer_ref);
256 eptrs[(i+1) % num_verts]->insert(&outer_ref);
268 if (egg_consider_fans && !_flat_shaded) {
273 if (egg_retesselate_coplanar) {
280 if (egg_show_quads) {
283 for (si = _quads.begin(); si != _quads.end(); ++si) {
284 if ((*si)._status == EggMesherStrip::MS_alive) {
285 (*si)._status = EggMesherStrip::MS_done;
288 for (si = _strips.begin(); si != _strips.end(); ++si) {
289 if ((*si)._status == EggMesherStrip::MS_alive) {
290 (*si)._status = EggMesherStrip::MS_done;
313 EggMesherStrip::PrimType orig_type = strip._type;
314 PT(
EggPrimitive) egg_prim = strip.make_prim(_vertex_pool);
316 if (egg_show_tstrips) {
320 LColor color1, color2;
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);
329 color1.set(0.85, 0.85, 0.85, 1.0);
330 color2.set(0.85, 0.85, 0.85, 1.0);
335 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
338 if (num_components > 0) {
340 for (
int i = 1; i < num_components; i++) {
345 egg_prim->set_color(color1);
348 int num_verts = egg_prim->size();
349 for (
int i = 0; i < num_verts; i++) {
350 egg_prim->get_vertex(i)->clear_color();
353 }
else if (egg_show_qsheets) {
360 if (strip._row_id < 0) {
362 ColorSheetMap::iterator ci = _color_sheets.find(strip._row_id);
364 if (ci == _color_sheets.end()) {
365 make_random_color(color1);
366 _color_sheets[strip._row_id] = color1;
368 color1 = (*ci).second;
373 egg_prim->set_color(color1);
374 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
377 for (
int i = 0; i < num_components; i++) {
381 int num_verts = egg_prim->size();
382 for (
int i = 0; i < num_verts; i++) {
383 egg_prim->get_vertex(i)->clear_color();
386 }
else if (egg_show_quads) {
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);
406 if (strip._origin == EggMesherStrip::MO_user) {
408 }
else if (strip._origin == EggMesherStrip::MO_firstquad) {
410 }
else if (strip._origin == EggMesherStrip::MO_fanpoly) {
414 case EggMesherStrip::PT_quad:
418 case EggMesherStrip::PT_quadstrip:
419 color1 = very_light_blue;
422 case EggMesherStrip::PT_tristrip:
423 make_random_color(color1);
425 if (color1[0] < color1[1]) {
426 PN_stdfloat t = color1[0];
427 color1[0] = color1[1];
430 color1[2] = color1[1];
433 case EggMesherStrip::PT_trifan:
434 make_random_color(color1);
436 if (color1[0] > color1[1]) {
437 PN_stdfloat t = color1[0];
438 color1[0] = color1[1];
441 color1[2] = color1[0];
450 egg_prim->set_color(color1);
451 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
454 for (
int i = 0; i < num_components; i++) {
458 int num_verts = egg_prim->size();
459 for (
int i = 0; i < num_verts; i++) {
460 egg_prim->get_vertex(i)->clear_color();
472 count_vert_edges(
const EdgePtrs &edges)
const {
474 EdgePtrs::const_iterator ei;
475 for (ei = edges.begin(); ei != edges.end(); ++ei) {
476 count += (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty());
487 switch (strip._status) {
488 case EggMesherStrip::MS_done:
491 case EggMesherStrip::MS_dead:
494 case EggMesherStrip::MS_alive:
495 switch (strip._type) {
496 case EggMesherStrip::PT_tri:
499 case EggMesherStrip::PT_quad:
507 egg_cat.fatal() <<
"Invalid strip status!\n";
524 int first_row_id = 1;
528 pre_sheeted.splice(pre_sheeted.end(), _quads);
530 while (!pre_sheeted.empty()) {
533 Strips::iterator best = pre_sheeted.begin();
538 if ((*best)._row_id >= 0 &&
539 (*best)._status == EggMesherStrip::MS_alive &&
540 !(*best)._edges.empty()) {
546 const EggMesherEdge *edge_b = (*best).find_adjacent_edge(edge_a);
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;
558 int first_row_id_b = first_row_id;
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;
568 if (edge_b !=
nullptr && avg_length_b >= avg_length_a) {
570 (*best).cut_sheet(first_row_id_b,
true, _vertex_pool);
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;
585 (*best).cut_sheet(first_row_id_a,
true, _vertex_pool);
591 Strips &list = choose_strip_list(*best);
592 list.splice(list.end(), pre_sheeted, best);
614 for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
615 EdgePtrs &edges = (*vi).second;
623 if (edges.size() > 6) {
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();
637 if (strip->_type == EggMesherStrip::PT_tri) {
639 if (!fan._edges.empty()) {
647 sort(fans.begin(), fans.end());
648 fans.erase(unique(fans.begin(), fans.end()),
651 FanMakers::iterator fi, fi2;
657 for (fi = fans.begin(); fi != fans.end(); ++fi) {
658 if (!(*fi).is_empty()) {
660 for (++fi2; fi2 != fans.end(); ++fi2) {
661 if (!(*fi2).is_empty()) {
662 joined_any = (*fi).join(*fi2);
667 }
while (joined_any);
669 for (fi = fans.begin(); fi != fans.end(); ++fi) {
670 if ((*fi).is_valid()) {
671 (*fi).build(unrolled_tris);
681 EggGroupNode::iterator ti;
682 for (ti = unrolled_tris->begin(); ti != unrolled_tris->end(); ++ti) {
683 add_polygon(DCAST(
EggPolygon, (*ti)), EggMesherStrip::MO_fanpoly);
707 typedef std::pair<EggMesherStrip *, EggMesherStrip *> Pair;
708 typedef std::pair<Pair, EggMesherEdge *> Matched;
717 for (si = _tris.begin(); si != _tris.end(); ++si) {
720 if (tri->_status == EggMesherStrip::MS_alive) {
723 if (mate->_type == EggMesherStrip::PT_tri &&
724 mate->_status == EggMesherStrip::MS_alive &&
728 soulmates.push_back(Matched(Pair(tri, mate), common_edge));
730 tri->_status = EggMesherStrip::MS_paired;
731 mate->_status = EggMesherStrip::MS_paired;
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;
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;
751 tri->_origin = EggMesherStrip::MO_firstquad;
755 Strips::iterator next;
757 while (si != _tris.end()) {
761 Strips &list = choose_strip_list(*si);
762 if (&list != &_tris) {
763 list.splice(list.end(), _tris, si);
774 mesh_list(Strips &strips) {
775 while (!strips.empty()) {
778 Strips::iterator best = strips.begin();
780 if ((*best)._status == EggMesherStrip::MS_alive) {
781 (*best).mate(_vertex_pool);
787 Strips &list = choose_strip_list(*best);
788 list.splice(list.end(), strips, best);
796 make_random_color(LColor &color) {
800 for (
int i = 0; i < 3; i++) {
801 rgb[i] = (double)rand() / (double)RAND_MAX;
806 }
while (len < .1 || len > 1.5);
808 color.set(rgb[0], rgb[1], rgb[2],
809 0.25 + 0.75 * (
double)rand() / (
double)RAND_MAX);