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