src/glu/sgi/libnurbs/internals/monoTriangulationBackend.cc

   1 /*
   2 ** License Applicability. Except to the extent portions of this file are
   3 ** made subject to an alternative license as permitted in the SGI Free
   4 ** Software License B, Version 1.1 (the "License"), the contents of this
   5 ** file are subject only to the provisions of the License. You may not use
   6 ** this file except in compliance with the License. You may obtain a copy
   7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
   8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
   9 **
  10 ** http://oss.sgi.com/projects/FreeB
  11 **
  12 ** Note that, as provided in the License, the Software is distributed on an
  13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
  14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
  15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
  16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
  17 **
  18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
  19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
  20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
  21 ** Copyright in any portions created by third parties is as indicated
  22 ** elsewhere herein. All Rights Reserved.
  23 **
  24 ** Additional Notice Provisions: The application programming interfaces
  25 ** established by SGI in conjunction with the Original Code are The
  26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
  27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
  28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
  29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
  30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
  31 ** published by SGI, but has not been independently verified as being
  32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
  33 **
  34 */
  35 /*
  36 */
  37
  38 #include "monoTriangulation.h"
  39 #include "polyUtil.h"
  40 #include "backend.h"
  41 #include "arc.h"
  42
  43 void reflexChain::outputFan(Real v[2], Backend* backend)
  44 {
  45   Int i;
  46   /*
  47   TrimVertex trimVert;
  48   */
  49   backend->bgntfan();
  50
  51   /*
  52   trimVert.param[0]=v[0];
  53   trimVert.param[1]=v[1];
  54   backend->tmeshvert(&trimVert);
  55   */
  56   backend->tmeshvert(v[0], v[1]);
  57
  58   if(isIncreasing) {
  59     for(i=0; i<index_queue; i++)
  60       {
  61         /*
  62         trimVert.param[0]=queue[i][0];
  63         trimVert.param[1]=queue[i][1];
  64         backend->tmeshvert(&trimVert);
  65         */
  66         backend->tmeshvert(queue[i][0], queue[i][1]);
  67       }
  68   }
  69   else {
  70     for(i=index_queue-1; i>=0; i--)
  71       {
  72         /*
  73         trimVert.param[0]=queue[i][0];
  74         trimVert.param[1]=queue[i][1];
  75         backend->tmeshvert(&trimVert);
  76         */
  77         backend->tmeshvert(queue[i][0], queue[i][1]);
  78       }
  79   }
  80   backend->endtfan();
  81 }
  82
  83 void reflexChain::processNewVertex(Real v[2], Backend* backend)
  84 {
  85   Int i,j,k;
  86   Int isReflex;
  87   /*TrimVertex trimVert;*/
  88   /*if there are at most one vertex in the queue, then simply insert
  89    */
  90   if(index_queue <=1){
  91     insert(v);
  92     return;
  93   }
  94
  95   /*there are at least two vertices in the queue*/
  96   j=index_queue-1;
  97
  98   for(i=j; i>=1; i--) {
  99     if(isIncreasing) {
 100       isReflex = (area(queue[i-1], queue[i], v) <= 0.0);
 101     }
 102     else /*decreasing*/{
 103       isReflex = (area(v, queue[i], queue[i-1]) <= 0.0);
 104     }
 105     if(isReflex) {
 106       break;
 107     }
 108   }
 109
 110   /*
 111    *if i<j then vertices: i+1--j are convex
 112    * output triangle fan:
 113    *  v, and queue[i], i+1, ..., j
 114    */
 115   if(i<j)
 116     {
 117       backend->bgntfan();
 118       /*
 119       trimVert.param[0]=v[0];
 120       trimVert.param[1]=v[1];
 121       backend->tmeshvert(& trimVert);
 122       */
 123       backend->tmeshvert(v[0], v[1]);
 124
 125       if(isIncreasing) {
 126         for(k=i; k<=j; k++)
 127           {
 128             /*
 129             trimVert.param[0]=queue[k][0];
 130             trimVert.param[1]=queue[k][1];
 131             backend->tmeshvert(& trimVert);
 132             */
 133             backend->tmeshvert(queue[k][0], queue[k][1]);
 134           }
 135       }
 136       else {
 137         for(k=j; k>=i; k--)
 138           {
 139             /*
 140             trimVert.param[0]=queue[k][0];
 141             trimVert.param[1]=queue[k][1];
 142             backend->tmeshvert(& trimVert);
 143             */
 144             backend->tmeshvert(queue[k][0], queue[k][1]);
 145           }
 146       }
 147
 148       backend->endtfan();
 149     }
 150
 151   /*delete vertices i+1--j from the queue*/
 152   index_queue = i+1;
 153   /*finally insert v at the end of the queue*/
 154   insert(v);
 155
 156 }
 157
 158
 159 void monoTriangulationRec(Real* topVertex, Real* botVertex,
 160                           vertexArray* inc_chain, Int inc_current,
 161                           vertexArray* dec_chain, Int dec_current,
 162                           Backend* backend)
 163 {
 164   assert( inc_chain != NULL && dec_chain != NULL);
 165   assert( ! (inc_current>=inc_chain->getNumElements() &&
 166              dec_current>=dec_chain->getNumElements()));
 167   Int inc_nVertices;
 168   Int dec_nVertices;
 169   Real** inc_array ;
 170   Real** dec_array ;
 171   Int i;
 172   assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
 173
 174   if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
 175     {
 176
 177       dec_array = dec_chain->getArray();
 178       dec_nVertices = dec_chain->getNumElements();
 179       reflexChain rChain(20,0);
 180       /*put the top vertex into the reflex chain*/
 181       rChain.processNewVertex(topVertex, backend);
 182       /*process all the vertices on the dec_chain*/
 183       for(i=dec_current; i<dec_nVertices; i++){
 184         rChain.processNewVertex(dec_array[i], backend);
 185       }
 186       /*process the bottom vertex*/
 187       rChain.processNewVertex(botVertex, backend);
 188
 189     }
 190   else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
 191     {
 192       inc_array = inc_chain->getArray();
 193       inc_nVertices= inc_chain->getNumElements();
 194       reflexChain rChain(20,1);
 195       /*put the top vertex into the reflex chain*/
 196       rChain.processNewVertex(topVertex, backend);
 197       /*process all the vertices on the inc_chain*/
 198       for(i=inc_current; i<inc_nVertices; i++){
 199         rChain.processNewVertex(inc_array[i], backend);
 200       }
 201       /*process the bottom vertex*/
 202       rChain.processNewVertex(botVertex, backend);
 203     }
 204   else /*neither chain is empty*/
 205     {
 206       inc_array = inc_chain -> getArray();
 207       dec_array = dec_chain -> getArray();
 208       inc_nVertices= inc_chain->getNumElements();
 209       dec_nVertices= dec_chain->getNumElements();
 210       /*if top of inc_chain is 'lower' than top of dec_chain, process all the
 211        *vertices on the dec_chain which are higher than top of inc_chain
 212        */
 213       if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
 214         {
 215
 216           reflexChain rChain(20, 0);
 217           rChain.processNewVertex(topVertex, backend);
 218           for(i=dec_current; i<dec_nVertices; i++)
 219             {
 220               if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
 221                 rChain.processNewVertex(dec_array[i], backend);
 222               else
 223                 break;
 224             }
 225           rChain.outputFan(inc_array[inc_current], backend);
 226           monoTriangulationRec(dec_array[i-1], botVertex,
 227                                inc_chain, inc_current,
 228                                dec_chain, i,
 229                                backend);
 230         }
 231       else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
 232         {
 233
 234           reflexChain rChain(20, 1);
 235           rChain.processNewVertex(topVertex, backend);
 236           for(i=inc_current; i<inc_nVertices; i++)
 237             {
 238               if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
 239                 rChain.processNewVertex(inc_array[i], backend);
 240               else
 241                 break;
 242             }
 243           rChain.outputFan(dec_array[dec_current], backend);
 244           monoTriangulationRec(inc_array[i-1], botVertex,
 245                                inc_chain, i,
 246                                dec_chain, dec_current,
 247                                backend);
 248         }
 249     }/*end case neither is empty*/
 250 }
 251
 252
 253 void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend)
 254 {
 255   Int i;
 256   /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
 257    *then call monoTriangulationRec
 258    */
 259   Arc_ptr tempV;
 260   Arc_ptr topV;
 261   Arc_ptr botV;
 262   topV = botV = loop;
 263   for(tempV = loop->next; tempV != loop; tempV = tempV->next)
 264     {
 265       if(compFun(topV->tail(), tempV->tail())<0) {
 266         topV = tempV;
 267       }
 268       if(compFun(botV->tail(), tempV->tail())>0) {
 269         botV = tempV;
 270       }
 271     }
 272
 273   /*creat increase and decrease chains*/
 274   vertexArray inc_chain(20); /*this is a dynamic array*/
 275   for(i=1; i<=topV->pwlArc->npts-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
 276     inc_chain.appendVertex(topV->pwlArc->pts[i].param);
 277   }
 278   for(tempV = topV->next; tempV != botV; tempV = tempV->next)
 279     {
 280       for(i=0; i<=tempV->pwlArc->npts-2; i++){
 281         inc_chain.appendVertex(tempV->pwlArc->pts[i].param);
 282       }
 283     }
 284
 285   vertexArray dec_chain(20);
 286   for(tempV = topV->prev; tempV != botV; tempV = tempV->prev)
 287     {
 288       for(i=tempV->pwlArc->npts-2; i>=0; i--){
 289         dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
 290       }
 291     }
 292   for(i=botV->pwlArc->npts-2; i>=1; i--){
 293     dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
 294   }
 295
 296   monoTriangulationRecFunBackend(topV->tail(), botV->tail(), &inc_chain, 0, &dec_chain, 0, compFun, backend);
 297
 298 }
 299
 300 /*if compFun == compV2InY, top to bottom: V-monotone
 301  *if compFun == compV2InX, right to left: U-monotone
 302  */
 303 void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex,
 304                           vertexArray* inc_chain, Int inc_current,
 305                           vertexArray* dec_chain, Int dec_current,
 306                           Int  (*compFun)(Real*, Real*),
 307                           Backend* backend)
 308 {
 309   assert( inc_chain != NULL && dec_chain != NULL);
 310   assert( ! (inc_current>=inc_chain->getNumElements() &&
 311              dec_current>=dec_chain->getNumElements()));
 312   Int inc_nVertices;
 313   Int dec_nVertices;
 314   Real** inc_array ;
 315   Real** dec_array ;
 316   Int i;
 317   assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
 318
 319   if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
 320     {
 321
 322       dec_array = dec_chain->getArray();
 323       dec_nVertices = dec_chain->getNumElements();
 324       reflexChain rChain(20,0);
 325       /*put the top vertex into the reflex chain*/
 326       rChain.processNewVertex(topVertex, backend);
 327       /*process all the vertices on the dec_chain*/
 328       for(i=dec_current; i<dec_nVertices; i++){
 329         rChain.processNewVertex(dec_array[i], backend);
 330       }
 331       /*process the bottom vertex*/
 332       rChain.processNewVertex(botVertex, backend);
 333
 334     }
 335   else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
 336     {
 337       inc_array = inc_chain->getArray();
 338       inc_nVertices= inc_chain->getNumElements();
 339       reflexChain rChain(20,1);
 340       /*put the top vertex into the reflex chain*/
 341       rChain.processNewVertex(topVertex, backend);
 342       /*process all the vertices on the inc_chain*/
 343       for(i=inc_current; i<inc_nVertices; i++){
 344         rChain.processNewVertex(inc_array[i], backend);
 345       }
 346       /*process the bottom vertex*/
 347       rChain.processNewVertex(botVertex, backend);
 348     }
 349   else /*neither chain is empty*/
 350     {
 351       inc_array = inc_chain -> getArray();
 352       dec_array = dec_chain -> getArray();
 353       inc_nVertices= inc_chain->getNumElements();
 354       dec_nVertices= dec_chain->getNumElements();
 355       /*if top of inc_chain is 'lower' than top of dec_chain, process all the
 356        *vertices on the dec_chain which are higher than top of inc_chain
 357        */
 358       if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
 359         {
 360
 361           reflexChain rChain(20, 0);
 362           rChain.processNewVertex(topVertex, backend);
 363           for(i=dec_current; i<dec_nVertices; i++)
 364             {
 365               if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
 366                 rChain.processNewVertex(dec_array[i], backend);
 367               else
 368                 break;
 369             }
 370           rChain.outputFan(inc_array[inc_current], backend);
 371           monoTriangulationRecFunBackend(dec_array[i-1], botVertex,
 372                                inc_chain, inc_current,
 373                                dec_chain, i,
 374                                compFun,
 375                                backend);
 376         }
 377       else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
 378         {
 379
 380           reflexChain rChain(20, 1);
 381           rChain.processNewVertex(topVertex, backend);
 382           for(i=inc_current; i<inc_nVertices; i++)
 383             {
 384               if(compFun(inc_array[i], dec_array[dec_current]) >0)
 385                 rChain.processNewVertex(inc_array[i], backend);
 386               else
 387                 break;
 388             }
 389           rChain.outputFan(dec_array[dec_current], backend);
 390           monoTriangulationRecFunBackend(inc_array[i-1], botVertex,
 391                                inc_chain, i,
 392                                dec_chain, dec_current,
 393                                compFun,
 394                                backend);
 395         }
 396     }/*end case neither is empty*/
 397 }