sampleCompBot.cc revision f220fa62 
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
52void 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
78void 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
107void 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
193void 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
232void 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
279void 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
311Int 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
452void 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
729void 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/*
814printf("in bot simple, actual leftChain is \n");
815ActualLeftChain.print();
816printf("Actual Top = %f,%f\n", ActualTop[0],ActualTop[1]);
817printf("Actual Bot = %f,%f\n", ActualBot[0],ActualBot[1]);
818printf("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
845