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