27 EggMesherStrip(PrimType prim_type, MesherOrigin origin) {
49 _flat_shaded = flat_shaded;
55 _prims.push_back(prim);
57 if (_type == PT_poly) {
58 switch (prim->size()) {
69 if (_type == PT_quad) {
72 _prims.push_back(prim);
77 if (prim->
is_of_type(EggPolygon::get_class_type())) {
81 if (DCAST(
EggPolygon, prim)->calculate_normal(normal)) {
82 _plane_normal = normal;
85 _plane_offset = -dot(_plane_normal, p1);
104 dest_type = PT_tristrip;
108 dest_type = PT_trifan;
115 if (dest_type != PT_tristrip && dest_type != PT_trifan) {
121 for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
128 if (dest_type == PT_trifan) {
141 for (vi = _verts.begin();
142 vi != _verts.end() && pi != _prims.end();
160 nassertr(vi == _verts.end(), prim);
161 nassertr(pi == _prims.end(), prim);
174 int &num_rows,
int first_row_id,
int this_row_id,
175 int this_row_distance) {
179 if (_row_id >= first_row_id) {
185 if (_row_id >= first_row_id && _row_distance <= this_row_distance) {
190 num_prims += _prims.size();
193 this_row_id = first_row_id + num_rows - 1;
196 _row_id = this_row_id;
199 EggMesherEdge::Strips::iterator si;
201 if (_type == PT_quad) {
205 int vi_a = edge->_vi_a;
206 int vi_b = edge->_vi_b;
230 for (
int secondary = 0; secondary <= 1; secondary++) {
235 want_count = new_row ? 0 : 1;
237 want_count = new_row ? 1 : 0;
240 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
242 ((*ei)->_vi_a == vi_a || (*ei)->_vi_a == vi_b) +
243 ((*ei)->_vi_b == vi_a || (*ei)->_vi_b == vi_b);
245 if (common_verts == want_count) {
252 for (si = strips.begin(); si != strips.end(); ++si) {
253 if ((*si)->_row_id < first_row_id) {
260 mate->measure_sheet(*ei, secondary, num_prims, num_rows,
261 first_row_id, this_row_id,
262 this_row_distance + secondary);
271 nassertv(_type != PT_tri);
274 nassertv(_type == PT_tristrip || _type == PT_quadstrip);
279 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
280 if (!(*ei)->matches(*edge)) {
285 for (si = strips.begin(); si != strips.end(); ++si) {
286 if ((*si)->_row_id < first_row_id) {
292 if (
mate !=
nullptr) {
293 mate->measure_sheet(*ei,
false, num_prims, num_rows,
294 first_row_id, this_row_id, this_row_distance);
305 void EggMesherStrip::
306 cut_sheet(
int first_row_id,
int do_mate,
const EggVertexPool *vertex_pool) {
308 EggMesherEdge::Strips::iterator si;
319 StripPtrs strip_ptrs;
321 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
323 for (si = strips.begin(); si != strips.end(); ++si) {
324 if ((*si)->_row_id > _row_id) {
326 strip_ptrs.push_back(*si);
334 StripPtrs::iterator spi;
335 for (spi = strip_ptrs.begin(); spi != strip_ptrs.end(); ++spi) {
336 if ((*spi)->_status == MS_alive) {
337 (*spi)->cut_sheet(first_row_id,
true, vertex_pool);
342 if (do_mate && _status == MS_alive) {
349 while (not_any && ei != _edges.end()) {
352 while (not_any && si != strips.end()) {
353 if (*si !=
this && (*si)->_row_id == _row_id) {
364 mate->cut_sheet(first_row_id,
false, vertex_pool);
366 if (_status == MS_alive &&
mate->_status == MS_alive) {
385 _row_id = -first_row_id;
400 nassertr(_status == MS_alive,
false);
412 nassertr(!
mate->_prims.empty(),
false);
413 nassertr(!
mate->_verts.empty(),
false);
432 common_edge =
nullptr;
434 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
436 EggMesherEdge::Strips::iterator si;
437 for (si = strips.begin(); si != strips.end(); ++si) {
448 return (
mate!=
nullptr);
461 nassertr(front._status == MS_alive,
false);
462 nassertr(back._status == MS_alive,
false);
463 nassertr(&front != &back,
false);
468 bool remove_sides =
true;
472 if (front._type == PT_tri && back._type == PT_tri) {
474 if (is_coplanar && egg_retesselate_coplanar &&
475 front._prims.front() == back._prims.front() &&
476 convex_quad(common_edge, front, back, vertex_pool)) {
479 front._type = PT_quad;
488 Verts::iterator a = front._verts.begin();
489 Verts::iterator b = a;
495 front._verts.insert(b, new_vert);
498 front._verts.push_back(new_vert);
503 front._verts.insert(b, new_vert);
506 front._prims.splice(front._prims.end(), back._prims);
511 remove_sides =
false;
515 front._type = PT_tristrip;
520 front._verts.push_back(new_vert);
521 front._prims.splice(front._prims.end(), back._prims);
525 }
else if ((front._type == PT_quad || front._type == PT_quadstrip) &&
526 (back._type == PT_quad || back._type == PT_quadstrip)) {
531 success =
mate_strips(common_edge, front, back, PT_quadstrip);
537 common_edge->
remove(&front);
538 common_edge->
remove(&back);
549 success =
mate_strips(common_edge, front, back, PT_tristrip);
555 success =
mate_strips(common_edge, back, front, PT_tristrip);
559 front._verts.splice(front._verts.end(), back._verts);
560 front._prims.splice(front._prims.end(), back._prims);
564 common_edge->
remove(&front);
565 common_edge->
remove(&back);
575 common_edge->
remove(&front);
578 nassertr(back._prims.empty(),
false);
579 nassertr(back._verts.empty(),
false);
582 back._status = MS_dead;
585 front._planar = is_coplanar;
586 front._origin = MO_mate;
611 if ((front._type != PT_tri && back._type == PT_tri) ||
612 (front._type == PT_tri && back._type != PT_tri) ||
613 (front._type == PT_tristrip && back._type == PT_tristrip &&
614 ((front._verts.size() + back._verts.size()) & 1) != 0)) {
620 if (front._type == PT_tri || front._type == PT_quad) {
623 if (back._type == PT_tri || back._type == PT_quad) {
630 bool invert_front =
false;
631 bool invert_back =
false;
633 if (reverse_front && front.
is_odd()) {
643 if (
must_invert(front, back, reverse_back, type)) {
656 reverse(front._verts.begin(), front._verts.end());
657 reverse(front._prims.begin(), front._prims.end());
661 reverse(back._verts.begin(), back._verts.end());
662 reverse(back._prims.begin(), back._prims.end());
667 if (will_reverse == is_headtotail) {
672 reverse(back._verts.begin(), back._verts.end());
673 reverse(back._prims.begin(), back._prims.end());
679 reverse(front._verts.begin(), front._verts.end());
680 reverse(front._prims.begin(), front._prims.end());
720 front._verts.pop_back();
721 front._verts.pop_back();
722 front._verts.splice(front._verts.end(), back._verts);
723 front._prims.splice(front._prims.end(), back._prims);
734 bool will_reverse_back, EggMesherStrip::PrimType type) {
737 if ((front._type == PT_quad || front._type == PT_quadstrip) &&
738 type == PT_tristrip) {
742 }
else if (front.
is_odd()) {
747 if (will_reverse_back) {
773 nassertr(vi_a >= 0 && vi_b >= 0,
false);
775 LPoint3d a3, b3, c3, d3;
785 nassertr(front._planar,
false);
787 LNormald n(front._plane_normal);
791 if (fabs(n[0]) > fabs(n[1])) {
792 if (fabs(n[0]) > fabs(n[2])) {
800 if (fabs(n[1]) > fabs(n[2])) {
809 LVecBase2d a2, b2, c2, d2;
810 a2.set(a3[xi], a3[yi]);
811 b2.set(b3[xi], b3[yi]);
812 c2.set(c3[xi], c3[yi]);
813 d2.set(d3[xi], d3[yi]);
820 double A = (b2[1] - a2[1]);
821 double B = (a2[0] - b2[0]);
822 double C = -(A*b2[0] + B*b2[1]);
828 double t = - ((A*c2[0] + B*c2[1]) + C) / (A*(d2[0]-c2[0]) + B*(d2[1]-c2[1]));
831 return (0.0 <= t && t <= 1.0);
840 Edges::const_iterator ei;
842 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
843 count += (*ei)->_strips.size();
853 Edges::const_iterator ei;
854 EggMesherEdge::Strips::const_iterator si;
856 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
857 for (si = (*ei)->_strips.begin();
858 si != (*ei)->_strips.end();
860 out <<
" " << (*si)->_index;
870 int vi_a = edge->_vi_a;
871 int vi_b = edge->_vi_b;
873 Edges::const_iterator ei;
874 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
877 if (e->_vi_a != vi_a && e->_vi_a != vi_b) {
879 }
else if (e->_vi_b != vi_a && e->_vi_b != vi_b) {
893 Edges::const_iterator ei;
894 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
910 int vi_a = edge->_vi_a;
911 int vi_b = edge->_vi_b;
913 Edges::const_iterator ei;
914 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
930 int vi_a = edge->_vi_a;
931 int vi_b = edge->_vi_b;
933 Edges::const_iterator ei;
934 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
950 int vi_a = edge->_vi_a;
951 int vi_b = edge->_vi_b;
954 if (_verts.front() == vi_a || _verts.front() == vi_b) {
955 Verts::iterator vi = _verts.begin();
957 if (*vi == vi_a || *vi == vi_b) {
967 int num_verts = _verts.size();
968 while (_verts.front() != vi_a && _verts.front() != vi_b) {
971 nassertv(num_verts > 0);
978 Verts::iterator vi = _verts.begin();
980 nassertv(*vi == vi_a || *vi == vi_b);
990 int vi_a = edge->_vi_a;
991 int vi_b = edge->_vi_b;
994 if (_verts.back() == vi_a || _verts.back() == vi_b) {
995 Verts::reverse_iterator vi = _verts.rbegin();
997 if (*vi == vi_a || *vi == vi_b) {
1007 int num_verts = _verts.size();
1008 while (_verts.back() != vi_a && _verts.back() != vi_b) {
1011 nassertv(num_verts > 0);
1018 Verts::reverse_iterator vi = _verts.rbegin();
1020 nassertv(*vi == vi_a || *vi == vi_b);
1031 return (_type == PT_quadstrip || _type == PT_quad);
1043 Verts::iterator vi, vi2;
1044 vi = _verts.begin();
1045 while (vi != _verts.end()) {
1048 nassertr(vi2 != _verts.end(),
false);
1067 if (_type == PT_quadstrip || _type == PT_quad) {
1070 return (_verts.size() % 4 == 0);
1074 return (_verts.size() % 2 == 1);
1084 bool reverse =
false;
1086 if (_type == want_type) {
1089 if (want_type == PT_tristrip) {
1099 reverse = (_verts.size() % 4 == 0);
1103 egg_cat.fatal() <<
"Invalid conversion!\n";
1108 }
else if (want_type == PT_quadstrip) {
1119 egg_cat.fatal() <<
"Invalid conversion!\n";
1135 Verts::iterator vi, vi2;
1138 if (_type == want_type) {
1141 if (want_type == PT_tristrip) {
1152 vi = _verts.begin();
1154 while (vi != _verts.end()) {
1157 nassertv(vi2 != _verts.end());
1174 egg_cat.fatal() <<
"Invalid conversion!\n";
1178 }
else if (want_type == PT_quadstrip) {
1189 egg_cat.fatal() <<
"Invalid conversion!\n";
1205 for (ei = other._edges.begin(); ei != other._edges.end(); ++ei) {
1206 (*ei)->change_strip(&other,
this);
1209 _edges.splice(_edges.end(), other._edges);
1224 Edges::iterator next_ei;
1225 ei = _edges.begin();
1226 while (ei != _edges.end()) {
1231 if (!(**ei == head) && !(**ei == tail)) {
1234 junk_edges.splice(junk_edges.end(), _edges, ei);
1240 for (ei = junk_edges.begin(); ei != junk_edges.end(); ++ei) {
1241 (*ei)->remove(
this);
1256 junk_edges.splice(junk_edges.end(), _edges);
1260 for (ei = junk_edges.begin(); ei != junk_edges.end(); ++ei) {
1261 (*ei)->remove(
this);
1281 if (a_cat != b_cat) {
1283 return abs(a_cat - me_cat) < abs(b_cat - me_cat);
1288 if (_type == PT_tri && a_strip._type == PT_tri &&
1289 b_strip._type == PT_tri) {
1298 double coplanar_diff = a_coplanar - b_coplanar;
1302 double length_diff = (a_length - b_length) / (a_length + b_length);
1305 double sum = 4.0 * coplanar_diff - 1.0 * length_diff;
1310 if (a_strip._prims.size() != b_strip._prims.size()) {
1311 return a_strip._prims.size() < b_strip._prims.size();
1328 if (_planar && a_strip._planar && b_strip._planar) {
1329 double a_diff = dot(LNormald(_plane_normal), LNormald(a_strip._plane_normal));
1330 double b_diff = dot(LNormald(_plane_normal), LNormald(b_strip._plane_normal));
1332 if (fabs(a_diff - b_diff) > 0.0001) {
1333 return a_diff > b_diff;
1340 if (a_cat != b_cat) {
1342 return abs(a_cat - me_cat) < abs(b_cat - me_cat);
1353 output(std::ostream &out)
const {
1367 out <<
"Unknown status ";
1399 out <<
" " << _index <<
" [";
1401 Verts::const_iterator vi;
1402 for (vi = _verts.begin(); vi != _verts.end(); vi++) {
1405 out <<
" ]: " << _prims.size()
1411 Edges::const_iterator ei;
1412 for (ei = _edges.begin(); ei != _edges.end(); ei++) {
1413 out <<
" " << (
void *)(*ei);