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:
10 ** http://oss.sgi.com/projects/FreeB
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.
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.
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.
46 #pragma warning 391 10
47 #pragma warning 726 10
50 static Real
area(Real A
[2], Real B
[2], Real C
[2])
60 Int
DBG_isConvex(directedLine
*poly
)
63 if(area(poly
->head(), poly
->tail(), poly
->getNext()->tail()) < 0.00000)
65 for(temp
= poly
->getNext(); temp
!= poly
; temp
= temp
->getNext())
67 if(area(temp
->head(), temp
->tail(), temp
->getNext()->tail()) < 0.00000)
73 Int
DBG_is_U_monotone(directedLine
* poly
)
79 cur_sign
= compV2InX(poly
->tail(), poly
->head());
81 n_changes
= (compV2InX(poly
->getPrev()->tail(), poly
->getPrev()->head())
84 for(temp
= poly
->getNext(); temp
!= poly
; temp
= temp
->getNext())
87 cur_sign
= compV2InX(temp
->tail(), temp
->head());
89 if(cur_sign
!= prev_sign
)
93 if(n_changes
==2) return 1;
97 /*if u-monotone, and there is a long horizontal edge*/
98 Int
DBG_is_U_direction(directedLine
* poly
)
101 if(! DBG_is_U_monotone(poly))
107 if( fabs(poly
->head()[0] - poly
->tail()[0]) <= fabs(poly
->head()[1]-poly
->tail()[1]))
108 V_count
+= poly
->get_npoints();
110 U_count
+= poly
->get_npoints();
112 else if(poly->head()[1] == poly->tail()[1])
113 U_count += poly->get_npoints();
115 for(temp
= poly
->getNext(); temp
!= poly
; temp
= temp
->getNext())
117 if( fabs(temp
->head()[0] - temp
->tail()[0]) <= fabs(temp
->head()[1]-temp
->tail()[1]))
118 V_count
+= temp
->get_npoints();
120 U_count
+= temp
->get_npoints();
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();
129 if(U_count
> V_count
) return 1;
133 /*given two line segments, determine whether
134 *they intersect each other or not.
135 *return 1 if they do,
138 Int
DBG_edgesIntersect(directedLine
* l1
, directedLine
* l2
)
140 if(l1
->getNext() == l2
)
142 if(area(l1
->head(), l1
->tail(), l2
->tail()) == 0) //colinear
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
150 //else we use the normal code
152 else if(l1
->getPrev() == l2
)
154 if(area(l2
->head(), l2
->tail(), l1
->tail()) == 0) //colinear
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
162 //else we use the normal code
164 else //the two edges are not connected
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]))
177 area(l1
->head(), l1
->tail(), l2
->head())
179 area(l1
->head(), l1
->tail(), l2
->tail())
184 area(l2
->head(), l2
->tail(), l1
->head())
185 *area(l2
->head(), l2
->tail(), l1
->tail())
194 /*whether AB and CD intersect
198 Int
DBG_edgesIntersectGen(Real A
[2], Real B
[2], Real C
[2], Real D
[2])
202 area(A
, B
, C
) * area(A
,B
,D
) <0
206 area(C
,D
,A
) * area(C
,D
,B
) < 0
214 /*determien whether (A,B) interesect chain[start] to [end]
216 Int
DBG_intersectChain(vertexArray
* chain
, Int start
, Int end
, Real A
[2], Real B
[2])
219 for(i
=start
; i
<=end
-2; i
++)
220 if(DBG_edgesIntersectGen(chain
->getVertex(i
), chain
->getVertex(i
+1), A
, B
))
226 /*determine whether a polygon intersect itself or not
227 *return 1 is it does,
230 Int
DBG_polygonSelfIntersect(directedLine
* poly
)
235 for(temp2
=temp1
->getNext(); temp2
!= temp1
; temp2
=temp2
->getNext())
237 if(DBG_edgesIntersect(temp1
, temp2
))
244 for(temp1
=poly
->getNext(); temp1
!= poly
; temp1
= temp1
->getNext())
245 for(temp2
=temp1
->getNext(); temp2
!= temp1
; temp2
=temp2
->getNext())
247 if(DBG_edgesIntersect(temp1
, temp2
))
255 /*check whether a line segment intersects a polygon
257 Int
DBG_edgeIntersectPoly(directedLine
* edge
, directedLine
* poly
)
260 if(DBG_edgesIntersect(edge
, poly
))
262 for(temp
=poly
->getNext(); temp
!= poly
; temp
=temp
->getNext())
263 if(DBG_edgesIntersect(edge
, temp
))
268 /*check whether two polygons intersect
270 Int
DBG_polygonsIntersect(directedLine
* p1
, directedLine
* p2
)
273 if(DBG_edgeIntersectPoly(p1
, p2
))
275 for(temp
=p1
->getNext(); temp
!= p1
; temp
= temp
->getNext())
276 if(DBG_edgeIntersectPoly(temp
, p2
))
281 /*check whether there are polygons intersecting each other in
284 Int
DBG_polygonListIntersect(directedLine
* pList
)
287 for(temp
=pList
; temp
!= NULL
; temp
= temp
->getNextPolygon())
288 if(DBG_polygonSelfIntersect(temp
))
291 for(temp
=pList
; temp
!=NULL
; temp
=temp
->getNextPolygon())
293 for(temp2
=temp
->getNextPolygon(); temp2
!= NULL
; temp2
=temp2
->getNextPolygon())
294 if(DBG_polygonsIntersect(temp
, temp2
))
302 Int
DBG_isCounterclockwise(directedLine
* poly
)
304 return (poly
->polyArea() > 0);
307 /*ray: v0 with direction (dx,dy).
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.
321 Int
DBG_rayIntersectEdge(Real v0
[2], Real dx
, Real dy
, Real v10
[2], Real v1
[2], Real v2
[2])
324 if( (v1[1] >= v0[1] && v2[1]<= v0[1] )
325 ||(v2[1] >= v0[1] && v1[1]<= v0[1] )
327 printf("rayIntersectEdge, *********\n");
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
);
335 /*if the ray is parallel to the edge, return 0: not intersect*/
339 /*if v0 is on the edge, return 0: not intersect*/
343 /*if v1 is on the positive ray, and the neighbor of v1 crosses the ray
347 { /*v1 is on the positive or negative ray*/
350 printf("v1 is on the ray\n");
353 if(dx
*(v1
[0]-v0
[0])>=0 && dy
*(v1
[1]-v0
[1])>=0) /*v1 on positive ray*/
355 if(area(v0
, v1
, v10
) * area(v0
, v1
, v2
) >0)
360 else /*v1 on negative ray*/
364 /*if v2 is on the ray, always return 0: not intersect*/
365 if(nomEdge
== denom
) {
366 /* printf("v2 is on the ray\n");*/
371 if(denom
*nomRay
>0 && denom
*nomEdge
>0 && nomEdge
/denom
<=1.0)
377 /*return the number of intersections*/
378 Int
DBG_rayIntersectPoly(Real v0
[2], Real dx
, Real dy
, directedLine
* poly
)
382 if(DBG_rayIntersectEdge(v0
, dx
, dy
, poly
->getPrev()->head(), poly
->head(), poly
->tail()))
385 for(temp
=poly
->getNext(); temp
!= poly
; temp
= temp
->getNext())
386 if(DBG_rayIntersectEdge(v0
, dx
, dy
, temp
->getPrev()->head(), temp
->head(), temp
->tail()))
388 /*printf("ray intersect poly: count=%i\n", count);*/
392 Int
DBG_pointInsidePoly(Real v
[2], directedLine
* poly
)
395 printf("enter pointInsidePoly , v=(%f,%f)\n", v[0], v[1]);
396 printf("the polygon is\n");
399 /*for debug purpose*/
400 assert( (DBG_rayIntersectPoly(v
,1,0,poly
) % 2 )
401 == (DBG_rayIntersectPoly(v
,1,Real(0.1234), poly
) % 2 )
403 if(DBG_rayIntersectPoly(v
, 1, 0, poly
) % 2 == 1)
409 /*return the number of polygons which contain thie polygon
412 Int
DBG_enclosingPolygons(directedLine
* poly
, directedLine
* list
)
417 printf("%i\n", DBG_pointInsidePoly(poly->head(),
418 list->getNextPolygon()
425 for(temp
= list
; temp
!= NULL
; temp
= temp
->getNextPolygon())
428 if(DBG_pointInsidePoly(poly
->head(), temp
))
430 /* printf("count=%i\n", count);*/
435 void DBG_reverse(directedLine
* poly
)
437 if(poly
->getDirection() == INCREASING
)
438 poly
->putDirection(DECREASING
);
440 poly
->putDirection(INCREASING
);
442 directedLine
* oldNext
= poly
->getNext();
443 poly
->putNext(poly
->getPrev());
444 poly
->putPrev(oldNext
);
447 for(temp
=oldNext
; temp
!=poly
; temp
= oldNext
)
449 if(temp
->getDirection() == INCREASING
)
450 temp
->putDirection(DECREASING
);
452 temp
->putDirection(INCREASING
);
454 oldNext
= temp
->getNext();
455 temp
->putNext(temp
->getPrev());
456 temp
->putPrev(oldNext
);
458 printf("reverse done\n");
461 Int
DBG_checkConnectivity(directedLine
*polygon
)
463 if(polygon
== NULL
) return 1;
465 if(polygon
->head()[0] != polygon
->getPrev()->tail()[0] ||
466 polygon
->head()[1] != polygon
->getPrev()->tail()[1])
468 for(temp
=polygon
->getNext(); temp
!= polygon
; temp
=temp
->getNext())
470 if(temp
->head()[0] != temp
->getPrev()->tail()[0] ||
471 temp
->head()[1] != temp
->getPrev()->tail()[1])
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
482 Int
DBG_check(directedLine
*polyList
)
485 if(polyList
== NULL
) return 0;
487 /*if there are intersections, print out error message
489 if(DBG_polygonListIntersect(polyList
))
491 fprintf(stderr
, "DBG_check: there are self intersections, don't know to modify the polygons\n");
495 /*check the connectivity of each polygon*/
496 for(temp
= polyList
; temp
!= NULL
; temp
= temp
->getNextPolygon())
498 if(! DBG_checkConnectivity(temp
))
500 fprintf(stderr
, "DBG_check, polygon not connected\n");
505 /*check the orientation of each polygon*/
506 for(temp
= polyList
; temp
!= NULL
; temp
= temp
->getNextPolygon())
512 if( DBG_enclosingPolygons(temp
, polyList
) % 2 == 0)
513 correctDir
= 1; /*counterclockwise*/
515 correctDir
= 0; /*clockwise*/
517 Int actualDir
= DBG_isCounterclockwise(temp
);
519 if(correctDir
!= actualDir
)
521 fprintf(stderr
, "DBG_check: polygon with incorrect orientations. reversed\n");
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
)
536 for(temp
=begin
; temp
!= end
; temp
= temp
->getNext())
538 if(DBG_edgesIntersect(e
, temp
))
541 if(DBG_edgesIntersect(e
, end
))
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
)
551 directedLine
*begin
, *end
, *next
;
555 while( (next
= end
->getNext()) != begin
)
557 directedLine
*interc
= NULL
;
558 if( (interc
= DBG_edgeIntersectChainD(next
, begin
, end
)))
561 if(DBG_edgesIntersect(next
, interc
->getNext()))
567 buf
[0] = interc
->tail()[0];
568 buf
[1] = interc
->tail()[1];
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())))
581 if(i
==n
) // we didn't fix it
585 interc
->tail()[0] = interc
->getNext()->head()[0] = buf
[0];
586 interc
->tail()[1] = interc
->getNext()->head()[1] = buf
[1];
596 begin
->deleteSingleLine(next
);
600 if(DBG_polygonSelfIntersect(begin
))
602 directedLine
* newEnd
= end
->getPrev();
603 begin
->deleteSingleLine(end
);
610 end
= end
->getNext();
615 end
= end
->getNext();
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 static directedLine
* DBG_cutIntersectionPoly_notwork(directedLine
*polygon
)
626 directedLine
*crt
;//current polygon
635 //if there are less than 3 edges, we should stop
636 if(crt
->getPrev()->getPrev() == crt
)
639 if(DBG_edgesIntersect(crt
, crt
->getNext()) ||
640 (crt
->head()[0] == crt
->getNext()->tail()[0] &&
641 crt
->head()[1] == crt
->getNext()->tail()[1])
645 crt
=crt
->deleteChain(crt
, crt
->getNext());
649 //now we know crt and crt->getNext do not intersect
651 end
= crt
->getNext();
652 //printf("begin=(%f,%f)\n", begin->head()[0], begin->head()[1]);
653 //printf("end=(%f,%f)\n", end->head()[0], end->head()[1]);
654 for(temp
=end
->getNext(); temp
!=begin
; temp
= temp
->getNext())
656 //printf("temp=(%f,%f)\n", temp->head()[0], temp->head()[1]);
657 directedLine
*intersect
= DBG_edgeIntersectChainD(temp
, begin
, end
);
658 if(intersect
!= NULL
)
660 crt
= crt
->deleteChain(intersect
, temp
);
662 break; //the for loop
673 find
= 0; //go to next loop
677 directedLine
* DBG_cutIntersectionAllPoly(directedLine
* list
)
680 directedLine
* tempNext
=NULL
;
681 directedLine
* ret
= NULL
;
683 for(temp
=list
; temp
!= NULL
; temp
= tempNext
)
686 tempNext
= temp
->getNextPolygon();
688 left
= DBG_cutIntersectionPoly(temp
, cutOccur
);
690 ret
=left
->insertPolygon(ret
);
695 sampledLine
* DBG_collectSampledLinesAllPoly(directedLine
*polygonList
)
698 sampledLine
* tempHead
= NULL
;
699 sampledLine
* tempTail
= NULL
;
700 sampledLine
* cHead
= NULL
;
701 sampledLine
* cTail
= NULL
;
703 if(polygonList
== NULL
)
706 DBG_collectSampledLinesPoly(polygonList
, cHead
, cTail
);
710 for(temp
= polygonList
->getNextPolygon(); temp
!= NULL
; temp
= temp
->getNextPolygon())
712 DBG_collectSampledLinesPoly(temp
, tempHead
, tempTail
);
713 cTail
->insert(tempHead
);
719 void DBG_collectSampledLinesPoly(directedLine
*polygon
, sampledLine
*& retHead
, sampledLine
*& retTail
)
722 sampledLine
*ret
= NULL
;
728 retHead
= retTail
= polygon
->getSampledLine();
729 for(temp
= polygon
->getNext(); temp
!= polygon
; temp
=temp
->getNext())
731 retHead
= temp
->getSampledLine()->insert(retHead
);