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