ReactOS 0.4.15-dev-7660-g0086d05
monoTriangulation.cc
Go to the documentation of this file.
1/*
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:
9**
10** http://oss.sgi.com/projects/FreeB
11**
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.
17**
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.
23**
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.
33**
34*/
35/*
36*/
37
38//#include <stdlib.h>
39//#include <stdio.h>
40//#include "gluos.h"
41//#include "glimports.h"
42//#include "zlassert.h"
43
44#include "monoTriangulation.h"
45#include "polyUtil.h" /*for area*/
46#include "partitionX.h"
47#include "monoPolyPart.h"
48
49
50
52
53/*poly is NOT deleted
54 */
56{
57 Int n_cusps;
58 Int n_edges = poly->numEdges();
59 directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*)*n_edges);
60 assert(cusps);
61 findInteriorCuspsX(poly, n_cusps, cusps);
62 if(n_cusps ==0) //u monotine
63 {
64 monoTriangulationFun(poly, compV2InX, pStream);
65 }
66 else if(n_cusps == 1) // one interior cusp
67 {
68 directedLine* new_polygon = polygonConvert(cusps[0]);
70 //<other> should NOT be null unless there are self-intersecting
71 //trim curves. In that case, we don't want to core dump, instead,
72 //we triangulate anyway, and print out error message.
73 if(other == NULL)
74 {
75 monoTriangulationFun(poly, compV2InX, pStream);
76 }
77 else
78 {
79 directedLine* ret_p1;
80 directedLine* ret_p2;
81
82 new_polygon->connectDiagonal_2slines(new_polygon, other,
83 &ret_p1,
84 &ret_p2,
85 new_polygon);
86
87 monoTriangulationFun(ret_p1, compV2InX, pStream);
88 monoTriangulationFun(ret_p2, compV2InX, pStream);
89
92 }
93 }
94 else
95 {
96 //we need a general partitionX funtion (supposed to be in partitionX.C,
97 //not implemented yet. XXX
98 monoTriangulationFun(poly, compV2InY, pStream);
99 }
100
101 free(cusps);
102}
103
104void monoTriangulationRecOpt(Real* topVertex, Real* botVertex,
105 vertexArray* left_chain, Int left_current,
106 vertexArray* right_chain, Int right_current,
107 primStream* pStream)
108{
109 Int i,j;
110 Int n_left = left_chain->getNumElements();
111 Int n_right = right_chain->getNumElements();
112 if(left_current>= n_left-1 ||
113 right_current>= n_right-1)
114 {
115 monoTriangulationRec(topVertex, botVertex, left_chain, left_current,
116 right_chain, right_current, pStream);
117 return;
118 }
119 //now both left and right have at least two vertices each.
120 Real left_v = left_chain->getVertex(left_current)[1];
121 Real right_v = right_chain->getVertex(right_current)[1];
122
123 if(left_v <= right_v) //first left vertex is below right
124 {
125 //find the last vertex of right which is above or equal to left
126 for(j=right_current; j<=n_right-1; j++)
127 {
128 if(right_chain->getVertex(j)[1] < left_v)
129 break;
130 }
131 monoTriangulationRecGen(topVertex, left_chain->getVertex(left_current),
132 left_chain, left_current, left_current,
133 right_chain, right_current, j-1,
134 pStream);
135 monoTriangulationRecOpt(right_chain->getVertex(j-1),
136 botVertex,
137 left_chain, left_current,
138 right_chain, j,
139 pStream);
140 }
141 else //first right vertex is strictly below left
142 {
143 //find the last vertex of left which is strictly above right
144 for(i=left_current; i<=n_left-1; i++)
145 {
146 if(left_chain->getVertex(i)[1] <= right_v)
147 break;
148 }
149 monoTriangulationRecGen(topVertex, right_chain->getVertex(right_current),
150 left_chain, left_current, i-1,
151 right_chain, right_current, right_current,
152 pStream);
153 monoTriangulationRecOpt(left_chain->getVertex(i-1),
154 botVertex,
155 left_chain, i,
156 right_chain, right_current,
157 pStream);
158 }
159}
160
161
162void monoTriangulationRecGenTBOpt(Real* topVertex, Real* botVertex,
163 vertexArray* inc_chain, Int inc_current, Int inc_end,
164 vertexArray* dec_chain, Int dec_current, Int dec_end,
165 primStream* pStream)
166{
167 pStream->triangle(topVertex, inc_chain->getVertex(inc_current), dec_chain->getVertex(dec_current));
168
169/*printf("**(%f,%f)\n", inc_chain->getArray()[0][0],inc_chain->getArray()[0][1]);*/
170 triangulateXYMonoTB(inc_end-inc_current+1, inc_chain->getArray()+inc_current, dec_end-dec_current+1, dec_chain->getArray()+dec_current, pStream);
171
172 pStream->triangle(botVertex, dec_chain->getVertex(dec_end), inc_chain->getVertex(inc_end));
173}
174
175
176/*n_left>=1
177 *n_right>=1
178 *the strip is going top to bottom. compared to the funtion
179 * triangulateXYmono()
180 */
181void triangulateXYMonoTB(Int n_left, Real** leftVerts,
182 Int n_right, Real** rightVerts,
183 primStream* pStream)
184{
185
186
187 Int i,j,k,l;
188 Real* topMostV;
189
190 assert(n_left>=1 && n_right>=1);
191 if(leftVerts[0][1] >= rightVerts[0][1])
192 {
193 i=1;
194 j=0;
195 topMostV = leftVerts[0];
196 }
197 else
198 {
199 i=0;
200 j=1;
201 topMostV = rightVerts[0];
202 }
203
204 while(1)
205 {
206 if(i >= n_left) /*case1: no more in left*/
207 {
208
209 if(j<n_right-1) /*at least two vertices in right*/
210 {
211 pStream->begin();
212 pStream->insert(topMostV);
213 for(k=n_right-1; k>=j; k--)
214 pStream->insert(rightVerts[j]);
215
216 pStream->end(PRIMITIVE_STREAM_FAN);
217
218 }
219
220 break;
221 }
222 else if(j>= n_right) /*case2: no more in right*/
223 {
224
225 if(i<n_left-1) /*at least two vertices in left*/
226 {
227 pStream->begin();
228 pStream->insert(topMostV);
229
230 for(k=i; k<n_left; k++)
231 pStream->insert(leftVerts[k]);
232
233 pStream->end(PRIMITIVE_STREAM_FAN);
234 }
235
236 break;
237 }
238 else /* case3: neither is empty, plus the topMostV, there is at least one triangle to output*/
239 {
240
241 if(leftVerts[i][1] >= rightVerts[j][1])
242 {
243 pStream->begin();
244 pStream->insert(rightVerts[j]); /*the origin of this fan*/
245
246 pStream->insert(topMostV);
247
248 /*find the last k>=i such that
249 *leftverts[k][1] >= rightverts[j][1]
250 */
251 k=i;
252 while(k<n_left)
253 {
254 if(leftVerts[k][1] < rightVerts[j][1])
255 break;
256 k++;
257 }
258 k--;
259 for(l=i; l<=k; l++)
260 {
261 pStream->insert(leftVerts[l]);
262 }
263
264 pStream->end(PRIMITIVE_STREAM_FAN);
265 //update i for next loop
266 i = k+1;
267 topMostV = leftVerts[k];
268
269 }
270 else /*leftVerts[i][1] < rightVerts[j][1]*/
271 {
272 pStream->begin();
273 pStream->insert(leftVerts[i]);/*the origion of this fan*/
274
275 /*find the last k>=j such that
276 *rightverts[k][1] > leftverts[i][1]*/
277 k=j;
278 while(k< n_right)
279 {
280 if(rightVerts[k][1] <= leftVerts[i][1])
281 break;
282 k++;
283 }
284 k--;
285
286 for(l=k; l>= j; l--)
287 pStream->insert(rightVerts[l]);
288
289 pStream->insert(topMostV);
290 pStream->end(PRIMITIVE_STREAM_FAN);
291 j=k+1;
292 topMostV = rightVerts[j-1];
293 }
294 }
295 }
296}
297
298static int chainConvex(vertexArray* inc_chain, Int inc_current, Int inc_end)
299{
300 Int i;
301 //if there are no more than 2 vertices, return 1
302 if(inc_current >= inc_end-1) return 1;
303 for(i=inc_current; i<= inc_end-2; i++)
304 {
305 if(area(inc_chain->getVertex(i), inc_chain->getVertex(i+1), inc_chain->getVertex(i+2)) <0)
306 return 0;
307 }
308 return 1;
309}
310
311static int chainConcave(vertexArray* dec_chain, Int dec_current, Int dec_end)
312{
313 Int i;
314 //if there are no more than 2 vertices, return 1
315 if(dec_current >= dec_end -1) return 1;
316 for(i=dec_current; i<=dec_end-2; i++)
317 {
318 if(area(dec_chain->getVertex(i), dec_chain->getVertex(i+1), dec_chain->getVertex(i+2)) >0)
319 return 0;
320 }
321 return 1;
322}
323
324void monoTriangulationRecGenInU(Real* topVertex, Real* botVertex,
325 vertexArray* inc_chain, Int inc_current, Int inc_end,
326 vertexArray* dec_chain, Int dec_current, Int dec_end,
327 primStream* pStream)
328{
329
330}
331
332void monoTriangulationRecGenOpt(Real* topVertex, Real* botVertex,
333 vertexArray* inc_chain, Int inc_current, Int inc_end,
334 vertexArray* dec_chain, Int dec_current, Int dec_end,
335 primStream* pStream)
336{
337 Int i;
338 //copy this to a polygon: directedLine Lioop
339 sampledLine* sline;
340 directedLine* dline;
341 directedLine* poly;
342
343 if(inc_current <= inc_end) //at least one vertex in inc_chain
344 {
345 sline = new sampledLine(topVertex, inc_chain->getVertex(inc_current));
346 poly = new directedLine(INCREASING, sline);
347 for(i=inc_current; i<=inc_end-1; i++)
348 {
349 sline = new sampledLine(inc_chain->getVertex(i), inc_chain->getVertex(i+1));
350 dline = new directedLine(INCREASING, sline);
351 poly->insert(dline);
352 }
353 sline = new sampledLine(inc_chain->getVertex(inc_end), botVertex);
354 dline = new directedLine(INCREASING, sline);
355 poly->insert(dline);
356 }
357 else //inc_chian is empty
358 {
359 sline = new sampledLine(topVertex, botVertex);
360 dline = new directedLine(INCREASING, sline);
361 poly = dline;
362 }
363
364 assert(poly != NULL);
365
366 if(dec_current <= dec_end) //at least on vertex in dec_Chain
367 {
368 sline = new sampledLine(botVertex, dec_chain->getVertex(dec_end));
369 dline = new directedLine(INCREASING, sline);
370 poly->insert(dline);
371 for(i=dec_end; i>dec_current; i--)
372 {
373 sline = new sampledLine(dec_chain->getVertex(i), dec_chain->getVertex(i-1));
374 dline = new directedLine(INCREASING, sline);
375 poly->insert(dline);
376 }
377 sline = new sampledLine(dec_chain->getVertex(dec_current), topVertex);
378 dline = new directedLine(INCREASING, sline);
379 poly->insert(dline);
380 }
381 else //dec_chain is empty
382 {
383 sline = new sampledLine(botVertex, topVertex);
384 dline = new directedLine(INCREASING, sline);
385 poly->insert(dline);
386 }
387
388 {
389 Int n_cusps;
390 Int n_edges = poly->numEdges();
391 directedLine** cusps = (directedLine**) malloc(sizeof(directedLine*)*n_edges);
392 assert(cusps);
393 findInteriorCuspsX(poly, n_cusps, cusps);
394
395 if(n_cusps ==0) //u monotine
396 {
397 monoTriangulationFun(poly, compV2InX, pStream);
398 }
399 else if(n_cusps == 1) // one interior cusp
400 {
401 directedLine* new_polygon = polygonConvert(cusps[0]);
403 //<other> should NOT be null unless there are self-intersecting
404 //trim curves. In that case, we don't want to core dump, instead,
405 //we triangulate anyway, and print out error message.
406 if(other == NULL)
407 {
408 monoTriangulationFun(poly, compV2InX, pStream);
409 }
410 else
411 {
412 directedLine* ret_p1;
413 directedLine* ret_p2;
414
415 new_polygon->connectDiagonal_2slines(new_polygon, other,
416 &ret_p1,
417 &ret_p2,
418 new_polygon);
419
420 monoTriangulationFun(ret_p1, compV2InX, pStream);
421 monoTriangulationFun(ret_p2, compV2InX, pStream);
422
425 }
426 }
427 else
428 {
429 //we need a general partitionX funtion (supposed to be in partitionX.C,
430 //not implemented yet. XXX
431 //monoTriangulationFun(poly, compV2InY, pStream);
432
433 directedLine* new_polygon = polygonConvert(poly);
434 directedLine* list = monoPolyPart(new_polygon);
435 for(directedLine* temp = list; temp != NULL; temp = temp->getNextPolygon())
436 {
438 }
439 //clean up
440 list->deletePolygonListWithSline();
441
442 }
443
444 free(cusps);
445 /*
446 if(numInteriorCuspsX(poly) == 0) //is u monotone
447 monoTriangulationFun(poly, compV2InX, pStream);
448 else //it is not u motone
449 monoTriangulationFun(poly, compV2InY, pStream);
450 */
451 //clean up space
453 return;
454 }
455
456 //apparently the following code is not reachable,
457 //it is for test purpose
458 if(inc_current > inc_end || dec_current>dec_end)
459 {
460 monoTriangulationRecGen(topVertex, botVertex, inc_chain, inc_current, inc_end,
461 dec_chain, dec_current, dec_end,
462 pStream);
463 return;
464 }
465
466
467 if(
468 area(dec_chain->getVertex(dec_current),
469 topVertex,
470 inc_chain->getVertex(inc_current)) >=0
471 && chainConvex(inc_chain, inc_current, inc_end)
472 && chainConcave(dec_chain, dec_current, dec_end)
473 && area(inc_chain->getVertex(inc_end), botVertex, dec_chain->getVertex(dec_end)) >=0
474 )
475 {
476 monoTriangulationRecFunGen(topVertex, botVertex,
477 inc_chain, inc_current, inc_end,
478 dec_chain, dec_current, dec_end,
479 compV2InX, pStream);
480 }
481 else
482 {
483 monoTriangulationRecGen(topVertex, botVertex, inc_chain, inc_current, inc_end,
484 dec_chain, dec_current, dec_end,
485 pStream);
486 }
487}
488
489/*if inc_current>inc_end, then inc_chain has no points to be considered
490 *same for dec_chain
491 */
492void monoTriangulationRecGen(Real* topVertex, Real* botVertex,
493 vertexArray* inc_chain, Int inc_current, Int inc_end,
494 vertexArray* dec_chain, Int dec_current, Int dec_end,
495 primStream* pStream)
496{
497 Real** inc_array ;
498 Real** dec_array ;
499 Int i;
500
501 if(inc_current > inc_end && dec_current>dec_end)
502 return;
503 else if(inc_current>inc_end) /*no more vertices on inc_chain*/
504 {
505 dec_array = dec_chain->getArray();
506 reflexChain rChain(100,0);
507 /*put the top vertex into the reflex chain*/
508 rChain.processNewVertex(topVertex, pStream);
509 /*process all the vertices on the dec_chain*/
510 for(i=dec_current; i<=dec_end; i++){
511 rChain.processNewVertex(dec_array[i], pStream);
512 }
513 /*process the bottom vertex*/
514 rChain.processNewVertex(botVertex, pStream);
515 }
516 else if(dec_current> dec_end) /*no more vertices on dec_chain*/
517 {
518 inc_array = inc_chain->getArray();
519
520 reflexChain rChain(100,1);
521 /*put the top vertex into the reflex chain*/
522 rChain.processNewVertex(topVertex, pStream);
523 /*process all the vertices on the inc_chain*/
524 for(i=inc_current; i<=inc_end; i++){
525 rChain.processNewVertex(inc_array[i], pStream);
526 }
527 /*process the bottom vertex*/
528 rChain.processNewVertex(botVertex, pStream);
529 }
530 else /*neither chain is empty*/
531 {
532 inc_array = inc_chain -> getArray();
533 dec_array = dec_chain -> getArray();
534
535 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
536 *vertices on the dec_chain which are higher than top of inc_chain
537 */
538 if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
539 {
540
541 reflexChain rChain(100, 0);
542 rChain.processNewVertex(topVertex, pStream);
543 for(i=dec_current; i<=dec_end; i++)
544 {
545 if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
546 rChain.processNewVertex(dec_array[i], pStream);
547 else
548 break;
549 }
550 rChain.outputFan(inc_array[inc_current], pStream);
551 monoTriangulationRecGen(dec_array[i-1], botVertex,
552 inc_chain, inc_current, inc_end,
553 dec_chain, i, dec_end,
554 pStream);
555 }
556 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
557 {
558
559 reflexChain rChain(100, 1);
560 rChain.processNewVertex(topVertex, pStream);
561 for(i=inc_current; i<=inc_end; i++)
562 {
563 if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
564 rChain.processNewVertex(inc_array[i], pStream);
565 else
566 break;
567 }
568 rChain.outputFan(dec_array[dec_current], pStream);
569 monoTriangulationRecGen(inc_array[i-1], botVertex,
570 inc_chain, i, inc_end,
571 dec_chain, dec_current,dec_end,
572 pStream);
573 }
574 }/*end case neither is empty*/
575}
576
577void monoTriangulationFun(directedLine* monoPolygon, Int (*compFun)(Real*, Real*), primStream* pStream)
578{
579 Int i;
580 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
581 *then call monoTriangulationRec
582 */
583 directedLine* tempV;
584 directedLine* topV;
585 directedLine* botV;
586 topV = botV = monoPolygon;
587 for(tempV = monoPolygon->getNext(); tempV != monoPolygon; tempV = tempV->getNext())
588 {
589 if(compFun(topV->head(), tempV->head())<0) {
590 topV = tempV;
591 }
592 if(compFun(botV->head(), tempV->head())>0) {
593 botV = tempV;
594 }
595 }
596
597 /*creat increase and decrease chains*/
598 vertexArray inc_chain(20); /*this is a dynamic array*/
599 for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
600 inc_chain.appendVertex(topV->getVertex(i));
601 }
602 for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
603 {
604 for(i=0; i<=tempV->get_npoints()-2; i++){
605 inc_chain.appendVertex(tempV->getVertex(i));
606 }
607 }
608
609 vertexArray dec_chain(20);
610 for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
611 {
612 for(i=tempV->get_npoints()-2; i>=0; i--){
613 dec_chain.appendVertex(tempV->getVertex(i));
614 }
615 }
616 for(i=botV->get_npoints()-2; i>=1; i--){
617 dec_chain.appendVertex(tempV->getVertex(i));
618 }
619
620 if (!(0 == inc_chain.getNumElements() && 0 == dec_chain.getNumElements())) {
621 monoTriangulationRecFun(topV->head(), botV->head(), &inc_chain, 0,
622 &dec_chain, 0, compFun, pStream);
623 }
624}
625
626void monoTriangulation(directedLine* monoPolygon, primStream* pStream)
627{
628 Int i;
629 /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
630 *then call monoTriangulationRec
631 */
632 directedLine* tempV;
633 directedLine* topV;
634 directedLine* botV;
635 topV = botV = monoPolygon;
636 for(tempV = monoPolygon->getNext(); tempV != monoPolygon; tempV = tempV->getNext())
637 {
638 if(compV2InY(topV->head(), tempV->head())<0) {
639 topV = tempV;
640 }
641 if(compV2InY(botV->head(), tempV->head())>0) {
642 botV = tempV;
643 }
644 }
645 /*creat increase and decrease chains*/
646 vertexArray inc_chain(20); /*this is a dynamic array*/
647 for(i=1; i<=topV->get_npoints()-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
648 inc_chain.appendVertex(topV->getVertex(i));
649 }
650 for(tempV = topV->getNext(); tempV != botV; tempV = tempV->getNext())
651 {
652 for(i=0; i<=tempV->get_npoints()-2; i++){
653 inc_chain.appendVertex(tempV->getVertex(i));
654 }
655 }
656
657 vertexArray dec_chain(20);
658 for(tempV = topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
659 {
660 for(i=tempV->get_npoints()-2; i>=0; i--){
661 dec_chain.appendVertex(tempV->getVertex(i));
662 }
663 }
664 for(i=botV->get_npoints()-2; i>=1; i--){
665 dec_chain.appendVertex(tempV->getVertex(i));
666 }
667
668 monoTriangulationRec(topV->head(), botV->head(), &inc_chain, 0, &dec_chain, 0, pStream);
669
670}
671
672/*the chain could be increasing or decreasing, although we use the
673 * name inc_chain.
674 *the argument is_increase_chain indicates whether this chain
675 *is increasing (left chain in V-monotone case) or decreaing (right chain
676 *in V-monotone case).
677 */
678void monoTriangulation2(Real* topVertex, Real* botVertex,
679 vertexArray* inc_chain, Int inc_smallIndex,
680 Int inc_largeIndex,
681 Int is_increase_chain,
682 primStream* pStream)
683{
684 assert( inc_chain != NULL);
685 Real** inc_array ;
686
687 if(inc_smallIndex > inc_largeIndex)
688 return; //no triangles
689 if(inc_smallIndex == inc_largeIndex)
690 {
691 if(is_increase_chain)
692 pStream->triangle(inc_chain->getVertex(inc_smallIndex), botVertex, topVertex);
693 else
694 pStream->triangle(inc_chain->getVertex(inc_smallIndex), topVertex, botVertex);
695 return;
696 }
697 Int i;
698
699 if(is_increase_chain && botVertex[1] == inc_chain->getVertex(inc_largeIndex)[1])
700 {
701 pStream->triangle(botVertex, inc_chain->getVertex(inc_largeIndex-1),
702 inc_chain->getVertex(inc_largeIndex));
703 monoTriangulation2(topVertex, botVertex, inc_chain, inc_smallIndex,
704 inc_largeIndex-1,
705 is_increase_chain,
706 pStream);
707 return;
708 }
709 else if( (!is_increase_chain) && topVertex[1] == inc_chain->getVertex(inc_smallIndex)[1])
710 {
711 pStream->triangle(topVertex, inc_chain->getVertex(inc_smallIndex+1),
712 inc_chain->getVertex(inc_smallIndex));
713 monoTriangulation2(topVertex, botVertex, inc_chain, inc_smallIndex+1,
714 inc_largeIndex, is_increase_chain, pStream);
715 return ;
716 }
717
718 inc_array = inc_chain->getArray();
719
720 reflexChain rChain(20,is_increase_chain); /*1 means the chain is increasing*/
721
722 rChain.processNewVertex(topVertex, pStream);
723
724 for(i=inc_smallIndex; i<=inc_largeIndex; i++){
725 rChain.processNewVertex(inc_array[i], pStream);
726 }
727 rChain.processNewVertex(botVertex, pStream);
728
729}
730
731/*if compFun == compV2InY, top to bottom: V-monotone
732 *if compFun == compV2InX, right to left: U-monotone
733 */
734void monoTriangulationRecFunGen(Real* topVertex, Real* botVertex,
735 vertexArray* inc_chain, Int inc_current, Int inc_end,
736 vertexArray* dec_chain, Int dec_current, Int dec_end,
737 Int (*compFun)(Real*, Real*),
738 primStream* pStream)
739{
740 assert( inc_chain != NULL && dec_chain != NULL);
741 assert( ! (inc_current> inc_end &&
742 dec_current> dec_end));
743 /*
744 Int inc_nVertices;
745 Int dec_nVertices;
746 */
747 Real** inc_array ;
748 Real** dec_array ;
749 Int i;
750 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
751
752 if(inc_current> inc_end) /*no more vertices on inc_chain*/
753 {
754
755 dec_array = dec_chain->getArray();
756 reflexChain rChain(20,0);
757 /*put the top vertex into the reflex chain*/
758 rChain.processNewVertex(topVertex, pStream);
759 /*process all the vertices on the dec_chain*/
760 for(i=dec_current; i<=dec_end; i++){
761 rChain.processNewVertex(dec_array[i], pStream);
762 }
763 /*process the bottom vertex*/
764 rChain.processNewVertex(botVertex, pStream);
765
766 }
767 else if(dec_current> dec_end) /*no more vertices on dec_chain*/
768 {
769 inc_array = inc_chain->getArray();
770 reflexChain rChain(20,1);
771 /*put the top vertex into the reflex chain*/
772 rChain.processNewVertex(topVertex, pStream);
773 /*process all the vertices on the inc_chain*/
774 for(i=inc_current; i<=inc_end; i++){
775 rChain.processNewVertex(inc_array[i], pStream);
776 }
777 /*process the bottom vertex*/
778 rChain.processNewVertex(botVertex, pStream);
779 }
780 else /*neither chain is empty*/
781 {
782 inc_array = inc_chain -> getArray();
783 dec_array = dec_chain -> getArray();
784
785 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
786 *vertices on the dec_chain which are higher than top of inc_chain
787 */
788 if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
789 {
790
791 reflexChain rChain(20, 0);
792 rChain.processNewVertex(topVertex, pStream);
793 for(i=dec_current; i<=dec_end; i++)
794 {
795 if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
796 rChain.processNewVertex(dec_array[i], pStream);
797 else
798 break;
799 }
800 rChain.outputFan(inc_array[inc_current], pStream);
801 monoTriangulationRecFunGen(dec_array[i-1], botVertex,
802 inc_chain, inc_current, inc_end,
803 dec_chain, i, dec_end,
804 compFun,
805 pStream);
806 }
807 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
808 {
809
810 reflexChain rChain(20, 1);
811 rChain.processNewVertex(topVertex, pStream);
812 for(i=inc_current; i<=inc_end; i++)
813 {
814 if(compFun(inc_array[i], dec_array[dec_current]) >0)
815 rChain.processNewVertex(inc_array[i], pStream);
816 else
817 break;
818 }
819 rChain.outputFan(dec_array[dec_current], pStream);
820 monoTriangulationRecFunGen(inc_array[i-1], botVertex,
821 inc_chain, i,inc_end,
822 dec_chain, dec_current,dec_end,
823 compFun,
824 pStream);
825 }
826 }/*end case neither is empty*/
827}
828
829/*if compFun == compV2InY, top to bottom: V-monotone
830 *if compFun == compV2InX, right to left: U-monotone
831 */
832void monoTriangulationRecFun(Real* topVertex, Real* botVertex,
833 vertexArray* inc_chain, Int inc_current,
834 vertexArray* dec_chain, Int dec_current,
835 Int (*compFun)(Real*, Real*),
836 primStream* pStream)
837{
838 assert( inc_chain != NULL && dec_chain != NULL);
839 assert( ! (inc_current>=inc_chain->getNumElements() &&
840 dec_current>=dec_chain->getNumElements()));
841 Int inc_nVertices;
842 Int dec_nVertices;
843 Real** inc_array ;
844 Real** dec_array ;
845 Int i;
846 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
847
848 if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
849 {
850
851 dec_array = dec_chain->getArray();
852 dec_nVertices = dec_chain->getNumElements();
853 reflexChain rChain(20,0);
854 /*put the top vertex into the reflex chain*/
855 rChain.processNewVertex(topVertex, pStream);
856 /*process all the vertices on the dec_chain*/
857 for(i=dec_current; i<dec_nVertices; i++){
858 rChain.processNewVertex(dec_array[i], pStream);
859 }
860 /*process the bottom vertex*/
861 rChain.processNewVertex(botVertex, pStream);
862
863 }
864 else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
865 {
866 inc_array = inc_chain->getArray();
867 inc_nVertices= inc_chain->getNumElements();
868 reflexChain rChain(20,1);
869 /*put the top vertex into the reflex chain*/
870 rChain.processNewVertex(topVertex, pStream);
871 /*process all the vertices on the inc_chain*/
872 for(i=inc_current; i<inc_nVertices; i++){
873 rChain.processNewVertex(inc_array[i], pStream);
874 }
875 /*process the bottom vertex*/
876 rChain.processNewVertex(botVertex, pStream);
877 }
878 else /*neither chain is empty*/
879 {
880 inc_array = inc_chain -> getArray();
881 dec_array = dec_chain -> getArray();
882 inc_nVertices= inc_chain->getNumElements();
883 dec_nVertices= dec_chain->getNumElements();
884 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
885 *vertices on the dec_chain which are higher than top of inc_chain
886 */
887 if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
888 {
889
890 reflexChain rChain(20, 0);
891 rChain.processNewVertex(topVertex, pStream);
892 for(i=dec_current; i<dec_nVertices; i++)
893 {
894 if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
895 rChain.processNewVertex(dec_array[i], pStream);
896 else
897 break;
898 }
899 rChain.outputFan(inc_array[inc_current], pStream);
900 monoTriangulationRecFun(dec_array[i-1], botVertex,
901 inc_chain, inc_current,
902 dec_chain, i,
903 compFun,
904 pStream);
905 }
906 else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
907 {
908
909 reflexChain rChain(20, 1);
910 rChain.processNewVertex(topVertex, pStream);
911 for(i=inc_current; i<inc_nVertices; i++)
912 {
913 if(compFun(inc_array[i], dec_array[dec_current]) >0)
914 rChain.processNewVertex(inc_array[i], pStream);
915 else
916 break;
917 }
918 rChain.outputFan(dec_array[dec_current], pStream);
919 monoTriangulationRecFun(inc_array[i-1], botVertex,
920 inc_chain, i,
921 dec_chain, dec_current,
922 compFun,
923 pStream);
924 }
925 }/*end case neither is empty*/
926}
927
928
929void monoTriangulationRec(Real* topVertex, Real* botVertex,
930 vertexArray* inc_chain, Int inc_current,
931 vertexArray* dec_chain, Int dec_current,
932 primStream* pStream)
933{
934 assert( inc_chain != NULL && dec_chain != NULL);
935 assert( ! (inc_current>=inc_chain->getNumElements() &&
936 dec_current>=dec_chain->getNumElements()));
937 Int inc_nVertices;
938 Int dec_nVertices;
939 Real** inc_array ;
940 Real** dec_array ;
941 Int i;
942 assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
943
944 if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
945 {
946
947 dec_array = dec_chain->getArray();
948 dec_nVertices = dec_chain->getNumElements();
949 reflexChain rChain(20,0);
950 /*put the top vertex into the reflex chain*/
951 rChain.processNewVertex(topVertex, pStream);
952 /*process all the vertices on the dec_chain*/
953 for(i=dec_current; i<dec_nVertices; i++){
954 rChain.processNewVertex(dec_array[i], pStream);
955 }
956 /*process the bottom vertex*/
957 rChain.processNewVertex(botVertex, pStream);
958
959 }
960 else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
961 {
962 inc_array = inc_chain->getArray();
963 inc_nVertices= inc_chain->getNumElements();
964 reflexChain rChain(20,1);
965 /*put the top vertex into the reflex chain*/
966 rChain.processNewVertex(topVertex, pStream);
967 /*process all the vertices on the inc_chain*/
968 for(i=inc_current; i<inc_nVertices; i++){
969 rChain.processNewVertex(inc_array[i], pStream);
970 }
971 /*process the bottom vertex*/
972 rChain.processNewVertex(botVertex, pStream);
973 }
974 else /*neither chain is empty*/
975 {
976 inc_array = inc_chain -> getArray();
977 dec_array = dec_chain -> getArray();
978 inc_nVertices= inc_chain->getNumElements();
979 dec_nVertices= dec_chain->getNumElements();
980 /*if top of inc_chain is 'lower' than top of dec_chain, process all the
981 *vertices on the dec_chain which are higher than top of inc_chain
982 */
983 if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
984 {
985
986 reflexChain rChain(20, 0);
987 rChain.processNewVertex(topVertex, pStream);
988 for(i=dec_current; i<dec_nVertices; i++)
989 {
990 if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
991 rChain.processNewVertex(dec_array[i], pStream);
992 else
993 break;
994 }
995 rChain.outputFan(inc_array[inc_current], pStream);
996 monoTriangulationRec(dec_array[i-1], botVertex,
997 inc_chain, inc_current,
998 dec_chain, i,
999 pStream);
1000 }
1001 else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
1002 {
1003
1004 reflexChain rChain(20, 1);
1005 rChain.processNewVertex(topVertex, pStream);
1006 for(i=inc_current; i<inc_nVertices; i++)
1007 {
1008 if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
1009 rChain.processNewVertex(inc_array[i], pStream);
1010 else
1011 break;
1012 }
1013 rChain.outputFan(dec_array[dec_current], pStream);
1014 monoTriangulationRec(inc_array[i-1], botVertex,
1015 inc_chain, i,
1016 dec_chain, dec_current,
1017 pStream);
1018 }
1019 }/*end case neither is empty*/
1020}
1021
1022
1023
1024/* the name here assumes that the polygon is Y-monotone, but
1025 *this function also works for X-monotone polygons.
1026 * a monotne polygon consists of two extrem verteices: topVertex and botVertex, and
1027 *two monotone chains: inc_chain, and dec_chain. The edges of the increasing chain (inc_chain)
1028 *is ordered by following pointer: next, while the edges of the decreasing chain (dec_chain)
1029 *is ordered by following pointer: prev
1030 * inc_index index the vertex which is the toppest of the inc_chain which we are handling currently.
1031 * dec_index index the vertex which is the toppest of the dec_chain which we are handling currently.
1032 */
1033void monoTriangulationRec(directedLine* inc_chain, Int inc_index,
1034 directedLine* dec_chain, Int dec_index,
1035 directedLine* topVertex, Int top_index,
1036 directedLine* botVertex,
1037 primStream* pStream)
1038{
1039 Int i;
1040 directedLine *temp, *oldtemp = NULL;
1041 Int tempIndex, oldtempIndex = 0;
1042
1043 assert(inc_chain != NULL && dec_chain != NULL);
1044
1045 if(inc_chain == botVertex) {
1046 reflexChain rChain(20, 0);
1047 rChain.processNewVertex(topVertex->getVertex(top_index), pStream);
1048 for(i=dec_index; i< dec_chain->get_npoints(); i++){
1049 rChain.processNewVertex(dec_chain->getVertex(i), pStream);
1050 }
1051 for(temp = dec_chain->getPrev(); temp != botVertex; temp = temp->getPrev())
1052 {
1053 for(i=0; i<temp->get_npoints(); i++){
1054 rChain.processNewVertex(temp->getVertex(i), pStream);
1055 }
1056 }
1057 }
1058 else if(dec_chain==botVertex) {
1059 reflexChain rChain(20, 1);
1060 rChain.processNewVertex(topVertex->getVertex(top_index), pStream);
1061 for(i=inc_index; i< inc_chain->get_npoints(); i++){
1062 rChain.processNewVertex(inc_chain->getVertex(i), pStream);
1063 }
1064 for(temp = inc_chain->getPrev(); temp != botVertex; temp = temp->getNext())
1065 {
1066 for(i=0; i<temp->get_npoints(); i++){
1067 rChain.processNewVertex(temp->getVertex(i), pStream);
1068 }
1069 }
1070 }
1071 else /*neither reached the bottom*/{
1072 if(compV2InY(inc_chain->getVertex(inc_index), dec_chain->getVertex(dec_index)) <=0) {
1073 reflexChain rChain(20, 0);
1074 rChain.processNewVertex(topVertex -> getVertex(top_index), pStream);
1075 temp = dec_chain;
1076 tempIndex = dec_index;
1077 while( compV2InY(inc_chain->getVertex(inc_index), temp->getVertex(tempIndex))<=0) {
1078 oldtemp = temp;
1079 oldtempIndex = tempIndex;
1080 rChain.processNewVertex(temp->getVertex(tempIndex), pStream);
1081
1082 if(tempIndex == temp->get_npoints()-1){
1083 tempIndex = 0;
1084 temp = temp->getPrev();
1085 }
1086 else{
1087 tempIndex++;
1088 }
1089 }
1090 rChain.outputFan(inc_chain->getVertex(inc_index), pStream);
1091 monoTriangulationRec(inc_chain, inc_index, temp, tempIndex, oldtemp, oldtempIndex, botVertex, pStream);
1092 }
1093 else /* >0*/ {
1094 reflexChain rChain(20, 1);
1095 rChain.processNewVertex(topVertex -> getVertex(top_index), pStream);
1096 temp = inc_chain;
1097 tempIndex = inc_index;
1098 while( compV2InY(temp->getVertex(tempIndex), dec_chain->getVertex(dec_index))>0){
1099 oldtemp = temp;
1100 oldtempIndex = tempIndex;
1101 rChain.processNewVertex(temp->getVertex(tempIndex), pStream);
1102
1103 if(tempIndex == temp->get_npoints()-1){
1104 tempIndex = 0;
1105 temp = temp->getNext();
1106 }
1107 else{
1108 tempIndex++;
1109 }
1110 }
1111 rChain.outputFan(dec_chain->getVertex(dec_index), pStream);
1112 monoTriangulationRec(temp, tempIndex, dec_chain, dec_index, oldtemp, oldtempIndex, botVertex, pStream);
1113 }
1114 } /*end case neither reached the bottom*/
1115}
1116
1117/***************************vertexArray begin here**********************************/
1118vertexArray::vertexArray(Real2* vertices, Int nVertices)
1119{
1120 Int i;
1121 size = index = nVertices;
1122 array = (Real**) malloc(sizeof(Real*) * nVertices);
1123 assert(array);
1124 for(i=0; i<nVertices; i++)
1125 {
1126 array[i] = vertices[i];
1127 array[i] = vertices[i];
1128 }
1129}
1130
1132{
1133 size = s;
1134 array = (Real**) malloc(sizeof(Real*) * s);
1135 assert(array);
1136 index = 0;
1137}
1138
1140{
1141 free(array);
1142}
1143
1145{
1146 Int i;
1147 if(index >= size){
1148 Real** temp = (Real**) malloc(sizeof(Real*) * (2*size +1));
1149 assert(temp);
1150 for(i=0; i<index; i++)
1151 temp[i] = array[i];
1152 free(array);
1153 array = temp;
1154 size = 2*size+1;
1155 }
1156 array[index++] = ptr;
1157}
1158
1160{
1161 printf("vertex Array:index=%i, size=%i\n", index, size);
1162 for(Int i=0; i<index; i++)
1163 {
1164 printf("(%f,%f) ", array[i][0], array[i][1]);
1165 }
1166 printf("\n");
1167}
1168
1169/*find the first i such that array[i][1] >= v
1170 * and array[i+1][1] <v
1171 * if index == 0 (the array is empty, return -1.
1172 * if v is above all, return -1.
1173 * if v is below all, return index-1.
1174 */
1176{
1177 Int i;
1178 if(index == 0)
1179 return -1;
1180 else if(array[0][1] < v)
1181 return -1;
1182 else
1183 {
1184 for(i=1; i<index; i++)
1185 {
1186 if(array[i][1] < v)
1187 break;
1188 }
1189 return i-1;
1190 }
1191}
1192
1193/*find the first i<=endIndex such that array[i][1] <= v
1194 * and array[i-1][1] > v
1195 *if sartIndex>endIndex, then return endIndex+1.
1196 *otherwise, startIndex<=endIndex, it is assumed that
1197 * 0<=startIndex<=endIndex<index.
1198 * if v is below all, return endIndex+1
1199 * if v is above all, return startIndex.
1200 */
1202{
1203 Int i;
1204 if(startIndex > endIndex)
1205 return endIndex+1;
1206 else if(array[endIndex][1] > v)
1207 return endIndex+1;
1208 else //now array[endIndex][1] <= v
1209 {
1210 for(i=endIndex-1; i>=startIndex; i--)
1211 {
1212 if(array[i][1] > v)
1213 break;
1214 }
1215 return i+1;
1216 }
1217}
1218
1219/*find the first i<=endIndex such that array[i-1][1] >= v
1220 * and array[i][1] < v
1221 *if sartIndex>endIndex, then return endIndex+1.
1222 *otherwise, startIndex<=endIndex, it is assumed that
1223 * 0<=startIndex<=endIndex<index.
1224 * if v is below or equal to all, return endIndex+1
1225 * if v is strictly above all, return startIndex.
1226 */
1228{
1229 Int i;
1230 if(startIndex > endIndex)
1231 return endIndex+1;
1232 else if(array[endIndex][1] >= v)
1233 return endIndex+1;
1234 else //now array[endIndex][1] < v
1235 {
1236 for(i=endIndex-1; i>=startIndex; i--)
1237 {
1238 if(array[i][1] >= v)
1239 break;
1240 }
1241 return i+1;
1242 }
1243}
1244
1245/*find the first i>startIndex such that array[i-1][1] > v
1246 * and array[i][1] >=v
1247 *if sartIndex>endIndex, then return startIndex-1.
1248 *otherwise, startIndex<=endIndex, it is assumed that
1249 * 0<=startIndex<=endIndex<index.
1250 * if v is strictly above all, return startIndex-1
1251 * if v is strictly below all, return endIndex.
1252 */
1254{
1255
1256 Int i;
1257 if(startIndex > endIndex)
1258 return startIndex-1;
1259 else if(array[startIndex][1] < v)
1260 return startIndex-1;
1261 else //now array[startIndex][1] >= v
1262 {
1263
1264 for(i=startIndex; i<=endIndex; i++)
1265 {
1266 if(array[i][1] <= v)
1267 break;
1268 }
1269 if(i>endIndex) // v is strictly below all
1270 return endIndex;
1271 else if(array[i][1] == v)
1272 return i;
1273 else
1274 return i-1;
1275 }
1276
1277}
1278
1279
1280/*find the first i>=startIndex such that array[i][1] >= v
1281 * and array[i+1][1] <v
1282 *if sartIndex>endIndex, then return startIndex-1.
1283 *otherwise, startIndex<=endIndex, it is assumed that
1284 * 0<=startIndex<=endIndex<index.
1285 * if v is above all, return startIndex-1
1286 * if v is below all, return endIndex.
1287 */
1289{
1290 Int i;
1291 if(startIndex > endIndex)
1292 return startIndex-1;
1293 else if(array[startIndex][1] < v)
1294 return startIndex-1;
1295 else //now array[startIndex][1] >= v
1296 {
1297 for(i=startIndex+1; i<=endIndex; i++)
1298 {
1299 if(array[i][1] < v)
1300 break;
1301 }
1302 return i-1;
1303 }
1304}
1305
1307{
1308 Int i = end;
1309 Real prevU = array[i][0];
1310 Real thisU;
1311 for(i=end-1; i>=begin; i--){
1312 thisU = array[i][0];
1313 if(thisU < prevU)
1314 prevU = thisU;
1315 else
1316 break;
1317 }
1318 return i;
1319}
1320
1321//if(V(start) == v, return start, other wise return the
1322//last i so that V(i)==v
1324{
1325 Int i;
1326 if(array[start][1] != v)
1327 return start;
1328 //now array[start][1] == v
1329 for(i=start+1; i<= end; i++)
1330 if(array[i][1] != v)
1331 break;
1332 return i-1;
1333}
1334
1335
1336/***************************vertexArray end****************************************/
1337
1338
1339
1340/***************************relfex chain stuff begin here*****************************/
1341
1343{
1344 queue = (Real2*) malloc(sizeof(Real2) * size);
1345 assert(queue);
1346 index_queue = 0;
1347 size_queue = size;
1348 isIncreasing = is_increasing;
1349}
1350
1352{
1353 free(queue);
1354}
1355
1356/*put (u,v) at the end of the queue
1357 *pay attention to space
1358 */
1360{
1361 Int i;
1362 if(index_queue >= size_queue) {
1363 Real2 *temp = (Real2*) malloc(sizeof(Real2) * (2*size_queue+1));
1364 assert(temp);
1365
1366 /*copy*/
1367 for(i=0; i<index_queue; i++){
1368 temp[i][0] = queue[i][0];
1369 temp[i][1] = queue[i][1];
1370 }
1371
1372 free(queue);
1373 queue = temp;
1374 size_queue = 2*size_queue + 1;
1375 }
1376
1377 queue[index_queue][0] = u;
1378 queue[index_queue][1] = v;
1379 index_queue ++;
1380}
1381
1383{
1384 insert(v[0], v[1]);
1385}
1386
1387/*
1388static Real area(Real A[2], Real B[2], Real C[2])
1389{
1390 Real Bx, By, Cx, Cy;
1391 Bx = B[0] - A[0];
1392 By = B[1] - A[1];
1393 Cx = C[0] - A[0];
1394 Cy = C[1] - A[1];
1395 return Bx*Cy - Cx*By;
1396}
1397*/
1398
1399/*the chain is reflex, and the vertex v is
1400 *on the other side of the chain, so that
1401 *we can outout the fan with v as the
1402 *the center
1403 */
1405{
1406 Int i;
1407 pStream->begin();
1408 pStream->insert(v);
1409 if(isIncreasing) {
1410 for(i=0; i<index_queue; i++)
1411 pStream->insert(queue[i]);
1412 }
1413 else {
1414 for(i=index_queue-1; i>=0; i--)
1415 pStream->insert(queue[i]);
1416 }
1417 pStream->end(PRIMITIVE_STREAM_FAN);
1418}
1419
1421{
1422 Int i,j,k;
1423 Int isReflex;
1424 /*if there are at most one vertex in the queue, then simply insert
1425 */
1426 if(index_queue <=1){
1427 insert(v);
1428 return;
1429 }
1430
1431 /*there are at least two vertices in the queue*/
1432 j=index_queue-1;
1433
1434 for(i=j; i>=1; i--) {
1435 if(isIncreasing) {
1436 isReflex = (area(queue[i-1], queue[i], v) <= 0.0);
1437 }
1438 else /*decreasing*/{
1439 isReflex = (area(v, queue[i], queue[i-1]) <= 0.0);
1440 }
1441 if(isReflex) {
1442 break;
1443 }
1444 }
1445
1446 /*
1447 *if i<j then vertices: i+1--j are convex
1448 * output triangle fan:
1449 * v, and queue[i], i+1, ..., j
1450 */
1451 if(i<j)
1452 {
1453 pStream->begin();
1454 pStream->insert(v);
1455 if(isIncreasing) {
1456 for(k=i; k<=j; k++)
1457 pStream->insert(queue[k]);
1458 }
1459 else {
1460 for(k=j; k>=i; k--)
1461 pStream->insert(queue[k]);
1462 }
1463
1464 pStream->end(PRIMITIVE_STREAM_FAN);
1465 }
1466
1467 /*delete vertices i+1--j from the queue*/
1468 index_queue = i+1;
1469 /*finally insert v at the end of the queue*/
1470 insert(v);
1471
1472}
1473
1475{
1476 Int i;
1477 printf("reflex chain: isIncreasing=%i\n", isIncreasing);
1478 for(i=0; i<index_queue; i++) {
1479 printf("(%f,%f) ", queue[i][0], queue[i][1]);
1480 }
1481 printf("\n");
1482}
r l[0]
Definition: byte_order.h:168
return
Definition: dirsup.c:529
Int get_npoints()
Definition: directedLine.h:72
directedLine * getPrev()
Definition: directedLine.h:73
void deleteSinglePolygonWithSline()
Real * getVertex(Int i)
void connectDiagonal_2slines(directedLine *v1, directedLine *v2, directedLine **ret_p1, directedLine **ret_p2, directedLine *list)
directedLine * getNext()
Definition: directedLine.h:74
Real * head()
void insert(directedLine *nl)
Definition: list.h:37
void triangle(Real A[2], Real B[2], Real C[2])
void insert(Real u, Real v)
void end(Int type)
Definition: _queue.h:67
reflexChain(Int size, Int isIncreasing)
void outputFan(Real v[2], primStream *pStream)
void processNewVertex(Real v[2], primStream *pStream)
void insert(Real u, Real v)
Real ** getArray()
Real * getVertex(Int i)
Int findIndexAbove(Real v)
Int findIndexStrictBelowGen(Real v, Int startIndex, Int EndIndex)
Int skipEqualityFromStart(Real v, Int start, Int end)
Int findIndexFirstAboveEqualGen(Real v, Int startIndex, Int endIndex)
void appendVertex(Real *ptr)
Int findIndexBelowGen(Real v, Int startIndex, Int EndIndex)
Int findDecreaseChainFromEnd(Int begin, Int end)
Int findIndexAboveGen(Real v, Int startIndex, Int EndIndex)
#define free
Definition: debug_ros.c:5
#define malloc
Definition: debug_ros.c:4
int Int
Definition: definitions.h:37
float Real
Definition: definitions.h:36
Real Real2[2]
Definition: definitions.h:38
Int compV2InY(Real A[2], Real B[2])
Int compV2InX(Real A[2], Real B[2])
@ INCREASING
Definition: directedLine.h:39
#define NULL
Definition: types.h:112
#define assert(x)
Definition: debug.h:53
#define printf
Definition: freeldr.h:94
GLuint start
Definition: gl.h:1545
const GLdouble * v
Definition: gl.h:2040
GLdouble s
Definition: gl.h:2039
GLuint GLuint end
Definition: gl.h:1545
GLsizeiptr size
Definition: glext.h:5919
GLuint index
Definition: glext.h:6031
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
static PVOID ptr
Definition: dispmode.c:27
directedLine * monoPolyPart(directedLine *polygon)
Definition: monoPolyPart.cc:80
void triangulateXYMonoTB(Int n_left, Real **leftVerts, Int n_right, Real **rightVerts, primStream *pStream)
void monoTriangulationRecGen(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)
void monoTriangulationRecFunGen(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, Int(*compFun)(Real *, Real *), primStream *pStream)
void monoTriangulation2(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_smallIndex, Int inc_largeIndex, Int is_increase_chain, primStream *pStream)
static int chainConcave(vertexArray *dec_chain, Int dec_current, Int dec_end)
void monoTriangulationRecGenOpt(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)
void monoTriangulationRecGenInU(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)
directedLine * polygonConvert(directedLine *polygon)
void monoTriangulationRecGenTBOpt(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, Int inc_end, vertexArray *dec_chain, Int dec_current, Int dec_end, primStream *pStream)
void monoTriangulationFun(directedLine *monoPolygon, Int(*compFun)(Real *, Real *), primStream *pStream)
void monoTriangulationRecFun(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, Int(*compFun)(Real *, Real *), primStream *pStream)
void monoTriangulationRecOpt(Real *topVertex, Real *botVertex, vertexArray *left_chain, Int left_current, vertexArray *right_chain, Int right_current, primStream *pStream)
void monoTriangulation(directedLine *monoPolygon, primStream *pStream)
static int chainConvex(vertexArray *inc_chain, Int inc_current, Int inc_end)
void monoTriangulationRec(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_current, vertexArray *dec_chain, Int dec_current, primStream *pStream)
void monoTriangulationOpt(directedLine *poly, primStream *pStream)
int k
Definition: mpi.c:3369
int other
Definition: msacm.c:1376
void findInteriorCuspsX(directedLine *polygon, Int &ret_n_interior_cusps, directedLine **ret_interior_cusps)
Definition: partitionX.cc:121
directedLine * findDiagonal_singleCuspX(directedLine *cusp)
Definition: partitionX.cc:137
Int isReflex(directedLine *v)
Definition: partitionY.cc:122
static Real area(Real A[2], Real B[2], Real C[2])
Definition: polyDBG.cc:50
@ PRIMITIVE_STREAM_FAN
static calc_node_t temp
Definition: rpn_ieee.c:38
static clock_t begin
Definition: xmllint.c:458
static int insert
Definition: xmllint.c:138