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