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 "glimports.h"
43 #include "sampleCompRight.h"
45 #define max(a,b) ((a>b)? a:b)
46 #define min(a,b) ((a>b)? b:a)
52 /*notice that we need leftChain because the
53 *corners could be on the leftChain.
55 void sampleCompRight(Real
* topVertex
, Real
* botVertex
,
56 vertexArray
* leftChain
,
57 Int leftStartIndex
, Int leftEndIndex
,
58 vertexArray
* rightChain
,
59 Int rightStartIndex
, Int rightEndIndex
,
60 gridBoundaryChain
* rightGridChain
,
61 Int gridIndex1
, Int gridIndex2
,
62 Int up_rightCornerWhere
,
63 Int up_rightCornerIndex
,
64 Int down_rightCornerWhere
,
65 Int down_rightCornerIndex
,
68 /*find out whether there is a trim vertex which is
69 *inbetween the top and bot grid lines or not.
73 Int gridMidIndex1
= 0, gridMidIndex2
= 0;
74 //midIndex1: array[i] <= v, array[i+1] > v
75 //midIndex2: array[i] >= v, array[i+1] < v
76 midIndex1
= rightChain
->findIndexBelowGen(rightGridChain
->get_v_value(gridIndex1
),
79 midIndex2
= -1; //initilization
80 if(midIndex1
<= rightEndIndex
&& gridIndex1
< gridIndex2
)
81 if(rightChain
->getVertex(midIndex1
)[1] >= rightGridChain
->get_v_value(gridIndex2
))
83 //midIndex2 must exist:
84 midIndex2
= rightChain
->findIndexAboveGen(rightGridChain
->get_v_value(gridIndex2
),
85 midIndex1
, //midIndex1<=midIndex2
87 //find gridMidIndex1 so that either it=gridIndex1 when the gridline is
88 // at the same height as trim vertex midIndex1, or it is the last one
89 //which is strictly above midIndex1.
91 Real temp
= rightChain
->getVertex(midIndex1
)[1];
92 if(rightGridChain
->get_v_value(gridIndex1
) == temp
)
93 gridMidIndex1
= gridIndex1
;
96 gridMidIndex1
= gridIndex1
;
97 while(rightGridChain
->get_v_value(gridMidIndex1
) > temp
)
101 }//end of find gridMindIndex1
102 //find gridMidIndex2 so that it is the (first one below or equal
103 //midIndex) last one above or equal midIndex2
105 Real temp
= rightChain
->getVertex(midIndex2
)[1];
106 for(gridMidIndex2
= gridMidIndex1
+1; gridMidIndex2
<= gridIndex2
; gridMidIndex2
++)
107 if(rightGridChain
->get_v_value(gridMidIndex2
) <= temp
)
110 assert(gridMidIndex2
<= gridIndex2
);
111 }//end of find gridMidIndex2
116 //to interprete the corner information
119 Int cornerRightStart
;
122 Int cornerLeftDownStart
;
123 if(up_rightCornerWhere
== 2) //right corner is on right chain
125 cornerTop
= rightChain
->getVertex(up_rightCornerIndex
);
126 cornerRightStart
= up_rightCornerIndex
+1;
127 cornerLeftUpEnd
= -1; //no left
129 else if(up_rightCornerWhere
== 1) //right corner is on top
131 cornerTop
= topVertex
;
132 cornerRightStart
= rightStartIndex
;
133 cornerLeftUpEnd
= -1; //no left
135 else //right corner is on left chain
137 cornerTop
= topVertex
;
138 cornerRightStart
= rightStartIndex
;
139 cornerLeftUpEnd
= up_rightCornerIndex
;
142 if(down_rightCornerWhere
== 2) //right corner is on right chan
144 cornerBot
= rightChain
->getVertex(down_rightCornerIndex
);
145 cornerRightEnd
= down_rightCornerIndex
-1;
146 cornerLeftDownStart
= leftEndIndex
+1; //no left
148 else if (down_rightCornerWhere
== 1) //right corner is at bot
150 cornerBot
= botVertex
;
151 cornerRightEnd
= rightEndIndex
;
152 cornerLeftDownStart
= leftEndIndex
+1; //no left
154 else //right corner is on the left chain
156 cornerBot
= botVertex
;
157 cornerRightEnd
= rightEndIndex
;
158 cornerLeftDownStart
= down_rightCornerIndex
;
162 if(midIndex2
>= 0) //there is a trm point between grid lines
165 sampleRightSingleTrimEdgeRegionGen(cornerTop
, rightChain
->getVertex(midIndex1
),
175 0, //no left down section,
179 sampleRightSingleTrimEdgeRegionGen(rightChain
->getVertex(midIndex2
),
188 0, //no left up section
194 sampleRightStripRecF(rightChain
,
205 sampleRightSingleTrimEdgeRegionGen(cornerTop
, cornerBot
,
221 void sampleRightSingleTrimEdgeRegionGen(Real topVertex
[2], Real botVertex
[2],
222 vertexArray
* rightChain
,
225 gridBoundaryChain
* gridChain
,
228 vertexArray
* leftChain
,
236 /*creat an array to store all the up and down secments of the left chain,
237 *and the right end grid points
239 *although vertex array is a dynamic array, but to gain efficiency,
240 *it is better to initiliza the exact array size
242 vertexArray
vArray(gridEndIndex
-gridBeginIndex
+1 +
243 max(0,leftUpEnd
- leftUpBegin
+1)+
244 max(0,leftDownEnd
- leftDownBegin
+1));
245 //append the vertices on the up section of the left chain
246 for(i
=leftUpBegin
; i
<= leftUpEnd
; i
++)
247 vArray
.appendVertex(leftChain
->getVertex(i
));
249 //append the vertices of the right extremal grid points,
250 //and at the same time, perform triangulation for the stair cases
251 vArray
.appendVertex(gridChain
->get_vertex(gridBeginIndex
));
253 for(k
=1, i
=gridBeginIndex
+1; i
<= gridEndIndex
; i
++, k
++)
255 vArray
.appendVertex(gridChain
->get_vertex(i
));
257 //output the fan of the grid points of the (i)th and (i-1)th grid line.
258 gridChain
->rightEndFan(i
, pStream
);
261 //append all the vertices on the down section of the left chain
262 for(i
=leftDownBegin
; i
<= leftDownEnd
; i
++)
263 vArray
.appendVertex(leftChain
->getVertex(i
));
264 monoTriangulationRecGen(topVertex
, botVertex
,
265 &vArray
, 0, vArray
.getNumElements()-1,
266 rightChain
, rightStart
, rightEnd
,
270 void sampleRightSingleTrimEdgeRegion(Real upperVert
[2], Real lowerVert
[2],
271 gridBoundaryChain
* gridChain
,
277 vertexArray
vArray(endIndex
-beginIndex
+1);
278 vArray
.appendVertex(gridChain
->get_vertex(beginIndex
));
279 for(k
=1, i
=beginIndex
+1; i
<= endIndex
; i
++, k
++)
281 vArray
.appendVertex(gridChain
->get_vertex(i
));
282 //output the fan of the grid points of the (i)_th and i-1th gridLine
283 gridChain
->rightEndFan(i
, pStream
);
285 monoTriangulation2(upperVert
, lowerVert
, &vArray
, 0, endIndex
-beginIndex
,
286 1, //increase chain (to the left)
291 /*the gridlines from rightGridChainStartIndex to
292 *rightGridChainEndIndex are assumed to form a
293 *connected componenet
294 *the trm vertex of topRightIndex is assumed to be below
295 *or equal the first gridLine, and the trm vertex of
296 *botRightIndex is assumed to be above or equal the last gridline
297 **there could be multipe trm vertices equal to the last gridline, but
298 **only one could be equal to top gridline. shape: ____| (recall that
299 **for left chain recF, we allow shape: |----
300 *if botRightIndex<topRightIndex, then no connected componenet exists, and
301 *no triangles are generated.
302 *Othewise, botRightIndex>= topRightIndex, there is at least one triangles to
305 void sampleRightStripRecF(vertexArray
* rightChain
,
308 gridBoundaryChain
* rightGridChain
,
309 Int rightGridChainStartIndex
,
310 Int rightGridChainEndIndex
,
315 //sstop conditionL: if topRightIndex > botRightIndex, then stop
316 if(topRightIndex
> botRightIndex
)
319 //if there is only one grid line, return
320 if(rightGridChainStartIndex
>= rightGridChainEndIndex
)
324 assert(rightChain
->getVertex(topRightIndex
)[1] <= rightGridChain
->get_v_value(rightGridChainStartIndex
) &&
325 rightChain
->getVertex(botRightIndex
)[1] >= rightGridChain
->get_v_value(rightGridChainEndIndex
));
327 //firstfind the first trim vertex which is strictly below the second top
329 Real secondGridChainV
= rightGridChain
->get_v_value(rightGridChainStartIndex
+1);
330 Int index1
= topRightIndex
;
331 while(rightChain
->getVertex(index1
)[1] >= secondGridChainV
){
333 if(index1
> botRightIndex
)
336 //now rightChain->getVertex(index1-1)[1] >= secondGridChainV and
337 //rightChain->getVertex(index1)[1] < secondGridChainV and
338 //we should include index1-1 to perform a gridStep
341 //now we have rightChain->getVertex(index1)[1] >= secondGridChainV, and
342 //rightChain->getVertex(index1+1)[1] < secondGridChainV
343 sampleRightOneGridStep(rightChain
, topRightIndex
, index1
, rightGridChain
, rightGridChainStartIndex
, pStream
);
345 //if rightChain->getVertex(index1)[1] ==secondGridChainV then we can
346 //recurvesively to the rest
347 if(rightChain
->getVertex(index1
)[1] == secondGridChainV
)
351 sampleRightStripRecF(rightChain
, index1
, botRightIndex
, rightGridChain
, rightGridChainStartIndex
+1, rightGridChainEndIndex
, pStream
);
353 else if(index1
< botRightIndex
)
355 //otherwise, we have rightChain->getVertex(index1)[1] > secondV
356 //let the next trim vertex be nextTrimVertex, (which should be strictly
357 //below the second grid line). Find the last grid line index2 which is STRICTLY ABOVE
359 //sample one trm edge region.
360 Real
*uppervert
, *lowervert
;
361 uppervert
= rightChain
->getVertex(index1
);
362 lowervert
= rightChain
->getVertex(index1
+1); //okay since index1<botRightindex
363 Int index2
= rightGridChainStartIndex
+1;
364 while(rightGridChain
->get_v_value(index2
) > lowervert
[1])
367 if(index2
> rightGridChainEndIndex
)
372 sampleRightSingleTrimEdgeRegion(uppervert
, lowervert
, rightGridChain
, rightGridChainStartIndex
+1, index2
, pStream
);
375 sampleRightStripRecF(rightChain
, index1
+1, botRightIndex
, rightGridChain
, index2
, rightGridChainEndIndex
, pStream
);
379 //the degenerate case of sampleRightOneGridStep
380 void sampleRightOneGridStepNoMiddle(vertexArray
* rightChain
,
383 gridBoundaryChain
* rightGridChain
,
384 Int rightGridChainStartIndex
,
387 /*since there is no middle, there is at most one point which is on the
388 *second grid line, there could be multiple points on the first (top)
391 rightGridChain
->rightEndFan(rightGridChainStartIndex
+1, pStream
);
392 monoTriangulation2(rightGridChain
->get_vertex(rightGridChainStartIndex
),
393 rightGridChain
->get_vertex(rightGridChainStartIndex
+1),
401 //sampling the right area in between two grid lines
403 void sampleRightOneGridStep(vertexArray
* rightChain
,
406 gridBoundaryChain
* rightGridChain
,
407 Int rightGridChainStartIndex
,
410 if(checkMiddle(rightChain
, beginRightIndex
, endRightIndex
,
411 rightGridChain
->get_v_value(rightGridChainStartIndex
),
412 rightGridChain
->get_v_value(rightGridChainStartIndex
+1))<0)
414 sampleRightOneGridStepNoMiddle(rightChain
, beginRightIndex
, endRightIndex
, rightGridChain
, rightGridChainStartIndex
, pStream
);
420 directedLine
* poly
= NULL
;
423 gridWrap
* grid
= rightGridChain
->getGrid();
428 Int innerInd
= rightGridChain
->getInnerIndex(rightGridChainStartIndex
+1);
429 Int upperInd
= rightGridChain
->getUlineIndex(rightGridChainStartIndex
);
430 Int lowerInd
= rightGridChain
->getUlineIndex(rightGridChainStartIndex
+1);
431 Real upperV
= rightGridChain
->get_v_value(rightGridChainStartIndex
);
432 Real lowerV
= rightGridChain
->get_v_value(rightGridChainStartIndex
+1);
435 vert1
[1]=vert2
[1]=upperV
;
440 vert1
[0]=grid
->get_u_value(i
);
441 vert2
[0]=grid
->get_u_value(i
-1);
442 sline
= new sampledLine(vert1
, vert2
);
443 dline
= new directedLine(INCREASING
, sline
);
450 //the vertical grid line segment
451 vert1
[0]=vert2
[0] = grid
->get_u_value(innerInd
);
454 sline
=new sampledLine(vert1
, vert2
);
455 dline
=new directedLine(INCREASING
, sline
);
461 //the lower grid line
462 vert1
[1]=vert2
[1]=lowerV
;
463 for(i
=innerInd
; i
<lowerInd
; i
++)
465 vert1
[0] = grid
->get_u_value(i
);
466 vert2
[0] = grid
->get_u_value(i
+1);
467 sline
= new sampledLine(vert1
, vert2
);
468 dline
= new directedLine(INCREASING
, sline
);
472 //the edge connecting lower grid to right chain
473 vert1
[0]=grid
->get_u_value(lowerInd
);
474 sline
= new sampledLine(vert1
, rightChain
->getVertex(endRightIndex
));
475 dline
= new directedLine(INCREASING
, sline
);
480 for(i
=endRightIndex
; i
>beginRightIndex
; i
--)
482 sline
= new sampledLine(rightChain
->getVertex(i
), rightChain
->getVertex(i
-1));
483 dline
= new directedLine(INCREASING
, sline
);
487 //the edge connecting right chain with upper grid
489 vert2
[0]=grid
->get_u_value(upperInd
);
490 sline
= new sampledLine(rightChain
->getVertex(beginRightIndex
), vert2
);
491 dline
= new directedLine(INCREASING
, sline
);
493 monoTriangulationOpt(poly
, pStream
);
495 poly
->deleteSinglePolygonWithSline();
500 //this following code cannot be reached, but leave it for debuggig purpose.
502 //find the maximal U-monotone chain of beginRightIndex, beginRightIndex+1,...
504 Real prevU
= rightChain
->getVertex(i
)[0];
505 for(i
=beginRightIndex
+1; i
<= endRightIndex
; i
++){
506 Real thisU
= rightChain
->getVertex(i
)[0];
512 //from beginRightIndex to i-1 is strictly U-monotne
513 //if(i-1==beginRightIndex and the vertex of rightchain is on the first
514 //gridline, then we should use 2 vertices on the right chain. Of we only
515 //use one (begin), we would output degenrate triangles.
516 if(i
-1 == beginRightIndex
&& rightChain
->getVertex(beginRightIndex
)[1] == rightGridChain
->get_v_value(rightGridChainStartIndex
))
519 Int j
= endRightIndex
-1;
520 if(rightGridChain
->getInnerIndex(rightGridChainStartIndex
+1) < rightGridChain
->getUlineIndex(rightGridChainStartIndex
+1))
522 j
= rightChain
->findDecreaseChainFromEnd(i
-1/*beginRightIndex*/, endRightIndex
);
523 Int temp
= endRightIndex
;
524 //now from j+1 to end is strictly U-monotone.
525 //if j+1 is on the last grid line, then we wat to skip to the vertex
526 //whcih is strictly above the second grid line. This vertex must exist
527 //since there is a middle vertex
528 if(j
+1 == endRightIndex
)
530 while(rightChain
->getVertex(j
+1)[1] == rightGridChain
->get_v_value(rightGridChainStartIndex
+1))
533 monoTriangulation2(rightChain
->getVertex(j
+1),
534 rightGridChain
->get_vertex(rightGridChainStartIndex
+1),
538 0, //a decrease chain
544 stripOfFanRight(rightChain
, temp
, j
+1, rightGridChain
->getGrid(),
545 rightGridChain
->getVlineIndex(rightGridChainStartIndex
+1),
546 rightGridChain
->getInnerIndex(rightGridChainStartIndex
+1),
547 rightGridChain
->getUlineIndex(rightGridChainStartIndex
+1),
549 0 //the grid line is below the trim line
555 stripOfFanRight(rightChain
, i
-1, beginRightIndex
, rightGridChain
->getGrid(),
556 rightGridChain
->getVlineIndex(rightGridChainStartIndex
),
557 rightGridChain
->getInnerIndex(rightGridChainStartIndex
+1),
558 rightGridChain
->getUlineIndex(rightGridChainStartIndex
),
560 1 //the grid line is above the trm lines
563 //monotone triangulate the remaining rightchain together with the
564 //two vertices on the two grid v-lines
566 vert
[0][0] = vert
[1][0] = rightGridChain
->getInner_u_value(rightGridChainStartIndex
+1);
567 vert
[0][1] = rightGridChain
->get_v_value(rightGridChainStartIndex
);
568 vert
[1][1] = rightGridChain
->get_v_value(rightGridChainStartIndex
+1);
570 monoTriangulation2(&vert
[0][0],
575 0, ///a decreae chain
581 void stripOfFanRight(vertexArray
* rightChain
,
589 Int gridLineUp
/*1 if the grid line is above the trim lines*/
592 assert(largeIndex
>= smallIndex
);
595 grid_v_value
= grid
->get_v_value(vlineIndex
);
597 Real2
* trimVerts
=(Real2
*) malloc(sizeof(Real2
)* (largeIndex
-smallIndex
+1));
601 Real2
* gridVerts
=(Real2
*) malloc(sizeof(Real2
)* (ulineLargeIndex
-ulineSmallIndex
+1));
605 if(! gridLineUp
) /*trim line is above grid line, so trim vertices are going right when index increases*/
606 for(k
=0, i
=smallIndex
; i
<=largeIndex
; i
++, k
++)
608 trimVerts
[k
][0] = rightChain
->getVertex(i
)[0];
609 trimVerts
[k
][1] = rightChain
->getVertex(i
)[1];
612 for(k
=0, i
=largeIndex
; i
>=smallIndex
; i
--, k
++)
614 trimVerts
[k
][0] = rightChain
->getVertex(i
)[0];
615 trimVerts
[k
][1] = rightChain
->getVertex(i
)[1];
618 for(k
=0, i
=ulineSmallIndex
; i
<= ulineLargeIndex
; i
++, k
++)
620 gridVerts
[k
][0] = grid
->get_u_value(i
);
621 gridVerts
[k
][1] = grid_v_value
;
626 ulineLargeIndex
-ulineSmallIndex
+1, gridVerts
,
627 largeIndex
-smallIndex
+1, trimVerts
,
630 triangulateXYMono(largeIndex
-smallIndex
+1, trimVerts
,
631 ulineLargeIndex
-ulineSmallIndex
+1, gridVerts
,