Panda3D
 All Classes Functions Variables Enumerations
eggMesher.cxx
00001 // Filename: eggMesher.cxx
00002 // Created by:  drose (13Mar05)
00003 //
00004 ////////////////////////////////////////////////////////////////////
00005 //
00006 // PANDA 3D SOFTWARE
00007 // Copyright (c) Carnegie Mellon University.  All rights reserved.
00008 //
00009 // All use of this software is subject to the terms of the revised BSD
00010 // license.  You should have received a copy of this license along
00011 // with this source code in a file named "LICENSE."
00012 //
00013 ////////////////////////////////////////////////////////////////////
00014 
00015 #include "eggMesher.h"
00016 #include "eggMesherFanMaker.h"
00017 #include "eggPolygon.h"
00018 #include "eggCompositePrimitive.h"
00019 #include "eggTriangleStrip.h"
00020 #include "eggTriangleFan.h"
00021 #include "eggGroup.h"
00022 #include "config_egg.h"
00023 #include "eggGroupNode.h"
00024 #include "dcast.h"
00025 #include "thread.h"
00026 
00027 #include <stdlib.h>
00028 
00029 ////////////////////////////////////////////////////////////////////
00030 //     Function: EggMesher::Constructor
00031 //       Access: Public
00032 //  Description: 
00033 ////////////////////////////////////////////////////////////////////
00034 EggMesher::
00035 EggMesher() {
00036   _vertex_pool = NULL;
00037   _strip_index = 0;
00038 }
00039 
00040 ////////////////////////////////////////////////////////////////////
00041 //     Function: EggMesher::mesh
00042 //       Access: Public
00043 //  Description: Accepts an EggGroupNode, which contains a set of
00044 //               EggPrimitives--typically, triangles and quads--as
00045 //               children.  Removes these primitives and replaces them
00046 //               with (mostly) equivalent EggTriangleStrips and
00047 //               EggTriangleFans where possible.
00048 //
00049 //               If flat_shaded is true, then odd-length triangle
00050 //               strips, and triangle fans of any length, are not
00051 //               permitted (because these can't be rotated when
00052 //               required to move the colored vertex of each triangle
00053 //               to the first or last position).
00054 ////////////////////////////////////////////////////////////////////
00055 void EggMesher::
00056 mesh(EggGroupNode *group, bool flat_shaded) {
00057   _flat_shaded = flat_shaded;
00058 
00059   // Create a temporary node to hold the children of group that aren't
00060   // involved in the meshing, as well as the newly-generate triangle
00061   // strips.
00062   PT(EggGroupNode) output_children = new EggGroupNode;
00063 
00064   // And another to hold the children that will be processed next
00065   // time.
00066   PT(EggGroupNode) next_children = new EggGroupNode;
00067   PT(EggGroupNode) this_children = group;
00068 
00069   // Only primitives that share a common vertex pool can be meshed
00070   // together.  Thus, pull out the primitives with the same vertex
00071   // pool in groups.
00072   while (this_children->size() != 0) {
00073     clear();
00074 
00075     // Add each polygon in the group to the mesh pool.
00076     while (!this_children->empty()) {
00077       PT(EggNode) child = this_children->get_first_child();
00078       this_children->remove_child(child);
00079       
00080       if (child->is_of_type(EggPolygon::get_class_type())) {
00081         EggPolygon *poly = DCAST(EggPolygon, child);
00082 
00083         if (_vertex_pool == (EggVertexPool *)NULL) {
00084           _vertex_pool = poly->get_pool();
00085           add_polygon(poly, EggMesherStrip::MO_user);
00086 
00087         } else if (_vertex_pool == poly->get_pool()) {
00088           add_polygon(poly, EggMesherStrip::MO_user);
00089 
00090         } else {
00091           // A different vertex pool; save this one for the next pass.
00092           next_children->add_child(poly);
00093         }
00094 
00095       } else {
00096         // If it's not a polygon of any kind, just output it
00097         // unchanged.
00098         output_children->add_child(child);
00099       }
00100     }
00101     
00102     do_mesh();
00103     
00104     Strips::iterator si;
00105     for (si = _done.begin(); si != _done.end(); ++si) {
00106       PT(EggPrimitive) egg_prim = get_prim(*si);
00107       if (egg_prim != (EggPrimitive *)NULL) {
00108         output_children->add_child(egg_prim);
00109       }
00110     }
00111 
00112     this_children = next_children;
00113     next_children = new EggGroupNode;
00114   }
00115 
00116   // Now copy the newly-meshed primitives back to the group.
00117   group->clear();
00118   group->steal_children(*output_children);
00119 
00120   clear();
00121 }
00122 
00123 ////////////////////////////////////////////////////////////////////
00124 //     Function: EggMesher::write
00125 //       Access: Public
00126 //  Description: 
00127 ////////////////////////////////////////////////////////////////////
00128 void EggMesher::
00129 write(ostream &out) const {
00130   /*
00131   out << _edges.size() << " edges:\n";
00132   copy(_edges.begin(), _edges.end(), ostream_iterator<Edge>(out, "\n"));
00133   */
00134 
00135   out << _verts.size() << " verts:\n";
00136   Verts::const_iterator vi;
00137 
00138   for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
00139     int v = (*vi).first;
00140     const EdgePtrs &edges = (*vi).second;
00141     out << v << " shares " << count_vert_edges(edges) << " edges:\n";
00142     EdgePtrs::const_iterator ei;
00143     for (ei = edges.begin(); ei != edges.end(); ++ei) {
00144       if (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty()) {
00145         out << "  " << **ei << "\n";
00146       }
00147     }
00148   }
00149 
00150   Strips::const_iterator si;
00151   out << _tris.size() << " tris:\n";
00152   for (si = _tris.begin(); si != _tris.end(); ++si) {
00153     out << (*si) << "\n";
00154   }
00155 
00156   out << _quads.size() << " quads:\n";
00157   for (si = _quads.begin(); si != _quads.end(); ++si) {
00158     out << (*si) << "\n";
00159   }
00160 
00161   out << _strips.size() << " strips:\n";
00162   for (si = _strips.begin(); si != _strips.end(); ++si) {
00163     out << (*si) << "\n";
00164   }
00165 }
00166 
00167 ////////////////////////////////////////////////////////////////////
00168 //     Function: EggMesher::clear
00169 //       Access: Private
00170 //  Description: Empties the pool of meshable primitives and resets to
00171 //               an initial state.
00172 ////////////////////////////////////////////////////////////////////
00173 void EggMesher::
00174 clear() {
00175   _tris.clear();
00176   _quads.clear();
00177   _strips.clear();
00178   _dead.clear();
00179   _done.clear();
00180   _verts.clear();
00181   _edges.clear();
00182   _strip_index = 0;
00183   _vertex_pool = NULL;
00184   _color_sheets.clear();
00185 }
00186 
00187 ////////////////////////////////////////////////////////////////////
00188 //     Function: EggMesher::add_polygon
00189 //       Access: Private
00190 //  Description: Adds a single polygon into the pool of available
00191 //               primitives for meshing.
00192 ////////////////////////////////////////////////////////////////////
00193 bool EggMesher::
00194 add_polygon(const EggPolygon *egg_poly, EggMesherStrip::MesherOrigin origin) {
00195   CPT(EggPolygon) this_poly = egg_poly;
00196   if (this_poly->size() != 3) {
00197     // If we have a higher-order or concave polygon, triangulate it
00198     // automatically.
00199 
00200     // We'll keep quads, unless they're concave.
00201     bool convex_also = (this_poly->size() != 4);
00202 
00203     PT(EggGroupNode) temp_group = new EggGroupNode;
00204     bool result = this_poly->triangulate_into(temp_group, convex_also);
00205     EggGroupNode::iterator ci;
00206     if (temp_group->size() != 1) {
00207       for (ci = temp_group->begin(); ci != temp_group->end(); ++ci) {
00208         add_polygon(DCAST(EggPolygon, *ci), EggMesherStrip::MO_user);
00209       }
00210       return result;
00211     }
00212 
00213     // Convert just the one polygon we got out of the group.  Don't
00214     // recurse, since it might be the same polygon we sent in.
00215     ci = temp_group->begin();
00216     this_poly = DCAST(EggPolygon, *ci);
00217   }
00218 
00219   if (_vertex_pool == NULL) {
00220     _vertex_pool = this_poly->get_pool();
00221   } else {
00222     nassertr(_vertex_pool == this_poly->get_pool(), false);
00223   }
00224 
00225   // Define an initial strip (probably of length 1) for the prim.
00226   EggMesherStrip temp_strip(this_poly, _strip_index++, _vertex_pool, 
00227                             _flat_shaded);
00228   Strips &list = choose_strip_list(temp_strip);
00229   list.push_back(temp_strip);
00230   EggMesherStrip &strip = list.back();
00231   strip._origin = origin;
00232 
00233   int i;
00234   int num_verts = this_poly->size();
00235 
00236   int *vptrs = (int *)alloca(num_verts * sizeof(int));
00237   EdgePtrs **eptrs = (EdgePtrs **)alloca(num_verts * sizeof(EdgePtrs *));
00238 
00239   // Get the common vertex pointers for the primitive's vertices.
00240   for (i = 0; i < num_verts; i++) {
00241     Verts::value_type v(this_poly->get_vertex(i)->get_index(), EdgePtrs());
00242     Verts::iterator n = _verts.insert(v).first;
00243 
00244     vptrs[i] = (*n).first;
00245     eptrs[i] = &(*n).second;
00246 
00247     strip._verts.push_back(vptrs[i]);
00248   }
00249 
00250   // Now identify the common edges.
00251   for (i = 0; i < num_verts; i++) {
00252     // Define an inner and outer edge.  A polygon shares an edge with a
00253     // neighbor only when one of its inner edges matches a neighbor's
00254     // outer edge (and vice-versa).
00255     EggMesherEdge inner(vptrs[i], vptrs[(i+1) % num_verts]);
00256     EggMesherEdge outer(vptrs[(i+1) % num_verts], vptrs[i]);
00257     
00258     // Add it to the list and get its common pointer.
00259     EggMesherEdge &inner_ref = (EggMesherEdge &)*_edges.insert(inner).first;
00260     EggMesherEdge &outer_ref = (EggMesherEdge &)*_edges.insert(outer).first;
00261     
00262     // Tell the edges about each other.
00263     inner_ref._opposite = &outer_ref;
00264     outer_ref._opposite = &inner_ref;
00265     
00266     // Associate the common edge to the strip.
00267     strip._edges.push_back(&inner_ref);
00268     
00269     // Associate the strip, as well as the original prim, to the edge.
00270     outer_ref._strips.push_back(&strip);
00271     
00272     // Associate the common edge with the vertices that share it.
00273     //      EggMesherEdge *edge_ptr = inner_ref.common_ptr();
00274     eptrs[i]->insert(&outer_ref);
00275     eptrs[(i+1) % num_verts]->insert(&outer_ref);
00276   }
00277   
00278   return true;
00279 }
00280 
00281 ////////////////////////////////////////////////////////////////////
00282 //     Function: EggMesher::do_mesh
00283 //       Access: Private
00284 //  Description: Performs the meshing process on the set of primitives
00285 //               that have been added via add_prim(), leaving the
00286 //               result in _done.
00287 ////////////////////////////////////////////////////////////////////
00288 void EggMesher::
00289 do_mesh() {
00290   if (egg_consider_fans && !_flat_shaded) {
00291     find_fans();
00292   }
00293 
00294   // First, we try to make all the best quads we can.
00295   if (egg_retesselate_coplanar) {
00296     make_quads();
00297   }
00298 
00299   // Then, we do the rest of the tris.
00300   mesh_list(_tris);
00301 
00302   if (egg_show_quads) {
00303     // If we're showing quads, we shouldn't do any more meshing.
00304     Strips::iterator si;
00305     for (si = _quads.begin(); si != _quads.end(); ++si) {
00306       if ((*si)._status == EggMesherStrip::MS_alive) {
00307         (*si)._status = EggMesherStrip::MS_done;
00308       }
00309     }
00310     for (si = _strips.begin(); si != _strips.end(); ++si) {
00311       if ((*si)._status == EggMesherStrip::MS_alive) {
00312         (*si)._status = EggMesherStrip::MS_done;
00313       }
00314     }
00315   }
00316 
00317   // Then, build quads into sheets where possible.
00318   build_sheets();
00319 
00320   // Pick up any quads that might have been left behind.
00321   mesh_list(_quads);
00322 
00323   // Finally, do the longer strips.
00324   mesh_list(_strips);
00325 
00326   Thread::consider_yield();
00327 }
00328 
00329 ////////////////////////////////////////////////////////////////////
00330 //     Function: EggMesher::get_prim
00331 //       Access: Private
00332 //  Description: Creates an EggPrimitive that represents the result of
00333 //               the meshed EggMesherStrip object.
00334 ////////////////////////////////////////////////////////////////////
00335 PT(EggPrimitive) EggMesher::
00336 get_prim(EggMesherStrip &strip) {
00337   EggMesherStrip::PrimType orig_type = strip._type;
00338   PT(EggPrimitive) egg_prim = strip.make_prim(_vertex_pool);
00339 
00340   if (egg_show_tstrips) {
00341     // If we have egg_show_tstrips on, it means we need to color every
00342     // primitive according to which, if any, tristrip it is in.
00343 
00344     LColor color1, color2;
00345 
00346     if (egg_prim->is_of_type(EggTriangleStrip::get_class_type()) ||
00347         egg_prim->is_of_type(EggTriangleFan::get_class_type())) {
00348       make_random_color(color2);
00349       color1 = (color2 * 0.8);   // somewhat darker.
00350 
00351     } else {
00352       // not-a-tristrip.
00353       color1.set(0.85, 0.85, 0.85, 1.0);
00354       color2.set(0.85, 0.85, 0.85, 1.0);
00355     }
00356 
00357     // Now color1 and color2 indicate the color for the first triangle
00358     // and the rest of the primitive, respectively.
00359     if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
00360       EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
00361       int num_components = egg_comp->get_num_components();
00362       if (num_components > 0) {
00363         egg_comp->get_component(0)->set_color(color1);
00364         for (int i = 1; i < num_components; i++) {
00365           egg_comp->get_component(i)->set_color(color2);
00366         }
00367       }
00368     } else {
00369       egg_prim->set_color(color1);
00370     }
00371 
00372     int num_verts = egg_prim->size();
00373     for (int i = 0; i < num_verts; i++) {
00374       egg_prim->get_vertex(i)->clear_color();
00375     }
00376 
00377   } else if (egg_show_qsheets) {
00378     // egg_show_qsheets means to color every primitive according to
00379     // which, if any, quadsheet it is in.  This is a bit easier,
00380     // because the entire primitive gets the same color.
00381 
00382     // Is this a quadsheet?
00383     LColor color1;
00384     if (strip._row_id < 0) {
00385       // Yep!  Assign a new color, if it doesn't already have one.
00386       ColorSheetMap::iterator ci = _color_sheets.find(strip._row_id);
00387 
00388       if (ci == _color_sheets.end()) {
00389         make_random_color(color1);
00390         _color_sheets[strip._row_id] = color1;
00391       } else {
00392         color1 = (*ci).second;
00393       }
00394     }
00395 
00396     // Now color1 is the color we want to assign to the whole
00397     // primitive.
00398     egg_prim->set_color(color1);
00399     if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
00400       EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
00401       int num_components = egg_comp->get_num_components();
00402       for (int i = 0; i < num_components; i++) {
00403         egg_comp->get_component(i)->clear_color();
00404       }
00405     }
00406     int num_verts = egg_prim->size();
00407     for (int i = 0; i < num_verts; i++) {
00408       egg_prim->get_vertex(i)->clear_color();
00409     }
00410 
00411   } else if (egg_show_quads) {
00412     // egg_show_quads means to show the assembling of tris into quads
00413     // and fans.
00414 
00415     // We use the following color convention:
00416 
00417     // white: unchanged; as supplied by user.
00418     // dark blue: quads made in the initial pass.  These are more certain.
00419     // light blue: quads made in the second pass.  These are less certain.
00420     // very light blue: quadstrips.  These are unlikely to appear.
00421     // random shades of red: triangles and tristrips.
00422     // green: fans and retesselated fan polygons.
00423 
00424     // We need a handful of entries.
00425     LColor white(0.85, 0.85, 0.85, 1.0);
00426     LColor dark_blue(0.0, 0.0, 0.75, 1.0);
00427     LColor light_blue(0.4, 0.4, 0.8, 1.0);
00428     LColor very_light_blue(0.6, 0.6, 1.0, 1.0);
00429     LColor green(0.2, 0.8, 0.2, 1.0);
00430 
00431     LColor color1;
00432     if (strip._origin == EggMesherStrip::MO_user) {
00433       color1 = white;
00434     } else if (strip._origin == EggMesherStrip::MO_firstquad) {
00435       color1 = dark_blue;
00436     } else if (strip._origin == EggMesherStrip::MO_fanpoly) {
00437       color1 = green;
00438     } else {
00439       switch (orig_type) {
00440       case EggMesherStrip::PT_quad:
00441         color1 = light_blue;
00442         break;
00443 
00444       case EggMesherStrip::PT_quadstrip:
00445         color1 = very_light_blue;
00446         break;
00447 
00448       case EggMesherStrip::PT_tristrip:
00449         make_random_color(color1);
00450         // Make it a shade of red.
00451         if (color1[0] < color1[1]) {
00452           PN_stdfloat t = color1[0];
00453           color1[0] = color1[1];
00454           color1[1] = t;
00455         }
00456         color1[2] = color1[1];
00457         break;
00458 
00459       case EggMesherStrip::PT_trifan:
00460         make_random_color(color1);
00461         // Make it a shade of green.
00462         if (color1[0] > color1[1]) {
00463           PN_stdfloat t = color1[0];
00464           color1[0] = color1[1];
00465           color1[1] = t;
00466         }
00467         color1[2] = color1[0];
00468         break;
00469 
00470       default:
00471         color1 = white;
00472       }
00473     }
00474 
00475     // Now color1 is the color we want to assign to the whole
00476     // primitive.
00477     egg_prim->set_color(color1);
00478     if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
00479       EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
00480       int num_components = egg_comp->get_num_components();
00481       for (int i = 0; i < num_components; i++) {
00482         egg_comp->get_component(i)->clear_color();
00483       }
00484     }
00485     int num_verts = egg_prim->size();
00486     for (int i = 0; i < num_verts; i++) {
00487       egg_prim->get_vertex(i)->clear_color();
00488     }
00489   }
00490 
00491   return egg_prim;
00492 }
00493 
00494 ////////////////////////////////////////////////////////////////////
00495 //     Function: EggMesher::count_vert_edges
00496 //       Access: Private
00497 //  Description: Returns the number of edges in the list that are used
00498 //               by at least one EggMesherStrip object.
00499 ////////////////////////////////////////////////////////////////////
00500 int EggMesher::
00501 count_vert_edges(const EdgePtrs &edges) const {
00502   int count = 0;
00503   EdgePtrs::const_iterator ei;
00504   for (ei = edges.begin(); ei != edges.end(); ++ei) {
00505     count += (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty());
00506   }
00507   return count;
00508 }
00509 
00510 ////////////////////////////////////////////////////////////////////
00511 //     Function: EggMesher::choose_strip_list
00512 //       Access: Private
00513 //  Description: Selects which of several strip lists on the EggMesher
00514 //               class the indicated EggMesherStrip should be added
00515 //               to.
00516 ////////////////////////////////////////////////////////////////////
00517 plist<EggMesherStrip> &EggMesher::
00518 choose_strip_list(const EggMesherStrip &strip) {
00519   switch (strip._status) {
00520   case EggMesherStrip::MS_done:
00521     return _done;
00522 
00523   case EggMesherStrip::MS_dead:
00524     return _dead;
00525 
00526   case EggMesherStrip::MS_alive:
00527     switch (strip._type) {
00528     case EggMesherStrip::PT_tri:
00529       return _tris;
00530 
00531     case EggMesherStrip::PT_quad:
00532       return _quads;
00533 
00534     default:
00535       return _strips;
00536     }
00537 
00538   default:
00539     egg_cat.fatal() << "Invalid strip status!\n";
00540     abort();
00541   }
00542 
00543   return _strips; // Unreachable; this is just to make the compiler happy.
00544 }
00545 
00546 ////////////////////////////////////////////////////////////////////
00547 //     Function: EggMesher::build_sheets
00548 //       Access: Private
00549 //  Description: Attempts to locate large quadsheets in the polygon
00550 //               soup.  A quadsheet is defined as a uniform
00551 //               rectangular mesh of quads joined at the corners.
00552 //
00553 //               Sheets like this are commonly output by modeling
00554 //               packages, especially uniform tesselators, and they
00555 //               are trivially converted into a row of triangle
00556 //               strips.
00557 ////////////////////////////////////////////////////////////////////
00558 void EggMesher::
00559 build_sheets() {
00560   int first_row_id = 1;
00561 
00562   // First, move all the quads to our own internal list.
00563   Strips pre_sheeted;
00564   pre_sheeted.splice(pre_sheeted.end(), _quads);
00565 
00566   while (!pre_sheeted.empty()) {
00567     // Pick the first quad on the list.
00568 
00569     Strips::iterator best = pre_sheeted.begin();
00570 
00571     // If the row_id is negative, we've already built a sheet out of
00572     // this quad.  Leave it alone.  We also need to leave it be if it
00573     // has no available edges.
00574     if ((*best)._row_id >= 0 &&
00575         (*best)._status == EggMesherStrip::MS_alive &&
00576         !(*best)._edges.empty()) {
00577       // There are two possible sheets we could make from this quad,
00578       // in two different orientations.  Measure them both and figure
00579       // out which one is best.
00580 
00581       const EggMesherEdge *edge_a = (*best)._edges.front();
00582       const EggMesherEdge *edge_b = (*best).find_adjacent_edge(edge_a);
00583 
00584       int num_prims_a = 0;
00585       int num_rows_a = 0;
00586       int first_row_id_a = first_row_id;
00587       (*best).measure_sheet(edge_a, true, num_prims_a, num_rows_a,
00588                            first_row_id_a, 0, 0);
00589       first_row_id += num_rows_a;
00590       double avg_length_a = (double)num_prims_a / (double)num_rows_a;
00591 
00592       int num_prims_b = 0;
00593       int num_rows_b = 0;
00594       int first_row_id_b = first_row_id;
00595       double avg_length_b;
00596       if (edge_b != NULL) {
00597         (*best).measure_sheet(edge_b, true, num_prims_b, num_rows_b,
00598                              first_row_id_b, 0, 0);
00599         first_row_id += num_rows_b;
00600         avg_length_b = (double)num_prims_b / (double)num_rows_b;
00601       }
00602 
00603       // Which sheet is better?
00604       if (edge_b != NULL && avg_length_b >= avg_length_a) {
00605         // Sheet b.  That's easy.
00606         (*best).cut_sheet(first_row_id_b, true, _vertex_pool);
00607 
00608       } else {
00609         // Nope, sheet a is better.  This is a bit of a nuisance
00610         // because we've unfortunately wiped out the information we
00611         // stored when we measured sheet a.  We'll have to do it
00612         // again.
00613 
00614         num_prims_a = 0;
00615         num_rows_a = 0;
00616         first_row_id_a = first_row_id;
00617         (*best).measure_sheet(edge_a, true, num_prims_a, num_rows_a,
00618                              first_row_id_a, 0, 0);
00619         first_row_id += num_rows_a;
00620 
00621         // Now we can cut it.
00622         (*best).cut_sheet(first_row_id_a, true, _vertex_pool);
00623       }
00624     }
00625 
00626     // Now put it somewhere.  We'll never see this quad again in
00627     // build_sheets().
00628     Strips &list = choose_strip_list(*best);
00629     list.splice(list.end(), pre_sheeted, best);
00630   }
00631 }
00632 
00633 ////////////////////////////////////////////////////////////////////
00634 //     Function: EggMesher::find_fans
00635 //       Access: Private
00636 //  Description: Looks for cases of multiple polygons all sharing a
00637 //               common vertex, and replaces these with a single fan.
00638 //
00639 //               This step is performed before detecting triangle
00640 //               strips.  We have to be careful: if we are too
00641 //               aggressive in detecting fans, we may ruin the ability
00642 //               to build good triangle strips, and we may thereby end
00643 //               up with a less-than-optimal solution.
00644 ////////////////////////////////////////////////////////////////////
00645 void EggMesher::
00646 find_fans() {
00647   PT(EggGroupNode) unrolled_tris = new EggGroup;
00648 
00649   // Consider all vertices.  Any vertex with over a certain number of
00650   // edges connected to it is eligible to become a fan.
00651 
00652   Verts::iterator vi;
00653 
00654   for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
00655     EdgePtrs &edges = (*vi).second;
00656 
00657     // 14 is the magic number of edges.  12 edges or fewer are likely
00658     // to be found on nearly every vertex in a quadsheet (six edges
00659     // times two, one each way).  We don't want to waste time fanning
00660     // out each vertex of a quadsheet, and we don't want to break up
00661     // the quadsheets anyway.  We bump this up to 14 because some
00662     // quadsheets are defined with triangles flipped here and there.
00663     if (edges.size() > 6) {
00664       int v = (*vi).first;
00665 
00666       // Build up a list of far fan edges.
00667       typedef pvector<EggMesherFanMaker> FanMakers;
00668       FanMakers fans;
00669 
00670       EdgePtrs::iterator ei;
00671       EggMesherEdge::Strips::iterator si;
00672       for (ei = edges.begin(); ei != edges.end(); ++ei) {
00673         for (si = (*ei)->_strips.begin();
00674              si != (*ei)->_strips.end();
00675              ++si) {
00676           EggMesherStrip *strip = *si;
00677           if (strip->_type == EggMesherStrip::PT_tri) {
00678             EggMesherFanMaker fan(v, strip, this);
00679             if (!fan._edges.empty()) {
00680               fans.push_back(fan);
00681             }
00682           }
00683         }
00684       }
00685 
00686       // Sort the fans list by edge pointers, and remove duplicates.
00687       sort(fans.begin(), fans.end());
00688       fans.erase(unique(fans.begin(), fans.end()),
00689                  fans.end());
00690 
00691       FanMakers::iterator fi, fi2;
00692 
00693       // Now pull out connected edges.
00694       bool joined_any;
00695       do {
00696         joined_any = false;
00697         for (fi = fans.begin(); fi != fans.end(); ++fi) {
00698           if (!(*fi).is_empty()) {
00699             fi2 = fi;
00700             for (++fi2; fi2 != fans.end(); ++fi2) {
00701               if (!(*fi2).is_empty()) {
00702                 joined_any = (*fi).join(*fi2);
00703               }
00704             }
00705           }
00706         }
00707       } while (joined_any);
00708 
00709       for (fi = fans.begin(); fi != fans.end(); ++fi) {
00710         if ((*fi).is_valid()) {
00711           (*fi).build(unrolled_tris);
00712         }
00713       }
00714     }
00715   }
00716 
00717   // Finally, add back in the triangles we might have produced by
00718   // unrolling some of the fans.  We can't add these back in safely
00719   // until we're done traversing all the vertices and primitives we
00720   // had in the first place (since adding them will affect the edge
00721   // lists).
00722   EggGroupNode::iterator ti;
00723   for (ti = unrolled_tris->begin(); ti != unrolled_tris->end(); ++ti) {
00724     add_polygon(DCAST(EggPolygon, (*ti)), EggMesherStrip::MO_fanpoly);
00725   }
00726 }
00727 
00728 ////////////////////////////////////////////////////////////////////
00729 //     Function: EggMesher::make_quads
00730 //       Access: Private
00731 //  Description: Attempts to join up each single tri to its neighbor,
00732 //               to reconstruct a pattern of quads, suitable for
00733 //               making into quadsheets or at least quadstrips.
00734 //
00735 //               Quads have some nice properties that make them easy
00736 //               to manipulate when meshing.  We will ultimately
00737 //               convert the quadsheets and quadstrips into tristrips,
00738 //               but it's easier to work with them first while they're
00739 //               quads.
00740 ////////////////////////////////////////////////////////////////////
00741 void EggMesher::
00742 make_quads() {
00743   // Ideally, we want to match tris across their hypotenuse to make a
00744   // pattern of quads.  (This assumes that we are working with a
00745   // triangulated mesh pattern, of course.  If we have some other
00746   // pattern of tris, all bets are off and it doesn't really matter
00747   // anyway.)
00748 
00749   // First, we'll find all the tris that have no doubt about their
00750   // ideal mate, and pair them up right away.  The others we'll get to
00751   // later.  This way, the uncertain matches won't pollute the quad
00752   // alignment for everyone else.
00753 
00754   typedef pair<EggMesherStrip *, EggMesherStrip *> Pair;
00755   typedef pair<Pair, EggMesherEdge *> Matched;
00756   typedef pvector<Matched> SoulMates;
00757 
00758   SoulMates soulmates;
00759 
00760   EggMesherStrip *tri, *mate, *mate2;
00761   EggMesherEdge *common_edge, *common_edge2;
00762 
00763   Strips::iterator si;
00764   for (si = _tris.begin(); si != _tris.end(); ++si) {
00765     tri = &(*si);
00766 
00767     if (tri->_status == EggMesherStrip::MS_alive) {
00768       if (tri->find_ideal_mate(mate, common_edge, _vertex_pool)) {
00769         // Does our chosen mate want us too?
00770         if (mate->_type == EggMesherStrip::PT_tri && 
00771             mate->_status == EggMesherStrip::MS_alive &&
00772             mate->find_ideal_mate(mate2, common_edge2, _vertex_pool) &&
00773             mate2 == tri) {
00774           // Hooray!
00775           soulmates.push_back(Matched(Pair(tri, mate), common_edge));
00776           // We'll temporarily mark the two tris as paired.
00777           tri->_status = EggMesherStrip::MS_paired;
00778           mate->_status = EggMesherStrip::MS_paired;
00779         }
00780       }
00781     }
00782   }
00783 
00784   // Now that we've found all the tris that are sure about each other,
00785   // mate them.
00786   SoulMates::iterator mi;
00787   for (mi = soulmates.begin(); mi != soulmates.end(); ++mi) {
00788     tri = (*mi).first.first;
00789     mate = (*mi).first.second;
00790     common_edge = (*mi).second;
00791 
00792     nassertv(tri->_status == EggMesherStrip::MS_paired);
00793     nassertv(mate->_status == EggMesherStrip::MS_paired);
00794     tri->_status = EggMesherStrip::MS_alive;
00795     mate->_status = EggMesherStrip::MS_alive;
00796 
00797     EggMesherStrip::mate_pieces(common_edge, *tri, *mate, _vertex_pool);
00798     tri->_origin = EggMesherStrip::MO_firstquad;
00799   }
00800 
00801   // Now move all the strips off the tri list that no longer belong.
00802   Strips::iterator next;
00803   si = _tris.begin();
00804   while (si != _tris.end()) {
00805     next = si;
00806     ++next;
00807 
00808     Strips &list = choose_strip_list(*si);
00809     if (&list != &_tris) {
00810       list.splice(list.end(), _tris, si);
00811     }
00812 
00813     si = next;
00814   }
00815 }
00816 
00817 ////////////////////////////////////////////////////////////////////
00818 //     Function: EggMesher::mesh_list
00819 //       Access: Private
00820 //  Description: Processes all of the strips on the indicated list.
00821 ////////////////////////////////////////////////////////////////////
00822 void EggMesher::
00823 mesh_list(Strips &strips) {
00824   while (!strips.empty()) {
00825     // Pick the first strip on the list.
00826 
00827     Strips::iterator best = strips.begin();
00828 
00829     if ((*best)._status == EggMesherStrip::MS_alive) {
00830       (*best).mate(_vertex_pool);
00831     }
00832 
00833     // Put the strip back on the end of whichever list it wants.  This
00834     // might be the same list, if the strip is still alive, or it
00835     // might be _done or _dead.
00836     Strips &list = choose_strip_list(*best);
00837     list.splice(list.end(), strips, best);
00838   }
00839 }
00840 
00841 ////////////////////////////////////////////////////////////////////
00842 //     Function: EggMesher::make_random_color
00843 //       Access: Private, Static
00844 //  Description: Chooses a reasonable random color.
00845 ////////////////////////////////////////////////////////////////////
00846 void EggMesher::
00847 make_random_color(LColor &color) {
00848   LVector3 rgb;
00849   PN_stdfloat len;
00850   do {
00851     for (int i = 0; i < 3; i++) {
00852       rgb[i] = (double)rand() / (double)RAND_MAX;
00853     }
00854     len = length(rgb);
00855 
00856     // Repeat until we have a color that's not too dark or too light.
00857   } while (len < .1 || len > 1.5);
00858 
00859   color.set(rgb[0], rgb[1], rgb[2],
00860             0.25 + 0.75 * (double)rand() / (double)RAND_MAX);
00861 }
00862 
 All Classes Functions Variables Enumerations