Synchronize with trunk's revision r57629.
[reactos.git] / dll / opengl / glu32 / src / libnurbs / nurbtess / sampleCompBot.cc
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 "zlassert.h"
41 #include "sampleCompBot.h"
42 #include "sampleCompRight.h"
43
44 #define max(a,b) ((a>b)? a:b)
45
46 //return: index_mono, index_pass
47 //from [pass, mono] is strictly U-monotone
48 //from [corner, pass] is <u
49 // vertex[pass][0] >= u
50 //if everybost is <u, then pass = end+1.
51 //otherwise both mono and pass are meanng full and we have corner<=pass<=mono<=end
52 void findBotLeftSegment(vertexArray* leftChain,
53 Int leftEnd,
54 Int leftCorner,
55 Real u,
56 Int& ret_index_mono,
57 Int& ret_index_pass)
58 {
59 Int i;
60
61 assert(leftCorner <= leftEnd);
62 for(i=leftCorner; i<= leftEnd; i++)
63 if(leftChain->getVertex(i)[0] >= u)
64 break;
65 ret_index_pass = i;
66 if(ret_index_pass <= leftEnd)
67 {
68 for(i=ret_index_pass; i< leftEnd; i++)
69 {
70 if(leftChain->getVertex(i+1)[0] <= leftChain->getVertex(i)[0])
71 break;
72 }
73 ret_index_mono = i;
74 }
75
76 }
77
78 void findBotRightSegment(vertexArray* rightChain,
79 Int rightEnd,
80 Int rightCorner,
81 Real u,
82 Int& ret_index_mono,
83 Int& ret_index_pass)
84 {
85 Int i;
86 assert(rightCorner <= rightEnd);
87 for(i=rightCorner; i<= rightEnd; i++)
88 if(rightChain->getVertex(i)[0] <= u)
89 break;
90
91
92
93 ret_index_pass = i;
94
95 if(ret_index_pass <= rightEnd)
96 {
97 for(i=ret_index_pass; i< rightEnd; i++)
98 {
99 if(rightChain->getVertex(i+1)[0] >= rightChain->getVertex(i)[0])
100 break;
101 }
102 ret_index_mono = i;
103 }
104 }
105
106
107 void sampleBotRightWithGridLinePost(Real* botVertex,
108 vertexArray* rightChain,
109 Int rightEnd,
110 Int segIndexMono,
111 Int segIndexPass,
112 Int rightCorner,
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(segIndexPass > rightCorner) //from corner to pass-1 is > u.
121 {
122 Real *tempBot;
123 if(segIndexPass <= rightEnd) //there is a point to the left of u
124 tempBot = rightChain->getVertex(segIndexPass);
125 else //nothing is to the left of u.
126 tempBot = botVertex;
127 Real tempTop[2];
128 tempTop[0] = grid->get_u_value(rightU);
129 tempTop[1] = grid->get_v_value(gridV);
130
131 monoTriangulation2(tempTop, tempBot,
132 rightChain,
133 rightCorner,
134 segIndexPass-1,
135 0, // a decrease chain
136 pStream);
137 }
138
139 //the possible section which is strictly Umonotone
140 if(segIndexPass <= rightEnd) //segIndex pass and mono exist
141 {
142 //if there are grid points which are to the left of botVertex
143 //then we should use botVertex to form a fan with these points to
144 //optimize the triangulation
145 int do_optimize = 1;
146 if(botVertex[0] <= grid->get_u_value(leftU))
147 do_optimize = 0;
148 else
149 {
150 //we also have to make sure that botVertex is the left most vertex on the chain
151 int i;
152 for(i=segIndexMono; i<=rightEnd; i++)
153 if(rightChain->getVertex(i)[0] <= botVertex[0])
154 {
155 do_optimize = 0;
156 break;
157 }
158 }
159
160 if(do_optimize)
161 {
162 //find midU so that grid->get_u_value(midU) <= botVertex[0]
163 //and grid->get_u_value(midU) > botVertex[0]
164 int midU = leftU;
165 while(grid->get_u_value(midU) <= botVertex[0])
166 {
167 midU++;
168 if(midU > rightU)
169 break;
170 }
171 midU--;
172
173 grid->outputFanWithPoint(gridV, leftU, midU, botVertex, pStream);
174 stripOfFanRight(rightChain, segIndexMono, segIndexPass, grid, gridV, midU, rightU, pStream, 1);
175 Real tempTop[2];
176 tempTop[0] = grid->get_u_value(midU);
177 tempTop[1] = grid->get_v_value(gridV);
178 monoTriangulation2(tempTop, botVertex, rightChain, segIndexMono, rightEnd, 0, pStream);
179 }
180 else //not optimize
181 {
182 stripOfFanRight(rightChain, segIndexMono, segIndexPass, grid, gridV, leftU, rightU, pStream, 1);
183 Real tempTop[2];
184 tempTop[0] = grid->get_u_value(leftU);
185 tempTop[1] = grid->get_v_value(gridV);
186 monoTriangulation2(tempTop, botVertex, rightChain, segIndexMono, rightEnd, 0, pStream);
187 }
188 }
189 else //the botVertex forms a fan witht eh grid points
190 grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
191 }
192
193 void sampleBotRightWithGridLine(Real* botVertex,
194 vertexArray* rightChain,
195 Int rightEnd,
196 Int rightCorner,
197 gridWrap* grid,
198 Int gridV,
199 Int leftU,
200 Int rightU,
201 primStream* pStream)
202 {
203 //if right chaain is empty, then there is only one bot vertex with
204 //one grid line
205 if(rightEnd<rightCorner){
206 grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
207 return;
208 }
209
210 Int segIndexMono = 0, segIndexPass;
211 findBotRightSegment(rightChain,
212 rightEnd,
213 rightCorner,
214 grid->get_u_value(rightU),
215 segIndexMono,
216 segIndexPass);
217
218 sampleBotRightWithGridLinePost(botVertex,
219 rightChain,
220 rightEnd,
221 segIndexMono,
222 segIndexPass,
223 rightCorner,
224 grid,
225 gridV,
226 leftU,
227 rightU,
228 pStream);
229 }
230
231
232 void sampleBotLeftWithGridLinePost(Real* botVertex,
233 vertexArray* leftChain,
234 Int leftEnd,
235 Int segIndexMono,
236 Int segIndexPass,
237 Int leftCorner,
238 gridWrap* grid,
239 Int gridV,
240 Int leftU,
241 Int rightU,
242 primStream* pStream)
243 {
244
245 //the possible section which is to the left of leftU
246 if(segIndexPass > leftCorner) //at least leftCorner is to the left of leftU
247 {
248 Real *tempBot;
249 if(segIndexPass <= leftEnd) //from corner to pass-1 is <u
250 tempBot = leftChain->getVertex(segIndexPass);
251 else //nothing is to the rigth of u
252 tempBot = botVertex;
253 Real tempTop[2];
254 tempTop[0] = grid->get_u_value(leftU);
255 tempTop[1] = grid->get_v_value(gridV);
256 monoTriangulation2(tempTop, tempBot, leftChain, leftCorner, segIndexPass-1,
257 1, //a increase chain,
258 pStream);
259 }
260 //the possible section which is strictly Umonotone
261 if(segIndexPass <= leftEnd) //segIndexpass and mono exist
262 {
263 stripOfFanLeft(leftChain, segIndexMono, segIndexPass, grid, gridV, leftU, rightU, pStream, 1);
264 Real tempTop[2];
265 tempTop[0] = grid->get_u_value(rightU);
266 tempTop[1] = grid->get_v_value(gridV);
267
268 monoTriangulation2(tempTop, botVertex, leftChain, segIndexMono, leftEnd,
269 1, //increase chain
270 pStream);
271 }
272 else //the botVertex forms a fan with the grid points
273 {
274 grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
275 }
276
277 }
278
279 void sampleBotLeftWithGridLine(Real* botVertex,
280 vertexArray* leftChain,
281 Int leftEnd,
282 Int leftCorner,
283 gridWrap* grid,
284 Int gridV,
285 Int leftU,
286 Int rightU,
287 primStream* pStream)
288 {
289
290 //if leftChain is empty, then there is only one botVertex with one grid line
291 if(leftEnd< leftCorner){
292 grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
293 return;
294 }
295
296 Int segIndexPass, segIndexMono = 0;
297 findBotLeftSegment(leftChain, leftEnd, leftCorner, grid->get_u_value(leftU), segIndexMono, segIndexPass);
298
299 sampleBotLeftWithGridLinePost(botVertex,
300 leftChain,
301 leftEnd,
302 segIndexMono,
303 segIndexPass,
304 leftCorner,
305 grid,
306 gridV,
307 leftU, rightU, pStream);
308 }
309
310 //return 1 if separator exists, 0 otherwise
311 Int findBotSeparator(vertexArray* leftChain,
312 Int leftEnd,
313 Int leftCorner,
314 vertexArray* rightChain,
315 Int rightEnd,
316 Int rightCorner,
317 Int& ret_sep_left,
318 Int& ret_sep_right)
319 {
320 Int oldLeftI, oldRightI, newLeftI, newRightI;
321 Int i,j,k;
322 Real leftMax /*= leftChain->getVertex(leftCorner)[0]*/;
323 Real rightMin /*= rightChain->getVertex(rightCorner)[0]*/;
324 if(leftChain->getVertex(leftCorner)[1] < rightChain->getVertex(rightCorner)[1])//leftlower
325 {
326 oldLeftI = leftCorner-1;
327 oldRightI = rightCorner;
328 leftMax = leftChain->getVertex(leftCorner)[0] - Real(1.0) ; //initilize to be left of leftCorner
329 rightMin = rightChain->getVertex(rightCorner)[0];
330 }
331 else //rightlower
332 {
333 oldLeftI = leftCorner;
334 oldRightI = rightCorner-1;
335 leftMax = leftChain->getVertex(leftCorner)[0];
336 rightMin = rightChain->getVertex(rightCorner)[0] + Real(1.0);
337 }
338
339 //i: the current working leftChain Index
340 //j: the curent working right chian index
341 //if(left(i) is lower than right(j), then the two chains above right(j) are separated.
342 //else the two chains below left(i) are separated.
343 i = leftCorner;
344 j = rightCorner;
345 while(1)
346 {
347 newLeftI = oldLeftI;
348 newRightI = oldRightI;
349 if(i> leftEnd) //left chain is doen , go through remaining right chain
350 {
351 for(k=j+1; k<= rightEnd; k++)
352 {
353 if(rightChain->getVertex(k)[0] > leftMax) //no conflict
354 {
355 //update oldRightI if necessary
356 if(rightChain->getVertex(k)[0] < rightMin)
357 {
358 rightMin = rightChain->getVertex(k)[0];
359 oldRightI = k;
360 }
361 }
362 else //there is a conflict
363 break; //the for-loop, above right(k+1) is separated: oldLeftI, oldRightI
364 }
365 break; //the while loop
366 }
367 else if(j > rightEnd) //right Chain is doen
368 {
369 for(k=i+1; k<= leftEnd; k++)
370 {
371 if(leftChain->getVertex(k)[0] < rightMin) //no conflict
372 {
373 //update oldLeftI if necessary
374 if(leftChain->getVertex(k)[0] > leftMax)
375 {
376 leftMax = leftChain->getVertex(k)[0];
377 oldLeftI = k;
378 }
379 }
380 else //there is a conflict
381 break; //the for-loop, above left(k+1) is separated: oldLeftI, oldRightI
382 }
383 break; //the while loop
384 }
385 else if(leftChain->getVertex(i)[1] < rightChain->getVertex(j)[1]) //left lower
386 {
387
388 if(leftChain->getVertex(i)[0] > leftMax) //update leftMax amd newLeftI
389 {
390 leftMax = leftChain->getVertex(i)[0];
391 newLeftI = i;
392 }
393 for(k=j+1; k<= rightEnd; k++) //update rightMin and newRightI;
394 {
395 if(rightChain->getVertex(k)[1] < leftChain->getVertex(i)[1]) //right gets lower
396 break;
397 if(rightChain->getVertex(k)[0] < rightMin)
398 {
399 rightMin = rightChain->getVertex(k)[0];
400 newRightI = k;
401 }
402 }
403 j = k; //next working j, since j will he lower than i in next loop
404 if(leftMax >= rightMin) //there is a conflict
405 break;
406 else //still no conflict
407 {
408 oldLeftI = newLeftI;
409 oldRightI = newRightI;
410
411 }
412 }
413 else //right lower
414 {
415 if(rightChain->getVertex(j)[0] < rightMin)
416 {
417 rightMin = rightChain->getVertex(j)[0];
418 newRightI = j;
419 }
420 for(k=i+1; k<= leftEnd; k++)
421 {
422 if(leftChain->getVertex(k)[1] < rightChain->getVertex(j)[1])
423 break;
424 if(leftChain->getVertex(k)[0] > leftMax)
425 {
426 leftMax = leftChain->getVertex(k)[0];
427 newLeftI = k;
428 }
429 }
430 i=k; //nexct working i, since i will be lower than j next loop
431 if(leftMax >= rightMin) //there is conflict
432 break;
433 else //still no conflict
434 {
435 oldLeftI = newLeftI;
436 oldRightI = newRightI;
437 }
438 }
439 }//end of while loop
440 //now oldLeftI and oldRight I are the desired separator index notice that they are not
441 //necessarily valid
442 if(oldLeftI < leftCorner || oldRightI < rightCorner)
443 return 0; //no separator
444 else
445 {
446 ret_sep_left = oldLeftI;
447 ret_sep_right = oldRightI;
448 return 1;
449 }
450 }
451
452 void sampleCompBot(Real* botVertex,
453 vertexArray* leftChain,
454 Int leftEnd,
455 vertexArray* rightChain,
456 Int rightEnd,
457 gridBoundaryChain* leftGridChain,
458 gridBoundaryChain* rightGridChain,
459 Int gridIndex,
460 Int down_leftCornerWhere,
461 Int down_leftCornerIndex,
462 Int down_rightCornerWhere,
463 Int down_rightCornerIndex,
464 primStream* pStream)
465 {
466
467 if(down_leftCornerWhere == 1 && down_rightCornerWhere == 1) //the bot is botVertex with possible grid points
468 {
469
470 leftGridChain->getGrid()->outputFanWithPoint(leftGridChain->getVlineIndex(gridIndex),
471 leftGridChain->getUlineIndex(gridIndex),
472 rightGridChain->getUlineIndex(gridIndex),
473 botVertex,
474 pStream);
475 return;
476 }
477 else if(down_leftCornerWhere != 0)
478 {
479
480 Real* tempBot;
481 Int tempRightEnd;
482 if(down_leftCornerWhere == 1){
483 tempRightEnd = rightEnd;
484 tempBot = botVertex;
485 }
486 else
487 {
488 tempRightEnd = down_leftCornerIndex-1;
489 tempBot = rightChain->getVertex(down_leftCornerIndex);
490 }
491
492 sampleBotRightWithGridLine(tempBot,
493 rightChain,
494 tempRightEnd,
495 down_rightCornerIndex,
496 rightGridChain->getGrid(),
497 leftGridChain->getVlineIndex(gridIndex),
498 leftGridChain->getUlineIndex(gridIndex),
499 rightGridChain->getUlineIndex(gridIndex),
500 pStream);
501 }
502 else if(down_rightCornerWhere != 2)
503 {
504
505 Real* tempBot;
506 Int tempLeftEnd;
507 if(down_rightCornerWhere == 1){
508 tempLeftEnd = leftEnd;
509 tempBot = botVertex;
510 }
511 else //right corner is on left chain
512 {
513 tempLeftEnd = down_rightCornerIndex-1;
514 tempBot = leftChain->getVertex(down_rightCornerIndex);
515 }
516
517
518 sampleBotLeftWithGridLine(tempBot, leftChain, tempLeftEnd, down_leftCornerIndex,
519 leftGridChain->getGrid(),
520 leftGridChain->getVlineIndex(gridIndex),
521 leftGridChain->getUlineIndex(gridIndex),
522 rightGridChain->getUlineIndex(gridIndex),
523 pStream);
524
525 }
526 else //down_leftCornereWhere == 0, down_rightCornerwhere == 2
527 {
528 sampleCompBotSimple(botVertex,
529 leftChain,
530 leftEnd,
531 rightChain,
532 rightEnd,
533 leftGridChain,
534 rightGridChain,
535 gridIndex,
536 down_leftCornerWhere,
537 down_leftCornerIndex,
538 down_rightCornerWhere,
539 down_rightCornerIndex,
540 pStream);
541
542 return;
543
544 #ifdef NOT_REACHABLE
545 //the following code is trying to do some optimization, but not quite working. so it is not reachable, but leave it here for reference
546 Int sep_left, sep_right;
547 if(findBotSeparator(leftChain, leftEnd, down_leftCornerIndex,
548 rightChain, rightEnd, down_rightCornerIndex,
549 sep_left, sep_right)
550 )//separator exiosts
551 {
552
553 if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex) &&
554 rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex))
555 {
556 Int gridSep;
557 Int segLeftMono, segLeftPass, segRightMono, segRightPass;
558 findBotLeftSegment(leftChain,
559 sep_left,
560 down_leftCornerIndex,
561 leftGridChain->get_u_value(gridIndex),
562 segLeftMono,
563 segLeftPass);
564 findBotRightSegment(rightChain,
565 sep_right,
566 down_rightCornerIndex,
567 rightGridChain->get_u_value(gridIndex),
568 segRightMono,
569 segRightPass);
570 if(leftChain->getVertex(segLeftMono)[1] <= rightChain->getVertex(segRightMono)[1])
571 {
572 gridSep = rightGridChain->getUlineIndex(gridIndex);
573 while(leftGridChain->getGrid()->get_u_value(gridSep) > leftChain->getVertex(segLeftMono)[0])
574 gridSep--;
575 }
576 else
577 {
578 gridSep = leftGridChain->getUlineIndex(gridIndex);
579 while(leftGridChain->getGrid()->get_u_value(gridSep) < rightChain->getVertex(segRightMono)[0])
580 gridSep++;
581 }
582
583 sampleBotLeftWithGridLinePost(leftChain->getVertex(segLeftMono),
584 leftChain,
585 segLeftMono-1,
586 segLeftMono-1,
587 segLeftPass,
588 down_leftCornerIndex,
589 leftGridChain->getGrid(),
590 leftGridChain->getVlineIndex(gridIndex),
591 leftGridChain->getUlineIndex(gridIndex),
592 gridSep,
593 pStream);
594 sampleBotRightWithGridLinePost(rightChain->getVertex(segRightMono),
595 rightChain,
596 segRightMono-1,
597 segRightMono-1,
598 segRightPass,
599 down_rightCornerIndex,
600 rightGridChain->getGrid(),
601 rightGridChain->getVlineIndex(gridIndex),
602 gridSep,
603 rightGridChain->getUlineIndex(gridIndex),
604 pStream);
605 Real tempTop[2];
606 tempTop[0] = leftGridChain->getGrid()->get_u_value(gridSep);
607 tempTop[1] = leftGridChain->get_v_value(gridIndex);
608 monoTriangulationRecGen(tempTop, botVertex,
609 leftChain, segLeftMono, leftEnd,
610 rightChain, segRightMono, rightEnd,
611 pStream);
612 }//end if both sides have vertices inside the gridboundary points
613 else if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex)) //left n right out
614
615 {
616 Int segLeftMono, segLeftPass;
617 findBotLeftSegment(leftChain,
618 sep_left,
619 down_leftCornerIndex,
620 leftGridChain->get_u_value(gridIndex),
621 segLeftMono,
622 segLeftPass);
623 assert(segLeftPass <= sep_left); //make sure there is a point to the right of u.
624 monoTriangulation2(leftGridChain->get_vertex(gridIndex),
625 leftChain->getVertex(segLeftPass),
626 leftChain,
627 down_leftCornerIndex,
628 segLeftPass-1,
629 1, //a increase chain
630 pStream);
631 stripOfFanLeft(leftChain, segLeftMono, segLeftPass,
632 leftGridChain->getGrid(),
633 leftGridChain->getVlineIndex(gridIndex),
634 leftGridChain->getUlineIndex(gridIndex),
635 rightGridChain->getUlineIndex(gridIndex),
636 pStream,1 );
637 /*
638 sampleBotLeftWithGridLinePost(leftChain->getVertex(segLeftMono),
639 leftChain,
640 segLeftMono-1,
641 segLeftMono-1,
642 segLeftPass,
643 down_leftCornerIndex,
644 leftGridChain->getGrid(),
645 leftGridChain->getVlineIndex(gridIndex),
646 leftGridChain->getUlineIndex(gridIndex),
647 rightGridChain->getUlineIndex(gridIndex),
648 pStream);
649 */
650
651 monoTriangulationRecGen(rightGridChain->get_vertex(gridIndex),
652 botVertex,
653 leftChain, segLeftMono, leftEnd,
654 rightChain, down_rightCornerIndex, rightEnd,
655 pStream);
656 }//end left in right out
657 else if(rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex))//left out right in
658 {
659 Int segRightMono, segRightPass;
660 findBotRightSegment(rightChain, sep_right, down_rightCornerIndex,
661 rightGridChain->get_u_value(gridIndex),
662 segRightMono,
663 segRightPass);
664
665 assert(segRightPass <= sep_right); //make sure there is a point to the left of u.
666 monoTriangulation2(rightGridChain->get_vertex(gridIndex),
667 rightChain->getVertex(segRightPass),
668 rightChain,
669 down_rightCornerIndex,
670 segRightPass-1,
671 0, // a decrease chain
672 pStream);
673
674 stripOfFanRight(rightChain, segRightMono, segRightPass,
675 rightGridChain->getGrid(),
676 rightGridChain->getVlineIndex(gridIndex),
677 leftGridChain->getUlineIndex(gridIndex),
678 rightGridChain->getUlineIndex(gridIndex),
679 pStream, 1);
680
681
682 monoTriangulationRecGen(leftGridChain->get_vertex(gridIndex),
683 botVertex,
684 leftChain, down_leftCornerIndex, leftEnd,
685 rightChain, segRightMono, rightEnd,
686 pStream);
687
688 }//end left out right in
689 else //left out, right out
690 {
691 sampleCompBotSimple(botVertex,
692 leftChain,
693 leftEnd,
694 rightChain,
695 rightEnd,
696 leftGridChain,
697 rightGridChain,
698 gridIndex,
699 down_leftCornerWhere,
700 down_leftCornerIndex,
701 down_rightCornerWhere,
702 down_rightCornerIndex,
703 pStream);
704
705 }//end leftout right out
706 }//end if separator exists
707 else //no separator
708 {
709
710 sampleCompBotSimple(botVertex,
711 leftChain,
712 leftEnd,
713 rightChain,
714 rightEnd,
715 leftGridChain,
716 rightGridChain,
717 gridIndex,
718 down_leftCornerWhere,
719 down_leftCornerIndex,
720 down_rightCornerWhere,
721 down_rightCornerIndex,
722 pStream);
723 }
724 #endif
725 }//end id 0 2
726 }//end if the functin
727
728
729 void sampleCompBotSimple(Real* botVertex,
730 vertexArray* leftChain,
731 Int leftEnd,
732 vertexArray* rightChain,
733 Int rightEnd,
734 gridBoundaryChain* leftGridChain,
735 gridBoundaryChain* rightGridChain,
736 Int gridIndex,
737 Int down_leftCornerWhere,
738 Int down_leftCornerIndex,
739 Int down_rightCornerWhere,
740 Int down_rightCornerIndex,
741 primStream* pStream)
742 {
743 //the plan is to use monotriangulation algorithm.
744 Int i,k;
745 Real* ActualTop;
746 Real* ActualBot;
747 Int ActualLeftStart, ActualLeftEnd;
748 Int ActualRightStart, ActualRightEnd;
749
750 //creat an array to store the points on the grid line
751 gridWrap* grid = leftGridChain->getGrid();
752 Int gridV = leftGridChain->getVlineIndex(gridIndex);
753 Int gridLeftU = leftGridChain->getUlineIndex(gridIndex);
754 Int gridRightU = rightGridChain->getUlineIndex(gridIndex);
755 Real2* gridPoints = (Real2*) malloc(sizeof(Real2) * (gridRightU - gridLeftU +1));
756 assert(gridPoints);
757
758 for(k=0, i=gridRightU; i>= gridLeftU; i--, k++)
759 {
760 gridPoints[k][0] = grid->get_u_value(i);
761 gridPoints[k][1] = grid->get_v_value(gridV);
762 }
763
764 if(down_rightCornerWhere != 0) //rightCorner is not on lef
765 ActualLeftEnd = leftEnd;
766 else
767 ActualLeftEnd = down_rightCornerIndex-1; //down_rightCornerIndex will be th actualBot
768
769 if(down_leftCornerWhere != 0) //left corner is not on let chian
770 ActualLeftStart = leftEnd+1; //meaning that there is no actual left section
771 else
772 ActualLeftStart = down_leftCornerIndex;
773
774 vertexArray ActualLeftChain(max(0, ActualLeftEnd - ActualLeftStart +1) + gridRightU - gridLeftU +1);
775
776 for(i=0; i<gridRightU - gridLeftU +1 ; i++)
777 ActualLeftChain.appendVertex(gridPoints[i]);
778 for(i=ActualLeftStart; i<= ActualLeftEnd; i++)
779 ActualLeftChain.appendVertex(leftChain->getVertex(i));
780
781 //determine ActualRightStart
782 if(down_rightCornerWhere != 2) //right is not on right
783 ActualRightStart = rightEnd +1; //meaning no section on right
784 else
785 ActualRightStart = down_rightCornerIndex;
786
787 //determine actualrightEnd
788 if(down_leftCornerWhere != 2) //left is not on right
789 {
790
791 ActualRightEnd = rightEnd;
792 }
793 else //left corner is on right
794 {
795 ActualRightEnd = down_leftCornerIndex-1; //down_leftCornerIndex will be the bot
796
797 }
798
799 //actual bot
800 if(down_rightCornerWhere == 2)
801 {
802 if(down_leftCornerWhere == 2)
803 ActualBot = rightChain->getVertex(down_leftCornerIndex);
804 else
805 ActualBot = botVertex;
806 }
807 else if(down_rightCornerWhere == 1) //right corner bot
808 ActualBot = botVertex;
809 else //down_rightCornerWhere == 0
810 ActualBot = leftChain->getVertex(down_rightCornerIndex);
811
812 ActualTop = gridPoints[0];
813 /*
814 printf("in bot simple, actual leftChain is \n");
815 ActualLeftChain.print();
816 printf("Actual Top = %f,%f\n", ActualTop[0],ActualTop[1]);
817 printf("Actual Bot = %f,%f\n", ActualBot[0],ActualBot[1]);
818 printf("Actual right start = %i, end=%i\n",ActualRightStart, ActualRightEnd);
819 */
820 if(rightChain->getVertex(ActualRightStart)[1] == ActualTop[1])
821 monoTriangulationRecGenOpt(rightChain->getVertex(ActualRightStart),
822 ActualBot,
823 &ActualLeftChain,
824 0,
825 ActualLeftChain.getNumElements()-1,
826 rightChain,
827 ActualRightStart+1,
828 ActualRightEnd,
829 pStream);
830 else
831 monoTriangulationRecGenOpt(ActualTop, ActualBot,
832 &ActualLeftChain,
833 1, //the first one is the top vertex
834 ActualLeftChain.getNumElements()-1,
835 rightChain,
836 ActualRightStart,
837 ActualRightEnd,
838 pStream);
839 free(gridPoints);
840 }
841
842
843
844