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