00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
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
00026
00027
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
00043
00044
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;
00057
00058
00059
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
00076
00077 _prims.push_back(prim);
00078 }
00079
00080 _planar = false;
00081
00082 if (prim->is_of_type(EggPolygon::get_class_type())) {
00083
00084
00085
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
00099
00100
00101
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
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
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
00144
00145
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
00159
00160
00161 const EggAttributes *attrib = (*pi);
00162 ++pi;
00163 DCAST(EggCompositePrimitive, prim)->set_component(count - 3, attrib);
00164 }
00165 }
00166
00167
00168
00169 nassertr(vi == _verts.end(), prim);
00170 nassertr(pi == _prims.end(), prim);
00171 }
00172
00173 return prim;
00174 }
00175
00176
00177
00178
00179
00180
00181
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
00189
00190 if (_row_id >= first_row_id) {
00191 return;
00192 }
00193 } else {
00194
00195
00196
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
00215
00216
00217 int vi_a = edge->_vi_a;
00218 int vi_b = edge->_vi_b;
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242 for (int secondary = 0; secondary <= 1; secondary++) {
00243
00244
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
00260
00261
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
00283
00284 nassertv(_type != PT_tri);
00285
00286
00287 nassertv(_type == PT_tristrip || _type == PT_quadstrip);
00288
00289
00290
00291
00292 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
00293 if (!(*ei)->matches(*edge)) {
00294
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
00317
00318
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
00326
00327
00328
00329
00330
00331
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
00341 strip_ptrs.push_back(*si);
00342 }
00343 }
00344 }
00345
00346
00347
00348
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
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
00370 not_any = false;
00371 EggMesherStrip *mate = *si;
00372
00373
00374
00375
00376
00377
00378
00379 mate->cut_sheet(first_row_id, false, vertex_pool);
00380
00381 if (_status == MS_alive && mate->_status == MS_alive) {
00382
00383
00384
00385
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
00400 _row_id = -first_row_id;
00401 }
00402 }
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415 bool EggMesherStrip::
00416 mate(const EggVertexPool *vertex_pool) {
00417
00418
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
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
00437
00438 return true;
00439 }
00440
00441
00442
00443
00444
00445
00446
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
00478
00479
00480
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
00491
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
00503
00504 front._type = PT_quad;
00505
00506
00507
00508 int new_vert = back.find_uncommon_vertex(common_edge);
00509
00510
00511
00512
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
00520 front._verts.insert(b, new_vert);
00521 } else {
00522
00523 front._verts.push_back(new_vert);
00524 }
00525 } else {
00526
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
00535
00536 remove_sides = false;
00537
00538 } else {
00539
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
00553
00554
00555
00556 success = mate_strips(common_edge, front, back, PT_quadstrip);
00557
00558 if (!success) {
00559
00560
00561
00562
00563 common_edge->remove(&front);
00564 common_edge->remove(&back);
00565 }
00566
00567 } else {
00568
00569
00570
00571
00572
00573
00574
00575 success = mate_strips(common_edge, front, back, PT_tristrip);
00576
00577 if (!success) {
00578
00579
00580
00581
00582 success = mate_strips(common_edge, back, front, PT_tristrip);
00583
00584 if (success) {
00585
00586 front._verts.splice(front._verts.end(), back._verts);
00587 front._prims.splice(front._prims.end(), back._prims);
00588
00589 } else {
00590
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
00601
00602 common_edge->remove(&front);
00603 }
00604
00605 nassertr(back._prims.empty(), false);
00606 nassertr(back._verts.empty(), false);
00607
00608
00609 back._status = MS_dead;
00610
00611
00612
00613 front._planar = is_coplanar;
00614 front._origin = MO_mate;
00615 }
00616
00617 return success;
00618 }
00619
00620
00621
00622
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633 bool EggMesherStrip::
00634 mate_strips(EggMesherEdge *common_edge, EggMesherStrip &front,
00635 EggMesherStrip &back, EggMesherStrip::PrimType type) {
00636
00637
00638
00639
00640
00641
00642
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
00651
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
00667
00668
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
00701
00702
00703
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
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735
00736
00737
00738
00739
00740
00741
00742
00743
00744
00745
00746
00747
00748
00749
00750
00751
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
00763
00764
00765
00766
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
00776
00777
00778 } else if (front.is_odd()) {
00779
00780 invert = !invert;
00781 }
00782
00783 if (will_reverse_back) {
00784
00785
00786
00787 if (back.is_odd()) {
00788
00789
00790 invert = !invert;
00791 }
00792 }
00793
00794 return invert;
00795 }
00796
00797
00798
00799
00800
00801
00802
00803
00804 bool EggMesherStrip::
00805 convex_quad(EggMesherEdge *common_edge, EggMesherStrip &front,
00806 EggMesherStrip &back, const EggVertexPool *vertex_pool) {
00807
00808
00809
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
00822
00823
00824
00825 nassertr(front._planar, false);
00826
00827 LNormald n(front._plane_normal);
00828 int xi, yi;
00829
00830
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
00856
00857
00858
00859
00860
00861
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
00867
00868
00869
00870
00871 double t = - ((A*c2[0] + B*c2[1]) + C) / (A*(d2[0]-c2[0]) + B*(d2[1]-c2[1]));
00872
00873
00874 return (0.0 <= t && t <= 1.0);
00875 }
00876
00877
00878
00879
00880
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
00895
00896
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
00914
00915
00916
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
00939
00940
00941
00942
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
00959
00960
00961
00962
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
00982
00983
00984
00985
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
01005
01006
01007
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
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
01020 return;
01021 }
01022
01023
01024 rotate_back();
01025
01026 } else {
01027
01028 int num_verts = _verts.size();
01029 while (_verts.front() != vi_a && _verts.front() != vi_b) {
01030
01031 num_verts--;
01032 nassertv(num_verts > 0);
01033 rotate_forward();
01034 }
01035 }
01036
01037 #ifndef NDEBUG
01038
01039 Verts::iterator vi = _verts.begin();
01040 ++vi;
01041 nassertv(*vi == vi_a || *vi == vi_b);
01042 #endif
01043 }
01044
01045
01046
01047
01048
01049
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
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
01062 return;
01063 }
01064
01065
01066 rotate_forward();
01067
01068 } else {
01069
01070 int num_verts = _verts.size();
01071 while (_verts.back() != vi_a && _verts.back() != vi_b) {
01072
01073 num_verts--;
01074 nassertv(num_verts > 0);
01075 rotate_back();
01076 }
01077 }
01078
01079 #ifndef NDEBUG
01080
01081 Verts::reverse_iterator vi = _verts.rbegin();
01082 ++vi;
01083 nassertv(*vi == vi_a || *vi == vi_b);
01084 #endif
01085 }
01086
01087
01088
01089
01090
01091
01092
01093
01094
01095 bool EggMesherStrip::
01096 can_invert() const {
01097 return (_type == PT_quadstrip || _type == PT_quad);
01098 }
01099
01100
01101
01102
01103
01104
01105
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
01120 int t = *vi2;
01121 *vi2 = *vi;
01122 *vi = t;
01123
01124
01125 vi = vi2;
01126 ++vi;
01127 }
01128 return true;
01129 }
01130
01131
01132
01133
01134
01135
01136
01137 bool EggMesherStrip::
01138 is_odd() const {
01139 if (_type == PT_quadstrip || _type == PT_quad) {
01140
01141
01142 return (_verts.size() % 4 == 0);
01143 } else {
01144
01145
01146 return (_verts.size() % 2 == 1);
01147 }
01148 }
01149
01150
01151
01152
01153
01154
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
01172
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
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
01205
01206
01207
01208
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
01227
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
01237 if (even) {
01238 int t = *vi2;
01239 *vi2 = *vi;
01240 *vi = t;
01241 }
01242
01243
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
01264
01265 default:
01266 egg_cat.fatal() << "Invalid conversion!\n";
01267 abort();
01268 }
01269 }
01270
01271 _type = want_type;
01272 }
01273
01274
01275
01276
01277
01278
01279
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
01292
01293 EggMesherEdge head = get_head_edge();
01294 EggMesherEdge tail = get_tail_edge();
01295
01296 if (!is_odd()) {
01297
01298
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
01311 if (!(**ei == head) && !(**ei == tail)) {
01312
01313
01314
01315 junk_edges.splice(junk_edges.end(), _edges, ei);
01316 }
01317 ei = next_ei;
01318 }
01319
01320
01321 for (ei = junk_edges.begin(); ei != junk_edges.end(); ++ei) {
01322 (*ei)->remove(this);
01323 }
01324 }
01325 }
01326
01327
01328
01329
01330
01331
01332
01333
01334
01335 void EggMesherStrip::
01336 remove_all_edges() {
01337
01338
01339 Edges junk_edges;
01340 junk_edges.splice(junk_edges.end(), _edges);
01341
01342
01343 Edges::iterator ei;
01344 for (ei = junk_edges.begin(); ei != junk_edges.end(); ++ei) {
01345 (*ei)->remove(this);
01346 }
01347 }
01348
01349
01350
01351
01352
01353
01354
01355
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
01362
01363
01364
01365
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
01374
01375 if (_type == PT_tri && a_strip._type == PT_tri &&
01376 b_strip._type == PT_tri) {
01377
01378
01379
01380
01381
01382
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
01393 double sum = 4.0 * coplanar_diff - 1.0 * length_diff;
01394 return sum < 0;
01395 }
01396
01397
01398 if (a_strip._prims.size() != b_strip._prims.size()) {
01399 return a_strip._prims.size() < b_strip._prims.size();
01400 }
01401
01402
01403 return a_strip.count_neighbors() < b_strip.count_neighbors();
01404 }
01405
01406
01407
01408
01409
01410
01411
01412
01413
01414
01415 bool EggMesherStrip::
01416 pick_sheet_mate(const EggMesherStrip &a_strip,
01417 const EggMesherStrip &b_strip) const {
01418
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
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
01437 return false;
01438 }
01439
01440
01441
01442
01443
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