00001
00002
00003
00004
00005
00006
00007 #include "mesh.h"
00008
00009 using namespace Mesh;
00010
00021 Face* Surf::create(Point *p0, Point *p1, Point *p2)
00022 {
00023 Vertex *v0 = new Vertex (p0); p0->add_vert(v0);
00024 Vertex *v1 = new Vertex (p1); p1->add_vert(v1);
00025 Vertex *v2 = new Vertex (p2); p2->add_vert(v2);
00026 add_vertex(v0);
00027 add_vertex(v1);
00028 add_vertex(v2);
00029
00030 Edge *e0 = new Edge (v0,v1);
00031 Edge *e1 = new Edge (v1,v2);
00032 Edge *e2 = new Edge (v2,v0);
00033 add_edge(e0);
00034 add_edge(e1);
00035 add_edge(e2);
00036
00037 Hedge *he0 = e0->hedge(0);
00038 Hedge *he1 = e1->hedge(0);
00039 Hedge *he2 = e2->hedge(0);
00040
00041 Face *f = new Face (this,he0,he1,he2);
00042 add_face(f);
00043
00044
00045 add_bdry(e0);
00046 e0->set_bdry(e0);
00047 e1->set_bdry(e0);
00048 e2->set_bdry(e0);
00049 he0->set_prev_on_bdry(he2);
00050 he1->set_prev_on_bdry(he0);
00051 he2->set_prev_on_bdry(he1);
00052
00053
00054 v0->set_star(he2);
00055 v1->set_star(he0);
00056 v2->set_star(he1);
00057
00058 return f;
00059 }
00060
00068 void Surf::destroy(Face *f)
00069 {
00070 Hedge *he0 = f->hedge(0);
00071 Hedge *he1 = f->hedge(1);
00072 Hedge *he2 = f->hedge(2);
00073
00074 Vertex *v0 = he0->org();
00075 Vertex *v1 = he1->org();
00076 Vertex *v2 = he2->org();
00077
00078 Edge *e0 = he0->edge();
00079 Edge *e1 = he1->edge();
00080 Edge *e2 = he2->edge();
00081 Edge *eb = he0->mate()->edge();
00082
00083 del_vertex(v0);
00084 del_vertex(v1);
00085 del_vertex(v2);
00086
00087 v0->p()->del_vert(v0);
00088 v1->p()->del_vert(v1);
00089 v2->p()->del_vert(v2);
00090
00091 delete v0;
00092 delete v1;
00093 delete v2;
00094
00095 del_bdry(eb);
00096 del_edge(e0);
00097 del_edge(e1);
00098 del_edge(e2);
00099
00100 delete e0;
00101 delete e1;
00102 delete e2;
00103
00104 del_face(f);
00105 delete f;
00106 }
00107
00115 Edge* Surf::glue(Hedge *e1, Hedge *e2)
00116 {
00117 Surf* s1 = e1->face()->surf();
00118 Surf* s2 = e2->face()->surf();
00119 Vertex* v1 = e1->org();
00120 Vertex* v2 = e1->dst();
00121 Vertex* v3 = e2->org();
00122 Vertex* v4 = e2->dst();
00123 Edge* b1 = e1->get_bdry();
00124 Edge* b2 = e2->get_bdry();
00125
00126 if (s1 != s2)
00127 return attach_handle_0(e1, e2);
00128 if (b1 != b2)
00129 return attach_handle_1(e1, e2);
00130 if (v1 == v4) {
00131 if (v2 != v3)
00132 return attach_handle_3(e1, e2);
00133 else
00134 return attach_handle_4(e1, e2);
00135 }
00136 if (v2 == v3)
00137 return attach_handle_3(e1, e2);
00138 return attach_handle_2(e1, e2);
00139 }
00140
00148 Edge* Surf::unglue(Hedge *e1, Hedge *e2)
00149 {
00150 Vertex* v1 = e1->org();
00151 Vertex* v2 = e1->dst();
00152
00153 if (!v1->is_bdry() && !v2->is_bdry())
00154 return detach_handle_4(e1, e2);
00155 if (v1->is_bdry() && !v2->is_bdry())
00156 return detach_handle_3(e1, e2);
00157 if (!v1->is_bdry() && v2->is_bdry())
00158 return detach_handle_3(e1, e2);
00159 if (v1->is_bdry() && v2->is_bdry()) {
00160 if (v2->star_first()->mate()->edge() != v1->star_first()->mate()->edge())
00161 return detach_handle_2(e1, e2);
00162 else
00163 return detach_handle_1(e1, e2);
00164 }
00165 return NULL;
00166 }
00167
00175 Edge* Surf::attach_handle_0(Hedge *he1, Hedge *he2)
00176 {
00177 Face *f2 = he2->face();
00178 Edge *e1 = he1->edge();
00179 Edge *e2 = he2->edge();
00180 Hedge *mhe1 = he1->mate();
00181 Hedge *nhe2 = he2->next();
00182 Hedge *phe2 = he2->prev();
00183 Vertex *v1 = he1->org();
00184 Vertex *v2 = he1->dst();
00185 Vertex *v3 = he2->org();
00186 Vertex *v4 = he2->dst();
00187 Edge *eb1 = he1->get_bdry();
00188 Edge *eb2 = he2->get_bdry();
00189 Hedge *he;
00190
00191 transfer_cells(he2->face()->surf());
00192
00193 if (eb1 == e1)
00194 {
00195 del_bdry(eb1);
00196 he = he1->prev_on_bdry();
00197 eb1 = he->edge();
00198 do
00199 {
00200 he->edge()->set_bdry(eb1);
00201 he = he->prev_on_bdry();
00202 }
00203 while(he != he1);
00204 add_bdry(eb1);
00205 }
00206
00207 he = he2->prev_on_bdry();
00208 do
00209 {
00210 he->edge()->set_bdry(eb1);
00211 he = he->prev_on_bdry();
00212 }
00213 while(he != he2);
00214 del_bdry(eb2);
00215
00216 he = he2;
00217 do
00218 {
00219 he->next()->set_org(v1);
00220 he = he->next()->mate();
00221 }
00222 while(!(he->next()->edge()->is_bdry()));
00223 del_vertex(v4);
00224 delete v4;
00225
00226 he = he2->prev_on_bdry();
00227 do
00228 {
00229 he->next()->set_org(v2);
00230 he = he->next()->mate();
00231 }
00232 while(!(he->next()->edge()->is_bdry()));
00233 del_vertex(v3);
00234 delete v3;
00235
00236 mhe1->set_edge(e1);
00237 mhe1->set_face(f2);
00238 f2->set_hedge(0,mhe1);
00239 f2->set_hedge(1,nhe2);
00240 f2->set_hedge(2,phe2);
00241
00242 del_edge(e2);
00243 delete e2;
00244
00245 return e1;
00246 }
00247
00255 Edge* Surf::attach_handle_1(Hedge *he1, Hedge *he2)
00256 {
00257 Face *f2 = he2->face();
00258 Edge *e1 = he1->edge();
00259 Edge *e2 = he2->edge();
00260 Hedge *mhe1 = he1->mate();
00261 Hedge *nhe2 = he2->next();
00262 Hedge *phe2 = he2->prev();
00263 Vertex *v1 = he1->org();
00264 Vertex *v2 = he1->dst();
00265 Vertex *v3 = he2->org();
00266 Vertex *v4 = he2->dst();
00267 Edge *eb1 = he1->get_bdry();
00268 Edge *eb2 = he2->get_bdry();
00269 Hedge *he;
00270
00271 if (eb1 == e1)
00272 {
00273 del_bdry(eb1);
00274 he = he1->prev_on_bdry();
00275 eb1 = he->edge();
00276 do
00277 {
00278 he->edge()->set_bdry(eb1);
00279 he = he->prev_on_bdry();
00280 }
00281 while(he != he1);
00282 add_bdry(eb1);
00283 }
00284
00285 he = he2->prev_on_bdry();
00286 do
00287 {
00288 he->edge()->set_bdry(eb1);
00289 he = he->prev_on_bdry();
00290 }
00291 while(he != he2);
00292 del_bdry(eb2);
00293
00294 he = he2->next();
00295 he->set_org(v1);
00296 while(!(he->edge()->is_bdry()))
00297 {
00298 he = he->mate()->next();
00299 he->set_org(v1);
00300 }
00301 he->set_prev_on_bdry(v1->star_first());
00302 del_vertex(v4);
00303 v4->p()->del_vert(v4);
00304 delete v4;
00305
00306
00307 he = he2->prev_on_bdry();
00308 he->mate()->set_org(v2);
00309 while(!(he->next()->edge()->is_bdry())){
00310 he->next()->set_org(v2);
00311 he = he->next()->mate();
00312 }
00313 v2->set_star(v3->star_first());
00314 del_vertex(v3);
00315 v3->p()->del_vert(v3);
00316 delete v3;
00317
00318 he = he1->next();
00319 while(!(he->edge()->is_bdry()))
00320 he = he->mate()->next();
00321 he->set_prev_on_bdry(v2->star_first());
00322
00323
00324 mhe1->set_edge(e1);
00325 mhe1->set_face(f2);
00326 f2->set_hedge(0,mhe1);
00327 f2->set_hedge(1,nhe2);
00328 f2->set_hedge(2,phe2);
00329
00330 del_edge(e2);
00331 delete e2;
00332
00333 return e1;
00334 }
00335
00343 Edge* Surf::attach_handle_2(Hedge *he1, Hedge *he2)
00344 {
00345 Face *f2 = he2->face();
00346 Edge *e1 = he1->edge();
00347 Edge *e2 = he2->edge();
00348 Hedge *mhe1 = he1->mate();
00349 Hedge *nhe2 = he2->next();
00350 Hedge *phe2 = he2->prev();
00351 Vertex *v1 = he1->org();
00352 Vertex *v2 = he1->dst();
00353 Vertex *v3 = he2->org();
00354 Vertex *v4 = he2->dst();
00355 Edge *eb = he1->get_bdry();
00356 Hedge *he;
00357
00358 del_bdry(eb);
00359
00360 he = he2->prev_on_bdry();
00361 eb = he->edge();
00362 do
00363 {
00364 he->edge()->set_bdry(eb);
00365 he = he->prev_on_bdry();
00366 }
00367 while(he != he1);
00368 add_bdry(eb);
00369
00370 he = he1->prev_on_bdry();
00371 eb = he->edge();
00372 do
00373 {
00374 he->edge()->set_bdry(eb);
00375 he = he->prev_on_bdry();
00376 }
00377 while(he != he2);
00378 add_bdry(eb);
00379
00380 he = he2->next();
00381 he->set_org(v1);
00382 while(!(he->edge()->is_bdry()))
00383 {
00384 he = he->mate()->next();
00385 he->set_org(v1);
00386 }
00387 he->set_prev_on_bdry(v1->star_first());
00388 del_vertex(v4);
00389 v4->p()->del_vert(v4);
00390 delete v4;
00391
00392
00393 he = he2->prev_on_bdry();
00394 he->mate()->set_org(v2);
00395 while(!(he->next()->edge()->is_bdry())){
00396 he->next()->set_org(v2);
00397 he = he->next()->mate();
00398 }
00399 v2->set_star(v3->star_first());
00400 del_vertex(v3);
00401 v3->p()->del_vert(v3);
00402 delete v3;
00403
00404 he = he1->next();
00405 while(!(he->edge()->is_bdry()))
00406 he = he->mate()->next();
00407 he->set_prev_on_bdry(v2->star_first());
00408
00409 mhe1->set_edge(e1);
00410 mhe1->set_face(f2);
00411 f2->set_hedge(0,mhe1);
00412 f2->set_hedge(1,nhe2);
00413 f2->set_hedge(2,phe2);
00414
00415 del_edge(e2);
00416 delete e2;
00417
00418 return e1;
00419 }
00420
00427 Edge* Surf::attach_handle_3(Hedge *he1, Hedge *he2)
00428 {
00429
00430 Face *f2 = he2->face();
00431 Edge *e1 = he1->edge();
00432 Edge *e2 = he2->edge();
00433 Hedge *mhe1 = he1->mate();
00434 Hedge *nhe2 = he2->next();
00435 Hedge *phe2 = he2->prev();
00436 Vertex *v1 = he1->org();
00437 Vertex *v2 = he1->dst();
00438 Vertex *v3 = he2->org();
00439 Vertex *v4 = he2->dst();
00440 Edge *eb = he1->get_bdry();
00441 Hedge *he;
00442
00443 if (he1 == he2->prev_on_bdry()){
00444
00445 if ((eb == e1) || (eb == e2))
00446 {
00447 del_bdry(eb);
00448 he = he1->prev_on_bdry();
00449 eb = he->edge();
00450 do
00451 {
00452 he->edge()->set_bdry(eb);
00453 he = he->prev_on_bdry();
00454 }
00455 while(he != he2);
00456 add_bdry(eb);
00457 }
00458
00459 he = he2->next();
00460 he->set_org(v1);
00461 while(!(he->edge()->is_bdry()))
00462 {
00463 he = he->mate()->next();
00464 he->set_org(v1);
00465 }
00466 he->set_prev_on_bdry(v1->star_first());
00467 del_vertex(v4);
00468 v4->p()->del_vert(v4);
00469 delete v4;
00470
00471 }
00472 else {
00473 if ((eb == e1) || (eb == e2))
00474 {
00475 del_bdry(eb);
00476 he = he1->prev_on_bdry()->prev_on_bdry();
00477 eb = he->edge();
00478 do
00479 {
00480 he->edge()->set_bdry(eb);
00481 he = he->prev_on_bdry();
00482 }
00483 while(he != he1);
00484 add_bdry(eb);
00485 }
00486
00487 v2->set_star(v3->star_first());
00488 v1->set_star(mhe1);
00489 he = he2->prev();
00490 he->mate()->set_org(v2);
00491 while(!(he->edge()->is_bdry()))
00492 {
00493 he = he->mate()->prev();
00494 he->mate()->set_org(v2);
00495 }
00496
00497 del_vertex(v3);
00498 v3->p()->del_vert(v3);
00499 delete v3;
00500
00501 he = he1->next();
00502 while(!(he->edge()->is_bdry()))
00503 he = he->mate()->next();
00504 he->set_prev_on_bdry(v2->star_first());
00505 }
00506
00507 mhe1->set_edge(e1);
00508 mhe1->set_face(f2);
00509 f2->set_hedge(0,mhe1);
00510 f2->set_hedge(1,nhe2);
00511 f2->set_hedge(2,phe2);
00512
00513 del_edge(e2);
00514 delete e2;
00515
00516 return e1;
00517 }
00518
00526 Edge* Surf::attach_handle_4(Hedge *he1, Hedge *he2)
00527 {
00528 Face *f2 = he2->face();
00529 Edge *e1 = he1->edge();
00530 Edge *e2 = he2->edge();
00531 Hedge *mhe1 = he1->mate();
00532 Hedge *nhe2 = he2->next();
00533 Hedge *phe2 = he2->prev();
00534 Vertex *v1 = he1->org();
00535
00536 del_bdry(he1->get_bdry());
00537
00538 mhe1->set_edge(e1);
00539 mhe1->set_face(f2);
00540 f2->set_hedge(0,mhe1);
00541 f2->set_hedge(1,nhe2);
00542 f2->set_hedge(2,phe2);
00543
00544 v1->set_star(mhe1);
00545 del_edge(e2);
00546 delete e2;
00547
00548 return e1;
00549 }
00550
00551
00552
00560 Edge* Surf::detach_handle_1(Hedge *he1, Hedge *he2)
00561 {
00562 Hedge *he, *he2_old;
00563 Face *f2 = he2->face();
00564 Vertex *v1 = he1->org();
00565 Vertex *v2 = he1->dst();
00566 Edge *eb1 = v1->star_first()->get_bdry();
00567 Edge *eb2;
00568 Vertex *v3 = new Vertex(v2->p());
00569 Vertex *v4 = new Vertex(v1->p());
00570 v3->p()->add_vert(v3);
00571 v4->p()->add_vert(v4);
00572 add_vertex(v3);
00573 add_vertex(v4);
00574
00575 Edge *ne = new Edge(v3, v4);
00576 he2_old = he2;
00577 he2 = ne->hedge(0);
00578 eb2 = ne;
00579 add_edge(ne);
00580
00581
00582 if (f2->reuse(he2_old, he2)<0) return NULL;
00583 he2_old->set_face(NULL);
00584
00585
00586 ne->set_bdry(eb2);
00587 he1->edge()->set_bdry(eb1);
00588
00589 add_bdry(eb2);
00590
00591 he = v2->star_first();
00592 do
00593 {
00594 he->edge()->set_bdry(eb2);
00595 he = he->prev_on_bdry();
00596 }
00597 while(he != v1->star_first());
00598
00599
00600
00601 he1->set_prev_on_bdry(v1->star_first());
00602
00603 he = he1->next();
00604 while(!(he->edge()->is_bdry()))
00605 he = he->mate()->next();
00606 he->set_prev_on_bdry(he1);
00607
00608 he = he2->prev();
00609 while(!(he->edge()->is_bdry())){
00610 he->mate()->set_org(v3);
00611 he = he->mate()->prev();
00612 }
00613 he->mate()->set_org(v3);
00614 he2->set_prev_on_bdry(he);
00615 v3->set_star(he);
00616
00617 he = he2->next();
00618 he->set_org(v4);
00619 while(!(he->edge()->is_bdry())){
00620 he = he->mate()->next();
00621 he->set_org(v4);
00622 }
00623 he->set_prev_on_bdry(he2);
00624
00625
00626 v2->set_star(he1);
00627 v4->set_star(he2);
00628
00629 return ne;
00630 }
00631
00639 Edge* Surf::detach_handle_2(Hedge *he1, Hedge *he2)
00640 {
00641 Hedge *he, *he2_old;
00642 Face *f2 = he2->face();
00643 Vertex *v1 = he1->org();
00644 Vertex *v2 = he1->dst();
00645 Edge *eb1 = v1->star_first()->get_bdry();
00646 Edge *eb2 = v2->star_first()->get_bdry();
00647 Vertex *v3 = new Vertex(v2->p());
00648 Vertex *v4 = new Vertex(v1->p());
00649 v3->p()->add_vert(v3);
00650 v4->p()->add_vert(v4);
00651 add_vertex(v3);
00652 add_vertex(v4);
00653
00654 Edge *ne = new Edge(v3, v4);
00655 he2_old = he2;
00656 he2 = ne->hedge(0);
00657 add_edge(ne);
00658
00659
00660 if (f2->reuse(he2_old, he2)<0) return NULL;
00661 he2_old->set_face(NULL);
00662
00663
00664 ne->set_bdry(eb1);
00665 he1->edge()->set_bdry(eb1);
00666
00667 del_bdry(eb2);
00668 he = v2->star_first();
00669 do
00670 {
00671 he->edge()->set_bdry(eb1);
00672 he = he->prev_on_bdry();
00673 }
00674 while(he != v2->star_first());
00675
00676
00677
00678 he1->set_prev_on_bdry(v1->star_first());
00679
00680 he = he1->next();
00681 while(!(he->edge()->is_bdry()))
00682 he = he->mate()->next();
00683 he->set_prev_on_bdry(he1);
00684
00685 he = he2->prev();
00686 while(!(he->edge()->is_bdry())){
00687 he->mate()->set_org(v3);
00688 he = he->mate()->prev();
00689 }
00690 he->mate()->set_org(v3);
00691 he2->set_prev_on_bdry(he);
00692 v3->set_star(he);
00693
00694 he = he2->next();
00695 he->set_org(v4);
00696 while(!(he->edge()->is_bdry())){
00697 he = he->mate()->next();
00698 he->set_org(v4);
00699 }
00700 he->set_prev_on_bdry(he2);
00701
00702
00703 v2->set_star(he1);
00704 v4->set_star(he2);
00705
00706 return ne;
00707 }
00708
00715 Edge* Surf::detach_handle_3(Hedge *he1, Hedge *he2)
00716 {
00717 if(he1->org()->is_bdry()){
00718 Hedge *temp = he1;
00719 he1 = he2;
00720 he2 = temp;
00721 }
00722 Hedge *he2_old, *he;
00723 Face *f2 = he2->face();
00724 Vertex *v1 = he1->org();
00725 Vertex *v2 = he1->dst();
00726 Edge *eb = v2->star_first()->get_bdry();
00727 Vertex *v3 = new Vertex(v2->p());
00728 v3->p()->add_vert(v3);
00729 add_vertex(v3);
00730
00731 Edge *ne = new Edge(v3, v1);
00732 he2_old = he2;
00733 he2 = ne->hedge(0);
00734 add_edge(ne);
00735
00736
00737 if (f2->reuse(he2_old, he2)<0) return NULL;
00738 he2_old->set_face(NULL);
00739
00740
00741 ne->set_bdry(eb);
00742 he1->edge()->set_bdry(eb);
00743
00744 he = he2->prev();
00745 while(!(he->edge()->is_bdry())){
00746 he->mate()->set_org(v3);
00747 he = he->mate()->prev();
00748 }
00749 he->mate()->set_org(v3);
00750 he2->set_prev_on_bdry(he);
00751 v3->set_star(he);
00752
00753
00754 he1->set_prev_on_bdry(he2);
00755 he = he1->next();
00756 while(!(he->edge()->is_bdry()))
00757 he = he->mate()->next();
00758 he->set_prev_on_bdry(he1);
00759
00760
00761 v1->set_star(he2);
00762 v2->set_star(he1);
00763 return ne;
00764 }
00765
00773 Edge* Surf::detach_handle_4(Hedge *he1, Hedge *he2)
00774 {
00775 Hedge *he2_old;
00776 Face *f2 = he2->face();
00777 Vertex *v1 = he1->org();
00778 Vertex *v2 = he1->dst();
00779
00780 Edge *ne = new Edge(v2, v1);
00781 he2_old = he2;
00782 he2 = ne->hedge(0);
00783 add_edge(ne);
00784 add_bdry(ne);
00785
00786
00787 if (f2->reuse(he2_old, he2)<0) return NULL;
00788 he2_old->set_face(NULL);
00789
00790
00791 ne->set_bdry(ne);
00792 he1->edge()->set_bdry(ne);
00793
00794
00795 he1->set_prev_on_bdry(he2);
00796 he2->set_prev_on_bdry(he1);
00797
00798
00799 v1->set_star(he2);
00800 v2->set_star(he1);
00801
00802 return ne;
00803 }