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
53void 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
80void 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
107void 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);
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
158void 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
196void 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
286void 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
326Int 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
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
771static 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
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
1031