reactos/lib/glu32/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 ** $Date$ $Revision: 1.1 $
  35 */
  36 /*
  37 ** $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libnurbs/internals/monoTriangulationBackend.cc,v 1.1 2004/02/02 16:39:12 navaraf Exp $
  38 */
  39
  40 #include "monoTriangulation.h"
  41 #include "polyUtil.h"
  42 #include "backend.h"
  43 #include "arc.h"
  44
  45 void reflexChain::outputFan(Real v[2], Backend* backend)
  46 {
  47   Int i;
  48
  49   backend->bgntfan();
  50   backend->tmeshvert(v[0], v[1]);
  51
  52   if(isIncreasing) {
  53     for(i=0; i<index_queue; i++)
  54       {
  55         /*
  56         trimVert.param[0]=queue[i][0];
  57         trimVert.param[1]=queue[i][1];
  58         backend->tmeshvert(&trimVert);
  59         */
  60         backend->tmeshvert(queue[i][0], queue[i][1]);
  61       }
  62   }
  63   else {
  64     for(i=index_queue-1; i>=0; i--)
  65       {
  66         /*
  67         trimVert.param[0]=queue[i][0];
  68         trimVert.param[1]=queue[i][1];
  69         backend->tmeshvert(&trimVert);
  70         */
  71         backend->tmeshvert(queue[i][0], queue[i][1]);
  72       }
  73   }
  74   backend->endtfan();
  75 }
  76
  77 void reflexChain::processNewVertex(Real v[2], Backend* backend)
  78 {
  79   Int i,j,k;
  80   Int isReflex;
  81
  82   /*if there are at most one vertex in the queue, then simply insert
  83    */
  84   if(index_queue <=1){
  85     insert(v);
  86     return;
  87   }
  88
  89   /*there are at least two vertices in the queue*/
  90   j=index_queue-1;
  91
  92   for(i=j; i>=1; i--) {
  93     if(isIncreasing) {
  94       isReflex = (area(queue[i-1], queue[i], v) <= 0.0);
  95     }
  96     else /*decreasing*/{
  97       isReflex = (area(v, queue[i], queue[i-1]) <= 0.0);
  98     }
  99     if(isReflex) {
 100       break;
 101     }
 102   }
 103
 104   /*
 105    *if i<j then vertices: i+1--j are convex
 106    * output triangle fan:
 107    *  v, and queue[i], i+1, ..., j
 108    */
 109   if(i<j)
 110     {
 111       backend->bgntfan();
 112       /*
 113       trimVert.param[0]=v[0];
 114       trimVert.param[1]=v[1];
 115       backend->tmeshvert(& trimVert);
 116       */
 117       backend->tmeshvert(v[0], v[1]);
 118
 119       if(isIncreasing) {
 120         for(k=i; k<=j; k++)
 121           {
 122             /*
 123             trimVert.param[0]=queue[k][0];
 124             trimVert.param[1]=queue[k][1];
 125             backend->tmeshvert(& trimVert);
 126             */
 127             backend->tmeshvert(queue[k][0], queue[k][1]);
 128           }
 129       }
 130       else {
 131         for(k=j; k>=i; k--)
 132           {
 133             /*
 134             trimVert.param[0]=queue[k][0];
 135             trimVert.param[1]=queue[k][1];
 136             backend->tmeshvert(& trimVert);
 137             */
 138             backend->tmeshvert(queue[k][0], queue[k][1]);
 139           }
 140       }
 141
 142       backend->endtfan();
 143     }
 144
 145   /*delete vertices i+1--j from the queue*/
 146   index_queue = i+1;
 147   /*finally insert v at the end of the queue*/
 148   insert(v);
 149
 150 }
 151
 152
 153 void monoTriangulationRec(Real* topVertex, Real* botVertex,
 154                           vertexArray* inc_chain, Int inc_current,
 155                           vertexArray* dec_chain, Int dec_current,
 156                           Backend* backend)
 157 {
 158   assert( inc_chain != NULL && dec_chain != NULL);
 159   assert( ! (inc_current>=inc_chain->getNumElements() &&
 160              dec_current>=dec_chain->getNumElements()));
 161   Int inc_nVertices;
 162   Int dec_nVertices;
 163   Real** inc_array ;
 164   Real** dec_array ;
 165   Int i;
 166   assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
 167
 168   if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
 169     {
 170
 171       dec_array = dec_chain->getArray();
 172       dec_nVertices = dec_chain->getNumElements();
 173       reflexChain rChain(20,0);
 174       /*put the top vertex into the reflex chain*/
 175       rChain.processNewVertex(topVertex, backend);
 176       /*process all the vertices on the dec_chain*/
 177       for(i=dec_current; i<dec_nVertices; i++){
 178         rChain.processNewVertex(dec_array[i], backend);
 179       }
 180       /*process the bottom vertex*/
 181       rChain.processNewVertex(botVertex, backend);
 182
 183     }
 184   else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
 185     {
 186       inc_array = inc_chain->getArray();
 187       inc_nVertices= inc_chain->getNumElements();
 188       reflexChain rChain(20,1);
 189       /*put the top vertex into the reflex chain*/
 190       rChain.processNewVertex(topVertex, backend);
 191       /*process all the vertices on the inc_chain*/
 192       for(i=inc_current; i<inc_nVertices; i++){
 193         rChain.processNewVertex(inc_array[i], backend);
 194       }
 195       /*process the bottom vertex*/
 196       rChain.processNewVertex(botVertex, backend);
 197     }
 198   else /*neither chain is empty*/
 199     {
 200       inc_array = inc_chain -> getArray();
 201       dec_array = dec_chain -> getArray();
 202       inc_nVertices= inc_chain->getNumElements();
 203       dec_nVertices= dec_chain->getNumElements();
 204       /*if top of inc_chain is 'lower' than top of dec_chain, process all the
 205        *vertices on the dec_chain which are higher than top of inc_chain
 206        */
 207       if(compV2InY(inc_array[inc_current], dec_array[dec_current]) <= 0)
 208         {
 209
 210           reflexChain rChain(20, 0);
 211           rChain.processNewVertex(topVertex, backend);
 212           for(i=dec_current; i<dec_nVertices; i++)
 213             {
 214               if(compV2InY(inc_array[inc_current], dec_array[i]) <= 0)
 215                 rChain.processNewVertex(dec_array[i], backend);
 216               else
 217                 break;
 218             }
 219           rChain.outputFan(inc_array[inc_current], backend);
 220           monoTriangulationRec(dec_array[i-1], botVertex,
 221                                inc_chain, inc_current,
 222                                dec_chain, i,
 223                                backend);
 224         }
 225       else /*compV2InY(inc_array[inc_current], dec_array[dec_current]) > 0*/
 226         {
 227
 228           reflexChain rChain(20, 1);
 229           rChain.processNewVertex(topVertex, backend);
 230           for(i=inc_current; i<inc_nVertices; i++)
 231             {
 232               if(compV2InY(inc_array[i], dec_array[dec_current]) >0)
 233                 rChain.processNewVertex(inc_array[i], backend);
 234               else
 235                 break;
 236             }
 237           rChain.outputFan(dec_array[dec_current], backend);
 238           monoTriangulationRec(inc_array[i-1], botVertex,
 239                                inc_chain, i,
 240                                dec_chain, dec_current,
 241                                backend);
 242         }
 243     }/*end case neither is empty*/
 244 }
 245
 246
 247 void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend)
 248 {
 249   Int i;
 250   /*find the top vertex, bottom vertex, inccreasing chain, and decreasing chain,
 251    *then call monoTriangulationRec
 252    */
 253   Arc_ptr tempV;
 254   Arc_ptr topV;
 255   Arc_ptr botV;
 256   topV = botV = loop;
 257   for(tempV = loop->next; tempV != loop; tempV = tempV->next)
 258     {
 259       if(compFun(topV->tail(), tempV->tail())<0) {
 260         topV = tempV;
 261       }
 262       if(compFun(botV->tail(), tempV->tail())>0) {
 263         botV = tempV;
 264       }
 265     }
 266
 267   /*creat increase and decrease chains*/
 268   vertexArray inc_chain(20); /*this is a dynamic array*/
 269   for(i=1; i<=topV->pwlArc->npts-2; i++) { /*the first vertex is the top vertex which doesn't belong to inc_chain*/
 270     inc_chain.appendVertex(topV->pwlArc->pts[i].param);
 271   }
 272   for(tempV = topV->next; tempV != botV; tempV = tempV->next)
 273     {
 274       for(i=0; i<=tempV->pwlArc->npts-2; i++){
 275         inc_chain.appendVertex(tempV->pwlArc->pts[i].param);
 276       }
 277     }
 278
 279   vertexArray dec_chain(20);
 280   for(tempV = topV->prev; tempV != botV; tempV = tempV->prev)
 281     {
 282       for(i=tempV->pwlArc->npts-2; i>=0; i--){
 283         dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
 284       }
 285     }
 286   for(i=botV->pwlArc->npts-2; i>=1; i--){
 287     dec_chain.appendVertex(tempV->pwlArc->pts[i].param);
 288   }
 289
 290   monoTriangulationRecFunBackend(topV->tail(), botV->tail(), &inc_chain, 0, &dec_chain, 0, compFun, backend);
 291
 292 }
 293
 294 /*if compFun == compV2InY, top to bottom: V-monotone
 295  *if compFun == compV2InX, right to left: U-monotone
 296  */
 297 void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex,
 298                           vertexArray* inc_chain, Int inc_current,
 299                           vertexArray* dec_chain, Int dec_current,
 300                           Int  (*compFun)(Real*, Real*),
 301                           Backend* backend)
 302 {
 303   assert( inc_chain != NULL && dec_chain != NULL);
 304   assert( ! (inc_current>=inc_chain->getNumElements() &&
 305              dec_current>=dec_chain->getNumElements()));
 306   Int inc_nVertices;
 307   Int dec_nVertices;
 308   Real** inc_array ;
 309   Real** dec_array ;
 310   Int i;
 311   assert( ! ( (inc_chain==NULL) && (dec_chain==NULL)));
 312
 313   if(inc_current>=inc_chain->getNumElements()) /*no more vertices on inc_chain*/
 314     {
 315
 316       dec_array = dec_chain->getArray();
 317       dec_nVertices = dec_chain->getNumElements();
 318       reflexChain rChain(20,0);
 319       /*put the top vertex into the reflex chain*/
 320       rChain.processNewVertex(topVertex, backend);
 321       /*process all the vertices on the dec_chain*/
 322       for(i=dec_current; i<dec_nVertices; i++){
 323         rChain.processNewVertex(dec_array[i], backend);
 324       }
 325       /*process the bottom vertex*/
 326       rChain.processNewVertex(botVertex, backend);
 327
 328     }
 329   else if(dec_current>= dec_chain->getNumElements()) /*no more vertices on dec_chain*/
 330     {
 331       inc_array = inc_chain->getArray();
 332       inc_nVertices= inc_chain->getNumElements();
 333       reflexChain rChain(20,1);
 334       /*put the top vertex into the reflex chain*/
 335       rChain.processNewVertex(topVertex, backend);
 336       /*process all the vertices on the inc_chain*/
 337       for(i=inc_current; i<inc_nVertices; i++){
 338         rChain.processNewVertex(inc_array[i], backend);
 339       }
 340       /*process the bottom vertex*/
 341       rChain.processNewVertex(botVertex, backend);
 342     }
 343   else /*neither chain is empty*/
 344     {
 345       inc_array = inc_chain -> getArray();
 346       dec_array = dec_chain -> getArray();
 347       inc_nVertices= inc_chain->getNumElements();
 348       dec_nVertices= dec_chain->getNumElements();
 349       /*if top of inc_chain is 'lower' than top of dec_chain, process all the
 350        *vertices on the dec_chain which are higher than top of inc_chain
 351        */
 352       if(compFun(inc_array[inc_current], dec_array[dec_current]) <= 0)
 353         {
 354
 355           reflexChain rChain(20, 0);
 356           rChain.processNewVertex(topVertex, backend);
 357           for(i=dec_current; i<dec_nVertices; i++)
 358             {
 359               if(compFun(inc_array[inc_current], dec_array[i]) <= 0)
 360                 rChain.processNewVertex(dec_array[i], backend);
 361               else
 362                 break;
 363             }
 364           rChain.outputFan(inc_array[inc_current], backend);
 365           monoTriangulationRecFunBackend(dec_array[i-1], botVertex,
 366                                inc_chain, inc_current,
 367                                dec_chain, i,
 368                                compFun,
 369                                backend);
 370         }
 371       else /*compFun(inc_array[inc_current], dec_array[dec_current]) > 0*/
 372         {
 373
 374           reflexChain rChain(20, 1);
 375           rChain.processNewVertex(topVertex, backend);
 376           for(i=inc_current; i<inc_nVertices; i++)
 377             {
 378               if(compFun(inc_array[i], dec_array[dec_current]) >0)
 379                 rChain.processNewVertex(inc_array[i], backend);
 380               else
 381                 break;
 382             }
 383           rChain.outputFan(dec_array[dec_current], backend);
 384           monoTriangulationRecFunBackend(inc_array[i-1], botVertex,
 385                                inc_chain, i,
 386                                dec_chain, dec_current,
 387                                compFun,
 388                                backend);
 389         }
 390     }/*end case neither is empty*/
 391 }