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