← Back to branch summary

~gma500/+junk/gma500-maverick

« back to all changes in this revision

Viewing changes to xpsb-glx/mesa/src/glu/sgi/libnurbs/nurbtess/sampleCompBot.cc

  • Committer: Luca Forina
  • Date: 2011-02-14 09:55:00 UTC
  • Revision ID: luca.forina@gmail.com-20110214095500-kq7o333fbjuoquqs
new commit

Show diffs side-by-side

added added

removed removed

Lines of Context:
xpsb-glx/mesa/src/glu/sgi/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, 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;
 
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