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 = 0, segIndexPass;
 211   findBotRightSegment(rightChain,
 212                       rightEnd,
 213                       rightCorner,
 214                       grid->get_u_value(rightU),
 215                       segIndexMono,
 216                       segIndexPass);
 217
 218   sampleBotRightWithGridLinePost(botVertex,
 219                                  rightChain,
 220                                  rightEnd,
 221                                  segIndexMono,
 222                                  segIndexPass,
 223                                  rightCorner,
 224                                  grid,
 225                                  gridV,
 226                                  leftU,
 227                                  rightU,
 228                                  pStream);
 229 }
 230
 231
 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 = 0;
 297   findBotLeftSegment(leftChain, leftEnd, leftCorner, grid->get_u_value(leftU), segIndexMono, segIndexPass);
 298
 299   sampleBotLeftWithGridLinePost(botVertex,
 300                             leftChain,
 301                             leftEnd,
 302                             segIndexMono,
 303                             segIndexPass,
 304                             leftCorner,
 305                             grid,
 306                             gridV,
 307                             leftU, rightU, pStream);
 308 }
 309
 310 //return 1 if separator exists, 0 otherwise
 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