Panda3D
eggMesher.cxx
1 // Filename: eggMesher.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 "eggMesher.h"
16 #include "eggMesherFanMaker.h"
17 #include "eggPolygon.h"
18 #include "eggCompositePrimitive.h"
19 #include "eggTriangleStrip.h"
20 #include "eggTriangleFan.h"
21 #include "eggGroup.h"
22 #include "config_egg.h"
23 #include "eggGroupNode.h"
24 #include "dcast.h"
25 #include "thread.h"
26 
27 #include <stdlib.h>
28 
29 ////////////////////////////////////////////////////////////////////
30 // Function: EggMesher::Constructor
31 // Access: Public
32 // Description:
33 ////////////////////////////////////////////////////////////////////
34 EggMesher::
35 EggMesher() {
36  _vertex_pool = NULL;
37  _strip_index = 0;
38 }
39 
40 ////////////////////////////////////////////////////////////////////
41 // Function: EggMesher::mesh
42 // Access: Public
43 // Description: Accepts an EggGroupNode, which contains a set of
44 // EggPrimitives--typically, triangles and quads--as
45 // children. Removes these primitives and replaces them
46 // with (mostly) equivalent EggTriangleStrips and
47 // EggTriangleFans where possible.
48 //
49 // If flat_shaded is true, then odd-length triangle
50 // strips, and triangle fans of any length, are not
51 // permitted (because these can't be rotated when
52 // required to move the colored vertex of each triangle
53 // to the first or last position).
54 ////////////////////////////////////////////////////////////////////
55 void EggMesher::
56 mesh(EggGroupNode *group, bool flat_shaded) {
57  _flat_shaded = flat_shaded;
58 
59  // Create a temporary node to hold the children of group that aren't
60  // involved in the meshing, as well as the newly-generate triangle
61  // strips.
62  PT(EggGroupNode) output_children = new EggGroupNode;
63 
64  // And another to hold the children that will be processed next
65  // time.
66  PT(EggGroupNode) next_children = new EggGroupNode;
67  PT(EggGroupNode) this_children = group;
68 
69  // Only primitives that share a common vertex pool can be meshed
70  // together. Thus, pull out the primitives with the same vertex
71  // pool in groups.
72  while (this_children->size() != 0) {
73  clear();
74 
75  // Add each polygon in the group to the mesh pool.
76  while (!this_children->empty()) {
77  PT(EggNode) child = this_children->get_first_child();
78  this_children->remove_child(child);
79 
80  if (child->is_of_type(EggPolygon::get_class_type())) {
81  EggPolygon *poly = DCAST(EggPolygon, child);
82 
83  if (_vertex_pool == (EggVertexPool *)NULL) {
84  _vertex_pool = poly->get_pool();
85  add_polygon(poly, EggMesherStrip::MO_user);
86 
87  } else if (_vertex_pool == poly->get_pool()) {
88  add_polygon(poly, EggMesherStrip::MO_user);
89 
90  } else {
91  // A different vertex pool; save this one for the next pass.
92  next_children->add_child(poly);
93  }
94 
95  } else {
96  // If it's not a polygon of any kind, just output it
97  // unchanged.
98  output_children->add_child(child);
99  }
100  }
101 
102  do_mesh();
103 
104  Strips::iterator si;
105  for (si = _done.begin(); si != _done.end(); ++si) {
106  PT(EggPrimitive) egg_prim = get_prim(*si);
107  if (egg_prim != (EggPrimitive *)NULL) {
108  output_children->add_child(egg_prim);
109  }
110  }
111 
112  this_children = next_children;
113  next_children = new EggGroupNode;
114  }
115 
116  // Now copy the newly-meshed primitives back to the group.
117  group->clear();
118  group->steal_children(*output_children);
119 
120  clear();
121 }
122 
123 ////////////////////////////////////////////////////////////////////
124 // Function: EggMesher::write
125 // Access: Public
126 // Description:
127 ////////////////////////////////////////////////////////////////////
128 void EggMesher::
129 write(ostream &out) const {
130  /*
131  out << _edges.size() << " edges:\n";
132  copy(_edges.begin(), _edges.end(), ostream_iterator<Edge>(out, "\n"));
133  */
134 
135  out << _verts.size() << " verts:\n";
136  Verts::const_iterator vi;
137 
138  for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
139  int v = (*vi).first;
140  const EdgePtrs &edges = (*vi).second;
141  out << v << " shares " << count_vert_edges(edges) << " edges:\n";
142  EdgePtrs::const_iterator ei;
143  for (ei = edges.begin(); ei != edges.end(); ++ei) {
144  if (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty()) {
145  out << " " << **ei << "\n";
146  }
147  }
148  }
149 
150  Strips::const_iterator si;
151  out << _tris.size() << " tris:\n";
152  for (si = _tris.begin(); si != _tris.end(); ++si) {
153  out << (*si) << "\n";
154  }
155 
156  out << _quads.size() << " quads:\n";
157  for (si = _quads.begin(); si != _quads.end(); ++si) {
158  out << (*si) << "\n";
159  }
160 
161  out << _strips.size() << " strips:\n";
162  for (si = _strips.begin(); si != _strips.end(); ++si) {
163  out << (*si) << "\n";
164  }
165 }
166 
167 ////////////////////////////////////////////////////////////////////
168 // Function: EggMesher::clear
169 // Access: Private
170 // Description: Empties the pool of meshable primitives and resets to
171 // an initial state.
172 ////////////////////////////////////////////////////////////////////
173 void EggMesher::
174 clear() {
175  _tris.clear();
176  _quads.clear();
177  _strips.clear();
178  _dead.clear();
179  _done.clear();
180  _verts.clear();
181  _edges.clear();
182  _strip_index = 0;
183  _vertex_pool = NULL;
184  _color_sheets.clear();
185 }
186 
187 ////////////////////////////////////////////////////////////////////
188 // Function: EggMesher::add_polygon
189 // Access: Private
190 // Description: Adds a single polygon into the pool of available
191 // primitives for meshing.
192 ////////////////////////////////////////////////////////////////////
193 bool EggMesher::
194 add_polygon(const EggPolygon *egg_poly, EggMesherStrip::MesherOrigin origin) {
195  CPT(EggPolygon) this_poly = egg_poly;
196  if (this_poly->size() != 3) {
197  // If we have a higher-order or concave polygon, triangulate it
198  // automatically.
199 
200  // We'll keep quads, unless they're concave.
201  bool convex_also = (this_poly->size() != 4);
202 
203  PT(EggGroupNode) temp_group = new EggGroupNode;
204  bool result = this_poly->triangulate_into(temp_group, convex_also);
205  EggGroupNode::iterator ci;
206  if (temp_group->size() != 1) {
207  for (ci = temp_group->begin(); ci != temp_group->end(); ++ci) {
208  add_polygon(DCAST(EggPolygon, *ci), EggMesherStrip::MO_user);
209  }
210  return result;
211  }
212 
213  // Convert just the one polygon we got out of the group. Don't
214  // recurse, since it might be the same polygon we sent in.
215  ci = temp_group->begin();
216  this_poly = DCAST(EggPolygon, *ci);
217  }
218 
219  if (_vertex_pool == NULL) {
220  _vertex_pool = this_poly->get_pool();
221  } else {
222  nassertr(_vertex_pool == this_poly->get_pool(), false);
223  }
224 
225  // Define an initial strip (probably of length 1) for the prim.
226  EggMesherStrip temp_strip(this_poly, _strip_index++, _vertex_pool,
227  _flat_shaded);
228  Strips &list = choose_strip_list(temp_strip);
229  list.push_back(temp_strip);
230  EggMesherStrip &strip = list.back();
231  strip._origin = origin;
232 
233  int i;
234  int num_verts = this_poly->size();
235 
236  int *vptrs = (int *)alloca(num_verts * sizeof(int));
237  EdgePtrs **eptrs = (EdgePtrs **)alloca(num_verts * sizeof(EdgePtrs *));
238 
239  // Get the common vertex pointers for the primitive's vertices.
240  for (i = 0; i < num_verts; i++) {
241  Verts::value_type v(this_poly->get_vertex(i)->get_index(), EdgePtrs());
242  Verts::iterator n = _verts.insert(v).first;
243 
244  vptrs[i] = (*n).first;
245  eptrs[i] = &(*n).second;
246 
247  strip._verts.push_back(vptrs[i]);
248  }
249 
250  // Now identify the common edges.
251  for (i = 0; i < num_verts; i++) {
252  // Define an inner and outer edge. A polygon shares an edge with a
253  // neighbor only when one of its inner edges matches a neighbor's
254  // outer edge (and vice-versa).
255  EggMesherEdge inner(vptrs[i], vptrs[(i+1) % num_verts]);
256  EggMesherEdge outer(vptrs[(i+1) % num_verts], vptrs[i]);
257 
258  // Add it to the list and get its common pointer.
259  EggMesherEdge &inner_ref = (EggMesherEdge &)*_edges.insert(inner).first;
260  EggMesherEdge &outer_ref = (EggMesherEdge &)*_edges.insert(outer).first;
261 
262  // Tell the edges about each other.
263  inner_ref._opposite = &outer_ref;
264  outer_ref._opposite = &inner_ref;
265 
266  // Associate the common edge to the strip.
267  strip._edges.push_back(&inner_ref);
268 
269  // Associate the strip, as well as the original prim, to the edge.
270  outer_ref._strips.push_back(&strip);
271 
272  // Associate the common edge with the vertices that share it.
273  // EggMesherEdge *edge_ptr = inner_ref.common_ptr();
274  eptrs[i]->insert(&outer_ref);
275  eptrs[(i+1) % num_verts]->insert(&outer_ref);
276  }
277 
278  return true;
279 }
280 
281 ////////////////////////////////////////////////////////////////////
282 // Function: EggMesher::do_mesh
283 // Access: Private
284 // Description: Performs the meshing process on the set of primitives
285 // that have been added via add_prim(), leaving the
286 // result in _done.
287 ////////////////////////////////////////////////////////////////////
288 void EggMesher::
289 do_mesh() {
290  if (egg_consider_fans && !_flat_shaded) {
291  find_fans();
292  }
293 
294  // First, we try to make all the best quads we can.
295  if (egg_retesselate_coplanar) {
296  make_quads();
297  }
298 
299  // Then, we do the rest of the tris.
300  mesh_list(_tris);
301 
302  if (egg_show_quads) {
303  // If we're showing quads, we shouldn't do any more meshing.
304  Strips::iterator si;
305  for (si = _quads.begin(); si != _quads.end(); ++si) {
306  if ((*si)._status == EggMesherStrip::MS_alive) {
307  (*si)._status = EggMesherStrip::MS_done;
308  }
309  }
310  for (si = _strips.begin(); si != _strips.end(); ++si) {
311  if ((*si)._status == EggMesherStrip::MS_alive) {
312  (*si)._status = EggMesherStrip::MS_done;
313  }
314  }
315  }
316 
317  // Then, build quads into sheets where possible.
318  build_sheets();
319 
320  // Pick up any quads that might have been left behind.
321  mesh_list(_quads);
322 
323  // Finally, do the longer strips.
324  mesh_list(_strips);
325 
327 }
328 
329 ////////////////////////////////////////////////////////////////////
330 // Function: EggMesher::get_prim
331 // Access: Private
332 // Description: Creates an EggPrimitive that represents the result of
333 // the meshed EggMesherStrip object.
334 ////////////////////////////////////////////////////////////////////
335 PT(EggPrimitive) EggMesher::
336 get_prim(EggMesherStrip &strip) {
337  EggMesherStrip::PrimType orig_type = strip._type;
338  PT(EggPrimitive) egg_prim = strip.make_prim(_vertex_pool);
339 
340  if (egg_show_tstrips) {
341  // If we have egg_show_tstrips on, it means we need to color every
342  // primitive according to which, if any, tristrip it is in.
343 
344  LColor color1, color2;
345 
346  if (egg_prim->is_of_type(EggTriangleStrip::get_class_type()) ||
347  egg_prim->is_of_type(EggTriangleFan::get_class_type())) {
348  make_random_color(color2);
349  color1 = (color2 * 0.8); // somewhat darker.
350 
351  } else {
352  // not-a-tristrip.
353  color1.set(0.85, 0.85, 0.85, 1.0);
354  color2.set(0.85, 0.85, 0.85, 1.0);
355  }
356 
357  // Now color1 and color2 indicate the color for the first triangle
358  // and the rest of the primitive, respectively.
359  if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
360  EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
361  int num_components = egg_comp->get_num_components();
362  if (num_components > 0) {
363  egg_comp->get_component(0)->set_color(color1);
364  for (int i = 1; i < num_components; i++) {
365  egg_comp->get_component(i)->set_color(color2);
366  }
367  }
368  } else {
369  egg_prim->set_color(color1);
370  }
371 
372  int num_verts = egg_prim->size();
373  for (int i = 0; i < num_verts; i++) {
374  egg_prim->get_vertex(i)->clear_color();
375  }
376 
377  } else if (egg_show_qsheets) {
378  // egg_show_qsheets means to color every primitive according to
379  // which, if any, quadsheet it is in. This is a bit easier,
380  // because the entire primitive gets the same color.
381 
382  // Is this a quadsheet?
383  LColor color1;
384  if (strip._row_id < 0) {
385  // Yep! Assign a new color, if it doesn't already have one.
386  ColorSheetMap::iterator ci = _color_sheets.find(strip._row_id);
387 
388  if (ci == _color_sheets.end()) {
389  make_random_color(color1);
390  _color_sheets[strip._row_id] = color1;
391  } else {
392  color1 = (*ci).second;
393  }
394  }
395 
396  // Now color1 is the color we want to assign to the whole
397  // primitive.
398  egg_prim->set_color(color1);
399  if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
400  EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
401  int num_components = egg_comp->get_num_components();
402  for (int i = 0; i < num_components; i++) {
403  egg_comp->get_component(i)->clear_color();
404  }
405  }
406  int num_verts = egg_prim->size();
407  for (int i = 0; i < num_verts; i++) {
408  egg_prim->get_vertex(i)->clear_color();
409  }
410 
411  } else if (egg_show_quads) {
412  // egg_show_quads means to show the assembling of tris into quads
413  // and fans.
414 
415  // We use the following color convention:
416 
417  // white: unchanged; as supplied by user.
418  // dark blue: quads made in the initial pass. These are more certain.
419  // light blue: quads made in the second pass. These are less certain.
420  // very light blue: quadstrips. These are unlikely to appear.
421  // random shades of red: triangles and tristrips.
422  // green: fans and retesselated fan polygons.
423 
424  // We need a handful of entries.
425  LColor white(0.85, 0.85, 0.85, 1.0);
426  LColor dark_blue(0.0, 0.0, 0.75, 1.0);
427  LColor light_blue(0.4, 0.4, 0.8, 1.0);
428  LColor very_light_blue(0.6, 0.6, 1.0, 1.0);
429  LColor green(0.2, 0.8, 0.2, 1.0);
430 
431  LColor color1;
432  if (strip._origin == EggMesherStrip::MO_user) {
433  color1 = white;
434  } else if (strip._origin == EggMesherStrip::MO_firstquad) {
435  color1 = dark_blue;
436  } else if (strip._origin == EggMesherStrip::MO_fanpoly) {
437  color1 = green;
438  } else {
439  switch (orig_type) {
440  case EggMesherStrip::PT_quad:
441  color1 = light_blue;
442  break;
443 
444  case EggMesherStrip::PT_quadstrip:
445  color1 = very_light_blue;
446  break;
447 
448  case EggMesherStrip::PT_tristrip:
449  make_random_color(color1);
450  // Make it a shade of red.
451  if (color1[0] < color1[1]) {
452  PN_stdfloat t = color1[0];
453  color1[0] = color1[1];
454  color1[1] = t;
455  }
456  color1[2] = color1[1];
457  break;
458 
459  case EggMesherStrip::PT_trifan:
460  make_random_color(color1);
461  // Make it a shade of green.
462  if (color1[0] > color1[1]) {
463  PN_stdfloat t = color1[0];
464  color1[0] = color1[1];
465  color1[1] = t;
466  }
467  color1[2] = color1[0];
468  break;
469 
470  default:
471  color1 = white;
472  }
473  }
474 
475  // Now color1 is the color we want to assign to the whole
476  // primitive.
477  egg_prim->set_color(color1);
478  if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
479  EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
480  int num_components = egg_comp->get_num_components();
481  for (int i = 0; i < num_components; i++) {
482  egg_comp->get_component(i)->clear_color();
483  }
484  }
485  int num_verts = egg_prim->size();
486  for (int i = 0; i < num_verts; i++) {
487  egg_prim->get_vertex(i)->clear_color();
488  }
489  }
490 
491  return egg_prim;
492 }
493 
494 ////////////////////////////////////////////////////////////////////
495 // Function: EggMesher::count_vert_edges
496 // Access: Private
497 // Description: Returns the number of edges in the list that are used
498 // by at least one EggMesherStrip object.
499 ////////////////////////////////////////////////////////////////////
500 int EggMesher::
501 count_vert_edges(const EdgePtrs &edges) const {
502  int count = 0;
503  EdgePtrs::const_iterator ei;
504  for (ei = edges.begin(); ei != edges.end(); ++ei) {
505  count += (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty());
506  }
507  return count;
508 }
509 
510 ////////////////////////////////////////////////////////////////////
511 // Function: EggMesher::choose_strip_list
512 // Access: Private
513 // Description: Selects which of several strip lists on the EggMesher
514 // class the indicated EggMesherStrip should be added
515 // to.
516 ////////////////////////////////////////////////////////////////////
517 plist<EggMesherStrip> &EggMesher::
518 choose_strip_list(const EggMesherStrip &strip) {
519  switch (strip._status) {
520  case EggMesherStrip::MS_done:
521  return _done;
522 
523  case EggMesherStrip::MS_dead:
524  return _dead;
525 
526  case EggMesherStrip::MS_alive:
527  switch (strip._type) {
528  case EggMesherStrip::PT_tri:
529  return _tris;
530 
531  case EggMesherStrip::PT_quad:
532  return _quads;
533 
534  default:
535  return _strips;
536  }
537 
538  default:
539  egg_cat.fatal() << "Invalid strip status!\n";
540  abort();
541  }
542 
543  return _strips; // Unreachable; this is just to make the compiler happy.
544 }
545 
546 ////////////////////////////////////////////////////////////////////
547 // Function: EggMesher::build_sheets
548 // Access: Private
549 // Description: Attempts to locate large quadsheets in the polygon
550 // soup. A quadsheet is defined as a uniform
551 // rectangular mesh of quads joined at the corners.
552 //
553 // Sheets like this are commonly output by modeling
554 // packages, especially uniform tesselators, and they
555 // are trivially converted into a row of triangle
556 // strips.
557 ////////////////////////////////////////////////////////////////////
558 void EggMesher::
559 build_sheets() {
560  int first_row_id = 1;
561 
562  // First, move all the quads to our own internal list.
563  Strips pre_sheeted;
564  pre_sheeted.splice(pre_sheeted.end(), _quads);
565 
566  while (!pre_sheeted.empty()) {
567  // Pick the first quad on the list.
568 
569  Strips::iterator best = pre_sheeted.begin();
570 
571  // If the row_id is negative, we've already built a sheet out of
572  // this quad. Leave it alone. We also need to leave it be if it
573  // has no available edges.
574  if ((*best)._row_id >= 0 &&
575  (*best)._status == EggMesherStrip::MS_alive &&
576  !(*best)._edges.empty()) {
577  // There are two possible sheets we could make from this quad,
578  // in two different orientations. Measure them both and figure
579  // out which one is best.
580 
581  const EggMesherEdge *edge_a = (*best)._edges.front();
582  const EggMesherEdge *edge_b = (*best).find_adjacent_edge(edge_a);
583 
584  int num_prims_a = 0;
585  int num_rows_a = 0;
586  int first_row_id_a = first_row_id;
587  (*best).measure_sheet(edge_a, true, num_prims_a, num_rows_a,
588  first_row_id_a, 0, 0);
589  first_row_id += num_rows_a;
590  double avg_length_a = (double)num_prims_a / (double)num_rows_a;
591 
592  int num_prims_b = 0;
593  int num_rows_b = 0;
594  int first_row_id_b = first_row_id;
595  double avg_length_b;
596  if (edge_b != NULL) {
597  (*best).measure_sheet(edge_b, true, num_prims_b, num_rows_b,
598  first_row_id_b, 0, 0);
599  first_row_id += num_rows_b;
600  avg_length_b = (double)num_prims_b / (double)num_rows_b;
601  }
602 
603  // Which sheet is better?
604  if (edge_b != NULL && avg_length_b >= avg_length_a) {
605  // Sheet b. That's easy.
606  (*best).cut_sheet(first_row_id_b, true, _vertex_pool);
607 
608  } else {
609  // Nope, sheet a is better. This is a bit of a nuisance
610  // because we've unfortunately wiped out the information we
611  // stored when we measured sheet a. We'll have to do it
612  // again.
613 
614  num_prims_a = 0;
615  num_rows_a = 0;
616  first_row_id_a = first_row_id;
617  (*best).measure_sheet(edge_a, true, num_prims_a, num_rows_a,
618  first_row_id_a, 0, 0);
619  first_row_id += num_rows_a;
620 
621  // Now we can cut it.
622  (*best).cut_sheet(first_row_id_a, true, _vertex_pool);
623  }
624  }
625 
626  // Now put it somewhere. We'll never see this quad again in
627  // build_sheets().
628  Strips &list = choose_strip_list(*best);
629  list.splice(list.end(), pre_sheeted, best);
630  }
631 }
632 
633 ////////////////////////////////////////////////////////////////////
634 // Function: EggMesher::find_fans
635 // Access: Private
636 // Description: Looks for cases of multiple polygons all sharing a
637 // common vertex, and replaces these with a single fan.
638 //
639 // This step is performed before detecting triangle
640 // strips. We have to be careful: if we are too
641 // aggressive in detecting fans, we may ruin the ability
642 // to build good triangle strips, and we may thereby end
643 // up with a less-than-optimal solution.
644 ////////////////////////////////////////////////////////////////////
645 void EggMesher::
646 find_fans() {
647  PT(EggGroupNode) unrolled_tris = new EggGroup;
648 
649  // Consider all vertices. Any vertex with over a certain number of
650  // edges connected to it is eligible to become a fan.
651 
652  Verts::iterator vi;
653 
654  for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
655  EdgePtrs &edges = (*vi).second;
656 
657  // 14 is the magic number of edges. 12 edges or fewer are likely
658  // to be found on nearly every vertex in a quadsheet (six edges
659  // times two, one each way). We don't want to waste time fanning
660  // out each vertex of a quadsheet, and we don't want to break up
661  // the quadsheets anyway. We bump this up to 14 because some
662  // quadsheets are defined with triangles flipped here and there.
663  if (edges.size() > 6) {
664  int v = (*vi).first;
665 
666  // Build up a list of far fan edges.
667  typedef pvector<EggMesherFanMaker> FanMakers;
668  FanMakers fans;
669 
670  EdgePtrs::iterator ei;
671  EggMesherEdge::Strips::iterator si;
672  for (ei = edges.begin(); ei != edges.end(); ++ei) {
673  for (si = (*ei)->_strips.begin();
674  si != (*ei)->_strips.end();
675  ++si) {
676  EggMesherStrip *strip = *si;
677  if (strip->_type == EggMesherStrip::PT_tri) {
678  EggMesherFanMaker fan(v, strip, this);
679  if (!fan._edges.empty()) {
680  fans.push_back(fan);
681  }
682  }
683  }
684  }
685 
686  // Sort the fans list by edge pointers, and remove duplicates.
687  sort(fans.begin(), fans.end());
688  fans.erase(unique(fans.begin(), fans.end()),
689  fans.end());
690 
691  FanMakers::iterator fi, fi2;
692 
693  // Now pull out connected edges.
694  bool joined_any;
695  do {
696  joined_any = false;
697  for (fi = fans.begin(); fi != fans.end(); ++fi) {
698  if (!(*fi).is_empty()) {
699  fi2 = fi;
700  for (++fi2; fi2 != fans.end(); ++fi2) {
701  if (!(*fi2).is_empty()) {
702  joined_any = (*fi).join(*fi2);
703  }
704  }
705  }
706  }
707  } while (joined_any);
708 
709  for (fi = fans.begin(); fi != fans.end(); ++fi) {
710  if ((*fi).is_valid()) {
711  (*fi).build(unrolled_tris);
712  }
713  }
714  }
715  }
716 
717  // Finally, add back in the triangles we might have produced by
718  // unrolling some of the fans. We can't add these back in safely
719  // until we're done traversing all the vertices and primitives we
720  // had in the first place (since adding them will affect the edge
721  // lists).
722  EggGroupNode::iterator ti;
723  for (ti = unrolled_tris->begin(); ti != unrolled_tris->end(); ++ti) {
724  add_polygon(DCAST(EggPolygon, (*ti)), EggMesherStrip::MO_fanpoly);
725  }
726 }
727 
728 ////////////////////////////////////////////////////////////////////
729 // Function: EggMesher::make_quads
730 // Access: Private
731 // Description: Attempts to join up each single tri to its neighbor,
732 // to reconstruct a pattern of quads, suitable for
733 // making into quadsheets or at least quadstrips.
734 //
735 // Quads have some nice properties that make them easy
736 // to manipulate when meshing. We will ultimately
737 // convert the quadsheets and quadstrips into tristrips,
738 // but it's easier to work with them first while they're
739 // quads.
740 ////////////////////////////////////////////////////////////////////
741 void EggMesher::
742 make_quads() {
743  // Ideally, we want to match tris across their hypotenuse to make a
744  // pattern of quads. (This assumes that we are working with a
745  // triangulated mesh pattern, of course. If we have some other
746  // pattern of tris, all bets are off and it doesn't really matter
747  // anyway.)
748 
749  // First, we'll find all the tris that have no doubt about their
750  // ideal mate, and pair them up right away. The others we'll get to
751  // later. This way, the uncertain matches won't pollute the quad
752  // alignment for everyone else.
753 
754  typedef pair<EggMesherStrip *, EggMesherStrip *> Pair;
755  typedef pair<Pair, EggMesherEdge *> Matched;
756  typedef pvector<Matched> SoulMates;
757 
758  SoulMates soulmates;
759 
760  EggMesherStrip *tri, *mate, *mate2;
761  EggMesherEdge *common_edge, *common_edge2;
762 
763  Strips::iterator si;
764  for (si = _tris.begin(); si != _tris.end(); ++si) {
765  tri = &(*si);
766 
767  if (tri->_status == EggMesherStrip::MS_alive) {
768  if (tri->find_ideal_mate(mate, common_edge, _vertex_pool)) {
769  // Does our chosen mate want us too?
770  if (mate->_type == EggMesherStrip::PT_tri &&
771  mate->_status == EggMesherStrip::MS_alive &&
772  mate->find_ideal_mate(mate2, common_edge2, _vertex_pool) &&
773  mate2 == tri) {
774  // Hooray!
775  soulmates.push_back(Matched(Pair(tri, mate), common_edge));
776  // We'll temporarily mark the two tris as paired.
777  tri->_status = EggMesherStrip::MS_paired;
778  mate->_status = EggMesherStrip::MS_paired;
779  }
780  }
781  }
782  }
783 
784  // Now that we've found all the tris that are sure about each other,
785  // mate them.
786  SoulMates::iterator mi;
787  for (mi = soulmates.begin(); mi != soulmates.end(); ++mi) {
788  tri = (*mi).first.first;
789  mate = (*mi).first.second;
790  common_edge = (*mi).second;
791 
792  nassertv(tri->_status == EggMesherStrip::MS_paired);
793  nassertv(mate->_status == EggMesherStrip::MS_paired);
794  tri->_status = EggMesherStrip::MS_alive;
795  mate->_status = EggMesherStrip::MS_alive;
796 
797  EggMesherStrip::mate_pieces(common_edge, *tri, *mate, _vertex_pool);
798  tri->_origin = EggMesherStrip::MO_firstquad;
799  }
800 
801  // Now move all the strips off the tri list that no longer belong.
802  Strips::iterator next;
803  si = _tris.begin();
804  while (si != _tris.end()) {
805  next = si;
806  ++next;
807 
808  Strips &list = choose_strip_list(*si);
809  if (&list != &_tris) {
810  list.splice(list.end(), _tris, si);
811  }
812 
813  si = next;
814  }
815 }
816 
817 ////////////////////////////////////////////////////////////////////
818 // Function: EggMesher::mesh_list
819 // Access: Private
820 // Description: Processes all of the strips on the indicated list.
821 ////////////////////////////////////////////////////////////////////
822 void EggMesher::
823 mesh_list(Strips &strips) {
824  while (!strips.empty()) {
825  // Pick the first strip on the list.
826 
827  Strips::iterator best = strips.begin();
828 
829  if ((*best)._status == EggMesherStrip::MS_alive) {
830  (*best).mate(_vertex_pool);
831  }
832 
833  // Put the strip back on the end of whichever list it wants. This
834  // might be the same list, if the strip is still alive, or it
835  // might be _done or _dead.
836  Strips &list = choose_strip_list(*best);
837  list.splice(list.end(), strips, best);
838  }
839 }
840 
841 ////////////////////////////////////////////////////////////////////
842 // Function: EggMesher::make_random_color
843 // Access: Private, Static
844 // Description: Chooses a reasonable random color.
845 ////////////////////////////////////////////////////////////////////
846 void EggMesher::
847 make_random_color(LColor &color) {
848  LVector3 rgb;
849  PN_stdfloat len;
850  do {
851  for (int i = 0; i < 3; i++) {
852  rgb[i] = (double)rand() / (double)RAND_MAX;
853  }
854  len = length(rgb);
855 
856  // Repeat until we have a color that's not too dark or too light.
857  } while (len < .1 || len > 1.5);
858 
859  color.set(rgb[0], rgb[1], rgb[2],
860  0.25 + 0.75 * (double)rand() / (double)RAND_MAX);
861 }
862 
A base class for any of a number of kinds of geometry primitives: polygons, point lights...
Definition: eggPrimitive.h:51
The base class for primitives such as triangle strips and triangle fans, which include several compon...
A base class for nodes in the hierarchy that are not leaf nodes.
Definition: eggGroupNode.h:51
const EggAttributes * get_component(int i) const
Returns the attributes for the nth component triangle.
This is a three-component vector distance (as opposed to a three-component point, which represents a ...
Definition: lvector3.h:100
static void consider_yield()
Possibly suspends the current thread for the rest of the current epoch, if it has run for enough this...
Definition: thread.I:263
This is our own Panda specialization on the default STL vector.
Definition: pvector.h:39
void mesh(EggGroupNode *group, bool flat_shaded)
Accepts an EggGroupNode, which contains a set of EggPrimitives–typically, triangles and quads–as ch...
Definition: eggMesher.cxx:56
The main glue of the egg hierarchy, this corresponds to the <Group>, <Instance>, and <Joint> type nod...
Definition: eggGroup.h:36
This class is used by EggMesher::find_fans() to attempt to make an EggTriangleFan out of the polygons...
void steal_children(EggGroupNode &other)
Moves all the children from the other node to this one.
int get_num_components() const
Returns the number of individual component triangles within the composite.
A single polygon.
Definition: eggPolygon.h:26
This is the base class for all three-component vectors and points.
Definition: lvecBase4.h:111
Represents one edge of a triangle, as used by the EggMesher to discover connected triangles...
Definition: eggMesherEdge.h:32
bool find_ideal_mate(EggMesherStrip *&mate, EggMesherEdge *&common_edge, const EggVertexPool *vertex_pool)
Searches our neighbors for the most suitable mate.
Represents a triangle strip or quad strip in progress, as assembled by the mesher.
A base class for things that may be directly added into the egg hierarchy.
Definition: eggNode.h:38
static bool mate_pieces(EggMesherEdge *common_edge, EggMesherStrip &front, EggMesherStrip &back, const EggVertexPool *vertex_pool)
Connects two pieces of arbitrary type, if possible.
This is our own Panda specialization on the default STL set.
Definition: pset.h:52
A collection of vertices.
Definition: eggVertexPool.h:46
EggVertexPool * get_pool() const
Returns the vertex pool associated with the vertices of the primitive, or NULL if the primitive has n...
Definition: eggPrimitive.I:480