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