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.
44 #define max(a,b) ((a>b)? a:b)
47 #define min(a,b) ((a>b)? b:a)
52 #include "glimports.h"
54 #include "sampleMonoPoly.h"
55 #include "sampleComp.h"
57 #include "partitionX.h"
64 //#define SHORTEN_GRID_LINE
65 //see work/newtess/internal/test/problems
68 /*split a polygon so that each vertex correcpond to one edge
69 *the head of the first edge of the returned plygon must be the head of the first
70 *edge of the origianl polygon. This is crucial for the code in sampleMonoPoly function
72 directedLine
* polygonConvert(directedLine
* polygon
)
77 sline
= new sampledLine(2);
78 sline
->setPoint(0, polygon
->getVertex(0));
79 sline
->setPoint(1, polygon
->getVertex(1));
80 ret
=new directedLine(INCREASING
, sline
);
81 for(i
=1; i
<= polygon
->get_npoints()-2; i
++)
83 sline
= new sampledLine(2);
84 sline
->setPoint(0, polygon
->getVertex(i
));
85 sline
->setPoint(1, polygon
->getVertex(i
+1));
86 ret
->insert(new directedLine(INCREASING
, sline
));
89 for(directedLine
*temp
= polygon
->getNext(); temp
!= polygon
; temp
= temp
->getNext())
91 for(i
=0; i
<= temp
->get_npoints()-2; i
++)
93 sline
= new sampledLine(2);
94 sline
->setPoint(0, temp
->getVertex(i
));
95 sline
->setPoint(1, temp
->getVertex(i
+1));
96 ret
->insert(new directedLine(INCREASING
, sline
));
102 void triangulateConvexPolyVertical(directedLine
* topV
, directedLine
* botV
, primStream
*pStream
)
111 for(tempV
= topV
; tempV
!= botV
; tempV
= tempV
->getNext())
113 n_leftVerts
+= tempV
->get_npoints();
116 for(tempV
= botV
; tempV
!= topV
; tempV
= tempV
->getNext())
118 n_rightVerts
+= tempV
->get_npoints();
121 Real2
* temp_leftVerts
= (Real2
*) malloc(sizeof(Real2
) * n_leftVerts
);
122 assert(temp_leftVerts
);
123 Real2
* temp_rightVerts
= (Real2
*) malloc(sizeof(Real2
) * n_rightVerts
);
124 assert(temp_rightVerts
);
126 leftVerts
= (Real
**) malloc(sizeof(Real2
*) * n_leftVerts
);
128 rightVerts
= (Real
**) malloc(sizeof(Real2
*) * n_rightVerts
);
130 for(i
=0; i
<n_leftVerts
; i
++)
131 leftVerts
[i
] = temp_leftVerts
[i
];
132 for(i
=0; i
<n_rightVerts
; i
++)
133 rightVerts
[i
] = temp_rightVerts
[i
];
136 for(tempV
= topV
; tempV
!= botV
; tempV
= tempV
->getNext())
138 for(j
=1; j
<tempV
->get_npoints(); j
++)
140 leftVerts
[i
][0] = tempV
->getVertex(j
)[0];
141 leftVerts
[i
][1] = tempV
->getVertex(j
)[1];
147 for(tempV
= topV
->getPrev(); tempV
!= botV
->getPrev(); tempV
= tempV
->getPrev())
149 for(j
=tempV
->get_npoints()-1; j
>=1; j
--)
151 rightVerts
[i
][0] = tempV
->getVertex(j
)[0];
152 rightVerts
[i
][1] = tempV
->getVertex(j
)[1];
157 triangulateXYMonoTB(n_leftVerts
, leftVerts
, n_rightVerts
, rightVerts
, pStream
);
160 free(temp_leftVerts
);
161 free(temp_rightVerts
);
164 void triangulateConvexPolyHoriz(directedLine
* leftV
, directedLine
* rightV
, primStream
*pStream
)
173 for(tempV
= leftV
; tempV
!= rightV
; tempV
= tempV
->getNext())
175 n_lowerVerts
+= tempV
->get_npoints();
178 for(tempV
= rightV
; tempV
!= leftV
; tempV
= tempV
->getNext())
180 n_upperVerts
+= tempV
->get_npoints();
182 lowerVerts
= (Real2
*) malloc(sizeof(Real2
) * n_lowerVerts
);
183 assert(n_lowerVerts
);
184 upperVerts
= (Real2
*) malloc(sizeof(Real2
) * n_upperVerts
);
185 assert(n_upperVerts
);
187 for(tempV
= leftV
; tempV
!= rightV
; tempV
= tempV
->getNext())
189 for(j
=0; j
<tempV
->get_npoints(); j
++)
191 lowerVerts
[i
][0] = tempV
->getVertex(j
)[0];
192 lowerVerts
[i
][1] = tempV
->getVertex(j
)[1];
197 for(tempV
= leftV
->getPrev(); tempV
!= rightV
->getPrev(); tempV
= tempV
->getPrev())
199 for(j
=tempV
->get_npoints()-1; j
>=0; j
--)
201 upperVerts
[i
][0] = tempV
->getVertex(j
)[0];
202 upperVerts
[i
][1] = tempV
->getVertex(j
)[1];
206 triangulateXYMono(n_upperVerts
, upperVerts
, n_lowerVerts
, lowerVerts
, pStream
);
210 void triangulateConvexPoly(directedLine
* polygon
, Int ulinear
, Int vlinear
, primStream
* pStream
)
212 /*find left, right, top , bot
218 directedLine
* rightV
;
219 topV
= botV
= polygon
;
221 for(tempV
= polygon
->getNext(); tempV
!= polygon
; tempV
= tempV
->getNext())
223 if(compV2InY(topV
->head(), tempV
->head())<0) {
227 if(compV2InY(botV
->head(), tempV
->head())>0) {
233 for(tempV
= topV
; tempV
!= botV
; tempV
= tempV
->getNext())
235 if(tempV
->tail()[0] >= tempV
->head()[0])
240 for(tempV
= botV
; tempV
!= topV
; tempV
= tempV
->getNext())
242 if(tempV
->tail()[0] <= tempV
->head()[0])
248 triangulateConvexPolyHoriz( leftV
, rightV
, pStream
);
252 triangulateConvexPolyVertical(topV
, botV
, pStream
);
256 if(DBG_is_U_direction(polygon
))
258 triangulateConvexPolyHoriz( leftV
, rightV
, pStream
);
261 triangulateConvexPolyVertical(topV
, botV
, pStream
);
265 /*for debug purpose*/
267 Real
* topV
, Real
* botV
,
268 vertexArray
* leftChain
,
269 vertexArray
* rightChain
,
270 gridBoundaryChain
* leftGridChain
,
271 gridBoundaryChain
* rightGridChain
,
276 Int rightCornerWhere
,
277 Int rightCornerIndex
,
278 Int bot_leftCornerWhere
,
279 Int bot_leftCornerIndex
,
280 Int bot_rightCornerWhere
,
281 Int bot_rightCornerIndex
)
285 Real
* bot_leftCornerV
;
286 Real
* bot_rightCornerV
;
288 if(leftCornerWhere
== 1)
290 else if(leftCornerWhere
== 0)
291 leftCornerV
= leftChain
->getVertex(leftCornerIndex
);
293 leftCornerV
= rightChain
->getVertex(leftCornerIndex
);
295 if(rightCornerWhere
== 1)
297 else if(rightCornerWhere
== 0)
298 rightCornerV
= leftChain
->getVertex(rightCornerIndex
);
300 rightCornerV
= rightChain
->getVertex(rightCornerIndex
);
302 if(bot_leftCornerWhere
== 1)
303 bot_leftCornerV
= botV
;
304 else if(bot_leftCornerWhere
== 0)
305 bot_leftCornerV
= leftChain
->getVertex(bot_leftCornerIndex
);
307 bot_leftCornerV
= rightChain
->getVertex(bot_leftCornerIndex
);
309 if(bot_rightCornerWhere
== 1)
310 bot_rightCornerV
= botV
;
311 else if(bot_rightCornerWhere
== 0)
312 bot_rightCornerV
= leftChain
->getVertex(bot_rightCornerIndex
);
314 bot_rightCornerV
= rightChain
->getVertex(bot_rightCornerIndex
);
316 Real topGridV
= leftGridChain
->get_v_value(gridIndex1
);
317 Real topGridU1
= leftGridChain
->get_u_value(gridIndex1
);
318 Real topGridU2
= rightGridChain
->get_u_value(gridIndex1
);
319 Real botGridV
= leftGridChain
->get_v_value(gridIndex2
);
320 Real botGridU1
= leftGridChain
->get_u_value(gridIndex2
);
321 Real botGridU2
= rightGridChain
->get_u_value(gridIndex2
);
323 glBegin(GL_LINE_STRIP
);
324 glVertex2fv(leftCornerV
);
325 glVertex2f(topGridU1
, topGridV
);
328 glBegin(GL_LINE_STRIP
);
329 glVertex2fv(rightCornerV
);
330 glVertex2f(topGridU2
, topGridV
);
333 glBegin(GL_LINE_STRIP
);
334 glVertex2fv(bot_leftCornerV
);
335 glVertex2f(botGridU1
, botGridV
);
338 glBegin(GL_LINE_STRIP
);
339 glVertex2fv(bot_rightCornerV
);
340 glVertex2f(botGridU2
, botGridV
);
346 void toVertexArrays(directedLine
* topV
, directedLine
* botV
, vertexArray
& leftChain
, vertexArray
& rightChain
)
350 for(i
=1; i
<=topV
->get_npoints()-2; i
++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
351 leftChain
.appendVertex(topV
->getVertex(i
));
353 for(tempV
= topV
->getNext(); tempV
!= botV
; tempV
= tempV
->getNext())
355 for(i
=0; i
<=tempV
->get_npoints()-2; i
++){
356 leftChain
.appendVertex(tempV
->getVertex(i
));
360 for(tempV
= topV
->getPrev(); tempV
!= botV
; tempV
= tempV
->getPrev())
362 for(i
=tempV
->get_npoints()-2; i
>=0; i
--){
363 rightChain
.appendVertex(tempV
->getVertex(i
));
366 for(i
=botV
->get_npoints()-2; i
>=1; i
--){
367 rightChain
.appendVertex(tempV
->getVertex(i
));
372 void findTopAndBot(directedLine
* polygon
, directedLine
*& topV
, directedLine
*& botV
)
376 topV
= botV
= polygon
;
377 for(tempV
= polygon
->getNext(); tempV
!= polygon
; tempV
= tempV
->getNext())
379 if(compV2InY(topV
->head(), tempV
->head())<0) {
382 if(compV2InY(botV
->head(), tempV
->head())>0) {
388 void findGridChains(directedLine
* topV
, directedLine
* botV
,
390 gridBoundaryChain
*& leftGridChain
,
391 gridBoundaryChain
*& rightGridChain
)
393 /*find the first(top) and the last (bottom) grid line which intersect the
396 Int firstGridIndex
; /*the index in the grid*/
399 firstGridIndex
= (Int
) ((topV
->head()[1] - grid
->get_v_min()) / (grid
->get_v_max() - grid
->get_v_min()) * (grid
->get_n_vlines()-1));
401 if(botV
->head()[1] < grid
->get_v_min())
404 lastGridIndex
= (Int
) ((botV
->head()[1] - grid
->get_v_min()) / (grid
->get_v_max() - grid
->get_v_min()) * (grid
->get_n_vlines()-1)) + 1;
406 /*find the interval inside the polygon for each gridline*/
407 Int
*leftGridIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
408 assert(leftGridIndices
);
409 Int
*rightGridIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
410 assert(rightGridIndices
);
411 Int
*leftGridInnerIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
412 assert(leftGridInnerIndices
);
413 Int
*rightGridInnerIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
414 assert(rightGridInnerIndices
);
416 findLeftGridIndices(topV
, firstGridIndex
, lastGridIndex
, grid
, leftGridIndices
, leftGridInnerIndices
);
418 findRightGridIndices(topV
, firstGridIndex
, lastGridIndex
, grid
, rightGridIndices
, rightGridInnerIndices
);
420 leftGridChain
= new gridBoundaryChain(grid
, firstGridIndex
, firstGridIndex
-lastGridIndex
+1, leftGridIndices
, leftGridInnerIndices
);
422 rightGridChain
= new gridBoundaryChain(grid
, firstGridIndex
, firstGridIndex
-lastGridIndex
+1, rightGridIndices
, rightGridInnerIndices
);
424 free(leftGridIndices
);
425 free(rightGridIndices
);
426 free(leftGridInnerIndices
);
427 free(rightGridInnerIndices
);
430 void findDownCorners(Real
*botVertex
,
431 vertexArray
*leftChain
, Int leftChainStartIndex
, Int leftChainEndIndex
,
432 vertexArray
*rightChain
, Int rightChainStartIndex
, Int rightChainEndIndex
,
436 Int
& ret_leftCornerWhere
, /*0: left chain, 1: topvertex, 2: rightchain*/
437 Int
& ret_leftCornerIndex
, /*useful when ret_leftCornerWhere == 0 or 2*/
438 Int
& ret_rightCornerWhere
, /*0: left chain, 1: topvertex, 2: rightchain*/
439 Int
& ret_rightCornerIndex
/*useful when ret_leftCornerWhere == 0 or 2*/
443 printf("*************enter find donw corner\n");
444 printf("finddownCorner: v=%f, uleft=%f, uright=%f\n", v
, uleft
, uright
);
445 printf("(%i,%i,%i,%i)\n", leftChainStartIndex
, leftChainEndIndex
,rightChainStartIndex
, rightChainEndIndex
);
446 printf("left chain is\n");
448 printf("right chain is\n");
452 assert(v
> botVertex
[1]);
453 Real leftGridPoint
[2];
454 leftGridPoint
[0] = uleft
;
455 leftGridPoint
[1] = v
;
456 Real rightGridPoint
[2];
457 rightGridPoint
[0] = uright
;
458 rightGridPoint
[1] = v
;
463 index1
= leftChain
->findIndexBelowGen(v
, leftChainStartIndex
, leftChainEndIndex
);
464 index2
= rightChain
->findIndexBelowGen(v
, rightChainStartIndex
, rightChainEndIndex
);
466 if(index2
<= rightChainEndIndex
) //index2 was found above
467 index2
= rightChain
->skipEqualityFromStart(v
, index2
, rightChainEndIndex
);
469 if(index1
>leftChainEndIndex
&& index2
> rightChainEndIndex
) /*no point below v on left chain or right chain*/
472 /*the botVertex is the only vertex below v*/
473 ret_leftCornerWhere
= 1;
474 ret_rightCornerWhere
= 1;
476 else if(index1
>leftChainEndIndex
) /*index2 <= rightChainEndIndex*/
479 ret_rightCornerWhere
= 2; /*on right chain*/
480 ret_rightCornerIndex
= index2
;
483 Real tempMin
= rightChain
->getVertex(index2
)[0];
485 for(i
=index2
+1; i
<= rightChainEndIndex
; i
++)
486 if(rightChain
->getVertex(i
)[0] < tempMin
)
489 tempMin
= rightChain
->getVertex(i
)[0];
493 //we consider whether we can use botVertex as left corner. First check
494 //if (leftGirdPoint, botVertex) interesects right chian or not.
495 if(DBG_intersectChain(rightChain
, rightChainStartIndex
,rightChainEndIndex
,
496 leftGridPoint
, botVertex
))
498 ret_leftCornerWhere
= 2;//right
499 ret_leftCornerIndex
= index2
; //should use tempI???
501 else if(botVertex
[0] < tempMin
)
502 ret_leftCornerWhere
= 1; //bot
505 ret_leftCornerWhere
= 2; //right
506 ret_leftCornerIndex
= tempI
;
509 else if(index2
> rightChainEndIndex
) /*index1<=leftChainEndIndex*/
511 ret_leftCornerWhere
= 0; /*left chain*/
512 ret_leftCornerIndex
= index1
;
514 /*find the vertex on the left chain with the maximum u,
515 *either this vertex or the botvertex can be used as the right corner
519 //skip those points which are equal to v. (avoid degeneratcy)
520 for(tempI
= index1
; tempI
<= leftChainEndIndex
; tempI
++)
521 if(leftChain
->getVertex(tempI
)[1] < v
)
523 if(tempI
> leftChainEndIndex
)
524 ret_rightCornerWhere
= 1;
527 Real tempMax
= leftChain
->getVertex(tempI
)[0];
528 for(i
=tempI
; i
<= leftChainEndIndex
; i
++)
529 if(leftChain
->getVertex(i
)[0] > tempMax
)
532 tempMax
= leftChain
->getVertex(i
)[0];
537 //we consider whether we can use botVertex as a corner. So first we check
538 //whether (rightGridPoint, botVertex) interescts the left chain or not.
539 if(DBG_intersectChain(leftChain
, leftChainStartIndex
,leftChainEndIndex
,
540 rightGridPoint
, botVertex
))
542 ret_rightCornerWhere
= 0;
543 ret_rightCornerIndex
= index1
; //should use tempI???
545 else if(botVertex
[0] > tempMax
)
548 ret_rightCornerWhere
= 1;
552 ret_rightCornerWhere
= 0;
553 ret_rightCornerIndex
= tempI
;
558 else /*index1<=leftChainEndIndex and index2 <=rightChainEndIndex*/
560 if(leftChain
->getVertex(index1
)[1] >= rightChain
->getVertex(index2
)[1]) /*left point above right point*/
562 ret_leftCornerWhere
= 0; /*on left chain*/
563 ret_leftCornerIndex
= index1
;
569 tempMax
= leftChain
->getVertex(index1
)[0];
571 /*find the maximum u for all the points on the left above the right point index2*/
572 for(i
=index1
+1; i
<= leftChainEndIndex
; i
++)
574 if(leftChain
->getVertex(i
)[1] < rightChain
->getVertex(index2
)[1])
577 if(leftChain
->getVertex(i
)[0]>tempMax
)
580 tempMax
= leftChain
->getVertex(i
)[0];
583 //we consider if we can use rightChain(index2) as right corner
584 //we check if (rightChain(index2), rightGidPoint) intersecs left chain or not.
585 if(DBG_intersectChain(leftChain
, leftChainStartIndex
,leftChainEndIndex
, rightGridPoint
, rightChain
->getVertex(index2
)))
587 ret_rightCornerWhere
= 0;
588 ret_rightCornerIndex
= index1
; //should use tempI???
590 else if(tempMax
>= rightChain
->getVertex(index2
)[0] ||
595 ret_rightCornerWhere
= 0; /*on left Chain*/
596 ret_rightCornerIndex
= tempI
;
600 ret_rightCornerWhere
= 2; /*on right chain*/
601 ret_rightCornerIndex
= index2
;
604 else /*left below right*/
606 ret_rightCornerWhere
= 2; /*on the right*/
607 ret_rightCornerIndex
= index2
;
613 tempMin
= rightChain
->getVertex(index2
)[0];
615 /*find the minimum u for all the points on the right above the left poitn index1*/
616 for(i
=index2
+1; i
<= rightChainEndIndex
; i
++)
618 if( rightChain
->getVertex(i
)[1] < leftChain
->getVertex(index1
)[1])
620 if(rightChain
->getVertex(i
)[0] < tempMin
)
623 tempMin
= rightChain
->getVertex(i
)[0];
627 //we consider if we can use leftchain(index1) as left corner.
628 //we check if (leftChain(index1) intersects right chian or not
629 if(DBG_intersectChain(rightChain
, rightChainStartIndex
, rightChainEndIndex
, leftGridPoint
, leftChain
->getVertex(index1
)))
631 ret_leftCornerWhere
= 2;
632 ret_leftCornerIndex
= index2
; //should use tempI???
634 else if(tempMin
<= leftChain
->getVertex(index1
)[0] ||
637 ret_leftCornerWhere
= 2; /* on right chain*/
638 ret_leftCornerIndex
= tempI
;
642 ret_leftCornerWhere
= 0; /*on left chain*/
643 ret_leftCornerIndex
= index1
;
651 void findUpCorners(Real
*topVertex
,
652 vertexArray
*leftChain
, Int leftChainStartIndex
, Int leftChainEndIndex
,
653 vertexArray
*rightChain
, Int rightChainStartIndex
, Int rightChainEndIndex
,
657 Int
& ret_leftCornerWhere
, /*0: left chain, 1: topvertex, 2: rightchain*/
658 Int
& ret_leftCornerIndex
, /*useful when ret_leftCornerWhere == 0 or 2*/
659 Int
& ret_rightCornerWhere
, /*0: left chain, 1: topvertex, 2: rightchain*/
660 Int
& ret_rightCornerIndex
/*useful when ret_leftCornerWhere == 0 or 2*/
664 printf("***********enter findUpCorners\n");
667 assert(v
< topVertex
[1]);
668 Real leftGridPoint
[2];
669 leftGridPoint
[0] = uleft
;
670 leftGridPoint
[1] = v
;
671 Real rightGridPoint
[2];
672 rightGridPoint
[0] = uright
;
673 rightGridPoint
[1] = v
;
678 index1
= leftChain
->findIndexFirstAboveEqualGen(v
, leftChainStartIndex
, leftChainEndIndex
);
681 index2
= rightChain
->findIndexFirstAboveEqualGen(v
, rightChainStartIndex
, rightChainEndIndex
);
683 if(index2
>= leftChainStartIndex
) //index2 was found above
684 index2
= rightChain
->skipEqualityFromStart(v
, index2
, rightChainEndIndex
);
686 if(index1
<leftChainStartIndex
&& index2
<rightChainStartIndex
) /*no point above v on left chain or right chain*/
688 /*the topVertex is the only vertex above v*/
689 ret_leftCornerWhere
= 1;
690 ret_rightCornerWhere
= 1;
692 else if(index1
<leftChainStartIndex
) /*index2 >= rightChainStartIndex*/
694 ret_rightCornerWhere
= 2; /*on right chain*/
695 ret_rightCornerIndex
= index2
;
697 //find the minimum u on right top, either that, or top, or right[index2] is the left corner
698 Real tempMin
= rightChain
->getVertex(index2
)[0];
700 for(i
=index2
-1; i
>=rightChainStartIndex
; i
--)
701 if(rightChain
->getVertex(i
)[0] < tempMin
)
703 tempMin
= rightChain
->getVertex(i
)[0];
706 //chech whether (leftGridPoint, top) intersects rightchai,
707 //if yes, use right corner as left corner
708 //if not, use top or right[tempI] as left corner
709 if(DBG_intersectChain(rightChain
, rightChainStartIndex
, rightChainEndIndex
,
710 leftGridPoint
, topVertex
))
712 ret_leftCornerWhere
= 2; //rightChain
713 ret_leftCornerIndex
= index2
;
715 else if(topVertex
[0] < tempMin
)
716 ret_leftCornerWhere
= 1; /*topvertex*/
719 ret_leftCornerWhere
= 2; //right chain
720 ret_leftCornerIndex
= tempI
;
724 else if(index2
< rightChainStartIndex
) /*index1>=leftChainStartIndex*/
726 ret_leftCornerWhere
= 0; /*left chain*/
727 ret_leftCornerIndex
= index1
;
729 //find the maximum u on the left top section. either that or topvertex, or left[index1] is the right corner
730 Real tempMax
= leftChain
->getVertex(index1
)[0];
733 for(i
=index1
-1; i
>=leftChainStartIndex
; i
--){
735 if(leftChain
->getVertex(i
)[0] > tempMax
)
738 tempMax
= leftChain
->getVertex(i
)[0];
742 //check whether (rightGridPoint, top) intersects leftChain or not
743 //if yes, we use leftCorner as the right corner
744 //if not, we use either top or left[tempI] as the right corner
745 if(DBG_intersectChain(leftChain
, leftChainStartIndex
,leftChainEndIndex
,
746 rightGridPoint
, topVertex
))
748 ret_rightCornerWhere
= 0; //left chan
749 ret_rightCornerIndex
= index1
;
751 else if(topVertex
[0] > tempMax
)
752 ret_rightCornerWhere
= 1;//topVertex
755 ret_rightCornerWhere
= 0;//left chain
756 ret_rightCornerIndex
= tempI
;
759 else /*index1>=leftChainStartIndex and index2 >=rightChainStartIndex*/
761 if(leftChain
->getVertex(index1
)[1] <= rightChain
->getVertex(index2
)[1]) /*left point below right point*/
763 ret_leftCornerWhere
= 0; /*on left chain*/
764 ret_leftCornerIndex
= index1
;
770 tempMax
= leftChain
->getVertex(index1
)[0];
772 /*find the maximum u for all the points on the left below the right point index2*/
773 for(i
=index1
-1; i
>= leftChainStartIndex
; i
--)
775 if(leftChain
->getVertex(i
)[1] > rightChain
->getVertex(index2
)[1])
778 if(leftChain
->getVertex(i
)[0]>tempMax
)
781 tempMax
= leftChain
->getVertex(i
)[0];
784 //chek whether (rightChain(index2), rightGridPoint) intersects leftchian or not
785 if(DBG_intersectChain(leftChain
, leftChainStartIndex
, leftChainEndIndex
, rightGridPoint
, rightChain
->getVertex(index2
)))
787 ret_rightCornerWhere
= 0;
788 ret_rightCornerIndex
= index1
;
790 else if(tempMax
>= rightChain
->getVertex(index2
)[0] ||
793 ret_rightCornerWhere
= 0; /*on left Chain*/
794 ret_rightCornerIndex
= tempI
;
798 ret_rightCornerWhere
= 2; /*on right chain*/
799 ret_rightCornerIndex
= index2
;
802 else /*left above right*/
804 ret_rightCornerWhere
= 2; /*on the right*/
805 ret_rightCornerIndex
= index2
;
811 tempMin
= rightChain
->getVertex(index2
)[0];
813 /*find the minimum u for all the points on the right below the left poitn index1*/
814 for(i
=index2
-1; i
>= rightChainStartIndex
; i
--)
816 if( rightChain
->getVertex(i
)[1] > leftChain
->getVertex(index1
)[1])
818 if(rightChain
->getVertex(i
)[0] < tempMin
)
821 tempMin
= rightChain
->getVertex(i
)[0];
824 //check whether (leftGRidPoint,left(index1)) interesect right chain
825 if(DBG_intersectChain(rightChain
, rightChainStartIndex
, rightChainEndIndex
,
826 leftGridPoint
, leftChain
->getVertex(index1
)))
828 ret_leftCornerWhere
= 2; //right
829 ret_leftCornerIndex
= index2
;
831 else if(tempMin
<= leftChain
->getVertex(index1
)[0] ||
834 ret_leftCornerWhere
= 2; /* on right chain*/
835 ret_leftCornerIndex
= tempI
;
839 ret_leftCornerWhere
= 0; /*on left chain*/
840 ret_leftCornerIndex
= index1
;
845 printf("***********leave findUpCorners\n");
849 //return 1 if neck exists, 0 othewise
850 Int
findNeckF(vertexArray
*leftChain
, Int botLeftIndex
,
851 vertexArray
*rightChain
, Int botRightIndex
,
852 gridBoundaryChain
* leftGridChain
,
853 gridBoundaryChain
* rightGridChain
,
859 printf("enter findNeckF, botleft, botright=%i,%i,gstartindex=%i\n",botLeftIndex,botRightIndex,gridStartIndex);
860 printf("leftChain is\n");
862 printf("rightChain is\n");
866 Int lowerGridIndex
; //the grid below leftChain and rightChian vertices
868 Int n_vlines
= leftGridChain
->get_nVlines();
870 if(botLeftIndex
>= leftChain
->getNumElements() ||
871 botRightIndex
>= rightChain
->getNumElements())
872 return 0; //no neck exists
874 v
=min(leftChain
->getVertex(botLeftIndex
)[1], rightChain
->getVertex(botRightIndex
)[1]);
879 for(i
=gridStartIndex
; i
<n_vlines
; i
++)
880 if(leftGridChain
->get_v_value(i
) <= v
&&
881 leftGridChain
->getUlineIndex(i
)<= rightGridChain
->getUlineIndex(i
))
886 if(lowerGridIndex
== n_vlines
) //the two trm vertex are higher than all gridlines
890 Int botLeft2
, botRight2
;
892 printf("leftGridChain->get_v_)value=%f\n",leftGridChain->get_v_value(lowerGridIndex), botLeftIndex);
893 printf("leftChain->get_vertex(0)=(%f,%f)\n", leftChain->getVertex(0)[0],leftChain->getVertex(0)[1]);
894 printf("leftChain->get_vertex(1)=(%f,%f)\n", leftChain->getVertex(1)[0],leftChain->getVertex(1)[1]);
895 printf("leftChain->get_vertex(2)=(%f,%f)\n", leftChain->getVertex(2)[0],leftChain->getVertex(2)[1]);
897 botLeft2
= leftChain
->findIndexFirstAboveEqualGen(leftGridChain
->get_v_value(lowerGridIndex
), botLeftIndex
, leftChain
->getNumElements()-1) -1 ;
900 printf("botLeft2=%i\n", botLeft2);
901 printf("leftChain->getNumElements=%i\n", leftChain->getNumElements());
904 botRight2
= rightChain
->findIndexFirstAboveEqualGen(leftGridChain
->get_v_value(lowerGridIndex
), botRightIndex
, rightChain
->getNumElements()-1) -1;
905 if(botRight2
< botRightIndex
) botRight2
=botRightIndex
;
907 if(botLeft2
< botLeftIndex
) botLeft2
= botLeftIndex
;
909 assert(botLeft2
>= botLeftIndex
);
910 assert(botRight2
>= botRightIndex
);
911 //find nectLeft so that it is th erightmost vertex on letChain
913 Int tempI
= botLeftIndex
;
914 Real temp
= leftChain
->getVertex(tempI
)[0];
915 for(i
=botLeftIndex
+1; i
<= botLeft2
; i
++)
916 if(leftChain
->getVertex(i
)[0] > temp
)
918 temp
= leftChain
->getVertex(i
)[0];
923 tempI
= botRightIndex
;
924 temp
= rightChain
->getVertex(tempI
)[0];
925 for(i
=botRightIndex
+1; i
<= botRight2
; i
++)
926 if(rightChain
->getVertex(i
)[0] < temp
)
928 temp
= rightChain
->getVertex(i
)[0];
938 /*find i>=botLeftIndex,j>=botRightIndex so that
939 *(leftChain[i], rightChain[j]) is a neck.
941 void findNeck(vertexArray
*leftChain
, Int botLeftIndex
,
942 vertexArray
*rightChain
, Int botRightIndex
,
943 Int
& leftLastIndex
, /*left point of the neck*/
944 Int
& rightLastIndex
/*right point of the neck*/
947 assert(botLeftIndex
< leftChain
->getNumElements() &&
948 botRightIndex
< rightChain
->getNumElements());
950 /*now the neck exists for sure*/
952 if(leftChain
->getVertex(botLeftIndex
)[1] <= rightChain
->getVertex(botRightIndex
)[1]) //left below right
955 leftLastIndex
= botLeftIndex
;
957 /*find i so that rightChain[i][1] >= leftchainbotverte[1], and i+1<
959 rightLastIndex
=rightChain
->findIndexAboveGen(leftChain
->getVertex(botLeftIndex
)[1], botRightIndex
+1, rightChain
->getNumElements()-1);
961 else //left above right
964 rightLastIndex
= botRightIndex
;
966 leftLastIndex
= leftChain
->findIndexAboveGen(rightChain
->getVertex(botRightIndex
)[1],
968 leftChain
->getNumElements()-1);
974 void findLeftGridIndices(directedLine
* topEdge
, Int firstGridIndex
, Int lastGridIndex
, gridWrap
* grid
, Int
* ret_indices
, Int
* ret_innerIndices
)
978 Int n_ulines
= grid
->get_n_ulines();
979 Real uMin
= grid
->get_u_min();
980 Real uMax
= grid
->get_u_max();
982 Real vMin = grid->get_v_min();
983 Real vMax = grid->get_v_max();
985 Real slop
= 0.0, uinterc
;
987 #ifdef SHORTEN_GRID_LINE
988 //uintercBuf stores all the interction u value for each grid line
989 //notice that lastGridIndex<= firstGridIndex
990 Real
*uintercBuf
= (Real
*) malloc (sizeof(Real
) * (firstGridIndex
-lastGridIndex
+1));
994 /*initialization to make vtail bigger than grid->...*/
995 directedLine
* dLine
= topEdge
;
996 Real vtail
= grid
->get_v_value(firstGridIndex
) + 1.0;
997 Real tempMaxU
= grid
->get_u_min();
1000 /*for each grid line*/
1001 for(k
=0, i
=firstGridIndex
; i
>=lastGridIndex
; i
--, k
++)
1004 Real grid_v_value
= grid
->get_v_value(i
);
1006 /*check whether this grid line is below the current trim edge.*/
1007 if(vtail
> grid_v_value
)
1009 /*since the grid line is below the trim edge, we
1010 *find the trim edge which will contain the trim line
1012 while( (vtail
=dLine
->tail()[1]) > grid_v_value
){
1014 tempMaxU
= max(tempMaxU
, dLine
->tail()[0]);
1015 dLine
= dLine
-> getNext();
1018 if( fabs(dLine
->head()[1] - vtail
) < ZERO
)
1023 slop
= (dLine
->head()[0] - dLine
->tail()[0]) / (dLine
->head()[1]-vtail
);
1029 uinterc
= max(dLine
->head()[0], dLine
->tail()[0]);
1033 uinterc
= slop
* (grid_v_value
- vtail
) + dLine
->tail()[0];
1036 tempMaxU
= max(tempMaxU
, uinterc
);
1038 if(uinterc
< uMin
&& uinterc
>= uMin
- ZERO
)
1040 if(uinterc
> uMax
&& uinterc
<= uMax
+ ZERO
)
1043 #ifdef SHORTEN_GRID_LINE
1044 uintercBuf
[k
] = uinterc
;
1047 assert(uinterc
>= uMin
&& uinterc
<= uMax
);
1049 ret_indices
[k
] = n_ulines
-1;
1051 ret_indices
[k
] = (Int
)(((uinterc
-uMin
)/(uMax
- uMin
)) * (n_ulines
-1)) + 1;
1052 if(ret_indices
[k
] >= n_ulines
)
1053 ret_indices
[k
] = n_ulines
-1;
1056 ret_innerIndices
[k
] = (Int
)(((tempMaxU
-uMin
)/(uMax
- uMin
)) * (n_ulines
-1)) + 1;
1058 /*reinitialize tempMaxU for next grdiLine*/
1061 #ifdef SHORTEN_GRID_LINE
1062 //for each grid line, compare the left grid point with the
1063 //intersection point. If the two points are too close, then
1064 //we should move the grid point one grid to the right
1065 //and accordingly we should update the inner index.
1066 for(k
=0, i
=firstGridIndex
; i
>=lastGridIndex
; i
--, k
++)
1069 //check ret_indices[k]
1070 Real a
= grid
->get_u_value(ret_indices
[k
]-1);
1071 Real b
= grid
->get_u_value(ret_indices
[k
]);
1072 assert(uintercBuf
[k
] >= a
&& uintercBuf
< b
);
1073 if( (b
-uintercBuf
[k
]) <= 0.2 * (b
-a
)) //interc is very close to b
1078 //check ret_innerIndices[k]
1081 if(ret_innerIndices
[k
] < ret_indices
[k
-1])
1082 ret_innerIndices
[k
] = ret_indices
[k
-1];
1083 if(ret_innerIndices
[k
] < ret_indices
[k
])
1084 ret_innerIndices
[k
] = ret_indices
[k
];
1092 void findRightGridIndices(directedLine
* topEdge
, Int firstGridIndex
, Int lastGridIndex
, gridWrap
* grid
, Int
* ret_indices
, Int
* ret_innerIndices
)
1096 Int n_ulines
= grid
->get_n_ulines();
1097 Real uMin
= grid
->get_u_min();
1098 Real uMax
= grid
->get_u_max();
1100 Real vMin = grid->get_v_min();
1101 Real vMax = grid->get_v_max();
1103 Real slop
= 0.0, uinterc
;
1105 #ifdef SHORTEN_GRID_LINE
1106 //uintercBuf stores all the interction u value for each grid line
1107 //notice that firstGridIndex >= lastGridIndex
1108 Real
*uintercBuf
= (Real
*) malloc (sizeof(Real
) * (firstGridIndex
-lastGridIndex
+1));
1112 /*initialization to make vhead bigger than grid->v_value...*/
1113 directedLine
* dLine
= topEdge
->getPrev();
1114 Real vhead
= dLine
->tail()[1];
1115 Real tempMinU
= grid
->get_u_max();
1117 /*for each grid line*/
1118 for(k
=0, i
=firstGridIndex
; i
>=lastGridIndex
; i
--, k
++)
1121 Real grid_v_value
= grid
->get_v_value(i
);
1124 /*check whether this grid line is below the current trim edge.*/
1125 if(vhead
>= grid_v_value
)
1127 /*since the grid line is below the tail of the trim edge, we
1128 *find the trim edge which will contain the trim line
1130 while( (vhead
=dLine
->head()[1]) > grid_v_value
){
1131 tempMinU
= min(tempMinU
, dLine
->head()[0]);
1132 dLine
= dLine
-> getPrev();
1135 /*skip the equality in the case of degenerat case: horizontal */
1136 while(dLine
->head()[1] == grid_v_value
)
1137 dLine
= dLine
->getPrev();
1139 assert( dLine
->tail()[1] != dLine
->head()[1]);
1140 slop
= (dLine
->tail()[0] - dLine
->head()[0]) / (dLine
->tail()[1]-dLine
->head()[1]);
1142 if(dLine->tail()[1] == vhead)
1147 slop = (dLine->tail()[0] - dLine->head()[0]) / (dLine->tail()[1]-vhead);
1151 uinterc
= slop
* (grid_v_value
- dLine
->head()[1]) + dLine
->head()[0];
1153 //in case unterc is outside of the grid due to floating point
1156 else if(uinterc
> uMax
)
1159 #ifdef SHORTEN_GRID_LINE
1160 uintercBuf
[k
] = uinterc
;
1163 tempMinU
= min(tempMinU
, uinterc
);
1165 assert(uinterc
>= uMin
&& uinterc
<= uMax
);
1170 ret_indices
[k
] = (int)ceil((((uinterc
-uMin
)/(uMax
- uMin
)) * (n_ulines
-1))) -1;
1172 if(ret_indices[k] >= grid->get_n_ulines())
1177 if(ret_indices[k] < 0)
1183 ret_innerIndices
[k
] = (int)ceil ((((tempMinU
-uMin
)/(uMax
- uMin
)) * (n_ulines
-1))) -1;
1187 #ifdef SHORTEN_GRID_LINE
1188 //for each grid line, compare the left grid point with the
1189 //intersection point. If the two points are too close, then
1190 //we should move the grid point one grid to the right
1191 //and accordingly we should update the inner index.
1192 for(k
=0, i
=firstGridIndex
; i
>=lastGridIndex
; i
--, k
++)
1195 //check ret_indices[k]
1196 Real a
= grid
->get_u_value(ret_indices
[k
]);
1197 Real b
= grid
->get_u_value(ret_indices
[k
]+1);
1198 assert(uintercBuf
[k
] > a
&& uintercBuf
<= b
);
1199 if( (uintercBuf
[k
]-a
) <= 0.2 * (b
-a
)) //interc is very close to a
1204 //check ret_innerIndices[k]
1207 if(ret_innerIndices
[k
] > ret_indices
[k
-1])
1208 ret_innerIndices
[k
] = ret_indices
[k
-1];
1209 if(ret_innerIndices
[k
] > ret_indices
[k
])
1210 ret_innerIndices
[k
] = ret_indices
[k
];
1219 void sampleMonoPoly(directedLine
* polygon
, gridWrap
* grid
, Int ulinear
, Int vlinear
, primStream
* pStream
, rectBlockArray
* rbArray
)
1224 polygon->writeAllPolygons("zloutputFile");
1229 if(grid
->get_n_ulines() == 2 ||
1230 grid
->get_n_vlines() == 2)
1232 if(ulinear
&& grid
->get_n_ulines() == 2)
1234 monoTriangulationFun(polygon
, compV2InY
, pStream
);
1237 else if(DBG_isConvex(polygon
) && polygon
->numEdges() >=4)
1239 triangulateConvexPoly(polygon
, ulinear
, vlinear
, pStream
);
1242 else if(vlinear
|| DBG_is_U_direction(polygon
))
1244 Int n_cusps
;//num interior cusps
1245 Int n_edges
= polygon
->numEdges();
1246 directedLine
** cusps
= (directedLine
**) malloc(sizeof(directedLine
*) * n_edges
);
1248 findInteriorCuspsX(polygon
, n_cusps
, cusps
);
1250 if(n_cusps
== 0) //u_monotone
1253 monoTriangulationFun(polygon
, compV2InX
, pStream
);
1258 else if(n_cusps
== 1) //one interior cusp
1261 directedLine
* new_polygon
= polygonConvert(cusps
[0]);
1263 directedLine
* other
= findDiagonal_singleCuspX( new_polygon
);
1267 //<other> should NOT be null unless there are self-intersecting
1268 //trim curves. In that case, we don't want to core dump, instead,
1269 //we triangulate anyway, and print out error message.
1272 monoTriangulationFun(polygon
, compV2InX
, pStream
);
1277 directedLine
* ret_p1
;
1278 directedLine
* ret_p2
;
1280 new_polygon
->connectDiagonal_2slines(new_polygon
, other
,
1285 monoTriangulationFun(ret_p1
, compV2InX
, pStream
);
1286 monoTriangulationFun(ret_p2
, compV2InX
, pStream
);
1288 ret_p1
->deleteSinglePolygonWithSline();
1289 ret_p2
->deleteSinglePolygonWithSline();
1298 /*find the top and bottom of the polygon. It is supposed to be
1299 *a V-monotone polygon
1302 directedLine
* tempV
;
1305 topV
= botV
= polygon
;
1307 for(tempV
= polygon
->getNext(); tempV
!= polygon
; tempV
= tempV
->getNext())
1309 if(compV2InY(topV
->head(), tempV
->head())<0) {
1313 if(compV2InY(botV
->head(), tempV
->head())>0) {
1319 /*find the first(top) and the last (bottom) grid line which intersect the
1322 Int firstGridIndex
; /*the index in the grid*/
1324 firstGridIndex
= (Int
) ((topV
->head()[1] - grid
->get_v_min()) / (grid
->get_v_max() - grid
->get_v_min()) * (grid
->get_n_vlines()-1));
1325 lastGridIndex
= (Int
) ((botV
->head()[1] - grid
->get_v_min()) / (grid
->get_v_max() - grid
->get_v_min()) * (grid
->get_n_vlines()-1)) + 1;
1328 /*find the interval inside the polygon for each gridline*/
1329 Int
*leftGridIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
1330 assert(leftGridIndices
);
1331 Int
*rightGridIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
1332 assert(rightGridIndices
);
1333 Int
*leftGridInnerIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
1334 assert(leftGridInnerIndices
);
1335 Int
*rightGridInnerIndices
= (Int
*) malloc(sizeof(Int
) * (firstGridIndex
- lastGridIndex
+1));
1336 assert(rightGridInnerIndices
);
1338 findLeftGridIndices(topV
, firstGridIndex
, lastGridIndex
, grid
, leftGridIndices
, leftGridInnerIndices
);
1340 findRightGridIndices(topV
, firstGridIndex
, lastGridIndex
, grid
, rightGridIndices
, rightGridInnerIndices
);
1342 gridBoundaryChain
leftGridChain(grid
, firstGridIndex
, firstGridIndex
-lastGridIndex
+1, leftGridIndices
, leftGridInnerIndices
);
1344 gridBoundaryChain
rightGridChain(grid
, firstGridIndex
, firstGridIndex
-lastGridIndex
+1, rightGridIndices
, rightGridInnerIndices
);
1348 // leftGridChain.draw();
1349 // leftGridChain.drawInner();
1350 // rightGridChain.draw();
1351 // rightGridChain.drawInner();
1352 /*(1) determine the grid boundaries (left and right).
1353 *(2) process polygon into two monotone chaines: use vertexArray
1354 *(3) call sampleMonoPolyRec
1357 /*copy the two chains into vertexArray datastructure*/
1359 vertexArray
leftChain(20); /*this is a dynamic array*/
1360 for(i
=1; i
<=topV
->get_npoints()-2; i
++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
1361 leftChain
.appendVertex(topV
->getVertex(i
));
1363 for(tempV
= topV
->getNext(); tempV
!= botV
; tempV
= tempV
->getNext())
1365 for(i
=0; i
<=tempV
->get_npoints()-2; i
++){
1366 leftChain
.appendVertex(tempV
->getVertex(i
));
1370 vertexArray
rightChain(20);
1371 for(tempV
= topV
->getPrev(); tempV
!= botV
; tempV
= tempV
->getPrev())
1373 for(i
=tempV
->get_npoints()-2; i
>=0; i
--){
1374 rightChain
.appendVertex(tempV
->getVertex(i
));
1377 for(i
=botV
->get_npoints()-2; i
>=1; i
--){
1378 rightChain
.appendVertex(tempV
->getVertex(i
));
1381 sampleMonoPolyRec(topV
->head(),
1395 free(leftGridIndices
);
1396 free(rightGridIndices
);
1397 free(leftGridInnerIndices
);
1398 free(rightGridInnerIndices
);
1401 void sampleMonoPolyRec(
1404 vertexArray
* leftChain
,
1406 vertexArray
* rightChain
,
1407 Int rightStartIndex
,
1408 gridBoundaryChain
* leftGridChain
,
1409 gridBoundaryChain
* rightGridChain
,
1411 primStream
* pStream
,
1412 rectBlockArray
* rbArray
)
1415 /*find the first connected component, and the four corners.
1417 Int index1
, index2
; /*the first and last grid line of the first connected component*/
1419 if(topVertex
[1] <= botVertex
[1])
1422 /*find i so that the grid line is below the top vertex*/
1423 Int i
=gridStartIndex
;
1424 while (i
< leftGridChain
->get_nVlines())
1426 if(leftGridChain
->get_v_value(i
) < topVertex
[1])
1431 /*find the first connected component starting with i*/
1432 /*find index1 so that left_uline_index <= right_uline_index, that is, this
1433 *grid line contains at least one inner grid point
1436 int num_skipped_grid_lines
=0;
1437 while(index1
< leftGridChain
->get_nVlines())
1439 if(leftGridChain
->getUlineIndex(index1
) <= rightGridChain
->getUlineIndex(index1
))
1441 num_skipped_grid_lines
++;
1447 if(index1
>= leftGridChain
->get_nVlines()) /*no grid line exists which has inner point*/
1449 /*stop recursion, ...*/
1450 /*monotone triangulate it...*/
1451 // printf("no grid line exists\n");
1453 monoTriangulationRecOpt(topVertex, botVertex, leftChain, leftStartIndex,
1454 rightChain, rightStartIndex, pStream);
1457 if(num_skipped_grid_lines
<2)
1459 monoTriangulationRecGenOpt(topVertex
, botVertex
, leftChain
, leftStartIndex
,
1460 leftChain
->getNumElements()-1,
1461 rightChain
, rightStartIndex
,
1462 rightChain
->getNumElements()-1,
1467 //the optimum way to triangulate is top-down since this polygon
1469 monoTriangulationRec(topVertex
, botVertex
, leftChain
, leftStartIndex
,
1470 rightChain
, rightStartIndex
, pStream
);
1474 monoTriangulationRec(topVertex, botVertex, leftChain, leftStartIndex,
1475 rightChain, rightStartIndex, pStream);
1478 /* monoTriangulationRecGenTBOpt(topVertex, botVertex,
1479 leftChain, leftStartIndex, leftChain->getNumElements()-1,
1480 rightChain, rightStartIndex, rightChain->getNumElements()-1,
1489 /*find index2 so that left_inner_index <= right_inner_index holds until index2*/
1491 if(index2
< leftGridChain
->get_nVlines())
1492 while(leftGridChain
->getInnerIndex(index2
) <= rightGridChain
->getInnerIndex(index2
))
1495 if(index2
>= leftGridChain
->get_nVlines())
1507 /*the four corners*/
1508 Int up_leftCornerWhere
;
1509 Int up_leftCornerIndex
;
1510 Int up_rightCornerWhere
;
1511 Int up_rightCornerIndex
;
1512 Int down_leftCornerWhere
;
1513 Int down_leftCornerIndex
;
1514 Int down_rightCornerWhere
;
1515 Int down_rightCornerIndex
;
1517 Real
* tempBotVertex
; /*the bottom vertex for this component*/
1518 Real
* nextTopVertex
=NULL
; /*for the recursion*/
1519 Int nextLeftStartIndex
=0;
1520 Int nextRightStartIndex
=0;
1522 /*find the points below the grid line index2 on both chains*/
1523 Int botLeftIndex
= leftChain
->findIndexStrictBelowGen(
1524 leftGridChain
->get_v_value(index2
),
1526 leftChain
->getNumElements()-1);
1527 Int botRightIndex
= rightChain
->findIndexStrictBelowGen(
1528 rightGridChain
->get_v_value(index2
),
1530 rightChain
->getNumElements()-1);
1531 /*if either botLeftIndex>= numelements,
1532 * or botRightIndex >= numelemnet,
1533 *then there is no neck exists. the bottom vertex is botVertex,
1535 if(! findNeckF(leftChain
, botLeftIndex
, rightChain
, botRightIndex
,
1536 leftGridChain
, rightGridChain
, index2
, neckLeftIndex
, neckRightIndex
))
1538 if(botLeftIndex == leftChain->getNumElements() ||
1539 botRightIndex == rightChain->getNumElements())
1543 printf("neck NOT exists, botRightIndex=%i\n", botRightIndex
);
1546 tempBotVertex
= botVertex
;
1547 nextTopVertex
= botVertex
;
1548 botLeftIndex
= leftChain
->getNumElements()-1;
1549 botRightIndex
= rightChain
->getNumElements()-1;
1551 else /*neck exists*/
1554 printf("neck exists\n");
1558 findNeck(leftChain, botLeftIndex,
1559 rightChain, botRightIndex,
1564 printf("neck is found, neckLeftIndex=%i, neckRightIndex=%i\n", neckLeftIndex
, neckRightIndex
);
1566 glVertex2fv(leftChain
->getVertex(neckLeftIndex
));
1567 glVertex2fv(rightChain
->getVertex(neckRightIndex
));
1571 if(leftChain
->getVertex(neckLeftIndex
)[1] <= rightChain
->getVertex(neckRightIndex
)[1])
1573 tempBotVertex
= leftChain
->getVertex(neckLeftIndex
);
1574 botLeftIndex
= neckLeftIndex
-1;
1575 botRightIndex
= neckRightIndex
;
1576 nextTopVertex
= rightChain
->getVertex(neckRightIndex
);
1577 nextLeftStartIndex
= neckLeftIndex
;
1578 nextRightStartIndex
= neckRightIndex
+1;
1582 tempBotVertex
= rightChain
->getVertex(neckRightIndex
);
1583 botLeftIndex
= neckLeftIndex
;
1584 botRightIndex
= neckRightIndex
-1;
1585 nextTopVertex
= leftChain
->getVertex(neckLeftIndex
);
1586 nextLeftStartIndex
= neckLeftIndex
+1;
1587 nextRightStartIndex
= neckRightIndex
;
1591 findUpCorners(topVertex
,
1593 leftStartIndex
, botLeftIndex
,
1595 rightStartIndex
, botRightIndex
,
1596 leftGridChain
->get_v_value(index1
),
1597 leftGridChain
->get_u_value(index1
),
1598 rightGridChain
->get_u_value(index1
),
1601 up_rightCornerWhere
,
1602 up_rightCornerIndex
);
1604 findDownCorners(tempBotVertex
,
1606 leftStartIndex
, botLeftIndex
,
1608 rightStartIndex
, botRightIndex
,
1609 leftGridChain
->get_v_value(index2
),
1610 leftGridChain
->get_u_value(index2
),
1611 rightGridChain
->get_u_value(index2
),
1612 down_leftCornerWhere
,
1613 down_leftCornerIndex
,
1614 down_rightCornerWhere
,
1615 down_rightCornerIndex
);
1617 printf("find corners done, down_leftwhere=%i, down_righwhere=%i,\n",down_leftCornerWhere
, down_rightCornerWhere
);
1618 printf("find corners done, up_leftwhere=%i, up_righwhere=%i,\n",up_leftCornerWhere
, up_rightCornerWhere
);
1619 printf("find corners done, up_leftindex=%i, up_righindex=%i,\n",up_leftCornerIndex
, up_rightCornerIndex
);
1620 printf("find corners done, down_leftindex=%i, down_righindex=%i,\n",down_leftCornerIndex
, down_rightCornerIndex
);
1624 drawCorners(topVertex,
1634 up_rightCornerWhere,
1635 up_rightCornerIndex,
1636 down_leftCornerWhere,
1637 down_leftCornerIndex,
1638 down_rightCornerWhere,
1639 down_rightCornerIndex);
1643 sampleConnectedComp(topVertex
, tempBotVertex
,
1645 leftStartIndex
, botLeftIndex
,
1647 rightStartIndex
, botRightIndex
,
1653 up_rightCornerWhere
,
1654 up_rightCornerIndex
,
1655 down_leftCornerWhere
,
1656 down_leftCornerIndex
,
1657 down_rightCornerWhere
,
1658 down_rightCornerIndex
,
1671 nextRightStartIndex
,
1682 void sampleLeftStrip(vertexArray
* leftChain
,
1685 gridBoundaryChain
* leftGridChain
,
1686 Int leftGridChainStartIndex
,
1687 Int leftGridChainEndIndex
,
1691 assert(leftChain
->getVertex(topLeftIndex
)[1] > leftGridChain
->get_v_value(leftGridChainStartIndex
));
1692 assert(leftChain
->getVertex(topLeftIndex
+1)[1] <= leftGridChain
->get_v_value(leftGridChainStartIndex
));
1693 assert(leftChain
->getVertex(botLeftIndex
)[1] <= leftGridChain
->get_v_value(leftGridChainEndIndex
));
1694 assert(leftChain
->getVertex(botLeftIndex
-1)[1] > leftGridChain
->get_v_value(leftGridChainEndIndex
));
1697 *(1)find the last grid line which doesn'; pass below
1698 * this first edge, sample this region: one trim edge and
1699 * possily multiple grid lines.
1701 Real
*upperVert
, *lowerVert
; /*the end points of the first trim edge*/
1702 upperVert
= leftChain
->getVertex(topLeftIndex
);
1703 lowerVert
= leftChain
->getVertex(topLeftIndex
+1);
1705 Int index
= leftGridChainStartIndex
;
1706 while(leftGridChain
->get_v_value(index
) >= lowerVert
[1]){
1708 if(index
> leftGridChainEndIndex
)
1713 sampleLeftSingleTrimEdgeRegion(upperVert
, lowerVert
,
1715 leftGridChainStartIndex
,
1718 sampleLeftStripRec(leftChain
, topLeftIndex
+1, botLeftIndex
,
1719 leftGridChain
, index
, leftGridChainEndIndex
,
1724 void sampleLeftStripRec(vertexArray
* leftChain
,
1727 gridBoundaryChain
* leftGridChain
,
1728 Int leftGridChainStartIndex
,
1729 Int leftGridChainEndIndex
,
1733 /*now top left trim vertex is below the top grid line.
1735 /*stop condition: if topLeftIndex >= botLeftIndex, then stop.
1737 if(topLeftIndex
>= botLeftIndex
)
1740 /*find the last trim vertex which is above the second top grid line:
1742 *and sampleLeftOneGridStep(leftchain, topLeftIndex, index1, leftGridChain,
1743 * leftGridChainStartIndex).
1744 * index1 could be equal to topLeftIndex.
1746 Real secondGridChainV
= leftGridChain
->get_v_value(leftGridChainStartIndex
+1);
1747 assert(leftGridChainStartIndex
< leftGridChainEndIndex
);
1748 Int index1
= topLeftIndex
;
1749 while(leftChain
->getVertex(index1
)[1] > secondGridChainV
)
1753 sampleLeftOneGridStep(leftChain
, topLeftIndex
, index1
, leftGridChain
, leftGridChainStartIndex
, pStream
);
1757 * Let the next trim vertex be nextTrimVertIndex (which should be
1758 * below the second grid line).
1759 * Find the last grid line index2 which is above nextTrimVert.
1760 * sampleLeftSingleTrimEdgeRegion(uppervert[2], lowervert[2],
1761 * leftGridChain, leftGridChainStartIndex+1, index2).
1763 Real
*uppervert
, *lowervert
;
1764 uppervert
= leftChain
->getVertex(index1
);
1765 lowervert
= leftChain
->getVertex(index1
+1);
1766 Int index2
= leftGridChainStartIndex
+1;
1768 while(leftGridChain
->get_v_value(index2
) >= lowervert
[1])
1771 if(index2
> leftGridChainEndIndex
)
1775 sampleLeftSingleTrimEdgeRegion(uppervert
, lowervert
, leftGridChain
, leftGridChainStartIndex
+1, index2
, pStream
);
1777 /* sampleLeftStripRec(leftChain,
1782 leftGridChainEndIndex
1786 sampleLeftStripRec(leftChain
, index1
+1, botLeftIndex
, leftGridChain
, index2
, leftGridChainEndIndex
, pStream
);
1791 /***************begin RecF***********************/
1792 /* the gridlines from leftGridChainStartIndex to
1793 * leftGridChainEndIndex are assumed to form a
1794 * connected component.
1795 * the trim vertex of topLeftIndex is assumed to
1796 * be below the first gridline, and the tim vertex
1797 * of botLeftIndex is assumed to be above the last
1799 * If botLeftIndex < topLeftIndex, then no connected componeent exists, and this funcion returns without
1800 * outputing any triangles.
1801 * Otherwise botLeftIndex >= topLeftIndex, there is at least one triangle to output.
1803 void sampleLeftStripRecF(vertexArray
* leftChain
,
1806 gridBoundaryChain
* leftGridChain
,
1807 Int leftGridChainStartIndex
,
1808 Int leftGridChainEndIndex
,
1812 /*now top left trim vertex is below the top grid line.
1814 /*stop condition: if topLeftIndex > botLeftIndex, then stop.
1816 if(topLeftIndex
> botLeftIndex
)
1819 /*if there is only one grid Line, return.*/
1821 if(leftGridChainStartIndex
>=leftGridChainEndIndex
)
1825 assert(leftChain
->getVertex(topLeftIndex
)[1] <= leftGridChain
->get_v_value(leftGridChainStartIndex
) &&
1826 leftChain
->getVertex(botLeftIndex
)[1] >= leftGridChain
->get_v_value(leftGridChainEndIndex
));
1828 /*firs find the first trim vertex which is below or equal to the second top grid line:
1831 Real secondGridChainV
= leftGridChain
->get_v_value(leftGridChainStartIndex
+1);
1834 Int index1
= topLeftIndex
;
1836 while(leftChain
->getVertex(index1
)[1] > secondGridChainV
){
1838 if(index1
>botLeftIndex
)
1842 /*now leftChain->getVertex(index-1)[1] > secondGridChainV and
1843 * leftChain->getVertex(index)[1] <= secondGridChainV
1844 *If equality holds, then we should include the vertex index1, otherwise we include only index1-1, to
1845 *perform sampleOneGridStep.
1847 if(index1
>botLeftIndex
)
1849 else if(leftChain
->getVertex(index1
)[1] < secondGridChainV
)
1852 /*now we have leftChain->getVertex(index1)[1] >= secondGridChainV, and
1853 * leftChain->getVertex(index1+1)[1] <= secondGridChainV
1857 sampleLeftOneGridStep(leftChain
, topLeftIndex
, index1
, leftGridChain
, leftGridChainStartIndex
, pStream
);
1860 /*if leftChain->getVertex(index1)[1] == secondGridChainV, then we can recursively do the rest.
1862 if(leftChain
->getVertex(index1
)[1] == secondGridChainV
)
1865 sampleLeftStripRecF(leftChain
, index1
, botLeftIndex
,leftGridChain
, leftGridChainStartIndex
+1, leftGridChainEndIndex
, pStream
);
1867 else if(index1
< botLeftIndex
)
1870 /* Otherwise, we have leftChain->getVertex(index1)[1] > secondGridChainV,
1871 * let the next trim vertex be nextTrimVertIndex (which should be strictly
1872 * below the second grid line).
1873 * Find the last grid line index2 which is above nextTrimVert.
1874 * sampleLeftSingleTrimEdgeRegion(uppervert[2], lowervert[2],
1875 * leftGridChain, leftGridChainStartIndex+1, index2).
1877 Real
*uppervert
, *lowervert
;
1878 uppervert
= leftChain
->getVertex(index1
);
1879 lowervert
= leftChain
->getVertex(index1
+1); //okay since index1<botLeftIndex
1880 Int index2
= leftGridChainStartIndex
+1;
1883 while(leftGridChain
->get_v_value(index2
) >= lowervert
[1])
1886 if(index2
> leftGridChainEndIndex
)
1892 sampleLeftSingleTrimEdgeRegion(uppervert
, lowervert
, leftGridChain
, leftGridChainStartIndex
+1, index2
, pStream
);
1896 sampleLeftStripRecF(leftChain
, index1
+1, botLeftIndex
, leftGridChain
, index2
, leftGridChainEndIndex
, pStream
);
1901 /***************End RecF***********************/
1903 /*sample the left area in between one trim edge and multiple grid lines.
1904 * all the grid lines should be in between the two end poins of the
1907 void sampleLeftSingleTrimEdgeRegion(Real upperVert
[2], Real lowerVert
[2],
1908 gridBoundaryChain
* gridChain
,
1911 primStream
* pStream
)
1915 vertexArray
vArray(endIndex
-beginIndex
+1);
1916 vArray
.appendVertex(gridChain
->get_vertex(beginIndex
));
1918 for(k
=1, i
=beginIndex
+1; i
<=endIndex
; i
++, k
++)
1920 vArray
.appendVertex(gridChain
->get_vertex(i
));
1922 /*output the fan of the grid points of the (i)th and (i-1)th grid line.
1924 if(gridChain
->getUlineIndex(i
) < gridChain
->getUlineIndex(i
-1))
1927 pStream
->insert(gridChain
->get_vertex(i
-1));
1928 for(j
=gridChain
->getUlineIndex(i
); j
<= gridChain
->getUlineIndex(i
-1); j
++)
1929 pStream
->insert(gridChain
->getGrid()->get_u_value(j
), gridChain
->get_v_value(i
));
1930 pStream
->end(PRIMITIVE_STREAM_FAN
);
1932 else if(gridChain
->getUlineIndex(i
) > gridChain
->getUlineIndex(i
-1))
1935 pStream
->insert(gridChain
->get_vertex(i
));
1936 for(j
=gridChain
->getUlineIndex(i
); j
>= gridChain
->getUlineIndex(i
-1); j
--)
1937 pStream
->insert(gridChain
->getGrid()->get_u_value(j
), gridChain
->get_v_value(i
-1));
1938 pStream
->end(PRIMITIVE_STREAM_FAN
);
1940 /*otherwisem, the two are equal, so there is no fan to outout*/
1943 monoTriangulation2(upperVert
, lowerVert
, &vArray
, 0, endIndex
-beginIndex
,
1944 0, /*decreasing chain*/
1948 /*return i, such that from begin to i-1 the chain is strictly u-monotone.
1950 Int
findIncreaseChainFromBegin(vertexArray
* chain
, Int begin
,Int end
)
1953 Real prevU
= chain
->getVertex(i
)[0];
1955 for(i
=begin
+1; i
<=end
; i
++){
1956 thisU
= chain
->getVertex(i
)[0];
1967 /*check whether there is a vertex whose v value is strictly
1968 *inbetween vup vbelow
1969 *if no middle exists return -1, else return the idnex.
1971 Int
checkMiddle(vertexArray
* chain
, Int begin
, Int end
,
1972 Real vup
, Real vbelow
)
1975 for(i
=begin
; i
<=end
; i
++)
1977 if(chain
->getVertex(i
)[1] < vup
&& chain
->getVertex(i
)[1]>vbelow
)
1983 /*the degenerat case of sampleLeftOneGridStep*/
1984 void sampleLeftOneGridStepNoMiddle(vertexArray
* leftChain
,
1987 gridBoundaryChain
* leftGridChain
,
1988 Int leftGridChainStartIndex
,
1989 primStream
* pStream
)
1991 /*since there is no middle, there is at most one point which is on the
1992 *second grid line, there could be multiple points on the first (top)
1996 leftGridChain
->leftEndFan(leftGridChainStartIndex
+1, pStream
);
1998 monoTriangulation2(leftGridChain
->get_vertex(leftGridChainStartIndex
),
1999 leftGridChain
->get_vertex(leftGridChainStartIndex
+1),
2003 1, //is increase chain.
2009 /*sampling the left area in between two grid lines.
2011 void sampleLeftOneGridStep(vertexArray
* leftChain
,
2014 gridBoundaryChain
* leftGridChain
,
2015 Int leftGridChainStartIndex
,
2019 if(checkMiddle(leftChain
, beginLeftIndex
, endLeftIndex
,
2020 leftGridChain
->get_v_value(leftGridChainStartIndex
),
2021 leftGridChain
->get_v_value(leftGridChainStartIndex
+1))<0)
2025 sampleLeftOneGridStepNoMiddle(leftChain
, beginLeftIndex
, endLeftIndex
, leftGridChain
, leftGridChainStartIndex
, pStream
);
2029 //copy into a polygon
2031 directedLine
* poly
= NULL
;
2033 directedLine
* dline
;
2034 gridWrap
* grid
= leftGridChain
->getGrid();
2039 Int innerInd
= leftGridChain
->getInnerIndex(leftGridChainStartIndex
+1);
2040 Int upperInd
= leftGridChain
->getUlineIndex(leftGridChainStartIndex
);
2041 Int lowerInd
= leftGridChain
->getUlineIndex(leftGridChainStartIndex
+1);
2042 Real upperV
= leftGridChain
->get_v_value(leftGridChainStartIndex
);
2043 Real lowerV
= leftGridChain
->get_v_value(leftGridChainStartIndex
+1);
2045 //the upper gridline
2046 vert1
[1] = vert2
[1] = upperV
;
2047 for(i
=innerInd
; i
>upperInd
; i
--)
2049 vert1
[0]=grid
->get_u_value(i
);
2050 vert2
[0]=grid
->get_u_value(i
-1);
2051 sline
= new sampledLine(vert1
, vert2
);
2052 dline
= new directedLine(INCREASING
, sline
);
2056 poly
->insert(dline
);
2059 //the edge connecting upper grid with left chain
2060 vert1
[0] = grid
->get_u_value(upperInd
);
2062 sline
= new sampledLine(vert1
, leftChain
->getVertex(beginLeftIndex
));
2063 dline
= new directedLine(INCREASING
, sline
);
2067 poly
->insert(dline
);
2070 for(i
=beginLeftIndex
; i
<endLeftIndex
; i
++)
2072 sline
= new sampledLine(leftChain
->getVertex(i
), leftChain
->getVertex(i
+1));
2073 dline
= new directedLine(INCREASING
, sline
);
2074 poly
->insert(dline
);
2077 //the edge connecting left chain with lower gridline
2078 vert2
[0] = grid
->get_u_value(lowerInd
);
2080 sline
= new sampledLine(leftChain
->getVertex(endLeftIndex
), vert2
);
2081 dline
= new directedLine(INCREASING
, sline
);
2082 poly
->insert(dline
);
2084 //the lower grid line
2085 vert1
[1] = vert2
[1] = lowerV
;
2086 for(i
=lowerInd
; i
<innerInd
; i
++)
2088 vert1
[0] = grid
->get_u_value(i
);
2089 vert2
[0] = grid
->get_u_value(i
+1);
2090 sline
= new sampledLine(vert1
, vert2
);
2091 dline
= new directedLine(INCREASING
, sline
);
2092 poly
->insert(dline
);
2095 //the vertical grid line segement
2096 vert1
[0]=vert2
[0] = grid
->get_u_value(innerInd
);
2099 sline
=new sampledLine(vert1
, vert2
);
2100 dline
=new directedLine(INCREASING
, sline
);
2101 poly
->insert(dline
);
2102 monoTriangulationOpt(poly
, pStream
);
2104 poly
->deleteSinglePolygonWithSline();
2113 if(1/*leftGridChain->getUlineIndex(leftGridChainStartIndex) >=
2114 leftGridChain->getUlineIndex(leftGridChainStartIndex+1)*/
2115 ) /*the second grid line is beyond the first one to the left*/
2117 /*find the maximal U-monotone chain
2118 * of endLeftIndex, endLeftIndex-1, ...,
2121 Real prevU
= leftChain
->getVertex(i
)[0];
2122 for(i
=endLeftIndex
-1; i
>=beginLeftIndex
; i
--){
2123 Real thisU
= leftChain
->getVertex(i
)[0];
2130 /*from endLeftIndex to i+1 is strictly U- monotone */
2131 /*if i+1==endLeftIndex and the vertex and leftchain is on the second gridline, then
2132 *we should use 2 vertices on the leftchain. If we only use one (endLeftIndex), then we
2133 *we would output degenerate triangles
2135 if(i
+1 == endLeftIndex
&& leftChain
->getVertex(endLeftIndex
)[1] == leftGridChain
->get_v_value(1+leftGridChainStartIndex
))
2138 Int j
= beginLeftIndex
/*endLeftIndex*/+1;
2141 if(leftGridChain
->getInnerIndex(leftGridChainStartIndex
+1) > leftGridChain
->getUlineIndex(leftGridChainStartIndex
))
2143 j
= findIncreaseChainFromBegin(leftChain
, beginLeftIndex
, i
+1/*endLeftIndex*/);
2145 Int temp
= beginLeftIndex
;
2146 /*now from begin to j-1 is strictly u-monotone*/
2147 /*if j-1 is on the first grid line, then we want to skip to the vertex which is strictly
2148 *below the grid line. This vertexmust exist since there is a 'corner turn' inbetween the two grid lines
2150 if(j
-1 == beginLeftIndex
)
2152 while(leftChain
->getVertex(j
-1)[1] == leftGridChain
->get_v_value(leftGridChainStartIndex
))
2156 vert
[0] = leftGridChain
->get_u_value(leftGridChainStartIndex
);
2157 vert
[1] = leftGridChain
->get_v_value(leftGridChainStartIndex
);
2160 vert
/*leftChain->getVertex(beginLeftIndex)*/,
2161 leftChain
->getVertex(j
-1),
2166 pStream
//increase chain
2172 stripOfFanLeft(leftChain
, j
-1, temp
/*beginLeftIndex*/, leftGridChain
->getGrid(),
2173 leftGridChain
->getVlineIndex(leftGridChainStartIndex
),
2174 leftGridChain
->getUlineIndex(leftGridChainStartIndex
),
2175 leftGridChain
->getInnerIndex(leftGridChainStartIndex
+1),
2177 1 /*the grid line is above the trim line*/
2181 stripOfFanLeft(leftChain
, endLeftIndex
, i
+1, leftGridChain
->getGrid(),
2182 leftGridChain
->getVlineIndex(leftGridChainStartIndex
+1),
2183 leftGridChain
->getUlineIndex(leftGridChainStartIndex
+1),
2184 leftGridChain
->getInnerIndex(leftGridChainStartIndex
+1),
2186 0 /*the grid line is below the trim lines*/
2189 /*monotone triangulate the remaining left chain togther with the
2190 *two vertices on the two grid v-lines.
2193 vert
[0][0]=vert
[1][0] = leftGridChain
->getInner_u_value(leftGridChainStartIndex
+1);
2194 vert
[0][1] = leftGridChain
->get_v_value(leftGridChainStartIndex
);
2195 vert
[1][1] = leftGridChain
->get_v_value(leftGridChainStartIndex
+1);
2197 // vertexArray right(vert, 2);
2200 &vert
[0][0], /*top vertex */
2201 &vert
[1][0], /*bottom vertex*/
2203 /*beginLeftIndex*/j
-1,
2205 1, /*an increasing chain*/
2208 else /*the second one is shorter than the first one to the left*/
2210 /*find the maximal U-monotone chain of beginLeftIndex, beginLeftIndex+1,...,
2213 Real prevU
= leftChain
->getVertex(i
)[0];
2214 for(i
=beginLeftIndex
+1; i
<=endLeftIndex
; i
++){
2215 Real thisU
= leftChain
->getVertex(i
)[0];
2223 /*from beginLeftIndex to i-1 is strictly U-monotone*/
2226 stripOfFanLeft(leftChain
, i
-1, beginLeftIndex
, leftGridChain
->getGrid(),
2227 leftGridChain
->getVlineIndex(leftGridChainStartIndex
),
2228 leftGridChain
->getUlineIndex(leftGridChainStartIndex
),
2229 leftGridChain
->getUlineIndex(leftGridChainStartIndex
+1),
2231 1 /*the grid line is above the trim lines*/
2233 /*monotone triangulate the remaining left chain together with the
2234 *two vertices on the two grid v-lines.
2237 vert
[0][0]=vert
[1][0] = leftGridChain
->get_u_value(leftGridChainStartIndex
+1);
2238 vert
[0][1] = leftGridChain
->get_v_value(leftGridChainStartIndex
);
2239 vert
[1][1] = leftGridChain
->get_v_value(leftGridChainStartIndex
+1);
2241 vertexArray
right(vert
, 2);
2244 &vert
[0][0], //top vertex
2245 &vert
[1][0], //bottom vertex
2249 1, /*an increase chain*/
2258 void triangulateXYMono(Int n_upper
, Real upperVerts
[][2],
2259 Int n_lower
, Real lowerVerts
[][2],
2260 primStream
* pStream
)
2265 assert(n_upper
>=1 && n_lower
>=1);
2266 if(upperVerts
[0][0] <= lowerVerts
[0][0])
2270 leftMostV
= upperVerts
[0];
2276 leftMostV
= lowerVerts
[0];
2281 if(i
>= n_upper
) /*case1: no more in upper*/
2284 if(j
<n_lower
-1) /*at least two vertices in lower*/
2287 pStream
->insert(leftMostV
);
2289 pStream
->insert(lowerVerts
[j
]);
2292 pStream
->end(PRIMITIVE_STREAM_FAN
);
2297 else if(j
>= n_lower
) /*case2: no more in lower*/
2300 if(i
<n_upper
-1) /*at least two vertices in upper*/
2303 pStream
->insert(leftMostV
);
2305 for(k
=n_upper
-1; k
>=i
; k
--)
2306 pStream
->insert(upperVerts
[k
]);
2308 pStream
->end(PRIMITIVE_STREAM_FAN
);
2313 else /* case3: neither is empty, plus the leftMostV, there is at least one triangle to output*/
2316 if(upperVerts
[i
][0] <= lowerVerts
[j
][0])
2319 pStream
->insert(lowerVerts
[j
]); /*the origin of this fan*/
2321 /*find the last k>=i such that
2322 *upperverts[k][0] <= lowerverts[j][0]
2327 if(upperVerts
[k
][0] > lowerVerts
[j
][0])
2332 for(l
=k
; l
>=i
; l
--)/*the reverse is for two-face lighting*/
2334 pStream
->insert(upperVerts
[l
]);
2336 pStream
->insert(leftMostV
);
2338 pStream
->end(PRIMITIVE_STREAM_FAN
);
2339 //update i for next loop
2341 leftMostV
= upperVerts
[k
];
2344 else /*upperVerts[i][0] > lowerVerts[j][0]*/
2347 pStream
->insert(upperVerts
[i
]);/*the origion of this fan*/
2348 pStream
->insert(leftMostV
);
2349 /*find the last k>=j such that
2350 *lowerverts[k][0] < upperverts[i][0]*/
2354 if(lowerVerts
[k
][0] >= upperVerts
[i
][0])
2356 pStream
->insert(lowerVerts
[k
]);
2359 pStream
->end(PRIMITIVE_STREAM_FAN
);
2361 leftMostV
= lowerVerts
[j
-1];
2368 void stripOfFanLeft(vertexArray
* leftChain
,
2373 Int ulineSmallIndex
,
2374 Int ulineLargeIndex
,
2375 primStream
* pStream
,
2376 Int gridLineUp
/*1 if the grid line is above the trim lines*/
2379 assert(largeIndex
>= smallIndex
);
2382 grid_v_value
= grid
->get_v_value(vlineIndex
);
2384 Real2
* trimVerts
=(Real2
*) malloc(sizeof(Real2
)* (largeIndex
-smallIndex
+1));
2388 Real2
* gridVerts
=(Real2
*) malloc(sizeof(Real2
)* (ulineLargeIndex
-ulineSmallIndex
+1));
2392 if(gridLineUp
) /*trim line is below grid line, so trim vertices are going right when index increases*/
2393 for(k
=0, i
=smallIndex
; i
<=largeIndex
; i
++, k
++)
2395 trimVerts
[k
][0] = leftChain
->getVertex(i
)[0];
2396 trimVerts
[k
][1] = leftChain
->getVertex(i
)[1];
2399 for(k
=0, i
=largeIndex
; i
>=smallIndex
; i
--, k
++)
2401 trimVerts
[k
][0] = leftChain
->getVertex(i
)[0];
2402 trimVerts
[k
][1] = leftChain
->getVertex(i
)[1];
2405 for(k
=0, i
=ulineSmallIndex
; i
<= ulineLargeIndex
; i
++, k
++)
2407 gridVerts
[k
][0] = grid
->get_u_value(i
);
2408 gridVerts
[k
][1] = grid_v_value
;
2413 ulineLargeIndex
-ulineSmallIndex
+1, gridVerts
,
2414 largeIndex
-smallIndex
+1, trimVerts
,
2417 triangulateXYMono(largeIndex
-smallIndex
+1, trimVerts
,
2418 ulineLargeIndex
-ulineSmallIndex
+1, gridVerts
,