Panda3D

eggMesherStrip.cxx

00001 // Filename: eggMesherStrip.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 "eggMesherStrip.h"
00016 #include "eggMesherEdge.h"
00017 #include "eggPrimitive.h"
00018 #include "eggTriangleFan.h"
00019 #include "eggTriangleStrip.h"
00020 #include "eggPolygon.h"
00021 #include "dcast.h"
00022 #include "config_egg.h"
00023 
00024 ////////////////////////////////////////////////////////////////////
00025 //     Function: EggMesherStrip::Constructor
00026 //       Access: Public
00027 //  Description:
00028 ////////////////////////////////////////////////////////////////////
00029 EggMesherStrip::
00030 EggMesherStrip(PrimType prim_type, MesherOrigin origin) {
00031   _origin = origin;
00032   _type = prim_type;
00033 
00034   _index = -1;
00035   _row_id = 0;
00036   _status = MS_alive;
00037   _planar = false;
00038   _flat_shaded = false;
00039 }
00040 
00041 ////////////////////////////////////////////////////////////////////
00042 //     Function: EggMesherStrip::Constructor
00043 //       Access: Public
00044 //  Description:
00045 ////////////////////////////////////////////////////////////////////
00046 EggMesherStrip::
00047 EggMesherStrip(const EggPrimitive *prim, int index, 
00048                const EggVertexPool *vertex_pool,
00049                bool flat_shaded) {
00050   _index = index;
00051   _row_id = 0;
00052   _status = MS_alive;
00053   _origin = MO_unknown;
00054   _flat_shaded = flat_shaded;
00055 
00056   _type = PT_poly; //prim.get_type();
00057 
00058   // We care only about the prim's attributes in the _prims array.
00059   // The vertices get re-added later by EggMesher::add_prim().
00060   _prims.push_back(prim);
00061 
00062   if (_type == PT_poly) {
00063     switch (prim->size()) {
00064     case 3:
00065       _type = PT_tri;
00066       break;
00067 
00068     case 4:
00069       _type = PT_quad;
00070       break;
00071     }
00072   }
00073 
00074   if (_type == PT_quad) {
00075     // A quad has two internal triangles; we therefore push the prim
00076     // attributes twice.
00077     _prims.push_back(prim);
00078   }
00079 
00080   _planar = false;
00081 
00082   if (prim->is_of_type(EggPolygon::get_class_type())) {
00083     // Although for the most part we ignore the actual value of the
00084     // vertices, we will ask the polygon for its plane equation
00085     // (i.e. its normal).
00086     if (DCAST(EggPolygon, prim)->calculate_normal(_plane_normal)) {
00087       _planar = true;
00088       LPoint3d p1 = prim->get_vertex(0)->get_pos3();
00089       _plane_offset = -dot(_plane_normal, p1);
00090     }
00091   }
00092 }
00093 
00094 
00095 ////////////////////////////////////////////////////////////////////
00096 //     Function: EggMesherStrip::make_prim
00097 //       Access: Public
00098 //  Description: Creates an EggPrimitive corresponding to the strip
00099 //               represented by this node.
00100 ////////////////////////////////////////////////////////////////////
00101 PT(EggPrimitive) EggMesherStrip::
00102 make_prim(const EggVertexPool *vertex_pool) {
00103   PT(EggPrimitive) prim;
00104   PrimType dest_type;
00105 
00106   switch (_type) {
00107   case PT_quad:
00108   case PT_tristrip:
00109   case PT_quadstrip:
00110     dest_type = PT_tristrip;
00111     break;
00112 
00113   case PT_trifan:
00114     dest_type = PT_trifan;
00115     break;
00116 
00117   default:
00118     dest_type = _type;
00119   }
00120 
00121   if (dest_type != PT_tristrip && dest_type != PT_trifan) {
00122     // The easy case: a simple primitive, i.e. a polygon.
00123     prim = new EggPolygon;
00124     prim->copy_attributes(*_prims.front());
00125 
00126     Verts::iterator vi;
00127     for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
00128       prim->add_vertex(vertex_pool->get_vertex(*vi));
00129     }
00130 
00131   } else {
00132     // The harder case: a tristrip of some kind.
00133     convert_to_type(dest_type);
00134     if (dest_type == PT_trifan) {
00135       prim = new EggTriangleFan;
00136     } else {
00137       prim = new EggTriangleStrip;
00138     }
00139     prim->copy_attributes(*_prims.front());
00140 
00141     // Now store all the vertices.  Each individual triangle's
00142     // attributes, if any, get applied to the third vertex of each
00143     // triangle.
00144     Verts::iterator vi;
00145     Prims::iterator pi;
00146     pi = _prims.begin();
00147     int count = 0;
00148     for (vi = _verts.begin();
00149          vi != _verts.end() && pi != _prims.end();
00150          ++vi) {
00151       PT(EggVertex) vertex = vertex_pool->get_vertex(*vi);
00152       prim->add_vertex(vertex);
00153       
00154       ++count;
00155       if (count >= 3) {
00156         // Beginning with the third vertex, we increment pi.  Thus, the
00157         // first two vertices stand alone, then each vertex beginning
00158         // with the third completes a triangle.
00159         const EggAttributes *attrib = (*pi);
00160         ++pi;
00161         DCAST(EggCompositePrimitive, prim)->set_component(count - 3, attrib);
00162       }
00163     }
00164 
00165     // If either of these fail, there weren't num_prims + 2 vertices in
00166     // the tristrip!
00167     nassertr(vi == _verts.end(), prim);
00168     nassertr(pi == _prims.end(), prim);
00169   }
00170 
00171   return prim;
00172 }
00173 
00174 ////////////////////////////////////////////////////////////////////
00175 //     Function: EggMesherStrip::measure_sheet
00176 //       Access: Public
00177 //  Description: Determines the extents of the quadsheet that can be
00178 //               derived by starting with this strip, and searching in
00179 //               the direction indicated by the given edge.
00180 ////////////////////////////////////////////////////////////////////
00181 void EggMesherStrip::
00182 measure_sheet(const EggMesherEdge *edge, int new_row, int &num_prims, 
00183               int &num_rows, int first_row_id, int this_row_id, 
00184               int this_row_distance) {
00185   if (new_row) {
00186     // If we would create a new row by stepping here, we won't stay if
00187     // there was any other row already defined here.
00188     if (_row_id >= first_row_id) {
00189       return;
00190     }
00191   } else {
00192     // On the other hand, if this is a continuation of the current
00193     // row, we'll stay if the other row had to travel farther to get
00194     // here.
00195     if (_row_id >= first_row_id && _row_distance <= this_row_distance) {
00196       return;
00197     }
00198   }
00199 
00200   num_prims += _prims.size();
00201   if (new_row) {
00202     ++num_rows;
00203     this_row_id = first_row_id + num_rows - 1;
00204   }
00205 
00206   _row_id = this_row_id;
00207 
00208   Edges::iterator ei;
00209   EggMesherEdge::Strips::iterator si;
00210 
00211   if (_type == PT_quad) {
00212     // If this is a quad, it has four neighbors: two in the direction
00213     // we are testing, and two in an orthagonal direction.
00214 
00215     int vi_a = edge->_vi_a;
00216     int vi_b = edge->_vi_b;
00217 
00218     // We use these vertices to differentiate the edges that run in
00219     // our primary direction from those in the secondary direction.
00220     // For each edge, we count the number of vertices that the edge
00221     // shares with our starting edge.  There are then three cases:
00222 
00223     // (a) The edge shares two vertices.  It is the direction we came
00224     // from; forget it.
00225 
00226     // (b) The edge shares one vertex.  It is at right angles to our
00227     // starting edge.  This is the primary direction if new_row is
00228     // true, and the secondary direction if new_row is false.
00229 
00230     // (c) The edge shares no vertices.  It is directly opposite our
00231     // starting edge.  This is the primary direction if new_row is
00232     // false, and the secondary direction if new_row is true.
00233 
00234 
00235     // Here's a silly little for loop that executes the following code
00236     // twice: once with secondary == 0, and once with secondary == 1.
00237     // This is because we want to find all the primary edges first,
00238     // and then all the secondary edges.
00239 
00240     for (int secondary = 0; secondary <= 1; secondary++) {
00241       // How many common vertices are we looking for this pass (see
00242       // above)?
00243 
00244       int want_count;
00245       if (secondary) {
00246         want_count = new_row ? 0 : 1;
00247       } else {
00248         want_count = new_row ? 1 : 0;
00249       }
00250 
00251       for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00252         int common_verts =
00253           ((*ei)->_vi_a == vi_a || (*ei)->_vi_a == vi_b) +
00254           ((*ei)->_vi_b == vi_a || (*ei)->_vi_b == vi_b);
00255 
00256         if (common_verts == want_count) {
00257           // Here's the edge.  Look at all its connections.  Hopefully,
00258           // there will only be one besides ourselves, but there may be
00259           // more.  Pick the best.
00260 
00261           EggMesherEdge::Strips &strips = (*ei)->_strips;
00262           EggMesherStrip *mate = NULL;
00263           for (si = strips.begin(); si != strips.end(); ++si) {
00264             if ((*si)->_row_id < first_row_id) {
00265               if (mate == NULL || pick_sheet_mate(**si, *mate)) {
00266                 mate = *si;
00267               }
00268             }
00269           }
00270           if (mate!=NULL) {
00271             mate->measure_sheet(*ei, secondary, num_prims, num_rows,
00272                                 first_row_id, this_row_id,
00273                                 this_row_distance + secondary);
00274           }
00275         }
00276       }
00277     }
00278 
00279   } else {
00280     // Otherwise, this is not a quad.  It's certainly not a triangle,
00281     // because we've built all the single triangles already.
00282     nassertv(_type != PT_tri);
00283 
00284     // Therefore, it must be a tristrip or quadstrip.
00285     nassertv(_type == PT_tristrip || _type == PT_quadstrip);
00286 
00287     // Since it's a strip, it only has two neighbors: the one we came
00288     // from, and the other one.  Find the other one.
00289 
00290     for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00291       if (!(*ei)->matches(*edge)) {
00292         // Here's the edge.  Same drill as above.
00293 
00294         EggMesherEdge::Strips &strips = (*ei)->_strips;
00295         EggMesherStrip *mate = NULL;
00296         for (si = strips.begin(); si != strips.end(); ++si) {
00297           if ((*si)->_row_id < first_row_id) {
00298             if (mate == NULL || pick_sheet_mate(**si, *mate)) {
00299               mate = *si;
00300             }
00301           }
00302         }
00303         if (mate != NULL) {
00304           mate->measure_sheet(*ei, false, num_prims, num_rows,
00305                               first_row_id, this_row_id, this_row_distance);
00306         }
00307       }
00308     }
00309   }
00310 }
00311 
00312 
00313 ////////////////////////////////////////////////////////////////////
00314 //     Function: EggMesherStrip::cut_sheet
00315 //       Access: Public
00316 //  Description:
00317 ////////////////////////////////////////////////////////////////////
00318 void EggMesherStrip::
00319 cut_sheet(int first_row_id, int do_mate, const EggVertexPool *vertex_pool) {
00320   Edges::iterator ei;
00321   EggMesherEdge::Strips::iterator si;
00322 
00323   // First, start the process going on any neighbors that belong to a
00324   // later row.  (We must do these first, because we'll change our
00325   // neighbor list when we start to mate.)
00326 
00327   // We need to build a temporary list of neighbors first, because
00328   // calling cut_sheet() recursively will start things mating, and
00329   // could damage our edge list.
00330 
00331   typedef plist<EggMesherStrip *> StripPtrs;
00332   StripPtrs strip_ptrs;
00333 
00334   for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00335     EggMesherEdge::Strips &strips = (*ei)->_strips;
00336     for (si = strips.begin(); si != strips.end(); ++si) {
00337       if ((*si)->_row_id > _row_id) {
00338         // Here's a different row in the sheet!
00339         strip_ptrs.push_back(*si);
00340       }
00341     }
00342   }
00343 
00344   // Now walk the temporary list and do some damage.  We pass do_mate
00345   // = true to each of these neighbors, because as far as we know,
00346   // they're the first nodes of a particular row.
00347   StripPtrs::iterator spi;
00348   for (spi = strip_ptrs.begin(); spi != strip_ptrs.end(); ++spi) {
00349     if ((*spi)->_status == MS_alive) {
00350       (*spi)->cut_sheet(first_row_id, true, vertex_pool);
00351     }
00352   }
00353 
00354 
00355   if (do_mate && _status == MS_alive) {
00356     // Now mate like a bunny until we don't have any more eligible mates.
00357     int not_any;
00358     do {
00359       not_any = true;
00360 
00361       ei = _edges.begin();
00362       while (not_any && ei != _edges.end()) {
00363         EggMesherEdge::Strips &strips = (*ei)->_strips;
00364         si = strips.begin();
00365         while (si != strips.end() && not_any) {
00366           if (*si != this && (*si)->_row_id == _row_id) {
00367             // Here's one!
00368             not_any = false;
00369             EggMesherStrip *mate = *si;
00370 
00371             // We also recurse on these guys so they can spread the
00372             // word to their own neighbors.  This time we don't need
00373             // to build a temporary list, because we'll be restarting
00374             // from the beginning of our edge list after we do this.
00375             // We also pass do_mate = false to these guys because
00376             // we're the ones doing the mating here.
00377             mate->cut_sheet(first_row_id, false, vertex_pool);
00378 
00379             if (_status == MS_alive && mate->_status == MS_alive) {
00380               // Now mate.  This will either succeed or fail.  It ought
00381               // to succeed, but if it doesn't, no harm done; it will
00382               // simply remove the common edge and return.  We'll go
00383               // around again and not encounter this neighbor next time.
00384               mate_pieces(*ei, *this, *mate, vertex_pool);
00385             }
00386           }
00387           if (not_any) {
00388             ++si;
00389           }
00390         }
00391         if (not_any) {
00392           ++ei;
00393         }
00394       }
00395     } while (!not_any);
00396 
00397     // All done.  Mark this one as down for the count.
00398     _row_id = -first_row_id;
00399   }
00400 }
00401 
00402 
00403 
00404 
00405 ////////////////////////////////////////////////////////////////////
00406 //     Function: EggMesherStrip::mate
00407 //       Access: Public
00408 //  Description: Finds a neighboring strip and joins up with it to
00409 //               make a larger strip.  Returns true if mating was
00410 //               successful or at least possible, false if the strip
00411 //               has no neighbors.
00412 ////////////////////////////////////////////////////////////////////
00413 bool EggMesherStrip::
00414 mate(const EggVertexPool *vertex_pool) {
00415   // We must walk through the list of our neighbors and choose our
00416   // best mate.
00417   nassertr(_status == MS_alive, false);
00418 
00419   EggMesherStrip *mate;
00420   EggMesherEdge *common_edge;
00421 
00422   if (!find_ideal_mate(mate, common_edge, vertex_pool)) {
00423     // We have no more eligible neighbors.  Call us done.
00424     _status = MS_done;
00425 
00426     return false;
00427   }
00428 
00429   nassertr(!mate->_prims.empty(), false);
00430   nassertr(!mate->_verts.empty(), false);
00431 
00432   mate_pieces(common_edge, *this, *mate, vertex_pool);
00433 
00434   // Whether the mate failed or not, the strip still (probably) has
00435   // other neighbors to consider.  Return true regardless.
00436   return true;
00437 }
00438 
00439 ////////////////////////////////////////////////////////////////////
00440 //     Function: EggMesherStrip::find_ideal_mate
00441 //       Access: Public
00442 //  Description: Searches our neighbors for the most suitable mate.
00443 //               Returns true if one is found, false if we have no
00444 //               neighbors.
00445 ////////////////////////////////////////////////////////////////////
00446 bool EggMesherStrip::
00447 find_ideal_mate(EggMesherStrip *&mate, EggMesherEdge *&common_edge,
00448                 const EggVertexPool *vertex_pool) {
00449   Edges::iterator ei;
00450 
00451   mate = NULL;
00452   common_edge = NULL;
00453 
00454   for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00455     EggMesherEdge::Strips &strips = (*ei)->_strips;
00456     EggMesherEdge::Strips::iterator si;
00457     for (si = strips.begin(); si != strips.end(); ++si) {
00458       if (*si != this) {
00459         if (mate==NULL || pick_mate(**si, *mate, **ei, *common_edge,
00460                                     vertex_pool)) {
00461           mate = *si;
00462           common_edge = *ei;
00463         }
00464       }
00465     }
00466   }
00467 
00468   return (mate!=NULL);
00469 }
00470 
00471 
00472 
00473 
00474 ////////////////////////////////////////////////////////////////////
00475 //     Function: EggMesherStrip::mate_pieces
00476 //       Access: Public, Static
00477 //  Description: Connects two pieces of arbitrary type, if possible.
00478 //               Returns true if successful, false if failure.
00479 ////////////////////////////////////////////////////////////////////
00480 bool EggMesherStrip::
00481 mate_pieces(EggMesherEdge *common_edge, EggMesherStrip &front, 
00482             EggMesherStrip &back, const EggVertexPool *vertex_pool) {
00483   nassertr(front._status == MS_alive, false);
00484   nassertr(back._status == MS_alive, false);
00485   nassertr(&front != &back, false);
00486 
00487   bool success = true;
00488   // remove_sides tracks whether we want to remove all but the leading
00489   // edges of the newly joined piece if we succeed.
00490   bool remove_sides = true;
00491 
00492   bool is_coplanar = front.is_coplanar_with(back, egg_coplanar_threshold);
00493 
00494   if (front._type == PT_tri && back._type == PT_tri) {
00495 
00496     if (is_coplanar && egg_retesselate_coplanar &&
00497         front._prims.front() == back._prims.front() &&
00498         convex_quad(common_edge, front, back, vertex_pool)) {
00499 
00500       // If we're joining two equivalent coplanar triangles, call it a
00501       // quad.
00502       front._type = PT_quad;
00503 
00504       // We add one additional vertex for the new triangle, the one
00505       // vertex we didn't already share.
00506       int new_vert = back.find_uncommon_vertex(common_edge);
00507 
00508       // Now we just need to find the right place to insert it.  It
00509       // belongs in the middle of the common edge, i.e. after the first
00510       // vertex that is on the common edge and before the second vertex.
00511       Verts::iterator a = front._verts.begin();
00512       Verts::iterator b = a;
00513       ++b;
00514 
00515       if (common_edge->contains_vertex(*a)) {
00516         if (common_edge->contains_vertex(*b)) {
00517           // It goes between a and b.
00518           front._verts.insert(b, new_vert);
00519         } else {
00520           // It goes at the end.
00521           front._verts.push_back(new_vert);
00522         }
00523       } else {
00524         // It goes between b and c.
00525         ++b;
00526         front._verts.insert(b, new_vert);
00527       }
00528 
00529       front._prims.splice(front._prims.end(), back._prims);
00530       back._verts.clear();
00531 
00532       // We leave all four surrounding edges for now, since the quad
00533       // might still be joined up in any direction.
00534       remove_sides = false;
00535 
00536     } else {
00537       // Otherwise, connect the two tris into a tristrip.
00538       front._type = PT_tristrip;
00539 
00540       int new_vert = back.find_uncommon_vertex(common_edge);
00541       front.rotate_to_back(common_edge);
00542 
00543       front._verts.push_back(new_vert);
00544       front._prims.splice(front._prims.end(), back._prims);
00545       back._verts.clear();
00546     }
00547 
00548   } else if ((front._type == PT_quad || front._type == PT_quadstrip) &&
00549              (back._type == PT_quad || back._type == PT_quadstrip)) {
00550     // Joining two quads, two quadstrips, or a quad and a quadstrip.
00551     // This makes another quadstrip.
00552 
00553     // We expect this to succeed every time with quadstrips.
00554     success = mate_strips(common_edge, front, back, PT_quadstrip);
00555 
00556     if (!success) {
00557       // Although it might fail in rare circumstances (specifically,
00558       // if the two strips we attempted to join were backfacing to
00559       // each other).  If so, remove the adjoining edge so these two
00560       // don't get tried again.
00561       common_edge->remove(&front);
00562       common_edge->remove(&back);
00563     }
00564 
00565   } else {
00566 
00567     // Otherwise.  This might be two tristrips, a quad and a tristrip,
00568     // a triangle and a quad, a triangle and a tristrip, a triangle
00569     // and a quadstrip, or a tristrip and a quadstrip.  In any case,
00570     // we'll end up with a tristrip.
00571 
00572     // This might fail if the tristrips don't match polarity.
00573     success = mate_strips(common_edge, front, back, PT_tristrip);
00574 
00575     if (!success) {
00576       // If it does fail, we'll try reversing the connection.  This
00577       // makes sense if we are joining a tri or tristrip to a quad or
00578       // quadstrip, which might fail in one direction but succeed in
00579       // the other.
00580       success = mate_strips(common_edge, back, front, PT_tristrip);
00581 
00582       if (success) {
00583         // Yay!  Now return all the stuff to front.
00584         front._verts.splice(front._verts.end(), back._verts);
00585         front._prims.splice(front._prims.end(), back._prims);
00586 
00587       } else {
00588         // A miserable failure.  Never try to join these two again.
00589         common_edge->remove(&front);
00590         common_edge->remove(&back);
00591       }
00592     }
00593   }
00594 
00595   if (success) {
00596     front.combine_edges(back, remove_sides);
00597     if (!remove_sides) {
00598       // If we didn't want to remove the side edges, at least remove
00599       // the join edge, which is now internal.
00600       common_edge->remove(&front);
00601     }
00602 
00603     nassertr(back._prims.empty(), false);
00604     nassertr(back._verts.empty(), false);
00605 
00606     // Strip back is no more.
00607     back._status = MS_dead;
00608 
00609     // The result is planar if and only if we joined two coplanar
00610     // pieces.
00611     front._planar = is_coplanar;
00612     front._origin = MO_mate;
00613   }
00614 
00615   return success;
00616 }
00617 
00618 ////////////////////////////////////////////////////////////////////
00619 //     Function: EggMesherStrip::mate_strips
00620 //       Access: Public, Static
00621 //  Description: Stitches two strips together, producing in "front" a
00622 //               new strip of the indicated type (quadstrip or
00623 //               tristrip).  The front strip stores the result, and
00624 //               the back strip is emptied on success.
00625 //
00626 //               Returns true if successful, false if failure
00627 //               (generally because of incorrect polarity of
00628 //               tristrips), in which case nothing has changed (or at
00629 //               least, not much).
00630 ////////////////////////////////////////////////////////////////////
00631 bool EggMesherStrip::
00632 mate_strips(EggMesherEdge *common_edge, EggMesherStrip &front, 
00633             EggMesherStrip &back, EggMesherStrip::PrimType type) {
00634   // We don't allow making odd-length strips at all.  Odd-length
00635   // strips can't be rotated if they're flat-shaded, and they can't be
00636   // joined end-to-end using degenerate triangles.  So forget 'em.
00637 
00638   // This might not be the right place to impose this rule, because it
00639   // tends to end up with lots of independent triangles in certain
00640   // kinds of meshes, but it's the easiest place to impose it.
00641   if ((front._type != PT_tri && back._type == PT_tri) ||
00642       (front._type == PT_tri && back._type != PT_tri) ||
00643       (front._type == PT_tristrip && back._type == PT_tristrip &&
00644        ((front._verts.size() + back._verts.size()) & 1) != 0)) {
00645     return false;
00646   }
00647 
00648   // If we start with a quad or tri, rotate the vertices around so we
00649   // start with the common edge.
00650   if (front._type == PT_tri || front._type == PT_quad) {
00651     front.rotate_to_back(common_edge);
00652   }
00653   if (back._type == PT_tri || back._type == PT_quad) {
00654     back.rotate_to_front(common_edge);
00655   }
00656 
00657   bool reverse_front = common_edge->matches(front.get_head_edge());
00658   bool reverse_back = !common_edge->matches(back.get_head_edge());
00659 
00660   bool invert_front = false;
00661   bool invert_back = false;
00662 
00663   if (reverse_front && front.is_odd()) {
00664     // If we're going to reverse the front strip, we have to be
00665     // careful.  This will also reverse the facing direction if it has
00666     // an odd number of prims.
00667     if (!front.can_invert()) {
00668       return false;
00669     }
00670     invert_front = true;
00671   }
00672 
00673   if (must_invert(front, back, reverse_back, type)) {
00674     if (!back.can_invert()) {
00675       return false;
00676     }
00677     invert_back = true;
00678     back.invert();
00679   }
00680 
00681   if (invert_front) {
00682     front.invert();
00683   }
00684 
00685   if (reverse_front) {
00686     reverse(front._verts.begin(), front._verts.end());
00687     reverse(front._prims.begin(), front._prims.end());
00688   }
00689 
00690   if (reverse_back) {
00691     reverse(back._verts.begin(), back._verts.end());
00692     reverse(back._prims.begin(), back._prims.end());
00693   }
00694 
00695   bool will_reverse = front.would_reverse_tail(type);
00696   bool is_headtotail = (front.get_tail_edge() == back.get_head_edge());
00697   if (will_reverse == is_headtotail) {
00698     // Oops, we tried to join two backfacing strips.  This really
00699     // shouldn't happen, but it occasionally does for some mysterious
00700     // reason.  Maybe one day I'll understand why.  In the meantime,
00701     // just recover and carry on.
00702     if (reverse_back) {
00703       reverse(back._verts.begin(), back._verts.end());
00704       reverse(back._prims.begin(), back._prims.end());
00705     }
00706     if (invert_back) {
00707       back.invert();
00708     }
00709     if (reverse_front) {
00710       reverse(front._verts.begin(), front._verts.end());
00711       reverse(front._prims.begin(), front._prims.end());
00712     }
00713     if (invert_front) {
00714       front.invert();
00715     }
00716     return false;
00717   }
00718 
00719   front.convert_to_type(type);
00720   back.convert_to_type(type);
00721 
00722   /*
00723   if (! (front.get_tail_edge() == back.get_head_edge()) ) {
00724     builder_cat.error()
00725          << "\nFailure, trying to connect " << front
00726          << "\nto " << back
00727          << "\nreverse_front = " << reverse_front
00728          << " reverse_back = " << reverse_back
00729          << " invert_front = " << invert_front
00730          << "\n";
00731     Edges::iterator ei;
00732 
00733     nout << "\nFront edges:\n";
00734     for (ei = front._edges.begin(); ei != front._edges.end(); ++ei) {
00735       nout << **ei << "\n";
00736     }
00737 
00738     nout << "\nBack edges:\n";
00739     for (ei = back._edges.begin(); ei != back._edges.end(); ++ei) {
00740       nout << **ei << "\n";
00741     }
00742   }
00743   */
00744 
00745   // If this assertion fails, we were misinformed about our ability to
00746   // join these two strips.  Either the must_invert() call returned the
00747   // incorrect value, or our edge-detection logic failed and we
00748   // attempted to join two oppositely-facing strips.
00749   //nassertr(front.get_tail_edge() == back.get_head_edge(), false);
00750 
00751   front._verts.pop_back();
00752   front._verts.pop_back();
00753   front._verts.splice(front._verts.end(), back._verts);
00754   front._prims.splice(front._prims.end(), back._prims);
00755 
00756   return true;
00757 }
00758 
00759 ////////////////////////////////////////////////////////////////////
00760 //     Function: EggMesherStrip::must_invert
00761 //       Access: Public, Static
00762 //  Description: Returns false if the strips can be mated as they
00763 //               currently are.  Returns true if the back strip must
00764 //               be inverted first.
00765 ////////////////////////////////////////////////////////////////////
00766 bool EggMesherStrip::
00767 must_invert(const EggMesherStrip &front, const EggMesherStrip &back,
00768             bool will_reverse_back, EggMesherStrip::PrimType type) {
00769   bool invert = false;
00770 
00771   if ((front._type == PT_quad || front._type == PT_quadstrip) &&
00772       type == PT_tristrip) {
00773     // If we'll be converting from quads to tris, the tail edge of the
00774     // front strip will always be even.
00775 
00776   } else if (front.is_odd()) {
00777     // Otherwise, we have to flip if the tail edge is odd.
00778     invert = !invert;
00779   }
00780 
00781   if (will_reverse_back) {
00782     // With the back strip, we don't care about what will happen to
00783     // its tail edge when we convert it, but we do care what happens
00784     // to its front edge if we reverse it.
00785     if (back.is_odd()) {
00786       // Specifically, the front edge will be reversed when the strip
00787       // is reversed only if the strip is odd.
00788       invert = !invert;
00789     }
00790   }
00791 
00792   return invert;
00793 }
00794 
00795 ////////////////////////////////////////////////////////////////////
00796 //     Function: EggMesherStrip::convex_quad
00797 //       Access: Public, Static
00798 //  Description: Returns true if the quad that would be formed by
00799 //               connecting coplanar tris front and back along
00800 //               common_edge is convex, false otherwise.
00801 ////////////////////////////////////////////////////////////////////
00802 bool EggMesherStrip::
00803 convex_quad(EggMesherEdge *common_edge, EggMesherStrip &front, 
00804             EggMesherStrip &back, const EggVertexPool *vertex_pool) {
00805   // Find the edge from the apex of one triangle to the apex of the
00806   // other.  This is the "other" diagonal of the quad-to-be, other
00807   // than the common_edge.
00808   int vi_a = front.find_uncommon_vertex(common_edge);
00809   int vi_b = back.find_uncommon_vertex(common_edge);
00810   nassertr(vi_a >= 0 && vi_b >= 0, false);
00811 
00812   LPoint3d a3, b3, c3, d3;
00813   a3 = vertex_pool->get_vertex(vi_a)->get_pos3();
00814   b3 = vertex_pool->get_vertex(vi_b)->get_pos3();
00815 
00816   c3 = vertex_pool->get_vertex(common_edge->_vi_a)->get_pos3();
00817   d3 = vertex_pool->get_vertex(common_edge->_vi_b)->get_pos3();
00818 
00819   // Project both edges into the 2-d axis plane most nearly
00820   // perpendicular to the normal.  We're assuming both tris have the
00821   // same normal.
00822 
00823   nassertr(front._planar, false);
00824 
00825   const Normald &n = front._plane_normal;
00826   int xi, yi;
00827 
00828   // Find the largest dimension of the normal.
00829   if (fabs(n[0]) > fabs(n[1])) {
00830     if (fabs(n[0]) > fabs(n[2])) {
00831       xi = 1;
00832       yi = 2;
00833     } else {
00834       xi = 0;
00835       yi = 1;
00836     }
00837   } else {
00838     if (fabs(n[1]) > fabs(n[2])) {
00839       xi = 0;
00840       yi = 2;
00841     } else {
00842       xi = 0;
00843       yi = 1;
00844     }
00845   }
00846 
00847   LVecBase2d a2, b2, c2, d2;
00848   a2.set(a3[xi], a3[yi]);
00849   b2.set(b3[xi], b3[yi]);
00850   c2.set(c3[xi], c3[yi]);
00851   d2.set(d3[xi], d3[yi]);
00852 
00853   // Now (c2-d2) is the common edge, and (a2-b2) is the new edge.  The
00854   // quad is convex iff (c2-d2) intersects (a2-b2).  We actually only
00855   // need to test whether (c2-d2) intersects the infinite line passing
00856   // through (a2-b2).
00857 
00858   // The equation for the infinite line containing (a2-b2):
00859   // Ax + By + C = 0
00860   double A = (b2[1] - a2[1]);
00861   double B = (a2[0] - b2[0]);
00862   double C = -(A*b2[0] + B*b2[1]);
00863 
00864   // The parametric equations for the line segment (c2-d2):
00865   // x = c2[0] + (d2[0]-c2[0])t
00866   // y = c2[1] + (d2[1]-c2[1])t
00867 
00868   // Solved for t:
00869   double t = - ((A*c2[0] + B*c2[1]) + C) / (A*(d2[0]-c2[0]) + B*(d2[1]-c2[1]));
00870 
00871   // Now the lines intersect if t is in [0, 1].
00872   return (0.0 <= t && t <= 1.0);
00873 }
00874 
00875 ////////////////////////////////////////////////////////////////////
00876 //     Function: EggMesherStrip::count_neighbors
00877 //       Access: Public
00878 //  Description: Returns the number of neighbors the strip shares.
00879 ////////////////////////////////////////////////////////////////////
00880 int EggMesherStrip::
00881 count_neighbors() const {
00882   int count = 0;
00883   Edges::const_iterator ei;
00884 
00885   for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00886     count += (*ei)->_strips.size();
00887   }
00888   return count;
00889 }
00890 
00891 ////////////////////////////////////////////////////////////////////
00892 //     Function: EggMesherStrip::output_neighbors
00893 //       Access: Public
00894 //  Description: Writes all the neighbor indexes to the ostream.
00895 ////////////////////////////////////////////////////////////////////
00896 void EggMesherStrip::
00897 output_neighbors(ostream &out) const {
00898   Edges::const_iterator ei;
00899   EggMesherEdge::Strips::const_iterator si;
00900 
00901   for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00902     for (si = (*ei)->_strips.begin();
00903          si != (*ei)->_strips.end();
00904          ++si) {
00905       out << " " << (*si)->_index;
00906     }
00907   }
00908 }
00909 
00910 ////////////////////////////////////////////////////////////////////
00911 //     Function: EggMesherStrip::find_uncommon_vertex
00912 //       Access: Public
00913 //  Description: Returns the first vertex found that is not shared by
00914 //               the given edge.
00915 ////////////////////////////////////////////////////////////////////
00916 int EggMesherStrip::
00917 find_uncommon_vertex(const EggMesherEdge *edge) const {
00918   int vi_a = edge->_vi_a;
00919   int vi_b = edge->_vi_b;
00920 
00921   Edges::const_iterator ei;
00922   for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00923     EggMesherEdge *e = (*ei);
00924 
00925     if (e->_vi_a != vi_a && e->_vi_a != vi_b) {
00926       return e->_vi_a;
00927     } else if (e->_vi_b != vi_a && e->_vi_b != vi_b) {
00928       return e->_vi_b;
00929     }
00930   }
00931 
00932   return -1;
00933 }
00934 
00935 ////////////////////////////////////////////////////////////////////
00936 //     Function: EggMesherStrip::find_opposite_edge
00937 //       Access: Public
00938 //  Description: Returns the first edge found that does not contain
00939 //               the given vertex.  In a tri, this will be the edge
00940 //               opposite the given vertex.
00941 ////////////////////////////////////////////////////////////////////
00942 const EggMesherEdge *EggMesherStrip::
00943 find_opposite_edge(int vi) const {
00944   Edges::const_iterator ei;
00945   for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00946     EggMesherEdge *e = (*ei);
00947     if (!e->contains_vertex(vi)) {
00948       return e;
00949     }
00950   }
00951 
00952   return NULL;
00953 }
00954 
00955 ////////////////////////////////////////////////////////////////////
00956 //     Function: EggMesherStrip::find_opposite_edge
00957 //       Access: Public
00958 //  Description: Returns the first edge found that shares no vertices
00959 //               with the given edge.  In a quad, this will be the
00960 //               edge opposite the given edge.
00961 ////////////////////////////////////////////////////////////////////
00962 const EggMesherEdge *EggMesherStrip::
00963 find_opposite_edge(const EggMesherEdge *edge) const {
00964   int vi_a = edge->_vi_a;
00965   int vi_b = edge->_vi_b;
00966 
00967   Edges::const_iterator ei;
00968   for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00969     EggMesherEdge *e = (*ei);
00970     if (!e->contains_vertex(vi_a) && !e->contains_vertex(vi_b)) {
00971       return e;
00972     }
00973   }
00974 
00975   return NULL;
00976 }
00977 
00978 ////////////////////////////////////////////////////////////////////
00979 //     Function: EggMesherStrip::find_adjacent_edge
00980 //       Access: Public
00981 //  Description: Returns the first edge found that shares exactly one
00982 //               vertex with the given edge.  In a quad, this will be
00983 //               one of two edges adjacent to the given edge.
00984 ////////////////////////////////////////////////////////////////////
00985 const EggMesherEdge *EggMesherStrip::
00986 find_adjacent_edge(const EggMesherEdge *edge) const {
00987   int vi_a = edge->_vi_a;
00988   int vi_b = edge->_vi_b;
00989 
00990   Edges::const_iterator ei;
00991   for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00992     EggMesherEdge *e = (*ei);
00993     if (e->contains_vertex(vi_a) != e->contains_vertex(vi_b)) {
00994       return e;
00995     }
00996   }
00997 
00998   return NULL;
00999 }
01000 
01001 ////////////////////////////////////////////////////////////////////
01002 //     Function: EggMesherStrip::rotate_to_front
01003 //       Access: Public
01004 //  Description: Rotates a triangle or quad so that the given edge is
01005 //               first in the vertex list.
01006 ////////////////////////////////////////////////////////////////////
01007 void EggMesherStrip::
01008 rotate_to_front(const EggMesherEdge *edge) {
01009   int vi_a = edge->_vi_a;
01010   int vi_b = edge->_vi_b;
01011 
01012   // See if we're already there.
01013   if (_verts.front() == vi_a || _verts.front() == vi_b) {
01014     Verts::iterator vi = _verts.begin();
01015     ++vi;
01016     if (*vi == vi_a || *vi == vi_b) {
01017       // Yes!
01018       return;
01019     }
01020 
01021     // No, we must be right on the line.  Roll back one.
01022     rotate_back();
01023 
01024   } else {
01025     // Roll forward until it comes into view.
01026     int num_verts = _verts.size();
01027     while (_verts.front() != vi_a && _verts.front() != vi_b) {
01028       // Make sure either vertex exists.
01029       num_verts--;
01030       nassertv(num_verts > 0);
01031       rotate_forward();
01032     }
01033   }
01034 
01035 #ifndef NDEBUG
01036   // Now make sure the edge actually exists.
01037   Verts::iterator vi = _verts.begin();
01038   ++vi;
01039   nassertv(*vi == vi_a || *vi == vi_b);
01040 #endif
01041 }
01042 
01043 ////////////////////////////////////////////////////////////////////
01044 //     Function: EggMesherStrip::rotate_to_back
01045 //       Access: Public
01046 //  Description: Rotates a triangle or quad so that the given edge is
01047 //               last in the vertex list.
01048 ////////////////////////////////////////////////////////////////////
01049 void EggMesherStrip::
01050 rotate_to_back(const EggMesherEdge *edge) {
01051   int vi_a = edge->_vi_a;
01052   int vi_b = edge->_vi_b;
01053 
01054   // See if we're already there.
01055   if (_verts.back() == vi_a || _verts.back() == vi_b) {
01056     Verts::reverse_iterator vi = _verts.rbegin();
01057     ++vi;
01058     if (*vi == vi_a || *vi == vi_b) {
01059       // Yes!
01060       return;
01061     }
01062 
01063     // No, we must be right on the line.  Roll forward one.
01064     rotate_forward();
01065 
01066   } else {
01067     // Roll backward until it comes into view.
01068     int num_verts = _verts.size();
01069     while (_verts.back() != vi_a && _verts.back() != vi_b) {
01070       // Make sure either vertex exists.
01071       num_verts--;
01072       nassertv(num_verts > 0);
01073       rotate_back();
01074     }
01075   }
01076 
01077 #ifndef NDEBUG
01078   // Now make sure the edge actually exists.
01079   Verts::reverse_iterator vi = _verts.rbegin();
01080   ++vi;
01081   nassertv(*vi == vi_a || *vi == vi_b);
01082 #endif
01083 }
01084 
01085 
01086 ////////////////////////////////////////////////////////////////////
01087 //     Function: EggMesherStrip::can_invert
01088 //       Access: Public
01089 //  Description: Returns true if the strip can be inverted (reverse
01090 //               its facing direction).  Generally, this is true for
01091 //               quadstrips and false for tristrips.
01092 ////////////////////////////////////////////////////////////////////
01093 bool EggMesherStrip::
01094 can_invert() const {
01095   return (_type == PT_quadstrip || _type == PT_quad);
01096 }
01097 
01098 ////////////////////////////////////////////////////////////////////
01099 //     Function: EggMesherStrip::invert
01100 //       Access: Public
01101 //  Description: Reverses the facing of a quadstrip by reversing pairs
01102 //               of vertices.  Returns true if successful, false if
01103 //               failure (for instance, on a tristrip).
01104 ////////////////////////////////////////////////////////////////////
01105 bool EggMesherStrip::
01106 invert() {
01107   if (!can_invert()) {
01108     return false;
01109   }
01110   Verts::iterator vi, vi2;
01111   vi = _verts.begin();
01112   while (vi != _verts.end()) {
01113     vi2 = vi;
01114     ++vi2;
01115     nassertr(vi2 != _verts.end(), false);
01116 
01117     // Exchange vi and vi2
01118     int t = *vi2;
01119     *vi2 = *vi;
01120     *vi = t;
01121 
01122     // Increment
01123     vi = vi2;
01124     ++vi;
01125   }
01126   return true;
01127 }
01128 
01129 ////////////////////////////////////////////////////////////////////
01130 //     Function: EggMesherStrip::is_odd
01131 //       Access: Public
01132 //  Description: Returns true if the tristrip or quadstrip contains an
01133 //               odd number of pieces.
01134 ////////////////////////////////////////////////////////////////////
01135 bool EggMesherStrip::
01136 is_odd() const {
01137   if (_type == PT_quadstrip || _type == PT_quad) {
01138     // If a quadstrip has a multiple of four vertices, it has an
01139     // odd number of quads.
01140     return (_verts.size() % 4 == 0);
01141   } else {
01142     // If a tristrip has an odd number of vertices, it has an odd
01143     // number of tris.
01144     return (_verts.size() % 2 == 1);
01145   }
01146 }
01147 
01148 ////////////////////////////////////////////////////////////////////
01149 //     Function: EggMesherStrip::would_reverse_tail
01150 //       Access: Public
01151 //  Description: Returns true if convert_to_type() would reverse the
01152 //               tail edge of the given strip, false otherwise.
01153 ////////////////////////////////////////////////////////////////////
01154 bool EggMesherStrip::
01155 would_reverse_tail(EggMesherStrip::PrimType want_type) const {
01156   bool reverse = false;
01157 
01158   if (_type == want_type) {
01159     return false;
01160   }
01161   if (want_type == PT_tristrip) {
01162     switch (_type) {
01163     case PT_tri:
01164     case PT_tristrip:
01165       break;
01166 
01167     case PT_quad:
01168     case PT_quadstrip:
01169       // When we convert a quadstrip to a tristrip, we reverse the
01170       // tail edge if we have a multiple of four verts.
01171       reverse = (_verts.size() % 4 == 0);
01172       break;
01173 
01174     default:
01175       egg_cat.fatal() << "Invalid conversion!\n";
01176       abort();
01177       break;
01178     }
01179 
01180   } else if (want_type == PT_quadstrip) {
01181     switch (_type) {
01182     case PT_quad:
01183     case PT_quadstrip:
01184       break;
01185 
01186     case PT_tri:
01187     case PT_tristrip:
01188       // We don't convert tristrips to quadstrips; fall through.
01189 
01190     default:
01191       egg_cat.fatal() << "Invalid conversion!\n";
01192       abort();
01193       break;
01194     }
01195   }
01196 
01197   return reverse;
01198 }
01199 
01200 
01201 ////////////////////////////////////////////////////////////////////
01202 //     Function: EggMesherStrip::convert_to_type
01203 //       Access: Public
01204 //  Description: Converts the EggMesherStrip from whatever form it
01205 //               is--triangle, quad, or quadstrip--into a tristrip or
01206 //               quadstrip.
01207 ////////////////////////////////////////////////////////////////////
01208 void EggMesherStrip::
01209 convert_to_type(EggMesherStrip::PrimType want_type) {
01210   Verts::iterator vi, vi2;
01211   int even;
01212 
01213   if (_type == want_type) {
01214     return;
01215   }
01216   if (want_type == PT_tristrip) {
01217     switch (_type) {
01218     case PT_tri:
01219     case PT_tristrip:
01220       break;
01221 
01222     case PT_quad:
01223     case PT_quadstrip:
01224       // To convert from quad/quadstrip to tristrip, we reverse every
01225       // other pair of vertices.
01226 
01227       vi = _verts.begin();
01228       even = 0;
01229       while (vi != _verts.end()) {
01230         vi2 = vi;
01231         ++vi2;
01232         nassertv(vi2 != _verts.end());
01233 
01234         // vi and vi2 are a pair.  Should we reverse them?
01235         if (even) {
01236           int t = *vi2;
01237           *vi2 = *vi;
01238           *vi = t;
01239         }
01240 
01241         // Increment
01242         vi = vi2;
01243         ++vi;
01244         even = !even;
01245       }
01246       break;
01247 
01248     default:
01249       egg_cat.fatal() << "Invalid conversion!\n";
01250       abort();
01251     }
01252 
01253   } else if (want_type == PT_quadstrip) {
01254     switch (_type) {
01255     case PT_quad:
01256     case PT_quadstrip:
01257       break;
01258 
01259     case PT_tri:
01260     case PT_tristrip:
01261       // We don't convert tristrips to quadstrips; fall through.
01262 
01263     default:
01264       egg_cat.fatal() << "Invalid conversion!\n";
01265       abort();
01266     }
01267   }
01268 
01269   _type = want_type;
01270 }
01271 
01272 ////////////////////////////////////////////////////////////////////
01273 //     Function: EggMesherStrip::combine_edges
01274 //       Access: Public
01275 //  Description: Removes the edges from the given strip and appends
01276 //               them to our own.  If remove_sides is true, then
01277 //               removes all the edges except the head and the tail.
01278 ////////////////////////////////////////////////////////////////////
01279 void EggMesherStrip::
01280 combine_edges(EggMesherStrip &other, int remove_sides) {
01281   Edges::iterator ei;
01282   for (ei = other._edges.begin(); ei != other._edges.end(); ++ei) {
01283     (*ei)->change_strip(&other, this);
01284   }
01285 
01286   _edges.splice(_edges.end(), other._edges);
01287 
01288   if (remove_sides) {
01289     // Identify the head and tail edges so we can remove everything
01290     // else.
01291     EggMesherEdge head = get_head_edge();
01292     EggMesherEdge tail = get_tail_edge();
01293 
01294     if (!is_odd()) {
01295       // If the strip is odd, its true tail edge is the inverse of its
01296       // actual edge.
01297       tail = EggMesherEdge(tail._vi_b, tail._vi_a);
01298     }
01299 
01300     Edges junk_edges;
01301 
01302     Edges::iterator next_ei;
01303     ei = _edges.begin();
01304     while (ei != _edges.end()) {
01305       next_ei = ei;
01306       ++next_ei;
01307 
01308       // Is this edge to be saved or is it fodder?
01309       if (!(**ei == head) && !(**ei == tail)) {
01310         // Fodder!  But we can't remove it right away, because this
01311         // will upset the current list; instead, we'll splice it to
01312         // junk_edges.
01313         junk_edges.splice(junk_edges.end(), _edges, ei);
01314       }
01315       ei = next_ei;
01316     }
01317 
01318     // Now we can safely remove all the to-be-junked edges.
01319     for (ei = junk_edges.begin(); ei != junk_edges.end(); ++ei) {
01320       (*ei)->remove(this);
01321     }
01322   }
01323 }
01324 
01325 
01326 ////////////////////////////////////////////////////////////////////
01327 //     Function: EggMesherStrip::remove_all_edges
01328 //       Access: Public
01329 //  Description: Removes all active edges from the strip.  This
01330 //               effectively renders it ineligible to mate with
01331 //               anything else.
01332 ////////////////////////////////////////////////////////////////////
01333 void EggMesherStrip::
01334 remove_all_edges() {
01335   // First, move all the edges to a safe place so we can traverse the
01336   // list without it changing on us.
01337   Edges junk_edges;
01338   junk_edges.splice(junk_edges.end(), _edges);
01339 
01340   // Now we can safely remove all the to-be-junked edges.
01341   Edges::iterator ei;
01342   for (ei = junk_edges.begin(); ei != junk_edges.end(); ++ei) {
01343     (*ei)->remove(this);
01344   }
01345 }
01346 
01347 ////////////////////////////////////////////////////////////////////
01348 //     Function: EggMesherStrip::pick_mate
01349 //       Access: Public
01350 //  Description: Defines an ordering to select neighbors to mate with.
01351 //               This compares strip a with strip b and returns true
01352 //               if strip a is the preferable choice, false if strip
01353 //               b.
01354 ////////////////////////////////////////////////////////////////////
01355 bool EggMesherStrip::
01356 pick_mate(const EggMesherStrip &a_strip, const EggMesherStrip &b_strip,
01357           const EggMesherEdge &a_edge, const EggMesherEdge &b_edge,
01358           const EggVertexPool *vertex_pool) const {
01359   // First, try to avoid polluting quads, quadstrips, and tristrips
01360   // with arbitrary triangles.  When we mate a tri or tristrip to a
01361   // quadstrip, we end up with a tristrip that may be less versatile
01362   // than the original quadstrip.  Better to avoid this if we can.
01363   // Try to choose a mate that more closely matches our own type.
01364   int a_cat = a_strip.type_category();
01365   int b_cat = b_strip.type_category();
01366   if (a_cat != b_cat) {
01367     int me_cat = type_category();
01368     return abs(a_cat - me_cat) < abs(b_cat - me_cat);
01369   }
01370 
01371   // Now, if we're connecting two tris, try to connect them up so they
01372   // make good quads.
01373   if (_type == PT_tri && a_strip._type == PT_tri &&
01374       b_strip._type == PT_tri) {
01375 
01376     // This will depend on both coplanarity and edge length.  We can't
01377     // use just one or the other, because some tris are nearly
01378     // isosceles, and some have more than one coplanar neighbor.
01379     // Hopefully the combination of both factors will zero us in on
01380     // the correct neighbor first.
01381 
01382     double a_coplanar = coplanarity(a_strip);
01383     double b_coplanar = coplanarity(b_strip);
01384     double coplanar_diff = a_coplanar - b_coplanar;
01385 
01386     double a_length = a_edge.compute_length(vertex_pool);
01387     double b_length = b_edge.compute_length(vertex_pool);
01388     double length_diff = (a_length - b_length) / (a_length + b_length);
01389 
01390     // These weights were chosen empirically to yield fairly good results.
01391     double sum = 4.0 * coplanar_diff - 1.0 * length_diff;
01392     return sum < 0;
01393   }
01394 
01395   // Then, get the smallest strip.
01396   if (a_strip._prims.size() != b_strip._prims.size()) {
01397     return a_strip._prims.size() < b_strip._prims.size();
01398   }
01399 
01400   // Finally, get the strip with the fewest neighbors.
01401   return a_strip.count_neighbors() < b_strip.count_neighbors();
01402 }
01403 
01404 ////////////////////////////////////////////////////////////////////
01405 //     Function: EggMesherStrip::pick_sheet_mate
01406 //       Access: Public
01407 //  Description: Defines an ordering to select neighbors to follow
01408 //               when measuring out a quadsheet.  This is only called
01409 //               when three or more prims share a single edge, which
01410 //               should be rarely--generally only when coplanar polys
01411 //               are going on.
01412 ////////////////////////////////////////////////////////////////////
01413 bool EggMesherStrip::
01414 pick_sheet_mate(const EggMesherStrip &a_strip, 
01415                 const EggMesherStrip &b_strip) const {
01416   // First, try to get the poly which is closest to our own normal.
01417   if (_planar && a_strip._planar && b_strip._planar) {
01418     double a_diff = dot(_plane_normal, a_strip._plane_normal);
01419     double b_diff = dot(_plane_normal, b_strip._plane_normal);
01420 
01421     if (fabs(a_diff - b_diff) > 0.0001) {
01422       return a_diff > b_diff;
01423     }
01424   }
01425 
01426   // Then, pick the one that's most like our own type.
01427   int a_cat = a_strip.type_category();
01428   int b_cat = b_strip.type_category();
01429   if (a_cat != b_cat) {
01430     int me_cat = type_category();
01431     return abs(a_cat - me_cat) < abs(b_cat - me_cat);
01432   }
01433 
01434   // Oh, just pick any old one.
01435   return false;
01436 }
01437 
01438 ////////////////////////////////////////////////////////////////////
01439 //     Function: EggMesherStrip::output
01440 //       Access: Public
01441 //  Description: Formats the vertex for output in some sensible way.
01442 ////////////////////////////////////////////////////////////////////
01443 void EggMesherStrip::
01444 output(ostream &out) const {
01445   switch (_status) {
01446   case MS_alive:
01447     break;
01448 
01449   case MS_dead:
01450     out << "Dead ";
01451     break;
01452 
01453   case MS_done:
01454     out << "Done ";
01455     break;
01456 
01457   default:
01458     out << "Unknown status ";
01459   }
01460 
01461   switch (_type) {
01462   case PT_tri:
01463     out << "Tri";
01464     break;
01465 
01466   case PT_quad:
01467     out << "Quad";
01468     break;
01469 
01470   case PT_tristrip:
01471     out << "TriStrip";
01472     break;
01473 
01474   case PT_trifan:
01475     out << "TriFan";
01476     break;
01477 
01478   case PT_quadstrip:
01479     out << "QuadStrip";
01480     break;
01481 
01482   default:
01483     out << "Unknown";
01484   }
01485 
01486   if (_planar) {
01487     out << " (planar)";
01488   }
01489 
01490   out << " " << _index << " [";
01491 
01492   Verts::const_iterator vi;
01493   for (vi = _verts.begin(); vi != _verts.end(); vi++) {
01494     out << " " << *vi;
01495   }
01496   out << " ]: " << _prims.size()
01497       << " prims, " << count_neighbors() << " neighbors";
01498 
01499   output_neighbors(out);
01500 
01501   out << " edges";
01502   Edges::const_iterator ei;
01503   for (ei = _edges.begin(); ei != _edges.end(); ei++) {
01504     out << " " << (void *)(*ei);
01505   }
01506 
01507   out << ".";
01508 }
01509 
 All Classes Functions Variables Enumerations