Panda3D
|
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 ©) : 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 ©) { 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 }