Panda3D
eggMesherStrip.cxx
1 // Filename: eggMesherStrip.cxx
2 // Created by: drose (13Mar05)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #include "eggMesherStrip.h"
16 #include "eggMesherEdge.h"
17 #include "eggPrimitive.h"
18 #include "eggTriangleFan.h"
19 #include "eggTriangleStrip.h"
20 #include "eggPolygon.h"
21 #include "dcast.h"
22 #include "config_egg.h"
23 
24 ////////////////////////////////////////////////////////////////////
25 // Function: EggMesherStrip::Constructor
26 // Access: Public
27 // Description:
28 ////////////////////////////////////////////////////////////////////
29 EggMesherStrip::
30 EggMesherStrip(PrimType prim_type, MesherOrigin origin) {
31  _origin = origin;
32  _type = prim_type;
33 
34  _index = -1;
35  _row_id = 0;
36  _status = MS_alive;
37  _planar = false;
38  _flat_shaded = false;
39 }
40 
41 ////////////////////////////////////////////////////////////////////
42 // Function: EggMesherStrip::Constructor
43 // Access: Public
44 // Description:
45 ////////////////////////////////////////////////////////////////////
46 EggMesherStrip::
47 EggMesherStrip(const EggPrimitive *prim, int index,
48  const EggVertexPool *vertex_pool,
49  bool flat_shaded) {
50  _index = index;
51  _row_id = 0;
52  _status = MS_alive;
53  _origin = MO_unknown;
54  _flat_shaded = flat_shaded;
55 
56  _type = PT_poly; //prim.get_type();
57 
58  // We care only about the prim's attributes in the _prims array.
59  // The vertices get re-added later by EggMesher::add_prim().
60  _prims.push_back(prim);
61 
62  if (_type == PT_poly) {
63  switch (prim->size()) {
64  case 3:
65  _type = PT_tri;
66  break;
67 
68  case 4:
69  _type = PT_quad;
70  break;
71  }
72  }
73 
74  if (_type == PT_quad) {
75  // A quad has two internal triangles; we therefore push the prim
76  // attributes twice.
77  _prims.push_back(prim);
78  }
79 
80  _planar = false;
81 
82  if (prim->is_of_type(EggPolygon::get_class_type())) {
83  // Although for the most part we ignore the actual value of the
84  // vertices, we will ask the polygon for its plane equation
85  // (i.e. its normal).
86  LNormald normal;
87  if (DCAST(EggPolygon, prim)->calculate_normal(normal)) {
88  _plane_normal = normal;
89  _planar = true;
90  LPoint3d p1 = prim->get_vertex(0)->get_pos3();
91  _plane_offset = -dot(_plane_normal, p1);
92  }
93  }
94 }
95 
96 
97 ////////////////////////////////////////////////////////////////////
98 // Function: EggMesherStrip::make_prim
99 // Access: Public
100 // Description: Creates an EggPrimitive corresponding to the strip
101 // represented by this node.
102 ////////////////////////////////////////////////////////////////////
103 PT(EggPrimitive) EggMesherStrip::
104 make_prim(const EggVertexPool *vertex_pool) {
105  PT(EggPrimitive) prim;
106  PrimType dest_type;
107 
108  switch (_type) {
109  case PT_quad:
110  case PT_tristrip:
111  case PT_quadstrip:
112  dest_type = PT_tristrip;
113  break;
114 
115  case PT_trifan:
116  dest_type = PT_trifan;
117  break;
118 
119  default:
120  dest_type = _type;
121  }
122 
123  if (dest_type != PT_tristrip && dest_type != PT_trifan) {
124  // The easy case: a simple primitive, i.e. a polygon.
125  prim = new EggPolygon;
126  prim->copy_attributes(*_prims.front());
127 
128  Verts::iterator vi;
129  for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
130  prim->add_vertex(vertex_pool->get_vertex(*vi));
131  }
132 
133  } else {
134  // The harder case: a tristrip of some kind.
135  convert_to_type(dest_type);
136  if (dest_type == PT_trifan) {
137  prim = new EggTriangleFan;
138  } else {
139  prim = new EggTriangleStrip;
140  }
141  prim->copy_attributes(*_prims.front());
142 
143  // Now store all the vertices. Each individual triangle's
144  // attributes, if any, get applied to the third vertex of each
145  // triangle.
146  Verts::iterator vi;
147  Prims::iterator pi;
148  pi = _prims.begin();
149  int count = 0;
150  for (vi = _verts.begin();
151  vi != _verts.end() && pi != _prims.end();
152  ++vi) {
153  PT(EggVertex) vertex = vertex_pool->get_vertex(*vi);
154  prim->add_vertex(vertex);
155 
156  ++count;
157  if (count >= 3) {
158  // Beginning with the third vertex, we increment pi. Thus, the
159  // first two vertices stand alone, then each vertex beginning
160  // with the third completes a triangle.
161  const EggAttributes *attrib = (*pi);
162  ++pi;
163  DCAST(EggCompositePrimitive, prim)->set_component(count - 3, attrib);
164  }
165  }
166 
167  // If either of these fail, there weren't num_prims + 2 vertices in
168  // the tristrip!
169  nassertr(vi == _verts.end(), prim);
170  nassertr(pi == _prims.end(), prim);
171  }
172 
173  return prim;
174 }
175 
176 ////////////////////////////////////////////////////////////////////
177 // Function: EggMesherStrip::measure_sheet
178 // Access: Public
179 // Description: Determines the extents of the quadsheet that can be
180 // derived by starting with this strip, and searching in
181 // the direction indicated by the given edge.
182 ////////////////////////////////////////////////////////////////////
183 void EggMesherStrip::
184 measure_sheet(const EggMesherEdge *edge, int new_row, int &num_prims,
185  int &num_rows, int first_row_id, int this_row_id,
186  int this_row_distance) {
187  if (new_row) {
188  // If we would create a new row by stepping here, we won't stay if
189  // there was any other row already defined here.
190  if (_row_id >= first_row_id) {
191  return;
192  }
193  } else {
194  // On the other hand, if this is a continuation of the current
195  // row, we'll stay if the other row had to travel farther to get
196  // here.
197  if (_row_id >= first_row_id && _row_distance <= this_row_distance) {
198  return;
199  }
200  }
201 
202  num_prims += _prims.size();
203  if (new_row) {
204  ++num_rows;
205  this_row_id = first_row_id + num_rows - 1;
206  }
207 
208  _row_id = this_row_id;
209 
210  Edges::iterator ei;
211  EggMesherEdge::Strips::iterator si;
212 
213  if (_type == PT_quad) {
214  // If this is a quad, it has four neighbors: two in the direction
215  // we are testing, and two in an orthagonal direction.
216 
217  int vi_a = edge->_vi_a;
218  int vi_b = edge->_vi_b;
219 
220  // We use these vertices to differentiate the edges that run in
221  // our primary direction from those in the secondary direction.
222  // For each edge, we count the number of vertices that the edge
223  // shares with our starting edge. There are then three cases:
224 
225  // (a) The edge shares two vertices. It is the direction we came
226  // from; forget it.
227 
228  // (b) The edge shares one vertex. It is at right angles to our
229  // starting edge. This is the primary direction if new_row is
230  // true, and the secondary direction if new_row is false.
231 
232  // (c) The edge shares no vertices. It is directly opposite our
233  // starting edge. This is the primary direction if new_row is
234  // false, and the secondary direction if new_row is true.
235 
236 
237  // Here's a silly little for loop that executes the following code
238  // twice: once with secondary == 0, and once with secondary == 1.
239  // This is because we want to find all the primary edges first,
240  // and then all the secondary edges.
241 
242  for (int secondary = 0; secondary <= 1; secondary++) {
243  // How many common vertices are we looking for this pass (see
244  // above)?
245 
246  int want_count;
247  if (secondary) {
248  want_count = new_row ? 0 : 1;
249  } else {
250  want_count = new_row ? 1 : 0;
251  }
252 
253  for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
254  int common_verts =
255  ((*ei)->_vi_a == vi_a || (*ei)->_vi_a == vi_b) +
256  ((*ei)->_vi_b == vi_a || (*ei)->_vi_b == vi_b);
257 
258  if (common_verts == want_count) {
259  // Here's the edge. Look at all its connections. Hopefully,
260  // there will only be one besides ourselves, but there may be
261  // more. Pick the best.
262 
263  EggMesherEdge::Strips &strips = (*ei)->_strips;
264  EggMesherStrip *mate = NULL;
265  for (si = strips.begin(); si != strips.end(); ++si) {
266  if ((*si)->_row_id < first_row_id) {
267  if (mate == NULL || pick_sheet_mate(**si, *mate)) {
268  mate = *si;
269  }
270  }
271  }
272  if (mate!=NULL) {
273  mate->measure_sheet(*ei, secondary, num_prims, num_rows,
274  first_row_id, this_row_id,
275  this_row_distance + secondary);
276  }
277  }
278  }
279  }
280 
281  } else {
282  // Otherwise, this is not a quad. It's certainly not a triangle,
283  // because we've built all the single triangles already.
284  nassertv(_type != PT_tri);
285 
286  // Therefore, it must be a tristrip or quadstrip.
287  nassertv(_type == PT_tristrip || _type == PT_quadstrip);
288 
289  // Since it's a strip, it only has two neighbors: the one we came
290  // from, and the other one. Find the other one.
291 
292  for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
293  if (!(*ei)->matches(*edge)) {
294  // Here's the edge. Same drill as above.
295 
296  EggMesherEdge::Strips &strips = (*ei)->_strips;
297  EggMesherStrip *mate = NULL;
298  for (si = strips.begin(); si != strips.end(); ++si) {
299  if ((*si)->_row_id < first_row_id) {
300  if (mate == NULL || pick_sheet_mate(**si, *mate)) {
301  mate = *si;
302  }
303  }
304  }
305  if (mate != NULL) {
306  mate->measure_sheet(*ei, false, num_prims, num_rows,
307  first_row_id, this_row_id, this_row_distance);
308  }
309  }
310  }
311  }
312 }
313 
314 
315 ////////////////////////////////////////////////////////////////////
316 // Function: EggMesherStrip::cut_sheet
317 // Access: Public
318 // Description:
319 ////////////////////////////////////////////////////////////////////
320 void EggMesherStrip::
321 cut_sheet(int first_row_id, int do_mate, const EggVertexPool *vertex_pool) {
322  Edges::iterator ei;
323  EggMesherEdge::Strips::iterator si;
324 
325  // First, start the process going on any neighbors that belong to a
326  // later row. (We must do these first, because we'll change our
327  // neighbor list when we start to mate.)
328 
329  // We need to build a temporary list of neighbors first, because
330  // calling cut_sheet() recursively will start things mating, and
331  // could damage our edge list.
332 
333  typedef plist<EggMesherStrip *> StripPtrs;
334  StripPtrs strip_ptrs;
335 
336  for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
337  EggMesherEdge::Strips &strips = (*ei)->_strips;
338  for (si = strips.begin(); si != strips.end(); ++si) {
339  if ((*si)->_row_id > _row_id) {
340  // Here's a different row in the sheet!
341  strip_ptrs.push_back(*si);
342  }
343  }
344  }
345 
346  // Now walk the temporary list and do some damage. We pass do_mate
347  // = true to each of these neighbors, because as far as we know,
348  // they're the first nodes of a particular row.
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);
353  }
354  }
355 
356 
357  if (do_mate && _status == MS_alive) {
358  // Now mate like a bunny until we don't have any more eligible mates.
359  int not_any;
360  do {
361  not_any = true;
362 
363  ei = _edges.begin();
364  while (not_any && ei != _edges.end()) {
365  EggMesherEdge::Strips &strips = (*ei)->_strips;
366  si = strips.begin();
367  while (not_any && si != strips.end()) {
368  if (*si != this && (*si)->_row_id == _row_id) {
369  // Here's one!
370  not_any = false;
371  EggMesherStrip *mate = *si;
372 
373  // We also recurse on these guys so they can spread the
374  // word to their own neighbors. This time we don't need
375  // to build a temporary list, because we'll be restarting
376  // from the beginning of our edge list after we do this.
377  // We also pass do_mate = false to these guys because
378  // we're the ones doing the mating here.
379  mate->cut_sheet(first_row_id, false, vertex_pool);
380 
381  if (_status == MS_alive && mate->_status == MS_alive) {
382  // Now mate. This will either succeed or fail. It ought
383  // to succeed, but if it doesn't, no harm done; it will
384  // simply remove the common edge and return. We'll go
385  // around again and not encounter this neighbor next time.
386  mate_pieces(*ei, *this, *mate, vertex_pool);
387  }
388  }
389  if (not_any) {
390  ++si;
391  }
392  }
393  if (not_any) {
394  ++ei;
395  }
396  }
397  } while (!not_any);
398 
399  // All done. Mark this one as down for the count.
400  _row_id = -first_row_id;
401  }
402 }
403 
404 
405 
406 
407 ////////////////////////////////////////////////////////////////////
408 // Function: EggMesherStrip::mate
409 // Access: Public
410 // Description: Finds a neighboring strip and joins up with it to
411 // make a larger strip. Returns true if mating was
412 // successful or at least possible, false if the strip
413 // has no neighbors.
414 ////////////////////////////////////////////////////////////////////
415 bool EggMesherStrip::
416 mate(const EggVertexPool *vertex_pool) {
417  // We must walk through the list of our neighbors and choose our
418  // best mate.
419  nassertr(_status == MS_alive, false);
420 
422  EggMesherEdge *common_edge;
423 
424  if (!find_ideal_mate(mate, common_edge, vertex_pool)) {
425  // We have no more eligible neighbors. Call us done.
426  _status = MS_done;
427 
428  return false;
429  }
430 
431  nassertr(!mate->_prims.empty(), false);
432  nassertr(!mate->_verts.empty(), false);
433 
434  mate_pieces(common_edge, *this, *mate, vertex_pool);
435 
436  // Whether the mate failed or not, the strip still (probably) has
437  // other neighbors to consider. Return true regardless.
438  return true;
439 }
440 
441 ////////////////////////////////////////////////////////////////////
442 // Function: EggMesherStrip::find_ideal_mate
443 // Access: Public
444 // Description: Searches our neighbors for the most suitable mate.
445 // Returns true if one is found, false if we have no
446 // neighbors.
447 ////////////////////////////////////////////////////////////////////
448 bool EggMesherStrip::
450  const EggVertexPool *vertex_pool) {
451  Edges::iterator ei;
452 
453  mate = NULL;
454  common_edge = NULL;
455 
456  for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
457  EggMesherEdge::Strips &strips = (*ei)->_strips;
458  EggMesherEdge::Strips::iterator si;
459  for (si = strips.begin(); si != strips.end(); ++si) {
460  if (*si != this) {
461  if (mate==NULL || pick_mate(**si, *mate, **ei, *common_edge,
462  vertex_pool)) {
463  mate = *si;
464  common_edge = *ei;
465  }
466  }
467  }
468  }
469 
470  return (mate!=NULL);
471 }
472 
473 
474 
475 
476 ////////////////////////////////////////////////////////////////////
477 // Function: EggMesherStrip::mate_pieces
478 // Access: Public, Static
479 // Description: Connects two pieces of arbitrary type, if possible.
480 // Returns true if successful, false if failure.
481 ////////////////////////////////////////////////////////////////////
482 bool EggMesherStrip::
484  EggMesherStrip &back, const EggVertexPool *vertex_pool) {
485  nassertr(front._status == MS_alive, false);
486  nassertr(back._status == MS_alive, false);
487  nassertr(&front != &back, false);
488 
489  bool success = true;
490  // remove_sides tracks whether we want to remove all but the leading
491  // edges of the newly joined piece if we succeed.
492  bool remove_sides = true;
493 
494  bool is_coplanar = front.is_coplanar_with(back, egg_coplanar_threshold);
495 
496  if (front._type == PT_tri && back._type == PT_tri) {
497 
498  if (is_coplanar && egg_retesselate_coplanar &&
499  front._prims.front() == back._prims.front() &&
500  convex_quad(common_edge, front, back, vertex_pool)) {
501 
502  // If we're joining two equivalent coplanar triangles, call it a
503  // quad.
504  front._type = PT_quad;
505 
506  // We add one additional vertex for the new triangle, the one
507  // vertex we didn't already share.
508  int new_vert = back.find_uncommon_vertex(common_edge);
509 
510  // Now we just need to find the right place to insert it. It
511  // belongs in the middle of the common edge, i.e. after the first
512  // vertex that is on the common edge and before the second vertex.
513  Verts::iterator a = front._verts.begin();
514  Verts::iterator b = a;
515  ++b;
516 
517  if (common_edge->contains_vertex(*a)) {
518  if (common_edge->contains_vertex(*b)) {
519  // It goes between a and b.
520  front._verts.insert(b, new_vert);
521  } else {
522  // It goes at the end.
523  front._verts.push_back(new_vert);
524  }
525  } else {
526  // It goes between b and c.
527  ++b;
528  front._verts.insert(b, new_vert);
529  }
530 
531  front._prims.splice(front._prims.end(), back._prims);
532  back._verts.clear();
533 
534  // We leave all four surrounding edges for now, since the quad
535  // might still be joined up in any direction.
536  remove_sides = false;
537 
538  } else {
539  // Otherwise, connect the two tris into a tristrip.
540  front._type = PT_tristrip;
541 
542  int new_vert = back.find_uncommon_vertex(common_edge);
543  front.rotate_to_back(common_edge);
544 
545  front._verts.push_back(new_vert);
546  front._prims.splice(front._prims.end(), back._prims);
547  back._verts.clear();
548  }
549 
550  } else if ((front._type == PT_quad || front._type == PT_quadstrip) &&
551  (back._type == PT_quad || back._type == PT_quadstrip)) {
552  // Joining two quads, two quadstrips, or a quad and a quadstrip.
553  // This makes another quadstrip.
554 
555  // We expect this to succeed every time with quadstrips.
556  success = mate_strips(common_edge, front, back, PT_quadstrip);
557 
558  if (!success) {
559  // Although it might fail in rare circumstances (specifically,
560  // if the two strips we attempted to join were backfacing to
561  // each other). If so, remove the adjoining edge so these two
562  // don't get tried again.
563  common_edge->remove(&front);
564  common_edge->remove(&back);
565  }
566 
567  } else {
568 
569  // Otherwise. This might be two tristrips, a quad and a tristrip,
570  // a triangle and a quad, a triangle and a tristrip, a triangle
571  // and a quadstrip, or a tristrip and a quadstrip. In any case,
572  // we'll end up with a tristrip.
573 
574  // This might fail if the tristrips don't match polarity.
575  success = mate_strips(common_edge, front, back, PT_tristrip);
576 
577  if (!success) {
578  // If it does fail, we'll try reversing the connection. This
579  // makes sense if we are joining a tri or tristrip to a quad or
580  // quadstrip, which might fail in one direction but succeed in
581  // the other.
582  success = mate_strips(common_edge, back, front, PT_tristrip);
583 
584  if (success) {
585  // Yay! Now return all the stuff to front.
586  front._verts.splice(front._verts.end(), back._verts);
587  front._prims.splice(front._prims.end(), back._prims);
588 
589  } else {
590  // A miserable failure. Never try to join these two again.
591  common_edge->remove(&front);
592  common_edge->remove(&back);
593  }
594  }
595  }
596 
597  if (success) {
598  front.combine_edges(back, remove_sides);
599  if (!remove_sides) {
600  // If we didn't want to remove the side edges, at least remove
601  // the join edge, which is now internal.
602  common_edge->remove(&front);
603  }
604 
605  nassertr(back._prims.empty(), false);
606  nassertr(back._verts.empty(), false);
607 
608  // Strip back is no more.
609  back._status = MS_dead;
610 
611  // The result is planar if and only if we joined two coplanar
612  // pieces.
613  front._planar = is_coplanar;
614  front._origin = MO_mate;
615  }
616 
617  return success;
618 }
619 
620 ////////////////////////////////////////////////////////////////////
621 // Function: EggMesherStrip::mate_strips
622 // Access: Public, Static
623 // Description: Stitches two strips together, producing in "front" a
624 // new strip of the indicated type (quadstrip or
625 // tristrip). The front strip stores the result, and
626 // the back strip is emptied on success.
627 //
628 // Returns true if successful, false if failure
629 // (generally because of incorrect polarity of
630 // tristrips), in which case nothing has changed (or at
631 // least, not much).
632 ////////////////////////////////////////////////////////////////////
633 bool EggMesherStrip::
635  EggMesherStrip &back, EggMesherStrip::PrimType type) {
636  // We don't allow making odd-length strips at all. Odd-length
637  // strips can't be rotated if they're flat-shaded, and they can't be
638  // joined end-to-end using degenerate triangles. So forget 'em.
639 
640  // This might not be the right place to impose this rule, because it
641  // tends to end up with lots of independent triangles in certain
642  // kinds of meshes, but it's the easiest place to impose it.
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)) {
647  return false;
648  }
649 
650  // If we start with a quad or tri, rotate the vertices around so we
651  // start with the common edge.
652  if (front._type == PT_tri || front._type == PT_quad) {
653  front.rotate_to_back(common_edge);
654  }
655  if (back._type == PT_tri || back._type == PT_quad) {
656  back.rotate_to_front(common_edge);
657  }
658 
659  bool reverse_front = common_edge->matches(front.get_head_edge());
660  bool reverse_back = !common_edge->matches(back.get_head_edge());
661 
662  bool invert_front = false;
663  bool invert_back = false;
664 
665  if (reverse_front && front.is_odd()) {
666  // If we're going to reverse the front strip, we have to be
667  // careful. This will also reverse the facing direction if it has
668  // an odd number of prims.
669  if (!front.can_invert()) {
670  return false;
671  }
672  invert_front = true;
673  }
674 
675  if (must_invert(front, back, reverse_back, type)) {
676  if (!back.can_invert()) {
677  return false;
678  }
679  invert_back = true;
680  back.invert();
681  }
682 
683  if (invert_front) {
684  front.invert();
685  }
686 
687  if (reverse_front) {
688  reverse(front._verts.begin(), front._verts.end());
689  reverse(front._prims.begin(), front._prims.end());
690  }
691 
692  if (reverse_back) {
693  reverse(back._verts.begin(), back._verts.end());
694  reverse(back._prims.begin(), back._prims.end());
695  }
696 
697  bool will_reverse = front.would_reverse_tail(type);
698  bool is_headtotail = (front.get_tail_edge() == back.get_head_edge());
699  if (will_reverse == is_headtotail) {
700  // Oops, we tried to join two backfacing strips. This really
701  // shouldn't happen, but it occasionally does for some mysterious
702  // reason. Maybe one day I'll understand why. In the meantime,
703  // just recover and carry on.
704  if (reverse_back) {
705  reverse(back._verts.begin(), back._verts.end());
706  reverse(back._prims.begin(), back._prims.end());
707  }
708  if (invert_back) {
709  back.invert();
710  }
711  if (reverse_front) {
712  reverse(front._verts.begin(), front._verts.end());
713  reverse(front._prims.begin(), front._prims.end());
714  }
715  if (invert_front) {
716  front.invert();
717  }
718  return false;
719  }
720 
721  front.convert_to_type(type);
722  back.convert_to_type(type);
723 
724  /*
725  if (! (front.get_tail_edge() == back.get_head_edge()) ) {
726  builder_cat.error()
727  << "\nFailure, trying to connect " << front
728  << "\nto " << back
729  << "\nreverse_front = " << reverse_front
730  << " reverse_back = " << reverse_back
731  << " invert_front = " << invert_front
732  << "\n";
733  Edges::iterator ei;
734 
735  nout << "\nFront edges:\n";
736  for (ei = front._edges.begin(); ei != front._edges.end(); ++ei) {
737  nout << **ei << "\n";
738  }
739 
740  nout << "\nBack edges:\n";
741  for (ei = back._edges.begin(); ei != back._edges.end(); ++ei) {
742  nout << **ei << "\n";
743  }
744  }
745  */
746 
747  // If this assertion fails, we were misinformed about our ability to
748  // join these two strips. Either the must_invert() call returned the
749  // incorrect value, or our edge-detection logic failed and we
750  // attempted to join two oppositely-facing strips.
751  //nassertr(front.get_tail_edge() == back.get_head_edge(), false);
752 
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);
757 
758  return true;
759 }
760 
761 ////////////////////////////////////////////////////////////////////
762 // Function: EggMesherStrip::must_invert
763 // Access: Public, Static
764 // Description: Returns false if the strips can be mated as they
765 // currently are. Returns true if the back strip must
766 // be inverted first.
767 ////////////////////////////////////////////////////////////////////
768 bool EggMesherStrip::
769 must_invert(const EggMesherStrip &front, const EggMesherStrip &back,
770  bool will_reverse_back, EggMesherStrip::PrimType type) {
771  bool invert = false;
772 
773  if ((front._type == PT_quad || front._type == PT_quadstrip) &&
774  type == PT_tristrip) {
775  // If we'll be converting from quads to tris, the tail edge of the
776  // front strip will always be even.
777 
778  } else if (front.is_odd()) {
779  // Otherwise, we have to flip if the tail edge is odd.
780  invert = !invert;
781  }
782 
783  if (will_reverse_back) {
784  // With the back strip, we don't care about what will happen to
785  // its tail edge when we convert it, but we do care what happens
786  // to its front edge if we reverse it.
787  if (back.is_odd()) {
788  // Specifically, the front edge will be reversed when the strip
789  // is reversed only if the strip is odd.
790  invert = !invert;
791  }
792  }
793 
794  return invert;
795 }
796 
797 ////////////////////////////////////////////////////////////////////
798 // Function: EggMesherStrip::convex_quad
799 // Access: Public, Static
800 // Description: Returns true if the quad that would be formed by
801 // connecting coplanar tris front and back along
802 // common_edge is convex, false otherwise.
803 ////////////////////////////////////////////////////////////////////
804 bool EggMesherStrip::
806  EggMesherStrip &back, const EggVertexPool *vertex_pool) {
807  // Find the edge from the apex of one triangle to the apex of the
808  // other. This is the "other" diagonal of the quad-to-be, other
809  // than the common_edge.
810  int vi_a = front.find_uncommon_vertex(common_edge);
811  int vi_b = back.find_uncommon_vertex(common_edge);
812  nassertr(vi_a >= 0 && vi_b >= 0, false);
813 
814  LPoint3d a3, b3, c3, d3;
815  a3 = vertex_pool->get_vertex(vi_a)->get_pos3();
816  b3 = vertex_pool->get_vertex(vi_b)->get_pos3();
817 
818  c3 = vertex_pool->get_vertex(common_edge->_vi_a)->get_pos3();
819  d3 = vertex_pool->get_vertex(common_edge->_vi_b)->get_pos3();
820 
821  // Project both edges into the 2-d axis plane most nearly
822  // perpendicular to the normal. We're assuming both tris have the
823  // same normal.
824 
825  nassertr(front._planar, false);
826 
827  LNormald n(front._plane_normal);
828  int xi, yi;
829 
830  // Find the largest dimension of the normal.
831  if (fabs(n[0]) > fabs(n[1])) {
832  if (fabs(n[0]) > fabs(n[2])) {
833  xi = 1;
834  yi = 2;
835  } else {
836  xi = 0;
837  yi = 1;
838  }
839  } else {
840  if (fabs(n[1]) > fabs(n[2])) {
841  xi = 0;
842  yi = 2;
843  } else {
844  xi = 0;
845  yi = 1;
846  }
847  }
848 
849  LVecBase2d a2, b2, c2, d2;
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]);
854 
855  // Now (c2-d2) is the common edge, and (a2-b2) is the new edge. The
856  // quad is convex iff (c2-d2) intersects (a2-b2). We actually only
857  // need to test whether (c2-d2) intersects the infinite line passing
858  // through (a2-b2).
859 
860  // The equation for the infinite line containing (a2-b2):
861  // Ax + By + C = 0
862  double A = (b2[1] - a2[1]);
863  double B = (a2[0] - b2[0]);
864  double C = -(A*b2[0] + B*b2[1]);
865 
866  // The parametric equations for the line segment (c2-d2):
867  // x = c2[0] + (d2[0]-c2[0])t
868  // y = c2[1] + (d2[1]-c2[1])t
869 
870  // Solved for t:
871  double t = - ((A*c2[0] + B*c2[1]) + C) / (A*(d2[0]-c2[0]) + B*(d2[1]-c2[1]));
872 
873  // Now the lines intersect if t is in [0, 1].
874  return (0.0 <= t && t <= 1.0);
875 }
876 
877 ////////////////////////////////////////////////////////////////////
878 // Function: EggMesherStrip::count_neighbors
879 // Access: Public
880 // Description: Returns the number of neighbors the strip shares.
881 ////////////////////////////////////////////////////////////////////
884  int count = 0;
885  Edges::const_iterator ei;
886 
887  for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
888  count += (*ei)->_strips.size();
889  }
890  return count;
891 }
892 
893 ////////////////////////////////////////////////////////////////////
894 // Function: EggMesherStrip::output_neighbors
895 // Access: Public
896 // Description: Writes all the neighbor indexes to the ostream.
897 ////////////////////////////////////////////////////////////////////
898 void EggMesherStrip::
899 output_neighbors(ostream &out) const {
900  Edges::const_iterator ei;
901  EggMesherEdge::Strips::const_iterator si;
902 
903  for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
904  for (si = (*ei)->_strips.begin();
905  si != (*ei)->_strips.end();
906  ++si) {
907  out << " " << (*si)->_index;
908  }
909  }
910 }
911 
912 ////////////////////////////////////////////////////////////////////
913 // Function: EggMesherStrip::find_uncommon_vertex
914 // Access: Public
915 // Description: Returns the first vertex found that is not shared by
916 // the given edge.
917 ////////////////////////////////////////////////////////////////////
920  int vi_a = edge->_vi_a;
921  int vi_b = edge->_vi_b;
922 
923  Edges::const_iterator ei;
924  for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
925  EggMesherEdge *e = (*ei);
926 
927  if (e->_vi_a != vi_a && e->_vi_a != vi_b) {
928  return e->_vi_a;
929  } else if (e->_vi_b != vi_a && e->_vi_b != vi_b) {
930  return e->_vi_b;
931  }
932  }
933 
934  return -1;
935 }
936 
937 ////////////////////////////////////////////////////////////////////
938 // Function: EggMesherStrip::find_opposite_edge
939 // Access: Public
940 // Description: Returns the first edge found that does not contain
941 // the given vertex. In a tri, this will be the edge
942 // opposite the given vertex.
943 ////////////////////////////////////////////////////////////////////
945 find_opposite_edge(int vi) const {
946  Edges::const_iterator ei;
947  for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
948  EggMesherEdge *e = (*ei);
949  if (!e->contains_vertex(vi)) {
950  return e;
951  }
952  }
953 
954  return NULL;
955 }
956 
957 ////////////////////////////////////////////////////////////////////
958 // Function: EggMesherStrip::find_opposite_edge
959 // Access: Public
960 // Description: Returns the first edge found that shares no vertices
961 // with the given edge. In a quad, this will be the
962 // edge opposite the given edge.
963 ////////////////////////////////////////////////////////////////////
965 find_opposite_edge(const EggMesherEdge *edge) const {
966  int vi_a = edge->_vi_a;
967  int vi_b = edge->_vi_b;
968 
969  Edges::const_iterator ei;
970  for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
971  EggMesherEdge *e = (*ei);
972  if (!e->contains_vertex(vi_a) && !e->contains_vertex(vi_b)) {
973  return e;
974  }
975  }
976 
977  return NULL;
978 }
979 
980 ////////////////////////////////////////////////////////////////////
981 // Function: EggMesherStrip::find_adjacent_edge
982 // Access: Public
983 // Description: Returns the first edge found that shares exactly one
984 // vertex with the given edge. In a quad, this will be
985 // one of two edges adjacent to the given edge.
986 ////////////////////////////////////////////////////////////////////
988 find_adjacent_edge(const EggMesherEdge *edge) const {
989  int vi_a = edge->_vi_a;
990  int vi_b = edge->_vi_b;
991 
992  Edges::const_iterator ei;
993  for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
994  EggMesherEdge *e = (*ei);
995  if (e->contains_vertex(vi_a) != e->contains_vertex(vi_b)) {
996  return e;
997  }
998  }
999 
1000  return NULL;
1001 }
1002 
1003 ////////////////////////////////////////////////////////////////////
1004 // Function: EggMesherStrip::rotate_to_front
1005 // Access: Public
1006 // Description: Rotates a triangle or quad so that the given edge is
1007 // first in the vertex list.
1008 ////////////////////////////////////////////////////////////////////
1009 void EggMesherStrip::
1011  int vi_a = edge->_vi_a;
1012  int vi_b = edge->_vi_b;
1013 
1014  // See if we're already there.
1015  if (_verts.front() == vi_a || _verts.front() == vi_b) {
1016  Verts::iterator vi = _verts.begin();
1017  ++vi;
1018  if (*vi == vi_a || *vi == vi_b) {
1019  // Yes!
1020  return;
1021  }
1022 
1023  // No, we must be right on the line. Roll back one.
1024  rotate_back();
1025 
1026  } else {
1027  // Roll forward until it comes into view.
1028  int num_verts = _verts.size();
1029  while (_verts.front() != vi_a && _verts.front() != vi_b) {
1030  // Make sure either vertex exists.
1031  num_verts--;
1032  nassertv(num_verts > 0);
1033  rotate_forward();
1034  }
1035  }
1036 
1037 #ifndef NDEBUG
1038  // Now make sure the edge actually exists.
1039  Verts::iterator vi = _verts.begin();
1040  ++vi;
1041  nassertv(*vi == vi_a || *vi == vi_b);
1042 #endif
1043 }
1044 
1045 ////////////////////////////////////////////////////////////////////
1046 // Function: EggMesherStrip::rotate_to_back
1047 // Access: Public
1048 // Description: Rotates a triangle or quad so that the given edge is
1049 // last in the vertex list.
1050 ////////////////////////////////////////////////////////////////////
1051 void EggMesherStrip::
1053  int vi_a = edge->_vi_a;
1054  int vi_b = edge->_vi_b;
1055 
1056  // See if we're already there.
1057  if (_verts.back() == vi_a || _verts.back() == vi_b) {
1058  Verts::reverse_iterator vi = _verts.rbegin();
1059  ++vi;
1060  if (*vi == vi_a || *vi == vi_b) {
1061  // Yes!
1062  return;
1063  }
1064 
1065  // No, we must be right on the line. Roll forward one.
1066  rotate_forward();
1067 
1068  } else {
1069  // Roll backward until it comes into view.
1070  int num_verts = _verts.size();
1071  while (_verts.back() != vi_a && _verts.back() != vi_b) {
1072  // Make sure either vertex exists.
1073  num_verts--;
1074  nassertv(num_verts > 0);
1075  rotate_back();
1076  }
1077  }
1078 
1079 #ifndef NDEBUG
1080  // Now make sure the edge actually exists.
1081  Verts::reverse_iterator vi = _verts.rbegin();
1082  ++vi;
1083  nassertv(*vi == vi_a || *vi == vi_b);
1084 #endif
1085 }
1086 
1087 
1088 ////////////////////////////////////////////////////////////////////
1089 // Function: EggMesherStrip::can_invert
1090 // Access: Public
1091 // Description: Returns true if the strip can be inverted (reverse
1092 // its facing direction). Generally, this is true for
1093 // quadstrips and false for tristrips.
1094 ////////////////////////////////////////////////////////////////////
1095 bool EggMesherStrip::
1096 can_invert() const {
1097  return (_type == PT_quadstrip || _type == PT_quad);
1098 }
1099 
1100 ////////////////////////////////////////////////////////////////////
1101 // Function: EggMesherStrip::invert
1102 // Access: Public
1103 // Description: Reverses the facing of a quadstrip by reversing pairs
1104 // of vertices. Returns true if successful, false if
1105 // failure (for instance, on a tristrip).
1106 ////////////////////////////////////////////////////////////////////
1107 bool EggMesherStrip::
1109  if (!can_invert()) {
1110  return false;
1111  }
1112  Verts::iterator vi, vi2;
1113  vi = _verts.begin();
1114  while (vi != _verts.end()) {
1115  vi2 = vi;
1116  ++vi2;
1117  nassertr(vi2 != _verts.end(), false);
1118 
1119  // Exchange vi and vi2
1120  int t = *vi2;
1121  *vi2 = *vi;
1122  *vi = t;
1123 
1124  // Increment
1125  vi = vi2;
1126  ++vi;
1127  }
1128  return true;
1129 }
1130 
1131 ////////////////////////////////////////////////////////////////////
1132 // Function: EggMesherStrip::is_odd
1133 // Access: Public
1134 // Description: Returns true if the tristrip or quadstrip contains an
1135 // odd number of pieces.
1136 ////////////////////////////////////////////////////////////////////
1137 bool EggMesherStrip::
1138 is_odd() const {
1139  if (_type == PT_quadstrip || _type == PT_quad) {
1140  // If a quadstrip has a multiple of four vertices, it has an
1141  // odd number of quads.
1142  return (_verts.size() % 4 == 0);
1143  } else {
1144  // If a tristrip has an odd number of vertices, it has an odd
1145  // number of tris.
1146  return (_verts.size() % 2 == 1);
1147  }
1148 }
1149 
1150 ////////////////////////////////////////////////////////////////////
1151 // Function: EggMesherStrip::would_reverse_tail
1152 // Access: Public
1153 // Description: Returns true if convert_to_type() would reverse the
1154 // tail edge of the given strip, false otherwise.
1155 ////////////////////////////////////////////////////////////////////
1156 bool EggMesherStrip::
1157 would_reverse_tail(EggMesherStrip::PrimType want_type) const {
1158  bool reverse = false;
1159 
1160  if (_type == want_type) {
1161  return false;
1162  }
1163  if (want_type == PT_tristrip) {
1164  switch (_type) {
1165  case PT_tri:
1166  case PT_tristrip:
1167  break;
1168 
1169  case PT_quad:
1170  case PT_quadstrip:
1171  // When we convert a quadstrip to a tristrip, we reverse the
1172  // tail edge if we have a multiple of four verts.
1173  reverse = (_verts.size() % 4 == 0);
1174  break;
1175 
1176  default:
1177  egg_cat.fatal() << "Invalid conversion!\n";
1178  abort();
1179  break;
1180  }
1181 
1182  } else if (want_type == PT_quadstrip) {
1183  switch (_type) {
1184  case PT_quad:
1185  case PT_quadstrip:
1186  break;
1187 
1188  case PT_tri:
1189  case PT_tristrip:
1190  // We don't convert tristrips to quadstrips; fall through.
1191 
1192  default:
1193  egg_cat.fatal() << "Invalid conversion!\n";
1194  abort();
1195  break;
1196  }
1197  }
1198 
1199  return reverse;
1200 }
1201 
1202 
1203 ////////////////////////////////////////////////////////////////////
1204 // Function: EggMesherStrip::convert_to_type
1205 // Access: Public
1206 // Description: Converts the EggMesherStrip from whatever form it
1207 // is--triangle, quad, or quadstrip--into a tristrip or
1208 // quadstrip.
1209 ////////////////////////////////////////////////////////////////////
1210 void EggMesherStrip::
1211 convert_to_type(EggMesherStrip::PrimType want_type) {
1212  Verts::iterator vi, vi2;
1213  int even;
1214 
1215  if (_type == want_type) {
1216  return;
1217  }
1218  if (want_type == PT_tristrip) {
1219  switch (_type) {
1220  case PT_tri:
1221  case PT_tristrip:
1222  break;
1223 
1224  case PT_quad:
1225  case PT_quadstrip:
1226  // To convert from quad/quadstrip to tristrip, we reverse every
1227  // other pair of vertices.
1228 
1229  vi = _verts.begin();
1230  even = 0;
1231  while (vi != _verts.end()) {
1232  vi2 = vi;
1233  ++vi2;
1234  nassertv(vi2 != _verts.end());
1235 
1236  // vi and vi2 are a pair. Should we reverse them?
1237  if (even) {
1238  int t = *vi2;
1239  *vi2 = *vi;
1240  *vi = t;
1241  }
1242 
1243  // Increment
1244  vi = vi2;
1245  ++vi;
1246  even = !even;
1247  }
1248  break;
1249 
1250  default:
1251  egg_cat.fatal() << "Invalid conversion!\n";
1252  abort();
1253  }
1254 
1255  } else if (want_type == PT_quadstrip) {
1256  switch (_type) {
1257  case PT_quad:
1258  case PT_quadstrip:
1259  break;
1260 
1261  case PT_tri:
1262  case PT_tristrip:
1263  // We don't convert tristrips to quadstrips; fall through.
1264 
1265  default:
1266  egg_cat.fatal() << "Invalid conversion!\n";
1267  abort();
1268  }
1269  }
1270 
1271  _type = want_type;
1272 }
1273 
1274 ////////////////////////////////////////////////////////////////////
1275 // Function: EggMesherStrip::combine_edges
1276 // Access: Public
1277 // Description: Removes the edges from the given strip and appends
1278 // them to our own. If remove_sides is true, then
1279 // removes all the edges except the head and the tail.
1280 ////////////////////////////////////////////////////////////////////
1281 void EggMesherStrip::
1282 combine_edges(EggMesherStrip &other, int remove_sides) {
1283  Edges::iterator ei;
1284  for (ei = other._edges.begin(); ei != other._edges.end(); ++ei) {
1285  (*ei)->change_strip(&other, this);
1286  }
1287 
1288  _edges.splice(_edges.end(), other._edges);
1289 
1290  if (remove_sides) {
1291  // Identify the head and tail edges so we can remove everything
1292  // else.
1293  EggMesherEdge head = get_head_edge();
1294  EggMesherEdge tail = get_tail_edge();
1295 
1296  if (!is_odd()) {
1297  // If the strip is odd, its true tail edge is the inverse of its
1298  // actual edge.
1299  tail = EggMesherEdge(tail._vi_b, tail._vi_a);
1300  }
1301 
1302  Edges junk_edges;
1303 
1304  Edges::iterator next_ei;
1305  ei = _edges.begin();
1306  while (ei != _edges.end()) {
1307  next_ei = ei;
1308  ++next_ei;
1309 
1310  // Is this edge to be saved or is it fodder?
1311  if (!(**ei == head) && !(**ei == tail)) {
1312  // Fodder! But we can't remove it right away, because this
1313  // will upset the current list; instead, we'll splice it to
1314  // junk_edges.
1315  junk_edges.splice(junk_edges.end(), _edges, ei);
1316  }
1317  ei = next_ei;
1318  }
1319 
1320  // Now we can safely remove all the to-be-junked edges.
1321  for (ei = junk_edges.begin(); ei != junk_edges.end(); ++ei) {
1322  (*ei)->remove(this);
1323  }
1324  }
1325 }
1326 
1327 
1328 ////////////////////////////////////////////////////////////////////
1329 // Function: EggMesherStrip::remove_all_edges
1330 // Access: Public
1331 // Description: Removes all active edges from the strip. This
1332 // effectively renders it ineligible to mate with
1333 // anything else.
1334 ////////////////////////////////////////////////////////////////////
1335 void EggMesherStrip::
1337  // First, move all the edges to a safe place so we can traverse the
1338  // list without it changing on us.
1339  Edges junk_edges;
1340  junk_edges.splice(junk_edges.end(), _edges);
1341 
1342  // Now we can safely remove all the to-be-junked edges.
1343  Edges::iterator ei;
1344  for (ei = junk_edges.begin(); ei != junk_edges.end(); ++ei) {
1345  (*ei)->remove(this);
1346  }
1347 }
1348 
1349 ////////////////////////////////////////////////////////////////////
1350 // Function: EggMesherStrip::pick_mate
1351 // Access: Public
1352 // Description: Defines an ordering to select neighbors to mate with.
1353 // This compares strip a with strip b and returns true
1354 // if strip a is the preferable choice, false if strip
1355 // b.
1356 ////////////////////////////////////////////////////////////////////
1357 bool EggMesherStrip::
1358 pick_mate(const EggMesherStrip &a_strip, const EggMesherStrip &b_strip,
1359  const EggMesherEdge &a_edge, const EggMesherEdge &b_edge,
1360  const EggVertexPool *vertex_pool) const {
1361  // First, try to avoid polluting quads, quadstrips, and tristrips
1362  // with arbitrary triangles. When we mate a tri or tristrip to a
1363  // quadstrip, we end up with a tristrip that may be less versatile
1364  // than the original quadstrip. Better to avoid this if we can.
1365  // Try to choose a mate that more closely matches our own type.
1366  int a_cat = a_strip.type_category();
1367  int b_cat = b_strip.type_category();
1368  if (a_cat != b_cat) {
1369  int me_cat = type_category();
1370  return abs(a_cat - me_cat) < abs(b_cat - me_cat);
1371  }
1372 
1373  // Now, if we're connecting two tris, try to connect them up so they
1374  // make good quads.
1375  if (_type == PT_tri && a_strip._type == PT_tri &&
1376  b_strip._type == PT_tri) {
1377 
1378  // This will depend on both coplanarity and edge length. We can't
1379  // use just one or the other, because some tris are nearly
1380  // isosceles, and some have more than one coplanar neighbor.
1381  // Hopefully the combination of both factors will zero us in on
1382  // the correct neighbor first.
1383 
1384  double a_coplanar = coplanarity(a_strip);
1385  double b_coplanar = coplanarity(b_strip);
1386  double coplanar_diff = a_coplanar - b_coplanar;
1387 
1388  double a_length = a_edge.compute_length(vertex_pool);
1389  double b_length = b_edge.compute_length(vertex_pool);
1390  double length_diff = (a_length - b_length) / (a_length + b_length);
1391 
1392  // These weights were chosen empirically to yield fairly good results.
1393  double sum = 4.0 * coplanar_diff - 1.0 * length_diff;
1394  return sum < 0;
1395  }
1396 
1397  // Then, get the smallest strip.
1398  if (a_strip._prims.size() != b_strip._prims.size()) {
1399  return a_strip._prims.size() < b_strip._prims.size();
1400  }
1401 
1402  // Finally, get the strip with the fewest neighbors.
1403  return a_strip.count_neighbors() < b_strip.count_neighbors();
1404 }
1405 
1406 ////////////////////////////////////////////////////////////////////
1407 // Function: EggMesherStrip::pick_sheet_mate
1408 // Access: Public
1409 // Description: Defines an ordering to select neighbors to follow
1410 // when measuring out a quadsheet. This is only called
1411 // when three or more prims share a single edge, which
1412 // should be rarely--generally only when coplanar polys
1413 // are going on.
1414 ////////////////////////////////////////////////////////////////////
1415 bool EggMesherStrip::
1417  const EggMesherStrip &b_strip) const {
1418  // First, try to get the poly which is closest to our own normal.
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));
1422 
1423  if (fabs(a_diff - b_diff) > 0.0001) {
1424  return a_diff > b_diff;
1425  }
1426  }
1427 
1428  // Then, pick the one that's most like our own type.
1429  int a_cat = a_strip.type_category();
1430  int b_cat = b_strip.type_category();
1431  if (a_cat != b_cat) {
1432  int me_cat = type_category();
1433  return abs(a_cat - me_cat) < abs(b_cat - me_cat);
1434  }
1435 
1436  // Oh, just pick any old one.
1437  return false;
1438 }
1439 
1440 ////////////////////////////////////////////////////////////////////
1441 // Function: EggMesherStrip::output
1442 // Access: Public
1443 // Description: Formats the vertex for output in some sensible way.
1444 ////////////////////////////////////////////////////////////////////
1445 void EggMesherStrip::
1446 output(ostream &out) const {
1447  switch (_status) {
1448  case MS_alive:
1449  break;
1450 
1451  case MS_dead:
1452  out << "Dead ";
1453  break;
1454 
1455  case MS_done:
1456  out << "Done ";
1457  break;
1458 
1459  default:
1460  out << "Unknown status ";
1461  }
1462 
1463  switch (_type) {
1464  case PT_tri:
1465  out << "Tri";
1466  break;
1467 
1468  case PT_quad:
1469  out << "Quad";
1470  break;
1471 
1472  case PT_tristrip:
1473  out << "TriStrip";
1474  break;
1475 
1476  case PT_trifan:
1477  out << "TriFan";
1478  break;
1479 
1480  case PT_quadstrip:
1481  out << "QuadStrip";
1482  break;
1483 
1484  default:
1485  out << "Unknown";
1486  }
1487 
1488  if (_planar) {
1489  out << " (planar)";
1490  }
1491 
1492  out << " " << _index << " [";
1493 
1494  Verts::const_iterator vi;
1495  for (vi = _verts.begin(); vi != _verts.end(); vi++) {
1496  out << " " << *vi;
1497  }
1498  out << " ]: " << _prims.size()
1499  << " prims, " << count_neighbors() << " neighbors";
1500 
1501  output_neighbors(out);
1502 
1503  out << " edges";
1504  Edges::const_iterator ei;
1505  for (ei = _edges.begin(); ei != _edges.end(); ei++) {
1506  out << " " << (void *)(*ei);
1507  }
1508 
1509  out << ".";
1510 }
1511 
A base class for any of a number of kinds of geometry primitives: polygons, point lights...
Definition: eggPrimitive.h:51
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.
Definition: lvecBase2.h:1257
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.
Definition: plist.h:38
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.
Definition: eggVertex.I:160
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...
Definition: eggAttributes.h:37
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...
Definition: eggMesherEdge.I:59
bool contains_vertex(int vi) const
Returns true if the edge contains the indicated vertex index, false otherwise.
Definition: eggMesherEdge.I:48
Any one-, two-, three-, or four-component vertex, possibly with attributes such as a normal...
Definition: eggVertex.h:41
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.
A single polygon.
Definition: eggPolygon.h:26
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...
Definition: eggMesherEdge.h:32
This is a three-component vector distance (as opposed to a three-component point, which represents a ...
Definition: lvector3.h:760
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 ...
Definition: lpoint3.h:544
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.
Definition: typedObject.I:63
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.
Definition: eggVertexPool.h:46
EggVertex * add_vertex(EggVertex *vertex)
Adds the indicated vertex to the end of the primitive&#39;s list of vertices, and returns it...
EggVertex * get_vertex(int index) const
Returns a particular index based on its index number.
Definition: eggPrimitive.I:466