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.
41 #include "sampleCompBot.h"
42 #include "sampleCompRight.h"
44 #define max(a,b) ((a>b)? a:b)
46 //return: index_mono, index_pass
47 //from [pass, mono] is strictly U-monotone
48 //from [corner, pass] is <u
49 // vertex[pass][0] >= u
50 //if everybost is <u, then pass = end+1.
51 //otherwise both mono and pass are meanng full and we have corner<=pass<=mono<=end
52 void findBotLeftSegment(vertexArray
* leftChain
,
61 assert(leftCorner
<= leftEnd
);
62 for(i
=leftCorner
; i
<= leftEnd
; i
++)
63 if(leftChain
->getVertex(i
)[0] >= u
)
66 if(ret_index_pass
<= leftEnd
)
68 for(i
=ret_index_pass
; i
< leftEnd
; i
++)
70 if(leftChain
->getVertex(i
+1)[0] <= leftChain
->getVertex(i
)[0])
78 void findBotRightSegment(vertexArray
* rightChain
,
86 assert(rightCorner
<= rightEnd
);
87 for(i
=rightCorner
; i
<= rightEnd
; i
++)
88 if(rightChain
->getVertex(i
)[0] <= u
)
95 if(ret_index_pass
<= rightEnd
)
97 for(i
=ret_index_pass
; i
< rightEnd
; i
++)
99 if(rightChain
->getVertex(i
+1)[0] >= rightChain
->getVertex(i
)[0])
107 void sampleBotRightWithGridLinePost(Real
* botVertex
,
108 vertexArray
* rightChain
,
119 //the possible section which is to the right of rightU
120 if(segIndexPass
> rightCorner
) //from corner to pass-1 is > u.
123 if(segIndexPass
<= rightEnd
) //there is a point to the left of u
124 tempBot
= rightChain
->getVertex(segIndexPass
);
125 else //nothing is to the left of u.
128 tempTop
[0] = grid
->get_u_value(rightU
);
129 tempTop
[1] = grid
->get_v_value(gridV
);
131 monoTriangulation2(tempTop
, tempBot
,
135 0, // a decrease chain
139 //the possible section which is strictly Umonotone
140 if(segIndexPass
<= rightEnd
) //segIndex pass and mono exist
142 //if there are grid points which are to the left of botVertex
143 //then we should use botVertex to form a fan with these points to
144 //optimize the triangulation
146 if(botVertex
[0] <= grid
->get_u_value(leftU
))
150 //we also have to make sure that botVertex is the left most vertex on the chain
152 for(i
=segIndexMono
; i
<=rightEnd
; i
++)
153 if(rightChain
->getVertex(i
)[0] <= botVertex
[0])
162 //find midU so that grid->get_u_value(midU) <= botVertex[0]
163 //and grid->get_u_value(midU) > botVertex[0]
165 while(grid
->get_u_value(midU
) <= botVertex
[0])
173 grid
->outputFanWithPoint(gridV
, leftU
, midU
, botVertex
, pStream
);
174 stripOfFanRight(rightChain
, segIndexMono
, segIndexPass
, grid
, gridV
, midU
, rightU
, pStream
, 1);
176 tempTop
[0] = grid
->get_u_value(midU
);
177 tempTop
[1] = grid
->get_v_value(gridV
);
178 monoTriangulation2(tempTop
, botVertex
, rightChain
, segIndexMono
, rightEnd
, 0, pStream
);
182 stripOfFanRight(rightChain
, segIndexMono
, segIndexPass
, grid
, gridV
, leftU
, rightU
, pStream
, 1);
184 tempTop
[0] = grid
->get_u_value(leftU
);
185 tempTop
[1] = grid
->get_v_value(gridV
);
186 monoTriangulation2(tempTop
, botVertex
, rightChain
, segIndexMono
, rightEnd
, 0, pStream
);
189 else //the botVertex forms a fan witht eh grid points
190 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, botVertex
, pStream
);
193 void sampleBotRightWithGridLine(Real
* botVertex
,
194 vertexArray
* rightChain
,
203 //if right chaain is empty, then there is only one bot vertex with
205 if(rightEnd
<rightCorner
){
206 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, botVertex
, pStream
);
210 Int segIndexMono
= 0, segIndexPass
;
211 findBotRightSegment(rightChain
,
214 grid
->get_u_value(rightU
),
218 sampleBotRightWithGridLinePost(botVertex
,
232 void sampleBotLeftWithGridLinePost(Real
* botVertex
,
233 vertexArray
* leftChain
,
245 //the possible section which is to the left of leftU
246 if(segIndexPass
> leftCorner
) //at least leftCorner is to the left of leftU
249 if(segIndexPass
<= leftEnd
) //from corner to pass-1 is <u
250 tempBot
= leftChain
->getVertex(segIndexPass
);
251 else //nothing is to the rigth of u
254 tempTop
[0] = grid
->get_u_value(leftU
);
255 tempTop
[1] = grid
->get_v_value(gridV
);
256 monoTriangulation2(tempTop
, tempBot
, leftChain
, leftCorner
, segIndexPass
-1,
257 1, //a increase chain,
260 //the possible section which is strictly Umonotone
261 if(segIndexPass
<= leftEnd
) //segIndexpass and mono exist
263 stripOfFanLeft(leftChain
, segIndexMono
, segIndexPass
, grid
, gridV
, leftU
, rightU
, pStream
, 1);
265 tempTop
[0] = grid
->get_u_value(rightU
);
266 tempTop
[1] = grid
->get_v_value(gridV
);
268 monoTriangulation2(tempTop
, botVertex
, leftChain
, segIndexMono
, leftEnd
,
272 else //the botVertex forms a fan with the grid points
274 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, botVertex
, pStream
);
279 void sampleBotLeftWithGridLine(Real
* botVertex
,
280 vertexArray
* leftChain
,
290 //if leftChain is empty, then there is only one botVertex with one grid line
291 if(leftEnd
< leftCorner
){
292 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, botVertex
, pStream
);
296 Int segIndexPass
, segIndexMono
= 0;
297 findBotLeftSegment(leftChain
, leftEnd
, leftCorner
, grid
->get_u_value(leftU
), segIndexMono
, segIndexPass
);
299 sampleBotLeftWithGridLinePost(botVertex
,
307 leftU
, rightU
, pStream
);
310 //return 1 if separator exists, 0 otherwise
311 Int
findBotSeparator(vertexArray
* leftChain
,
314 vertexArray
* rightChain
,
320 Int oldLeftI
, oldRightI
, newLeftI
, newRightI
;
322 Real leftMax
/*= leftChain->getVertex(leftCorner)[0]*/;
323 Real rightMin
/*= rightChain->getVertex(rightCorner)[0]*/;
324 if(leftChain
->getVertex(leftCorner
)[1] < rightChain
->getVertex(rightCorner
)[1])//leftlower
326 oldLeftI
= leftCorner
-1;
327 oldRightI
= rightCorner
;
328 leftMax
= leftChain
->getVertex(leftCorner
)[0] - Real(1.0) ; //initilize to be left of leftCorner
329 rightMin
= rightChain
->getVertex(rightCorner
)[0];
333 oldLeftI
= leftCorner
;
334 oldRightI
= rightCorner
-1;
335 leftMax
= leftChain
->getVertex(leftCorner
)[0];
336 rightMin
= rightChain
->getVertex(rightCorner
)[0] + Real(1.0);
339 //i: the current working leftChain Index
340 //j: the curent working right chian index
341 //if(left(i) is lower than right(j), then the two chains above right(j) are separated.
342 //else the two chains below left(i) are separated.
348 newRightI
= oldRightI
;
349 if(i
> leftEnd
) //left chain is doen , go through remaining right chain
351 for(k
=j
+1; k
<= rightEnd
; k
++)
353 if(rightChain
->getVertex(k
)[0] > leftMax
) //no conflict
355 //update oldRightI if necessary
356 if(rightChain
->getVertex(k
)[0] < rightMin
)
358 rightMin
= rightChain
->getVertex(k
)[0];
362 else //there is a conflict
363 break; //the for-loop, above right(k+1) is separated: oldLeftI, oldRightI
365 break; //the while loop
367 else if(j
> rightEnd
) //right Chain is doen
369 for(k
=i
+1; k
<= leftEnd
; k
++)
371 if(leftChain
->getVertex(k
)[0] < rightMin
) //no conflict
373 //update oldLeftI if necessary
374 if(leftChain
->getVertex(k
)[0] > leftMax
)
376 leftMax
= leftChain
->getVertex(k
)[0];
380 else //there is a conflict
381 break; //the for-loop, above left(k+1) is separated: oldLeftI, oldRightI
383 break; //the while loop
385 else if(leftChain
->getVertex(i
)[1] < rightChain
->getVertex(j
)[1]) //left lower
388 if(leftChain
->getVertex(i
)[0] > leftMax
) //update leftMax amd newLeftI
390 leftMax
= leftChain
->getVertex(i
)[0];
393 for(k
=j
+1; k
<= rightEnd
; k
++) //update rightMin and newRightI;
395 if(rightChain
->getVertex(k
)[1] < leftChain
->getVertex(i
)[1]) //right gets lower
397 if(rightChain
->getVertex(k
)[0] < rightMin
)
399 rightMin
= rightChain
->getVertex(k
)[0];
403 j
= k
; //next working j, since j will he lower than i in next loop
404 if(leftMax
>= rightMin
) //there is a conflict
406 else //still no conflict
409 oldRightI
= newRightI
;
415 if(rightChain
->getVertex(j
)[0] < rightMin
)
417 rightMin
= rightChain
->getVertex(j
)[0];
420 for(k
=i
+1; k
<= leftEnd
; k
++)
422 if(leftChain
->getVertex(k
)[1] < rightChain
->getVertex(j
)[1])
424 if(leftChain
->getVertex(k
)[0] > leftMax
)
426 leftMax
= leftChain
->getVertex(k
)[0];
430 i
=k
; //nexct working i, since i will be lower than j next loop
431 if(leftMax
>= rightMin
) //there is conflict
433 else //still no conflict
436 oldRightI
= newRightI
;
440 //now oldLeftI and oldRight I are the desired separator index notice that they are not
442 if(oldLeftI
< leftCorner
|| oldRightI
< rightCorner
)
443 return 0; //no separator
446 ret_sep_left
= oldLeftI
;
447 ret_sep_right
= oldRightI
;
452 void sampleCompBot(Real
* botVertex
,
453 vertexArray
* leftChain
,
455 vertexArray
* rightChain
,
457 gridBoundaryChain
* leftGridChain
,
458 gridBoundaryChain
* rightGridChain
,
460 Int down_leftCornerWhere
,
461 Int down_leftCornerIndex
,
462 Int down_rightCornerWhere
,
463 Int down_rightCornerIndex
,
467 if(down_leftCornerWhere
== 1 && down_rightCornerWhere
== 1) //the bot is botVertex with possible grid points
470 leftGridChain
->getGrid()->outputFanWithPoint(leftGridChain
->getVlineIndex(gridIndex
),
471 leftGridChain
->getUlineIndex(gridIndex
),
472 rightGridChain
->getUlineIndex(gridIndex
),
477 else if(down_leftCornerWhere
!= 0)
482 if(down_leftCornerWhere
== 1){
483 tempRightEnd
= rightEnd
;
488 tempRightEnd
= down_leftCornerIndex
-1;
489 tempBot
= rightChain
->getVertex(down_leftCornerIndex
);
492 sampleBotRightWithGridLine(tempBot
,
495 down_rightCornerIndex
,
496 rightGridChain
->getGrid(),
497 leftGridChain
->getVlineIndex(gridIndex
),
498 leftGridChain
->getUlineIndex(gridIndex
),
499 rightGridChain
->getUlineIndex(gridIndex
),
502 else if(down_rightCornerWhere
!= 2)
507 if(down_rightCornerWhere
== 1){
508 tempLeftEnd
= leftEnd
;
511 else //right corner is on left chain
513 tempLeftEnd
= down_rightCornerIndex
-1;
514 tempBot
= leftChain
->getVertex(down_rightCornerIndex
);
518 sampleBotLeftWithGridLine(tempBot
, leftChain
, tempLeftEnd
, down_leftCornerIndex
,
519 leftGridChain
->getGrid(),
520 leftGridChain
->getVlineIndex(gridIndex
),
521 leftGridChain
->getUlineIndex(gridIndex
),
522 rightGridChain
->getUlineIndex(gridIndex
),
526 else //down_leftCornereWhere == 0, down_rightCornerwhere == 2
528 sampleCompBotSimple(botVertex
,
536 down_leftCornerWhere
,
537 down_leftCornerIndex
,
538 down_rightCornerWhere
,
539 down_rightCornerIndex
,
545 //the following code is trying to do some optimization, but not quite working. so it is not reachable, but leave it here for reference
546 Int sep_left
, sep_right
;
547 if(findBotSeparator(leftChain
, leftEnd
, down_leftCornerIndex
,
548 rightChain
, rightEnd
, down_rightCornerIndex
,
553 if(leftChain
->getVertex(sep_left
)[0] >= leftGridChain
->get_u_value(gridIndex
) &&
554 rightChain
->getVertex(sep_right
)[0] <= rightGridChain
->get_u_value(gridIndex
))
557 Int segLeftMono
, segLeftPass
, segRightMono
, segRightPass
;
558 findBotLeftSegment(leftChain
,
560 down_leftCornerIndex
,
561 leftGridChain
->get_u_value(gridIndex
),
564 findBotRightSegment(rightChain
,
566 down_rightCornerIndex
,
567 rightGridChain
->get_u_value(gridIndex
),
570 if(leftChain
->getVertex(segLeftMono
)[1] <= rightChain
->getVertex(segRightMono
)[1])
572 gridSep
= rightGridChain
->getUlineIndex(gridIndex
);
573 while(leftGridChain
->getGrid()->get_u_value(gridSep
) > leftChain
->getVertex(segLeftMono
)[0])
578 gridSep
= leftGridChain
->getUlineIndex(gridIndex
);
579 while(leftGridChain
->getGrid()->get_u_value(gridSep
) < rightChain
->getVertex(segRightMono
)[0])
583 sampleBotLeftWithGridLinePost(leftChain
->getVertex(segLeftMono
),
588 down_leftCornerIndex
,
589 leftGridChain
->getGrid(),
590 leftGridChain
->getVlineIndex(gridIndex
),
591 leftGridChain
->getUlineIndex(gridIndex
),
594 sampleBotRightWithGridLinePost(rightChain
->getVertex(segRightMono
),
599 down_rightCornerIndex
,
600 rightGridChain
->getGrid(),
601 rightGridChain
->getVlineIndex(gridIndex
),
603 rightGridChain
->getUlineIndex(gridIndex
),
606 tempTop
[0] = leftGridChain
->getGrid()->get_u_value(gridSep
);
607 tempTop
[1] = leftGridChain
->get_v_value(gridIndex
);
608 monoTriangulationRecGen(tempTop
, botVertex
,
609 leftChain
, segLeftMono
, leftEnd
,
610 rightChain
, segRightMono
, rightEnd
,
612 }//end if both sides have vertices inside the gridboundary points
613 else if(leftChain
->getVertex(sep_left
)[0] >= leftGridChain
->get_u_value(gridIndex
)) //left n right out
616 Int segLeftMono
, segLeftPass
;
617 findBotLeftSegment(leftChain
,
619 down_leftCornerIndex
,
620 leftGridChain
->get_u_value(gridIndex
),
623 assert(segLeftPass
<= sep_left
); //make sure there is a point to the right of u.
624 monoTriangulation2(leftGridChain
->get_vertex(gridIndex
),
625 leftChain
->getVertex(segLeftPass
),
627 down_leftCornerIndex
,
629 1, //a increase chain
631 stripOfFanLeft(leftChain
, segLeftMono
, segLeftPass
,
632 leftGridChain
->getGrid(),
633 leftGridChain
->getVlineIndex(gridIndex
),
634 leftGridChain
->getUlineIndex(gridIndex
),
635 rightGridChain
->getUlineIndex(gridIndex
),
638 sampleBotLeftWithGridLinePost(leftChain->getVertex(segLeftMono),
643 down_leftCornerIndex,
644 leftGridChain->getGrid(),
645 leftGridChain->getVlineIndex(gridIndex),
646 leftGridChain->getUlineIndex(gridIndex),
647 rightGridChain->getUlineIndex(gridIndex),
651 monoTriangulationRecGen(rightGridChain
->get_vertex(gridIndex
),
653 leftChain
, segLeftMono
, leftEnd
,
654 rightChain
, down_rightCornerIndex
, rightEnd
,
656 }//end left in right out
657 else if(rightChain
->getVertex(sep_right
)[0] <= rightGridChain
->get_u_value(gridIndex
))//left out right in
659 Int segRightMono
, segRightPass
;
660 findBotRightSegment(rightChain
, sep_right
, down_rightCornerIndex
,
661 rightGridChain
->get_u_value(gridIndex
),
665 assert(segRightPass
<= sep_right
); //make sure there is a point to the left of u.
666 monoTriangulation2(rightGridChain
->get_vertex(gridIndex
),
667 rightChain
->getVertex(segRightPass
),
669 down_rightCornerIndex
,
671 0, // a decrease chain
674 stripOfFanRight(rightChain
, segRightMono
, segRightPass
,
675 rightGridChain
->getGrid(),
676 rightGridChain
->getVlineIndex(gridIndex
),
677 leftGridChain
->getUlineIndex(gridIndex
),
678 rightGridChain
->getUlineIndex(gridIndex
),
682 monoTriangulationRecGen(leftGridChain
->get_vertex(gridIndex
),
684 leftChain
, down_leftCornerIndex
, leftEnd
,
685 rightChain
, segRightMono
, rightEnd
,
688 }//end left out right in
689 else //left out, right out
691 sampleCompBotSimple(botVertex
,
699 down_leftCornerWhere
,
700 down_leftCornerIndex
,
701 down_rightCornerWhere
,
702 down_rightCornerIndex
,
705 }//end leftout right out
706 }//end if separator exists
710 sampleCompBotSimple(botVertex
,
718 down_leftCornerWhere
,
719 down_leftCornerIndex
,
720 down_rightCornerWhere
,
721 down_rightCornerIndex
,
726 }//end if the functin
729 void sampleCompBotSimple(Real
* botVertex
,
730 vertexArray
* leftChain
,
732 vertexArray
* rightChain
,
734 gridBoundaryChain
* leftGridChain
,
735 gridBoundaryChain
* rightGridChain
,
737 Int down_leftCornerWhere
,
738 Int down_leftCornerIndex
,
739 Int down_rightCornerWhere
,
740 Int down_rightCornerIndex
,
743 //the plan is to use monotriangulation algorithm.
747 Int ActualLeftStart
, ActualLeftEnd
;
748 Int ActualRightStart
, ActualRightEnd
;
750 //creat an array to store the points on the grid line
751 gridWrap
* grid
= leftGridChain
->getGrid();
752 Int gridV
= leftGridChain
->getVlineIndex(gridIndex
);
753 Int gridLeftU
= leftGridChain
->getUlineIndex(gridIndex
);
754 Int gridRightU
= rightGridChain
->getUlineIndex(gridIndex
);
755 Real2
* gridPoints
= (Real2
*) malloc(sizeof(Real2
) * (gridRightU
- gridLeftU
+1));
758 for(k
=0, i
=gridRightU
; i
>= gridLeftU
; i
--, k
++)
760 gridPoints
[k
][0] = grid
->get_u_value(i
);
761 gridPoints
[k
][1] = grid
->get_v_value(gridV
);
764 if(down_rightCornerWhere
!= 0) //rightCorner is not on lef
765 ActualLeftEnd
= leftEnd
;
767 ActualLeftEnd
= down_rightCornerIndex
-1; //down_rightCornerIndex will be th actualBot
769 if(down_leftCornerWhere
!= 0) //left corner is not on let chian
770 ActualLeftStart
= leftEnd
+1; //meaning that there is no actual left section
772 ActualLeftStart
= down_leftCornerIndex
;
774 vertexArray
ActualLeftChain(max(0, ActualLeftEnd
- ActualLeftStart
+1) + gridRightU
- gridLeftU
+1);
776 for(i
=0; i
<gridRightU
- gridLeftU
+1 ; i
++)
777 ActualLeftChain
.appendVertex(gridPoints
[i
]);
778 for(i
=ActualLeftStart
; i
<= ActualLeftEnd
; i
++)
779 ActualLeftChain
.appendVertex(leftChain
->getVertex(i
));
781 //determine ActualRightStart
782 if(down_rightCornerWhere
!= 2) //right is not on right
783 ActualRightStart
= rightEnd
+1; //meaning no section on right
785 ActualRightStart
= down_rightCornerIndex
;
787 //determine actualrightEnd
788 if(down_leftCornerWhere
!= 2) //left is not on right
791 ActualRightEnd
= rightEnd
;
793 else //left corner is on right
795 ActualRightEnd
= down_leftCornerIndex
-1; //down_leftCornerIndex will be the bot
800 if(down_rightCornerWhere
== 2)
802 if(down_leftCornerWhere
== 2)
803 ActualBot
= rightChain
->getVertex(down_leftCornerIndex
);
805 ActualBot
= botVertex
;
807 else if(down_rightCornerWhere
== 1) //right corner bot
808 ActualBot
= botVertex
;
809 else //down_rightCornerWhere == 0
810 ActualBot
= leftChain
->getVertex(down_rightCornerIndex
);
812 ActualTop
= gridPoints
[0];
814 printf("in bot simple, actual leftChain is \n");
815 ActualLeftChain.print();
816 printf("Actual Top = %f,%f\n", ActualTop[0],ActualTop[1]);
817 printf("Actual Bot = %f,%f\n", ActualBot[0],ActualBot[1]);
818 printf("Actual right start = %i, end=%i\n",ActualRightStart, ActualRightEnd);
820 if(rightChain
->getVertex(ActualRightStart
)[1] == ActualTop
[1])
821 monoTriangulationRecGenOpt(rightChain
->getVertex(ActualRightStart
),
825 ActualLeftChain
.getNumElements()-1,
831 monoTriangulationRecGenOpt(ActualTop
, ActualBot
,
833 1, //the first one is the top vertex
834 ActualLeftChain
.getNumElements()-1,