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.
34 ** $Date: 2001/03/17 00:25:41 $ $Revision: 1.1 $
37 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/sampleCompTop.cc,v 1.1 2001/03/17 00:25:41 brianp Exp $
44 #include "sampleCompTop.h"
45 #include "sampleCompRight.h"
47 #define max(a,b) ((a>b)? a:b)
49 //return : index_small, and index_large,
50 //from [small, large] is strictly U-monotne,
51 //from [large+1, end] is <u
52 //and vertex[large][0] is >= u
53 //if eveybody is <u, the large = start-1.
54 //otherwise both large and small are meaningful and we have start<=small<=large<=end
55 void findTopLeftSegment(vertexArray
* leftChain
,
64 assert(leftStart
<= leftEnd
);
65 for(i
=leftEnd
; i
>= leftStart
; i
--)
67 if(leftChain
->getVertex(i
)[0] >= u
)
71 if(ret_index_large
>= leftStart
)
73 for(i
=ret_index_large
; i
>leftStart
; i
--)
75 if(leftChain
->getVertex(i
-1)[0] <= leftChain
->getVertex(i
)[0])
82 void findTopRightSegment(vertexArray
* rightChain
,
90 assert(rightStart
<=rightEnd
);
91 for(i
=rightEnd
; i
>=rightStart
; i
--)
93 if(rightChain
->getVertex(i
)[0] <= u
)
97 if(ret_index_large
>= rightStart
)
99 for(i
=ret_index_large
; i
>rightStart
;i
--)
101 if(rightChain
->getVertex(i
-1)[0] >= rightChain
->getVertex(i
)[0])
109 void sampleTopRightWithGridLinePost(Real
* topVertex
,
110 vertexArray
* rightChain
,
121 //the possible section which is to the right of rightU
122 if(segIndexLarge
< rightEnd
)
125 if(segIndexLarge
>= rightStart
)
126 tempTop
= rightChain
->getVertex(segIndexLarge
);
130 tempBot
[0] = grid
->get_u_value(rightU
);
131 tempBot
[1] = grid
->get_v_value(gridV
);
132 monoTriangulationRecGenOpt(tempTop
, tempBot
,
134 rightChain
, segIndexLarge
+1, rightEnd
,
137 monoTriangulation2(tempTop, tempBot,
141 0, //a decrease chian
147 //the possible section which is strictly Umonotone
148 if(segIndexLarge
>= rightStart
)
150 stripOfFanRight(rightChain
, segIndexLarge
, segIndexSmall
, grid
, gridV
, leftU
, rightU
, pStream
, 0);
152 tempBot
[0] = grid
->get_u_value(leftU
);
153 tempBot
[1] = grid
->get_v_value(gridV
);
154 monoTriangulation2(topVertex
, tempBot
, rightChain
, rightStart
, segIndexSmall
, 0, pStream
);
156 else //the topVertex forms a fan with the grid points
157 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, topVertex
, pStream
);
160 void sampleTopRightWithGridLine(Real
* topVertex
,
161 vertexArray
* rightChain
,
171 //if right chian is empty, then there is only one topVertex with one grid line
172 if(rightEnd
< rightStart
){
173 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, topVertex
, pStream
);
177 Int segIndexSmall
, segIndexLarge
;
178 findTopRightSegment(rightChain
,
181 grid
->get_u_value(rightU
),
185 sampleTopRightWithGridLinePost(topVertex
, rightChain
,
198 void sampleTopLeftWithGridLinePost(Real
* topVertex
,
199 vertexArray
* leftChain
,
210 //the possible section which is to the left of leftU
212 if(segIndexLarge
< leftEnd
)
215 if(segIndexLarge
>= leftStart
)
216 tempTop
= leftChain
->getVertex(segIndexLarge
);
220 tempBot
[0] = grid
->get_u_value(leftU
);
221 tempBot
[1] = grid
->get_v_value(gridV
);
223 monoTriangulation2(tempTop
, tempBot
,
227 1, //a increase chian
231 //the possible section which is strictly Umonotone
232 if(segIndexLarge
>= leftStart
)
234 //if there are grid points which are to the right of topV,
235 //then we should use topVertex to form a fan with these points to
236 //optimize the triangualtion
238 if(topVertex
[0] >= grid
->get_u_value(rightU
))
242 //we also have to make sure that topVertex are the right most vertex
245 for(i
=leftStart
; i
<=segIndexSmall
; i
++)
246 if(leftChain
->getVertex(i
)[0] >= topVertex
[0])
255 //find midU so that grid->get_u_value(midU) >= topVertex[0]
256 //and grid->get_u_value(midU-1) < topVertex[0]
258 while(grid
->get_u_value(midU
) >= topVertex
[0])
266 grid
->outputFanWithPoint(gridV
, midU
, rightU
, topVertex
, pStream
);
267 stripOfFanLeft(leftChain
, segIndexLarge
, segIndexSmall
, grid
, gridV
, leftU
, midU
, pStream
, 0);
269 tempBot
[0] = grid
->get_u_value(midU
);
270 tempBot
[1] = grid
->get_v_value(gridV
);
271 monoTriangulation2(topVertex
, tempBot
, leftChain
, leftStart
, segIndexSmall
, 1, pStream
);
276 stripOfFanLeft(leftChain
, segIndexLarge
, segIndexSmall
, grid
, gridV
, leftU
, rightU
, pStream
, 0);
278 tempBot
[0] = grid
->get_u_value(rightU
);
279 tempBot
[1] = grid
->get_v_value(gridV
);
280 monoTriangulation2(topVertex
, tempBot
, leftChain
, leftStart
, segIndexSmall
, 1, pStream
);
283 else //the topVertex forms a fan with the grid points
284 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, topVertex
, pStream
);
288 void sampleTopLeftWithGridLine(Real
* topVertex
,
289 vertexArray
* leftChain
,
299 Int segIndexSmall
, segIndexLarge
;
300 //if left chain is empty, then there is only one top vertex with one grid
302 if(leftEnd
< leftStart
) {
303 grid
->outputFanWithPoint(gridV
, leftU
, rightU
, topVertex
, pStream
);
306 findTopLeftSegment(leftChain
,
309 grid
->get_u_value(leftU
),
313 sampleTopLeftWithGridLinePost(topVertex
,
327 //return 1 if saprator exits, 0 otherwise
328 Int
findTopSeparator(vertexArray
* leftChain
,
331 vertexArray
* rightChain
,
338 Int oldLeftI
, oldRightI
, newLeftI
, newRightI
;
340 Real leftMax
/*= leftChain->getVertex(leftEndIndex)[0]*/;
341 Real rightMin
/*= rightChain->getVertex(rightEndIndex)[0]*/;
342 if(leftChain
->getVertex(leftEndIndex
)[1] > rightChain
->getVertex(rightEndIndex
)[1]) //left higher
344 oldLeftI
= leftEndIndex
+1;
345 oldRightI
= rightEndIndex
;
346 leftMax
= leftChain
->getVertex(leftEndIndex
)[0] - 1.0; //initilza to left of leftU
347 rightMin
= rightChain
->getVertex(rightEndIndex
)[0];
351 oldLeftI
= leftEndIndex
;
352 oldRightI
= rightEndIndex
+1;
353 leftMax
= leftChain
->getVertex(leftEndIndex
)[0];
354 rightMin
= rightChain
->getVertex(rightEndIndex
)[0] + 1.0;
357 //i: the current working leftChain index,
358 //j: the current working rightChain index,
359 //if left(i) is higher than right(j), then the two chains beloew right(j) are separated.
360 //else the two chains below left(i) are separeated.
366 newRightI
= oldRightI
;
368 if(i
<leftStartIndex
) //left chain is done, go through remining right chain.
370 for(k
=j
-1; k
>= rightStartIndex
; k
--)
372 if(rightChain
->getVertex(k
)[0] > leftMax
) //no conflict
374 //update oldRightI if necessary
375 if(rightChain
->getVertex(k
)[0] < rightMin
)
377 rightMin
= rightChain
->getVertex(k
)[0];
381 else //there is a conflict
382 break; //the for-loop. below right(k-1) is seperated: oldLeftI, oldRightI.
384 break; //the while loop
386 else if(j
<rightStartIndex
) //rightChain is done
388 for(k
=i
-1; k
>= leftStartIndex
; k
--)
390 if(leftChain
->getVertex(k
)[0] < rightMin
) //no conflict
392 //update oldLeftI if necessary
393 if(leftChain
->getVertex(k
)[0] > leftMax
)
395 leftMax
= leftChain
->getVertex(k
)[0];
399 else //there is a conflict
400 break; //the for loop
402 break; //the while loop
404 else if(leftChain
->getVertex(i
)[1] > rightChain
->getVertex(j
)[1]) //left hgiher
406 if(leftChain
->getVertex(i
)[0] > leftMax
) //update leftMax and newLeftI.
408 leftMax
= leftChain
->getVertex(i
)[0];
411 for(k
=j
-1; k
>= rightStartIndex
; k
--) //update rightMin and newRightI.
413 if(rightChain
->getVertex(k
)[1] > leftChain
->getVertex(i
)[1])
415 if(rightChain
->getVertex(k
)[0] < rightMin
)
417 rightMin
= rightChain
->getVertex(k
)[0];
421 j
= k
; //next working j, since j will be higher than i in next loop
422 if(leftMax
>= rightMin
) //there is a conflict
424 else //still no conflict
427 oldRightI
= newRightI
;
432 if(rightChain
->getVertex(j
)[0] < rightMin
)
434 rightMin
= rightChain
->getVertex(j
)[0];
437 for(k
=i
-1; k
>= leftStartIndex
; k
--)
439 if(leftChain
->getVertex(k
)[1] > rightChain
->getVertex(j
)[1])
441 if(leftChain
->getVertex(k
)[0] > leftMax
)
443 leftMax
= leftChain
->getVertex(k
)[0];
447 i
= k
; //next working i, since i will be higher than j next loop
449 if(leftMax
>= rightMin
) //there is a conflict
451 else //still no conflict
454 oldRightI
= newRightI
;
458 //now oldLeftI and oldRightI are the desired separeator index, notice that there are not necessarily valid
459 if(oldLeftI
> leftEndIndex
|| oldRightI
> rightEndIndex
)
463 ret_sep_left
= oldLeftI
;
464 ret_sep_right
= oldRightI
;
470 void sampleCompTop(Real
* topVertex
,
471 vertexArray
* leftChain
,
473 vertexArray
* rightChain
,
475 gridBoundaryChain
* leftGridChain
,
476 gridBoundaryChain
* rightGridChain
,
478 Int up_leftCornerWhere
,
479 Int up_leftCornerIndex
,
480 Int up_rightCornerWhere
,
481 Int up_rightCornerIndex
,
484 if(up_leftCornerWhere
== 1 && up_rightCornerWhere
== 1) //the top is topVertex with possible grid points
486 leftGridChain
->getGrid()->outputFanWithPoint(leftGridChain
->getVlineIndex(gridIndex1
),
487 leftGridChain
->getUlineIndex(gridIndex1
),
488 rightGridChain
->getUlineIndex(gridIndex1
),
494 else if(up_leftCornerWhere
!= 0)
498 if(up_leftCornerWhere
== 1){
499 tempRightStart
= rightStartIndex
;
504 tempRightStart
= up_leftCornerIndex
+1;
505 tempTop
= rightChain
->getVertex(up_leftCornerIndex
);
507 sampleTopRightWithGridLine(tempTop
, rightChain
, tempRightStart
, up_rightCornerIndex
,
508 rightGridChain
->getGrid(),
509 leftGridChain
->getVlineIndex(gridIndex1
),
510 leftGridChain
->getUlineIndex(gridIndex1
),
511 rightGridChain
->getUlineIndex(gridIndex1
),
514 else if(up_rightCornerWhere
!= 2)
518 if(up_rightCornerWhere
== 1)
520 tempLeftStart
= leftStartIndex
;
525 tempLeftStart
= up_rightCornerIndex
+1;
526 tempTop
= leftChain
->getVertex(up_rightCornerIndex
);
529 sampleTopLeftWithGridLine(tempTop, leftChain, tempLeftStart, up_leftCornerIndex,
530 leftGridChain->getGrid(),
531 leftGridChain->getVlineIndex(gridIndex1),
532 leftGridChain->getUlineIndex(gridIndex1),
533 rightGridChain->getUlineIndex(gridIndex1),
536 sampleCompTopSimple(topVertex
,
550 else //up_leftCornerWhere == 0, up_rightCornerWhere == 2.
552 sampleCompTopSimple(topVertex
,
566 #ifdef NOT_REACHABLE //code is not reachable, for test purpose only
567 //the following code is trying to do some optimization, but not quite working, also see sampleCompBot.C:
568 Int sep_left
, sep_right
;
569 if(findTopSeparator(leftChain
,
580 if( leftChain
->getVertex(sep_left
)[0] >= leftGridChain
->get_u_value(gridIndex1
) &&
581 rightChain
->getVertex(sep_right
)[0] <= rightGridChain
->get_u_value(gridIndex1
))
584 Int segLeftSmall
, segLeftLarge
, segRightSmall
, segRightLarge
;
585 Int valid
=1; //whether the gridStep is valid or not.
586 findTopLeftSegment(leftChain
,
589 leftGridChain
->get_u_value(gridIndex1
),
592 findTopRightSegment(rightChain
,
595 rightGridChain
->get_u_value(gridIndex1
),
598 if(leftChain
->getVertex(segLeftSmall
)[1] >= rightChain
->getVertex(segRightSmall
)[1])
600 gridSep
= rightGridChain
->getUlineIndex(gridIndex1
);
601 while(leftGridChain
->getGrid()->get_u_value(gridSep
) > leftChain
->getVertex(segLeftSmall
)[0])
603 if(segLeftSmall
<segLeftLarge
)
604 if(leftGridChain
->getGrid()->get_u_value(gridSep
) < leftChain
->getVertex(segLeftSmall
+1)[0])
611 gridSep
= leftGridChain
->getUlineIndex(gridIndex1
);
612 while(leftGridChain
->getGrid()->get_u_value(gridSep
) < rightChain
->getVertex(segRightSmall
)[0])
614 if(segRightSmall
<segRightLarge
)
615 if(leftGridChain
->getGrid()->get_u_value(gridSep
) > rightChain
->getVertex(segRightSmall
+1)[0])
623 sampleCompTopSimple(topVertex
,
639 sampleTopLeftWithGridLinePost(leftChain
->getVertex(segLeftSmall
),
645 leftGridChain
->getGrid(),
646 leftGridChain
->getVlineIndex(gridIndex1
),
647 leftGridChain
->getUlineIndex(gridIndex1
),
650 sampleTopRightWithGridLinePost(rightChain
->getVertex(segRightSmall
),
656 leftGridChain
->getGrid(),
657 leftGridChain
->getVlineIndex(gridIndex1
),
659 rightGridChain
->getUlineIndex(gridIndex1
),
662 tempBot
[0] = leftGridChain
->getGrid()->get_u_value(gridSep
);
663 tempBot
[1] = leftGridChain
->get_v_value(gridIndex1
);
664 monoTriangulationRecGen(topVertex
, tempBot
,
665 leftChain
, leftStartIndex
, segLeftSmall
,
666 rightChain
, rightStartIndex
, segRightSmall
,
669 }//end if both sides have vetices inside the gridboundary points
670 else if(leftChain
->getVertex(sep_left
)[0] >= leftGridChain
->get_u_value(gridIndex1
)) //left is in, right is nout
673 Int segLeftSmall
, segLeftLarge
;
674 findTopLeftSegment(leftChain
,
677 leftGridChain
->get_u_value(gridIndex1
),
680 assert(segLeftLarge
>= sep_left
);
681 monoTriangulation2(leftChain
->getVertex(segLeftLarge
),
682 leftGridChain
->get_vertex(gridIndex1
),
686 1, //a increase chain,
689 stripOfFanLeft(leftChain
, segLeftLarge
, segLeftSmall
,
690 leftGridChain
->getGrid(),
691 leftGridChain
->getVlineIndex(gridIndex1
),
692 leftGridChain
->getUlineIndex(gridIndex1
),
693 rightGridChain
->getUlineIndex(gridIndex1
),
697 monoTriangulationRecGen(topVertex
, rightGridChain
->get_vertex(gridIndex1
),
698 leftChain
, leftStartIndex
, segLeftSmall
,
699 rightChain
, rightStartIndex
, up_rightCornerIndex
,
701 }//end left in right out
702 else if(rightChain
->getVertex(sep_right
)[0] <= rightGridChain
->get_u_value(gridIndex1
))
704 Int segRightSmall
, segRightLarge
;
705 findTopRightSegment(rightChain
,
708 rightGridChain
->get_u_value(gridIndex1
),
711 assert(segRightLarge
>=sep_right
);
712 monoTriangulation2(rightChain
->getVertex(segRightLarge
),
713 rightGridChain
->get_vertex(gridIndex1
),
717 0, //a decrease chain
719 stripOfFanRight(rightChain
, segRightLarge
, segRightSmall
,
720 rightGridChain
->getGrid(),
721 rightGridChain
->getVlineIndex(gridIndex1
),
722 leftGridChain
->getUlineIndex(gridIndex1
),
723 rightGridChain
->getUlineIndex(gridIndex1
),
727 monoTriangulationRecGen(topVertex
, leftGridChain
->get_vertex(gridIndex1
),
728 leftChain
, leftStartIndex
, up_leftCornerIndex
,
729 rightChain
, rightStartIndex
,segRightSmall
,
732 }//end left out rigth in
733 else //left out , right out
736 sampleCompTopSimple(topVertex
,
749 }//end leftout, right out
750 }//end if separator exixts.
754 sampleCompTopSimple(topVertex
,
770 }//end if the function
773 static void sampleCompTopSimpleOpt(gridWrap
* grid
,
775 Real
* topVertex
, Real
* botVertex
,
776 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
777 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
780 if(gridV
<= 0 || dec_end
<dec_current
|| inc_end
<inc_current
)
782 monoTriangulationRecGenOpt(topVertex
, botVertex
,
783 inc_chain
, inc_current
, inc_end
,
784 dec_chain
, dec_current
, dec_end
,
788 if(grid
->get_v_value(gridV
+1) >= topVertex
[1])
790 monoTriangulationRecGenOpt(topVertex
, botVertex
,
791 inc_chain
, inc_current
, inc_end
,
792 dec_chain
, dec_current
, dec_end
,
797 Real currentV
= grid
->get_v_value(gridV
+1);
798 if(inc_chain
->getVertex(inc_end
)[1] <= currentV
&&
799 dec_chain
->getVertex(dec_end
)[1] < currentV
)
801 //find i bottom up so that inc_chain[i]<= curentV and inc_chain[i-1] > currentV,
802 //find j botom up so that dec_chain[j] < currentV and dec_chain[j-1] >= currentV
803 for(i
=inc_end
; i
>= inc_current
; i
--)
805 if(inc_chain
->getVertex(i
)[1] > currentV
)
809 for(j
=dec_end
; j
>= dec_current
; j
--)
811 if(dec_chain
->getVertex(j
)[1] >= currentV
)
815 if(inc_chain
->getVertex(i
)[1] <= dec_chain
->getVertex(j
)[1])
817 //find the k so that dec_chain[k][1] < inc_chain[i][1]
818 for(k
=j
; k
<=dec_end
; k
++)
820 if(dec_chain
->getVertex(k
)[1] < inc_chain
->getVertex(i
)[1])
823 //we know that dec_chain[j][1] >= inc_chian[i][1]
824 //we know that dec_chain[k-1][1]>=inc_chain[i][1]
825 //we know that dec_chian[k][1] < inc_chain[i][1]
826 //find l in [j, k-1] so that dec_chain[l][0] 0 is closest to
830 Real tempMin
= fabs(inc_chain
->getVertex(i
)[0] - dec_chain
->getVertex(j
)[0]);
831 for(l
=j
+1; l
<= k
-1; l
++)
833 if(fabs(inc_chain
->getVertex(i
)[0] - dec_chain
->getVertex(l
)[0])
836 tempMin
= fabs(inc_chain
->getVertex(i
)[0] - dec_chain
->getVertex(l
)[0]);
840 //inc_chain[i] and dec_chain[tempI] are connected.
841 monoTriangulationRecGenOpt(dec_chain
->getVertex(tempI
),
843 inc_chain
, i
, inc_end
,
844 dec_chain
, (int)(tempI
+1), dec_end
,
846 //recursively do the rest
847 sampleCompTopSimpleOpt(grid
,
849 topVertex
, inc_chain
->getVertex(i
),
850 inc_chain
, inc_current
, i
-1,
851 dec_chain
, dec_current
, (int)tempI
,
856 //find the k so that inc_chain[k][1] <= dec_chain[j][1]
857 for(k
=i
; k
<=inc_end
; k
++)
859 if(inc_chain
->getVertex(k
)[1] <= dec_chain
->getVertex(j
)[1])
862 //we know that inc_chain[i] > dec_chain[j]
863 //we know that inc_chain[k-1][1] > dec_chain[j][1]
864 //we know that inc_chain[k][1] <= dec_chain[j][1]
865 //so we find l between [i,k-1] so that
866 //inc_chain[l][0] is the closet to dec_chain[j][0]
869 Real tempMin
= fabs(inc_chain
->getVertex(i
)[0] - dec_chain
->getVertex(j
)[0]);
870 for(l
=i
+1; l
<=k
-1; l
++)
872 if(fabs(inc_chain
->getVertex(l
)[0] - dec_chain
->getVertex(j
)[0]) <= tempMin
)
874 tempMin
= fabs(inc_chain
->getVertex(l
)[0] - dec_chain
->getVertex(j
)[0]);
879 //inc_chain[tempI] and dec_chain[j] are connected
881 monoTriangulationRecGenOpt(inc_chain
->getVertex(tempI
),
883 inc_chain
, tempI
+1, inc_end
,
884 dec_chain
, j
, dec_end
,
887 //recurvesily do the rest
888 sampleCompTopSimpleOpt(grid
, gridV
+1,
889 topVertex
, dec_chain
->getVertex(j
),
890 inc_chain
, inc_current
, tempI
,
891 dec_chain
, dec_current
, j
-1,
895 else //go to the next higher gridV
897 sampleCompTopSimpleOpt(grid
,
899 topVertex
, botVertex
,
900 inc_chain
, inc_current
, inc_end
,
901 dec_chain
, dec_current
, dec_end
,
906 void sampleCompTopSimple(Real
* topVertex
,
907 vertexArray
* leftChain
,
909 vertexArray
* rightChain
,
911 gridBoundaryChain
* leftGridChain
,
912 gridBoundaryChain
* rightGridChain
,
914 Int up_leftCornerWhere
,
915 Int up_leftCornerIndex
,
916 Int up_rightCornerWhere
,
917 Int up_rightCornerIndex
,
920 //the plan is to use monotriangulation algortihm.
924 Int ActualLeftStart
, ActualLeftEnd
;
925 Int ActualRightStart
, ActualRightEnd
;
927 //creat an array to store the points on the grid line
928 gridWrap
* grid
= leftGridChain
->getGrid();
929 Int gridV
= leftGridChain
->getVlineIndex(gridIndex1
);
930 Int gridLeftU
= leftGridChain
->getUlineIndex(gridIndex1
);
931 Int gridRightU
= rightGridChain
->getUlineIndex(gridIndex1
);
933 Real2
* gridPoints
= (Real2
*) malloc(sizeof(Real2
) * (gridRightU
- gridLeftU
+1));
936 for(k
=0, i
=gridRightU
; i
>= gridLeftU
; i
--, k
++)
938 gridPoints
[k
][0] = grid
->get_u_value(i
);
939 gridPoints
[k
][1] = grid
->get_v_value(gridV
);
942 if(up_leftCornerWhere
!= 2)
943 ActualRightStart
= rightStartIndex
;
945 ActualRightStart
= up_leftCornerIndex
+1; //up_leftCornerIndex will be the ActualTop
947 if(up_rightCornerWhere
!= 2) //right corner is not on right chain
948 ActualRightEnd
= rightStartIndex
-1; //meaning that there is no actual rigth section
950 ActualRightEnd
= up_rightCornerIndex
;
952 vertexArray
ActualRightChain(max(0, ActualRightEnd
-ActualRightStart
+1) + gridRightU
-gridLeftU
+1);
954 for(i
=ActualRightStart
; i
<= ActualRightEnd
; i
++)
955 ActualRightChain
.appendVertex(rightChain
->getVertex(i
));
956 for(i
=0; i
<gridRightU
-gridLeftU
+1; i
++)
957 ActualRightChain
.appendVertex(gridPoints
[i
]);
959 //determine ActualLeftEnd
960 if(up_leftCornerWhere
!= 0)
961 ActualLeftEnd
= leftStartIndex
-1;
963 ActualLeftEnd
= up_leftCornerIndex
;
965 if(up_rightCornerWhere
!= 0)
966 ActualLeftStart
= leftStartIndex
;
968 ActualLeftStart
= up_rightCornerIndex
+1; //up_rightCornerIndex will be the actual top
970 if(up_leftCornerWhere
== 0)
972 if(up_rightCornerWhere
== 0)
973 ActualTop
= leftChain
->getVertex(up_rightCornerIndex
);
975 ActualTop
= topVertex
;
977 else if(up_leftCornerWhere
== 1)
978 ActualTop
= topVertex
;
979 else //up_leftCornerWhere == 2
980 ActualTop
= rightChain
->getVertex(up_leftCornerIndex
);
982 ActualBot
= gridPoints
[gridRightU
- gridLeftU
];
987 if(leftChain
->getVertex(ActualLeftEnd
)[1] == ActualBot
[1])
990 monoTriangulationRecGenOpt(ActualTop, leftChain->getVertex(ActualLeftEnd),
992 ActualLeftStart, ActualLeftEnd-1,
995 ActualRightChain.getNumElements()-1,
999 sampleCompTopSimpleOpt(grid
, gridV
,
1000 ActualTop
, leftChain
->getVertex(ActualLeftEnd
),
1002 ActualLeftStart
, ActualLeftEnd
-1,
1005 ActualRightChain
.getNumElements()-1,
1012 monoTriangulationRecGenOpt(ActualTop, ActualBot, leftChain,
1013 ActualLeftStart, ActualLeftEnd,
1015 0, ActualRightChain.getNumElements()-2, //the last is the bot.
1019 sampleCompTopSimpleOpt(grid
, gridV
,
1020 ActualTop
, ActualBot
, leftChain
,
1021 ActualLeftStart
, ActualLeftEnd
,
1023 0, ActualRightChain
.getNumElements()-2, //the last is the bot.