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.
42 #include "sampleCompTop.h"
43 #include "sampleCompRight.h"
45 #define max(a,b) ((a>b)? a:b)
47 //return : index_small, and index_large,
48 //from [small, large] is strictly U-monotne,
49 //from [large+1, end] is <u
50 //and vertex[large][0] is >= u
51 //if eveybody is <u, the large = start-1.
52 //otherwise both large and small are meaningful and we have start<=small<=large<=end
53 void findTopLeftSegment(vertexArray
* leftChain
,
62 assert(leftStart
<= leftEnd
);
63 for(i
=leftEnd
; i
>= leftStart
; i
--)
65 if(leftChain
->getVertex(i
)[0] >= u
)
69 if(ret_index_large
>= leftStart
)
71 for(i
=ret_index_large
; i
>leftStart
; i
--)
73 if(leftChain
->getVertex(i
-1)[0] <= leftChain
->getVertex(i
)[0])
80 void findTopRightSegment(vertexArray
* rightChain
,
88 assert(rightStart
<=rightEnd
);
89 for(i
=rightEnd
; i
>=rightStart
; i
--)
91 if(rightChain
->getVertex(i
)[0] <= u
)
95 if(ret_index_large
>= rightStart
)
97 for(i
=ret_index_large
; i
>rightStart
;i
--)
99 if(rightChain
->getVertex(i
-1)[0] >= rightChain
->getVertex(i
)[0])
107 void sampleTopRightWithGridLinePost(Real
* topVertex
,
108 vertexArray
* rightChain
,
119 //the possible section which is to the right of rightU
120 if(segIndexLarge
< rightEnd
)
123 if(segIndexLarge
>= rightStart
)
124 tempTop
= rightChain
->getVertex(segIndexLarge
);
128 tempBot
[0] = grid
->get_u_value(rightU
);
129 tempBot
[1] = grid
->get_v_value(gridV
);
130 monoTriangulationRecGenOpt(tempTop
, tempBot
,
132 rightChain
, segIndexLarge
+1, rightEnd
,
135 monoTriangulation2(tempTop, tempBot,
139 0, //a decrease chian
145 //the possible section which is strictly Umonotone
146 if(segIndexLarge
>= rightStart
)
148 stripOfFanRight(rightChain
, segIndexLarge
, segIndexSmall
, grid
, gridV
, leftU
, rightU
, pStream
, 0);
150 tempBot
[0] = grid
->get_u_value(leftU
);
151 tempBot
[1] = grid
->get_v_value(gridV
);
152 monoTriangulation2(topVertex
, tempBot
, rightChain
, rightStart
, segIndexSmall
, 0, pStream
);
154 else //the topVertex forms a fan with the grid points
155 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, topVertex
, pStream
);
158 void sampleTopRightWithGridLine(Real
* topVertex
,
159 vertexArray
* rightChain
,
169 //if right chian is empty, then there is only one topVertex with one grid line
170 if(rightEnd
< rightStart
){
171 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, topVertex
, pStream
);
175 Int segIndexSmall
= 0, segIndexLarge
;
176 findTopRightSegment(rightChain
,
179 grid
->get_u_value(rightU
),
183 sampleTopRightWithGridLinePost(topVertex
, rightChain
,
196 void sampleTopLeftWithGridLinePost(Real
* topVertex
,
197 vertexArray
* leftChain
,
208 //the possible section which is to the left of leftU
210 if(segIndexLarge
< leftEnd
)
213 if(segIndexLarge
>= leftStart
)
214 tempTop
= leftChain
->getVertex(segIndexLarge
);
218 tempBot
[0] = grid
->get_u_value(leftU
);
219 tempBot
[1] = grid
->get_v_value(gridV
);
221 monoTriangulation2(tempTop
, tempBot
,
225 1, //a increase chian
229 //the possible section which is strictly Umonotone
230 if(segIndexLarge
>= leftStart
)
232 //if there are grid points which are to the right of topV,
233 //then we should use topVertex to form a fan with these points to
234 //optimize the triangualtion
236 if(topVertex
[0] >= grid
->get_u_value(rightU
))
240 //we also have to make sure that topVertex are the right most vertex
243 for(i
=leftStart
; i
<=segIndexSmall
; i
++)
244 if(leftChain
->getVertex(i
)[0] >= topVertex
[0])
253 //find midU so that grid->get_u_value(midU) >= topVertex[0]
254 //and grid->get_u_value(midU-1) < topVertex[0]
256 while(grid
->get_u_value(midU
) >= topVertex
[0])
264 grid
->outputFanWithPoint(gridV
, midU
, rightU
, topVertex
, pStream
);
265 stripOfFanLeft(leftChain
, segIndexLarge
, segIndexSmall
, grid
, gridV
, leftU
, midU
, pStream
, 0);
267 tempBot
[0] = grid
->get_u_value(midU
);
268 tempBot
[1] = grid
->get_v_value(gridV
);
269 monoTriangulation2(topVertex
, tempBot
, leftChain
, leftStart
, segIndexSmall
, 1, pStream
);
274 stripOfFanLeft(leftChain
, segIndexLarge
, segIndexSmall
, grid
, gridV
, leftU
, rightU
, pStream
, 0);
276 tempBot
[0] = grid
->get_u_value(rightU
);
277 tempBot
[1] = grid
->get_v_value(gridV
);
278 monoTriangulation2(topVertex
, tempBot
, leftChain
, leftStart
, segIndexSmall
, 1, pStream
);
281 else //the topVertex forms a fan with the grid points
282 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, topVertex
, pStream
);
286 void sampleTopLeftWithGridLine(Real
* topVertex
,
287 vertexArray
* leftChain
,
297 Int segIndexSmall
= 0, segIndexLarge
;
298 //if left chain is empty, then there is only one top vertex with one grid
300 if(leftEnd
< leftStart
) {
301 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, topVertex
, pStream
);
304 findTopLeftSegment(leftChain
,
307 grid
->get_u_value(leftU
),
311 sampleTopLeftWithGridLinePost(topVertex
,
325 //return 1 if saprator exits, 0 otherwise
326 Int
findTopSeparator(vertexArray
* leftChain
,
329 vertexArray
* rightChain
,
336 Int oldLeftI
, oldRightI
, newLeftI
, newRightI
;
338 Real leftMax
/*= leftChain->getVertex(leftEndIndex)[0]*/;
339 Real rightMin
/*= rightChain->getVertex(rightEndIndex)[0]*/;
340 if(leftChain
->getVertex(leftEndIndex
)[1] > rightChain
->getVertex(rightEndIndex
)[1]) //left higher
342 oldLeftI
= leftEndIndex
+1;
343 oldRightI
= rightEndIndex
;
344 leftMax
= leftChain
->getVertex(leftEndIndex
)[0] - Real(1.0); //initilza to left of leftU
345 rightMin
= rightChain
->getVertex(rightEndIndex
)[0];
349 oldLeftI
= leftEndIndex
;
350 oldRightI
= rightEndIndex
+1;
351 leftMax
= leftChain
->getVertex(leftEndIndex
)[0];
352 rightMin
= rightChain
->getVertex(rightEndIndex
)[0] + Real(1.0);
355 //i: the current working leftChain index,
356 //j: the current working rightChain index,
357 //if left(i) is higher than right(j), then the two chains beloew right(j) are separated.
358 //else the two chains below left(i) are separeated.
364 newRightI
= oldRightI
;
366 if(i
<leftStartIndex
) //left chain is done, go through remining right chain.
368 for(k
=j
-1; k
>= rightStartIndex
; k
--)
370 if(rightChain
->getVertex(k
)[0] > leftMax
) //no conflict
372 //update oldRightI if necessary
373 if(rightChain
->getVertex(k
)[0] < rightMin
)
375 rightMin
= rightChain
->getVertex(k
)[0];
379 else //there is a conflict
380 break; //the for-loop. below right(k-1) is seperated: oldLeftI, oldRightI.
382 break; //the while loop
384 else if(j
<rightStartIndex
) //rightChain is done
386 for(k
=i
-1; k
>= leftStartIndex
; k
--)
388 if(leftChain
->getVertex(k
)[0] < rightMin
) //no conflict
390 //update oldLeftI if necessary
391 if(leftChain
->getVertex(k
)[0] > leftMax
)
393 leftMax
= leftChain
->getVertex(k
)[0];
397 else //there is a conflict
398 break; //the for loop
400 break; //the while loop
402 else if(leftChain
->getVertex(i
)[1] > rightChain
->getVertex(j
)[1]) //left hgiher
404 if(leftChain
->getVertex(i
)[0] > leftMax
) //update leftMax and newLeftI.
406 leftMax
= leftChain
->getVertex(i
)[0];
409 for(k
=j
-1; k
>= rightStartIndex
; k
--) //update rightMin and newRightI.
411 if(rightChain
->getVertex(k
)[1] > leftChain
->getVertex(i
)[1])
413 if(rightChain
->getVertex(k
)[0] < rightMin
)
415 rightMin
= rightChain
->getVertex(k
)[0];
419 j
= k
; //next working j, since j will be higher than i in next loop
420 if(leftMax
>= rightMin
) //there is a conflict
422 else //still no conflict
425 oldRightI
= newRightI
;
430 if(rightChain
->getVertex(j
)[0] < rightMin
)
432 rightMin
= rightChain
->getVertex(j
)[0];
435 for(k
=i
-1; k
>= leftStartIndex
; k
--)
437 if(leftChain
->getVertex(k
)[1] > rightChain
->getVertex(j
)[1])
439 if(leftChain
->getVertex(k
)[0] > leftMax
)
441 leftMax
= leftChain
->getVertex(k
)[0];
445 i
= k
; //next working i, since i will be higher than j next loop
447 if(leftMax
>= rightMin
) //there is a conflict
449 else //still no conflict
452 oldRightI
= newRightI
;
456 //now oldLeftI and oldRightI are the desired separeator index, notice that there are not necessarily valid
457 if(oldLeftI
> leftEndIndex
|| oldRightI
> rightEndIndex
)
461 ret_sep_left
= oldLeftI
;
462 ret_sep_right
= oldRightI
;
468 void sampleCompTop(Real
* topVertex
,
469 vertexArray
* leftChain
,
471 vertexArray
* rightChain
,
473 gridBoundaryChain
* leftGridChain
,
474 gridBoundaryChain
* rightGridChain
,
476 Int up_leftCornerWhere
,
477 Int up_leftCornerIndex
,
478 Int up_rightCornerWhere
,
479 Int up_rightCornerIndex
,
482 if(up_leftCornerWhere
== 1 && up_rightCornerWhere
== 1) //the top is topVertex with possible grid points
484 leftGridChain
->getGrid()->outputFanWithPoint(leftGridChain
->getVlineIndex(gridIndex1
),
485 leftGridChain
->getUlineIndex(gridIndex1
),
486 rightGridChain
->getUlineIndex(gridIndex1
),
492 else if(up_leftCornerWhere
!= 0)
496 if(up_leftCornerWhere
== 1){
497 tempRightStart
= rightStartIndex
;
502 tempRightStart
= up_leftCornerIndex
+1;
503 tempTop
= rightChain
->getVertex(up_leftCornerIndex
);
505 sampleTopRightWithGridLine(tempTop
, rightChain
, tempRightStart
, up_rightCornerIndex
,
506 rightGridChain
->getGrid(),
507 leftGridChain
->getVlineIndex(gridIndex1
),
508 leftGridChain
->getUlineIndex(gridIndex1
),
509 rightGridChain
->getUlineIndex(gridIndex1
),
512 else if(up_rightCornerWhere
!= 2)
516 if(up_rightCornerWhere
== 1)
518 tempLeftStart
= leftStartIndex
;
523 tempLeftStart
= up_rightCornerIndex
+1;
524 tempTop
= leftChain
->getVertex(up_rightCornerIndex
);
527 sampleTopLeftWithGridLine(tempTop, leftChain, tempLeftStart, up_leftCornerIndex,
528 leftGridChain->getGrid(),
529 leftGridChain->getVlineIndex(gridIndex1),
530 leftGridChain->getUlineIndex(gridIndex1),
531 rightGridChain->getUlineIndex(gridIndex1),
534 sampleCompTopSimple(topVertex
,
548 else //up_leftCornerWhere == 0, up_rightCornerWhere == 2.
550 sampleCompTopSimple(topVertex
,
564 #ifdef NOT_REACHABLE //code is not reachable, for test purpose only
565 //the following code is trying to do some optimization, but not quite working, also see sampleCompBot.C:
566 Int sep_left
, sep_right
;
567 if(findTopSeparator(leftChain
,
578 if( leftChain
->getVertex(sep_left
)[0] >= leftGridChain
->get_u_value(gridIndex1
) &&
579 rightChain
->getVertex(sep_right
)[0] <= rightGridChain
->get_u_value(gridIndex1
))
582 Int segLeftSmall
, segLeftLarge
, segRightSmall
, segRightLarge
;
583 Int valid
=1; //whether the gridStep is valid or not.
584 findTopLeftSegment(leftChain
,
587 leftGridChain
->get_u_value(gridIndex1
),
590 findTopRightSegment(rightChain
,
593 rightGridChain
->get_u_value(gridIndex1
),
596 if(leftChain
->getVertex(segLeftSmall
)[1] >= rightChain
->getVertex(segRightSmall
)[1])
598 gridSep
= rightGridChain
->getUlineIndex(gridIndex1
);
599 while(leftGridChain
->getGrid()->get_u_value(gridSep
) > leftChain
->getVertex(segLeftSmall
)[0])
601 if(segLeftSmall
<segLeftLarge
)
602 if(leftGridChain
->getGrid()->get_u_value(gridSep
) < leftChain
->getVertex(segLeftSmall
+1)[0])
609 gridSep
= leftGridChain
->getUlineIndex(gridIndex1
);
610 while(leftGridChain
->getGrid()->get_u_value(gridSep
) < rightChain
->getVertex(segRightSmall
)[0])
612 if(segRightSmall
<segRightLarge
)
613 if(leftGridChain
->getGrid()->get_u_value(gridSep
) > rightChain
->getVertex(segRightSmall
+1)[0])
621 sampleCompTopSimple(topVertex
,
637 sampleTopLeftWithGridLinePost(leftChain
->getVertex(segLeftSmall
),
643 leftGridChain
->getGrid(),
644 leftGridChain
->getVlineIndex(gridIndex1
),
645 leftGridChain
->getUlineIndex(gridIndex1
),
648 sampleTopRightWithGridLinePost(rightChain
->getVertex(segRightSmall
),
654 leftGridChain
->getGrid(),
655 leftGridChain
->getVlineIndex(gridIndex1
),
657 rightGridChain
->getUlineIndex(gridIndex1
),
660 tempBot
[0] = leftGridChain
->getGrid()->get_u_value(gridSep
);
661 tempBot
[1] = leftGridChain
->get_v_value(gridIndex1
);
662 monoTriangulationRecGen(topVertex
, tempBot
,
663 leftChain
, leftStartIndex
, segLeftSmall
,
664 rightChain
, rightStartIndex
, segRightSmall
,
667 }//end if both sides have vetices inside the gridboundary points
668 else if(leftChain
->getVertex(sep_left
)[0] >= leftGridChain
->get_u_value(gridIndex1
)) //left is in, right is nout
671 Int segLeftSmall
, segLeftLarge
;
672 findTopLeftSegment(leftChain
,
675 leftGridChain
->get_u_value(gridIndex1
),
678 assert(segLeftLarge
>= sep_left
);
679 monoTriangulation2(leftChain
->getVertex(segLeftLarge
),
680 leftGridChain
->get_vertex(gridIndex1
),
684 1, //a increase chain,
687 stripOfFanLeft(leftChain
, segLeftLarge
, segLeftSmall
,
688 leftGridChain
->getGrid(),
689 leftGridChain
->getVlineIndex(gridIndex1
),
690 leftGridChain
->getUlineIndex(gridIndex1
),
691 rightGridChain
->getUlineIndex(gridIndex1
),
695 monoTriangulationRecGen(topVertex
, rightGridChain
->get_vertex(gridIndex1
),
696 leftChain
, leftStartIndex
, segLeftSmall
,
697 rightChain
, rightStartIndex
, up_rightCornerIndex
,
699 }//end left in right out
700 else if(rightChain
->getVertex(sep_right
)[0] <= rightGridChain
->get_u_value(gridIndex1
))
702 Int segRightSmall
, segRightLarge
;
703 findTopRightSegment(rightChain
,
706 rightGridChain
->get_u_value(gridIndex1
),
709 assert(segRightLarge
>=sep_right
);
710 monoTriangulation2(rightChain
->getVertex(segRightLarge
),
711 rightGridChain
->get_vertex(gridIndex1
),
715 0, //a decrease chain
717 stripOfFanRight(rightChain
, segRightLarge
, segRightSmall
,
718 rightGridChain
->getGrid(),
719 rightGridChain
->getVlineIndex(gridIndex1
),
720 leftGridChain
->getUlineIndex(gridIndex1
),
721 rightGridChain
->getUlineIndex(gridIndex1
),
725 monoTriangulationRecGen(topVertex
, leftGridChain
->get_vertex(gridIndex1
),
726 leftChain
, leftStartIndex
, up_leftCornerIndex
,
727 rightChain
, rightStartIndex
,segRightSmall
,
730 }//end left out rigth in
731 else //left out , right out
734 sampleCompTopSimple(topVertex
,
747 }//end leftout, right out
748 }//end if separator exixts.
752 sampleCompTopSimple(topVertex
,
768 }//end if the function
771 static void sampleCompTopSimpleOpt(gridWrap
* grid
,
773 Real
* topVertex
, Real
* botVertex
,
774 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
775 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
778 if(gridV
<= 0 || dec_end
<dec_current
|| inc_end
<inc_current
)
780 monoTriangulationRecGenOpt(topVertex
, botVertex
,
781 inc_chain
, inc_current
, inc_end
,
782 dec_chain
, dec_current
, dec_end
,
786 if(grid
->get_v_value(gridV
+1) >= topVertex
[1])
788 monoTriangulationRecGenOpt(topVertex
, botVertex
,
789 inc_chain
, inc_current
, inc_end
,
790 dec_chain
, dec_current
, dec_end
,
795 Real currentV
= grid
->get_v_value(gridV
+1);
796 if(inc_chain
->getVertex(inc_end
)[1] <= currentV
&&
797 dec_chain
->getVertex(dec_end
)[1] < currentV
)
799 //find i bottom up so that inc_chain[i]<= curentV and inc_chain[i-1] > currentV,
800 //find j botom up so that dec_chain[j] < currentV and dec_chain[j-1] >= currentV
801 for(i
=inc_end
; i
>= inc_current
; i
--)
803 if(inc_chain
->getVertex(i
)[1] > currentV
)
807 for(j
=dec_end
; j
>= dec_current
; j
--)
809 if(dec_chain
->getVertex(j
)[1] >= currentV
)
813 if(inc_chain
->getVertex(i
)[1] <= dec_chain
->getVertex(j
)[1])
815 //find the k so that dec_chain[k][1] < inc_chain[i][1]
816 for(k
=j
; k
<=dec_end
; k
++)
818 if(dec_chain
->getVertex(k
)[1] < inc_chain
->getVertex(i
)[1])
821 //we know that dec_chain[j][1] >= inc_chian[i][1]
822 //we know that dec_chain[k-1][1]>=inc_chain[i][1]
823 //we know that dec_chian[k][1] < inc_chain[i][1]
824 //find l in [j, k-1] so that dec_chain[l][0] 0 is closest to
827 Real tempI
= Real(j
);
828 Real tempMin
= (Real
)fabs(inc_chain
->getVertex(i
)[0] - dec_chain
->getVertex(j
)[0]);
829 for(l
=j
+1; l
<= k
-1; l
++)
831 if(fabs(inc_chain
->getVertex(i
)[0] - dec_chain
->getVertex(l
)[0])
834 tempMin
= (Real
)fabs(inc_chain
->getVertex(i
)[0] - dec_chain
->getVertex(l
)[0]);
838 //inc_chain[i] and dec_chain[tempI] are connected.
839 monoTriangulationRecGenOpt(dec_chain
->getVertex((int)tempI
),
841 inc_chain
, i
, inc_end
,
842 dec_chain
, (int)(tempI
+1), dec_end
,
844 //recursively do the rest
845 sampleCompTopSimpleOpt(grid
,
847 topVertex
, inc_chain
->getVertex(i
),
848 inc_chain
, inc_current
, i
-1,
849 dec_chain
, dec_current
, (int)tempI
,
854 //find the k so that inc_chain[k][1] <= dec_chain[j][1]
855 for(k
=i
; k
<=inc_end
; k
++)
857 if(inc_chain
->getVertex(k
)[1] <= dec_chain
->getVertex(j
)[1])
860 //we know that inc_chain[i] > dec_chain[j]
861 //we know that inc_chain[k-1][1] > dec_chain[j][1]
862 //we know that inc_chain[k][1] <= dec_chain[j][1]
863 //so we find l between [i,k-1] so that
864 //inc_chain[l][0] is the closet to dec_chain[j][0]
867 Real tempMin
= (Real
)fabs(inc_chain
->getVertex(i
)[0] - dec_chain
->getVertex(j
)[0]);
868 for(l
=i
+1; l
<=k
-1; l
++)
870 if(fabs(inc_chain
->getVertex(l
)[0] - dec_chain
->getVertex(j
)[0]) <= tempMin
)
872 tempMin
= (Real
)fabs(inc_chain
->getVertex(l
)[0] - dec_chain
->getVertex(j
)[0]);
877 //inc_chain[tempI] and dec_chain[j] are connected
879 monoTriangulationRecGenOpt(inc_chain
->getVertex(tempI
),
881 inc_chain
, tempI
+1, inc_end
,
882 dec_chain
, j
, dec_end
,
885 //recurvesily do the rest
886 sampleCompTopSimpleOpt(grid
, gridV
+1,
887 topVertex
, dec_chain
->getVertex(j
),
888 inc_chain
, inc_current
, tempI
,
889 dec_chain
, dec_current
, j
-1,
893 else //go to the next higher gridV
895 sampleCompTopSimpleOpt(grid
,
897 topVertex
, botVertex
,
898 inc_chain
, inc_current
, inc_end
,
899 dec_chain
, dec_current
, dec_end
,
904 void sampleCompTopSimple(Real
* topVertex
,
905 vertexArray
* leftChain
,
907 vertexArray
* rightChain
,
909 gridBoundaryChain
* leftGridChain
,
910 gridBoundaryChain
* rightGridChain
,
912 Int up_leftCornerWhere
,
913 Int up_leftCornerIndex
,
914 Int up_rightCornerWhere
,
915 Int up_rightCornerIndex
,
918 //the plan is to use monotriangulation algortihm.
922 Int ActualLeftStart
, ActualLeftEnd
;
923 Int ActualRightStart
, ActualRightEnd
;
925 //creat an array to store the points on the grid line
926 gridWrap
* grid
= leftGridChain
->getGrid();
927 Int gridV
= leftGridChain
->getVlineIndex(gridIndex1
);
928 Int gridLeftU
= leftGridChain
->getUlineIndex(gridIndex1
);
929 Int gridRightU
= rightGridChain
->getUlineIndex(gridIndex1
);
931 Real2
* gridPoints
= (Real2
*) malloc(sizeof(Real2
) * (gridRightU
- gridLeftU
+1));
934 for(k
=0, i
=gridRightU
; i
>= gridLeftU
; i
--, k
++)
936 gridPoints
[k
][0] = grid
->get_u_value(i
);
937 gridPoints
[k
][1] = grid
->get_v_value(gridV
);
940 if(up_leftCornerWhere
!= 2)
941 ActualRightStart
= rightStartIndex
;
943 ActualRightStart
= up_leftCornerIndex
+1; //up_leftCornerIndex will be the ActualTop
945 if(up_rightCornerWhere
!= 2) //right corner is not on right chain
946 ActualRightEnd
= rightStartIndex
-1; //meaning that there is no actual rigth section
948 ActualRightEnd
= up_rightCornerIndex
;
950 vertexArray
ActualRightChain(max(0, ActualRightEnd
-ActualRightStart
+1) + gridRightU
-gridLeftU
+1);
952 for(i
=ActualRightStart
; i
<= ActualRightEnd
; i
++)
953 ActualRightChain
.appendVertex(rightChain
->getVertex(i
));
954 for(i
=0; i
<gridRightU
-gridLeftU
+1; i
++)
955 ActualRightChain
.appendVertex(gridPoints
[i
]);
957 //determine ActualLeftEnd
958 if(up_leftCornerWhere
!= 0)
959 ActualLeftEnd
= leftStartIndex
-1;
961 ActualLeftEnd
= up_leftCornerIndex
;
963 if(up_rightCornerWhere
!= 0)
964 ActualLeftStart
= leftStartIndex
;
966 ActualLeftStart
= up_rightCornerIndex
+1; //up_rightCornerIndex will be the actual top
968 if(up_leftCornerWhere
== 0)
970 if(up_rightCornerWhere
== 0)
971 ActualTop
= leftChain
->getVertex(up_rightCornerIndex
);
973 ActualTop
= topVertex
;
975 else if(up_leftCornerWhere
== 1)
976 ActualTop
= topVertex
;
977 else //up_leftCornerWhere == 2
978 ActualTop
= rightChain
->getVertex(up_leftCornerIndex
);
980 ActualBot
= gridPoints
[gridRightU
- gridLeftU
];
985 if(leftChain
->getVertex(ActualLeftEnd
)[1] == ActualBot
[1])
988 monoTriangulationRecGenOpt(ActualTop, leftChain->getVertex(ActualLeftEnd),
990 ActualLeftStart, ActualLeftEnd-1,
993 ActualRightChain.getNumElements()-1,
997 sampleCompTopSimpleOpt(grid
, gridV
,
998 ActualTop
, leftChain
->getVertex(ActualLeftEnd
),
1000 ActualLeftStart
, ActualLeftEnd
-1,
1003 ActualRightChain
.getNumElements()-1,
1010 monoTriangulationRecGenOpt(ActualTop, ActualBot, leftChain,
1011 ActualLeftStart, ActualLeftEnd,
1013 0, ActualRightChain.getNumElements()-2, //the last is the bot.
1017 sampleCompTopSimpleOpt(grid
, gridV
,
1018 ActualTop
, ActualBot
, leftChain
,
1019 ActualLeftStart
, ActualLeftEnd
,
1021 0, ActualRightChain
.getNumElements()-2, //the last is the bot.