15 #include "eggMesherStrip.h" 16 #include "eggMesherEdge.h" 17 #include "eggPrimitive.h" 18 #include "eggTriangleFan.h" 19 #include "eggTriangleStrip.h" 20 #include "eggPolygon.h" 22 #include "config_egg.h" 30 EggMesherStrip(PrimType prim_type, MesherOrigin origin) {
54 _flat_shaded = flat_shaded;
60 _prims.push_back(prim);
62 if (_type == PT_poly) {
63 switch (prim->size()) {
74 if (_type == PT_quad) {
77 _prims.push_back(prim);
82 if (prim->
is_of_type(EggPolygon::get_class_type())) {
87 if (DCAST(
EggPolygon, prim)->calculate_normal(normal)) {
88 _plane_normal = normal;
91 _plane_offset = -dot(_plane_normal, p1);
112 dest_type = PT_tristrip;
116 dest_type = PT_trifan;
123 if (dest_type != PT_tristrip && dest_type != PT_trifan) {
129 for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
136 if (dest_type == PT_trifan) {
150 for (vi = _verts.begin();
151 vi != _verts.end() && pi != _prims.end();
169 nassertr(vi == _verts.end(), prim);
170 nassertr(pi == _prims.end(), prim);
185 int &num_rows,
int first_row_id,
int this_row_id,
186 int this_row_distance) {
190 if (_row_id >= first_row_id) {
197 if (_row_id >= first_row_id && _row_distance <= this_row_distance) {
202 num_prims += _prims.size();
205 this_row_id = first_row_id + num_rows - 1;
208 _row_id = this_row_id;
211 EggMesherEdge::Strips::iterator si;
213 if (_type == PT_quad) {
217 int vi_a = edge->_vi_a;
218 int vi_b = edge->_vi_b;
242 for (
int secondary = 0; secondary <= 1; secondary++) {
248 want_count = new_row ? 0 : 1;
250 want_count = new_row ? 1 : 0;
253 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
255 ((*ei)->_vi_a == vi_a || (*ei)->_vi_a == vi_b) +
256 ((*ei)->_vi_b == vi_a || (*ei)->_vi_b == vi_b);
258 if (common_verts == want_count) {
265 for (si = strips.begin(); si != strips.end(); ++si) {
266 if ((*si)->_row_id < first_row_id) {
274 first_row_id, this_row_id,
275 this_row_distance + secondary);
284 nassertv(_type != PT_tri);
287 nassertv(_type == PT_tristrip || _type == PT_quadstrip);
292 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
293 if (!(*ei)->matches(*edge)) {
298 for (si = strips.begin(); si != strips.end(); ++si) {
299 if ((*si)->_row_id < first_row_id) {
307 first_row_id, this_row_id, this_row_distance);
320 void EggMesherStrip::
321 cut_sheet(
int first_row_id,
int do_mate,
const EggVertexPool *vertex_pool) {
323 EggMesherEdge::Strips::iterator si;
334 StripPtrs strip_ptrs;
336 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
338 for (si = strips.begin(); si != strips.end(); ++si) {
339 if ((*si)->_row_id > _row_id) {
341 strip_ptrs.push_back(*si);
349 StripPtrs::iterator spi;
350 for (spi = strip_ptrs.begin(); spi != strip_ptrs.end(); ++spi) {
351 if ((*spi)->_status == MS_alive) {
352 (*spi)->cut_sheet(first_row_id,
true, vertex_pool);
357 if (do_mate && _status == MS_alive) {
364 while (not_any && ei != _edges.end()) {
367 while (not_any && si != strips.end()) {
368 if (*si !=
this && (*si)->_row_id == _row_id) {
379 mate->cut_sheet(first_row_id,
false, vertex_pool);
381 if (_status == MS_alive && mate->_status == MS_alive) {
400 _row_id = -first_row_id;
419 nassertr(_status == MS_alive,
false);
431 nassertr(!mate->_prims.empty(),
false);
432 nassertr(!mate->_verts.empty(),
false);
434 mate_pieces(common_edge, *
this, *mate, vertex_pool);
456 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
458 EggMesherEdge::Strips::iterator si;
459 for (si = strips.begin(); si != strips.end(); ++si) {
461 if (mate==NULL ||
pick_mate(**si, *mate, **ei, *common_edge,
485 nassertr(front._status == MS_alive,
false);
486 nassertr(back._status == MS_alive,
false);
487 nassertr(&front != &back,
false);
492 bool remove_sides =
true;
496 if (front._type == PT_tri && back._type == PT_tri) {
498 if (is_coplanar && egg_retesselate_coplanar &&
499 front._prims.front() == back._prims.front() &&
500 convex_quad(common_edge, front, back, vertex_pool)) {
504 front._type = PT_quad;
513 Verts::iterator a = front._verts.begin();
514 Verts::iterator b = a;
520 front._verts.insert(b, new_vert);
523 front._verts.push_back(new_vert);
528 front._verts.insert(b, new_vert);
531 front._prims.splice(front._prims.end(), back._prims);
536 remove_sides =
false;
540 front._type = PT_tristrip;
545 front._verts.push_back(new_vert);
546 front._prims.splice(front._prims.end(), back._prims);
550 }
else if ((front._type == PT_quad || front._type == PT_quadstrip) &&
551 (back._type == PT_quad || back._type == PT_quadstrip)) {
556 success =
mate_strips(common_edge, front, back, PT_quadstrip);
563 common_edge->
remove(&front);
564 common_edge->
remove(&back);
575 success =
mate_strips(common_edge, front, back, PT_tristrip);
582 success =
mate_strips(common_edge, back, front, PT_tristrip);
586 front._verts.splice(front._verts.end(), back._verts);
587 front._prims.splice(front._prims.end(), back._prims);
591 common_edge->
remove(&front);
592 common_edge->
remove(&back);
602 common_edge->
remove(&front);
605 nassertr(back._prims.empty(),
false);
606 nassertr(back._verts.empty(),
false);
609 back._status = MS_dead;
613 front._planar = is_coplanar;
614 front._origin = MO_mate;
643 if ((front._type != PT_tri && back._type == PT_tri) ||
644 (front._type == PT_tri && back._type != PT_tri) ||
645 (front._type == PT_tristrip && back._type == PT_tristrip &&
646 ((front._verts.size() + back._verts.size()) & 1) != 0)) {
652 if (front._type == PT_tri || front._type == PT_quad) {
655 if (back._type == PT_tri || back._type == PT_quad) {
662 bool invert_front =
false;
663 bool invert_back =
false;
665 if (reverse_front && front.
is_odd()) {
675 if (
must_invert(front, back, reverse_back, type)) {
688 reverse(front._verts.begin(), front._verts.end());
689 reverse(front._prims.begin(), front._prims.end());
693 reverse(back._verts.begin(), back._verts.end());
694 reverse(back._prims.begin(), back._prims.end());
699 if (will_reverse == is_headtotail) {
705 reverse(back._verts.begin(), back._verts.end());
706 reverse(back._prims.begin(), back._prims.end());
712 reverse(front._verts.begin(), front._verts.end());
713 reverse(front._prims.begin(), front._prims.end());
753 front._verts.pop_back();
754 front._verts.pop_back();
755 front._verts.splice(front._verts.end(), back._verts);
756 front._prims.splice(front._prims.end(), back._prims);
770 bool will_reverse_back, EggMesherStrip::PrimType type) {
773 if ((front._type == PT_quad || front._type == PT_quadstrip) &&
774 type == PT_tristrip) {
778 }
else if (front.
is_odd()) {
783 if (will_reverse_back) {
812 nassertr(vi_a >= 0 && vi_b >= 0,
false);
825 nassertr(front._planar,
false);
831 if (fabs(n[0]) > fabs(n[1])) {
832 if (fabs(n[0]) > fabs(n[2])) {
840 if (fabs(n[1]) > fabs(n[2])) {
850 a2.set(a3[xi], a3[yi]);
851 b2.set(b3[xi], b3[yi]);
852 c2.set(c3[xi], c3[yi]);
853 d2.set(d3[xi], d3[yi]);
862 double A = (b2[1] - a2[1]);
863 double B = (a2[0] - b2[0]);
864 double C = -(A*b2[0] + B*b2[1]);
871 double t = - ((A*c2[0] + B*c2[1]) + C) / (A*(d2[0]-c2[0]) + B*(d2[1]-c2[1]));
874 return (0.0 <= t && t <= 1.0);
885 Edges::const_iterator ei;
887 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
888 count += (*ei)->_strips.size();
900 Edges::const_iterator ei;
901 EggMesherEdge::Strips::const_iterator si;
903 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
904 for (si = (*ei)->_strips.begin();
905 si != (*ei)->_strips.end();
907 out <<
" " << (*si)->_index;
920 int vi_a = edge->_vi_a;
921 int vi_b = edge->_vi_b;
923 Edges::const_iterator ei;
924 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
927 if (e->_vi_a != vi_a && e->_vi_a != vi_b) {
929 }
else if (e->_vi_b != vi_a && e->_vi_b != vi_b) {
946 Edges::const_iterator ei;
947 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
966 int vi_a = edge->_vi_a;
967 int vi_b = edge->_vi_b;
969 Edges::const_iterator ei;
970 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
989 int vi_a = edge->_vi_a;
990 int vi_b = edge->_vi_b;
992 Edges::const_iterator ei;
993 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
1011 int vi_a = edge->_vi_a;
1012 int vi_b = edge->_vi_b;
1015 if (_verts.front() == vi_a || _verts.front() == vi_b) {
1016 Verts::iterator vi = _verts.begin();
1018 if (*vi == vi_a || *vi == vi_b) {
1028 int num_verts = _verts.size();
1029 while (_verts.front() != vi_a && _verts.front() != vi_b) {
1032 nassertv(num_verts > 0);
1039 Verts::iterator vi = _verts.begin();
1041 nassertv(*vi == vi_a || *vi == vi_b);
1053 int vi_a = edge->_vi_a;
1054 int vi_b = edge->_vi_b;
1057 if (_verts.back() == vi_a || _verts.back() == vi_b) {
1058 Verts::reverse_iterator vi = _verts.rbegin();
1060 if (*vi == vi_a || *vi == vi_b) {
1070 int num_verts = _verts.size();
1071 while (_verts.back() != vi_a && _verts.back() != vi_b) {
1074 nassertv(num_verts > 0);
1081 Verts::reverse_iterator vi = _verts.rbegin();
1083 nassertv(*vi == vi_a || *vi == vi_b);
1097 return (_type == PT_quadstrip || _type == PT_quad);
1112 Verts::iterator vi, vi2;
1113 vi = _verts.begin();
1114 while (vi != _verts.end()) {
1117 nassertr(vi2 != _verts.end(),
false);
1139 if (_type == PT_quadstrip || _type == PT_quad) {
1142 return (_verts.size() % 4 == 0);
1146 return (_verts.size() % 2 == 1);
1158 bool reverse =
false;
1160 if (_type == want_type) {
1163 if (want_type == PT_tristrip) {
1173 reverse = (_verts.size() % 4 == 0);
1177 egg_cat.fatal() <<
"Invalid conversion!\n";
1182 }
else if (want_type == PT_quadstrip) {
1193 egg_cat.fatal() <<
"Invalid conversion!\n";
1212 Verts::iterator vi, vi2;
1215 if (_type == want_type) {
1218 if (want_type == PT_tristrip) {
1229 vi = _verts.begin();
1231 while (vi != _verts.end()) {
1234 nassertv(vi2 != _verts.end());
1251 egg_cat.fatal() <<
"Invalid conversion!\n";
1255 }
else if (want_type == PT_quadstrip) {
1266 egg_cat.fatal() <<
"Invalid conversion!\n";
1284 for (ei = other._edges.begin(); ei != other._edges.end(); ++ei) {
1285 (*ei)->change_strip(&other,
this);
1288 _edges.splice(_edges.end(), other._edges);
1304 Edges::iterator next_ei;
1305 ei = _edges.begin();
1306 while (ei != _edges.end()) {
1311 if (!(**ei == head) && !(**ei == tail)) {
1315 junk_edges.splice(junk_edges.end(), _edges, ei);
1321 for (ei = junk_edges.begin(); ei != junk_edges.end(); ++ei) {
1322 (*ei)->remove(
this);
1340 junk_edges.splice(junk_edges.end(), _edges);
1344 for (ei = junk_edges.begin(); ei != junk_edges.end(); ++ei) {
1345 (*ei)->remove(
this);
1368 if (a_cat != b_cat) {
1370 return abs(a_cat - me_cat) < abs(b_cat - me_cat);
1375 if (_type == PT_tri && a_strip._type == PT_tri &&
1376 b_strip._type == PT_tri) {
1386 double coplanar_diff = a_coplanar - b_coplanar;
1390 double length_diff = (a_length - b_length) / (a_length + b_length);
1393 double sum = 4.0 * coplanar_diff - 1.0 * length_diff;
1398 if (a_strip._prims.size() != b_strip._prims.size()) {
1399 return a_strip._prims.size() < b_strip._prims.size();
1419 if (_planar && a_strip._planar && b_strip._planar) {
1420 double a_diff = dot(
LNormald(_plane_normal),
LNormald(a_strip._plane_normal));
1421 double b_diff = dot(
LNormald(_plane_normal),
LNormald(b_strip._plane_normal));
1423 if (fabs(a_diff - b_diff) > 0.0001) {
1424 return a_diff > b_diff;
1431 if (a_cat != b_cat) {
1433 return abs(a_cat - me_cat) < abs(b_cat - me_cat);
1460 out <<
"Unknown status ";
1492 out <<
" " << _index <<
" [";
1494 Verts::const_iterator vi;
1495 for (vi = _verts.begin(); vi != _verts.end(); vi++) {
1498 out <<
" ]: " << _prims.size()
1504 Edges::const_iterator ei;
1505 for (ei = _edges.begin(); ei != _edges.end(); ei++) {
1506 out <<
" " << (
void *)(*ei);
A base class for any of a number of kinds of geometry primitives: polygons, point lights...
void remove(EggMesherStrip *strip)
Removes an edge from a particular strip.
The base class for primitives such as triangle strips and triangle fans, which include several compon...
void rotate_to_front(const EggMesherEdge *edge)
Rotates a triangle or quad so that the given edge is first in the vertex list.
This is the base class for all two-component vectors and points.
EggVertex * get_vertex(int index) const
Returns the vertex in the pool with the indicated index number, or NULL if no vertices have that inde...
void rotate_forward()
Rotates a triangle or quad by bringing its first vertex to the back.
static bool mate_strips(EggMesherEdge *common_edge, EggMesherStrip &front, EggMesherStrip &back, PrimType type)
Stitches two strips together, producing in "front" a new strip of the indicated type (quadstrip or tr...
A connected fan of triangles.
bool can_invert() const
Returns true if the strip can be inverted (reverse its facing direction).
void copy_attributes(const EggAttributes &other)
Copies the rendering attributes from the indicated primitive.
bool is_coplanar_with(const EggMesherStrip &other, PN_stdfloat threshold) const
Returns true if the strip and the other strip are coplanar, within the indicated threshold.
PN_stdfloat coplanarity(const EggMesherStrip &other) const
Returns the degree to which the two strips are coplanar.
bool mate(const EggVertexPool *vertex_pool)
Finds a neighboring strip and joins up with it to make a larger strip.
This is our own Panda specialization on the default STL list.
EggMesherEdge get_head_edge() const
Returns an EggMesherEdge which represents the leading edge in the quadstrip or tristrip.
LVertexd get_pos3() const
Valid if get_num_dimensions() returns 3 or 4.
void combine_edges(EggMesherStrip &other, int remove_sides)
Removes the edges from the given strip and appends them to our own.
void rotate_back()
Rotates a triangle or quad by bringing its last vertex to the front.
const EggMesherEdge * find_opposite_edge(int vi) const
Returns the first edge found that does not contain the given vertex.
void measure_sheet(const EggMesherEdge *edge, int new_row, int &num_prims, int &num_rows, int first_row_id, int this_row_id, int this_row_distance)
Determines the extents of the quadsheet that can be derived by starting with this strip...
The set of attributes that may be applied to vertices as well as polygons, such as surface normal and...
void convert_to_type(PrimType want_type)
Converts the EggMesherStrip from whatever form it is–triangle, quad, or quadstrip–into a tristrip o...
bool pick_mate(const EggMesherStrip &a_strip, const EggMesherStrip &b_strip, const EggMesherEdge &a_edge, const EggMesherEdge &b_edge, const EggVertexPool *vertex_pool) const
Defines an ordering to select neighbors to mate with.
bool is_odd() const
Returns true if the tristrip or quadstrip contains an odd number of pieces.
EggMesherEdge get_tail_edge() const
Returns an EggMesherEdge which represents the trailing edge in the quadstrip or tristrip.
bool matches(const EggMesherEdge &other) const
Returns true if this edge represents the same line segment as the other edge, in either direction...
bool contains_vertex(int vi) const
Returns true if the edge contains the indicated vertex index, false otherwise.
Any one-, two-, three-, or four-component vertex, possibly with attributes such as a normal...
void output_neighbors(ostream &out) const
Writes all the neighbor indexes to the ostream.
bool pick_sheet_mate(const EggMesherStrip &a_strip, const EggMesherStrip &b_strip) const
Defines an ordering to select neighbors to follow when measuring out a quadsheet. ...
void remove_all_edges()
Removes all active edges from the strip.
void output(ostream &out) const
Formats the vertex for output in some sensible way.
static bool convex_quad(EggMesherEdge *common_edge, EggMesherStrip &front, EggMesherStrip &back, const EggVertexPool *vertex_pool)
Returns true if the quad that would be formed by connecting coplanar tris front and back along common...
static bool must_invert(const EggMesherStrip &front, const EggMesherStrip &back, bool will_reverse_back, PrimType type)
Returns false if the strips can be mated as they currently are.
int count_neighbors() const
Returns the number of neighbors the strip shares.
void rotate_to_back(const EggMesherEdge *edge)
Rotates a triangle or quad so that the given edge is last in the vertex list.
bool would_reverse_tail(PrimType want_type) const
Returns true if convert_to_type() would reverse the tail edge of the given strip, false otherwise...
Represents one edge of a triangle, as used by the EggMesher to discover connected triangles...
This is a three-component vector distance (as opposed to a three-component point, which represents a ...
int find_uncommon_vertex(const EggMesherEdge *edge) const
Returns the first vertex found that is not shared by the given edge.
This is a three-component point in space (as opposed to a three-component vector, which represents a ...
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.
double compute_length(const EggVertexPool *vertex_pool) const
Returns the length of the edge in model units.
int type_category() const
Returns an integer which gives a heuristic about the similarity of different strip types...
static bool mate_pieces(EggMesherEdge *common_edge, EggMesherStrip &front, EggMesherStrip &back, const EggVertexPool *vertex_pool)
Connects two pieces of arbitrary type, if possible.
bool is_of_type(TypeHandle handle) const
Returns true if the current object is or derives from the indicated type.
bool invert()
Reverses the facing of a quadstrip by reversing pairs of vertices.
const EggMesherEdge * find_adjacent_edge(const EggMesherEdge *edge) const
Returns the first edge found that shares exactly one vertex with the given edge.
A connected strip of triangles.
A collection of vertices.
EggVertex * add_vertex(EggVertex *vertex)
Adds the indicated vertex to the end of the primitive's list of vertices, and returns it...
EggVertex * get_vertex(int index) const
Returns a particular index based on its index number.