src/glu/sgi/libnurbs/nurbtess/sampleCompTop.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 <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
  53 void findTopLeftSegment(vertexArray* leftChain,
  54                         Int leftStart,
  55                         Int leftEnd,
  56                         Real u,
  57                         Int& ret_index_small,
  58                         Int& ret_index_large
  59                         )
  60 {
  61   Int i;
  62   assert(leftStart <= leftEnd);
  63   for(i=leftEnd; i>= leftStart; i--)
  64     {
  65       if(leftChain->getVertex(i)[0] >= u)
  66         break;
  67     }
  68   ret_index_large = i;
  69   if(ret_index_large >= leftStart)
  70     {
  71       for(i=ret_index_large; i>leftStart; i--)
  72         {
  73           if(leftChain->getVertex(i-1)[0] <= leftChain->getVertex(i)[0])
  74             break;
  75         }
  76       ret_index_small = i;
  77     }
  78 }
  79
  80 void findTopRightSegment(vertexArray* rightChain,
  81                          Int rightStart,
  82                          Int rightEnd,
  83                          Real u,
  84                          Int& ret_index_small,
  85                          Int& ret_index_large)
  86 {
  87   Int i;
  88   assert(rightStart<=rightEnd);
  89   for(i=rightEnd; i>=rightStart; i--)
  90     {
  91       if(rightChain->getVertex(i)[0] <= u)
  92         break;
  93     }
  94   ret_index_large = i;
  95   if(ret_index_large >= rightStart)
  96     {
  97       for(i=ret_index_large; i>rightStart;i--)
  98         {
  99           if(rightChain->getVertex(i-1)[0] >= rightChain->getVertex(i)[0])
 100             break;
 101         }
 102       ret_index_small = i;
 103     }
 104 }
 105
 106
 107 void sampleTopRightWithGridLinePost(Real* topVertex,
 108                                    vertexArray* rightChain,
 109                                    Int rightStart,
 110                                    Int segIndexSmall,
 111                                    Int segIndexLarge,
 112                                    Int rightEnd,
 113                                    gridWrap* grid,
 114                                    Int gridV,
 115                                    Int leftU,
 116                                    Int rightU,
 117                                    primStream* pStream)
 118 {
 119   //the possible section which is to the right of rightU
 120   if(segIndexLarge < rightEnd)
 121     {
 122       Real *tempTop;
 123       if(segIndexLarge >= rightStart)
 124         tempTop = rightChain->getVertex(segIndexLarge);
 125       else
 126         tempTop = topVertex;
 127       Real tempBot[2];
 128       tempBot[0] = grid->get_u_value(rightU);
 129       tempBot[1] = grid->get_v_value(gridV);
 130 monoTriangulationRecGenOpt(tempTop, tempBot,
 131                            NULL, 1,0,
 132                            rightChain, segIndexLarge+1, rightEnd,
 133                            pStream);
 134 /*
 135       monoTriangulation2(tempTop, tempBot,
 136                          rightChain,
 137                          segIndexLarge+1,
 138                          rightEnd,
 139                          0, //a decrease  chian
 140                          pStream);
 141 */
 142
 143     }
 144
 145   //the possible section which is strictly Umonotone
 146   if(segIndexLarge >= rightStart)
 147     {
 148       stripOfFanRight(rightChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, rightU, pStream, 0);
 149       Real tempBot[2];
 150       tempBot[0] = grid->get_u_value(leftU);
 151       tempBot[1] = grid->get_v_value(gridV);
 152       monoTriangulation2(topVertex, tempBot, rightChain, rightStart, segIndexSmall, 0, pStream);
 153     }
 154   else //the topVertex forms a fan with the grid points
 155     grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
 156 }
 157
 158 void sampleTopRightWithGridLine(Real* topVertex,
 159                                 vertexArray* rightChain,
 160                                 Int rightStart,
 161                                 Int rightEnd,
 162                                 gridWrap* grid,
 163                                 Int gridV,
 164                                 Int leftU,
 165                                 Int rightU,
 166                                 primStream* pStream
 167                                 )
 168 {
 169   //if right chian is empty, then there is only one topVertex with one grid line
 170   if(rightEnd < rightStart){
 171     grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
 172     return;
 173   }
 174
 175   Int segIndexSmall = 0, segIndexLarge;
 176   findTopRightSegment(rightChain,
 177                       rightStart,
 178                       rightEnd,
 179                       grid->get_u_value(rightU),
 180                       segIndexSmall,
 181                       segIndexLarge
 182                       );
 183   sampleTopRightWithGridLinePost(topVertex, rightChain,
 184                                  rightStart,
 185                                  segIndexSmall,
 186                                  segIndexLarge,
 187                                  rightEnd,
 188                                  grid,
 189                                  gridV,
 190                                  leftU,
 191                                  rightU,
 192                                  pStream);
 193 }
 194
 195
 196 void sampleTopLeftWithGridLinePost(Real* topVertex,
 197                                    vertexArray* leftChain,
 198                                    Int leftStart,
 199                                    Int segIndexSmall,
 200                                    Int segIndexLarge,
 201                                    Int leftEnd,
 202                                    gridWrap* grid,
 203                                    Int gridV,
 204                                    Int leftU,
 205                                    Int rightU,
 206                                    primStream* pStream)
 207 {
 208   //the possible section which is to the left of leftU
 209
 210   if(segIndexLarge < leftEnd)
 211     {
 212       Real *tempTop;
 213       if(segIndexLarge >= leftStart)
 214         tempTop = leftChain->getVertex(segIndexLarge);
 215       else
 216         tempTop = topVertex;
 217       Real tempBot[2];
 218       tempBot[0] = grid->get_u_value(leftU);
 219       tempBot[1] = grid->get_v_value(gridV);
 220
 221       monoTriangulation2(tempTop, tempBot,
 222                          leftChain,
 223                          segIndexLarge+1,
 224                          leftEnd,
 225                          1, //a increase  chian
 226                          pStream);
 227     }
 228
 229   //the possible section which is strictly Umonotone
 230   if(segIndexLarge >= leftStart)
 231     {
 232       //if there are grid points which are to the right of topV,
 233       //then we should use topVertex to form a fan with these points to
 234       //optimize the triangualtion
 235       int do_optimize=1;
 236       if(topVertex[0] >= grid->get_u_value(rightU))
 237         do_optimize = 0;
 238       else
 239         {
 240           //we also have to make sure that topVertex are the right most vertex
 241           //on the chain.
 242           int i;
 243           for(i=leftStart; i<=segIndexSmall; i++)
 244             if(leftChain->getVertex(i)[0] >= topVertex[0])
 245               {
 246                 do_optimize = 0;
 247                 break;
 248               }
 249         }
 250
 251       if(do_optimize)
 252         {
 253           //find midU so that grid->get_u_value(midU) >= topVertex[0]
 254           //and               grid->get_u_value(midU-1) < topVertex[0]
 255           int midU=rightU;
 256           while(grid->get_u_value(midU) >= topVertex[0])
 257             {
 258               midU--;
 259               if(midU < leftU)
 260                 break;
 261             }
 262           midU++;
 263
 264           grid->outputFanWithPoint(gridV, midU, rightU, topVertex, pStream);
 265           stripOfFanLeft(leftChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, midU, pStream, 0);
 266           Real tempBot[2];
 267           tempBot[0] = grid->get_u_value(midU);
 268           tempBot[1] = grid->get_v_value(gridV);
 269           monoTriangulation2(topVertex, tempBot, leftChain, leftStart, segIndexSmall, 1, pStream);
 270         }
 271       else //not optimize
 272         {
 273
 274           stripOfFanLeft(leftChain, segIndexLarge, segIndexSmall, grid, gridV, leftU, rightU, pStream, 0);
 275           Real tempBot[2];
 276           tempBot[0] = grid->get_u_value(rightU);
 277           tempBot[1] = grid->get_v_value(gridV);
 278           monoTriangulation2(topVertex, tempBot, leftChain, leftStart, segIndexSmall, 1, pStream);
 279         }
 280     }
 281   else //the topVertex forms a fan with the grid points
 282     grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
 283 }
 284
 285
 286 void sampleTopLeftWithGridLine(Real* topVertex,
 287                                 vertexArray* leftChain,
 288                                 Int leftStart,
 289                                 Int leftEnd,
 290                                 gridWrap* grid,
 291                                 Int gridV,
 292                                 Int leftU,
 293                                 Int rightU,
 294                                 primStream* pStream
 295                                 )
 296 {
 297   Int segIndexSmall = 0, segIndexLarge;
 298   //if left chain is empty, then there is only one top vertex with one grid
 299   //  line
 300   if(leftEnd < leftStart) {
 301     grid->outputFanWithPoint(gridV, leftU, rightU, topVertex, pStream);
 302     return;
 303   }
 304   findTopLeftSegment(leftChain,
 305                       leftStart,
 306                       leftEnd,
 307                       grid->get_u_value(leftU),
 308                       segIndexSmall,
 309                       segIndexLarge
 310                       );
 311   sampleTopLeftWithGridLinePost(topVertex,
 312                                 leftChain,
 313                                 leftStart,
 314                                 segIndexSmall,
 315                                 segIndexLarge,
 316                                 leftEnd,
 317                                 grid,
 318                                 gridV,
 319                                 leftU,
 320                                 rightU,
 321                                 pStream);
 322 }
 323
 324
 325 //return 1 if saprator exits, 0 otherwise
 326 Int findTopSeparator(vertexArray* leftChain,
 327                      Int leftStartIndex,
 328                      Int leftEndIndex,
 329                      vertexArray* rightChain,
 330                      Int rightStartIndex,
 331                      Int rightEndIndex,
 332                      Int& ret_sep_left,
 333                      Int& ret_sep_right)
 334 {
 335
 336   Int oldLeftI, oldRightI, newLeftI, newRightI;
 337   Int i,j,k;
 338   Real leftMax /*= leftChain->getVertex(leftEndIndex)[0]*/;
 339   Real rightMin /*= rightChain->getVertex(rightEndIndex)[0]*/;
 340   if(leftChain->getVertex(leftEndIndex)[1] > rightChain->getVertex(rightEndIndex)[1]) //left higher
 341     {
 342       oldLeftI = leftEndIndex+1;
 343       oldRightI = rightEndIndex;
 344       leftMax =  leftChain->getVertex(leftEndIndex)[0] - Real(1.0); //initilza to left of leftU
 345       rightMin = rightChain->getVertex(rightEndIndex)[0];
 346     }
 347   else
 348     {
 349       oldLeftI = leftEndIndex;
 350       oldRightI = rightEndIndex+1;
 351       leftMax =  leftChain->getVertex(leftEndIndex)[0];
 352       rightMin = rightChain->getVertex(rightEndIndex)[0] + Real(1.0);
 353     }
 354
 355   //i: the current working leftChain index,
 356   //j: the current working rightChain index,
 357   //if left(i) is higher than right(j), then the two chains beloew right(j) are separated.
 358   //else the two chains below left(i) are separeated.
 359   i=leftEndIndex;
 360   j=rightEndIndex;
 361   while(1)
 362     {
 363       newLeftI = oldLeftI;
 364       newRightI = oldRightI;
 365
 366       if(i<leftStartIndex) //left chain is done, go through remining right chain.
 367         {
 368           for(k=j-1; k>= rightStartIndex; k--)
 369             {
 370               if(rightChain->getVertex(k)[0] > leftMax) //no conflict
 371                 {
 372                   //update oldRightI if necessary
 373                   if(rightChain->getVertex(k)[0] < rightMin)
 374                     {
 375                       rightMin = rightChain->getVertex(k)[0];
 376                       oldRightI = k;
 377                     }
 378                 }
 379               else  //there is a conflict
 380                 break; //the for-loop. below right(k-1) is seperated: oldLeftI, oldRightI.
 381             }
 382           break; //the while loop
 383         }
 384       else if(j<rightStartIndex) //rightChain is done
 385         {
 386           for(k=i-1; k>= leftStartIndex; k--)
 387             {
 388               if(leftChain->getVertex(k)[0] < rightMin) //no conflict
 389                 {
 390                   //update oldLeftI if necessary
 391                   if(leftChain->getVertex(k)[0] > leftMax)
 392                     {
 393                       leftMax = leftChain->getVertex(k)[0];
 394                       oldLeftI = k;
 395                     }
 396                 }
 397               else //there is a conflict
 398                 break; //the for loop
 399             }
 400           break; //the while loop
 401         }
 402       else if(leftChain->getVertex(i)[1] > rightChain->getVertex(j)[1]) //left hgiher
 403         {
 404           if(leftChain->getVertex(i)[0] > leftMax) //update leftMax and newLeftI.
 405             {
 406               leftMax = leftChain->getVertex(i)[0];
 407               newLeftI = i;
 408             }
 409           for(k=j-1; k>= rightStartIndex; k--) //update rightMin and newRightI.
 410             {
 411               if(rightChain->getVertex(k)[1] > leftChain->getVertex(i)[1])
 412                 break;
 413               if(rightChain->getVertex(k)[0] < rightMin)
 414                 {
 415                   rightMin = rightChain->getVertex(k)[0];
 416                   newRightI = k;
 417                 }
 418             }
 419           j = k; //next working j, since j will be higher than i in next loop
 420           if(leftMax >= rightMin) //there is a conflict
 421             break;
 422           else //still no conflict
 423             {
 424               oldLeftI = newLeftI;
 425               oldRightI = newRightI;
 426             }
 427         }
 428       else //right higher
 429         {
 430           if(rightChain->getVertex(j)[0] < rightMin)
 431             {
 432               rightMin = rightChain->getVertex(j)[0];
 433               newRightI = j;
 434             }
 435           for(k=i-1; k>= leftStartIndex; k--)
 436             {
 437               if(leftChain->getVertex(k)[1] > rightChain->getVertex(j)[1])
 438                 break;
 439               if(leftChain->getVertex(k)[0] > leftMax)
 440                 {
 441                   leftMax = leftChain->getVertex(k)[0];
 442                   newLeftI = k;
 443                 }
 444             }
 445           i = k; //next working i, since i will be higher than j next loop
 446
 447           if(leftMax >= rightMin) //there is a conflict
 448             break;
 449           else //still no conflict
 450             {
 451               oldLeftI = newLeftI;
 452               oldRightI = newRightI;
 453             }
 454         }
 455     }//end of while loop
 456   //now oldLeftI and oldRightI are the desired separeator index, notice that there are not necessarily valid
 457   if(oldLeftI > leftEndIndex || oldRightI > rightEndIndex)
 458     return 0;
 459   else
 460     {
 461       ret_sep_left = oldLeftI;
 462       ret_sep_right = oldRightI;
 463       return 1;
 464     }
 465 }
 466
 467
 468 void sampleCompTop(Real* topVertex,
 469                    vertexArray* leftChain,
 470                    Int leftStartIndex,
 471                    vertexArray* rightChain,
 472                    Int rightStartIndex,
 473                    gridBoundaryChain* leftGridChain,
 474                    gridBoundaryChain* rightGridChain,
 475                    Int gridIndex1,
 476                    Int up_leftCornerWhere,
 477                    Int up_leftCornerIndex,
 478                    Int up_rightCornerWhere,
 479                    Int up_rightCornerIndex,
 480                    primStream* pStream)
 481 {
 482   if(up_leftCornerWhere == 1 && up_rightCornerWhere == 1) //the top is topVertex with possible grid points
 483     {
 484       leftGridChain->getGrid()->outputFanWithPoint(leftGridChain->getVlineIndex(gridIndex1),
 485                                                    leftGridChain->getUlineIndex(gridIndex1),
 486                                                    rightGridChain->getUlineIndex(gridIndex1),
 487                                                    topVertex,
 488                                                    pStream);
 489       return;
 490     }
 491
 492   else if(up_leftCornerWhere != 0)
 493     {
 494       Real* tempTop;
 495       Int tempRightStart;
 496       if(up_leftCornerWhere == 1){
 497         tempRightStart = rightStartIndex;
 498         tempTop = topVertex;
 499       }
 500       else
 501         {
 502           tempRightStart = up_leftCornerIndex+1;
 503           tempTop = rightChain->getVertex(up_leftCornerIndex);
 504         }
 505       sampleTopRightWithGridLine(tempTop, rightChain, tempRightStart, up_rightCornerIndex,
 506                                  rightGridChain->getGrid(),
 507                                  leftGridChain->getVlineIndex(gridIndex1),
 508                                  leftGridChain->getUlineIndex(gridIndex1),
 509                                  rightGridChain->getUlineIndex(gridIndex1),
 510                                  pStream);
 511     }
 512   else if(up_rightCornerWhere != 2)
 513     {
 514       Real* tempTop;
 515       Int tempLeftStart;
 516       if(up_rightCornerWhere == 1)
 517         {
 518           tempLeftStart = leftStartIndex;
 519           tempTop = topVertex;
 520         }
 521       else //0
 522         {
 523           tempLeftStart = up_rightCornerIndex+1;
 524           tempTop = leftChain->getVertex(up_rightCornerIndex);
 525         }
 526 /*
 527       sampleTopLeftWithGridLine(tempTop, leftChain, tempLeftStart, up_leftCornerIndex,
 528                                 leftGridChain->getGrid(),
 529                                  leftGridChain->getVlineIndex(gridIndex1),
 530                                  leftGridChain->getUlineIndex(gridIndex1),
 531                                  rightGridChain->getUlineIndex(gridIndex1),
 532                                  pStream);
 533 */
 534       sampleCompTopSimple(topVertex,
 535                           leftChain,
 536                           leftStartIndex,
 537                           rightChain,
 538                           rightStartIndex,
 539                           leftGridChain,
 540                           rightGridChain,
 541                           gridIndex1,
 542                           up_leftCornerWhere,
 543                           up_leftCornerIndex,
 544                           up_rightCornerWhere,
 545                           up_rightCornerIndex,
 546                           pStream);
 547     }
 548   else //up_leftCornerWhere == 0, up_rightCornerWhere == 2.
 549     {
 550       sampleCompTopSimple(topVertex,
 551                           leftChain,
 552                           leftStartIndex,
 553                           rightChain,
 554                           rightStartIndex,
 555                           leftGridChain,
 556                           rightGridChain,
 557                           gridIndex1,
 558                           up_leftCornerWhere,
 559                           up_leftCornerIndex,
 560                           up_rightCornerWhere,
 561                           up_rightCornerIndex,
 562                           pStream);
 563       return;
 564 #ifdef NOT_REACHABLE //code is not reachable, for test purpose only
 565       //the following code is trying to do some optimization, but not quite working, also see sampleCompBot.C:
 566       Int sep_left, sep_right;
 567       if(findTopSeparator(leftChain,
 568                           leftStartIndex,
 569                           up_leftCornerIndex,
 570                           rightChain,
 571                           rightStartIndex,
 572                           up_rightCornerIndex,
 573                           sep_left,
 574                           sep_right)
 575          ) //separator exists
 576         {
 577
 578           if( leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex1) &&
 579              rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex1))
 580             {
 581               Int gridSep;
 582               Int segLeftSmall, segLeftLarge, segRightSmall, segRightLarge;
 583               Int valid=1; //whether the gridStep is valid or not.
 584               findTopLeftSegment(leftChain,
 585                                  sep_left,
 586                                  up_leftCornerIndex,
 587                                  leftGridChain->get_u_value(gridIndex1),
 588                                  segLeftSmall,
 589                                  segLeftLarge);
 590               findTopRightSegment(rightChain,
 591                                  sep_right,
 592                                  up_rightCornerIndex,
 593                                  rightGridChain->get_u_value(gridIndex1),
 594                                  segRightSmall,
 595                                  segRightLarge);
 596               if(leftChain->getVertex(segLeftSmall)[1] >= rightChain->getVertex(segRightSmall)[1])
 597                 {
 598                   gridSep = rightGridChain->getUlineIndex(gridIndex1);
 599                   while(leftGridChain->getGrid()->get_u_value(gridSep) > leftChain->getVertex(segLeftSmall)[0])
 600                     gridSep--;
 601                   if(segLeftSmall<segLeftLarge)
 602                     if(leftGridChain->getGrid()->get_u_value(gridSep) < leftChain->getVertex(segLeftSmall+1)[0])
 603                       {
 604                         valid = 0;
 605                       }
 606                 }
 607               else
 608                 {
 609                   gridSep = leftGridChain->getUlineIndex(gridIndex1);
 610                   while(leftGridChain->getGrid()->get_u_value(gridSep) < rightChain->getVertex(segRightSmall)[0])
 611                     gridSep++;
 612                   if(segRightSmall<segRightLarge)
 613                     if(leftGridChain->getGrid()->get_u_value(gridSep) > rightChain->getVertex(segRightSmall+1)[0])
 614                       {
 615                         valid = 0;
 616                       }
 617                 }
 618
 619               if(! valid)
 620                 {
 621                   sampleCompTopSimple(topVertex,
 622                                       leftChain,
 623                                       leftStartIndex,
 624                                       rightChain,
 625                                       rightStartIndex,
 626                                       leftGridChain,
 627                                       rightGridChain,
 628                                       gridIndex1,
 629                                       up_leftCornerWhere,
 630                                       up_leftCornerIndex,
 631                                       up_rightCornerWhere,
 632                                       up_rightCornerIndex,
 633                                       pStream);
 634                 }
 635               else
 636                 {
 637                   sampleTopLeftWithGridLinePost(leftChain->getVertex(segLeftSmall),
 638                                                 leftChain,
 639                                                 segLeftSmall+1,
 640                                                 segLeftSmall+1,
 641                                                 segLeftLarge,
 642                                                 up_leftCornerIndex,
 643                                                 leftGridChain->getGrid(),
 644                                                 leftGridChain->getVlineIndex(gridIndex1),
 645                                                 leftGridChain->getUlineIndex(gridIndex1),
 646                                                 gridSep,
 647                                                 pStream);
 648                   sampleTopRightWithGridLinePost(rightChain->getVertex(segRightSmall),
 649                                                  rightChain,
 650                                                  segRightSmall+1,
 651                                                  segRightSmall+1,
 652                                                  segRightLarge,
 653                                                  up_rightCornerIndex,
 654                                                  leftGridChain->getGrid(),
 655                                                  leftGridChain->getVlineIndex(gridIndex1),
 656                                                  gridSep,
 657                                                  rightGridChain->getUlineIndex(gridIndex1),
 658                                                  pStream);
 659                   Real tempBot[2];
 660                   tempBot[0] = leftGridChain->getGrid()->get_u_value(gridSep);
 661                   tempBot[1] = leftGridChain->get_v_value(gridIndex1);
 662                   monoTriangulationRecGen(topVertex, tempBot,
 663                                           leftChain, leftStartIndex, segLeftSmall,
 664                                           rightChain, rightStartIndex, segRightSmall,
 665                                           pStream);
 666                 }
 667             }//end if both sides have vetices inside the gridboundary points
 668           else if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex1)) //left is in, right is nout
 669             {
 670
 671               Int segLeftSmall, segLeftLarge;
 672               findTopLeftSegment(leftChain,
 673                                  sep_left,
 674                                  up_leftCornerIndex,
 675                                  leftGridChain->get_u_value(gridIndex1),
 676                                  segLeftSmall,
 677                                  segLeftLarge);
 678               assert(segLeftLarge >= sep_left);
 679               monoTriangulation2(leftChain->getVertex(segLeftLarge),
 680                                  leftGridChain->get_vertex(gridIndex1),
 681                                  leftChain,
 682                                  segLeftLarge+1,
 683                                  up_leftCornerIndex,
 684                                  1, //a increase chain,
 685                                  pStream);
 686
 687               stripOfFanLeft(leftChain, segLeftLarge, segLeftSmall,
 688                              leftGridChain->getGrid(),
 689                              leftGridChain->getVlineIndex(gridIndex1),
 690                              leftGridChain->getUlineIndex(gridIndex1),
 691                              rightGridChain->getUlineIndex(gridIndex1),
 692                              pStream, 0);
 693
 694
 695               monoTriangulationRecGen(topVertex, rightGridChain->get_vertex(gridIndex1),
 696                                       leftChain, leftStartIndex, segLeftSmall,
 697                                       rightChain, rightStartIndex, up_rightCornerIndex,
 698                                       pStream);
 699             }//end left in right out
 700           else if(rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex1))
 701             {
 702               Int segRightSmall, segRightLarge;
 703               findTopRightSegment(rightChain,
 704                                  sep_right,
 705                                  up_rightCornerIndex,
 706                                  rightGridChain->get_u_value(gridIndex1),
 707                                  segRightSmall,
 708                                  segRightLarge);
 709               assert(segRightLarge>=sep_right);
 710               monoTriangulation2(rightChain->getVertex(segRightLarge),
 711                                  rightGridChain->get_vertex(gridIndex1),
 712                                  rightChain,
 713                                  segRightLarge+1,
 714                                  up_rightCornerIndex,
 715                                  0, //a decrease chain
 716                                  pStream);
 717               stripOfFanRight(rightChain, segRightLarge, segRightSmall,
 718                               rightGridChain->getGrid(),
 719                               rightGridChain->getVlineIndex(gridIndex1),
 720                               leftGridChain->getUlineIndex(gridIndex1),
 721                               rightGridChain->getUlineIndex(gridIndex1),
 722                               pStream, 0);
 723
 724
 725               monoTriangulationRecGen(topVertex, leftGridChain->get_vertex(gridIndex1),
 726                                       leftChain, leftStartIndex, up_leftCornerIndex,
 727                                       rightChain, rightStartIndex,segRightSmall,
 728                                       pStream);
 729
 730             }//end left out rigth in
 731           else //left out , right out
 732             {
 733
 734               sampleCompTopSimple(topVertex,
 735                                   leftChain,
 736                                   leftStartIndex,
 737                                   rightChain,
 738                                   rightStartIndex,
 739                                   leftGridChain,
 740                                   rightGridChain,
 741                                   gridIndex1,
 742                                   up_leftCornerWhere,
 743                                   up_leftCornerIndex,
 744                                   up_rightCornerWhere,
 745                                   up_rightCornerIndex,
 746                                   pStream);
 747             }//end leftout, right out
 748         }//end if separator exixts.
 749       else //no separator
 750         {
 751
 752           sampleCompTopSimple(topVertex,
 753                             leftChain,
 754                               leftStartIndex,
 755                               rightChain,
 756                               rightStartIndex,
 757                               leftGridChain,
 758                               rightGridChain,
 759                               gridIndex1,
 760                             up_leftCornerWhere,
 761                               up_leftCornerIndex,
 762                               up_rightCornerWhere,
 763                               up_rightCornerIndex,
 764                             pStream);
 765         }
 766 #endif
 767     }//end if 0,2
 768 }//end if the function
 769
 770
 771 static void sampleCompTopSimpleOpt(gridWrap* grid,
 772                                    Int gridV,
 773                                    Real* topVertex, Real* botVertex,
 774                                    vertexArray* inc_chain, Int inc_current, Int inc_end,
 775                                    vertexArray* dec_chain, Int dec_current, Int dec_end,
 776                                    primStream* pStream)
 777 {
 778   if(gridV <= 0 || dec_end<dec_current || inc_end <inc_current)
 779     {
 780       monoTriangulationRecGenOpt(topVertex, botVertex,
 781                                  inc_chain, inc_current, inc_end,
 782                                  dec_chain, dec_current, dec_end,
 783                                  pStream);
 784       return;
 785     }
 786   if(grid->get_v_value(gridV+1) >= topVertex[1])
 787     {
 788       monoTriangulationRecGenOpt(topVertex, botVertex,
 789                                  inc_chain, inc_current, inc_end,
 790                                  dec_chain, dec_current, dec_end,
 791                                  pStream);
 792       return;
 793     }
 794  Int i,j,k;
 795   Real currentV = grid->get_v_value(gridV+1);
 796   if(inc_chain->getVertex(inc_end)[1] <= currentV &&
 797      dec_chain->getVertex(dec_end)[1] < currentV)
 798     {
 799       //find i bottom up so that inc_chain[i]<= curentV and inc_chain[i-1] > currentV,
 800       //find j botom up so that dec_chain[j] < currentV and dec_chain[j-1] >= currentV
 801       for(i=inc_end; i >= inc_current; i--)
 802         {
 803           if(inc_chain->getVertex(i)[1] > currentV)
 804             break;
 805         }
 806       i++;
 807       for(j=dec_end; j >= dec_current; j--)
 808         {
 809           if(dec_chain->getVertex(j)[1] >= currentV)
 810             break;
 811         }
 812       j++;
 813      if(inc_chain->getVertex(i)[1] <= dec_chain->getVertex(j)[1])
 814        {
 815          //find the k so that dec_chain[k][1] < inc_chain[i][1]
 816          for(k=j; k<=dec_end; k++)
 817            {
 818              if(dec_chain->getVertex(k)[1] < inc_chain->getVertex(i)[1])
 819                break;
 820            }
 821          //we know that dec_chain[j][1] >= inc_chian[i][1]
 822          //we know that dec_chain[k-1][1]>=inc_chain[i][1]
 823          //we know that dec_chian[k][1] < inc_chain[i][1]
 824          //find l in [j, k-1] so that dec_chain[l][0] 0 is closest to
 825          // inc_chain[i]
 826          int l;
 827          Real tempI = Real(j);
 828          Real tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(j)[0]);
 829          for(l=j+1; l<= k-1; l++)
 830            {
 831              if(fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0])
 832                 <= tempMin)
 833                {
 834                  tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(l)[0]);
 835                  tempI = (Real)l;
 836                }
 837            }
 838          //inc_chain[i] and dec_chain[tempI] are connected.
 839          monoTriangulationRecGenOpt(dec_chain->getVertex((int)tempI),
 840                                     botVertex,
 841                                     inc_chain, i, inc_end,
 842                                     dec_chain, (int)(tempI+1), dec_end,
 843                                     pStream);
 844          //recursively do the rest
 845          sampleCompTopSimpleOpt(grid,
 846                                 gridV+1,
 847                                 topVertex, inc_chain->getVertex(i),
 848                                 inc_chain, inc_current, i-1,
 849                                 dec_chain, dec_current, (int)tempI,
 850                                 pStream);
 851        }
 852       else
 853         {
 854           //find the k so that inc_chain[k][1] <= dec_chain[j][1]
 855           for(k=i; k<=inc_end; k++)
 856             {
 857               if(inc_chain->getVertex(k)[1] <= dec_chain->getVertex(j)[1])
 858                 break;
 859             }
 860           //we know that inc_chain[i] > dec_chain[j]
 861           //we know that inc_chain[k-1][1] > dec_chain[j][1]
 862           //we know that inc_chain[k][1] <= dec_chain[j][1]
 863           //so we find l between [i,k-1] so that
 864           //inc_chain[l][0] is the closet to dec_chain[j][0]
 865           int tempI = i;
 866           int l;
 867           Real tempMin = (Real)fabs(inc_chain->getVertex(i)[0] - dec_chain->getVertex(j)[0]);
 868           for(l=i+1; l<=k-1; l++)
 869             {
 870               if(fabs(inc_chain->getVertex(l)[0] - dec_chain->getVertex(j)[0]) <= tempMin)
 871                 {
 872                   tempMin = (Real)fabs(inc_chain->getVertex(l)[0] - dec_chain->getVertex(j)[0]);
 873                   tempI = l;
 874                 }
 875             }
 876
 877           //inc_chain[tempI] and dec_chain[j] are connected
 878
 879           monoTriangulationRecGenOpt(inc_chain->getVertex(tempI),
 880                                      botVertex,
 881                                      inc_chain, tempI+1, inc_end,
 882                                      dec_chain, j, dec_end,
 883                                      pStream);
 884
 885           //recurvesily do the rest
 886           sampleCompTopSimpleOpt(grid, gridV+1,
 887                                  topVertex, dec_chain->getVertex(j),
 888                                  inc_chain, inc_current, tempI,
 889                                  dec_chain, dec_current, j-1,
 890                                  pStream);
 891         }
 892     }
 893   else //go to the next higher gridV
 894     {
 895       sampleCompTopSimpleOpt(grid,
 896                              gridV+1,
 897                              topVertex, botVertex,
 898                              inc_chain, inc_current, inc_end,
 899                              dec_chain, dec_current, dec_end,
 900                              pStream);
 901     }
 902 }
 903
 904 void sampleCompTopSimple(Real* topVertex,
 905                    vertexArray* leftChain,
 906                    Int leftStartIndex,
 907                    vertexArray* rightChain,
 908                    Int rightStartIndex,
 909                    gridBoundaryChain* leftGridChain,
 910                    gridBoundaryChain* rightGridChain,
 911                    Int gridIndex1,
 912                    Int up_leftCornerWhere,
 913                    Int up_leftCornerIndex,
 914                    Int up_rightCornerWhere,
 915                    Int up_rightCornerIndex,
 916                    primStream* pStream)
 917 {
 918   //the plan is to use monotriangulation algortihm.
 919   Int i,k;
 920   Real* ActualTop;
 921   Real* ActualBot;
 922   Int ActualLeftStart, ActualLeftEnd;
 923   Int ActualRightStart, ActualRightEnd;
 924
 925   //creat an array to store the points on the grid line
 926   gridWrap* grid = leftGridChain->getGrid();
 927   Int gridV = leftGridChain->getVlineIndex(gridIndex1);
 928   Int gridLeftU = leftGridChain->getUlineIndex(gridIndex1);
 929   Int gridRightU = rightGridChain->getUlineIndex(gridIndex1);
 930
 931   Real2* gridPoints = (Real2*) malloc(sizeof(Real2) * (gridRightU - gridLeftU +1));
 932   assert(gridPoints);
 933
 934   for(k=0, i=gridRightU; i>= gridLeftU; i--, k++)
 935     {
 936       gridPoints[k][0] = grid->get_u_value(i);
 937       gridPoints[k][1] = grid->get_v_value(gridV);
 938     }
 939
 940   if(up_leftCornerWhere != 2)
 941     ActualRightStart = rightStartIndex;
 942   else
 943     ActualRightStart = up_leftCornerIndex+1; //up_leftCornerIndex will be the ActualTop
 944
 945   if(up_rightCornerWhere != 2) //right corner is not on right chain
 946     ActualRightEnd = rightStartIndex-1; //meaning that there is no actual rigth section
 947   else
 948     ActualRightEnd = up_rightCornerIndex;
 949
 950   vertexArray ActualRightChain(max(0, ActualRightEnd-ActualRightStart+1) + gridRightU-gridLeftU+1);
 951
 952   for(i=ActualRightStart; i<= ActualRightEnd; i++)
 953     ActualRightChain.appendVertex(rightChain->getVertex(i));
 954   for(i=0; i<gridRightU-gridLeftU+1; i++)
 955     ActualRightChain.appendVertex(gridPoints[i]);
 956
 957   //determine ActualLeftEnd
 958   if(up_leftCornerWhere != 0)
 959     ActualLeftEnd = leftStartIndex-1;
 960   else
 961     ActualLeftEnd = up_leftCornerIndex;
 962
 963   if(up_rightCornerWhere != 0)
 964     ActualLeftStart = leftStartIndex;
 965   else
 966     ActualLeftStart = up_rightCornerIndex+1; //up_rightCornerIndex will be the actual top
 967
 968   if(up_leftCornerWhere == 0)
 969     {
 970       if(up_rightCornerWhere == 0)
 971         ActualTop = leftChain->getVertex(up_rightCornerIndex);
 972       else
 973         ActualTop = topVertex;
 974     }
 975   else if(up_leftCornerWhere == 1)
 976     ActualTop = topVertex;
 977   else  //up_leftCornerWhere == 2
 978     ActualTop = rightChain->getVertex(up_leftCornerIndex);
 979
 980   ActualBot = gridPoints[gridRightU - gridLeftU];
 981
 982
 983
 984
 985   if(leftChain->getVertex(ActualLeftEnd)[1] == ActualBot[1])
 986     {
 987 /*
 988     monoTriangulationRecGenOpt(ActualTop, leftChain->getVertex(ActualLeftEnd),
 989                             leftChain,
 990                             ActualLeftStart, ActualLeftEnd-1,
 991                             &ActualRightChain,
 992                             0,
 993                             ActualRightChain.getNumElements()-1,
 994                             pStream);
 995 */
 996
 997     sampleCompTopSimpleOpt(grid, gridV,
 998                            ActualTop, leftChain->getVertex(ActualLeftEnd),
 999                             leftChain,
1000                             ActualLeftStart, ActualLeftEnd-1,
1001                             &ActualRightChain,
1002                             0,
1003                             ActualRightChain.getNumElements()-1,
1004                             pStream);
1005
1006   }
1007   else
1008     {
1009 /*
1010     monoTriangulationRecGenOpt(ActualTop, ActualBot, leftChain,
1011                           ActualLeftStart, ActualLeftEnd,
1012                           &ActualRightChain,
1013                           0, ActualRightChain.getNumElements()-2, //the last is the bot.
1014                           pStream);
1015 */
1016
1017     sampleCompTopSimpleOpt(grid, gridV,
1018                            ActualTop, ActualBot, leftChain,
1019                           ActualLeftStart, ActualLeftEnd,
1020                           &ActualRightChain,
1021                           0, ActualRightChain.getNumElements()-2, //the last is the bot.
1022                           pStream);
1023
1024
1025   }
1026
1027   free(gridPoints);
1028
1029 }
1030