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