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
findTopLeftSegment(vertexArray * leftChain,Int leftStart,Int leftEnd,Real u,Int & ret_index_small,Int & ret_index_large)53 void findTopLeftSegment(vertexArray* leftChain,
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
findTopRightSegment(vertexArray * rightChain,Int rightStart,Int rightEnd,Real u,Int & ret_index_small,Int & ret_index_large)80 void findTopRightSegment(vertexArray* rightChain,
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
sampleTopRightWithGridLinePost(Real * topVertex,vertexArray * rightChain,Int rightStart,Int segIndexSmall,Int segIndexLarge,Int rightEnd,gridWrap * grid,Int gridV,Int leftU,Int rightU,primStream * pStream)107 void sampleTopRightWithGridLinePost(Real* topVertex,
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);
130 monoTriangulationRecGenOpt(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
sampleTopRightWithGridLine(Real * topVertex,vertexArray * rightChain,Int rightStart,Int rightEnd,gridWrap * grid,Int gridV,Int leftU,Int rightU,primStream * pStream)158 void sampleTopRightWithGridLine(Real* topVertex,
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
sampleTopLeftWithGridLinePost(Real * topVertex,vertexArray * leftChain,Int leftStart,Int segIndexSmall,Int segIndexLarge,Int leftEnd,gridWrap * grid,Int gridV,Int leftU,Int rightU,primStream * pStream)196 void sampleTopLeftWithGridLinePost(Real* topVertex,
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
sampleTopLeftWithGridLine(Real * topVertex,vertexArray * leftChain,Int leftStart,Int leftEnd,gridWrap * grid,Int gridV,Int leftU,Int rightU,primStream * pStream)286 void sampleTopLeftWithGridLine(Real* topVertex,
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 );
311 sampleTopLeftWithGridLinePost(topVertex,
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
findTopSeparator(vertexArray * leftChain,Int leftStartIndex,Int leftEndIndex,vertexArray * rightChain,Int rightStartIndex,Int rightEndIndex,Int & ret_sep_left,Int & ret_sep_right)326 Int findTopSeparator(vertexArray* leftChain,
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
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)468 void 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
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)771 static void sampleCompTopSimpleOpt(gridWrap* grid,
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
845 sampleCompTopSimpleOpt(grid,
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 {
895 sampleCompTopSimpleOpt(grid,
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
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)904 void 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
1031