15 #include "eggMesher.h"
16 #include "eggMesherFanMaker.h"
17 #include "eggPolygon.h"
18 #include "eggCompositePrimitive.h"
19 #include "eggTriangleStrip.h"
20 #include "eggTriangleFan.h"
22 #include "config_egg.h"
23 #include "eggGroupNode.h"
57 _flat_shaded = flat_shaded;
72 while (this_children->size() != 0) {
76 while (!this_children->empty()) {
77 PT(
EggNode) child = this_children->get_first_child();
78 this_children->remove_child(child);
80 if (child->is_of_type(EggPolygon::get_class_type())) {
85 add_polygon(poly, EggMesherStrip::MO_user);
87 }
else if (_vertex_pool == poly->
get_pool()) {
88 add_polygon(poly, EggMesherStrip::MO_user);
92 next_children->add_child(poly);
98 output_children->add_child(child);
105 for (si = _done.begin(); si != _done.end(); ++si) {
108 output_children->add_child(egg_prim);
112 this_children = next_children;
129 write(ostream &out)
const {
135 out << _verts.size() <<
" verts:\n";
136 Verts::const_iterator vi;
138 for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
140 const EdgePtrs &edges = (*vi).second;
141 out << v <<
" shares " << count_vert_edges(edges) <<
" edges:\n";
142 EdgePtrs::const_iterator ei;
143 for (ei = edges.begin(); ei != edges.end(); ++ei) {
144 if (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty()) {
145 out <<
" " << **ei <<
"\n";
150 Strips::const_iterator si;
151 out << _tris.size() <<
" tris:\n";
152 for (si = _tris.begin(); si != _tris.end(); ++si) {
153 out << (*si) <<
"\n";
156 out << _quads.size() <<
" quads:\n";
157 for (si = _quads.begin(); si != _quads.end(); ++si) {
158 out << (*si) <<
"\n";
161 out << _strips.size() <<
" strips:\n";
162 for (si = _strips.begin(); si != _strips.end(); ++si) {
163 out << (*si) <<
"\n";
184 _color_sheets.clear();
194 add_polygon(
const EggPolygon *egg_poly, EggMesherStrip::MesherOrigin origin) {
196 if (this_poly->size() != 3) {
201 bool convex_also = (this_poly->size() != 4);
204 bool result = this_poly->triangulate_into(temp_group, convex_also);
205 EggGroupNode::iterator ci;
206 if (temp_group->size() != 1) {
207 for (ci = temp_group->begin(); ci != temp_group->end(); ++ci) {
208 add_polygon(DCAST(
EggPolygon, *ci), EggMesherStrip::MO_user);
215 ci = temp_group->begin();
219 if (_vertex_pool == NULL) {
220 _vertex_pool = this_poly->get_pool();
222 nassertr(_vertex_pool == this_poly->get_pool(),
false);
226 EggMesherStrip temp_strip(this_poly, _strip_index++, _vertex_pool,
228 Strips &list = choose_strip_list(temp_strip);
229 list.push_back(temp_strip);
231 strip._origin = origin;
234 int num_verts = this_poly->size();
236 int *vptrs = (
int *)alloca(num_verts *
sizeof(
int));
237 EdgePtrs **eptrs = (EdgePtrs **)alloca(num_verts *
sizeof(EdgePtrs *));
240 for (i = 0; i < num_verts; i++) {
241 Verts::value_type v(this_poly->get_vertex(i)->get_index(), EdgePtrs());
242 Verts::iterator n = _verts.insert(v).first;
244 vptrs[i] = (*n).first;
245 eptrs[i] = &(*n).second;
247 strip._verts.push_back(vptrs[i]);
251 for (i = 0; i < num_verts; i++) {
263 inner_ref._opposite = &outer_ref;
264 outer_ref._opposite = &inner_ref;
267 strip._edges.push_back(&inner_ref);
270 outer_ref._strips.push_back(&strip);
274 eptrs[i]->insert(&outer_ref);
275 eptrs[(i+1) % num_verts]->insert(&outer_ref);
290 if (egg_consider_fans && !_flat_shaded) {
295 if (egg_retesselate_coplanar) {
302 if (egg_show_quads) {
305 for (si = _quads.begin(); si != _quads.end(); ++si) {
306 if ((*si)._status == EggMesherStrip::MS_alive) {
307 (*si)._status = EggMesherStrip::MS_done;
310 for (si = _strips.begin(); si != _strips.end(); ++si) {
311 if ((*si)._status == EggMesherStrip::MS_alive) {
312 (*si)._status = EggMesherStrip::MS_done;
337 EggMesherStrip::PrimType orig_type = strip._type;
338 PT(
EggPrimitive) egg_prim = strip.make_prim(_vertex_pool);
340 if (egg_show_tstrips) {
346 if (egg_prim->is_of_type(EggTriangleStrip::get_class_type()) ||
347 egg_prim->is_of_type(EggTriangleFan::get_class_type())) {
348 make_random_color(color2);
349 color1 = (color2 * 0.8);
353 color1.set(0.85, 0.85, 0.85, 1.0);
354 color2.set(0.85, 0.85, 0.85, 1.0);
359 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
362 if (num_components > 0) {
364 for (
int i = 1; i < num_components; i++) {
369 egg_prim->set_color(color1);
372 int num_verts = egg_prim->size();
373 for (
int i = 0; i < num_verts; i++) {
374 egg_prim->get_vertex(i)->clear_color();
377 }
else if (egg_show_qsheets) {
384 if (strip._row_id < 0) {
386 ColorSheetMap::iterator ci = _color_sheets.find(strip._row_id);
388 if (ci == _color_sheets.end()) {
389 make_random_color(color1);
390 _color_sheets[strip._row_id] = color1;
392 color1 = (*ci).second;
398 egg_prim->set_color(color1);
399 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
402 for (
int i = 0; i < num_components; i++) {
406 int num_verts = egg_prim->size();
407 for (
int i = 0; i < num_verts; i++) {
408 egg_prim->get_vertex(i)->clear_color();
411 }
else if (egg_show_quads) {
425 LColor white(0.85, 0.85, 0.85, 1.0);
426 LColor dark_blue(0.0, 0.0, 0.75, 1.0);
427 LColor light_blue(0.4, 0.4, 0.8, 1.0);
428 LColor very_light_blue(0.6, 0.6, 1.0, 1.0);
429 LColor green(0.2, 0.8, 0.2, 1.0);
432 if (strip._origin == EggMesherStrip::MO_user) {
434 }
else if (strip._origin == EggMesherStrip::MO_firstquad) {
436 }
else if (strip._origin == EggMesherStrip::MO_fanpoly) {
440 case EggMesherStrip::PT_quad:
444 case EggMesherStrip::PT_quadstrip:
445 color1 = very_light_blue;
448 case EggMesherStrip::PT_tristrip:
449 make_random_color(color1);
451 if (color1[0] < color1[1]) {
452 PN_stdfloat t = color1[0];
453 color1[0] = color1[1];
456 color1[2] = color1[1];
459 case EggMesherStrip::PT_trifan:
460 make_random_color(color1);
462 if (color1[0] > color1[1]) {
463 PN_stdfloat t = color1[0];
464 color1[0] = color1[1];
467 color1[2] = color1[0];
477 egg_prim->set_color(color1);
478 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
481 for (
int i = 0; i < num_components; i++) {
485 int num_verts = egg_prim->size();
486 for (
int i = 0; i < num_verts; i++) {
487 egg_prim->get_vertex(i)->clear_color();
501 count_vert_edges(
const EdgePtrs &edges)
const {
503 EdgePtrs::const_iterator ei;
504 for (ei = edges.begin(); ei != edges.end(); ++ei) {
505 count += (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty());
519 switch (strip._status) {
520 case EggMesherStrip::MS_done:
523 case EggMesherStrip::MS_dead:
526 case EggMesherStrip::MS_alive:
527 switch (strip._type) {
528 case EggMesherStrip::PT_tri:
531 case EggMesherStrip::PT_quad:
539 egg_cat.fatal() <<
"Invalid strip status!\n";
560 int first_row_id = 1;
564 pre_sheeted.splice(pre_sheeted.end(), _quads);
566 while (!pre_sheeted.empty()) {
569 Strips::iterator best = pre_sheeted.begin();
574 if ((*best)._row_id >= 0 &&
575 (*best)._status == EggMesherStrip::MS_alive &&
576 !(*best)._edges.empty()) {
582 const EggMesherEdge *edge_b = (*best).find_adjacent_edge(edge_a);
586 int first_row_id_a = first_row_id;
587 (*best).measure_sheet(edge_a,
true, num_prims_a, num_rows_a,
588 first_row_id_a, 0, 0);
589 first_row_id += num_rows_a;
590 double avg_length_a = (double)num_prims_a / (
double)num_rows_a;
594 int first_row_id_b = first_row_id;
596 if (edge_b != NULL) {
597 (*best).measure_sheet(edge_b,
true, num_prims_b, num_rows_b,
598 first_row_id_b, 0, 0);
599 first_row_id += num_rows_b;
600 avg_length_b = (double)num_prims_b / (
double)num_rows_b;
604 if (edge_b != NULL && avg_length_b >= avg_length_a) {
606 (*best).cut_sheet(first_row_id_b,
true, _vertex_pool);
616 first_row_id_a = first_row_id;
617 (*best).measure_sheet(edge_a,
true, num_prims_a, num_rows_a,
618 first_row_id_a, 0, 0);
619 first_row_id += num_rows_a;
622 (*best).cut_sheet(first_row_id_a,
true, _vertex_pool);
628 Strips &list = choose_strip_list(*best);
629 list.splice(list.end(), pre_sheeted, best);
647 PT(EggGroupNode) unrolled_tris = new
EggGroup;
654 for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
655 EdgePtrs &edges = (*vi).second;
663 if (edges.size() > 6) {
670 EdgePtrs::iterator ei;
671 EggMesherEdge::Strips::iterator si;
672 for (ei = edges.begin(); ei != edges.end(); ++ei) {
673 for (si = (*ei)->_strips.begin();
674 si != (*ei)->_strips.end();
677 if (strip->_type == EggMesherStrip::PT_tri) {
679 if (!fan._edges.empty()) {
687 sort(fans.begin(), fans.end());
688 fans.erase(unique(fans.begin(), fans.end()),
691 FanMakers::iterator fi, fi2;
697 for (fi = fans.begin(); fi != fans.end(); ++fi) {
698 if (!(*fi).is_empty()) {
700 for (++fi2; fi2 != fans.end(); ++fi2) {
701 if (!(*fi2).is_empty()) {
702 joined_any = (*fi).join(*fi2);
707 }
while (joined_any);
709 for (fi = fans.begin(); fi != fans.end(); ++fi) {
710 if ((*fi).is_valid()) {
711 (*fi).build(unrolled_tris);
722 EggGroupNode::iterator ti;
723 for (ti = unrolled_tris->begin(); ti != unrolled_tris->end(); ++ti) {
724 add_polygon(DCAST(
EggPolygon, (*ti)), EggMesherStrip::MO_fanpoly);
754 typedef pair<EggMesherStrip *, EggMesherStrip *> Pair;
755 typedef pair<Pair, EggMesherEdge *> Matched;
764 for (si = _tris.begin(); si != _tris.end(); ++si) {
767 if (tri->_status == EggMesherStrip::MS_alive) {
770 if (mate->_type == EggMesherStrip::PT_tri &&
771 mate->_status == EggMesherStrip::MS_alive &&
775 soulmates.push_back(Matched(Pair(tri, mate), common_edge));
777 tri->_status = EggMesherStrip::MS_paired;
778 mate->_status = EggMesherStrip::MS_paired;
786 SoulMates::iterator mi;
787 for (mi = soulmates.begin(); mi != soulmates.end(); ++mi) {
788 tri = (*mi).first.first;
789 mate = (*mi).first.second;
790 common_edge = (*mi).second;
792 nassertv(tri->_status == EggMesherStrip::MS_paired);
793 nassertv(mate->_status == EggMesherStrip::MS_paired);
794 tri->_status = EggMesherStrip::MS_alive;
795 mate->_status = EggMesherStrip::MS_alive;
798 tri->_origin = EggMesherStrip::MO_firstquad;
802 Strips::iterator next;
804 while (si != _tris.end()) {
808 Strips &list = choose_strip_list(*si);
809 if (&list != &_tris) {
810 list.splice(list.end(), _tris, si);
823 mesh_list(Strips &strips) {
824 while (!strips.empty()) {
827 Strips::iterator best = strips.begin();
829 if ((*best)._status == EggMesherStrip::MS_alive) {
830 (*best).mate(_vertex_pool);
836 Strips &list = choose_strip_list(*best);
837 list.splice(list.end(), strips, best);
851 for (
int i = 0; i < 3; i++) {
852 rgb[i] = (double)rand() / (double)RAND_MAX;
857 }
while (len < .1 || len > 1.5);
859 color.set(rgb[0], rgb[1], rgb[2],
860 0.25 + 0.75 * (
double)rand() / (
double)RAND_MAX);
A base class for any of a number of kinds of geometry primitives: polygons, point lights...
The base class for primitives such as triangle strips and triangle fans, which include several compon...
A base class for nodes in the hierarchy that are not leaf nodes.
This is a three-component vector distance (as opposed to a three-component point, which represents a ...
static void consider_yield()
Possibly suspends the current thread for the rest of the current epoch, if it has run for enough this...
This is our own Panda specialization on the default STL vector.
void mesh(EggGroupNode *group, bool flat_shaded)
Accepts an EggGroupNode, which contains a set of EggPrimitives–typically, triangles and quads–as chil...
The main glue of the egg hierarchy, this corresponds to the <Group>, <Instance>, and <Joint> type nod...
This class is used by EggMesher::find_fans() to attempt to make an EggTriangleFan out of the polygons...
Collects together unrelated EggPrimitives, determines their edge connectivity, and generates a set of...
const EggAttributes * get_component(int i) const
Returns the attributes for the nth component triangle.
void steal_children(EggGroupNode &other)
Moves all the children from the other node to this one.
This is the base class for all three-component vectors and points.
Represents one edge of a triangle, as used by the EggMesher to discover connected triangles...
bool find_ideal_mate(EggMesherStrip *&mate, EggMesherEdge *&common_edge, const EggVertexPool *vertex_pool)
Searches our neighbors for the most suitable mate.
Represents a triangle strip or quad strip in progress, as assembled by the mesher.
A base class for things that may be directly added into the egg hierarchy.
static bool mate_pieces(EggMesherEdge *common_edge, EggMesherStrip &front, EggMesherStrip &back, const EggVertexPool *vertex_pool)
Connects two pieces of arbitrary type, if possible.
A collection of vertices.
int get_num_components() const
Returns the number of individual component triangles within the composite.
EggVertexPool * get_pool() const
Returns the vertex pool associated with the vertices of the primitive, or NULL if the primitive has n...