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