src/glu/sgi/libnurbs/internals/slicer.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  * slicer.c++
  37  *
  38  */
  39
  40 #include <stdlib.h>
  41 #include <stdio.h>
  42 #include <math.h>
  43 #include "glimports.h"
  44 #include "mystdio.h"
  45 #include "myassert.h"
  46 #include "bufpool.h"
  47 #include "slicer.h"
  48 #include "backend.h"
  49 #include "arc.h"
  50 #include "gridtrimvertex.h"
  51 #include "simplemath.h"
  52 #include "trimvertex.h"
  53 #include "varray.h"
  54
  55 #include "polyUtil.h" //for area()
  56
  57 //static int count=0;
  58
  59 /*USE_OPTTT is initiated in trimvertex.h*/
  60
  61 #ifdef USE_OPTTT
  62         #include <GL/gl.h>
  63 #endif
  64
  65 //#define USE_READ_FLAG //whether to use new or old tesselator
  66                           //if defined, it reads "flagFile",
  67                           // if the number is 1, then use new tess
  68                           // otherwise, use the old tess.
  69                          //if not defined, then use new tess.
  70 #ifdef USE_READ_FLAG
  71 static Int read_flag(char* name);
  72 Int newtess_flag = read_flag("flagFile");
  73 #endif
  74
  75 //#define COUNT_TRIANGLES
  76 #ifdef COUNT_TRIANGLES
  77 Int num_triangles = 0;
  78 Int num_quads = 0;
  79 #endif
  80
  81 #define max(a,b) ((a>b)? a:b)
  82 #define ZERO 0.00001 /*determing whether a loop is a rectngle or not*/
  83 #define equalRect(a,b) ((glu_abs(a-b) <= ZERO)? 1:0) //only used in tessellating a rectangle
  84
  85 #if 0 // UNUSED
  86 static Int is_Convex(Arc_ptr loop)
  87 {
  88   if(area(loop->tail(), loop->head(), loop->next->head()) <0 )
  89     return 0;
  90   for(Arc_ptr jarc = loop->next; jarc != loop; jarc = jarc->next)
  91     {
  92       if(area(jarc->tail(), jarc->head(), jarc->next->head()) < 0)
  93         return 0;
  94     }
  95   return 1;
  96 }
  97 #endif
  98
  99 /******triangulate a monotone polygon**************/
 100 #include "monoTriangulation.h"
 101 #if 0 // UNUSED
 102 static int is_U_monotone(Arc_ptr loop)
 103 {
 104   int n_changes=0;
 105   int prev_sign;
 106   int cur_sign;
 107   Arc_ptr temp;
 108
 109   cur_sign = compV2InX(loop->head(), loop->tail());
 110
 111   n_changes  = (compV2InX(loop->prev->head(), loop->prev->tail())
 112                 != cur_sign);
 113
 114   for(temp=loop->next; temp != loop; temp = temp->next)
 115     {
 116       prev_sign = cur_sign;
 117       cur_sign = compV2InX(temp->head(), temp->tail());
 118       if(cur_sign != prev_sign)
 119        {
 120 #ifdef DEBUG
 121          printf("***change signe\n");
 122 #endif
 123          n_changes++;
 124        }
 125     }
 126   if(n_changes == 2) return 1;
 127   else
 128     return 0;
 129 }
 130 #endif
 131
 132 inline int compInY(REAL a[2], REAL b[2])
 133 {
 134   if(a[1] < b[1])
 135     return -1;
 136   else if (a[1] > b[1])
 137     return 1;
 138   else if(a[0] > b[0])
 139     return 1;
 140   else return -1;
 141 }
 142
 143 void monoTriangulationLoop(Arc_ptr loop, Backend& backend, primStream* pStream)
 144 {
 145   int i;
 146   //find the top, bottom, increasing and decreasing chain
 147   //then call monoTrianulation
 148   Arc_ptr jarc, temp;
 149   Arc_ptr top;
 150   Arc_ptr bot;
 151   top = bot = loop;
 152   if(compInY(loop->tail(), loop->prev->tail()) < 0)
 153     {
 154       //first find bot
 155       for(temp = loop->next; temp != loop; temp = temp->next)
 156         {
 157           if(compInY(temp->tail(), temp->prev->tail()) > 0)
 158             break;
 159         }
 160       bot = temp->prev;
 161       //then find top
 162       for(temp=loop->prev; temp != loop; temp = temp->prev)
 163         {
 164           if(compInY(temp->tail(), temp->prev->tail()) > 0)
 165             break;
 166         }
 167       top = temp;
 168     }
 169   else //loop > loop->prev
 170     {
 171       for(temp=loop->next; temp != loop; temp = temp->next)
 172         {
 173           if(compInY(temp->tail(), temp->prev->tail()) < 0)
 174             break;
 175         }
 176       top = temp->prev;
 177       for(temp=loop->prev; temp != loop; temp = temp->prev)
 178         {
 179           if(compInY(temp->tail(), temp->prev->tail()) < 0)
 180             break;
 181         }
 182       bot = temp;
 183     }
 184   //creat increase and decrease chains
 185   vertexArray inc_chain(50); //this is a dynamci array
 186   for(i=1; i<=top->pwlArc->npts-2; i++)
 187     {
 188       //the first vertex is the top which doesn't below to inc_chain
 189       inc_chain.appendVertex(top->pwlArc->pts[i].param);
 190     }
 191   for(jarc=top->next; jarc != bot; jarc = jarc->next)
 192     {
 193       for(i=0; i<=jarc->pwlArc->npts-2; i++)
 194         {
 195           inc_chain.appendVertex(jarc->pwlArc->pts[i].param);
 196         }
 197
 198     }
 199   vertexArray dec_chain(50);
 200   for(jarc = top->prev; jarc != bot; jarc = jarc->prev)
 201     {
 202       for(i=jarc->pwlArc->npts-2; i>=0; i--)
 203         {
 204           dec_chain.appendVertex(jarc->pwlArc->pts[i].param);
 205         }
 206     }
 207   for(i=bot->pwlArc->npts-2; i>=1; i--)
 208     {
 209       dec_chain.appendVertex(jarc->pwlArc->pts[i].param);
 210     }
 211
 212   monoTriangulationRec(top->tail(), bot->tail(), &inc_chain, 0,
 213                        &dec_chain, 0, &backend);
 214
 215 }
 216
 217 /********tesselate a rectanlge (OPTIMIZATION**************/
 218 static void triangulateRectGen(Arc_ptr loop, int n_ulines, int n_vlines, Backend& backend);
 219
 220 static Int is_rect(Arc_ptr loop)
 221 {
 222   Int nlines =1;
 223   for(Arc_ptr jarc = loop->next; jarc != loop; jarc = jarc->next)
 224     {
 225       nlines++;
 226       if(nlines == 5)
 227         break;
 228     }
 229   if(nlines != 4)
 230     return 0;
 231
 232
 233 /*
 234 printf("here1\n");
 235 printf("loop->tail=(%f,%f)\n", loop->tail()[0], loop->tail()[1]);
 236 printf("loop->head=(%f,%f)\n", loop->head()[0], loop->head()[1]);
 237 printf("loop->next->tail=(%f,%f)\n", loop->next->tail()[0], loop->next->tail()[1]);
 238 printf("loop->next->head=(%f,%f)\n", loop->next->head()[0], loop->next->head()[1]);
 239 if(fglu_abs(loop->tail()[0] - loop->head()[0])<0.000001)
 240         printf("equal 1\n");
 241 if(loop->next->tail()[1] == loop->next->head()[1])
 242         printf("equal 2\n");
 243 */
 244
 245   if( (glu_abs(loop->tail()[0] - loop->head()[0])<=ZERO) &&
 246       (glu_abs(loop->next->tail()[1] - loop->next->head()[1])<=ZERO) &&
 247       (glu_abs(loop->prev->tail()[1] - loop->prev->head()[1])<=ZERO) &&
 248       (glu_abs(loop->prev->prev->tail()[0] - loop->prev->prev->head()[0])<=ZERO)
 249      )
 250     return 1;
 251   else if
 252     ( (glu_abs(loop->tail()[1] - loop->head()[1]) <= ZERO) &&
 253       (glu_abs(loop->next->tail()[0] - loop->next->head()[0]) <= ZERO) &&
 254       (glu_abs(loop->prev->tail()[0] - loop->prev->head()[0]) <= ZERO) &&
 255       (glu_abs(loop->prev->prev->tail()[1] - loop->prev->prev->head()[1]) <= ZERO)
 256      )
 257       return 1;
 258   else
 259     return 0;
 260 }
 261
 262
 263 //a line with the same u for opt
 264 #ifdef USE_OPTTT
 265 static void evalLineNOGE_BU(TrimVertex *verts, int n, Backend& backend)
 266 {
 267   int i;
 268   backend.preEvaluateBU(verts[0].param[0]);
 269   for(i=0; i<n; i++)
 270     backend.tmeshvertNOGE_BU(&verts[i]);
 271 }
 272 #endif
 273
 274 //a line with the same v for opt
 275 #ifdef USE_OPTTT
 276 static void evalLineNOGE_BV(TrimVertex *verts, int n, Backend& backend)
 277 {
 278   int i;
 279   backend.preEvaluateBV(verts[0].param[1]);
 280
 281   for(i=0; i<n; i++)
 282     backend.tmeshvertNOGE_BV(&verts[i]);
 283 }
 284 #endif
 285
 286 #ifdef USE_OPTTT
 287 static void evalLineNOGE(TrimVertex *verts, int n, Backend& backend)
 288 {
 289
 290   if(verts[0].param[0] == verts[n-1].param[0]) //all u;s are equal
 291     evalLineNOGE_BU(verts, n, backend);
 292   else if(verts[0].param[1] == verts[n-1].param[1]) //all v's are equal
 293     evalLineNOGE_BV(verts, n, backend);
 294   else
 295     {
 296       int i;
 297       for(i=0; i<n; i++)
 298         backend.tmeshvertNOGE(&verts[i]);
 299     }
 300 }
 301 #endif
 302
 303 inline void  OPT_OUTVERT(TrimVertex& vv, Backend& backend)
 304 {
 305
 306 #ifdef USE_OPTTT
 307   glNormal3fv(vv.cache_normal);
 308   glVertex3fv(vv.cache_point);
 309 #else
 310
 311   backend.tmeshvert(&vv);
 312
 313 #endif
 314
 315 }
 316
 317 static void triangulateRectAux(PwlArc* top, PwlArc* bot, PwlArc* left, PwlArc* right, Backend& backend);
 318
 319 static void triangulateRect(Arc_ptr loop, Backend& backend, int TB_or_LR, int ulinear, int vlinear)
 320 {
 321   //we know the loop is a rectangle, but not sure which is top
 322   Arc_ptr top, bot, left, right;
 323   if(loop->tail()[1] == loop->head()[1])
 324     {
 325       if(loop->tail()[1] > loop->prev->prev->tail()[1])
 326         {
 327
 328         top = loop;
 329         }
 330       else{
 331
 332         top = loop->prev->prev;
 333         }
 334     }
 335   else
 336     {
 337       if(loop->tail()[0] > loop->prev->prev->tail()[0])
 338         {
 339           //loop is the right arc
 340
 341           top = loop->next;
 342         }
 343       else
 344         {
 345
 346           top = loop->prev;
 347         }
 348     }
 349   left = top->next;
 350   bot  = left->next;
 351   right= bot->next;
 352
 353   //if u, v are both nonlinear, then if the
 354   //boundary is tessellated dense, we also
 355   //sample the inside to get a better tesslletant.
 356   if( (!ulinear) && (!vlinear))
 357     {
 358       int nu = top->pwlArc->npts;
 359       if(nu < bot->pwlArc->npts)
 360         nu = bot->pwlArc->npts;
 361       int nv = left->pwlArc->npts;
 362       if(nv < right->pwlArc->npts)
 363         nv = right->pwlArc->npts;
 364 /*
 365       if(nu > 2 && nv > 2)
 366         {
 367           triangulateRectGen(top, nu-2,  nv-2, backend);
 368           return;
 369         }
 370 */
 371     }
 372
 373   if(TB_or_LR == 1)
 374     triangulateRectAux(top->pwlArc, bot->pwlArc, left->pwlArc, right->pwlArc, backend);
 375   else if(TB_or_LR == -1)
 376     triangulateRectAux(left->pwlArc, right->pwlArc, bot->pwlArc, top->pwlArc, backend);
 377   else
 378     {
 379       Int maxPointsTB = top->pwlArc->npts + bot->pwlArc->npts;
 380       Int maxPointsLR = left->pwlArc->npts + right->pwlArc->npts;
 381
 382       if(maxPointsTB < maxPointsLR)
 383         triangulateRectAux(left->pwlArc, right->pwlArc, bot->pwlArc, top->pwlArc, backend);
 384       else
 385         triangulateRectAux(top->pwlArc, bot->pwlArc, left->pwlArc, right->pwlArc, backend);
 386     }
 387 }
 388
 389 static void triangulateRectAux(PwlArc* top, PwlArc* bot, PwlArc* left, PwlArc* right, Backend& backend)
 390 { //if(maxPointsTB >= maxPointsLR)
 391     {
 392
 393       Int d, topd_left, topd_right, botd_left, botd_right, i,j;
 394       d = left->npts /2;
 395
 396 #ifdef USE_OPTTT
 397       evalLineNOGE(top->pts, top->npts, backend);
 398       evalLineNOGE(bot->pts, bot->npts, backend);
 399       evalLineNOGE(left->pts, left->npts, backend);
 400       evalLineNOGE(right->pts, right->npts, backend);
 401 #endif
 402
 403       if(top->npts == 2) {
 404         backend.bgntfan();
 405         OPT_OUTVERT(top->pts[0], backend);//the root
 406         for(i=0; i<left->npts; i++){
 407           OPT_OUTVERT(left->pts[i], backend);
 408         }
 409         for(i=1; i<= bot->npts-2; i++){
 410           OPT_OUTVERT(bot->pts[i], backend);
 411         }
 412         backend.endtfan();
 413
 414         backend.bgntfan();
 415         OPT_OUTVERT(bot->pts[bot->npts-2], backend);
 416         for(i=0; i<right->npts; i++){
 417           OPT_OUTVERT(right->pts[i], backend);
 418         }
 419         backend.endtfan();
 420       }
 421       else if(bot->npts == 2) {
 422         backend.bgntfan();
 423         OPT_OUTVERT(bot->pts[0], backend);//the root
 424         for(i=0; i<right->npts; i++){
 425           OPT_OUTVERT(right->pts[i], backend);
 426         }
 427         for(i=1; i<= top->npts-2; i++){
 428           OPT_OUTVERT(top->pts[i], backend);
 429         }
 430         backend.endtfan();
 431
 432         backend.bgntfan();
 433         OPT_OUTVERT(top->pts[top->npts-2], backend);
 434         for(i=0; i<left->npts; i++){
 435           OPT_OUTVERT(left->pts[i], backend);
 436         }
 437         backend.endtfan();
 438       }
 439       else { //both top and bot have >=3 points
 440
 441         backend.bgntfan();
 442
 443         OPT_OUTVERT(top->pts[top->npts-2], backend);
 444
 445         for(i=0; i<=d; i++)
 446           {
 447             OPT_OUTVERT(left->pts[i], backend);
 448           }
 449         backend.endtfan();
 450
 451         backend.bgntfan();
 452
 453         OPT_OUTVERT(bot->pts[1], backend);
 454
 455         OPT_OUTVERT(top->pts[top->npts-2], backend);
 456
 457         for(i=d; i< left->npts; i++)
 458           {
 459             OPT_OUTVERT(left->pts[i], backend);
 460           }
 461         backend.endtfan();
 462
 463         d = right->npts/2;
 464         //output only when d<right->npts-1 and
 465         //
 466         if(d<right->npts-1)
 467           {
 468             backend.bgntfan();
 469             //      backend.tmeshvert(& top->pts[1]);
 470             OPT_OUTVERT(top->pts[1], backend);
 471             for(i=d; i< right->npts; i++)
 472               {
 473                 //        backend.tmeshvert(& right->pts[i]);
 474
 475                 OPT_OUTVERT(right->pts[i], backend);
 476
 477               }
 478             backend.endtfan();
 479           }
 480
 481         backend.bgntfan();
 482         //      backend.tmeshvert(& bot->pts[bot->npts-2]);
 483         OPT_OUTVERT( bot->pts[bot->npts-2], backend);
 484         for(i=0; i<=d; i++)
 485           {
 486             //    backend.tmeshvert(& right->pts[i]);
 487             OPT_OUTVERT(right->pts[i], backend);
 488
 489           }
 490
 491         //      backend.tmeshvert(& top->pts[1]);
 492         OPT_OUTVERT(top->pts[1], backend);
 493
 494         backend.endtfan();
 495
 496
 497         topd_left = top->npts-2;
 498         topd_right = 1; //topd_left>= topd_right
 499
 500         botd_left = 1;
 501         botd_right = bot->npts-2; //botd_left<= bot_dright
 502
 503
 504         if(top->npts < bot->npts)
 505           {
 506             int delta=bot->npts - top->npts;
 507             int u = delta/2;
 508             botd_left = 1+ u;
 509             botd_right = bot->npts-2-( delta-u);
 510
 511             if(botd_left >1)
 512               {
 513                 backend.bgntfan();
 514                 //        backend.tmeshvert(& top->pts[top->npts-2]);
 515                 OPT_OUTVERT(top->pts[top->npts-2], backend);
 516                 for(i=1; i<= botd_left; i++)
 517                   {
 518                     //        backend.tmeshvert(& bot->pts[i]);
 519                     OPT_OUTVERT(bot->pts[i] , backend);
 520                   }
 521                 backend.endtfan();
 522               }
 523             if(botd_right < bot->npts-2)
 524               {
 525                 backend.bgntfan();
 526                 OPT_OUTVERT(top->pts[1], backend);
 527                 for(i=botd_right; i<= bot->npts-2; i++)
 528                   OPT_OUTVERT(bot->pts[i], backend);
 529                 backend.endtfan();
 530               }
 531           }
 532         else if(top->npts> bot->npts)
 533           {
 534             int delta=top->npts-bot->npts;
 535             int u = delta/2;
 536             topd_left = top->npts-2 - u;
 537             topd_right = 1+delta-u;
 538
 539             if(topd_left < top->npts-2)
 540               {
 541                 backend.bgntfan();
 542                 //        backend.tmeshvert(& bot->pts[1]);
 543                 OPT_OUTVERT(bot->pts[1], backend);
 544                 for(i=topd_left; i<= top->npts-2; i++)
 545                   {
 546                     //        backend.tmeshvert(& top->pts[i]);
 547                     OPT_OUTVERT(top->pts[i], backend);
 548                   }
 549                 backend.endtfan();
 550               }
 551             if(topd_right > 1)
 552               {
 553                 backend.bgntfan();
 554                 OPT_OUTVERT(bot->pts[bot->npts-2], backend);
 555                 for(i=1; i<= topd_right; i++)
 556                   OPT_OUTVERT(top->pts[i], backend);
 557                 backend.endtfan();
 558               }
 559           }
 560
 561         if(topd_left <= topd_right)
 562           return;
 563
 564         backend.bgnqstrip();
 565         for(j=botd_left, i=topd_left; i>=topd_right; i--,j++)
 566           {
 567             //    backend.tmeshvert(& top->pts[i]);
 568             //    backend.tmeshvert(& bot->pts[j]);
 569             OPT_OUTVERT(top->pts[i], backend);
 570             OPT_OUTVERT(bot->pts[j], backend);
 571           }
 572         backend.endqstrip();
 573
 574       }
 575     }
 576 }
 577
 578
 579 static void triangulateRectCenter(int n_ulines, REAL* u_val,
 580                                   int n_vlines, REAL* v_val,
 581                                   Backend& backend)
 582 {
 583
 584   // XXX this code was patched by Diego Santa Cruz <Diego.SantaCruz@epfl.ch>
 585   // to fix a problem in which glMapGrid2f() was called with bad parameters.
 586   // This has beens submitted to SGI but not integrated as of May 1, 2001.
 587   if(n_ulines>1 && n_vlines>1) {
 588     backend.surfgrid(u_val[0], u_val[n_ulines-1], n_ulines-1,
 589                      v_val[n_vlines-1], v_val[0], n_vlines-1);
 590     backend.surfmesh(0,0,n_ulines-1,n_vlines-1);
 591   }
 592
 593   return;
 594
 595   /*
 596   for(i=0; i<n_vlines-1; i++)
 597     {
 598
 599       backend.bgnqstrip();
 600       for(j=0; j<n_ulines; j++)
 601         {
 602           trimVert.param[0] = u_val[j];
 603           trimVert.param[1] = v_val[i+1];
 604           backend.tmeshvert(& trimVert);
 605
 606           trimVert.param[1] = v_val[i];
 607           backend.tmeshvert(& trimVert);
 608         }
 609       backend.endqstrip();
 610
 611     }
 612     */
 613 }
 614
 615 //it works for top, bot, left ad right, you need ot select correct arguments
 616 static void triangulateRectTopGen(Arc_ptr arc, int n_ulines, REAL* u_val, Real v, int dir, int is_u, Backend& backend)
 617 {
 618
 619   if(is_u)
 620     {
 621       int i,k;
 622       REAL* upper_val = (REAL*) malloc(sizeof(REAL) * arc->pwlArc->npts);
 623       assert(upper_val);
 624       if(dir)
 625         {
 626           for(k=0,i=arc->pwlArc->npts-1; i>=0; i--,k++)
 627             {
 628               upper_val[k] = arc->pwlArc->pts[i].param[0];
 629             }
 630           backend.evalUStrip(arc->pwlArc->npts, arc->pwlArc->pts[0].param[1],
 631                              upper_val,
 632                              n_ulines, v, u_val);
 633         }
 634       else
 635         {
 636           for(k=0,i=0;  i<arc->pwlArc->npts; i++,k++)
 637             {
 638               upper_val[k] = arc->pwlArc->pts[i].param[0];
 639
 640             }
 641
 642           backend.evalUStrip(
 643                              n_ulines, v, u_val,
 644                              arc->pwlArc->npts, arc->pwlArc->pts[0].param[1], upper_val
 645                              );
 646         }
 647
 648       free(upper_val);
 649       return;
 650     }
 651   else //is_v
 652     {
 653       int i,k;
 654       REAL* left_val = (REAL*) malloc(sizeof(REAL) * arc->pwlArc->npts);
 655       assert(left_val);
 656       if(dir)
 657         {
 658           for(k=0,i=arc->pwlArc->npts-1; i>=0; i--,k++)
 659             {
 660               left_val[k] = arc->pwlArc->pts[i].param[1];
 661             }
 662           backend.evalVStrip(arc->pwlArc->npts, arc->pwlArc->pts[0].param[0],
 663                              left_val,
 664                              n_ulines, v, u_val);
 665         }
 666       else
 667         {
 668           for(k=0,i=0;  i<arc->pwlArc->npts; i++,k++)
 669             {
 670               left_val[k] = arc->pwlArc->pts[i].param[1];
 671             }
 672            backend.evalVStrip(
 673                              n_ulines, v, u_val,
 674                              arc->pwlArc->npts, arc->pwlArc->pts[0].param[0], left_val
 675                              );
 676         }
 677       free(left_val);
 678       return;
 679     }
 680
 681   //the following is a different version of the above code. If you comment
 682   //the above code, the following code will still work. The reason to leave
 683   //the folliwng code here is purely for testing purpose.
 684   /*
 685   int i,j;
 686   PwlArc* parc = arc->pwlArc;
 687   int d1 = parc->npts-1;
 688   int d2 = 0;
 689   TrimVertex trimVert;
 690   trimVert.nuid = 0;//????
 691   REAL* temp_u_val = u_val;
 692   if(dir ==0) //have to reverse u_val
 693     {
 694       temp_u_val = (REAL*) malloc(sizeof(REAL) * n_ulines);
 695       assert(temp_u_val);
 696       for(i=0; i<n_ulines; i++)
 697         temp_u_val[i] = u_val[n_ulines-1-i];
 698     }
 699   u_val = temp_u_val;
 700
 701   if(parc->npts > n_ulines)
 702     {
 703       d1 = n_ulines-1;
 704
 705       backend.bgntfan();
 706       if(is_u){
 707         trimVert.param[0] = u_val[0];
 708         trimVert.param[1] = v;
 709       }
 710       else
 711         {
 712         trimVert.param[1] = u_val[0];
 713         trimVert.param[0] = v;
 714       }
 715
 716       backend.tmeshvert(& trimVert);
 717       for(i=d1; i< parc->npts; i++)
 718         backend.tmeshvert(& parc->pts[i]);
 719       backend.endtfan();
 720
 721
 722     }
 723   else if(parc->npts < n_ulines)
 724     {
 725       d2 = n_ulines-parc->npts;
 726
 727
 728       backend.bgntfan();
 729       backend.tmeshvert(& parc->pts[parc->npts-1]);
 730       for(i=0; i<= d2; i++)
 731         {
 732           if(is_u){
 733             trimVert.param[0] = u_val[i];
 734             trimVert.param[1] = v;
 735           }
 736           else
 737             {
 738               trimVert.param[1] = u_val[i];
 739               trimVert.param[0] = v;
 740             }
 741           backend.tmeshvert(&trimVert);
 742         }
 743       backend.endtfan();
 744
 745     }
 746   if(d1>0){
 747
 748
 749     backend.bgnqstrip();
 750     for(i=d1, j=d2; i>=0; i--, j++)
 751       {
 752         backend.tmeshvert(& parc->pts[i]);
 753
 754         if(is_u){
 755           trimVert.param[0] = u_val[j];
 756           trimVert.param[1] = v;
 757         }
 758         else{
 759           trimVert.param[1] = u_val[j];
 760           trimVert.param[0] = v;
 761         }
 762         backend.tmeshvert(&trimVert);
 763
 764
 765
 766       }
 767     backend.endqstrip();
 768
 769
 770   }
 771   if(dir == 0)  //temp_u_val was mallocated
 772     free(temp_u_val);
 773  */
 774 }
 775
 776 //n_ulines is the number of ulines inside, and n_vlines is the number of vlines
 777 //inside, different from meanings elsewhere!!!
 778 static void triangulateRectGen(Arc_ptr loop, int n_ulines, int n_vlines, Backend& backend)
 779 {
 780
 781   int i;
 782   //we know the loop is a rectangle, but not sure which is top
 783   Arc_ptr top, bot, left, right;
 784
 785   if(equalRect(loop->tail()[1] ,  loop->head()[1]))
 786     {
 787
 788       if(loop->tail()[1] > loop->prev->prev->tail()[1])
 789         {
 790
 791         top = loop;
 792         }
 793       else{
 794
 795         top = loop->prev->prev;
 796         }
 797     }
 798   else
 799     {
 800       if(loop->tail()[0] > loop->prev->prev->tail()[0])
 801         {
 802           //loop is the right arc
 803
 804           top = loop->next;
 805         }
 806       else
 807         {
 808
 809           top = loop->prev;
 810         }
 811     }
 812
 813   left = top->next;
 814   bot  = left->next;
 815   right= bot->next;
 816
 817 #ifdef COUNT_TRIANGLES
 818   num_triangles += loop->pwlArc->npts +
 819                  left->pwlArc->npts +
 820                  bot->pwlArc->npts +
 821                   right->pwlArc->npts
 822                       + 2*n_ulines + 2*n_vlines
 823                         -8;
 824   num_quads += (n_ulines-1)*(n_vlines-1);
 825 #endif
 826 /*
 827   backend.surfgrid(left->tail()[0], right->tail()[0], n_ulines+1,
 828                    top->tail()[1], bot->tail()[1], n_vlines+1);
 829 //  if(n_ulines>1 && n_vlines>1)
 830     backend.surfmesh(0,0,n_ulines+1,n_vlines+1);
 831 return;
 832 */
 833   REAL* u_val=(REAL*) malloc(sizeof(REAL)*n_ulines);
 834   assert(u_val);
 835   REAL* v_val=(REAL*)malloc(sizeof(REAL) * n_vlines);
 836   assert(v_val);
 837   REAL u_stepsize = (right->tail()[0] - left->tail()[0])/( (REAL) n_ulines+1);
 838   REAL v_stepsize = (top->tail()[1] - bot->tail()[1])/( (REAL) n_vlines+1);
 839   Real temp=left->tail()[0]+u_stepsize;
 840   for(i=0; i<n_ulines; i++)
 841     {
 842       u_val[i] = temp;
 843       temp += u_stepsize;
 844     }
 845   temp = bot->tail()[1] + v_stepsize;
 846   for(i=0; i<n_vlines; i++)
 847     {
 848       v_val[i] = temp;
 849       temp += v_stepsize;
 850     }
 851
 852   triangulateRectTopGen(top, n_ulines, u_val, v_val[n_vlines-1], 1,1, backend);
 853   triangulateRectTopGen(bot, n_ulines, u_val, v_val[0], 0, 1, backend);
 854   triangulateRectTopGen(left, n_vlines, v_val, u_val[0], 1, 0, backend);
 855   triangulateRectTopGen(right, n_vlines, v_val, u_val[n_ulines-1], 0,0, backend);
 856
 857
 858
 859
 860   //triangulate the center
 861   triangulateRectCenter(n_ulines, u_val, n_vlines, v_val, backend);
 862
 863   free(u_val);
 864   free(v_val);
 865
 866 }
 867
 868
 869
 870
 871 /**********for reading newtess_flag from a file**********/
 872 #ifdef USE_READ_FLAG
 873 static Int read_flag(char* name)
 874 {
 875   Int ret;
 876   FILE* fp = fopen(name, "r");
 877   if(fp == NULL)
 878     {
 879       fprintf(stderr, "can't open file %s\n", name);
 880       exit(1);
 881     }
 882   fscanf(fp, "%i", &ret);
 883   fclose(fp);
 884   return ret;
 885 }
 886 #endif
 887
 888 /***********nextgen tess****************/
 889 #include "sampleMonoPoly.h"
 890 directedLine* arcToDLine(Arc_ptr arc)
 891 {
 892   int i;
 893   Real vert[2];
 894   directedLine* ret;
 895   sampledLine* sline = new sampledLine(arc->pwlArc->npts);
 896   for(i=0; i<arc->pwlArc->npts; i++)
 897     {
 898       vert[0] = arc->pwlArc->pts[i].param[0];
 899       vert[1] = arc->pwlArc->pts[i].param[1];
 900       sline->setPoint(i, vert);
 901     }
 902   ret = new directedLine(INCREASING, sline);
 903   return ret;
 904 }
 905
 906 /*an pwlArc may not be a straight line*/
 907 directedLine* arcToMultDLines(directedLine* original, Arc_ptr arc)
 908 {
 909   directedLine* ret = original;
 910   int is_linear = 0;
 911   if(arc->pwlArc->npts == 2 )
 912     is_linear = 1;
 913   else if(area(arc->pwlArc->pts[0].param, arc->pwlArc->pts[1].param, arc->pwlArc->pts[arc->pwlArc->npts-1].param) == 0.0)
 914     is_linear = 1;
 915
 916   if(is_linear)
 917     {
 918       directedLine *dline = arcToDLine(arc);
 919       if(ret == NULL)
 920         ret = dline;
 921       else
 922         ret->insert(dline);
 923       return ret;
 924     }
 925   else /*not linear*/
 926     {
 927       for(Int i=0; i<arc->pwlArc->npts-1; i++)
 928         {
 929           Real vert[2][2];
 930           vert[0][0] = arc->pwlArc->pts[i].param[0];
 931           vert[0][1] = arc->pwlArc->pts[i].param[1];
 932           vert[1][0] = arc->pwlArc->pts[i+1].param[0];
 933           vert[1][1] = arc->pwlArc->pts[i+1].param[1];
 934
 935           sampledLine *sline = new sampledLine(2, vert);
 936           directedLine *dline = new directedLine(INCREASING, sline);
 937           if(ret == NULL)
 938             ret = dline;
 939           else
 940             ret->insert(dline);
 941         }
 942       return ret;
 943     }
 944 }
 945
 946
 947
 948 directedLine* arcLoopToDLineLoop(Arc_ptr loop)
 949 {
 950   directedLine* ret;
 951
 952   if(loop == NULL)
 953     return NULL;
 954   ret = arcToMultDLines(NULL, loop);
 955 //ret->printSingle();
 956   for(Arc_ptr temp = loop->next; temp != loop; temp = temp->next){
 957     ret = arcToMultDLines(ret, temp);
 958 //ret->printSingle();
 959   }
 960
 961   return ret;
 962 }
 963
 964 /*
 965 void Slicer::evalRBArray(rectBlockArray* rbArray, gridWrap* grid)
 966 {
 967   TrimVertex *trimVert = (TrimVertex*)malloc(sizeof(TrimVertex));
 968   trimVert -> nuid = 0;//????
 969
 970   Real* u_values = grid->get_u_values();
 971   Real* v_values = grid->get_v_values();
 972
 973   Int i,j,k,l;
 974
 975   for(l=0; l<rbArray->get_n_elements(); l++)
 976     {
 977       rectBlock* block = rbArray->get_element(l);
 978       for(k=0, i=block->get_upGridLineIndex(); i>block->get_lowGridLineIndex(); i--, k++)
 979         {
 980
 981           backend.bgnqstrip();
 982           for(j=block->get_leftIndices()[k+1]; j<= block->get_rightIndices()[k+1]; j++)
 983             {
 984               trimVert->param[0] = u_values[j];
 985               trimVert->param[1] = v_values[i];
 986               backend.tmeshvert(trimVert);
 987
 988               trimVert->param[1] = v_values[i-1];
 989               backend.tmeshvert(trimVert);
 990
 991             }
 992           backend.endqstrip();
 993
 994         }
 995     }
 996
 997   free(trimVert);
 998 }
 999 */
1000
1001 void Slicer::evalRBArray(rectBlockArray* rbArray, gridWrap* grid)
1002 {
1003   Int i,j,k;
1004
1005   Int n_vlines=grid->get_n_vlines();
1006   //the reason to switch the position of v_max and v_min is because of the
1007   //the orientation problem. glEvalMesh generates quad_strip clockwise, but
1008   //we need counter-clockwise.
1009   backend.surfgrid(grid->get_u_min(), grid->get_u_max(), grid->get_n_ulines()-1,
1010                    grid->get_v_max(), grid->get_v_min(), n_vlines-1);
1011
1012
1013   for(j=0; j<rbArray->get_n_elements(); j++)
1014     {
1015       rectBlock* block = rbArray->get_element(j);
1016       Int low = block->get_lowGridLineIndex();
1017       Int high = block->get_upGridLineIndex();
1018
1019       for(k=0, i=high; i>low; i--, k++)
1020         {
1021           backend.surfmesh(block->get_leftIndices()[k+1], n_vlines-1-i, block->get_rightIndices()[k+1]-block->get_leftIndices()[k+1], 1);
1022         }
1023     }
1024 }
1025
1026
1027 void Slicer::evalStream(primStream* pStream)
1028 {
1029   Int i,j,k;
1030   k=0;
1031 /*  TrimVertex X;*/
1032   TrimVertex *trimVert =/*&X*/  (TrimVertex*)malloc(sizeof(TrimVertex));
1033   trimVert -> nuid = 0;//???
1034   Real* vertices = pStream->get_vertices(); //for efficiency
1035   for(i=0; i<pStream->get_n_prims(); i++)
1036     {
1037
1038      //ith primitive  has #vertices = lengths[i], type=types[i]
1039       switch(pStream->get_type(i)){
1040       case PRIMITIVE_STREAM_FAN:
1041
1042         backend.bgntfan();
1043
1044         for(j=0; j<pStream->get_length(i); j++)
1045           {
1046             trimVert->param[0] = vertices[k];
1047             trimVert->param[1] = vertices[k+1];
1048             backend.tmeshvert(trimVert);
1049
1050 //          backend.tmeshvert(vertices[k], vertices[k+1]);
1051             k += 2;
1052           }
1053         backend.endtfan();
1054         break;
1055
1056       default:
1057         fprintf(stderr, "evalStream: not implemented yet\n");
1058         exit(1);
1059
1060       }
1061     }
1062   free(trimVert);
1063 }
1064
1065
1066
1067
1068 void Slicer::slice_new(Arc_ptr loop)
1069 {
1070 //count++;
1071 //if(count == 78) count=1;
1072 //printf("count=%i\n", count);
1073 //if( ! (4<= count && count <=4)) return;
1074
1075
1076   Int num_ulines;
1077   Int num_vlines;
1078   Real uMin, uMax, vMin, vMax;
1079   Real mydu, mydv;
1080   uMin = uMax = loop->tail()[0];
1081   vMin = vMax = loop->tail()[1];
1082   mydu = (du>0)? du: -du;
1083   mydv = (dv>0)? dv: -dv;
1084
1085   for(Arc_ptr jarc=loop->next; jarc != loop; jarc = jarc->next)
1086    {
1087
1088      if(jarc->tail()[0] < uMin)
1089        uMin = jarc->tail()[0];
1090      if(jarc->tail()[0] > uMax)
1091        uMax = jarc->tail()[0];
1092      if(jarc->tail()[1] < vMin)
1093        vMin = jarc->tail()[1];
1094      if(jarc->tail()[1] > vMax)
1095        vMax = jarc->tail()[1];
1096    }
1097
1098   if (uMax == uMin)
1099     return; // prevent divide-by-zero.  Jon Perry.  17 June 2002
1100
1101   if(mydu > uMax - uMin)
1102     num_ulines = 2;
1103   else
1104     {
1105       num_ulines = 3 + (Int) ((uMax-uMin)/mydu);
1106     }
1107   if(mydv>=vMax-vMin)
1108     num_vlines = 2;
1109   else
1110     {
1111       num_vlines = 2+(Int)((vMax-vMin)/mydv);
1112     }
1113
1114   Int isRect = is_rect(loop);
1115
1116   if(isRect && (num_ulines<=2 || num_vlines<=2))
1117     {
1118       if(vlinear)
1119         triangulateRect(loop, backend, 1, ulinear, vlinear);
1120       else if(ulinear)
1121         triangulateRect(loop, backend, -1, ulinear, vlinear);
1122       else
1123         triangulateRect(loop, backend, 0, ulinear, vlinear);
1124     }
1125
1126    else if(isRect)
1127     {
1128       triangulateRectGen(loop, num_ulines-2, num_vlines-2, backend);
1129     }
1130   else if( (num_ulines<=2 || num_vlines <=2) && ulinear)
1131     {
1132       monoTriangulationFunBackend(loop, compV2InY, &backend);
1133     }
1134   else if( (!ulinear) && (!vlinear) && (num_ulines == 2) && (num_vlines > 2))
1135     {
1136       monoTriangulationFunBackend(loop, compV2InY, &backend);
1137     }
1138   else
1139     {
1140       directedLine* poly = arcLoopToDLineLoop(loop);
1141
1142       gridWrap grid(num_ulines, num_vlines, uMin, uMax, vMin, vMax);
1143       primStream pStream(20, 20);
1144       rectBlockArray rbArray(20);
1145
1146       sampleMonoPoly(poly, &grid, ulinear, vlinear, &pStream, &rbArray);
1147
1148       evalStream(&pStream);
1149
1150       evalRBArray(&rbArray, &grid);
1151
1152 #ifdef COUNT_TRIANGLES
1153       num_triangles += pStream.num_triangles();
1154       num_quads += rbArray.num_quads();
1155 #endif
1156       poly->deleteSinglePolygonWithSline();
1157     }
1158
1159 #ifdef COUNT_TRIANGLES
1160   printf("num_triangles=%i\n", num_triangles);
1161   printf("num_quads = %i\n", num_quads);
1162 #endif
1163 }
1164
1165 void Slicer::slice(Arc_ptr loop)
1166 {
1167 #ifdef USE_READ_FLAG
1168   if(read_flag("flagFile"))
1169     slice_new(loop);
1170   else
1171     slice_old(loop);
1172
1173 #else
1174     slice_new(loop);
1175 #endif
1176
1177 }
1178
1179
1180
1181 Slicer::Slicer( Backend &b )
1182         : CoveAndTiler( b ), Mesher( b ), backend( b )
1183 {
1184     oneOverDu = 0;
1185     du = 0;
1186     dv = 0;
1187     isolines = 0;
1188     ulinear = 0;
1189     vlinear = 0;
1190 }
1191
1192 Slicer::~Slicer()
1193 {
1194 }
1195
1196 void
1197 Slicer::setisolines( int x )
1198 {
1199     isolines = x;
1200 }
1201
1202 void
1203 Slicer::setstriptessellation( REAL x, REAL y )
1204 {
1205     assert(x > 0 && y > 0);
1206     du = x;
1207     dv = y;
1208     setDu( du );
1209 }
1210
1211 void
1212 Slicer::slice_old( Arc_ptr loop )
1213 {
1214     loop->markverts();
1215
1216     Arc_ptr extrema[4];
1217     loop->getextrema( extrema );
1218
1219     unsigned int npts = loop->numpts();
1220     TrimRegion::init( npts, extrema[0] );
1221
1222     Mesher::init( npts );
1223
1224     long ulines = uarray.init( du, extrema[1], extrema[3] );
1225 //printf("ulines = %i\n", ulines);
1226     Varray varray;
1227     long vlines = varray.init( dv, extrema[0], extrema[2] );
1228 //printf("vlines = %i\n", vlines);
1229     long botv = 0;
1230     long topv;
1231     TrimRegion::init( varray.varray[botv] );
1232     getGridExtent( &extrema[0]->pwlArc->pts[0], &extrema[0]->pwlArc->pts[0] );
1233
1234     for( long quad=0; quad<varray.numquads; quad++ ) {
1235         backend.surfgrid( uarray.uarray[0],
1236                        uarray.uarray[ulines-1],
1237                        ulines-1,
1238                        varray.vval[quad],
1239                        varray.vval[quad+1],
1240                        varray.voffset[quad+1] - varray.voffset[quad] );
1241
1242         for( long i=varray.voffset[quad]+1; i <= varray.voffset[quad+1]; i++ ) {
1243             topv = botv++;
1244             advance( topv - varray.voffset[quad],
1245                      botv - varray.voffset[quad],
1246                      varray.varray[botv] );
1247             if( i == vlines )
1248                 getPts( extrema[2] );
1249             else
1250                 getPts( backend );
1251             getGridExtent();
1252             if( isolines ) {
1253                 outline();
1254             } else {
1255                 if( canTile() )
1256                     coveAndTile();
1257                 else
1258                     mesh();
1259             }
1260         }
1261    }
1262 }
1263
1264
1265 void
1266 Slicer::outline( void )
1267 {
1268     GridTrimVertex upper, lower;
1269     Hull::init( );
1270
1271     backend.bgnoutline();
1272     while( (nextupper( &upper )) ) {
1273         if( upper.isGridVert() )
1274             backend.linevert( upper.g );
1275         else
1276             backend.linevert( upper.t );
1277     }
1278     backend.endoutline();
1279
1280     backend.bgnoutline();
1281     while( (nextlower( &lower )) ) {
1282         if( lower.isGridVert() )
1283             backend.linevert( lower.g );
1284         else
1285             backend.linevert( lower.t );
1286     }
1287     backend.endoutline();
1288 }
1289
1290
1291 void
1292 Slicer::outline( Arc_ptr jarc )
1293 {
1294     jarc->markverts();
1295
1296     if( jarc->pwlArc->npts >= 2 ) {
1297         backend.bgnoutline();
1298         for( int j = jarc->pwlArc->npts-1; j >= 0; j--  )
1299             backend.linevert( &(jarc->pwlArc->pts[j]) );
1300         backend.endoutline();
1301     }
1302 }
1303
1304