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$ $Revision: 1.1 $
37 ** $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libnurbs/nurbtess/sampleCompRight.cc,v 1.1 2004/02/02 16:39:14 navaraf Exp $
43 #include "glimports.h"
45 #include "sampleCompRight.h"
47 #define max(a,b) ((a>b)? a:b)
48 #define min(a,b) ((a>b)? b:a)
54 /*notice that we need leftChain because the
55 *corners could be on the leftChain.
57 void sampleCompRight(Real
* topVertex
, Real
* botVertex
,
58 vertexArray
* leftChain
,
59 Int leftStartIndex
, Int leftEndIndex
,
60 vertexArray
* rightChain
,
61 Int rightStartIndex
, Int rightEndIndex
,
62 gridBoundaryChain
* rightGridChain
,
63 Int gridIndex1
, Int gridIndex2
,
64 Int up_rightCornerWhere
,
65 Int up_rightCornerIndex
,
66 Int down_rightCornerWhere
,
67 Int down_rightCornerIndex
,
70 /*find out whether there is a trim vertex which is
71 *inbetween the top and bot grid lines or not.
75 Int gridMidIndex1
=0, gridMidIndex2
=0;
76 //midIndex1: array[i] <= v, array[i+1] > v
77 //midIndex2: array[i] >= v, array[i+1] < v
78 midIndex1
= rightChain
->findIndexBelowGen(rightGridChain
->get_v_value(gridIndex1
),
81 midIndex2
= -1; //initilization
82 if(midIndex1
<= rightEndIndex
&& gridIndex1
< gridIndex2
)
83 if(rightChain
->getVertex(midIndex1
)[1] >= rightGridChain
->get_v_value(gridIndex2
))
85 //midIndex2 must exist:
86 midIndex2
= rightChain
->findIndexAboveGen(rightGridChain
->get_v_value(gridIndex2
),
87 midIndex1
, //midIndex1<=midIndex2
89 //find gridMidIndex1 so that either it=gridIndex1 when the gridline is
90 // at the same height as trim vertex midIndex1, or it is the last one
91 //which is strictly above midIndex1.
93 Real temp
= rightChain
->getVertex(midIndex1
)[1];
94 if(rightGridChain
->get_v_value(gridIndex1
) == temp
)
95 gridMidIndex1
= gridIndex1
;
98 gridMidIndex1
= gridIndex1
;
99 while(rightGridChain
->get_v_value(gridMidIndex1
) > temp
)
103 }//end of find gridMindIndex1
104 //find gridMidIndex2 so that it is the (first one below or equal
105 //midIndex) last one above or equal midIndex2
107 Real temp
= rightChain
->getVertex(midIndex2
)[1];
108 for(gridMidIndex2
= gridMidIndex1
+1; gridMidIndex2
<= gridIndex2
; gridMidIndex2
++)
109 if(rightGridChain
->get_v_value(gridMidIndex2
) <= temp
)
112 assert(gridMidIndex2
<= gridIndex2
);
113 }//end of find gridMidIndex2
118 //to interprete the corner information
121 Int cornerRightStart
;
124 Int cornerLeftDownStart
;
125 if(up_rightCornerWhere
== 2) //right corner is on right chain
127 cornerTop
= rightChain
->getVertex(up_rightCornerIndex
);
128 cornerRightStart
= up_rightCornerIndex
+1;
129 cornerLeftUpEnd
= -1; //no left
131 else if(up_rightCornerWhere
== 1) //right corner is on top
133 cornerTop
= topVertex
;
134 cornerRightStart
= rightStartIndex
;
135 cornerLeftUpEnd
= -1; //no left
137 else //right corner is on left chain
139 cornerTop
= topVertex
;
140 cornerRightStart
= rightStartIndex
;
141 cornerLeftUpEnd
= up_rightCornerIndex
;
144 if(down_rightCornerWhere
== 2) //right corner is on right chan
146 cornerBot
= rightChain
->getVertex(down_rightCornerIndex
);
147 cornerRightEnd
= down_rightCornerIndex
-1;
148 cornerLeftDownStart
= leftEndIndex
+1; //no left
150 else if (down_rightCornerWhere
== 1) //right corner is at bot
152 cornerBot
= botVertex
;
153 cornerRightEnd
= rightEndIndex
;
154 cornerLeftDownStart
= leftEndIndex
+1; //no left
156 else //right corner is on the left chain
158 cornerBot
= botVertex
;
159 cornerRightEnd
= rightEndIndex
;
160 cornerLeftDownStart
= down_rightCornerIndex
;
164 if(midIndex2
>= 0) //there is a trm point between grid lines
167 sampleRightSingleTrimEdgeRegionGen(cornerTop
, rightChain
->getVertex(midIndex1
),
177 0, //no left down section,
181 sampleRightSingleTrimEdgeRegionGen(rightChain
->getVertex(midIndex2
),
190 0, //no left up section
196 sampleRightStripRecF(rightChain
,
207 sampleRightSingleTrimEdgeRegionGen(cornerTop
, cornerBot
,
223 void sampleRightSingleTrimEdgeRegionGen(Real topVertex
[2], Real botVertex
[2],
224 vertexArray
* rightChain
,
227 gridBoundaryChain
* gridChain
,
230 vertexArray
* leftChain
,
238 /*creat an array to store all the up and down secments of the left chain,
239 *and the right end grid points
241 *although vertex array is a dynamic array, but to gain efficiency,
242 *it is better to initiliza the exact array size
244 vertexArray
vArray(gridEndIndex
-gridBeginIndex
+1 +
245 max(0,leftUpEnd
- leftUpBegin
+1)+
246 max(0,leftDownEnd
- leftDownBegin
+1));
247 //append the vertices on the up section of the left chain
248 for(i
=leftUpBegin
; i
<= leftUpEnd
; i
++)
249 vArray
.appendVertex(leftChain
->getVertex(i
));
251 //append the vertices of the right extremal grid points,
252 //and at the same time, perform triangulation for the stair cases
253 vArray
.appendVertex(gridChain
->get_vertex(gridBeginIndex
));
255 for(k
=1, i
=gridBeginIndex
+1; i
<= gridEndIndex
; i
++, k
++)
257 vArray
.appendVertex(gridChain
->get_vertex(i
));
259 //output the fan of the grid points of the (i)th and (i-1)th grid line.
260 gridChain
->rightEndFan(i
, pStream
);
263 //append all the vertices on the down section of the left chain
264 for(i
=leftDownBegin
; i
<= leftDownEnd
; i
++)
265 vArray
.appendVertex(leftChain
->getVertex(i
));
266 monoTriangulationRecGen(topVertex
, botVertex
,
267 &vArray
, 0, vArray
.getNumElements()-1,
268 rightChain
, rightStart
, rightEnd
,
272 void sampleRightSingleTrimEdgeRegion(Real upperVert
[2], Real lowerVert
[2],
273 gridBoundaryChain
* gridChain
,
279 vertexArray
vArray(endIndex
-beginIndex
+1);
280 vArray
.appendVertex(gridChain
->get_vertex(beginIndex
));
281 for(k
=1, i
=beginIndex
+1; i
<= endIndex
; i
++, k
++)
283 vArray
.appendVertex(gridChain
->get_vertex(i
));
284 //output the fan of the grid points of the (i)_th and i-1th gridLine
285 gridChain
->rightEndFan(i
, pStream
);
287 monoTriangulation2(upperVert
, lowerVert
, &vArray
, 0, endIndex
-beginIndex
,
288 1, //increase chain (to the left)
293 /*the gridlines from rightGridChainStartIndex to
294 *rightGridChainEndIndex are assumed to form a
295 *connected componenet
296 *the trm vertex of topRightIndex is assumed to be below
297 *or equal the first gridLine, and the trm vertex of
298 *botRightIndex is assumed to be above or equal the last gridline
299 **there could be multipe trm vertices equal to the last gridline, but
300 **only one could be equal to top gridline. shape: ____| (recall that
301 **for left chain recF, we allow shape: |----
302 *if botRightIndex<topRightIndex, then no connected componenet exists, and
303 *no triangles are generated.
304 *Othewise, botRightIndex>= topRightIndex, there is at least one triangles to
307 void sampleRightStripRecF(vertexArray
* rightChain
,
310 gridBoundaryChain
* rightGridChain
,
311 Int rightGridChainStartIndex
,
312 Int rightGridChainEndIndex
,
317 //sstop conditionL: if topRightIndex > botRightIndex, then stop
318 if(topRightIndex
> botRightIndex
)
321 //if there is only one grid line, return
322 if(rightGridChainStartIndex
>= rightGridChainEndIndex
)
326 assert(rightChain
->getVertex(topRightIndex
)[1] <= rightGridChain
->get_v_value(rightGridChainStartIndex
) &&
327 rightChain
->getVertex(botRightIndex
)[1] >= rightGridChain
->get_v_value(rightGridChainEndIndex
));
329 //firstfind the first trim vertex which is strictly below the second top
331 Real secondGridChainV
= rightGridChain
->get_v_value(rightGridChainStartIndex
+1);
332 Int index1
= topRightIndex
;
333 while(rightChain
->getVertex(index1
)[1] >= secondGridChainV
){
335 if(index1
> botRightIndex
)
338 //now rightChain->getVertex(index1-1)[1] >= secondGridChainV and
339 //rightChain->getVertex(index1)[1] < secondGridChainV and
340 //we should include index1-1 to perform a gridStep
343 //now we have rightChain->getVertex(index1)[1] >= secondGridChainV, and
344 //rightChain->getVertex(index1+1)[1] < secondGridChainV
345 sampleRightOneGridStep(rightChain
, topRightIndex
, index1
, rightGridChain
, rightGridChainStartIndex
, pStream
);
347 //if rightChain->getVertex(index1)[1] ==secondGridChainV then we can
348 //recurvesively to the rest
349 if(rightChain
->getVertex(index1
)[1] == secondGridChainV
)
353 sampleRightStripRecF(rightChain
, index1
, botRightIndex
, rightGridChain
, rightGridChainStartIndex
+1, rightGridChainEndIndex
, pStream
);
355 else if(index1
< botRightIndex
)
357 //otherwise, we have rightChain->getVertex(index1)[1] > secondV
358 //let the next trim vertex be nextTrimVertex, (which should be strictly
359 //below the second grid line). Find the last grid line index2 which is STRICTLY ABOVE
361 //sample one trm edge region.
362 Real
*uppervert
, *lowervert
;
363 uppervert
= rightChain
->getVertex(index1
);
364 lowervert
= rightChain
->getVertex(index1
+1); //okay since index1<botRightindex
365 Int index2
= rightGridChainStartIndex
+1;
366 while(rightGridChain
->get_v_value(index2
) > lowervert
[1])
369 if(index2
> rightGridChainEndIndex
)
374 sampleRightSingleTrimEdgeRegion(uppervert
, lowervert
, rightGridChain
, rightGridChainStartIndex
+1, index2
, pStream
);
377 sampleRightStripRecF(rightChain
, index1
+1, botRightIndex
, rightGridChain
, index2
, rightGridChainEndIndex
, pStream
);
381 //the degenerate case of sampleRightOneGridStep
382 void sampleRightOneGridStepNoMiddle(vertexArray
* rightChain
,
385 gridBoundaryChain
* rightGridChain
,
386 Int rightGridChainStartIndex
,
389 /*since there is no middle, there is at most one point which is on the
390 *second grid line, there could be multiple points on the first (top)
393 rightGridChain
->rightEndFan(rightGridChainStartIndex
+1, pStream
);
394 monoTriangulation2(rightGridChain
->get_vertex(rightGridChainStartIndex
),
395 rightGridChain
->get_vertex(rightGridChainStartIndex
+1),
403 //sampling the right area in between two grid lines
405 void sampleRightOneGridStep(vertexArray
* rightChain
,
408 gridBoundaryChain
* rightGridChain
,
409 Int rightGridChainStartIndex
,
412 if(checkMiddle(rightChain
, beginRightIndex
, endRightIndex
,
413 rightGridChain
->get_v_value(rightGridChainStartIndex
),
414 rightGridChain
->get_v_value(rightGridChainStartIndex
+1))<0)
416 sampleRightOneGridStepNoMiddle(rightChain
, beginRightIndex
, endRightIndex
, rightGridChain
, rightGridChainStartIndex
, pStream
);
422 directedLine
* poly
= NULL
;
425 gridWrap
* grid
= rightGridChain
->getGrid();
430 Int innerInd
= rightGridChain
->getInnerIndex(rightGridChainStartIndex
+1);
431 Int upperInd
= rightGridChain
->getUlineIndex(rightGridChainStartIndex
);
432 Int lowerInd
= rightGridChain
->getUlineIndex(rightGridChainStartIndex
+1);
433 Real upperV
= rightGridChain
->get_v_value(rightGridChainStartIndex
);
434 Real lowerV
= rightGridChain
->get_v_value(rightGridChainStartIndex
+1);
437 vert1
[1]=vert2
[1]=upperV
;
442 vert1
[0]=grid
->get_u_value(i
);
443 vert2
[0]=grid
->get_u_value(i
-1);
444 sline
= new sampledLine(vert1
, vert2
);
445 dline
= new directedLine(INCREASING
, sline
);
452 //the vertical grid line segment
453 vert1
[0]=vert2
[0] = grid
->get_u_value(innerInd
);
456 sline
=new sampledLine(vert1
, vert2
);
457 dline
=new directedLine(INCREASING
, sline
);
463 //the lower grid line
464 vert1
[1]=vert2
[1]=lowerV
;
465 for(i
=innerInd
; i
<lowerInd
; i
++)
467 vert1
[0] = grid
->get_u_value(i
);
468 vert2
[0] = grid
->get_u_value(i
+1);
469 sline
= new sampledLine(vert1
, vert2
);
470 dline
= new directedLine(INCREASING
, sline
);
474 //the edge connecting lower grid to right chain
475 vert1
[0]=grid
->get_u_value(lowerInd
);
476 sline
= new sampledLine(vert1
, rightChain
->getVertex(endRightIndex
));
477 dline
= new directedLine(INCREASING
, sline
);
482 for(i
=endRightIndex
; i
>beginRightIndex
; i
--)
484 sline
= new sampledLine(rightChain
->getVertex(i
), rightChain
->getVertex(i
-1));
485 dline
= new directedLine(INCREASING
, sline
);
489 //the edge connecting right chain with upper grid
491 vert2
[0]=grid
->get_u_value(upperInd
);
492 sline
= new sampledLine(rightChain
->getVertex(beginRightIndex
), vert2
);
493 dline
= new directedLine(INCREASING
, sline
);
495 monoTriangulationOpt(poly
, pStream
);
497 poly
->deleteSinglePolygonWithSline();
502 //this following code cannot be reached, but leave it for debuggig purpose.
504 //find the maximal U-monotone chain of beginRightIndex, beginRightIndex+1,...
506 Real prevU
= rightChain
->getVertex(i
)[0];
507 for(i
=beginRightIndex
+1; i
<= endRightIndex
; i
++){
508 Real thisU
= rightChain
->getVertex(i
)[0];
514 //from beginRightIndex to i-1 is strictly U-monotne
515 //if(i-1==beginRightIndex and the vertex of rightchain is on the first
516 //gridline, then we should use 2 vertices on the right chain. Of we only
517 //use one (begin), we would output degenrate triangles.
518 if(i
-1 == beginRightIndex
&& rightChain
->getVertex(beginRightIndex
)[1] == rightGridChain
->get_v_value(rightGridChainStartIndex
))
521 Int j
= endRightIndex
-1;
522 if(rightGridChain
->getInnerIndex(rightGridChainStartIndex
+1) < rightGridChain
->getUlineIndex(rightGridChainStartIndex
+1))
524 j
= rightChain
->findDecreaseChainFromEnd(i
-1/*beginRightIndex*/, endRightIndex
);
525 Int temp
= endRightIndex
;
526 //now from j+1 to end is strictly U-monotone.
527 //if j+1 is on the last grid line, then we wat to skip to the vertex
528 //whcih is strictly above the second grid line. This vertex must exist
529 //since there is a middle vertex
530 if(j
+1 == endRightIndex
)
532 while(rightChain
->getVertex(j
+1)[1] == rightGridChain
->get_v_value(rightGridChainStartIndex
+1))
535 monoTriangulation2(rightChain
->getVertex(j
+1),
536 rightGridChain
->get_vertex(rightGridChainStartIndex
+1),
540 0, //a decrease chain
546 stripOfFanRight(rightChain
, temp
, j
+1, rightGridChain
->getGrid(),
547 rightGridChain
->getVlineIndex(rightGridChainStartIndex
+1),
548 rightGridChain
->getInnerIndex(rightGridChainStartIndex
+1),
549 rightGridChain
->getUlineIndex(rightGridChainStartIndex
+1),
551 0 //the grid line is below the trim line
557 stripOfFanRight(rightChain
, i
-1, beginRightIndex
, rightGridChain
->getGrid(),
558 rightGridChain
->getVlineIndex(rightGridChainStartIndex
),
559 rightGridChain
->getInnerIndex(rightGridChainStartIndex
+1),
560 rightGridChain
->getUlineIndex(rightGridChainStartIndex
),
562 1 //the grid line is above the trm lines
565 //monotone triangulate the remaining rightchain together with the
566 //two vertices on the two grid v-lines
568 vert
[0][0] = vert
[1][0] = rightGridChain
->getInner_u_value(rightGridChainStartIndex
+1);
569 vert
[0][1] = rightGridChain
->get_v_value(rightGridChainStartIndex
);
570 vert
[1][1] = rightGridChain
->get_v_value(rightGridChainStartIndex
+1);
572 monoTriangulation2(&vert
[0][0],
577 0, ///a decreae chain
583 void stripOfFanRight(vertexArray
* rightChain
,
591 Int gridLineUp
/*1 if the grid line is above the trim lines*/
594 assert(largeIndex
>= smallIndex
);
597 grid_v_value
= grid
->get_v_value(vlineIndex
);
599 Real2
* trimVerts
=(Real2
*) malloc(sizeof(Real2
)* (largeIndex
-smallIndex
+1));
603 Real2
* gridVerts
=(Real2
*) malloc(sizeof(Real2
)* (ulineLargeIndex
-ulineSmallIndex
+1));
607 if(! gridLineUp
) /*trim line is above grid line, so trim vertices are going right when index increases*/
608 for(k
=0, i
=smallIndex
; i
<=largeIndex
; i
++, k
++)
610 trimVerts
[k
][0] = rightChain
->getVertex(i
)[0];
611 trimVerts
[k
][1] = rightChain
->getVertex(i
)[1];
614 for(k
=0, i
=largeIndex
; i
>=smallIndex
; i
--, k
++)
616 trimVerts
[k
][0] = rightChain
->getVertex(i
)[0];
617 trimVerts
[k
][1] = rightChain
->getVertex(i
)[1];
620 for(k
=0, i
=ulineSmallIndex
; i
<= ulineLargeIndex
; i
++, k
++)
622 gridVerts
[k
][0] = grid
->get_u_value(i
);
623 gridVerts
[k
][1] = grid_v_value
;
628 ulineLargeIndex
-ulineSmallIndex
+1, gridVerts
,
629 largeIndex
-smallIndex
+1, trimVerts
,
632 triangulateXYMono(largeIndex
-smallIndex
+1, trimVerts
,
633 ulineLargeIndex
-ulineSmallIndex
+1, gridVerts
,