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: 2005/10/28 13:09:23 $ $Revision: 1.5 $
37 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/sampleMonoPoly.cc,v 1.5 2005/10/28 13:09:23 brianp Exp $
46 #define max(a,b) ((a>b)? a:b)
49 #define min(a,b) ((a>b)? b:a)
54 #include "glimports.h"
56 #include "sampleMonoPoly.h"
57 #include "sampleComp.h"
59 #include "partitionX.h"
66 //#define SHORTEN_GRID_LINE
67 //see work/newtess/internal/test/problems
70 /*split a polygon so that each vertex correcpond to one edge
71 *the head of the first edge of the returned plygon must be the head of the first
72 *edge of the origianl polygon. This is crucial for the code in sampleMonoPoly function
74 directedLine
* polygonConvert(directedLine
* polygon
)
79 sline
= new sampledLine(2);
80 sline
->setPoint(0, polygon
->getVertex(0));
81 sline
->setPoint(1, polygon
->getVertex(1));
82 ret
=new directedLine(INCREASING
, sline
);
83 for(i
=1; i
<= polygon
->get_npoints()-2; i
++)
85 sline
= new sampledLine(2);
86 sline
->setPoint(0, polygon
->getVertex(i
));
87 sline
->setPoint(1, polygon
->getVertex(i
+1));
88 ret
->insert(new directedLine(INCREASING
, sline
));
91 for(directedLine
*temp
= polygon
->getNext(); temp
!= polygon
; temp
= temp
->getNext())
93 for(i
=0; i
<= temp
->get_npoints()-2; i
++)
95 sline
= new sampledLine(2);
96 sline
->setPoint(0, temp
->getVertex(i
));
97 sline
->setPoint(1, temp
->getVertex(i
+1));
98 ret
->insert(new directedLine(INCREASING
, sline
));
104 void triangulateConvexPolyVertical(directedLine
* topV
, directedLine
* botV
, primStream
*pStream
)
113 for(tempV
= topV
; tempV
!= botV
; tempV
= tempV
->getNext())
115 n_leftVerts
+= tempV
->get_npoints();
118 for(tempV
= botV
; tempV
!= topV
; tempV
= tempV
->getNext())
120 n_rightVerts
+= tempV
->get_npoints();
123 Real2
* temp_leftVerts
= (Real2
*) malloc(sizeof(Real2
) * n_leftVerts
);
124 assert(temp_leftVerts
);
125 Real2
* temp_rightVerts
= (Real2
*) malloc(sizeof(Real2
) * n_rightVerts
);
126 assert(temp_rightVerts
);
128 leftVerts
= (Real
**) malloc(sizeof(Real2
*) * n_leftVerts
);
130 rightVerts
= (Real
**) malloc(sizeof(Real2
*) * n_rightVerts
);
132 for(i
=0; i
<n_leftVerts
; i
++)
133 leftVerts
[i
] = temp_leftVerts
[i
];
134 for(i
=0; i
<n_rightVerts
; i
++)
135 rightVerts
[i
] = temp_rightVerts
[i
];
138 for(tempV
= topV
; tempV
!= botV
; tempV
= tempV
->getNext())
140 for(j
=1; j
<tempV
->get_npoints(); j
++)
142 leftVerts
[i
][0] = tempV
->getVertex(j
)[0];
143 leftVerts
[i
][1] = tempV
->getVertex(j
)[1];
149 for(tempV
= topV
->getPrev(); tempV
!= botV
->getPrev(); tempV
= tempV
->getPrev())
151 for(j
=tempV
->get_npoints()-1; j
>=1; j
--)
153 rightVerts
[i
][0] = tempV
->getVertex(j
)[0];
154 rightVerts
[i
][1] = tempV
->getVertex(j
)[1];
159 triangulateXYMonoTB(n_leftVerts
, leftVerts
, n_rightVerts
, rightVerts
, pStream
);
162 free(temp_leftVerts
);
163 free(temp_rightVerts
);
166 void triangulateConvexPolyHoriz(directedLine
* leftV
, directedLine
* rightV
, primStream
*pStream
)
175 for(tempV
= leftV
; tempV
!= rightV
; tempV
= tempV
->getNext())
177 n_lowerVerts
+= tempV
->get_npoints();
180 for(tempV
= rightV
; tempV
!= leftV
; tempV
= tempV
->getNext())
182 n_upperVerts
+= tempV
->get_npoints();
184 lowerVerts
= (Real2
*) malloc(sizeof(Real2
) * n_lowerVerts
);
185 assert(n_lowerVerts
);
186 upperVerts
= (Real2
*) malloc(sizeof(Real2
) * n_upperVerts
);
187 assert(n_upperVerts
);
189 for(tempV
= leftV
; tempV
!= rightV
; tempV
= tempV
->getNext())
191 for(j
=0; j
<tempV
->get_npoints(); j
++)
193 lowerVerts
[i
][0] = tempV
->getVertex(j
)[0];
194 lowerVerts
[i
][1] = tempV
->getVertex(j
)[1];
199 for(tempV
= leftV
->getPrev(); tempV
!= rightV
->getPrev(); tempV
= tempV
->getPrev())
201 for(j
=tempV
->get_npoints()-1; j
>=0; j
--)
203 upperVerts
[i
][0] = tempV
->getVertex(j
)[0];
204 upperVerts
[i
][1] = tempV
->getVertex(j
)[1];
208 triangulateXYMono(n_upperVerts
, upperVerts
, n_lowerVerts
, lowerVerts
, pStream
);
212 void triangulateConvexPoly(directedLine
* polygon
, Int ulinear
, Int vlinear
, primStream
* pStream
)
214 /*find left, right, top , bot
220 directedLine
* rightV
;
221 topV
= botV
= polygon
;
223 for(tempV
= polygon
->getNext(); tempV
!= polygon
; tempV
= tempV
->getNext())
225 if(compV2InY(topV
->head(), tempV
->head())<0) {
229 if(compV2InY(botV
->head(), tempV
->head())>0) {
235 for(tempV
= topV
; tempV
!= botV
; tempV
= tempV
->getNext())
237 if(tempV
->tail()[0] >= tempV
->head()[0])
242 for(tempV
= botV
; tempV
!= topV
; tempV
= tempV
->getNext())
244 if(tempV
->tail()[0] <= tempV
->head()[0])
250 triangulateConvexPolyHoriz( leftV
, rightV
, pStream
);
254 triangulateConvexPolyVertical(topV
, botV
, pStream
);
258 if(DBG_is_U_direction(polygon
))
260 triangulateConvexPolyHoriz( leftV
, rightV
, pStream
);
263 triangulateConvexPolyVertical(topV
, botV
, pStream
);
267 /*for debug purpose*/
269 Real
* topV
, Real
* botV
,
270 vertexArray
* leftChain
,
271 vertexArray
* rightChain
,
272 gridBoundaryChain
* leftGridChain
,
273 gridBoundaryChain
* rightGridChain
,
278 Int rightCornerWhere
,
279 Int rightCornerIndex
,
280 Int bot_leftCornerWhere
,
281 Int bot_leftCornerIndex
,
282 Int bot_rightCornerWhere
,
283 Int bot_rightCornerIndex
)
287 Real
* bot_leftCornerV
;
288 Real
* bot_rightCornerV
;
290 if(leftCornerWhere
== 1)
292 else if(leftCornerWhere
== 0)
293 leftCornerV
= leftChain
->getVertex(leftCornerIndex
);
295 leftCornerV
= rightChain
->getVertex(leftCornerIndex
);
297 if(rightCornerWhere
== 1)
299 else if(rightCornerWhere
== 0)
300 rightCornerV
= leftChain
->getVertex(rightCornerIndex
);
302 rightCornerV
= rightChain
->getVertex(rightCornerIndex
);
304 if(bot_leftCornerWhere
== 1)
305 bot_leftCornerV
= botV
;
306 else if(bot_leftCornerWhere
== 0)
307 bot_leftCornerV
= leftChain
->getVertex(bot_leftCornerIndex
);
309 bot_leftCornerV
= rightChain
->getVertex(bot_leftCornerIndex
);
311 if(bot_rightCornerWhere
== 1)
312 bot_rightCornerV
= botV
;
313 else if(bot_rightCornerWhere
== 0)
314 bot_rightCornerV
= leftChain
->getVertex(bot_rightCornerIndex
);
316 bot_rightCornerV
= rightChain
->getVertex(bot_rightCornerIndex
);
318 Real topGridV
= leftGridChain
->get_v_value(gridIndex1
);
319 Real topGridU1
= leftGridChain
->get_u_value(gridIndex1
);
320 Real topGridU2
= rightGridChain
->get_u_value(gridIndex1
);
321 Real botGridV
= leftGridChain
->get_v_value(gridIndex2
);
322 Real botGridU1
= leftGridChain
->get_u_value(gridIndex2
);
323 Real botGridU2
= rightGridChain
->get_u_value(gridIndex2
);
325 glBegin(GL_LINE_STRIP
);
326 glVertex2fv(leftCornerV
);
327 glVertex2f(topGridU1
, topGridV
);
330 glBegin(GL_LINE_STRIP
);
331 glVertex2fv(rightCornerV
);
332 glVertex2f(topGridU2
, topGridV
);
335 glBegin(GL_LINE_STRIP
);
336 glVertex2fv(bot_leftCornerV
);
337 glVertex2f(botGridU1
, botGridV
);
340 glBegin(GL_LINE_STRIP
);
341 glVertex2fv(bot_rightCornerV
);
342 glVertex2f(botGridU2
, botGridV
);
348 void toVertexArrays(directedLine
* topV
, directedLine
* botV
, vertexArray
& leftChain
, vertexArray
& rightChain
)
352 for(i
=1; i
<=topV
->get_npoints()-2; i
++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
353 leftChain
.appendVertex(topV
->getVertex(i
));
355 for(tempV
= topV
->getNext(); tempV
!= botV
; tempV
= tempV
->getNext())
357 for(i
=0; i
<=tempV
->get_npoints()-2; i
++){
358 leftChain
.appendVertex(tempV
->getVertex(i
));
362 for(tempV
= topV
->getPrev(); tempV
!= botV
; tempV
= tempV
->getPrev())
364 for(i
=tempV
->get_npoints()-2; i
>=0; i
--){
365 rightChain
.appendVertex(tempV
->getVertex(i
));
368 for(i
=botV
->get_npoints()-2; i
>=1; i
--){
369 rightChain
.appendVertex(tempV
->getVertex(i
));
374 void findTopAndBot(directedLine
* polygon
, directedLine
*& topV
, directedLine
*& botV
)
378 topV
= botV
= polygon
;
379 for(tempV
= polygon
->getNext(); tempV
!= polygon
; tempV
= tempV
->getNext())
381 if(compV2InY(topV
->head(), tempV
->head())<0) {
384 if(compV2InY(botV
->head(), tempV
->head())>0) {
390 void findGridChains(directedLine
* topV
, directedLine
* botV
,
392 gridBoundaryChain
*& leftGridChain
,
393 gridBoundaryChain
*& rightGridChain
)
395 /*find the first(top) and the last (bottom) grid line which intersect the
398 Int firstGridIndex
; /*the index in the grid*/
401 firstGridIndex
= (Int
) ((topV
->head()[1] - grid
->get_v_min()) / (grid
->get_v_max() - grid
->get_v_min()) * (grid
->get_n_vlines()-1));
403 if(botV
->head()[1] < grid
->get_v_min())
406 lastGridIndex
= (Int
) ((botV
->head()[1] - grid
->get_v_min()) / (grid
->get_v_max() - grid
->get_v_min()) * (grid
->get_n_vlines()-1)) + 1;
408 /*find the interval inside the polygon for each gridline*/
409 Int
*leftGridIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
410 assert(leftGridIndices
);
411 Int
*rightGridIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
412 assert(rightGridIndices
);
413 Int
*leftGridInnerIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
414 assert(leftGridInnerIndices
);
415 Int
*rightGridInnerIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
416 assert(rightGridInnerIndices
);
418 findLeftGridIndices(topV
, firstGridIndex
, lastGridIndex
, grid
, leftGridIndices
, leftGridInnerIndices
);
420 findRightGridIndices(topV
, firstGridIndex
, lastGridIndex
, grid
, rightGridIndices
, rightGridInnerIndices
);
422 leftGridChain
= new gridBoundaryChain(grid
, firstGridIndex
, firstGridIndex
-lastGridIndex
+1, leftGridIndices
, leftGridInnerIndices
);
424 rightGridChain
= new gridBoundaryChain(grid
, firstGridIndex
, firstGridIndex
-lastGridIndex
+1, rightGridIndices
, rightGridInnerIndices
);
426 free(leftGridIndices
);
427 free(rightGridIndices
);
428 free(leftGridInnerIndices
);
429 free(rightGridInnerIndices
);
432 void findDownCorners(Real
*botVertex
,
433 vertexArray
*leftChain
, Int leftChainStartIndex
, Int leftChainEndIndex
,
434 vertexArray
*rightChain
, Int rightChainStartIndex
, Int rightChainEndIndex
,
438 Int
& ret_leftCornerWhere
, /*0: left chain, 1: topvertex, 2: rightchain*/
439 Int
& ret_leftCornerIndex
, /*useful when ret_leftCornerWhere == 0 or 2*/
440 Int
& ret_rightCornerWhere
, /*0: left chain, 1: topvertex, 2: rightchain*/
441 Int
& ret_rightCornerIndex
/*useful when ret_leftCornerWhere == 0 or 2*/
445 printf("*************enter find donw corner\n");
446 printf("finddownCorner: v=%f, uleft=%f, uright=%f\n", v
, uleft
, uright
);
447 printf("(%i,%i,%i,%i)\n", leftChainStartIndex
, leftChainEndIndex
,rightChainStartIndex
, rightChainEndIndex
);
448 printf("left chain is\n");
450 printf("right chain is\n");
454 assert(v
> botVertex
[1]);
455 Real leftGridPoint
[2];
456 leftGridPoint
[0] = uleft
;
457 leftGridPoint
[1] = v
;
458 Real rightGridPoint
[2];
459 rightGridPoint
[0] = uright
;
460 rightGridPoint
[1] = v
;
465 index1
= leftChain
->findIndexBelowGen(v
, leftChainStartIndex
, leftChainEndIndex
);
466 index2
= rightChain
->findIndexBelowGen(v
, rightChainStartIndex
, rightChainEndIndex
);
468 if(index2
<= rightChainEndIndex
) //index2 was found above
469 index2
= rightChain
->skipEqualityFromStart(v
, index2
, rightChainEndIndex
);
471 if(index1
>leftChainEndIndex
&& index2
> rightChainEndIndex
) /*no point below v on left chain or right chain*/
474 /*the botVertex is the only vertex below v*/
475 ret_leftCornerWhere
= 1;
476 ret_rightCornerWhere
= 1;
478 else if(index1
>leftChainEndIndex
) /*index2 <= rightChainEndIndex*/
481 ret_rightCornerWhere
= 2; /*on right chain*/
482 ret_rightCornerIndex
= index2
;
485 Real tempMin
= rightChain
->getVertex(index2
)[0];
487 for(i
=index2
+1; i
<= rightChainEndIndex
; i
++)
488 if(rightChain
->getVertex(i
)[0] < tempMin
)
491 tempMin
= rightChain
->getVertex(i
)[0];
495 //we consider whether we can use botVertex as left corner. First check
496 //if (leftGirdPoint, botVertex) interesects right chian or not.
497 if(DBG_intersectChain(rightChain
, rightChainStartIndex
,rightChainEndIndex
,
498 leftGridPoint
, botVertex
))
500 ret_leftCornerWhere
= 2;//right
501 ret_leftCornerIndex
= index2
; //should use tempI???
503 else if(botVertex
[0] < tempMin
)
504 ret_leftCornerWhere
= 1; //bot
507 ret_leftCornerWhere
= 2; //right
508 ret_leftCornerIndex
= tempI
;
511 else if(index2
> rightChainEndIndex
) /*index1<=leftChainEndIndex*/
513 ret_leftCornerWhere
= 0; /*left chain*/
514 ret_leftCornerIndex
= index1
;
516 /*find the vertex on the left chain with the maximum u,
517 *either this vertex or the botvertex can be used as the right corner
521 //skip those points which are equal to v. (avoid degeneratcy)
522 for(tempI
= index1
; tempI
<= leftChainEndIndex
; tempI
++)
523 if(leftChain
->getVertex(tempI
)[1] < v
)
525 if(tempI
> leftChainEndIndex
)
526 ret_rightCornerWhere
= 1;
529 Real tempMax
= leftChain
->getVertex(tempI
)[0];
530 for(i
=tempI
; i
<= leftChainEndIndex
; i
++)
531 if(leftChain
->getVertex(i
)[0] > tempMax
)
534 tempMax
= leftChain
->getVertex(i
)[0];
539 //we consider whether we can use botVertex as a corner. So first we check
540 //whether (rightGridPoint, botVertex) interescts the left chain or not.
541 if(DBG_intersectChain(leftChain
, leftChainStartIndex
,leftChainEndIndex
,
542 rightGridPoint
, botVertex
))
544 ret_rightCornerWhere
= 0;
545 ret_rightCornerIndex
= index1
; //should use tempI???
547 else if(botVertex
[0] > tempMax
)
550 ret_rightCornerWhere
= 1;
554 ret_rightCornerWhere
= 0;
555 ret_rightCornerIndex
= tempI
;
560 else /*index1<=leftChainEndIndex and index2 <=rightChainEndIndex*/
562 if(leftChain
->getVertex(index1
)[1] >= rightChain
->getVertex(index2
)[1]) /*left point above right point*/
564 ret_leftCornerWhere
= 0; /*on left chain*/
565 ret_leftCornerIndex
= index1
;
571 tempMax
= leftChain
->getVertex(index1
)[0];
573 /*find the maximum u for all the points on the left above the right point index2*/
574 for(i
=index1
+1; i
<= leftChainEndIndex
; i
++)
576 if(leftChain
->getVertex(i
)[1] < rightChain
->getVertex(index2
)[1])
579 if(leftChain
->getVertex(i
)[0]>tempMax
)
582 tempMax
= leftChain
->getVertex(i
)[0];
585 //we consider if we can use rightChain(index2) as right corner
586 //we check if (rightChain(index2), rightGidPoint) intersecs left chain or not.
587 if(DBG_intersectChain(leftChain
, leftChainStartIndex
,leftChainEndIndex
, rightGridPoint
, rightChain
->getVertex(index2
)))
589 ret_rightCornerWhere
= 0;
590 ret_rightCornerIndex
= index1
; //should use tempI???
592 else if(tempMax
>= rightChain
->getVertex(index2
)[0] ||
597 ret_rightCornerWhere
= 0; /*on left Chain*/
598 ret_rightCornerIndex
= tempI
;
602 ret_rightCornerWhere
= 2; /*on right chain*/
603 ret_rightCornerIndex
= index2
;
606 else /*left below right*/
608 ret_rightCornerWhere
= 2; /*on the right*/
609 ret_rightCornerIndex
= index2
;
615 tempMin
= rightChain
->getVertex(index2
)[0];
617 /*find the minimum u for all the points on the right above the left poitn index1*/
618 for(i
=index2
+1; i
<= rightChainEndIndex
; i
++)
620 if( rightChain
->getVertex(i
)[1] < leftChain
->getVertex(index1
)[1])
622 if(rightChain
->getVertex(i
)[0] < tempMin
)
625 tempMin
= rightChain
->getVertex(i
)[0];
629 //we consider if we can use leftchain(index1) as left corner.
630 //we check if (leftChain(index1) intersects right chian or not
631 if(DBG_intersectChain(rightChain
, rightChainStartIndex
, rightChainEndIndex
, leftGridPoint
, leftChain
->getVertex(index1
)))
633 ret_leftCornerWhere
= 2;
634 ret_leftCornerIndex
= index2
; //should use tempI???
636 else if(tempMin
<= leftChain
->getVertex(index1
)[0] ||
639 ret_leftCornerWhere
= 2; /* on right chain*/
640 ret_leftCornerIndex
= tempI
;
644 ret_leftCornerWhere
= 0; /*on left chain*/
645 ret_leftCornerIndex
= index1
;
653 void findUpCorners(Real
*topVertex
,
654 vertexArray
*leftChain
, Int leftChainStartIndex
, Int leftChainEndIndex
,
655 vertexArray
*rightChain
, Int rightChainStartIndex
, Int rightChainEndIndex
,
659 Int
& ret_leftCornerWhere
, /*0: left chain, 1: topvertex, 2: rightchain*/
660 Int
& ret_leftCornerIndex
, /*useful when ret_leftCornerWhere == 0 or 2*/
661 Int
& ret_rightCornerWhere
, /*0: left chain, 1: topvertex, 2: rightchain*/
662 Int
& ret_rightCornerIndex
/*useful when ret_leftCornerWhere == 0 or 2*/
666 printf("***********enter findUpCorners\n");
669 assert(v
< topVertex
[1]);
670 Real leftGridPoint
[2];
671 leftGridPoint
[0] = uleft
;
672 leftGridPoint
[1] = v
;
673 Real rightGridPoint
[2];
674 rightGridPoint
[0] = uright
;
675 rightGridPoint
[1] = v
;
680 index1
= leftChain
->findIndexFirstAboveEqualGen(v
, leftChainStartIndex
, leftChainEndIndex
);
683 index2
= rightChain
->findIndexFirstAboveEqualGen(v
, rightChainStartIndex
, rightChainEndIndex
);
685 if(index2
>= leftChainStartIndex
) //index2 was found above
686 index2
= rightChain
->skipEqualityFromStart(v
, index2
, rightChainEndIndex
);
688 if(index1
<leftChainStartIndex
&& index2
<rightChainStartIndex
) /*no point above v on left chain or right chain*/
690 /*the topVertex is the only vertex above v*/
691 ret_leftCornerWhere
= 1;
692 ret_rightCornerWhere
= 1;
694 else if(index1
<leftChainStartIndex
) /*index2 >= rightChainStartIndex*/
696 ret_rightCornerWhere
= 2; /*on right chain*/
697 ret_rightCornerIndex
= index2
;
699 //find the minimum u on right top, either that, or top, or right[index2] is the left corner
700 Real tempMin
= rightChain
->getVertex(index2
)[0];
702 for(i
=index2
-1; i
>=rightChainStartIndex
; i
--)
703 if(rightChain
->getVertex(i
)[0] < tempMin
)
705 tempMin
= rightChain
->getVertex(i
)[0];
708 //chech whether (leftGridPoint, top) intersects rightchai,
709 //if yes, use right corner as left corner
710 //if not, use top or right[tempI] as left corner
711 if(DBG_intersectChain(rightChain
, rightChainStartIndex
, rightChainEndIndex
,
712 leftGridPoint
, topVertex
))
714 ret_leftCornerWhere
= 2; //rightChain
715 ret_leftCornerIndex
= index2
;
717 else if(topVertex
[0] < tempMin
)
718 ret_leftCornerWhere
= 1; /*topvertex*/
721 ret_leftCornerWhere
= 2; //right chain
722 ret_leftCornerIndex
= tempI
;
726 else if(index2
< rightChainStartIndex
) /*index1>=leftChainStartIndex*/
728 ret_leftCornerWhere
= 0; /*left chain*/
729 ret_leftCornerIndex
= index1
;
731 //find the maximum u on the left top section. either that or topvertex, or left[index1] is the right corner
732 Real tempMax
= leftChain
->getVertex(index1
)[0];
735 for(i
=index1
-1; i
>=leftChainStartIndex
; i
--){
737 if(leftChain
->getVertex(i
)[0] > tempMax
)
740 tempMax
= leftChain
->getVertex(i
)[0];
744 //check whether (rightGridPoint, top) intersects leftChain or not
745 //if yes, we use leftCorner as the right corner
746 //if not, we use either top or left[tempI] as the right corner
747 if(DBG_intersectChain(leftChain
, leftChainStartIndex
,leftChainEndIndex
,
748 rightGridPoint
, topVertex
))
750 ret_rightCornerWhere
= 0; //left chan
751 ret_rightCornerIndex
= index1
;
753 else if(topVertex
[0] > tempMax
)
754 ret_rightCornerWhere
= 1;//topVertex
757 ret_rightCornerWhere
= 0;//left chain
758 ret_rightCornerIndex
= tempI
;
761 else /*index1>=leftChainStartIndex and index2 >=rightChainStartIndex*/
763 if(leftChain
->getVertex(index1
)[1] <= rightChain
->getVertex(index2
)[1]) /*left point below right point*/
765 ret_leftCornerWhere
= 0; /*on left chain*/
766 ret_leftCornerIndex
= index1
;
772 tempMax
= leftChain
->getVertex(index1
)[0];
774 /*find the maximum u for all the points on the left below the right point index2*/
775 for(i
=index1
-1; i
>= leftChainStartIndex
; i
--)
777 if(leftChain
->getVertex(i
)[1] > rightChain
->getVertex(index2
)[1])
780 if(leftChain
->getVertex(i
)[0]>tempMax
)
783 tempMax
= leftChain
->getVertex(i
)[0];
786 //chek whether (rightChain(index2), rightGridPoint) intersects leftchian or not
787 if(DBG_intersectChain(leftChain
, leftChainStartIndex
, leftChainEndIndex
, rightGridPoint
, rightChain
->getVertex(index2
)))
789 ret_rightCornerWhere
= 0;
790 ret_rightCornerIndex
= index1
;
792 else if(tempMax
>= rightChain
->getVertex(index2
)[0] ||
795 ret_rightCornerWhere
= 0; /*on left Chain*/
796 ret_rightCornerIndex
= tempI
;
800 ret_rightCornerWhere
= 2; /*on right chain*/
801 ret_rightCornerIndex
= index2
;
804 else /*left above right*/
806 ret_rightCornerWhere
= 2; /*on the right*/
807 ret_rightCornerIndex
= index2
;
813 tempMin
= rightChain
->getVertex(index2
)[0];
815 /*find the minimum u for all the points on the right below the left poitn index1*/
816 for(i
=index2
-1; i
>= rightChainStartIndex
; i
--)
818 if( rightChain
->getVertex(i
)[1] > leftChain
->getVertex(index1
)[1])
820 if(rightChain
->getVertex(i
)[0] < tempMin
)
823 tempMin
= rightChain
->getVertex(i
)[0];
826 //check whether (leftGRidPoint,left(index1)) interesect right chain
827 if(DBG_intersectChain(rightChain
, rightChainStartIndex
, rightChainEndIndex
,
828 leftGridPoint
, leftChain
->getVertex(index1
)))
830 ret_leftCornerWhere
= 2; //right
831 ret_leftCornerIndex
= index2
;
833 else if(tempMin
<= leftChain
->getVertex(index1
)[0] ||
836 ret_leftCornerWhere
= 2; /* on right chain*/
837 ret_leftCornerIndex
= tempI
;
841 ret_leftCornerWhere
= 0; /*on left chain*/
842 ret_leftCornerIndex
= index1
;
847 printf("***********leave findUpCorners\n");
851 //return 1 if neck exists, 0 othewise
852 Int
findNeckF(vertexArray
*leftChain
, Int botLeftIndex
,
853 vertexArray
*rightChain
, Int botRightIndex
,
854 gridBoundaryChain
* leftGridChain
,
855 gridBoundaryChain
* rightGridChain
,
861 printf("enter findNeckF, botleft, botright=%i,%i,gstartindex=%i\n",botLeftIndex,botRightIndex,gridStartIndex);
862 printf("leftChain is\n");
864 printf("rightChain is\n");
868 Int lowerGridIndex
; //the grid below leftChain and rightChian vertices
870 Int n_vlines
= leftGridChain
->get_nVlines();
872 if(botLeftIndex
>= leftChain
->getNumElements() ||
873 botRightIndex
>= rightChain
->getNumElements())
874 return 0; //no neck exists
876 v
=min(leftChain
->getVertex(botLeftIndex
)[1], rightChain
->getVertex(botRightIndex
)[1]);
881 for(i
=gridStartIndex
; i
<n_vlines
; i
++)
882 if(leftGridChain
->get_v_value(i
) <= v
&&
883 leftGridChain
->getUlineIndex(i
)<= rightGridChain
->getUlineIndex(i
))
888 if(lowerGridIndex
== n_vlines
) //the two trm vertex are higher than all gridlines
892 Int botLeft2
, botRight2
;
894 printf("leftGridChain->get_v_)value=%f\n",leftGridChain->get_v_value(lowerGridIndex), botLeftIndex);
895 printf("leftChain->get_vertex(0)=(%f,%f)\n", leftChain->getVertex(0)[0],leftChain->getVertex(0)[1]);
896 printf("leftChain->get_vertex(1)=(%f,%f)\n", leftChain->getVertex(1)[0],leftChain->getVertex(1)[1]);
897 printf("leftChain->get_vertex(2)=(%f,%f)\n", leftChain->getVertex(2)[0],leftChain->getVertex(2)[1]);
899 botLeft2
= leftChain
->findIndexFirstAboveEqualGen(leftGridChain
->get_v_value(lowerGridIndex
), botLeftIndex
, leftChain
->getNumElements()-1) -1 ;
902 printf("botLeft2=%i\n", botLeft2);
903 printf("leftChain->getNumElements=%i\n", leftChain->getNumElements());
906 botRight2
= rightChain
->findIndexFirstAboveEqualGen(leftGridChain
->get_v_value(lowerGridIndex
), botRightIndex
, rightChain
->getNumElements()-1) -1;
907 if(botRight2
< botRightIndex
) botRight2
=botRightIndex
;
909 if(botLeft2
< botLeftIndex
) botLeft2
= botLeftIndex
;
911 assert(botLeft2
>= botLeftIndex
);
912 assert(botRight2
>= botRightIndex
);
913 //find nectLeft so that it is th erightmost vertex on letChain
915 Int tempI
= botLeftIndex
;
916 Real temp
= leftChain
->getVertex(tempI
)[0];
917 for(i
=botLeftIndex
+1; i
<= botLeft2
; i
++)
918 if(leftChain
->getVertex(i
)[0] > temp
)
920 temp
= leftChain
->getVertex(i
)[0];
925 tempI
= botRightIndex
;
926 temp
= rightChain
->getVertex(tempI
)[0];
927 for(i
=botRightIndex
+1; i
<= botRight2
; i
++)
928 if(rightChain
->getVertex(i
)[0] < temp
)
930 temp
= rightChain
->getVertex(i
)[0];
940 /*find i>=botLeftIndex,j>=botRightIndex so that
941 *(leftChain[i], rightChain[j]) is a neck.
943 void findNeck(vertexArray
*leftChain
, Int botLeftIndex
,
944 vertexArray
*rightChain
, Int botRightIndex
,
945 Int
& leftLastIndex
, /*left point of the neck*/
946 Int
& rightLastIndex
/*right point of the neck*/
949 assert(botLeftIndex
< leftChain
->getNumElements() &&
950 botRightIndex
< rightChain
->getNumElements());
952 /*now the neck exists for sure*/
954 if(leftChain
->getVertex(botLeftIndex
)[1] <= rightChain
->getVertex(botRightIndex
)[1]) //left below right
957 leftLastIndex
= botLeftIndex
;
959 /*find i so that rightChain[i][1] >= leftchainbotverte[1], and i+1<
961 rightLastIndex
=rightChain
->findIndexAboveGen(leftChain
->getVertex(botLeftIndex
)[1], botRightIndex
+1, rightChain
->getNumElements()-1);
963 else //left above right
966 rightLastIndex
= botRightIndex
;
968 leftLastIndex
= leftChain
->findIndexAboveGen(rightChain
->getVertex(botRightIndex
)[1],
970 leftChain
->getNumElements()-1);
976 void findLeftGridIndices(directedLine
* topEdge
, Int firstGridIndex
, Int lastGridIndex
, gridWrap
* grid
, Int
* ret_indices
, Int
* ret_innerIndices
)
980 Int n_ulines
= grid
->get_n_ulines();
981 Real uMin
= grid
->get_u_min();
982 Real uMax
= grid
->get_u_max();
984 Real vMin = grid->get_v_min();
985 Real vMax = grid->get_v_max();
987 Real slop
= 0.0, uinterc
;
989 #ifdef SHORTEN_GRID_LINE
990 //uintercBuf stores all the interction u value for each grid line
991 //notice that lastGridIndex<= firstGridIndex
992 Real
*uintercBuf
= (Real
*) malloc (sizeof(Real
) * (firstGridIndex
-lastGridIndex
+1));
996 /*initialization to make vtail bigger than grid->...*/
997 directedLine
* dLine
= topEdge
;
998 Real vtail
= grid
->get_v_value(firstGridIndex
) + 1.0;
999 Real tempMaxU
= grid
->get_u_min();
1002 /*for each grid line*/
1003 for(k
=0, i
=firstGridIndex
; i
>=lastGridIndex
; i
--, k
++)
1006 Real grid_v_value
= grid
->get_v_value(i
);
1008 /*check whether this grid line is below the current trim edge.*/
1009 if(vtail
> grid_v_value
)
1011 /*since the grid line is below the trim edge, we
1012 *find the trim edge which will contain the trim line
1014 while( (vtail
=dLine
->tail()[1]) > grid_v_value
){
1016 tempMaxU
= max(tempMaxU
, dLine
->tail()[0]);
1017 dLine
= dLine
-> getNext();
1020 if( fabs(dLine
->head()[1] - vtail
) < ZERO
)
1025 slop
= (dLine
->head()[0] - dLine
->tail()[0]) / (dLine
->head()[1]-vtail
);
1031 uinterc
= max(dLine
->head()[0], dLine
->tail()[0]);
1035 uinterc
= slop
* (grid_v_value
- vtail
) + dLine
->tail()[0];
1038 tempMaxU
= max(tempMaxU
, uinterc
);
1040 if(uinterc
< uMin
&& uinterc
>= uMin
- ZERO
)
1042 if(uinterc
> uMax
&& uinterc
<= uMax
+ ZERO
)
1045 #ifdef SHORTEN_GRID_LINE
1046 uintercBuf
[k
] = uinterc
;
1049 assert(uinterc
>= uMin
&& uinterc
<= uMax
);
1051 ret_indices
[k
] = n_ulines
-1;
1053 ret_indices
[k
] = (Int
)(((uinterc
-uMin
)/(uMax
- uMin
)) * (n_ulines
-1)) + 1;
1054 if(ret_indices
[k
] >= n_ulines
)
1055 ret_indices
[k
] = n_ulines
-1;
1058 ret_innerIndices
[k
] = (Int
)(((tempMaxU
-uMin
)/(uMax
- uMin
)) * (n_ulines
-1)) + 1;
1060 /*reinitialize tempMaxU for next grdiLine*/
1063 #ifdef SHORTEN_GRID_LINE
1064 //for each grid line, compare the left grid point with the
1065 //intersection point. If the two points are too close, then
1066 //we should move the grid point one grid to the right
1067 //and accordingly we should update the inner index.
1068 for(k
=0, i
=firstGridIndex
; i
>=lastGridIndex
; i
--, k
++)
1071 //check ret_indices[k]
1072 Real a
= grid
->get_u_value(ret_indices
[k
]-1);
1073 Real b
= grid
->get_u_value(ret_indices
[k
]);
1074 assert(uintercBuf
[k
] >= a
&& uintercBuf
< b
);
1075 if( (b
-uintercBuf
[k
]) <= 0.2 * (b
-a
)) //interc is very close to b
1080 //check ret_innerIndices[k]
1083 if(ret_innerIndices
[k
] < ret_indices
[k
-1])
1084 ret_innerIndices
[k
] = ret_indices
[k
-1];
1085 if(ret_innerIndices
[k
] < ret_indices
[k
])
1086 ret_innerIndices
[k
] = ret_indices
[k
];
1094 void findRightGridIndices(directedLine
* topEdge
, Int firstGridIndex
, Int lastGridIndex
, gridWrap
* grid
, Int
* ret_indices
, Int
* ret_innerIndices
)
1098 Int n_ulines
= grid
->get_n_ulines();
1099 Real uMin
= grid
->get_u_min();
1100 Real uMax
= grid
->get_u_max();
1102 Real vMin = grid->get_v_min();
1103 Real vMax = grid->get_v_max();
1105 Real slop
= 0.0, uinterc
;
1107 #ifdef SHORTEN_GRID_LINE
1108 //uintercBuf stores all the interction u value for each grid line
1109 //notice that firstGridIndex >= lastGridIndex
1110 Real
*uintercBuf
= (Real
*) malloc (sizeof(Real
) * (firstGridIndex
-lastGridIndex
+1));
1114 /*initialization to make vhead bigger than grid->v_value...*/
1115 directedLine
* dLine
= topEdge
->getPrev();
1116 Real vhead
= dLine
->tail()[1];
1117 Real tempMinU
= grid
->get_u_max();
1119 /*for each grid line*/
1120 for(k
=0, i
=firstGridIndex
; i
>=lastGridIndex
; i
--, k
++)
1123 Real grid_v_value
= grid
->get_v_value(i
);
1126 /*check whether this grid line is below the current trim edge.*/
1127 if(vhead
>= grid_v_value
)
1129 /*since the grid line is below the tail of the trim edge, we
1130 *find the trim edge which will contain the trim line
1132 while( (vhead
=dLine
->head()[1]) > grid_v_value
){
1133 tempMinU
= min(tempMinU
, dLine
->head()[0]);
1134 dLine
= dLine
-> getPrev();
1137 /*skip the equality in the case of degenerat case: horizontal */
1138 while(dLine
->head()[1] == grid_v_value
)
1139 dLine
= dLine
->getPrev();
1141 assert( dLine
->tail()[1] != dLine
->head()[1]);
1142 slop
= (dLine
->tail()[0] - dLine
->head()[0]) / (dLine
->tail()[1]-dLine
->head()[1]);
1144 if(dLine->tail()[1] == vhead)
1149 slop = (dLine->tail()[0] - dLine->head()[0]) / (dLine->tail()[1]-vhead);
1153 uinterc
= slop
* (grid_v_value
- dLine
->head()[1]) + dLine
->head()[0];
1155 //in case unterc is outside of the grid due to floating point
1158 else if(uinterc
> uMax
)
1161 #ifdef SHORTEN_GRID_LINE
1162 uintercBuf
[k
] = uinterc
;
1165 tempMinU
= min(tempMinU
, uinterc
);
1167 assert(uinterc
>= uMin
&& uinterc
<= uMax
);
1172 ret_indices
[k
] = (int)ceil((((uinterc
-uMin
)/(uMax
- uMin
)) * (n_ulines
-1))) -1;
1174 if(ret_indices[k] >= grid->get_n_ulines())
1179 if(ret_indices[k] < 0)
1185 ret_innerIndices
[k
] = (int)ceil ((((tempMinU
-uMin
)/(uMax
- uMin
)) * (n_ulines
-1))) -1;
1189 #ifdef SHORTEN_GRID_LINE
1190 //for each grid line, compare the left grid point with the
1191 //intersection point. If the two points are too close, then
1192 //we should move the grid point one grid to the right
1193 //and accordingly we should update the inner index.
1194 for(k
=0, i
=firstGridIndex
; i
>=lastGridIndex
; i
--, k
++)
1197 //check ret_indices[k]
1198 Real a
= grid
->get_u_value(ret_indices
[k
]);
1199 Real b
= grid
->get_u_value(ret_indices
[k
]+1);
1200 assert(uintercBuf
[k
] > a
&& uintercBuf
<= b
);
1201 if( (uintercBuf
[k
]-a
) <= 0.2 * (b
-a
)) //interc is very close to a
1206 //check ret_innerIndices[k]
1209 if(ret_innerIndices
[k
] > ret_indices
[k
-1])
1210 ret_innerIndices
[k
] = ret_indices
[k
-1];
1211 if(ret_innerIndices
[k
] > ret_indices
[k
])
1212 ret_innerIndices
[k
] = ret_indices
[k
];
1221 void sampleMonoPoly(directedLine
* polygon
, gridWrap
* grid
, Int ulinear
, Int vlinear
, primStream
* pStream
, rectBlockArray
* rbArray
)
1226 polygon->writeAllPolygons("zloutputFile");
1231 if(grid
->get_n_ulines() == 2 ||
1232 grid
->get_n_vlines() == 2)
1234 if(ulinear
&& grid
->get_n_ulines() == 2)
1236 monoTriangulationFun(polygon
, compV2InY
, pStream
);
1239 else if(DBG_isConvex(polygon
) && polygon
->numEdges() >=4)
1241 triangulateConvexPoly(polygon
, ulinear
, vlinear
, pStream
);
1244 else if(vlinear
|| DBG_is_U_direction(polygon
))
1246 Int n_cusps
;//num interior cusps
1247 Int n_edges
= polygon
->numEdges();
1248 directedLine
** cusps
= (directedLine
**) malloc(sizeof(directedLine
*) * n_edges
);
1250 findInteriorCuspsX(polygon
, n_cusps
, cusps
);
1252 if(n_cusps
== 0) //u_monotone
1255 monoTriangulationFun(polygon
, compV2InX
, pStream
);
1260 else if(n_cusps
== 1) //one interior cusp
1263 directedLine
* new_polygon
= polygonConvert(cusps
[0]);
1265 directedLine
* other
= findDiagonal_singleCuspX( new_polygon
);
1269 //<other> should NOT be null unless there are self-intersecting
1270 //trim curves. In that case, we don't want to core dump, instead,
1271 //we triangulate anyway, and print out error message.
1274 monoTriangulationFun(polygon
, compV2InX
, pStream
);
1279 directedLine
* ret_p1
;
1280 directedLine
* ret_p2
;
1282 new_polygon
->connectDiagonal_2slines(new_polygon
, other
,
1287 monoTriangulationFun(ret_p1
, compV2InX
, pStream
);
1288 monoTriangulationFun(ret_p2
, compV2InX
, pStream
);
1290 ret_p1
->deleteSinglePolygonWithSline();
1291 ret_p2
->deleteSinglePolygonWithSline();
1300 /*find the top and bottom of the polygon. It is supposed to be
1301 *a V-monotone polygon
1304 directedLine
* tempV
;
1307 topV
= botV
= polygon
;
1309 for(tempV
= polygon
->getNext(); tempV
!= polygon
; tempV
= tempV
->getNext())
1311 if(compV2InY(topV
->head(), tempV
->head())<0) {
1315 if(compV2InY(botV
->head(), tempV
->head())>0) {
1321 /*find the first(top) and the last (bottom) grid line which intersect the
1324 Int firstGridIndex
; /*the index in the grid*/
1326 firstGridIndex
= (Int
) ((topV
->head()[1] - grid
->get_v_min()) / (grid
->get_v_max() - grid
->get_v_min()) * (grid
->get_n_vlines()-1));
1327 lastGridIndex
= (Int
) ((botV
->head()[1] - grid
->get_v_min()) / (grid
->get_v_max() - grid
->get_v_min()) * (grid
->get_n_vlines()-1)) + 1;
1330 /*find the interval inside the polygon for each gridline*/
1331 Int
*leftGridIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
1332 assert(leftGridIndices
);
1333 Int
*rightGridIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
1334 assert(rightGridIndices
);
1335 Int
*leftGridInnerIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
1336 assert(leftGridInnerIndices
);
1337 Int
*rightGridInnerIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
1338 assert(rightGridInnerIndices
);
1340 findLeftGridIndices(topV
, firstGridIndex
, lastGridIndex
, grid
, leftGridIndices
, leftGridInnerIndices
);
1342 findRightGridIndices(topV
, firstGridIndex
, lastGridIndex
, grid
, rightGridIndices
, rightGridInnerIndices
);
1344 gridBoundaryChain
leftGridChain(grid
, firstGridIndex
, firstGridIndex
-lastGridIndex
+1, leftGridIndices
, leftGridInnerIndices
);
1346 gridBoundaryChain
rightGridChain(grid
, firstGridIndex
, firstGridIndex
-lastGridIndex
+1, rightGridIndices
, rightGridInnerIndices
);
1350 // leftGridChain.draw();
1351 // leftGridChain.drawInner();
1352 // rightGridChain.draw();
1353 // rightGridChain.drawInner();
1354 /*(1) determine the grid boundaries (left and right).
1355 *(2) process polygon into two monotone chaines: use vertexArray
1356 *(3) call sampleMonoPolyRec
1359 /*copy the two chains into vertexArray datastructure*/
1361 vertexArray
leftChain(20); /*this is a dynamic array*/
1362 for(i
=1; i
<=topV
->get_npoints()-2; i
++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
1363 leftChain
.appendVertex(topV
->getVertex(i
));
1365 for(tempV
= topV
->getNext(); tempV
!= botV
; tempV
= tempV
->getNext())
1367 for(i
=0; i
<=tempV
->get_npoints()-2; i
++){
1368 leftChain
.appendVertex(tempV
->getVertex(i
));
1372 vertexArray
rightChain(20);
1373 for(tempV
= topV
->getPrev(); tempV
!= botV
; tempV
= tempV
->getPrev())
1375 for(i
=tempV
->get_npoints()-2; i
>=0; i
--){
1376 rightChain
.appendVertex(tempV
->getVertex(i
));
1379 for(i
=botV
->get_npoints()-2; i
>=1; i
--){
1380 rightChain
.appendVertex(tempV
->getVertex(i
));
1383 sampleMonoPolyRec(topV
->head(),
1397 free(leftGridIndices
);
1398 free(rightGridIndices
);
1399 free(leftGridInnerIndices
);
1400 free(rightGridInnerIndices
);
1403 void sampleMonoPolyRec(
1406 vertexArray
* leftChain
,
1408 vertexArray
* rightChain
,
1409 Int rightStartIndex
,
1410 gridBoundaryChain
* leftGridChain
,
1411 gridBoundaryChain
* rightGridChain
,
1413 primStream
* pStream
,
1414 rectBlockArray
* rbArray
)
1417 /*find the first connected component, and the four corners.
1419 Int index1
, index2
; /*the first and last grid line of the first connected component*/
1421 if(topVertex
[1] <= botVertex
[1])
1424 /*find i so that the grid line is below the top vertex*/
1425 Int i
=gridStartIndex
;
1426 while (i
< leftGridChain
->get_nVlines())
1428 if(leftGridChain
->get_v_value(i
) < topVertex
[1])
1433 /*find the first connected component starting with i*/
1434 /*find index1 so that left_uline_index <= right_uline_index, that is, this
1435 *grid line contains at least one inner grid point
1438 int num_skipped_grid_lines
=0;
1439 while(index1
< leftGridChain
->get_nVlines())
1441 if(leftGridChain
->getUlineIndex(index1
) <= rightGridChain
->getUlineIndex(index1
))
1443 num_skipped_grid_lines
++;
1449 if(index1
>= leftGridChain
->get_nVlines()) /*no grid line exists which has inner point*/
1451 /*stop recursion, ...*/
1452 /*monotone triangulate it...*/
1453 // printf("no grid line exists\n");
1455 monoTriangulationRecOpt(topVertex, botVertex, leftChain, leftStartIndex,
1456 rightChain, rightStartIndex, pStream);
1459 if(num_skipped_grid_lines
<2)
1461 monoTriangulationRecGenOpt(topVertex
, botVertex
, leftChain
, leftStartIndex
,
1462 leftChain
->getNumElements()-1,
1463 rightChain
, rightStartIndex
,
1464 rightChain
->getNumElements()-1,
1469 //the optimum way to triangulate is top-down since this polygon
1471 monoTriangulationRec(topVertex
, botVertex
, leftChain
, leftStartIndex
,
1472 rightChain
, rightStartIndex
, pStream
);
1476 monoTriangulationRec(topVertex, botVertex, leftChain, leftStartIndex,
1477 rightChain, rightStartIndex, pStream);
1480 /* monoTriangulationRecGenTBOpt(topVertex, botVertex,
1481 leftChain, leftStartIndex, leftChain->getNumElements()-1,
1482 rightChain, rightStartIndex, rightChain->getNumElements()-1,
1491 /*find index2 so that left_inner_index <= right_inner_index holds until index2*/
1493 if(index2
< leftGridChain
->get_nVlines())
1494 while(leftGridChain
->getInnerIndex(index2
) <= rightGridChain
->getInnerIndex(index2
))
1497 if(index2
>= leftGridChain
->get_nVlines())
1509 /*the four corners*/
1510 Int up_leftCornerWhere
;
1511 Int up_leftCornerIndex
;
1512 Int up_rightCornerWhere
;
1513 Int up_rightCornerIndex
;
1514 Int down_leftCornerWhere
;
1515 Int down_leftCornerIndex
;
1516 Int down_rightCornerWhere
;
1517 Int down_rightCornerIndex
;
1519 Real
* tempBotVertex
; /*the bottom vertex for this component*/
1520 Real
* nextTopVertex
=NULL
; /*for the recursion*/
1521 Int nextLeftStartIndex
=0;
1522 Int nextRightStartIndex
=0;
1524 /*find the points below the grid line index2 on both chains*/
1525 Int botLeftIndex
= leftChain
->findIndexStrictBelowGen(
1526 leftGridChain
->get_v_value(index2
),
1528 leftChain
->getNumElements()-1);
1529 Int botRightIndex
= rightChain
->findIndexStrictBelowGen(
1530 rightGridChain
->get_v_value(index2
),
1532 rightChain
->getNumElements()-1);
1533 /*if either botLeftIndex>= numelements,
1534 * or botRightIndex >= numelemnet,
1535 *then there is no neck exists. the bottom vertex is botVertex,
1537 if(! findNeckF(leftChain
, botLeftIndex
, rightChain
, botRightIndex
,
1538 leftGridChain
, rightGridChain
, index2
, neckLeftIndex
, neckRightIndex
))
1540 if(botLeftIndex == leftChain->getNumElements() ||
1541 botRightIndex == rightChain->getNumElements())
1545 printf("neck NOT exists, botRightIndex=%i\n", botRightIndex
);
1548 tempBotVertex
= botVertex
;
1549 nextTopVertex
= botVertex
;
1550 botLeftIndex
= leftChain
->getNumElements()-1;
1551 botRightIndex
= rightChain
->getNumElements()-1;
1553 else /*neck exists*/
1556 printf("neck exists\n");
1560 findNeck(leftChain, botLeftIndex,
1561 rightChain, botRightIndex,
1566 printf("neck is found, neckLeftIndex=%i, neckRightIndex=%i\n", neckLeftIndex
, neckRightIndex
);
1568 glVertex2fv(leftChain
->getVertex(neckLeftIndex
));
1569 glVertex2fv(rightChain
->getVertex(neckRightIndex
));
1573 if(leftChain
->getVertex(neckLeftIndex
)[1] <= rightChain
->getVertex(neckRightIndex
)[1])
1575 tempBotVertex
= leftChain
->getVertex(neckLeftIndex
);
1576 botLeftIndex
= neckLeftIndex
-1;
1577 botRightIndex
= neckRightIndex
;
1578 nextTopVertex
= rightChain
->getVertex(neckRightIndex
);
1579 nextLeftStartIndex
= neckLeftIndex
;
1580 nextRightStartIndex
= neckRightIndex
+1;
1584 tempBotVertex
= rightChain
->getVertex(neckRightIndex
);
1585 botLeftIndex
= neckLeftIndex
;
1586 botRightIndex
= neckRightIndex
-1;
1587 nextTopVertex
= leftChain
->getVertex(neckLeftIndex
);
1588 nextLeftStartIndex
= neckLeftIndex
+1;
1589 nextRightStartIndex
= neckRightIndex
;
1593 findUpCorners(topVertex
,
1595 leftStartIndex
, botLeftIndex
,
1597 rightStartIndex
, botRightIndex
,
1598 leftGridChain
->get_v_value(index1
),
1599 leftGridChain
->get_u_value(index1
),
1600 rightGridChain
->get_u_value(index1
),
1603 up_rightCornerWhere
,
1604 up_rightCornerIndex
);
1606 findDownCorners(tempBotVertex
,
1608 leftStartIndex
, botLeftIndex
,
1610 rightStartIndex
, botRightIndex
,
1611 leftGridChain
->get_v_value(index2
),
1612 leftGridChain
->get_u_value(index2
),
1613 rightGridChain
->get_u_value(index2
),
1614 down_leftCornerWhere
,
1615 down_leftCornerIndex
,
1616 down_rightCornerWhere
,
1617 down_rightCornerIndex
);
1619 printf("find corners done, down_leftwhere=%i, down_righwhere=%i,\n",down_leftCornerWhere
, down_rightCornerWhere
);
1620 printf("find corners done, up_leftwhere=%i, up_righwhere=%i,\n",up_leftCornerWhere
, up_rightCornerWhere
);
1621 printf("find corners done, up_leftindex=%i, up_righindex=%i,\n",up_leftCornerIndex
, up_rightCornerIndex
);
1622 printf("find corners done, down_leftindex=%i, down_righindex=%i,\n",down_leftCornerIndex
, down_rightCornerIndex
);
1626 drawCorners(topVertex,
1636 up_rightCornerWhere,
1637 up_rightCornerIndex,
1638 down_leftCornerWhere,
1639 down_leftCornerIndex,
1640 down_rightCornerWhere,
1641 down_rightCornerIndex);
1645 sampleConnectedComp(topVertex
, tempBotVertex
,
1647 leftStartIndex
, botLeftIndex
,
1649 rightStartIndex
, botRightIndex
,
1655 up_rightCornerWhere
,
1656 up_rightCornerIndex
,
1657 down_leftCornerWhere
,
1658 down_leftCornerIndex
,
1659 down_rightCornerWhere
,
1660 down_rightCornerIndex
,
1673 nextRightStartIndex
,
1684 void sampleLeftStrip(vertexArray
* leftChain
,
1687 gridBoundaryChain
* leftGridChain
,
1688 Int leftGridChainStartIndex
,
1689 Int leftGridChainEndIndex
,
1693 assert(leftChain
->getVertex(topLeftIndex
)[1] > leftGridChain
->get_v_value(leftGridChainStartIndex
));
1694 assert(leftChain
->getVertex(topLeftIndex
+1)[1] <= leftGridChain
->get_v_value(leftGridChainStartIndex
));
1695 assert(leftChain
->getVertex(botLeftIndex
)[1] <= leftGridChain
->get_v_value(leftGridChainEndIndex
));
1696 assert(leftChain
->getVertex(botLeftIndex
-1)[1] > leftGridChain
->get_v_value(leftGridChainEndIndex
));
1699 *(1)find the last grid line which doesn'; pass below
1700 * this first edge, sample this region: one trim edge and
1701 * possily multiple grid lines.
1703 Real
*upperVert
, *lowerVert
; /*the end points of the first trim edge*/
1704 upperVert
= leftChain
->getVertex(topLeftIndex
);
1705 lowerVert
= leftChain
->getVertex(topLeftIndex
+1);
1707 Int index
= leftGridChainStartIndex
;
1708 while(leftGridChain
->get_v_value(index
) >= lowerVert
[1]){
1710 if(index
> leftGridChainEndIndex
)
1715 sampleLeftSingleTrimEdgeRegion(upperVert
, lowerVert
,
1717 leftGridChainStartIndex
,
1720 sampleLeftStripRec(leftChain
, topLeftIndex
+1, botLeftIndex
,
1721 leftGridChain
, index
, leftGridChainEndIndex
,
1726 void sampleLeftStripRec(vertexArray
* leftChain
,
1729 gridBoundaryChain
* leftGridChain
,
1730 Int leftGridChainStartIndex
,
1731 Int leftGridChainEndIndex
,
1735 /*now top left trim vertex is below the top grid line.
1737 /*stop condition: if topLeftIndex >= botLeftIndex, then stop.
1739 if(topLeftIndex
>= botLeftIndex
)
1742 /*find the last trim vertex which is above the second top grid line:
1744 *and sampleLeftOneGridStep(leftchain, topLeftIndex, index1, leftGridChain,
1745 * leftGridChainStartIndex).
1746 * index1 could be equal to topLeftIndex.
1748 Real secondGridChainV
= leftGridChain
->get_v_value(leftGridChainStartIndex
+1);
1749 assert(leftGridChainStartIndex
< leftGridChainEndIndex
);
1750 Int index1
= topLeftIndex
;
1751 while(leftChain
->getVertex(index1
)[1] > secondGridChainV
)
1755 sampleLeftOneGridStep(leftChain
, topLeftIndex
, index1
, leftGridChain
, leftGridChainStartIndex
, pStream
);
1759 * Let the next trim vertex be nextTrimVertIndex (which should be
1760 * below the second grid line).
1761 * Find the last grid line index2 which is above nextTrimVert.
1762 * sampleLeftSingleTrimEdgeRegion(uppervert[2], lowervert[2],
1763 * leftGridChain, leftGridChainStartIndex+1, index2).
1765 Real
*uppervert
, *lowervert
;
1766 uppervert
= leftChain
->getVertex(index1
);
1767 lowervert
= leftChain
->getVertex(index1
+1);
1768 Int index2
= leftGridChainStartIndex
+1;
1770 while(leftGridChain
->get_v_value(index2
) >= lowervert
[1])
1773 if(index2
> leftGridChainEndIndex
)
1777 sampleLeftSingleTrimEdgeRegion(uppervert
, lowervert
, leftGridChain
, leftGridChainStartIndex
+1, index2
, pStream
);
1779 /* sampleLeftStripRec(leftChain,
1784 leftGridChainEndIndex
1788 sampleLeftStripRec(leftChain
, index1
+1, botLeftIndex
, leftGridChain
, index2
, leftGridChainEndIndex
, pStream
);
1793 /***************begin RecF***********************/
1794 /* the gridlines from leftGridChainStartIndex to
1795 * leftGridChainEndIndex are assumed to form a
1796 * connected component.
1797 * the trim vertex of topLeftIndex is assumed to
1798 * be below the first gridline, and the tim vertex
1799 * of botLeftIndex is assumed to be above the last
1801 * If botLeftIndex < topLeftIndex, then no connected componeent exists, and this funcion returns without
1802 * outputing any triangles.
1803 * Otherwise botLeftIndex >= topLeftIndex, there is at least one triangle to output.
1805 void sampleLeftStripRecF(vertexArray
* leftChain
,
1808 gridBoundaryChain
* leftGridChain
,
1809 Int leftGridChainStartIndex
,
1810 Int leftGridChainEndIndex
,
1814 /*now top left trim vertex is below the top grid line.
1816 /*stop condition: if topLeftIndex > botLeftIndex, then stop.
1818 if(topLeftIndex
> botLeftIndex
)
1821 /*if there is only one grid Line, return.*/
1823 if(leftGridChainStartIndex
>=leftGridChainEndIndex
)
1827 assert(leftChain
->getVertex(topLeftIndex
)[1] <= leftGridChain
->get_v_value(leftGridChainStartIndex
) &&
1828 leftChain
->getVertex(botLeftIndex
)[1] >= leftGridChain
->get_v_value(leftGridChainEndIndex
));
1830 /*firs find the first trim vertex which is below or equal to the second top grid line:
1833 Real secondGridChainV
= leftGridChain
->get_v_value(leftGridChainStartIndex
+1);
1836 Int index1
= topLeftIndex
;
1838 while(leftChain
->getVertex(index1
)[1] > secondGridChainV
){
1840 if(index1
>botLeftIndex
)
1844 /*now leftChain->getVertex(index-1)[1] > secondGridChainV and
1845 * leftChain->getVertex(index)[1] <= secondGridChainV
1846 *If equality holds, then we should include the vertex index1, otherwise we include only index1-1, to
1847 *perform sampleOneGridStep.
1849 if(index1
>botLeftIndex
)
1851 else if(leftChain
->getVertex(index1
)[1] < secondGridChainV
)
1854 /*now we have leftChain->getVertex(index1)[1] >= secondGridChainV, and
1855 * leftChain->getVertex(index1+1)[1] <= secondGridChainV
1859 sampleLeftOneGridStep(leftChain
, topLeftIndex
, index1
, leftGridChain
, leftGridChainStartIndex
, pStream
);
1862 /*if leftChain->getVertex(index1)[1] == secondGridChainV, then we can recursively do the rest.
1864 if(leftChain
->getVertex(index1
)[1] == secondGridChainV
)
1867 sampleLeftStripRecF(leftChain
, index1
, botLeftIndex
,leftGridChain
, leftGridChainStartIndex
+1, leftGridChainEndIndex
, pStream
);
1869 else if(index1
< botLeftIndex
)
1872 /* Otherwise, we have leftChain->getVertex(index1)[1] > secondGridChainV,
1873 * let the next trim vertex be nextTrimVertIndex (which should be strictly
1874 * below the second grid line).
1875 * Find the last grid line index2 which is above nextTrimVert.
1876 * sampleLeftSingleTrimEdgeRegion(uppervert[2], lowervert[2],
1877 * leftGridChain, leftGridChainStartIndex+1, index2).
1879 Real
*uppervert
, *lowervert
;
1880 uppervert
= leftChain
->getVertex(index1
);
1881 lowervert
= leftChain
->getVertex(index1
+1); //okay since index1<botLeftIndex
1882 Int index2
= leftGridChainStartIndex
+1;
1885 while(leftGridChain
->get_v_value(index2
) >= lowervert
[1])
1888 if(index2
> leftGridChainEndIndex
)
1894 sampleLeftSingleTrimEdgeRegion(uppervert
, lowervert
, leftGridChain
, leftGridChainStartIndex
+1, index2
, pStream
);
1898 sampleLeftStripRecF(leftChain
, index1
+1, botLeftIndex
, leftGridChain
, index2
, leftGridChainEndIndex
, pStream
);
1903 /***************End RecF***********************/
1905 /*sample the left area in between one trim edge and multiple grid lines.
1906 * all the grid lines should be in between the two end poins of the
1909 void sampleLeftSingleTrimEdgeRegion(Real upperVert
[2], Real lowerVert
[2],
1910 gridBoundaryChain
* gridChain
,
1913 primStream
* pStream
)
1917 vertexArray
vArray(endIndex
-beginIndex
+1);
1918 vArray
.appendVertex(gridChain
->get_vertex(beginIndex
));
1920 for(k
=1, i
=beginIndex
+1; i
<=endIndex
; i
++, k
++)
1922 vArray
.appendVertex(gridChain
->get_vertex(i
));
1924 /*output the fan of the grid points of the (i)th and (i-1)th grid line.
1926 if(gridChain
->getUlineIndex(i
) < gridChain
->getUlineIndex(i
-1))
1929 pStream
->insert(gridChain
->get_vertex(i
-1));
1930 for(j
=gridChain
->getUlineIndex(i
); j
<= gridChain
->getUlineIndex(i
-1); j
++)
1931 pStream
->insert(gridChain
->getGrid()->get_u_value(j
), gridChain
->get_v_value(i
));
1932 pStream
->end(PRIMITIVE_STREAM_FAN
);
1934 else if(gridChain
->getUlineIndex(i
) > gridChain
->getUlineIndex(i
-1))
1937 pStream
->insert(gridChain
->get_vertex(i
));
1938 for(j
=gridChain
->getUlineIndex(i
); j
>= gridChain
->getUlineIndex(i
-1); j
--)
1939 pStream
->insert(gridChain
->getGrid()->get_u_value(j
), gridChain
->get_v_value(i
-1));
1940 pStream
->end(PRIMITIVE_STREAM_FAN
);
1942 /*otherwisem, the two are equal, so there is no fan to outout*/
1945 monoTriangulation2(upperVert
, lowerVert
, &vArray
, 0, endIndex
-beginIndex
,
1946 0, /*decreasing chain*/
1950 /*return i, such that from begin to i-1 the chain is strictly u-monotone.
1952 Int
findIncreaseChainFromBegin(vertexArray
* chain
, Int begin
,Int end
)
1955 Real prevU
= chain
->getVertex(i
)[0];
1957 for(i
=begin
+1; i
<=end
; i
++){
1958 thisU
= chain
->getVertex(i
)[0];
1969 /*check whether there is a vertex whose v value is strictly
1970 *inbetween vup vbelow
1971 *if no middle exists return -1, else return the idnex.
1973 Int
checkMiddle(vertexArray
* chain
, Int begin
, Int end
,
1974 Real vup
, Real vbelow
)
1977 for(i
=begin
; i
<=end
; i
++)
1979 if(chain
->getVertex(i
)[1] < vup
&& chain
->getVertex(i
)[1]>vbelow
)
1985 /*the degenerat case of sampleLeftOneGridStep*/
1986 void sampleLeftOneGridStepNoMiddle(vertexArray
* leftChain
,
1989 gridBoundaryChain
* leftGridChain
,
1990 Int leftGridChainStartIndex
,
1991 primStream
* pStream
)
1993 /*since there is no middle, there is at most one point which is on the
1994 *second grid line, there could be multiple points on the first (top)
1998 leftGridChain
->leftEndFan(leftGridChainStartIndex
+1, pStream
);
2000 monoTriangulation2(leftGridChain
->get_vertex(leftGridChainStartIndex
),
2001 leftGridChain
->get_vertex(leftGridChainStartIndex
+1),
2005 1, //is increase chain.
2011 /*sampling the left area in between two grid lines.
2013 void sampleLeftOneGridStep(vertexArray
* leftChain
,
2016 gridBoundaryChain
* leftGridChain
,
2017 Int leftGridChainStartIndex
,
2021 if(checkMiddle(leftChain
, beginLeftIndex
, endLeftIndex
,
2022 leftGridChain
->get_v_value(leftGridChainStartIndex
),
2023 leftGridChain
->get_v_value(leftGridChainStartIndex
+1))<0)
2027 sampleLeftOneGridStepNoMiddle(leftChain
, beginLeftIndex
, endLeftIndex
, leftGridChain
, leftGridChainStartIndex
, pStream
);
2031 //copy into a polygon
2033 directedLine
* poly
= NULL
;
2035 directedLine
* dline
;
2036 gridWrap
* grid
= leftGridChain
->getGrid();
2041 Int innerInd
= leftGridChain
->getInnerIndex(leftGridChainStartIndex
+1);
2042 Int upperInd
= leftGridChain
->getUlineIndex(leftGridChainStartIndex
);
2043 Int lowerInd
= leftGridChain
->getUlineIndex(leftGridChainStartIndex
+1);
2044 Real upperV
= leftGridChain
->get_v_value(leftGridChainStartIndex
);
2045 Real lowerV
= leftGridChain
->get_v_value(leftGridChainStartIndex
+1);
2047 //the upper gridline
2048 vert1
[1] = vert2
[1] = upperV
;
2049 for(i
=innerInd
; i
>upperInd
; i
--)
2051 vert1
[0]=grid
->get_u_value(i
);
2052 vert2
[0]=grid
->get_u_value(i
-1);
2053 sline
= new sampledLine(vert1
, vert2
);
2054 dline
= new directedLine(INCREASING
, sline
);
2058 poly
->insert(dline
);
2061 //the edge connecting upper grid with left chain
2062 vert1
[0] = grid
->get_u_value(upperInd
);
2064 sline
= new sampledLine(vert1
, leftChain
->getVertex(beginLeftIndex
));
2065 dline
= new directedLine(INCREASING
, sline
);
2069 poly
->insert(dline
);
2072 for(i
=beginLeftIndex
; i
<endLeftIndex
; i
++)
2074 sline
= new sampledLine(leftChain
->getVertex(i
), leftChain
->getVertex(i
+1));
2075 dline
= new directedLine(INCREASING
, sline
);
2076 poly
->insert(dline
);
2079 //the edge connecting left chain with lower gridline
2080 vert2
[0] = grid
->get_u_value(lowerInd
);
2082 sline
= new sampledLine(leftChain
->getVertex(endLeftIndex
), vert2
);
2083 dline
= new directedLine(INCREASING
, sline
);
2084 poly
->insert(dline
);
2086 //the lower grid line
2087 vert1
[1] = vert2
[1] = lowerV
;
2088 for(i
=lowerInd
; i
<innerInd
; i
++)
2090 vert1
[0] = grid
->get_u_value(i
);
2091 vert2
[0] = grid
->get_u_value(i
+1);
2092 sline
= new sampledLine(vert1
, vert2
);
2093 dline
= new directedLine(INCREASING
, sline
);
2094 poly
->insert(dline
);
2097 //the vertical grid line segement
2098 vert1
[0]=vert2
[0] = grid
->get_u_value(innerInd
);
2101 sline
=new sampledLine(vert1
, vert2
);
2102 dline
=new directedLine(INCREASING
, sline
);
2103 poly
->insert(dline
);
2104 monoTriangulationOpt(poly
, pStream
);
2106 poly
->deleteSinglePolygonWithSline();
2115 if(1/*leftGridChain->getUlineIndex(leftGridChainStartIndex) >=
2116 leftGridChain->getUlineIndex(leftGridChainStartIndex+1)*/
2117 ) /*the second grid line is beyond the first one to the left*/
2119 /*find the maximal U-monotone chain
2120 * of endLeftIndex, endLeftIndex-1, ...,
2123 Real prevU
= leftChain
->getVertex(i
)[0];
2124 for(i
=endLeftIndex
-1; i
>=beginLeftIndex
; i
--){
2125 Real thisU
= leftChain
->getVertex(i
)[0];
2132 /*from endLeftIndex to i+1 is strictly U- monotone */
2133 /*if i+1==endLeftIndex and the vertex and leftchain is on the second gridline, then
2134 *we should use 2 vertices on the leftchain. If we only use one (endLeftIndex), then we
2135 *we would output degenerate triangles
2137 if(i
+1 == endLeftIndex
&& leftChain
->getVertex(endLeftIndex
)[1] == leftGridChain
->get_v_value(1+leftGridChainStartIndex
))
2140 Int j
= beginLeftIndex
/*endLeftIndex*/+1;
2143 if(leftGridChain
->getInnerIndex(leftGridChainStartIndex
+1) > leftGridChain
->getUlineIndex(leftGridChainStartIndex
))
2145 j
= findIncreaseChainFromBegin(leftChain
, beginLeftIndex
, i
+1/*endLeftIndex*/);
2147 Int temp
= beginLeftIndex
;
2148 /*now from begin to j-1 is strictly u-monotone*/
2149 /*if j-1 is on the first grid line, then we want to skip to the vertex which is strictly
2150 *below the grid line. This vertexmust exist since there is a 'corner turn' inbetween the two grid lines
2152 if(j
-1 == beginLeftIndex
)
2154 while(leftChain
->getVertex(j
-1)[1] == leftGridChain
->get_v_value(leftGridChainStartIndex
))
2158 vert
[0] = leftGridChain
->get_u_value(leftGridChainStartIndex
);
2159 vert
[1] = leftGridChain
->get_v_value(leftGridChainStartIndex
);
2162 vert
/*leftChain->getVertex(beginLeftIndex)*/,
2163 leftChain
->getVertex(j
-1),
2168 pStream
//increase chain
2174 stripOfFanLeft(leftChain
, j
-1, temp
/*beginLeftIndex*/, leftGridChain
->getGrid(),
2175 leftGridChain
->getVlineIndex(leftGridChainStartIndex
),
2176 leftGridChain
->getUlineIndex(leftGridChainStartIndex
),
2177 leftGridChain
->getInnerIndex(leftGridChainStartIndex
+1),
2179 1 /*the grid line is above the trim line*/
2183 stripOfFanLeft(leftChain
, endLeftIndex
, i
+1, leftGridChain
->getGrid(),
2184 leftGridChain
->getVlineIndex(leftGridChainStartIndex
+1),
2185 leftGridChain
->getUlineIndex(leftGridChainStartIndex
+1),
2186 leftGridChain
->getInnerIndex(leftGridChainStartIndex
+1),
2188 0 /*the grid line is below the trim lines*/
2191 /*monotone triangulate the remaining left chain togther with the
2192 *two vertices on the two grid v-lines.
2195 vert
[0][0]=vert
[1][0] = leftGridChain
->getInner_u_value(leftGridChainStartIndex
+1);
2196 vert
[0][1] = leftGridChain
->get_v_value(leftGridChainStartIndex
);
2197 vert
[1][1] = leftGridChain
->get_v_value(leftGridChainStartIndex
+1);
2199 // vertexArray right(vert, 2);
2202 &vert
[0][0], /*top vertex */
2203 &vert
[1][0], /*bottom vertex*/
2205 /*beginLeftIndex*/j
-1,
2207 1, /*an increasing chain*/
2210 else /*the second one is shorter than the first one to the left*/
2212 /*find the maximal U-monotone chain of beginLeftIndex, beginLeftIndex+1,...,
2215 Real prevU
= leftChain
->getVertex(i
)[0];
2216 for(i
=beginLeftIndex
+1; i
<=endLeftIndex
; i
++){
2217 Real thisU
= leftChain
->getVertex(i
)[0];
2225 /*from beginLeftIndex to i-1 is strictly U-monotone*/
2228 stripOfFanLeft(leftChain
, i
-1, beginLeftIndex
, leftGridChain
->getGrid(),
2229 leftGridChain
->getVlineIndex(leftGridChainStartIndex
),
2230 leftGridChain
->getUlineIndex(leftGridChainStartIndex
),
2231 leftGridChain
->getUlineIndex(leftGridChainStartIndex
+1),
2233 1 /*the grid line is above the trim lines*/
2235 /*monotone triangulate the remaining left chain together with the
2236 *two vertices on the two grid v-lines.
2239 vert
[0][0]=vert
[1][0] = leftGridChain
->get_u_value(leftGridChainStartIndex
+1);
2240 vert
[0][1] = leftGridChain
->get_v_value(leftGridChainStartIndex
);
2241 vert
[1][1] = leftGridChain
->get_v_value(leftGridChainStartIndex
+1);
2243 vertexArray
right(vert
, 2);
2246 &vert
[0][0], //top vertex
2247 &vert
[1][0], //bottom vertex
2251 1, /*an increase chain*/
2260 void triangulateXYMono(Int n_upper
, Real upperVerts
[][2],
2261 Int n_lower
, Real lowerVerts
[][2],
2262 primStream
* pStream
)
2267 assert(n_upper
>=1 && n_lower
>=1);
2268 if(upperVerts
[0][0] <= lowerVerts
[0][0])
2272 leftMostV
= upperVerts
[0];
2278 leftMostV
= lowerVerts
[0];
2283 if(i
>= n_upper
) /*case1: no more in upper*/
2286 if(j
<n_lower
-1) /*at least two vertices in lower*/
2289 pStream
->insert(leftMostV
);
2291 pStream
->insert(lowerVerts
[j
]);
2294 pStream
->end(PRIMITIVE_STREAM_FAN
);
2299 else if(j
>= n_lower
) /*case2: no more in lower*/
2302 if(i
<n_upper
-1) /*at least two vertices in upper*/
2305 pStream
->insert(leftMostV
);
2307 for(k
=n_upper
-1; k
>=i
; k
--)
2308 pStream
->insert(upperVerts
[k
]);
2310 pStream
->end(PRIMITIVE_STREAM_FAN
);
2315 else /* case3: neither is empty, plus the leftMostV, there is at least one triangle to output*/
2318 if(upperVerts
[i
][0] <= lowerVerts
[j
][0])
2321 pStream
->insert(lowerVerts
[j
]); /*the origin of this fan*/
2323 /*find the last k>=i such that
2324 *upperverts[k][0] <= lowerverts[j][0]
2329 if(upperVerts
[k
][0] > lowerVerts
[j
][0])
2334 for(l
=k
; l
>=i
; l
--)/*the reverse is for two-face lighting*/
2336 pStream
->insert(upperVerts
[l
]);
2338 pStream
->insert(leftMostV
);
2340 pStream
->end(PRIMITIVE_STREAM_FAN
);
2341 //update i for next loop
2343 leftMostV
= upperVerts
[k
];
2346 else /*upperVerts[i][0] > lowerVerts[j][0]*/
2349 pStream
->insert(upperVerts
[i
]);/*the origion of this fan*/
2350 pStream
->insert(leftMostV
);
2351 /*find the last k>=j such that
2352 *lowerverts[k][0] < upperverts[i][0]*/
2356 if(lowerVerts
[k
][0] >= upperVerts
[i
][0])
2358 pStream
->insert(lowerVerts
[k
]);
2361 pStream
->end(PRIMITIVE_STREAM_FAN
);
2363 leftMostV
= lowerVerts
[j
-1];
2370 void stripOfFanLeft(vertexArray
* leftChain
,
2375 Int ulineSmallIndex
,
2376 Int ulineLargeIndex
,
2377 primStream
* pStream
,
2378 Int gridLineUp
/*1 if the grid line is above the trim lines*/
2381 assert(largeIndex
>= smallIndex
);
2384 grid_v_value
= grid
->get_v_value(vlineIndex
);
2386 Real2
* trimVerts
=(Real2
*) malloc(sizeof(Real2
)* (largeIndex
-smallIndex
+1));
2390 Real2
* gridVerts
=(Real2
*) malloc(sizeof(Real2
)* (ulineLargeIndex
-ulineSmallIndex
+1));
2394 if(gridLineUp
) /*trim line is below grid line, so trim vertices are going right when index increases*/
2395 for(k
=0, i
=smallIndex
; i
<=largeIndex
; i
++, k
++)
2397 trimVerts
[k
][0] = leftChain
->getVertex(i
)[0];
2398 trimVerts
[k
][1] = leftChain
->getVertex(i
)[1];
2401 for(k
=0, i
=largeIndex
; i
>=smallIndex
; i
--, k
++)
2403 trimVerts
[k
][0] = leftChain
->getVertex(i
)[0];
2404 trimVerts
[k
][1] = leftChain
->getVertex(i
)[1];
2407 for(k
=0, i
=ulineSmallIndex
; i
<= ulineLargeIndex
; i
++, k
++)
2409 gridVerts
[k
][0] = grid
->get_u_value(i
);
2410 gridVerts
[k
][1] = grid_v_value
;
2415 ulineLargeIndex
-ulineSmallIndex
+1, gridVerts
,
2416 largeIndex
-smallIndex
+1, trimVerts
,
2419 triangulateXYMono(largeIndex
-smallIndex
+1, trimVerts
,
2420 ulineLargeIndex
-ulineSmallIndex
+1, gridVerts
,