1 /* 2 ** License Applicability. Except to the extent portions of this file are 3 ** made subject to an alternative license as permitted in the SGI Free 4 ** Software License B, Version 1.1 (the "License"), the contents of this 5 ** file are subject only to the provisions of the License. You may not use 6 ** this file except in compliance with the License. You may obtain a copy 7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: 9 ** 10 ** http://oss.sgi.com/projects/FreeB 11 ** 12 ** Note that, as provided in the License, the Software is distributed on an 13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS 14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND 15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A 16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. 17 ** 18 ** Original Code. The Original Code is: OpenGL Sample Implementation, 19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, 20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. 21 ** Copyright in any portions created by third parties is as indicated 22 ** elsewhere herein. All Rights Reserved. 23 ** 24 ** Additional Notice Provisions: The application programming interfaces 25 ** established by SGI in conjunction with the Original Code are The 26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released 27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version 28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X 29 ** Window System(R) (Version 1.3), released October 19, 1998. This software 30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation 31 ** published by SGI, but has not been independently verified as being 32 ** compliant with the OpenGL(R) version 1.2.1 Specification. 33 ** 34 */ 35 /* 36 */ 37 38 //#include <stdlib.h> 39 //#include <stdio.h> 40 #include <math.h> 41 //#include "zlassert.h" 42 #include "polyDBG.h" 43 44 #ifdef __WATCOMC__ 45 #pragma warning 14 10 46 #pragma warning 391 10 47 #pragma warning 726 10 48 #endif 49 50 static Real area(Real A[2], Real B[2], Real C[2]) 51 { 52 Real Bx, By, Cx, Cy; 53 Bx = B[0] - A[0]; 54 By = B[1] - A[1]; 55 Cx = C[0] - A[0]; 56 Cy = C[1] - A[1]; 57 return Bx*Cy - Cx*By; 58 } 59 60 Int DBG_isConvex(directedLine *poly) 61 { 62 directedLine* temp; 63 if(area(poly->head(), poly->tail(), poly->getNext()->tail()) < 0.00000) 64 return 0; 65 for(temp = poly->getNext(); temp != poly; temp = temp->getNext()) 66 { 67 if(area(temp->head(), temp->tail(), temp->getNext()->tail()) < 0.00000) 68 return 0; 69 } 70 return 1; 71 } 72 73 Int DBG_is_U_monotone(directedLine* poly) 74 { 75 Int n_changes = 0; 76 Int prev_sign; 77 Int cur_sign; 78 directedLine* temp; 79 cur_sign = compV2InX(poly->tail(), poly->head()); 80 81 n_changes = (compV2InX(poly->getPrev()->tail(), poly->getPrev()->head()) 82 != cur_sign); 83 84 for(temp = poly->getNext(); temp != poly; temp = temp->getNext()) 85 { 86 prev_sign = cur_sign; 87 cur_sign = compV2InX(temp->tail(), temp->head()); 88 89 if(cur_sign != prev_sign) 90 n_changes++; 91 } 92 93 if(n_changes ==2) return 1; 94 else return 0; 95 } 96 97 /*if u-monotone, and there is a long horizontal edge*/ 98 Int DBG_is_U_direction(directedLine* poly) 99 { 100 /* 101 if(! DBG_is_U_monotone(poly)) 102 return 0; 103 */ 104 Int V_count = 0; 105 Int U_count = 0; 106 directedLine* temp; 107 if( fabs(poly->head()[0] - poly->tail()[0]) <= fabs(poly->head()[1]-poly->tail()[1])) 108 V_count += poly->get_npoints(); 109 else 110 U_count += poly->get_npoints(); 111 /* 112 else if(poly->head()[1] == poly->tail()[1]) 113 U_count += poly->get_npoints(); 114 */ 115 for(temp = poly->getNext(); temp != poly; temp = temp->getNext()) 116 { 117 if( fabs(temp->head()[0] - temp->tail()[0]) <= fabs(temp->head()[1]-temp->tail()[1])) 118 V_count += temp->get_npoints(); 119 else 120 U_count += temp->get_npoints(); 121 /* 122 if(temp->head()[0] == temp->tail()[0]) 123 V_count += temp->get_npoints(); 124 else if(temp->head()[1] == temp->tail()[1]) 125 U_count += temp->get_npoints(); 126 */ 127 } 128 129 if(U_count > V_count) return 1; 130 else return 0; 131 } 132 133 /*given two line segments, determine whether 134 *they intersect each other or not. 135 *return 1 if they do, 136 *return 0 otherwise 137 */ 138 Int DBG_edgesIntersect(directedLine* l1, directedLine* l2) 139 { 140 if(l1->getNext() == l2) 141 { 142 if(area(l1->head(), l1->tail(), l2->tail()) == 0) //colinear 143 { 144 if( (l1->tail()[0] - l1->head()[0])*(l2->tail()[0]-l2->head()[0]) + 145 (l1->tail()[1] - l1->head()[1])*(l2->tail()[1]-l2->head()[1]) >=0) 146 return 0; //not intersect 147 else 148 return 1; 149 } 150 //else we use the normal code 151 } 152 else if(l1->getPrev() == l2) 153 { 154 if(area(l2->head(), l2->tail(), l1->tail()) == 0) //colinear 155 { 156 if( (l2->tail()[0] - l2->head()[0])*(l1->tail()[0]-l1->head()[0]) + 157 (l2->tail()[1] - l2->head()[1])*(l1->tail()[1]-l1->head()[1]) >=0) 158 return 0; //not intersect 159 else 160 return 1; 161 } 162 //else we use the normal code 163 } 164 else //the two edges are not connected 165 { 166 if((l1->head()[0] == l2->head()[0] && 167 l1->head()[1] == l2->head()[1]) || 168 (l1->tail()[0] == l2->tail()[0] && 169 l1->tail()[1] == l2->tail()[1])) 170 return 1; 171 172 } 173 174 175 if( 176 ( 177 area(l1->head(), l1->tail(), l2->head()) 178 * 179 area(l1->head(), l1->tail(), l2->tail()) 180 < 0 181 ) 182 && 183 ( 184 area(l2->head(), l2->tail(), l1->head()) 185 *area(l2->head(), l2->tail(), l1->tail()) 186 < 0 187 ) 188 ) 189 return 1; 190 else 191 return 0; 192 } 193 194 /*whether AB and CD intersect 195 *return 1 if they do 196 *retur 0 otheriwse 197 */ 198 Int DBG_edgesIntersectGen(Real A[2], Real B[2], Real C[2], Real D[2]) 199 { 200 if( 201 ( 202 area(A, B, C) * area(A,B,D) <0 203 ) 204 && 205 ( 206 area(C,D,A) * area(C,D,B) < 0 207 ) 208 ) 209 return 1; 210 else 211 return 0; 212 } 213 214 /*determien whether (A,B) interesect chain[start] to [end] 215 */ 216 Int DBG_intersectChain(vertexArray* chain, Int start, Int end, Real A[2], Real B[2]) 217 { 218 Int i; 219 for(i=start; i<=end-2; i++) 220 if(DBG_edgesIntersectGen(chain->getVertex(i), chain->getVertex(i+1), A, B)) 221 return 1; 222 223 return 0; 224 } 225 226 /*determine whether a polygon intersect itself or not 227 *return 1 is it does, 228 * 0 otherwise 229 */ 230 Int DBG_polygonSelfIntersect(directedLine* poly) 231 { 232 directedLine* temp1; 233 directedLine* temp2; 234 temp1=poly; 235 for(temp2=temp1->getNext(); temp2 != temp1; temp2=temp2->getNext()) 236 { 237 if(DBG_edgesIntersect(temp1, temp2)) 238 { 239 return 1; 240 } 241 242 } 243 244 for(temp1=poly->getNext(); temp1 != poly; temp1 = temp1->getNext()) 245 for(temp2=temp1->getNext(); temp2 != temp1; temp2=temp2->getNext()) 246 { 247 if(DBG_edgesIntersect(temp1, temp2)) 248 { 249 return 1; 250 } 251 } 252 return 0; 253 } 254 255 /*check whether a line segment intersects a polygon 256 */ 257 Int DBG_edgeIntersectPoly(directedLine* edge, directedLine* poly) 258 { 259 directedLine* temp; 260 if(DBG_edgesIntersect(edge, poly)) 261 return 1; 262 for(temp=poly->getNext(); temp != poly; temp=temp->getNext()) 263 if(DBG_edgesIntersect(edge, temp)) 264 return 1; 265 return 0; 266 } 267 268 /*check whether two polygons intersect 269 */ 270 Int DBG_polygonsIntersect(directedLine* p1, directedLine* p2) 271 { 272 directedLine* temp; 273 if(DBG_edgeIntersectPoly(p1, p2)) 274 return 1; 275 for(temp=p1->getNext(); temp!= p1; temp = temp->getNext()) 276 if(DBG_edgeIntersectPoly(temp, p2)) 277 return 1; 278 return 0; 279 } 280 281 /*check whether there are polygons intersecting each other in 282 *a list of polygons 283 */ 284 Int DBG_polygonListIntersect(directedLine* pList) 285 { 286 directedLine *temp; 287 for(temp=pList; temp != NULL; temp = temp->getNextPolygon()) 288 if(DBG_polygonSelfIntersect(temp)) 289 return 1; 290 directedLine* temp2; 291 for(temp=pList; temp!=NULL; temp=temp->getNextPolygon()) 292 { 293 for(temp2=temp->getNextPolygon(); temp2 != NULL; temp2=temp2->getNextPolygon()) 294 if(DBG_polygonsIntersect(temp, temp2)) 295 return 1; 296 } 297 298 return 0; 299 } 300 301 302 Int DBG_isCounterclockwise(directedLine* poly) 303 { 304 return (poly->polyArea() > 0); 305 } 306 307 /*ray: v0 with direction (dx,dy). 308 *edge: v1-v2. 309 * the extra point v10[2] is given for the information at 310 *v1. Basically this edge is connectd to edge 311 * v10-v1. If v1 is on the ray, 312 * then we need v10 to determine whether this ray intersects 313 * the edge or not (that is, return 1 or return 0). 314 * If v1 is on the ray, then if v2 and v10 are on the same side of the ray, 315 * we return 0, otherwise return 1. 316 *For v2, if v2 is on the ray, we always return 0. 317 *Notice that v1 and v2 are not symmetric. So the edge is directed!!! 318 * The purpose for this convention is such that: a point is inside a polygon 319 * if and only if it intersets with odd number of edges. 320 */ 321 Int DBG_rayIntersectEdge(Real v0[2], Real dx, Real dy, Real v10[2], Real v1[2], Real v2[2]) 322 { 323 /* 324 if( (v1[1] >= v0[1] && v2[1]<= v0[1] ) 325 ||(v2[1] >= v0[1] && v1[1]<= v0[1] ) 326 ) 327 printf("rayIntersectEdge, *********\n"); 328 */ 329 330 Real denom = (v2[0]-v1[0])*(-dy) - (v2[1]-v1[1]) * (-dx); 331 Real nomRay = (v2[0]-v1[0]) * (v0[1] - v1[1]) - (v2[1]-v1[1])*(v0[0]-v1[0]); 332 Real nomEdge = (v0[0]-v1[0]) * (-dy) - (v0[1]-v1[1])*(-dx); 333 334 335 /*if the ray is parallel to the edge, return 0: not intersect*/ 336 if(denom == 0.0) 337 return 0; 338 339 /*if v0 is on the edge, return 0: not intersect*/ 340 if(nomRay == 0.0) 341 return 0; 342 343 /*if v1 is on the positive ray, and the neighbor of v1 crosses the ray 344 *return 1: intersect 345 */ 346 if(nomEdge == 0) 347 { /*v1 is on the positive or negative ray*/ 348 349 /* 350 printf("v1 is on the ray\n"); 351 */ 352 353 if(dx*(v1[0]-v0[0])>=0 && dy*(v1[1]-v0[1])>=0) /*v1 on positive ray*/ 354 { 355 if(area(v0, v1, v10) * area(v0, v1, v2) >0) 356 return 0; 357 else 358 return 1; 359 } 360 else /*v1 on negative ray*/ 361 return 0; 362 } 363 364 /*if v2 is on the ray, always return 0: not intersect*/ 365 if(nomEdge == denom) { 366 /* printf("v2 is on the ray\n");*/ 367 return 0; 368 } 369 370 /*finally */ 371 if(denom*nomRay>0 && denom*nomEdge>0 && nomEdge/denom <=1.0) 372 return 1; 373 return 0; 374 } 375 376 377 /*return the number of intersections*/ 378 Int DBG_rayIntersectPoly(Real v0[2], Real dx, Real dy, directedLine* poly) 379 { 380 directedLine* temp; 381 Int count=0; 382 if(DBG_rayIntersectEdge(v0, dx, dy, poly->getPrev()->head(), poly->head(), poly->tail())) 383 count++; 384 385 for(temp=poly->getNext(); temp != poly; temp = temp->getNext()) 386 if(DBG_rayIntersectEdge(v0, dx, dy, temp->getPrev()->head(), temp->head(), temp->tail())) 387 count++; 388 /*printf("ray intersect poly: count=%i\n", count);*/ 389 return count; 390 } 391 392 Int DBG_pointInsidePoly(Real v[2], directedLine* poly) 393 { 394 /* 395 printf("enter pointInsidePoly , v=(%f,%f)\n", v[0], v[1]); 396 printf("the polygon is\n"); 397 poly->printList(); 398 */ 399 /*for debug purpose*/ 400 assert( (DBG_rayIntersectPoly(v,1,0,poly) % 2 ) 401 == (DBG_rayIntersectPoly(v,1,Real(0.1234), poly) % 2 ) 402 ); 403 if(DBG_rayIntersectPoly(v, 1, 0, poly) % 2 == 1) 404 return 1; 405 else 406 return 0; 407 } 408 409 /*return the number of polygons which contain thie polygon 410 * as a subset 411 */ 412 Int DBG_enclosingPolygons(directedLine* poly, directedLine* list) 413 { 414 directedLine* temp; 415 Int count=0; 416 /* 417 printf("%i\n", DBG_pointInsidePoly(poly->head(), 418 list->getNextPolygon() 419 ->getNextPolygon() 420 ->getNextPolygon() 421 ->getNextPolygon() 422 )); 423 */ 424 425 for(temp = list; temp != NULL; temp = temp->getNextPolygon()) 426 { 427 if(poly != temp) 428 if(DBG_pointInsidePoly(poly->head(), temp)) 429 count++; 430 /* printf("count=%i\n", count);*/ 431 } 432 return count; 433 } 434 435 void DBG_reverse(directedLine* poly) 436 { 437 if(poly->getDirection() == INCREASING) 438 poly->putDirection(DECREASING); 439 else 440 poly->putDirection(INCREASING); 441 442 directedLine* oldNext = poly->getNext(); 443 poly->putNext(poly->getPrev()); 444 poly->putPrev(oldNext); 445 446 directedLine* temp; 447 for(temp=oldNext; temp!=poly; temp = oldNext) 448 { 449 if(temp->getDirection() == INCREASING) 450 temp->putDirection(DECREASING); 451 else 452 temp->putDirection(INCREASING); 453 454 oldNext = temp->getNext(); 455 temp->putNext(temp->getPrev()); 456 temp->putPrev(oldNext); 457 } 458 printf("reverse done\n"); 459 } 460 461 Int DBG_checkConnectivity(directedLine *polygon) 462 { 463 if(polygon == NULL) return 1; 464 directedLine* temp; 465 if(polygon->head()[0] != polygon->getPrev()->tail()[0] || 466 polygon->head()[1] != polygon->getPrev()->tail()[1]) 467 return 0; 468 for(temp=polygon->getNext(); temp != polygon; temp=temp->getNext()) 469 { 470 if(temp->head()[0] != temp->getPrev()->tail()[0] || 471 temp->head()[1] != temp->getPrev()->tail()[1]) 472 return 0; 473 } 474 return 1; 475 } 476 477 /*print out error message. 478 *If it cannot modify the polygon list to make it satify the 479 *requirements, return 1. 480 *otherwise modify the polygon list, and return 0 481 */ 482 Int DBG_check(directedLine *polyList) 483 { 484 directedLine* temp; 485 if(polyList == NULL) return 0; 486 487 /*if there are intersections, print out error message 488 */ 489 if(DBG_polygonListIntersect(polyList)) 490 { 491 fprintf(stderr, "DBG_check: there are self intersections, don't know to modify the polygons\n"); 492 return 1; 493 } 494 495 /*check the connectivity of each polygon*/ 496 for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon()) 497 { 498 if(! DBG_checkConnectivity(temp)) 499 { 500 fprintf(stderr, "DBG_check, polygon not connected\n"); 501 return 1; 502 } 503 } 504 505 /*check the orientation of each polygon*/ 506 for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon()) 507 { 508 509 510 Int correctDir; 511 512 if( DBG_enclosingPolygons(temp, polyList) % 2 == 0) 513 correctDir = 1; /*counterclockwise*/ 514 else 515 correctDir = 0; /*clockwise*/ 516 517 Int actualDir = DBG_isCounterclockwise(temp); 518 519 if(correctDir != actualDir) 520 { 521 fprintf(stderr, "DBG_check: polygon with incorrect orientations. reversed\n"); 522 523 DBG_reverse(temp); 524 } 525 526 } 527 return 0; 528 } 529 530 /**************handle self intersections*****************/ 531 //determine whether e interects [begin, end] or not 532 static directedLine* DBG_edgeIntersectChainD(directedLine *e, 533 directedLine *begin, directedLine *end) 534 { 535 directedLine *temp; 536 for(temp=begin; temp != end; temp = temp->getNext()) 537 { 538 if(DBG_edgesIntersect(e, temp)) 539 return temp; 540 } 541 if(DBG_edgesIntersect(e, end)) 542 return end; 543 return NULL; 544 } 545 546 //given a polygon, cut the edges off and finally obtain a 547 //a polygon without intersections. The cut-off edges are 548 //dealloated. The new polygon is returned. 549 directedLine* DBG_cutIntersectionPoly(directedLine *polygon, int& cutOccur) 550 { 551 directedLine *begin, *end, *next; 552 begin = polygon; 553 end = polygon; 554 cutOccur = 0; 555 while( (next = end->getNext()) != begin) 556 { 557 directedLine *interc = NULL; 558 if( (interc = DBG_edgeIntersectChainD(next, begin, end))) 559 { 560 int fixed = 0; 561 if(DBG_edgesIntersect(next, interc->getNext())) 562 { 563 //trying to fix it 564 Real buf[2]; 565 int i; 566 Int n=5; 567 buf[0] = interc->tail()[0]; 568 buf[1] = interc->tail()[1]; 569 570 for(i=1; i<n; i++) 571 { 572 Real r = ((Real)i) / ((Real) n); 573 Real u = (1-r) * interc->head()[0] + r * interc->tail()[0]; 574 Real v = (1-r) * interc->head()[1] + r * interc->tail()[1]; 575 interc->tail()[0] = interc->getNext()->head()[0] = u; 576 interc->tail()[1] = interc->getNext()->head()[1] = v; 577 if( (! DBG_edgesIntersect(next, interc)) && 578 (! DBG_edgesIntersect(next, interc->getNext()))) 579 break; //we fixed it 580 } 581 if(i==n) // we didn't fix it 582 { 583 fixed = 0; 584 //back to original 585 interc->tail()[0] = interc->getNext()->head()[0] = buf[0]; 586 interc->tail()[1] = interc->getNext()->head()[1] = buf[1]; 587 } 588 else 589 { 590 fixed = 1; 591 } 592 } 593 if(fixed == 0) 594 { 595 cutOccur = 1; 596 begin->deleteSingleLine(next); 597 598 if(begin != end) 599 { 600 if(DBG_polygonSelfIntersect(begin)) 601 { 602 directedLine* newEnd = end->getPrev(); 603 begin->deleteSingleLine(end); 604 end = newEnd; 605 } 606 } 607 } 608 else 609 { 610 end = end->getNext(); 611 } 612 } 613 else 614 { 615 end = end->getNext(); 616 } 617 } 618 return begin; 619 } 620 621 //given a polygon, cut the edges off and finally obtain a 622 //a polygon without intersections. The cut-off edges are 623 //dealloated. The new polygon is returned. 624 #if 0 // UNUSED 625 static directedLine* DBG_cutIntersectionPoly_notwork(directedLine *polygon) 626 { 627 directedLine *crt;//current polygon 628 directedLine *begin; 629 directedLine *end; 630 directedLine *temp; 631 crt = polygon; 632 int find=0; 633 while(1) 634 { 635 //printf("loop\n"); 636 //if there are less than 3 edges, we should stop 637 if(crt->getPrev()->getPrev() == crt) 638 return NULL; 639 640 if(DBG_edgesIntersect(crt, crt->getNext()) || 641 (crt->head()[0] == crt->getNext()->tail()[0] && 642 crt->head()[1] == crt->getNext()->tail()[1]) 643 ) 644 { 645 find = 1; 646 crt=crt->deleteChain(crt, crt->getNext()); 647 } 648 else 649 { 650 //now we know crt and crt->getNext do not intersect 651 begin = crt; 652 end = crt->getNext(); 653 //printf("begin=(%f,%f)\n", begin->head()[0], begin->head()[1]); 654 //printf("end=(%f,%f)\n", end->head()[0], end->head()[1]); 655 for(temp=end->getNext(); temp!=begin; temp= temp->getNext()) 656 { 657 //printf("temp=(%f,%f)\n", temp->head()[0], temp->head()[1]); 658 directedLine *intersect = DBG_edgeIntersectChainD(temp, begin, end); 659 if(intersect != NULL) 660 { 661 crt = crt->deleteChain(intersect, temp); 662 find=1; 663 break; //the for loop 664 } 665 else 666 { 667 end = temp; 668 } 669 } 670 } 671 if(find == 0) 672 return crt; 673 else 674 find = 0; //go to next loop 675 } 676 } 677 #endif 678 679 directedLine* DBG_cutIntersectionAllPoly(directedLine* list) 680 { 681 directedLine* temp; 682 directedLine* tempNext=NULL; 683 directedLine* ret = NULL; 684 int cutOccur=0; 685 for(temp=list; temp != NULL; temp = tempNext) 686 { 687 directedLine *left; 688 tempNext = temp->getNextPolygon(); 689 690 left = DBG_cutIntersectionPoly(temp, cutOccur); 691 if(left != NULL) 692 ret=left->insertPolygon(ret); 693 } 694 return ret; 695 } 696 697 sampledLine* DBG_collectSampledLinesAllPoly(directedLine *polygonList) 698 { 699 directedLine *temp; 700 sampledLine* tempHead = NULL; 701 sampledLine* tempTail = NULL; 702 sampledLine* cHead = NULL; 703 sampledLine* cTail = NULL; 704 705 if(polygonList == NULL) 706 return NULL; 707 708 DBG_collectSampledLinesPoly(polygonList, cHead, cTail); 709 710 assert(cHead); 711 assert(cTail); 712 for(temp = polygonList->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon()) 713 { 714 DBG_collectSampledLinesPoly(temp, tempHead, tempTail); 715 cTail->insert(tempHead); 716 cTail = tempTail; 717 } 718 return cHead; 719 } 720 721 void DBG_collectSampledLinesPoly(directedLine *polygon, sampledLine*& retHead, sampledLine*& retTail) 722 { 723 directedLine *temp; 724 retHead = NULL; 725 retTail = NULL; 726 if(polygon == NULL) 727 return; 728 729 retHead = retTail = polygon->getSampledLine(); 730 for(temp = polygon->getNext(); temp != polygon; temp=temp->getNext()) 731 { 732 retHead = temp->getSampledLine()->insert(retHead); 733 } 734 } 735