00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #include "eggMesher.h"
00016 #include "eggMesherFanMaker.h"
00017 #include "eggPolygon.h"
00018 #include "eggCompositePrimitive.h"
00019 #include "eggTriangleStrip.h"
00020 #include "eggTriangleFan.h"
00021 #include "eggGroup.h"
00022 #include "config_egg.h"
00023 #include "eggGroupNode.h"
00024 #include "dcast.h"
00025 #include "thread.h"
00026
00027 #include <stdlib.h>
00028
00029
00030
00031
00032
00033
00034 EggMesher::
00035 EggMesher() {
00036 _vertex_pool = NULL;
00037 _strip_index = 0;
00038 }
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055 void EggMesher::
00056 mesh(EggGroupNode *group, bool flat_shaded) {
00057 _flat_shaded = flat_shaded;
00058
00059
00060
00061
00062 PT(EggGroupNode) output_children = new EggGroupNode;
00063
00064
00065
00066 PT(EggGroupNode) next_children = new EggGroupNode;
00067 PT(EggGroupNode) this_children = group;
00068
00069
00070
00071
00072 while (this_children->size() != 0) {
00073 clear();
00074
00075
00076 while (!this_children->empty()) {
00077 PT(EggNode) child = this_children->get_first_child();
00078 this_children->remove_child(child);
00079
00080 if (child->is_of_type(EggPolygon::get_class_type())) {
00081 EggPolygon *poly = DCAST(EggPolygon, child);
00082
00083 if (_vertex_pool == (EggVertexPool *)NULL) {
00084 _vertex_pool = poly->get_pool();
00085 add_polygon(poly, EggMesherStrip::MO_user);
00086
00087 } else if (_vertex_pool == poly->get_pool()) {
00088 add_polygon(poly, EggMesherStrip::MO_user);
00089
00090 } else {
00091
00092 next_children->add_child(poly);
00093 }
00094
00095 } else {
00096
00097
00098 output_children->add_child(child);
00099 }
00100 }
00101
00102 do_mesh();
00103
00104 Strips::iterator si;
00105 for (si = _done.begin(); si != _done.end(); ++si) {
00106 PT(EggPrimitive) egg_prim = get_prim(*si);
00107 if (egg_prim != (EggPrimitive *)NULL) {
00108 output_children->add_child(egg_prim);
00109 }
00110 }
00111
00112 this_children = next_children;
00113 next_children = new EggGroupNode;
00114 }
00115
00116
00117 group->clear();
00118 group->steal_children(*output_children);
00119
00120 clear();
00121 }
00122
00123
00124
00125
00126
00127
00128 void EggMesher::
00129 write(ostream &out) const {
00130
00131
00132
00133
00134
00135 out << _verts.size() << " verts:\n";
00136 Verts::const_iterator vi;
00137
00138 for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
00139 int v = (*vi).first;
00140 const EdgePtrs &edges = (*vi).second;
00141 out << v << " shares " << count_vert_edges(edges) << " edges:\n";
00142 EdgePtrs::const_iterator ei;
00143 for (ei = edges.begin(); ei != edges.end(); ++ei) {
00144 if (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty()) {
00145 out << " " << **ei << "\n";
00146 }
00147 }
00148 }
00149
00150 Strips::const_iterator si;
00151 out << _tris.size() << " tris:\n";
00152 for (si = _tris.begin(); si != _tris.end(); ++si) {
00153 out << (*si) << "\n";
00154 }
00155
00156 out << _quads.size() << " quads:\n";
00157 for (si = _quads.begin(); si != _quads.end(); ++si) {
00158 out << (*si) << "\n";
00159 }
00160
00161 out << _strips.size() << " strips:\n";
00162 for (si = _strips.begin(); si != _strips.end(); ++si) {
00163 out << (*si) << "\n";
00164 }
00165 }
00166
00167
00168
00169
00170
00171
00172
00173 void EggMesher::
00174 clear() {
00175 _tris.clear();
00176 _quads.clear();
00177 _strips.clear();
00178 _dead.clear();
00179 _done.clear();
00180 _verts.clear();
00181 _edges.clear();
00182 _strip_index = 0;
00183 _vertex_pool = NULL;
00184 _color_sheets.clear();
00185 }
00186
00187
00188
00189
00190
00191
00192
00193 bool EggMesher::
00194 add_polygon(const EggPolygon *egg_poly, EggMesherStrip::MesherOrigin origin) {
00195 CPT(EggPolygon) this_poly = egg_poly;
00196 if (this_poly->size() != 3) {
00197
00198
00199
00200
00201 bool convex_also = (this_poly->size() != 4);
00202
00203 PT(EggGroupNode) temp_group = new EggGroupNode;
00204 bool result = this_poly->triangulate_into(temp_group, convex_also);
00205 EggGroupNode::iterator ci;
00206 if (temp_group->size() != 1) {
00207 for (ci = temp_group->begin(); ci != temp_group->end(); ++ci) {
00208 add_polygon(DCAST(EggPolygon, *ci), EggMesherStrip::MO_user);
00209 }
00210 return result;
00211 }
00212
00213
00214
00215 ci = temp_group->begin();
00216 this_poly = DCAST(EggPolygon, *ci);
00217 }
00218
00219 if (_vertex_pool == NULL) {
00220 _vertex_pool = this_poly->get_pool();
00221 } else {
00222 nassertr(_vertex_pool == this_poly->get_pool(), false);
00223 }
00224
00225
00226 EggMesherStrip temp_strip(this_poly, _strip_index++, _vertex_pool,
00227 _flat_shaded);
00228 Strips &list = choose_strip_list(temp_strip);
00229 list.push_back(temp_strip);
00230 EggMesherStrip &strip = list.back();
00231 strip._origin = origin;
00232
00233 int i;
00234 int num_verts = this_poly->size();
00235
00236 int *vptrs = (int *)alloca(num_verts * sizeof(int));
00237 EdgePtrs **eptrs = (EdgePtrs **)alloca(num_verts * sizeof(EdgePtrs *));
00238
00239
00240 for (i = 0; i < num_verts; i++) {
00241 Verts::value_type v(this_poly->get_vertex(i)->get_index(), EdgePtrs());
00242 Verts::iterator n = _verts.insert(v).first;
00243
00244 vptrs[i] = (*n).first;
00245 eptrs[i] = &(*n).second;
00246
00247 strip._verts.push_back(vptrs[i]);
00248 }
00249
00250
00251 for (i = 0; i < num_verts; i++) {
00252
00253
00254
00255 EggMesherEdge inner(vptrs[i], vptrs[(i+1) % num_verts]);
00256 EggMesherEdge outer(vptrs[(i+1) % num_verts], vptrs[i]);
00257
00258
00259 EggMesherEdge &inner_ref = (EggMesherEdge &)*_edges.insert(inner).first;
00260 EggMesherEdge &outer_ref = (EggMesherEdge &)*_edges.insert(outer).first;
00261
00262
00263 inner_ref._opposite = &outer_ref;
00264 outer_ref._opposite = &inner_ref;
00265
00266
00267 strip._edges.push_back(&inner_ref);
00268
00269
00270 outer_ref._strips.push_back(&strip);
00271
00272
00273
00274 eptrs[i]->insert(&outer_ref);
00275 eptrs[(i+1) % num_verts]->insert(&outer_ref);
00276 }
00277
00278 return true;
00279 }
00280
00281
00282
00283
00284
00285
00286
00287
00288 void EggMesher::
00289 do_mesh() {
00290 if (egg_consider_fans && !_flat_shaded) {
00291 find_fans();
00292 }
00293
00294
00295 if (egg_retesselate_coplanar) {
00296 make_quads();
00297 }
00298
00299
00300 mesh_list(_tris);
00301
00302 if (egg_show_quads) {
00303
00304 Strips::iterator si;
00305 for (si = _quads.begin(); si != _quads.end(); ++si) {
00306 if ((*si)._status == EggMesherStrip::MS_alive) {
00307 (*si)._status = EggMesherStrip::MS_done;
00308 }
00309 }
00310 for (si = _strips.begin(); si != _strips.end(); ++si) {
00311 if ((*si)._status == EggMesherStrip::MS_alive) {
00312 (*si)._status = EggMesherStrip::MS_done;
00313 }
00314 }
00315 }
00316
00317
00318 build_sheets();
00319
00320
00321 mesh_list(_quads);
00322
00323
00324 mesh_list(_strips);
00325
00326 Thread::consider_yield();
00327 }
00328
00329
00330
00331
00332
00333
00334
00335 PT(EggPrimitive) EggMesher::
00336 get_prim(EggMesherStrip &strip) {
00337 EggMesherStrip::PrimType orig_type = strip._type;
00338 PT(EggPrimitive) egg_prim = strip.make_prim(_vertex_pool);
00339
00340 if (egg_show_tstrips) {
00341
00342
00343
00344 LColor color1, color2;
00345
00346 if (egg_prim->is_of_type(EggTriangleStrip::get_class_type()) ||
00347 egg_prim->is_of_type(EggTriangleFan::get_class_type())) {
00348 make_random_color(color2);
00349 color1 = (color2 * 0.8);
00350
00351 } else {
00352
00353 color1.set(0.85, 0.85, 0.85, 1.0);
00354 color2.set(0.85, 0.85, 0.85, 1.0);
00355 }
00356
00357
00358
00359 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
00360 EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
00361 int num_components = egg_comp->get_num_components();
00362 if (num_components > 0) {
00363 egg_comp->get_component(0)->set_color(color1);
00364 for (int i = 1; i < num_components; i++) {
00365 egg_comp->get_component(i)->set_color(color2);
00366 }
00367 }
00368 } else {
00369 egg_prim->set_color(color1);
00370 }
00371
00372 int num_verts = egg_prim->size();
00373 for (int i = 0; i < num_verts; i++) {
00374 egg_prim->get_vertex(i)->clear_color();
00375 }
00376
00377 } else if (egg_show_qsheets) {
00378
00379
00380
00381
00382
00383 LColor color1;
00384 if (strip._row_id < 0) {
00385
00386 ColorSheetMap::iterator ci = _color_sheets.find(strip._row_id);
00387
00388 if (ci == _color_sheets.end()) {
00389 make_random_color(color1);
00390 _color_sheets[strip._row_id] = color1;
00391 } else {
00392 color1 = (*ci).second;
00393 }
00394 }
00395
00396
00397
00398 egg_prim->set_color(color1);
00399 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
00400 EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
00401 int num_components = egg_comp->get_num_components();
00402 for (int i = 0; i < num_components; i++) {
00403 egg_comp->get_component(i)->clear_color();
00404 }
00405 }
00406 int num_verts = egg_prim->size();
00407 for (int i = 0; i < num_verts; i++) {
00408 egg_prim->get_vertex(i)->clear_color();
00409 }
00410
00411 } else if (egg_show_quads) {
00412
00413
00414
00415
00416
00417
00418
00419
00420
00421
00422
00423
00424
00425 LColor white(0.85, 0.85, 0.85, 1.0);
00426 LColor dark_blue(0.0, 0.0, 0.75, 1.0);
00427 LColor light_blue(0.4, 0.4, 0.8, 1.0);
00428 LColor very_light_blue(0.6, 0.6, 1.0, 1.0);
00429 LColor green(0.2, 0.8, 0.2, 1.0);
00430
00431 LColor color1;
00432 if (strip._origin == EggMesherStrip::MO_user) {
00433 color1 = white;
00434 } else if (strip._origin == EggMesherStrip::MO_firstquad) {
00435 color1 = dark_blue;
00436 } else if (strip._origin == EggMesherStrip::MO_fanpoly) {
00437 color1 = green;
00438 } else {
00439 switch (orig_type) {
00440 case EggMesherStrip::PT_quad:
00441 color1 = light_blue;
00442 break;
00443
00444 case EggMesherStrip::PT_quadstrip:
00445 color1 = very_light_blue;
00446 break;
00447
00448 case EggMesherStrip::PT_tristrip:
00449 make_random_color(color1);
00450
00451 if (color1[0] < color1[1]) {
00452 PN_stdfloat t = color1[0];
00453 color1[0] = color1[1];
00454 color1[1] = t;
00455 }
00456 color1[2] = color1[1];
00457 break;
00458
00459 case EggMesherStrip::PT_trifan:
00460 make_random_color(color1);
00461
00462 if (color1[0] > color1[1]) {
00463 PN_stdfloat t = color1[0];
00464 color1[0] = color1[1];
00465 color1[1] = t;
00466 }
00467 color1[2] = color1[0];
00468 break;
00469
00470 default:
00471 color1 = white;
00472 }
00473 }
00474
00475
00476
00477 egg_prim->set_color(color1);
00478 if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
00479 EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
00480 int num_components = egg_comp->get_num_components();
00481 for (int i = 0; i < num_components; i++) {
00482 egg_comp->get_component(i)->clear_color();
00483 }
00484 }
00485 int num_verts = egg_prim->size();
00486 for (int i = 0; i < num_verts; i++) {
00487 egg_prim->get_vertex(i)->clear_color();
00488 }
00489 }
00490
00491 return egg_prim;
00492 }
00493
00494
00495
00496
00497
00498
00499
00500 int EggMesher::
00501 count_vert_edges(const EdgePtrs &edges) const {
00502 int count = 0;
00503 EdgePtrs::const_iterator ei;
00504 for (ei = edges.begin(); ei != edges.end(); ++ei) {
00505 count += (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty());
00506 }
00507 return count;
00508 }
00509
00510
00511
00512
00513
00514
00515
00516
00517 plist<EggMesherStrip> &EggMesher::
00518 choose_strip_list(const EggMesherStrip &strip) {
00519 switch (strip._status) {
00520 case EggMesherStrip::MS_done:
00521 return _done;
00522
00523 case EggMesherStrip::MS_dead:
00524 return _dead;
00525
00526 case EggMesherStrip::MS_alive:
00527 switch (strip._type) {
00528 case EggMesherStrip::PT_tri:
00529 return _tris;
00530
00531 case EggMesherStrip::PT_quad:
00532 return _quads;
00533
00534 default:
00535 return _strips;
00536 }
00537
00538 default:
00539 egg_cat.fatal() << "Invalid strip status!\n";
00540 abort();
00541 }
00542
00543 return _strips;
00544 }
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557
00558 void EggMesher::
00559 build_sheets() {
00560 int first_row_id = 1;
00561
00562
00563 Strips pre_sheeted;
00564 pre_sheeted.splice(pre_sheeted.end(), _quads);
00565
00566 while (!pre_sheeted.empty()) {
00567
00568
00569 Strips::iterator best = pre_sheeted.begin();
00570
00571
00572
00573
00574 if ((*best)._row_id >= 0 &&
00575 (*best)._status == EggMesherStrip::MS_alive &&
00576 !(*best)._edges.empty()) {
00577
00578
00579
00580
00581 const EggMesherEdge *edge_a = (*best)._edges.front();
00582 const EggMesherEdge *edge_b = (*best).find_adjacent_edge(edge_a);
00583
00584 int num_prims_a = 0;
00585 int num_rows_a = 0;
00586 int first_row_id_a = first_row_id;
00587 (*best).measure_sheet(edge_a, true, num_prims_a, num_rows_a,
00588 first_row_id_a, 0, 0);
00589 first_row_id += num_rows_a;
00590 double avg_length_a = (double)num_prims_a / (double)num_rows_a;
00591
00592 int num_prims_b = 0;
00593 int num_rows_b = 0;
00594 int first_row_id_b = first_row_id;
00595 double avg_length_b;
00596 if (edge_b != NULL) {
00597 (*best).measure_sheet(edge_b, true, num_prims_b, num_rows_b,
00598 first_row_id_b, 0, 0);
00599 first_row_id += num_rows_b;
00600 avg_length_b = (double)num_prims_b / (double)num_rows_b;
00601 }
00602
00603
00604 if (edge_b != NULL && avg_length_b >= avg_length_a) {
00605
00606 (*best).cut_sheet(first_row_id_b, true, _vertex_pool);
00607
00608 } else {
00609
00610
00611
00612
00613
00614 num_prims_a = 0;
00615 num_rows_a = 0;
00616 first_row_id_a = first_row_id;
00617 (*best).measure_sheet(edge_a, true, num_prims_a, num_rows_a,
00618 first_row_id_a, 0, 0);
00619 first_row_id += num_rows_a;
00620
00621
00622 (*best).cut_sheet(first_row_id_a, true, _vertex_pool);
00623 }
00624 }
00625
00626
00627
00628 Strips &list = choose_strip_list(*best);
00629 list.splice(list.end(), pre_sheeted, best);
00630 }
00631 }
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644
00645 void EggMesher::
00646 find_fans() {
00647 PT(EggGroupNode) unrolled_tris = new EggGroup;
00648
00649
00650
00651
00652 Verts::iterator vi;
00653
00654 for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
00655 EdgePtrs &edges = (*vi).second;
00656
00657
00658
00659
00660
00661
00662
00663 if (edges.size() > 6) {
00664 int v = (*vi).first;
00665
00666
00667 typedef pvector<EggMesherFanMaker> FanMakers;
00668 FanMakers fans;
00669
00670 EdgePtrs::iterator ei;
00671 EggMesherEdge::Strips::iterator si;
00672 for (ei = edges.begin(); ei != edges.end(); ++ei) {
00673 for (si = (*ei)->_strips.begin();
00674 si != (*ei)->_strips.end();
00675 ++si) {
00676 EggMesherStrip *strip = *si;
00677 if (strip->_type == EggMesherStrip::PT_tri) {
00678 EggMesherFanMaker fan(v, strip, this);
00679 if (!fan._edges.empty()) {
00680 fans.push_back(fan);
00681 }
00682 }
00683 }
00684 }
00685
00686
00687 sort(fans.begin(), fans.end());
00688 fans.erase(unique(fans.begin(), fans.end()),
00689 fans.end());
00690
00691 FanMakers::iterator fi, fi2;
00692
00693
00694 bool joined_any;
00695 do {
00696 joined_any = false;
00697 for (fi = fans.begin(); fi != fans.end(); ++fi) {
00698 if (!(*fi).is_empty()) {
00699 fi2 = fi;
00700 for (++fi2; fi2 != fans.end(); ++fi2) {
00701 if (!(*fi2).is_empty()) {
00702 joined_any = (*fi).join(*fi2);
00703 }
00704 }
00705 }
00706 }
00707 } while (joined_any);
00708
00709 for (fi = fans.begin(); fi != fans.end(); ++fi) {
00710 if ((*fi).is_valid()) {
00711 (*fi).build(unrolled_tris);
00712 }
00713 }
00714 }
00715 }
00716
00717
00718
00719
00720
00721
00722 EggGroupNode::iterator ti;
00723 for (ti = unrolled_tris->begin(); ti != unrolled_tris->end(); ++ti) {
00724 add_polygon(DCAST(EggPolygon, (*ti)), EggMesherStrip::MO_fanpoly);
00725 }
00726 }
00727
00728
00729
00730
00731
00732
00733
00734
00735
00736
00737
00738
00739
00740
00741 void EggMesher::
00742 make_quads() {
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752
00753
00754 typedef pair<EggMesherStrip *, EggMesherStrip *> Pair;
00755 typedef pair<Pair, EggMesherEdge *> Matched;
00756 typedef pvector<Matched> SoulMates;
00757
00758 SoulMates soulmates;
00759
00760 EggMesherStrip *tri, *mate, *mate2;
00761 EggMesherEdge *common_edge, *common_edge2;
00762
00763 Strips::iterator si;
00764 for (si = _tris.begin(); si != _tris.end(); ++si) {
00765 tri = &(*si);
00766
00767 if (tri->_status == EggMesherStrip::MS_alive) {
00768 if (tri->find_ideal_mate(mate, common_edge, _vertex_pool)) {
00769
00770 if (mate->_type == EggMesherStrip::PT_tri &&
00771 mate->_status == EggMesherStrip::MS_alive &&
00772 mate->find_ideal_mate(mate2, common_edge2, _vertex_pool) &&
00773 mate2 == tri) {
00774
00775 soulmates.push_back(Matched(Pair(tri, mate), common_edge));
00776
00777 tri->_status = EggMesherStrip::MS_paired;
00778 mate->_status = EggMesherStrip::MS_paired;
00779 }
00780 }
00781 }
00782 }
00783
00784
00785
00786 SoulMates::iterator mi;
00787 for (mi = soulmates.begin(); mi != soulmates.end(); ++mi) {
00788 tri = (*mi).first.first;
00789 mate = (*mi).first.second;
00790 common_edge = (*mi).second;
00791
00792 nassertv(tri->_status == EggMesherStrip::MS_paired);
00793 nassertv(mate->_status == EggMesherStrip::MS_paired);
00794 tri->_status = EggMesherStrip::MS_alive;
00795 mate->_status = EggMesherStrip::MS_alive;
00796
00797 EggMesherStrip::mate_pieces(common_edge, *tri, *mate, _vertex_pool);
00798 tri->_origin = EggMesherStrip::MO_firstquad;
00799 }
00800
00801
00802 Strips::iterator next;
00803 si = _tris.begin();
00804 while (si != _tris.end()) {
00805 next = si;
00806 ++next;
00807
00808 Strips &list = choose_strip_list(*si);
00809 if (&list != &_tris) {
00810 list.splice(list.end(), _tris, si);
00811 }
00812
00813 si = next;
00814 }
00815 }
00816
00817
00818
00819
00820
00821
00822 void EggMesher::
00823 mesh_list(Strips &strips) {
00824 while (!strips.empty()) {
00825
00826
00827 Strips::iterator best = strips.begin();
00828
00829 if ((*best)._status == EggMesherStrip::MS_alive) {
00830 (*best).mate(_vertex_pool);
00831 }
00832
00833
00834
00835
00836 Strips &list = choose_strip_list(*best);
00837 list.splice(list.end(), strips, best);
00838 }
00839 }
00840
00841
00842
00843
00844
00845
00846 void EggMesher::
00847 make_random_color(LColor &color) {
00848 LVector3 rgb;
00849 PN_stdfloat len;
00850 do {
00851 for (int i = 0; i < 3; i++) {
00852 rgb[i] = (double)rand() / (double)RAND_MAX;
00853 }
00854 len = length(rgb);
00855
00856
00857 } while (len < .1 || len > 1.5);
00858
00859 color.set(rgb[0], rgb[1], rgb[2],
00860 0.25 + 0.75 * (double)rand() / (double)RAND_MAX);
00861 }
00862