Panda3D
 All Classes Functions Variables Enumerations
eggMesherFanMaker.cxx
00001 // Filename: eggMesherFanMaker.cxx
00002 // Created by:  drose (22Mar05)
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 "eggMesherFanMaker.h"
00016 #include "eggMesher.h"
00017 #include "eggPolygon.h"
00018 #include "eggGroupNode.h"
00019 
00020 ////////////////////////////////////////////////////////////////////
00021 //     Function: EggMesherFanMaker::Constructor
00022 //       Access: Public
00023 //  Description: 
00024 ////////////////////////////////////////////////////////////////////
00025 EggMesherFanMaker::
00026 EggMesherFanMaker(int vertex, EggMesherStrip *tri, 
00027                   EggMesher *mesher) {
00028   _vertex = vertex;
00029   const EggMesherEdge *edge = tri->find_opposite_edge(vertex);
00030   if (edge != (const EggMesherEdge *)NULL) {
00031     _edges.push_back(edge);
00032   }
00033   _strips.push_back(tri);
00034   _planar = tri->_planar;
00035   _mesher = mesher;
00036 }
00037 
00038 ////////////////////////////////////////////////////////////////////
00039 //     Function: EggMesherFanMaker::Copy Constructor
00040 //       Access: Public
00041 //  Description: 
00042 ////////////////////////////////////////////////////////////////////
00043 EggMesherFanMaker::
00044 EggMesherFanMaker(const EggMesherFanMaker &copy) :
00045   _vertex(copy._vertex),
00046   _edges(copy._edges),
00047   _strips(copy._strips),
00048   _planar(copy._planar),
00049   _mesher(copy._mesher)
00050 {
00051 }
00052 
00053 ////////////////////////////////////////////////////////////////////
00054 //     Function: EggMesherFanMaker::Copy Assignment Operator
00055 //       Access: Public
00056 //  Description: 
00057 ////////////////////////////////////////////////////////////////////
00058 void EggMesherFanMaker::
00059 operator = (const EggMesherFanMaker &copy) {
00060   _vertex = copy._vertex;
00061   _edges = copy._edges;
00062   _strips = copy._strips;
00063   _planar = copy._planar;
00064   _mesher = copy._mesher;
00065 }
00066 
00067 ////////////////////////////////////////////////////////////////////
00068 //     Function: EggMesherFanMaker::join
00069 //       Access: Public
00070 //  Description: Attempts to connect two fans end-to-end.  They must
00071 //               both share the same common vertex and a common edge.
00072 //
00073 //               The return value is true if the fans were
00074 //               successfully joined, or false if they could not be.
00075 ////////////////////////////////////////////////////////////////////
00076 bool EggMesherFanMaker::
00077 join(EggMesherFanMaker &other) {
00078   nassertr(_vertex == other._vertex, false);
00079   nassertr(_mesher == other._mesher, false);
00080 
00081   nassertr(!_edges.empty() && !other._edges.empty(), false);
00082 
00083   const EggMesherEdge *my_back = _edges.back();
00084   const EggMesherEdge *other_front = other._edges.front();
00085   nassertr(my_back != (EggMesherEdge *)NULL && 
00086            other_front != (EggMesherEdge *)NULL, false);
00087 
00088   int my_back_b = my_back->_vi_b;
00089   int other_front_a = other_front->_vi_a;
00090 
00091   if (my_back_b == other_front_a) {
00092     _planar = is_coplanar_with(other);
00093     _edges.splice(_edges.end(), other._edges);
00094     _strips.splice(_strips.end(), other._strips);
00095     return true;
00096   }
00097 
00098   const EggMesherEdge *my_front = _edges.front();
00099   const EggMesherEdge *other_back = other._edges.back();
00100   nassertr(my_front != (EggMesherEdge *)NULL && 
00101            other_back != (EggMesherEdge *)NULL, false);
00102 
00103   int my_front_a = my_front->_vi_a;
00104   int other_back_b = other_back->_vi_b;
00105 
00106   if (my_front_a == other_back_b) {
00107     _planar = is_coplanar_with(other);
00108     _edges.splice(_edges.begin(), other._edges);
00109     _strips.splice(_strips.begin(), other._strips);
00110     return true;
00111   }
00112 
00113   return false;
00114 }
00115 
00116 ////////////////////////////////////////////////////////////////////
00117 //     Function: EggMesherFanMaker::compute_angle
00118 //       Access: Public
00119 //  Description: Returns the overall angle subtended by the fan, from
00120 //               the leading edge to the trailing edge, in degrees.
00121 ////////////////////////////////////////////////////////////////////
00122 double EggMesherFanMaker::
00123 compute_angle() const {
00124   // We sum up the angles of each triangle.  This is more correct than
00125   // taking the net angle from the first edge to the last (since we
00126   // may not be in a plane).
00127   nassertr(is_valid(), 0.0);
00128 
00129   EggVertexPool *vertex_pool = _mesher->_vertex_pool;
00130   
00131   double angle = 0.0;
00132   LPoint3d v0 = vertex_pool->get_vertex(_vertex)->get_pos3();
00133 
00134   Edges::const_iterator ei;
00135   for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00136     LVector3d v1 = vertex_pool->get_vertex((*ei)->_vi_a)->get_pos3() - v0;
00137     LVector3d v2 = vertex_pool->get_vertex((*ei)->_vi_b)->get_pos3() - v0;
00138 
00139     v1 = normalize(v1);
00140     v2 = normalize(v2);
00141     angle += acos(dot(v1, v2));
00142   }
00143 
00144   return rad_2_deg(angle);
00145 }
00146 
00147 ////////////////////////////////////////////////////////////////////
00148 //     Function: EggMesherFanMaker::build
00149 //       Access: Public
00150 //  Description: Begins the fanning process.  Searches for triangles
00151 //               and connects them into a fan.
00152 //
00153 //               In certain cases, if egg_unroll_fans is enabled, the
00154 //               resulting fan may be retesselated into a series of
00155 //               zig-zag triangles, which are stored in unrolled_tris.
00156 //               Otherwise, an EggMesherStrip (representing the fan)
00157 //               is created and added to the mesher.
00158 //
00159 //               The return value is (loosely) the number of
00160 //               primitives created.
00161 ////////////////////////////////////////////////////////////////////
00162 int EggMesherFanMaker::
00163 build(EggGroupNode *unrolled_tris) {
00164   nassertr(_edges.size() == _strips.size(), 0);
00165 
00166   int num_tris = _edges.size();
00167   double net_angle = compute_angle();
00168   double avg_angle = net_angle / (double)num_tris;
00169 
00170   if (avg_angle > egg_max_tfan_angle) {
00171     // The triangles are too loose to justify making a fan; it'll
00172     // probably make a better quadsheet.
00173     return 0;
00174   }
00175 
00176   if (egg_min_tfan_tris == 0 || num_tris < egg_min_tfan_tris) {
00177     // Oops, not enough triangles to justify a fan.
00178     if (!egg_unroll_fans) {
00179       return 0;
00180     }
00181 
00182     // However, we could (maybe) make it a few tristrips!
00183 
00184     // Each section of the fan which is made up of coplanar tris, with
00185     // identical properties, may be retesselated into a tristrip.
00186     // What a sneaky trick!  To do this, we must first identify each
00187     // such qualifying section.
00188 
00189     // We define a seam as the edge between any two tris which are
00190     // noncoplanar or have different properties.  Then we can send
00191     // each piece between the seams to unroll().
00192 
00193     Strips::iterator si, last_si;
00194     Edges::iterator ei, last_ei;
00195 
00196     // First, rotate the fan so it begins at a seam.  We do this so we
00197     // won't be left out with part of one piece at the beginning and
00198     // also at the end.
00199     si = _strips.begin();
00200     last_si = si;
00201     ei = _edges.begin();
00202     last_ei = ei;
00203     int found_seam = false;
00204 
00205     for (++si, ++ei; si != _strips.end() && !found_seam; ++si, ++ei) {
00206       nassertr(ei != _edges.end(), 0);
00207       if ( ((*si)->_prims.front()->compare_to(*(*last_si)->_prims.front()) != 0) ||
00208            !(*si)->is_coplanar_with(*(*last_si), egg_coplanar_threshold)) {
00209         // Here's a seam.  Break the fan here.
00210         found_seam = true;
00211         _edges.splice(_edges.begin(), _edges, ei, _edges.end());
00212         _strips.splice(_strips.begin(), _strips, si, _strips.end());
00213       }
00214     }
00215 
00216     // Now break the fan up along its seams and unroll each piece
00217     // separately.
00218     si = _strips.begin();
00219     last_si = si;
00220     ei = _edges.begin();
00221     last_ei = ei;
00222 
00223     int count = 0;
00224     for (++si, ++ei; si != _strips.end(); ++si, ++ei) {
00225       nassertr(ei != _edges.end(), 0);
00226       if ( ((*si)->_prims.front()->compare_to(*(*last_si)->_prims.front()) != 0) ||
00227            !(*si)->is_coplanar_with(*(*last_si), egg_coplanar_threshold)) {
00228         // Here's the end of a run of matching pieces.
00229         count += unroll(last_si, si, last_ei, ei, unrolled_tris);
00230         last_si = si;
00231         last_ei = ei;
00232       }
00233     }
00234     count += unroll(last_si, si, last_ei, ei, unrolled_tris);
00235 
00236     return count;
00237 
00238   } else {
00239     EggMesherStrip new_fan(EggMesherStrip::PT_trifan, EggMesherStrip::MO_fanpoly);
00240     new_fan._verts.push_back(_vertex);
00241 
00242     new_fan._verts.push_back(_edges.front()->_vi_a);
00243     Edges::iterator ei;
00244     for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00245       new_fan._verts.push_back((*ei)->_vi_b);
00246     }
00247 
00248     Strips::iterator si;
00249     for (si = _strips.begin(); si != _strips.end(); ++si) {
00250       new_fan._prims.splice(new_fan._prims.end(), (*si)->_prims);
00251       (*si)->remove_all_edges();
00252       (*si)->_verts.clear();
00253       (*si)->_status = EggMesherStrip::MS_dead;
00254     }
00255 
00256     // If we'd built our list of edges and strips right, this sum should
00257     // come out so that there are two more vertices than triangles in
00258     // the new fan.
00259     nassertr(new_fan._verts.size() == new_fan._prims.size() + 2, 0);
00260 
00261     // Now we've built a fan, and it won't be able to mate with
00262     // anything else, so add it to the done list.
00263     _mesher->_done.push_back(new_fan);
00264   }
00265 
00266   return 1;
00267 }
00268 
00269 ////////////////////////////////////////////////////////////////////
00270 //     Function: EggMesherFanMaker::unroll
00271 //       Access: Public
00272 //  Description: Unrolls a planar subset of the current working fan,
00273 //               defined by the given iterators, into a series of
00274 //               triangles that zig-zag back and forth for better
00275 //               tristripping properties.  The new triangles are added
00276 //               to unrolled_tris; the return value is 1 if
00277 //               successful, or 0 otherwise.
00278 ////////////////////////////////////////////////////////////////////
00279 int EggMesherFanMaker::
00280 unroll(Strips::iterator strip_begin, Strips::iterator strip_end,
00281        Edges::iterator edge_begin, Edges::iterator edge_end,
00282        EggGroupNode *unrolled_tris) {
00283   Edges::iterator ei;
00284   Strips::iterator si;
00285 
00286   int num_tris = 0;
00287   for (ei = edge_begin; ei != edge_end; ++ei) {
00288     num_tris++;
00289   }
00290 
00291   if (num_tris < 3) {
00292     // Don't even bother.
00293     return 0;
00294   }
00295 
00296   PT(EggPolygon) poly = new EggPolygon;
00297 
00298   // Now we build an n-sided polygon the same shape as the fan.  We'll
00299   // decompose it into tris in a second.
00300   poly->copy_attributes(*(*strip_begin)->_prims.front());
00301   EggVertexPool *vertex_pool = _mesher->_vertex_pool;
00302 
00303   ei = edge_end;
00304   --ei;
00305   if ((*ei)->_vi_b != (*edge_begin)->_vi_a) {
00306     // If the fan is less than a full circle, we need to keep the
00307     // hub vertex and initial vertex in the poly.  Otherwise, we'll
00308     // discard them.
00309     poly->add_vertex(vertex_pool->get_vertex(_vertex));
00310     poly->add_vertex(vertex_pool->get_vertex((*edge_begin)->_vi_a));
00311   }
00312 
00313   for (ei = edge_begin; ei != edge_end; ++ei) {
00314     poly->add_vertex(vertex_pool->get_vertex((*ei)->_vi_b));
00315   }
00316 
00317   bool result = true;
00318 
00319   if (egg_show_quads) {
00320     // If we're showing quads, also show retesselated triangles.
00321 
00322     // We can't add it directly to the mesher, that's unsafe; instead,
00323     // we'll just add it to the end of the unrolled_tris list.  This
00324     // does mean we won't be able to color it a fancy color, but too
00325     // bad.
00326     //_mesher->add_polygon(poly, EggMesherStrip::MO_fanpoly);
00327     unrolled_tris->add_child(poly);
00328 
00329   } else {
00330     // Now decompose the new polygon into triangles.
00331     result = poly->triangulate_into(unrolled_tris, true);
00332   }
00333 
00334   if (result) {
00335     // Now that we've created a new poly, kill off all the old ones.
00336     for (si = strip_begin; si != strip_end; ++si) {
00337       (*si)->remove_all_edges();
00338       (*si)->_verts.clear();
00339       (*si)->_prims.clear();
00340       (*si)->_status = EggMesherStrip::MS_dead;
00341     }
00342     return 1;
00343   } else {
00344     return 0;
00345   }
00346 }
00347 
00348 ////////////////////////////////////////////////////////////////////
00349 //     Function: EggMesherFanMaker::output
00350 //       Access: Public
00351 //  Description: 
00352 ////////////////////////////////////////////////////////////////////
00353 void EggMesherFanMaker::
00354 output(ostream &out) const {
00355   out << _vertex << ":[";
00356   if (!_edges.empty()) {
00357     Edges::const_iterator ei;
00358     for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00359       out << " " << (*ei)->_vi_a;
00360     }
00361     out << " " << _edges.back()->_vi_b;
00362   }
00363   out << " ]";
00364 
00365   if (_planar) {
00366     out << " (planar)";
00367   }
00368 }
 All Classes Functions Variables Enumerations