ReactOS 0.4.15-dev-5829-g6b6a045
sampleCompTop.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 <math.h>
41//#include "zlassert.h"
42#include "sampleCompTop.h"
43#include "sampleCompRight.h"
44
45#define max(a,b) ((a>b)? a:b)
46
47//return : index_small, and index_large,
48//from [small, large] is strictly U-monotne,
49//from [large+1, end] is <u
50//and vertex[large][0] is >= u
51//if eveybody is <u, the large = start-1.
52//otherwise both large and small are meaningful and we have start<=small<=large<=end
54 Int leftStart,
55 Int leftEnd,
56 Real u,
57 Int& ret_index_small,
58 Int& ret_index_large
59 )
60{
61 Int i;
62 assert(leftStart <= leftEnd);
63 for(i=leftEnd; i>= leftStart; i--)
64 {
65 if(leftChain->getVertex(i)[0] >= u)
66 break;
67 }
68 ret_index_large = i;
69 if(ret_index_large >= leftStart)
70 {
71 for(i=ret_index_large; i>leftStart; i--)
72 {
73 if(leftChain->getVertex(i-1)[0] <= leftChain->getVertex(i)[0])
74 break;
75 }
76 ret_index_small = i;
77 }
78}
79
81 Int rightStart,
82 Int rightEnd,
83 Real u,
84 Int& ret_index_small,
85 Int& ret_index_large)
86{
87 Int i;
88 assert(rightStart<=rightEnd);
89 for(i=rightEnd; i>=rightStart; i--)
90 {
91 if(rightChain->getVertex(i)[0] <= u)
92 break;
93 }
94 ret_index_large = i;
95 if(ret_index_large >= rightStart)
96 {
97 for(i=ret_index_large; i>rightStart;i--)
98 {
99 if(rightChain->getVertex(i-1)[0] >= rightChain->getVertex(i)[0])
100 break;
101 }
102 ret_index_small = i;
103 }
104}
105
106
108 vertexArray* rightChain,
109 Int rightStart,
110 Int segIndexSmall,
111 Int segIndexLarge,
112 Int rightEnd,
113 gridWrap* grid,
114 Int gridV,
115 Int leftU,
116 Int rightU,
117 primStream* pStream)
118{
119 //the possible section which is to the right of rightU
120 if(segIndexLarge < rightEnd)
121 {
122 Real *tempTop;
123 if(segIndexLarge >= rightStart)
124 tempTop = rightChain->getVertex(segIndexLarge);
125 else
126 tempTop = topVertex;
127 Real tempBot[2];
128 tempBot[0] = grid->get_u_value(rightU);
129 tempBot[1] = grid->get_v_value(gridV);
130monoTriangulationRecGenOpt(tempTop, tempBot,
131 NULL, 1,0,
132 rightChain, segIndexLarge+1, rightEnd,
133 pStream);
134/*
135 monoTriangulation2(tempTop, tempBot,
136 rightChain,
137 segIndexLarge+1,
138 rightEnd,
139 0, //a decrease chian
140 pStream);
141*/
142
143 }
144
145 //the possible section which is strictly Umonotone
146 if(segIndexLarge >= rightStart)
147 {
148 stripOfFanRight(rightChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, rightU, pStream, 0);
149 Real tempBot[2];
150 tempBot[0] = grid->get_u_value(leftU);
151 tempBot[1] = grid->get_v_value(gridV);
152 monoTriangulation2(topVertex, tempBot, rightChain, rightStart, segIndexSmall, 0, pStream);
153 }
154 else //the topVertex forms a fan with the grid points
155 grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
156}
157
159 vertexArray* rightChain,
160 Int rightStart,
161 Int rightEnd,
162 gridWrap* grid,
163 Int gridV,
164 Int leftU,
165 Int rightU,
166 primStream* pStream
167 )
168{
169 //if right chian is empty, then there is only one topVertex with one grid line
170 if(rightEnd < rightStart){
171 grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
172 return;
173 }
174
175 Int segIndexSmall = 0, segIndexLarge;
176 findTopRightSegment(rightChain,
177 rightStart,
178 rightEnd,
179 grid->get_u_value(rightU),
180 segIndexSmall,
181 segIndexLarge
182 );
183 sampleTopRightWithGridLinePost(topVertex, rightChain,
184 rightStart,
185 segIndexSmall,
186 segIndexLarge,
187 rightEnd,
188 grid,
189 gridV,
190 leftU,
191 rightU,
192 pStream);
193}
194
195
197 vertexArray* leftChain,
198 Int leftStart,
199 Int segIndexSmall,
200 Int segIndexLarge,
201 Int leftEnd,
202 gridWrap* grid,
203 Int gridV,
204 Int leftU,
205 Int rightU,
206 primStream* pStream)
207{
208 //the possible section which is to the left of leftU
209
210 if(segIndexLarge < leftEnd)
211 {
212 Real *tempTop;
213 if(segIndexLarge >= leftStart)
214 tempTop = leftChain->getVertex(segIndexLarge);
215 else
216 tempTop = topVertex;
217 Real tempBot[2];
218 tempBot[0] = grid->get_u_value(leftU);
219 tempBot[1] = grid->get_v_value(gridV);
220
221 monoTriangulation2(tempTop, tempBot,
222 leftChain,
223 segIndexLarge+1,
224 leftEnd,
225 1, //a increase chian
226 pStream);
227 }
228
229 //the possible section which is strictly Umonotone
230 if(segIndexLarge >= leftStart)
231 {
232 //if there are grid points which are to the right of topV,
233 //then we should use topVertex to form a fan with these points to
234 //optimize the triangualtion
235 int do_optimize=1;
236 if(topVertex[0] >= grid->get_u_value(rightU))
237 do_optimize = 0;
238 else
239 {
240 //we also have to make sure that topVertex are the right most vertex
241 //on the chain.
242 int i;
243 for(i=leftStart; i<=segIndexSmall; i++)
244 if(leftChain->getVertex(i)[0] >= topVertex[0])
245 {
246 do_optimize = 0;
247 break;
248 }
249 }
250
251 if(do_optimize)
252 {
253 //find midU so that grid->get_u_value(midU) >= topVertex[0]
254 //and grid->get_u_value(midU-1) < topVertex[0]
255 int midU=rightU;
256 while(grid->get_u_value(midU) >= topVertex[0])
257 {
258 midU--;
259 if(midU < leftU)
260 break;
261 }
262 midU++;
263
264 grid->outputFanWithPoint(gridV, midU, rightU, topVertex, pStream);
265 stripOfFanLeft(leftChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, midU, pStream, 0);
266 Real tempBot[2];
267 tempBot[0] = grid->get_u_value(midU);
268 tempBot[1] = grid->get_v_value(gridV);
269 monoTriangulation2(topVertex, tempBot, leftChain, leftStart, segIndexSmall, 1, pStream);
270 }
271 else //not optimize
272 {
273
274 stripOfFanLeft(leftChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, rightU, pStream, 0);
275 Real tempBot[2];
276 tempBot[0] = grid->get_u_value(rightU);
277 tempBot[1] = grid->get_v_value(gridV);
278 monoTriangulation2(topVertex, tempBot, leftChain, leftStart, segIndexSmall, 1, pStream);
279 }
280 }
281 else //the topVertex forms a fan with the grid points
282 grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
283}
284
285
287 vertexArray* leftChain,
288 Int leftStart,
289 Int leftEnd,
290 gridWrap* grid,
291 Int gridV,
292 Int leftU,
293 Int rightU,
294 primStream* pStream
295 )
296{
297 Int segIndexSmall = 0, segIndexLarge;
298 //if left chain is empty, then there is only one top vertex with one grid
299 // line
300 if(leftEnd < leftStart) {
301 grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
302 return;
303 }
304 findTopLeftSegment(leftChain,
305 leftStart,
306 leftEnd,
307 grid->get_u_value(leftU),
308 segIndexSmall,
309 segIndexLarge
310 );
312 leftChain,
313 leftStart,
314 segIndexSmall,
315 segIndexLarge,
316 leftEnd,
317 grid,
318 gridV,
319 leftU,
320 rightU,
321 pStream);
322}
323
324
325//return 1 if saprator exits, 0 otherwise
327 Int leftStartIndex,
328 Int leftEndIndex,
329 vertexArray* rightChain,
330 Int rightStartIndex,
331 Int rightEndIndex,
332 Int& ret_sep_left,
333 Int& ret_sep_right)
334{
335
336 Int oldLeftI, oldRightI, newLeftI, newRightI;
337 Int i,j,k;
338 Real leftMax /*= leftChain->getVertex(leftEndIndex)[0]*/;
339 Real rightMin /*= rightChain->getVertex(rightEndIndex)[0]*/;
340 if(leftChain->getVertex(leftEndIndex)[1] > rightChain->getVertex(rightEndIndex)[1]) //left higher
341 {
342 oldLeftI = leftEndIndex+1;
343 oldRightI = rightEndIndex;
344 leftMax = leftChain->getVertex(leftEndIndex)[0] - Real(1.0); //initilza to left of leftU
345 rightMin = rightChain->getVertex(rightEndIndex)[0];
346 }
347 else
348 {
349 oldLeftI = leftEndIndex;
350 oldRightI = rightEndIndex+1;
351 leftMax = leftChain->getVertex(leftEndIndex)[0];
352 rightMin = rightChain->getVertex(rightEndIndex)[0] + Real(1.0);
353 }
354
355 //i: the current working leftChain index,
356 //j: the current working rightChain index,
357 //if left(i) is higher than right(j), then the two chains beloew right(j) are separated.
358 //else the two chains below left(i) are separeated.
359 i=leftEndIndex;
360 j=rightEndIndex;
361 while(1)
362 {
363 newLeftI = oldLeftI;
364 newRightI = oldRightI;
365
366 if(i<leftStartIndex) //left chain is done, go through remining right chain.
367 {
368 for(k=j-1; k>= rightStartIndex; k--)
369 {
370 if(rightChain->getVertex(k)[0] > leftMax) //no conflict
371 {
372 //update oldRightI if necessary
373 if(rightChain->getVertex(k)[0] < rightMin)
374 {
375 rightMin = rightChain->getVertex(k)[0];
376 oldRightI = k;
377 }
378 }
379 else //there is a conflict
380 break; //the for-loop. below right(k-1) is seperated: oldLeftI, oldRightI.
381 }
382 break; //the while loop
383 }
384 else if(j<rightStartIndex) //rightChain is done
385 {
386 for(k=i-1; k>= leftStartIndex; k--)
387 {
388 if(leftChain->getVertex(k)[0] < rightMin) //no conflict
389 {
390 //update oldLeftI if necessary
391 if(leftChain->getVertex(k)[0] > leftMax)
392 {
393 leftMax = leftChain->getVertex(k)[0];
394 oldLeftI = k;
395 }
396 }
397 else //there is a conflict
398 break; //the for loop
399 }
400 break; //the while loop
401 }
402 else if(leftChain->getVertex(i)[1] > rightChain->getVertex(j)[1]) //left hgiher
403 {
404 if(leftChain->getVertex(i)[0] > leftMax) //update leftMax and newLeftI.
405 {
406 leftMax = leftChain->getVertex(i)[0];
407 newLeftI = i;
408 }
409 for(k=j-1; k>= rightStartIndex; k--) //update rightMin and newRightI.
410 {
411 if(rightChain->getVertex(k)[1] > leftChain->getVertex(i)[1])
412 break;
413 if(rightChain->getVertex(k)[0] < rightMin)
414 {
415 rightMin = rightChain->getVertex(k)[0];
416 newRightI = k;
417 }
418 }
419 j = k; //next working j, since j will be higher than i in next loop
420 if(leftMax >= rightMin) //there is a conflict
421 break;
422 else //still no conflict
423 {
424 oldLeftI = newLeftI;
425 oldRightI = newRightI;
426 }
427 }
428 else //right higher
429 {
430 if(rightChain->getVertex(j)[0] < rightMin)
431 {
432 rightMin = rightChain->getVertex(j)[0];
433 newRightI = j;
434 }
435 for(k=i-1; k>= leftStartIndex; k--)
436 {
437 if(leftChain->getVertex(k)[1] > rightChain->getVertex(j)[1])
438 break;
439 if(leftChain->getVertex(k)[0] > leftMax)
440 {
441 leftMax = leftChain->getVertex(k)[0];
442 newLeftI = k;
443 }
444 }
445 i = k; //next working i, since i will be higher than j next loop
446
447 if(leftMax >= rightMin) //there is a conflict
448 break;
449 else //still no conflict
450 {
451 oldLeftI = newLeftI;
452 oldRightI = newRightI;
453 }
454 }
455 }//end of while loop
456 //now oldLeftI and oldRightI are the desired separeator index, notice that there are not necessarily valid
457 if(oldLeftI > leftEndIndex || oldRightI > rightEndIndex)
458 return 0;
459 else
460 {
461 ret_sep_left = oldLeftI;
462 ret_sep_right = oldRightI;
463 return 1;
464 }
465}
466
467
468void sampleCompTop(Real* topVertex,
469 vertexArray* leftChain,
470 Int leftStartIndex,
471 vertexArray* rightChain,
472 Int rightStartIndex,
473 gridBoundaryChain* leftGridChain,
474 gridBoundaryChain* rightGridChain,
475 Int gridIndex1,
476 Int up_leftCornerWhere,
477 Int up_leftCornerIndex,
478 Int up_rightCornerWhere,
479 Int up_rightCornerIndex,
480 primStream* pStream)
481{
482 if(up_leftCornerWhere == 1 && up_rightCornerWhere == 1) //the top is topVertex with possible grid points
483 {
484 leftGridChain->getGrid()->outputFanWithPoint(leftGridChain->getVlineIndex(gridIndex1),
485 leftGridChain->getUlineIndex(gridIndex1),
486 rightGridChain->getUlineIndex(gridIndex1),
487 topVertex,
488 pStream);
489 return;
490 }
491
492 else if(up_leftCornerWhere != 0)
493 {
494 Real* tempTop;
495 Int tempRightStart;
496 if(up_leftCornerWhere == 1){
497 tempRightStart = rightStartIndex;
498 tempTop = topVertex;
499 }
500 else
501 {
502 tempRightStart = up_leftCornerIndex+1;
503 tempTop = rightChain->getVertex(up_leftCornerIndex);
504 }
505 sampleTopRightWithGridLine(tempTop, rightChain, tempRightStart, up_rightCornerIndex,
506 rightGridChain->getGrid(),
507 leftGridChain->getVlineIndex(gridIndex1),
508 leftGridChain->getUlineIndex(gridIndex1),
509 rightGridChain->getUlineIndex(gridIndex1),
510 pStream);
511 }
512 else if(up_rightCornerWhere != 2)
513 {
514 Real* tempTop;
515 Int tempLeftStart;
516 if(up_rightCornerWhere == 1)
517 {
518 tempLeftStart = leftStartIndex;
519 tempTop = topVertex;
520 }
521 else //0
522 {
523 tempLeftStart = up_rightCornerIndex+1;
524 tempTop = leftChain->getVertex(up_rightCornerIndex);
525 }
526/*
527 sampleTopLeftWithGridLine(tempTop, leftChain, tempLeftStart, up_leftCornerIndex,
528 leftGridChain->getGrid(),
529 leftGridChain->getVlineIndex(gridIndex1),
530 leftGridChain->getUlineIndex(gridIndex1),
531 rightGridChain->getUlineIndex(gridIndex1),
532 pStream);
533*/
534 sampleCompTopSimple(topVertex,
535 leftChain,
536 leftStartIndex,
537 rightChain,
538 rightStartIndex,
539 leftGridChain,
540 rightGridChain,
541 gridIndex1,
542 up_leftCornerWhere,
543 up_leftCornerIndex,
544 up_rightCornerWhere,
545 up_rightCornerIndex,
546 pStream);
547 }
548 else //up_leftCornerWhere == 0, up_rightCornerWhere == 2.
549 {
550 sampleCompTopSimple(topVertex,
551 leftChain,
552 leftStartIndex,
553 rightChain,
554 rightStartIndex,
555 leftGridChain,
556 rightGridChain,
557 gridIndex1,
558 up_leftCornerWhere,
559 up_leftCornerIndex,
560 up_rightCornerWhere,
561 up_rightCornerIndex,
562 pStream);
563 return;
564#ifdef NOT_REACHABLE //code is not reachable, for test purpose only
565 //the following code is trying to do some optimization, but not quite working, also see sampleCompBot.C:
566 Int sep_left, sep_right;
567 if(findTopSeparator(leftChain,
568 leftStartIndex,
569 up_leftCornerIndex,
570 rightChain,
571 rightStartIndex,
572 up_rightCornerIndex,
573 sep_left,
574 sep_right)
575 ) //separator exists
576 {
577
578 if( leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex1) &&
579 rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex1))
580 {
581 Int gridSep;
582 Int segLeftSmall, segLeftLarge, segRightSmall, segRightLarge;
583 Int valid=1; //whether the gridStep is valid or not.
584 findTopLeftSegment(leftChain,
585 sep_left,
586 up_leftCornerIndex,
587 leftGridChain->get_u_value(gridIndex1),
588 segLeftSmall,
589 segLeftLarge);
590 findTopRightSegment(rightChain,
591 sep_right,
592 up_rightCornerIndex,
593 rightGridChain->get_u_value(gridIndex1),
594 segRightSmall,
595 segRightLarge);
596 if(leftChain->getVertex(segLeftSmall)[1] >= rightChain->getVertex(segRightSmall)[1])
597 {
598 gridSep = rightGridChain->getUlineIndex(gridIndex1);
599 while(leftGridChain->getGrid()->get_u_value(gridSep) > leftChain->getVertex(segLeftSmall)[0])
600 gridSep--;
601 if(segLeftSmall<segLeftLarge)
602 if(leftGridChain->getGrid()->get_u_value(gridSep) < leftChain->getVertex(segLeftSmall+1)[0])
603 {
604 valid = 0;
605 }
606 }
607 else
608 {
609 gridSep = leftGridChain->getUlineIndex(gridIndex1);
610 while(leftGridChain->getGrid()->get_u_value(gridSep) < rightChain->getVertex(segRightSmall)[0])
611 gridSep++;
612 if(segRightSmall<segRightLarge)
613 if(leftGridChain->getGrid()->get_u_value(gridSep) > rightChain->getVertex(segRightSmall+1)[0])
614 {
615 valid = 0;
616 }
617 }
618
619 if(! valid)
620 {
621 sampleCompTopSimple(topVertex,
622 leftChain,
623 leftStartIndex,
624 rightChain,
625 rightStartIndex,
626 leftGridChain,
627 rightGridChain,
628 gridIndex1,
629 up_leftCornerWhere,
630 up_leftCornerIndex,
631 up_rightCornerWhere,
632 up_rightCornerIndex,
633 pStream);
634 }
635 else
636 {
637 sampleTopLeftWithGridLinePost(leftChain->getVertex(segLeftSmall),
638 leftChain,
639 segLeftSmall+1,
640 segLeftSmall+1,
641 segLeftLarge,
642 up_leftCornerIndex,
643 leftGridChain->getGrid(),
644 leftGridChain->getVlineIndex(gridIndex1),
645 leftGridChain->getUlineIndex(gridIndex1),
646 gridSep,
647 pStream);
648 sampleTopRightWithGridLinePost(rightChain->getVertex(segRightSmall),
649 rightChain,
650 segRightSmall+1,
651 segRightSmall+1,
652 segRightLarge,
653 up_rightCornerIndex,
654 leftGridChain->getGrid(),
655 leftGridChain->getVlineIndex(gridIndex1),
656 gridSep,
657 rightGridChain->getUlineIndex(gridIndex1),
658 pStream);
659 Real tempBot[2];
660 tempBot[0] = leftGridChain->getGrid()->get_u_value(gridSep);
661 tempBot[1] = leftGridChain->get_v_value(gridIndex1);
662 monoTriangulationRecGen(topVertex, tempBot,
663 leftChain, leftStartIndex, segLeftSmall,
664 rightChain, rightStartIndex, segRightSmall,
665 pStream);
666 }
667 }//end if both sides have vetices inside the gridboundary points
668 else if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex1)) //left is in, right is nout
669 {
670
671 Int segLeftSmall, segLeftLarge;
672 findTopLeftSegment(leftChain,
673 sep_left,
674 up_leftCornerIndex,
675 leftGridChain->get_u_value(gridIndex1),
676 segLeftSmall,
677 segLeftLarge);
678 assert(segLeftLarge >= sep_left);
679 monoTriangulation2(leftChain->getVertex(segLeftLarge),
680 leftGridChain->get_vertex(gridIndex1),
681 leftChain,
682 segLeftLarge+1,
683 up_leftCornerIndex,
684 1, //a increase chain,
685 pStream);
686
687 stripOfFanLeft(leftChain, segLeftLarge, segLeftSmall,
688 leftGridChain->getGrid(),
689 leftGridChain->getVlineIndex(gridIndex1),
690 leftGridChain->getUlineIndex(gridIndex1),
691 rightGridChain->getUlineIndex(gridIndex1),
692 pStream, 0);
693
694
695 monoTriangulationRecGen(topVertex, rightGridChain->get_vertex(gridIndex1),
696 leftChain, leftStartIndex, segLeftSmall,
697 rightChain, rightStartIndex, up_rightCornerIndex,
698 pStream);
699 }//end left in right out
700 else if(rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex1))
701 {
702 Int segRightSmall, segRightLarge;
703 findTopRightSegment(rightChain,
704 sep_right,
705 up_rightCornerIndex,
706 rightGridChain->get_u_value(gridIndex1),
707 segRightSmall,
708 segRightLarge);
709 assert(segRightLarge>=sep_right);
710 monoTriangulation2(rightChain->getVertex(segRightLarge),
711 rightGridChain->get_vertex(gridIndex1),
712 rightChain,
713 segRightLarge+1,
714 up_rightCornerIndex,
715 0, //a decrease chain
716 pStream);
717 stripOfFanRight(rightChain, segRightLarge, segRightSmall,
718 rightGridChain->getGrid(),
719 rightGridChain->getVlineIndex(gridIndex1),
720 leftGridChain->getUlineIndex(gridIndex1),
721 rightGridChain->getUlineIndex(gridIndex1),
722 pStream, 0);
723
724
725 monoTriangulationRecGen(topVertex, leftGridChain->get_vertex(gridIndex1),
726 leftChain, leftStartIndex, up_leftCornerIndex,
727 rightChain, rightStartIndex,segRightSmall,
728 pStream);
729
730 }//end left out rigth in
731 else //left out , right out
732 {
733
734 sampleCompTopSimple(topVertex,
735 leftChain,
736 leftStartIndex,
737 rightChain,
738 rightStartIndex,
739 leftGridChain,
740 rightGridChain,
741 gridIndex1,
742 up_leftCornerWhere,
743 up_leftCornerIndex,
744 up_rightCornerWhere,
745 up_rightCornerIndex,
746 pStream);
747 }//end leftout, right out
748 }//end if separator exixts.
749 else //no separator
750 {
751
752 sampleCompTopSimple(topVertex,
753 leftChain,
754 leftStartIndex,
755 rightChain,
756 rightStartIndex,
757 leftGridChain,
758 rightGridChain,
759 gridIndex1,
760 up_leftCornerWhere,
761 up_leftCornerIndex,
762 up_rightCornerWhere,
763 up_rightCornerIndex,
764 pStream);
765 }
766#endif
767 }//end if 0,2
768}//end if the function
769
770
772 Int gridV,
773 Real* topVertex, Real* botVertex,
774 vertexArray* inc_chain, Int inc_current, Int inc_end,
775 vertexArray* dec_chain, Int dec_current, Int dec_end,
776 primStream* pStream)
777{
778 if(gridV <= 0 || dec_end<dec_current || inc_end <inc_current)
779 {
780 monoTriangulationRecGenOpt(topVertex, botVertex,
781 inc_chain, inc_current, inc_end,
782 dec_chain, dec_current, dec_end,
783 pStream);
784 return;
785 }
786 if(grid->get_v_value(gridV+1) >= topVertex[1])
787 {
788 monoTriangulationRecGenOpt(topVertex, botVertex,
789 inc_chain, inc_current, inc_end,
790 dec_chain, dec_current, dec_end,
791 pStream);
792 return;
793 }
794 Int i,j,k;
795 Real currentV = grid->get_v_value(gridV+1);
796 if(inc_chain->getVertex(inc_end)[1] <= currentV &&
797 dec_chain->getVertex(dec_end)[1] < currentV)
798 {
799 //find i bottom up so that inc_chain[i]<= curentV and inc_chain[i-1] > currentV,
800 //find j botom up so that dec_chain[j] < currentV and dec_chain[j-1] >= currentV
801 for(i=inc_end; i >= inc_current; i--)
802 {
803 if(inc_chain->getVertex(i)[1] > currentV)
804 break;
805 }
806 i++;
807 for(j=dec_end; j >= dec_current; j--)
808 {
809 if(dec_chain->getVertex(j)[1] >= currentV)
810 break;
811 }
812 j++;
813 if(inc_chain->getVertex(i)[1] <= dec_chain->getVertex(j)[1])
814 {
815 //find the k so that dec_chain[k][1] < inc_chain[i][1]
816 for(k=j; k<=dec_end; k++)
817 {
818 if(dec_chain->getVertex(k)[1] < inc_chain->getVertex(i)[1])
819 break;
820 }
821 //we know that dec_chain[j][1] >= inc_chian[i][1]
822 //we know that dec_chain[k-1][1]>=inc_chain[i][1]
823 //we know that dec_chian[k][1] < inc_chain[i][1]
824 //find l in [j, k-1] so that dec_chain[l][0] 0 is closest to
825 // inc_chain[i]
826 int l;
827 Real tempI = Real(j);
828 Real tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(j)[0]);
829 for(l=j+1; l<= k-1; l++)
830 {
831 if(fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0])
832 <= tempMin)
833 {
834 tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0]);
835 tempI = (Real)l;
836 }
837 }
838 //inc_chain[i] and dec_chain[tempI] are connected.
839 monoTriangulationRecGenOpt(dec_chain->getVertex((int)tempI),
840 botVertex,
841 inc_chain, i, inc_end,
842 dec_chain, (int)(tempI+1), dec_end,
843 pStream);
844 //recursively do the rest
846 gridV+1,
847 topVertex, inc_chain->getVertex(i),
848 inc_chain, inc_current, i-1,
849 dec_chain, dec_current, (int)tempI,
850 pStream);
851 }
852 else
853 {
854 //find the k so that inc_chain[k][1] <= dec_chain[j][1]
855 for(k=i; k<=inc_end; k++)
856 {
857 if(inc_chain->getVertex(k)[1] <= dec_chain->getVertex(j)[1])
858 break;
859 }
860 //we know that inc_chain[i] > dec_chain[j]
861 //we know that inc_chain[k-1][1] > dec_chain[j][1]
862 //we know that inc_chain[k][1] <= dec_chain[j][1]
863 //so we find l between [i,k-1] so that
864 //inc_chain[l][0] is the closet to dec_chain[j][0]
865 int tempI = i;
866 int l;
867 Real tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(j)[0]);
868 for(l=i+1; l<=k-1; l++)
869 {
870 if(fabs(inc_chain->getVertex(l)[0] - dec_chain->getVertex(j)[0]) <= tempMin)
871 {
872 tempMin = (Real)fabs(inc_chain->getVertex(l)[0] - dec_chain->getVertex(j)[0]);
873 tempI = l;
874 }
875 }
876
877 //inc_chain[tempI] and dec_chain[j] are connected
878
879 monoTriangulationRecGenOpt(inc_chain->getVertex(tempI),
880 botVertex,
881 inc_chain, tempI+1, inc_end,
882 dec_chain, j, dec_end,
883 pStream);
884
885 //recurvesily do the rest
886 sampleCompTopSimpleOpt(grid, gridV+1,
887 topVertex, dec_chain->getVertex(j),
888 inc_chain, inc_current, tempI,
889 dec_chain, dec_current, j-1,
890 pStream);
891 }
892 }
893 else //go to the next higher gridV
894 {
896 gridV+1,
897 topVertex, botVertex,
898 inc_chain, inc_current, inc_end,
899 dec_chain, dec_current, dec_end,
900 pStream);
901 }
902}
903
904void sampleCompTopSimple(Real* topVertex,
905 vertexArray* leftChain,
906 Int leftStartIndex,
907 vertexArray* rightChain,
908 Int rightStartIndex,
909 gridBoundaryChain* leftGridChain,
910 gridBoundaryChain* rightGridChain,
911 Int gridIndex1,
912 Int up_leftCornerWhere,
913 Int up_leftCornerIndex,
914 Int up_rightCornerWhere,
915 Int up_rightCornerIndex,
916 primStream* pStream)
917{
918 //the plan is to use monotriangulation algortihm.
919 Int i,k;
920 Real* ActualTop;
921 Real* ActualBot;
922 Int ActualLeftStart, ActualLeftEnd;
923 Int ActualRightStart, ActualRightEnd;
924
925 //creat an array to store the points on the grid line
926 gridWrap* grid = leftGridChain->getGrid();
927 Int gridV = leftGridChain->getVlineIndex(gridIndex1);
928 Int gridLeftU = leftGridChain->getUlineIndex(gridIndex1);
929 Int gridRightU = rightGridChain->getUlineIndex(gridIndex1);
930
931 Real2* gridPoints = (Real2*) malloc(sizeof(Real2) * (gridRightU - gridLeftU +1));
932 assert(gridPoints);
933
934 for(k=0, i=gridRightU; i>= gridLeftU; i--, k++)
935 {
936 gridPoints[k][0] = grid->get_u_value(i);
937 gridPoints[k][1] = grid->get_v_value(gridV);
938 }
939
940 if(up_leftCornerWhere != 2)
941 ActualRightStart = rightStartIndex;
942 else
943 ActualRightStart = up_leftCornerIndex+1; //up_leftCornerIndex will be the ActualTop
944
945 if(up_rightCornerWhere != 2) //right corner is not on right chain
946 ActualRightEnd = rightStartIndex-1; //meaning that there is no actual rigth section
947 else
948 ActualRightEnd = up_rightCornerIndex;
949
950 vertexArray ActualRightChain(max(0, ActualRightEnd-ActualRightStart+1) + gridRightU-gridLeftU+1);
951
952 for(i=ActualRightStart; i<= ActualRightEnd; i++)
953 ActualRightChain.appendVertex(rightChain->getVertex(i));
954 for(i=0; i<gridRightU-gridLeftU+1; i++)
955 ActualRightChain.appendVertex(gridPoints[i]);
956
957 //determine ActualLeftEnd
958 if(up_leftCornerWhere != 0)
959 ActualLeftEnd = leftStartIndex-1;
960 else
961 ActualLeftEnd = up_leftCornerIndex;
962
963 if(up_rightCornerWhere != 0)
964 ActualLeftStart = leftStartIndex;
965 else
966 ActualLeftStart = up_rightCornerIndex+1; //up_rightCornerIndex will be the actual top
967
968 if(up_leftCornerWhere == 0)
969 {
970 if(up_rightCornerWhere == 0)
971 ActualTop = leftChain->getVertex(up_rightCornerIndex);
972 else
973 ActualTop = topVertex;
974 }
975 else if(up_leftCornerWhere == 1)
976 ActualTop = topVertex;
977 else //up_leftCornerWhere == 2
978 ActualTop = rightChain->getVertex(up_leftCornerIndex);
979
980 ActualBot = gridPoints[gridRightU - gridLeftU];
981
982
983
984
985 if(leftChain->getVertex(ActualLeftEnd)[1] == ActualBot[1])
986 {
987/*
988 monoTriangulationRecGenOpt(ActualTop, leftChain->getVertex(ActualLeftEnd),
989 leftChain,
990 ActualLeftStart, ActualLeftEnd-1,
991 &ActualRightChain,
992 0,
993 ActualRightChain.getNumElements()-1,
994 pStream);
995*/
996
997 sampleCompTopSimpleOpt(grid, gridV,
998 ActualTop, leftChain->getVertex(ActualLeftEnd),
999 leftChain,
1000 ActualLeftStart, ActualLeftEnd-1,
1001 &ActualRightChain,
1002 0,
1003 ActualRightChain.getNumElements()-1,
1004 pStream);
1005
1006 }
1007 else
1008 {
1009/*
1010 monoTriangulationRecGenOpt(ActualTop, ActualBot, leftChain,
1011 ActualLeftStart, ActualLeftEnd,
1012 &ActualRightChain,
1013 0, ActualRightChain.getNumElements()-2, //the last is the bot.
1014 pStream);
1015*/
1016
1017 sampleCompTopSimpleOpt(grid, gridV,
1018 ActualTop, ActualBot, leftChain,
1019 ActualLeftStart, ActualLeftEnd,
1020 &ActualRightChain,
1021 0, ActualRightChain.getNumElements()-2, //the last is the bot.
1022 pStream);
1023
1024
1025 }
1026
1027 free(gridPoints);
1028
1029}
1030
r l[0]
Definition: byte_order.h:167
Int getVlineIndex(Int i)
Definition: gridWrap.h:119
Real get_v_value(Int i)
Definition: gridWrap.h:122
Real get_u_value(Int i)
Definition: gridWrap.h:121
Int getUlineIndex(Int i)
Definition: gridWrap.h:120
Real * get_vertex(Int i)
Definition: gridWrap.h:127
gridWrap * getGrid()
Definition: gridWrap.h:128
Real get_v_value(Int j)
Definition: gridWrap.h:83
Real get_u_value(Int i)
Definition: gridWrap.h:78
void outputFanWithPoint(Int v, Int uleft, Int uright, Real vert[2], primStream *pStream)
Definition: gridWrap.cc:137
Real * getVertex(Int i)
void appendVertex(Real *ptr)
#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
#define NULL
Definition: types.h:112
#define assert(x)
Definition: debug.h:53
BOOLEAN valid
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
_Check_return_ _CRT_JIT_INTRINSIC double __cdecl fabs(_In_ double x)
Definition: fabs.c:17
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 monoTriangulation2(Real *topVertex, Real *botVertex, vertexArray *inc_chain, Int inc_smallIndex, Int inc_largeIndex, Int is_increase_chain, primStream *pStream)
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)
int k
Definition: mpi.c:3369
void stripOfFanRight(vertexArray *rightChain, Int largeIndex, Int smallIndex, gridWrap *grid, Int vlineIndex, Int ulineSmallIndex, Int ulineLargeIndex, primStream *pStream, Int gridLineUp)
void sampleCompTopSimple(Real *topVertex, vertexArray *leftChain, Int leftStartIndex, vertexArray *rightChain, Int rightStartIndex, gridBoundaryChain *leftGridChain, gridBoundaryChain *rightGridChain, Int gridIndex1, Int up_leftCornerWhere, Int up_leftCornerIndex, Int up_rightCornerWhere, Int up_rightCornerIndex, primStream *pStream)
Int findTopSeparator(vertexArray *leftChain, Int leftStartIndex, Int leftEndIndex, vertexArray *rightChain, Int rightStartIndex, Int rightEndIndex, Int &ret_sep_left, Int &ret_sep_right)
void sampleTopLeftWithGridLine(Real *topVertex, vertexArray *leftChain, Int leftStart, Int leftEnd, gridWrap *grid, Int gridV, Int leftU, Int rightU, primStream *pStream)
void sampleTopRightWithGridLinePost(Real *topVertex, vertexArray *rightChain, Int rightStart, Int segIndexSmall, Int segIndexLarge, Int rightEnd, gridWrap *grid, Int gridV, Int leftU, Int rightU, primStream *pStream)
void sampleTopLeftWithGridLinePost(Real *topVertex, vertexArray *leftChain, Int leftStart, Int segIndexSmall, Int segIndexLarge, Int leftEnd, gridWrap *grid, Int gridV, Int leftU, Int rightU, primStream *pStream)
void findTopLeftSegment(vertexArray *leftChain, Int leftStart, Int leftEnd, Real u, Int &ret_index_small, Int &ret_index_large)
static void sampleCompTopSimpleOpt(gridWrap *grid, Int gridV, 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 findTopRightSegment(vertexArray *rightChain, Int rightStart, Int rightEnd, Real u, Int &ret_index_small, Int &ret_index_large)
void sampleCompTop(Real *topVertex, vertexArray *leftChain, Int leftStartIndex, vertexArray *rightChain, Int rightStartIndex, gridBoundaryChain *leftGridChain, gridBoundaryChain *rightGridChain, Int gridIndex1, Int up_leftCornerWhere, Int up_leftCornerIndex, Int up_rightCornerWhere, Int up_rightCornerIndex, primStream *pStream)
void sampleTopRightWithGridLine(Real *topVertex, vertexArray *rightChain, Int rightStart, Int rightEnd, gridWrap *grid, Int gridV, Int leftU, Int rightU, primStream *pStream)
#define max(a, b)
void stripOfFanLeft(vertexArray *leftChain, Int largeIndex, Int smallIndex, gridWrap *grid, Int vlineIndex, Int ulineSmallIndex, Int ulineLargeIndex, primStream *pStream, Int gridLineUp)