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 ** $Date: 2001/11/29 16:16:55 $ $Revision: 1.2 $
  35 */
  36 /*
  37 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/sampleCompBot.cc,v 1.2 2001/11/29 16:16:55 kschultz Exp $
  38 */
  39
  40 #include <stdlib.h>
  41 #include <stdio.h>
  42 #include "zlassert.h"
  43 #include "sampleCompBot.h"
  44 #include "sampleCompRight.h"
  45
  46 #define max(a,b) ((a>b)? a:b)
  47
  48 //return: index_mono, index_pass
  49 //from [pass, mono] is strictly U-monotone
  50 //from [corner, pass] is <u
  51 // vertex[pass][0] >= u
  52 //if everybost is <u, then pass = end+1.
  53 //otherwise both mono and pass are meanng full and we have corner<=pass<=mono<=end
  54 void findBotLeftSegment(vertexArray* leftChain,
  55                         Int leftEnd,
  56                         Int leftCorner,
  57                         Real u,
  58                         Int& ret_index_mono,
  59                         Int& ret_index_pass)
  60 {
  61   Int i;
  62
  63   assert(leftCorner <= leftEnd);
  64   for(i=leftCorner; i<= leftEnd; i++)
  65     if(leftChain->getVertex(i)[0] >= u)
  66       break;
  67   ret_index_pass = i;
  68   if(ret_index_pass <= leftEnd)
  69     {
  70       for(i=ret_index_pass; i< leftEnd; i++)
  71         {
  72           if(leftChain->getVertex(i+1)[0] <= leftChain->getVertex(i)[0])
  73             break;
  74         }
  75       ret_index_mono = i;
  76     }
  77
  78 }
  79
  80 void findBotRightSegment(vertexArray* rightChain,
  81                          Int rightEnd,
  82                          Int rightCorner,
  83                          Real u,
  84                          Int& ret_index_mono,
  85                          Int& ret_index_pass)
  86 {
  87   Int i;
  88   assert(rightCorner <= rightEnd);
  89   for(i=rightCorner; i<= rightEnd; i++)
  90     if(rightChain->getVertex(i)[0] <= u)
  91       break;
  92
  93
  94
  95   ret_index_pass = i;
  96
  97   if(ret_index_pass <= rightEnd)
  98     {
  99       for(i=ret_index_pass; i< rightEnd; i++)
 100         {
 101           if(rightChain->getVertex(i+1)[0] >= rightChain->getVertex(i)[0])
 102             break;
 103         }
 104       ret_index_mono = i;
 105     }
 106 }
 107
 108
 109 void sampleBotRightWithGridLinePost(Real* botVertex,
 110                                     vertexArray* rightChain,
 111                                     Int rightEnd,
 112                                     Int segIndexMono,
 113                                     Int segIndexPass,
 114                                     Int rightCorner,
 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(segIndexPass > rightCorner) //from corner to pass-1 is > u.
 123     {
 124       Real *tempBot;
 125       if(segIndexPass <= rightEnd) //there is a point to the left of u
 126         tempBot = rightChain->getVertex(segIndexPass);
 127       else   //nothing is to the left of u.
 128         tempBot = botVertex;
 129       Real tempTop[2];
 130       tempTop[0] = grid->get_u_value(rightU);
 131       tempTop[1] = grid->get_v_value(gridV);
 132
 133       monoTriangulation2(tempTop, tempBot,
 134                          rightChain,
 135                          rightCorner,
 136                          segIndexPass-1,
 137                          0, // a decrease chain
 138                          pStream);
 139     }
 140
 141   //the possible section which is strictly Umonotone
 142   if(segIndexPass <= rightEnd) //segIndex pass and mono exist
 143     {
 144       //if there are grid points which are to the left of botVertex
 145       //then we should use botVertex to form a fan with these points to
 146       //optimize the triangulation
 147       int do_optimize = 1;
 148       if(botVertex[0] <= grid->get_u_value(leftU))
 149         do_optimize = 0;
 150       else
 151         {
 152           //we also have to make sure that botVertex is the left most vertex on the chain
 153           int i;
 154           for(i=segIndexMono; i<=rightEnd; i++)
 155             if(rightChain->getVertex(i)[0] <= botVertex[0])
 156               {
 157                 do_optimize = 0;
 158                 break;
 159               }
 160         }
 161
 162       if(do_optimize)
 163         {
 164           //find midU so that grid->get_u_value(midU) <= botVertex[0]
 165           //and               grid->get_u_value(midU) >  botVertex[0]
 166           int midU = leftU;
 167           while(grid->get_u_value(midU) <= botVertex[0])
 168             {
 169               midU++;
 170               if(midU > rightU)
 171                 break;
 172             }
 173           midU--;
 174
 175           grid->outputFanWithPoint(gridV, leftU, midU, botVertex, pStream);
 176           stripOfFanRight(rightChain, segIndexMono, segIndexPass, grid, gridV, midU, rightU, pStream, 1);
 177           Real tempTop[2];
 178           tempTop[0] = grid->get_u_value(midU);
 179           tempTop[1] = grid->get_v_value(gridV);
 180           monoTriangulation2(tempTop, botVertex, rightChain, segIndexMono, rightEnd, 0, pStream);
 181         }
 182       else //not optimize
 183         {
 184           stripOfFanRight(rightChain, segIndexMono, segIndexPass, grid, gridV, leftU, rightU, pStream, 1);
 185           Real tempTop[2];
 186           tempTop[0] = grid->get_u_value(leftU);
 187           tempTop[1] = grid->get_v_value(gridV);
 188           monoTriangulation2(tempTop, botVertex, rightChain, segIndexMono, rightEnd, 0, pStream);
 189         }
 190     }
 191   else //the botVertex forms a fan witht eh grid points
 192     grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
 193 }
 194
 195 void sampleBotRightWithGridLine(Real* botVertex,
 196                                 vertexArray* rightChain,
 197                                 Int rightEnd,
 198                                 Int rightCorner,
 199                                 gridWrap* grid,
 200                                 Int gridV,
 201                                 Int leftU,
 202                                 Int rightU,
 203                                 primStream* pStream)
 204 {
 205   //if right chaain is empty, then there is only one bot vertex with
 206   //one grid line
 207   if(rightEnd<rightCorner){
 208     grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
 209     return;
 210   }
 211
 212   Int segIndexMono, segIndexPass;
 213   findBotRightSegment(rightChain,
 214                       rightEnd,
 215                       rightCorner,
 216                       grid->get_u_value(rightU),
 217                       segIndexMono,
 218                       segIndexPass);
 219
 220   sampleBotRightWithGridLinePost(botVertex,
 221                                  rightChain,
 222                                  rightEnd,
 223                                  segIndexMono,
 224                                  segIndexPass,
 225                                  rightCorner,
 226                                  grid,
 227                                  gridV,
 228                                  leftU,
 229                                  rightU,
 230                                  pStream);
 231 }
 232
 233
 234 void sampleBotLeftWithGridLinePost(Real* botVertex,
 235                                    vertexArray* leftChain,
 236                                    Int leftEnd,
 237                                    Int segIndexMono,
 238                                    Int segIndexPass,
 239                                    Int leftCorner,
 240                                    gridWrap* grid,
 241                                    Int gridV,
 242                                    Int leftU,
 243                                    Int rightU,
 244                                    primStream* pStream)
 245 {
 246
 247   //the possible section which is to the left of leftU
 248   if(segIndexPass > leftCorner) //at least leftCorner is to the left of leftU
 249     {
 250       Real *tempBot;
 251       if(segIndexPass <= leftEnd) //from corner to pass-1 is <u
 252         tempBot = leftChain->getVertex(segIndexPass);
 253       else //nothing is to the rigth of u
 254         tempBot = botVertex;
 255       Real tempTop[2];
 256       tempTop[0] = grid->get_u_value(leftU);
 257       tempTop[1] = grid->get_v_value(gridV);
 258       monoTriangulation2(tempTop, tempBot, leftChain, leftCorner, segIndexPass-1,
 259                          1, //a increase chain,
 260                          pStream);
 261     }
 262   //the possible section which is strictly Umonotone
 263   if(segIndexPass <= leftEnd) //segIndexpass and mono exist
 264     {
 265       stripOfFanLeft(leftChain, segIndexMono, segIndexPass, grid, gridV, leftU, rightU, pStream, 1);
 266       Real tempTop[2];
 267       tempTop[0] = grid->get_u_value(rightU);
 268       tempTop[1] = grid->get_v_value(gridV);
 269
 270       monoTriangulation2(tempTop, botVertex, leftChain, segIndexMono, leftEnd,
 271                          1,  //increase chain
 272                          pStream);
 273     }
 274   else //the botVertex forms a fan with the grid points
 275     {
 276       grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
 277     }
 278
 279 }
 280
 281 void sampleBotLeftWithGridLine(Real* botVertex,
 282                                vertexArray* leftChain,
 283                                Int leftEnd,
 284                                Int leftCorner,
 285                                gridWrap* grid,
 286                                Int gridV,
 287                                Int leftU,
 288                                Int rightU,
 289                                primStream* pStream)
 290 {
 291
 292   //if leftChain is empty, then there is only one botVertex with one grid line
 293   if(leftEnd< leftCorner){
 294     grid->outputFanWithPoint(gridV, leftU, rightU, botVertex, pStream);
 295     return;
 296   }
 297
 298   Int segIndexPass, segIndexMono;
 299   findBotLeftSegment(leftChain, leftEnd, leftCorner, grid->get_u_value(leftU), segIndexMono, segIndexPass);
 300
 301   sampleBotLeftWithGridLinePost(botVertex,
 302                             leftChain,
 303                             leftEnd,
 304                             segIndexMono,
 305                             segIndexPass,
 306                             leftCorner,
 307                             grid,
 308                             gridV,
 309                             leftU, rightU, pStream);
 310 }
 311
 312 //return 1 if separator exists, 0 otherwise
 313 Int findBotSeparator(vertexArray* leftChain,
 314                      Int leftEnd,
 315                      Int leftCorner,
 316                      vertexArray* rightChain,
 317                      Int rightEnd,
 318                      Int rightCorner,
 319                      Int& ret_sep_left,
 320                      Int& ret_sep_right)
 321 {
 322   Int oldLeftI, oldRightI, newLeftI, newRightI;
 323   Int i,j,k;
 324   Real leftMax /*= leftChain->getVertex(leftCorner)[0]*/;
 325   Real rightMin /*= rightChain->getVertex(rightCorner)[0]*/;
 326   if(leftChain->getVertex(leftCorner)[1] < rightChain->getVertex(rightCorner)[1])//leftlower
 327     {
 328       oldLeftI = leftCorner-1;
 329       oldRightI = rightCorner;
 330       leftMax = leftChain->getVertex(leftCorner)[0] - Real(1.0) ; //initilize to be left of leftCorner
 331       rightMin = rightChain->getVertex(rightCorner)[0];
 332     }
 333   else //rightlower
 334     {
 335       oldLeftI = leftCorner;
 336       oldRightI = rightCorner-1;
 337       leftMax = leftChain->getVertex(leftCorner)[0];
 338       rightMin = rightChain->getVertex(rightCorner)[0] + Real(1.0);
 339     }
 340
 341   //i: the current working leftChain Index
 342   //j: the curent working right chian index
 343   //if(left(i) is lower than right(j), then the two chains above right(j) are separated.
 344   //else the two chains below left(i) are separated.
 345   i = leftCorner;
 346   j = rightCorner;
 347   while(1)
 348     {
 349       newLeftI = oldLeftI;
 350       newRightI = oldRightI;
 351       if(i> leftEnd) //left chain is doen , go through remaining right chain
 352         {
 353           for(k=j+1; k<= rightEnd; k++)
 354             {
 355               if(rightChain->getVertex(k)[0] > leftMax) //no conflict
 356                 {
 357                   //update oldRightI if necessary
 358                   if(rightChain->getVertex(k)[0] < rightMin)
 359                     {
 360                       rightMin = rightChain->getVertex(k)[0];
 361                       oldRightI = k;
 362                     }
 363                 }
 364               else //there is a conflict
 365                 break; //the for-loop, above right(k+1) is separated: oldLeftI, oldRightI
 366             }
 367           break; //the while loop
 368         }
 369       else if(j > rightEnd) //right Chain is doen
 370         {
 371           for(k=i+1; k<= leftEnd; k++)
 372             {
 373               if(leftChain->getVertex(k)[0] < rightMin) //no conflict
 374                 {
 375                   //update oldLeftI if necessary
 376                   if(leftChain->getVertex(k)[0] > leftMax)
 377                     {
 378                       leftMax =  leftChain->getVertex(k)[0];
 379                       oldLeftI = k;
 380                     }
 381                 }
 382               else //there is a conflict
 383                 break; //the for-loop, above left(k+1) is separated: oldLeftI, oldRightI
 384             }
 385           break; //the while loop
 386         }
 387       else if(leftChain->getVertex(i)[1] < rightChain->getVertex(j)[1]) //left lower
 388         {
 389
 390           if(leftChain->getVertex(i)[0] > leftMax) //update leftMax amd newLeftI
 391             {
 392               leftMax = leftChain->getVertex(i)[0];
 393               newLeftI = i;
 394             }
 395           for(k=j+1; k<= rightEnd; k++) //update rightMin and newRightI;
 396             {
 397               if(rightChain->getVertex(k)[1] < leftChain->getVertex(i)[1]) //right gets lower
 398                 break;
 399               if(rightChain->getVertex(k)[0] < rightMin)
 400                 {
 401                   rightMin = rightChain->getVertex(k)[0];
 402                   newRightI = k;
 403                 }
 404             }
 405           j = k; //next working j, since j will he lower than i in next loop
 406           if(leftMax >= rightMin) //there is a conflict
 407             break;
 408           else //still no conflict
 409             {
 410               oldLeftI = newLeftI;
 411               oldRightI = newRightI;
 412
 413             }
 414         }
 415       else //right lower
 416         {
 417           if(rightChain->getVertex(j)[0] < rightMin)
 418             {
 419               rightMin = rightChain->getVertex(j)[0];
 420               newRightI = j;
 421             }
 422           for(k=i+1; k<= leftEnd; k++)
 423             {
 424               if(leftChain->getVertex(k)[1] < rightChain->getVertex(j)[1])
 425                 break;
 426               if(leftChain->getVertex(k)[0] > leftMax)
 427                 {
 428                   leftMax = leftChain->getVertex(k)[0];
 429                   newLeftI = k;
 430                 }
 431             }
 432           i=k; //nexct working i, since i will be lower than j next loop
 433           if(leftMax >= rightMin) //there is conflict
 434             break;
 435           else //still no conflict
 436             {
 437               oldLeftI = newLeftI;
 438               oldRightI = newRightI;
 439             }
 440         }
 441     }//end of while loop
 442   //now oldLeftI and oldRight I are the desired separator index notice that they are not
 443   //necessarily valid
 444   if(oldLeftI < leftCorner || oldRightI < rightCorner)
 445     return 0; //no separator
 446   else
 447     {
 448       ret_sep_left = oldLeftI;
 449       ret_sep_right = oldRightI;
 450       return 1;
 451     }
 452 }
 453
 454 void sampleCompBot(Real* botVertex,
 455                    vertexArray* leftChain,
 456                    Int leftEnd,
 457                    vertexArray* rightChain,
 458                    Int rightEnd,
 459                    gridBoundaryChain* leftGridChain,
 460                    gridBoundaryChain* rightGridChain,
 461                    Int gridIndex,
 462                    Int down_leftCornerWhere,
 463                    Int down_leftCornerIndex,
 464                    Int down_rightCornerWhere,
 465                    Int down_rightCornerIndex,
 466                    primStream* pStream)
 467 {
 468
 469   if(down_leftCornerWhere == 1 && down_rightCornerWhere == 1) //the bot is botVertex with possible grid points
 470     {
 471
 472       leftGridChain->getGrid()->outputFanWithPoint(leftGridChain->getVlineIndex(gridIndex),
 473                                                    leftGridChain->getUlineIndex(gridIndex),
 474                                                   rightGridChain->getUlineIndex(gridIndex),
 475                                                    botVertex,
 476                                                    pStream);
 477       return;
 478     }
 479   else if(down_leftCornerWhere != 0)
 480     {
 481
 482       Real* tempBot;
 483       Int tempRightEnd;
 484       if(down_leftCornerWhere == 1){
 485         tempRightEnd = rightEnd;
 486         tempBot = botVertex;
 487       }
 488       else
 489         {
 490           tempRightEnd = down_leftCornerIndex-1;
 491           tempBot = rightChain->getVertex(down_leftCornerIndex);
 492         }
 493
 494       sampleBotRightWithGridLine(tempBot,
 495                                  rightChain,
 496                                  tempRightEnd,
 497                                  down_rightCornerIndex,
 498                                  rightGridChain->getGrid(),
 499                                  leftGridChain->getVlineIndex(gridIndex),
 500                                  leftGridChain->getUlineIndex(gridIndex),
 501                                  rightGridChain->getUlineIndex(gridIndex),
 502                                  pStream);
 503     }
 504   else if(down_rightCornerWhere != 2)
 505     {
 506
 507       Real* tempBot;
 508       Int tempLeftEnd;
 509       if(down_rightCornerWhere == 1){
 510         tempLeftEnd = leftEnd;
 511         tempBot = botVertex;
 512       }
 513       else //right corner is on left chain
 514         {
 515           tempLeftEnd = down_rightCornerIndex-1;
 516           tempBot = leftChain->getVertex(down_rightCornerIndex);
 517         }
 518
 519
 520       sampleBotLeftWithGridLine(tempBot, leftChain, tempLeftEnd, down_leftCornerIndex,
 521                                 leftGridChain->getGrid(),
 522                                 leftGridChain->getVlineIndex(gridIndex),
 523                                 leftGridChain->getUlineIndex(gridIndex),
 524                                 rightGridChain->getUlineIndex(gridIndex),
 525                                 pStream);
 526
 527     }
 528   else //down_leftCornereWhere == 0, down_rightCornerwhere == 2
 529     {
 530       sampleCompBotSimple(botVertex,
 531                           leftChain,
 532                           leftEnd,
 533                           rightChain,
 534                           rightEnd,
 535                           leftGridChain,
 536                           rightGridChain,
 537                           gridIndex,
 538                           down_leftCornerWhere,
 539                           down_leftCornerIndex,
 540                           down_rightCornerWhere,
 541                           down_rightCornerIndex,
 542                           pStream);
 543
 544       return;
 545
 546 #ifdef NOT_REACHABLE
 547       //the following code is trying to do some optimization, but not quite working. so it is not reachable, but leave it here for reference
 548       Int sep_left, sep_right;
 549       if(findBotSeparator(leftChain, leftEnd, down_leftCornerIndex,
 550                           rightChain, rightEnd, down_rightCornerIndex,
 551                           sep_left, sep_right)
 552          )//separator exiosts
 553         {
 554
 555           if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex) &&
 556              rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex))
 557             {
 558               Int gridSep;
 559               Int segLeftMono, segLeftPass, segRightMono, segRightPass;
 560               findBotLeftSegment(leftChain,
 561                                  sep_left,
 562                                  down_leftCornerIndex,
 563                                  leftGridChain->get_u_value(gridIndex),
 564                                  segLeftMono,
 565                                  segLeftPass);
 566               findBotRightSegment(rightChain,
 567                                   sep_right,
 568                                   down_rightCornerIndex,
 569                                   rightGridChain->get_u_value(gridIndex),
 570                                   segRightMono,
 571                                   segRightPass);
 572               if(leftChain->getVertex(segLeftMono)[1] <= rightChain->getVertex(segRightMono)[1])
 573                 {
 574                   gridSep = rightGridChain->getUlineIndex(gridIndex);
 575                   while(leftGridChain->getGrid()->get_u_value(gridSep) > leftChain->getVertex(segLeftMono)[0])
 576                     gridSep--;
 577                 }
 578               else
 579                 {
 580                   gridSep = leftGridChain->getUlineIndex(gridIndex);
 581                   while(leftGridChain->getGrid()->get_u_value(gridSep) < rightChain->getVertex(segRightMono)[0])
 582                     gridSep++;
 583                 }
 584
 585               sampleBotLeftWithGridLinePost(leftChain->getVertex(segLeftMono),
 586                                             leftChain,
 587                                             segLeftMono-1,
 588                                             segLeftMono-1,
 589                                             segLeftPass,
 590                                             down_leftCornerIndex,
 591                                             leftGridChain->getGrid(),
 592                                             leftGridChain->getVlineIndex(gridIndex),
 593                                             leftGridChain->getUlineIndex(gridIndex),
 594                                             gridSep,
 595                                             pStream);
 596               sampleBotRightWithGridLinePost(rightChain->getVertex(segRightMono),
 597                                              rightChain,
 598                                              segRightMono-1,
 599                                              segRightMono-1,
 600                                              segRightPass,
 601                                              down_rightCornerIndex,
 602                                              rightGridChain->getGrid(),
 603                                              rightGridChain->getVlineIndex(gridIndex),
 604                                              gridSep,
 605                                              rightGridChain->getUlineIndex(gridIndex),
 606                                              pStream);
 607               Real tempTop[2];
 608               tempTop[0] = leftGridChain->getGrid()->get_u_value(gridSep);
 609               tempTop[1] = leftGridChain->get_v_value(gridIndex);
 610               monoTriangulationRecGen(tempTop, botVertex,
 611                                       leftChain, segLeftMono, leftEnd,
 612                                       rightChain, segRightMono, rightEnd,
 613                                       pStream);
 614             }//end if both sides have vertices inside the gridboundary points
 615           else if(leftChain->getVertex(sep_left)[0] >= leftGridChain->get_u_value(gridIndex)) //left n right out
 616
 617             {
 618               Int segLeftMono, segLeftPass;
 619               findBotLeftSegment(leftChain,
 620                                  sep_left,
 621                                  down_leftCornerIndex,
 622                                  leftGridChain->get_u_value(gridIndex),
 623                                  segLeftMono,
 624                                  segLeftPass);
 625               assert(segLeftPass <= sep_left); //make sure there is a point to the right of u.
 626               monoTriangulation2(leftGridChain->get_vertex(gridIndex),
 627                                  leftChain->getVertex(segLeftPass),
 628                                  leftChain,
 629                                  down_leftCornerIndex,
 630                                  segLeftPass-1,
 631                                  1, //a increase chain
 632                                  pStream);
 633               stripOfFanLeft(leftChain, segLeftMono, segLeftPass,
 634                              leftGridChain->getGrid(),
 635                              leftGridChain->getVlineIndex(gridIndex),
 636                              leftGridChain->getUlineIndex(gridIndex),
 637                              rightGridChain->getUlineIndex(gridIndex),
 638                              pStream,1 );
 639 /*
 640               sampleBotLeftWithGridLinePost(leftChain->getVertex(segLeftMono),
 641                                             leftChain,
 642                                             segLeftMono-1,
 643                                             segLeftMono-1,
 644                                             segLeftPass,
 645                                             down_leftCornerIndex,
 646                                             leftGridChain->getGrid(),
 647                                             leftGridChain->getVlineIndex(gridIndex),
 648                                             leftGridChain->getUlineIndex(gridIndex),
 649                                             rightGridChain->getUlineIndex(gridIndex),
 650                                             pStream);
 651 */
 652
 653               monoTriangulationRecGen(rightGridChain->get_vertex(gridIndex),
 654                                       botVertex,
 655                                       leftChain, segLeftMono, leftEnd,
 656                                       rightChain, down_rightCornerIndex, rightEnd,
 657                                       pStream);
 658             }//end left in right out
 659           else if(rightChain->getVertex(sep_right)[0] <= rightGridChain->get_u_value(gridIndex))//left out right in
 660             {
 661               Int segRightMono, segRightPass;
 662               findBotRightSegment(rightChain, sep_right, down_rightCornerIndex,
 663                                   rightGridChain->get_u_value(gridIndex),
 664                                   segRightMono,
 665                                   segRightPass);
 666
 667               assert(segRightPass <= sep_right); //make sure there is a point to the left of u.
 668               monoTriangulation2(rightGridChain->get_vertex(gridIndex),
 669                                  rightChain->getVertex(segRightPass),
 670                                  rightChain,
 671                                  down_rightCornerIndex,
 672                                  segRightPass-1,
 673                                  0, // a decrease chain
 674                                  pStream);
 675
 676               stripOfFanRight(rightChain, segRightMono, segRightPass,
 677                               rightGridChain->getGrid(),
 678                               rightGridChain->getVlineIndex(gridIndex),
 679                               leftGridChain->getUlineIndex(gridIndex),
 680                               rightGridChain->getUlineIndex(gridIndex),
 681                               pStream, 1);
 682
 683
 684               monoTriangulationRecGen(leftGridChain->get_vertex(gridIndex),
 685                                       botVertex,
 686                                       leftChain, down_leftCornerIndex, leftEnd,
 687                                       rightChain, segRightMono, rightEnd,
 688                                       pStream);
 689
 690             }//end left out right in
 691           else //left out, right out
 692             {
 693               sampleCompBotSimple(botVertex,
 694                                  leftChain,
 695                                  leftEnd,
 696                                  rightChain,
 697                                  rightEnd,
 698                                  leftGridChain,
 699                                  rightGridChain,
 700                                  gridIndex,
 701                                  down_leftCornerWhere,
 702                                  down_leftCornerIndex,
 703                                  down_rightCornerWhere,
 704                                  down_rightCornerIndex,
 705                                  pStream);
 706
 707             }//end leftout right out
 708         }//end if separator exists
 709       else //no separator
 710         {
 711
 712           sampleCompBotSimple(botVertex,
 713                              leftChain,
 714                              leftEnd,
 715                              rightChain,
 716                              rightEnd,
 717                              leftGridChain,
 718                              rightGridChain,
 719                              gridIndex,
 720                              down_leftCornerWhere,
 721                              down_leftCornerIndex,
 722                              down_rightCornerWhere,
 723                              down_rightCornerIndex,
 724                              pStream);
 725         }
 726 #endif
 727     }//end id 0 2
 728 }//end if the functin
 729
 730
 731 void sampleCompBotSimple(Real* botVertex,
 732                    vertexArray* leftChain,
 733                    Int leftEnd,
 734                    vertexArray* rightChain,
 735                    Int rightEnd,
 736                    gridBoundaryChain* leftGridChain,
 737                    gridBoundaryChain* rightGridChain,
 738                    Int gridIndex,
 739                    Int down_leftCornerWhere,
 740                    Int down_leftCornerIndex,
 741                    Int down_rightCornerWhere,
 742                    Int down_rightCornerIndex,
 743                    primStream* pStream)
 744 {
 745   //the plan is to use monotriangulation algorithm.
 746   Int i,k;
 747   Real* ActualTop;
 748   Real* ActualBot;
 749   Int ActualLeftStart, ActualLeftEnd;
 750   Int ActualRightStart, ActualRightEnd;
 751
 752   //creat an array to store the points on the grid line
 753   gridWrap* grid = leftGridChain->getGrid();
 754   Int gridV = leftGridChain->getVlineIndex(gridIndex);
 755   Int gridLeftU = leftGridChain->getUlineIndex(gridIndex);
 756   Int gridRightU = rightGridChain->getUlineIndex(gridIndex);
 757   Real2* gridPoints = (Real2*) malloc(sizeof(Real2) * (gridRightU - gridLeftU +1));
 758   assert(gridPoints);
 759
 760   for(k=0, i=gridRightU; i>= gridLeftU; i--, k++)
 761     {
 762       gridPoints[k][0] = grid->get_u_value(i);
 763       gridPoints[k][1] = grid->get_v_value(gridV);
 764     }
 765
 766   if(down_rightCornerWhere != 0) //rightCorner is not on lef
 767     ActualLeftEnd = leftEnd;
 768   else
 769     ActualLeftEnd = down_rightCornerIndex-1; //down_rightCornerIndex will be th actualBot
 770
 771   if(down_leftCornerWhere != 0) //left corner is not on let chian
 772     ActualLeftStart = leftEnd+1; //meaning that there is no actual left section
 773   else
 774     ActualLeftStart = down_leftCornerIndex;
 775
 776   vertexArray ActualLeftChain(max(0, ActualLeftEnd - ActualLeftStart +1) + gridRightU - gridLeftU +1);
 777
 778   for(i=0; i<gridRightU - gridLeftU +1 ; i++)
 779     ActualLeftChain.appendVertex(gridPoints[i]);
 780   for(i=ActualLeftStart; i<= ActualLeftEnd; i++)
 781     ActualLeftChain.appendVertex(leftChain->getVertex(i));
 782
 783   //determine ActualRightStart
 784   if(down_rightCornerWhere != 2) //right is not on right
 785     ActualRightStart = rightEnd +1; //meaning no section on right
 786   else
 787     ActualRightStart = down_rightCornerIndex;
 788
 789   //determine actualrightEnd
 790   if(down_leftCornerWhere != 2) //left is not on right
 791     {
 792
 793       ActualRightEnd = rightEnd;
 794     }
 795   else //left corner is on right
 796     {
 797       ActualRightEnd = down_leftCornerIndex-1; //down_leftCornerIndex will be the bot
 798
 799     }
 800
 801   //actual bot
 802   if(down_rightCornerWhere == 2)
 803     {
 804       if(down_leftCornerWhere == 2)
 805         ActualBot = rightChain->getVertex(down_leftCornerIndex);
 806       else
 807         ActualBot = botVertex;
 808     }
 809   else if(down_rightCornerWhere == 1) //right corner bot
 810     ActualBot = botVertex;
 811   else //down_rightCornerWhere == 0
 812     ActualBot = leftChain->getVertex(down_rightCornerIndex);
 813
 814   ActualTop = gridPoints[0];
 815 /*
 816 printf("in bot simple, actual leftChain is \n");
 817 ActualLeftChain.print();
 818 printf("Actual Top = %f,%f\n", ActualTop[0],ActualTop[1]);
 819 printf("Actual Bot = %f,%f\n", ActualBot[0],ActualBot[1]);
 820 printf("Actual right start = %i, end=%i\n",ActualRightStart,   ActualRightEnd);
 821 */
 822   if(rightChain->getVertex(ActualRightStart)[1] == ActualTop[1])
 823     monoTriangulationRecGenOpt(rightChain->getVertex(ActualRightStart),
 824                             ActualBot,
 825                             &ActualLeftChain,
 826                             0,
 827                             ActualLeftChain.getNumElements()-1,
 828                             rightChain,
 829                             ActualRightStart+1,
 830                             ActualRightEnd,
 831                             pStream);
 832   else
 833     monoTriangulationRecGenOpt(ActualTop, ActualBot,
 834                           &ActualLeftChain,
 835                           1, //the first one is the top vertex
 836                           ActualLeftChain.getNumElements()-1,
 837                           rightChain,
 838                           ActualRightStart,
 839                           ActualRightEnd,
 840                           pStream);
 841   free(gridPoints);
 842 }
 843
 844
 845
 846