reactos/dll/win32/glu32/libnurbs/nurbtess/monoPolyPart.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  *monoPolyPart.C
  38  *
  39  *To partition a v-monotone polygon into some uv-monotone polygons.
  40  *The algorithm is different from the general monotone partition algorithm.
  41  *while the general monotone partition algorithm works for this special case,
  42  *but it is more expensive (O(nlogn)). The algorithm implemented here takes
  43  *advantage of the fact that the input is a v-monotone polygon and it is
  44  *conceptually simpler and  computationally cheaper (a linear time algorithm).
  45  *The algorithm is described in Zicheng Liu's  paper
  46  * "Quality-Oriented Linear Time Tessellation".
  47  */
  48
  49 #include <stdlib.h>
  50 #include <stdio.h>
  51 #include "directedLine.h"
  52 #include "monoPolyPart.h"
  53
  54 /*a vertex is u_maximal if both of its two neightbors are to the left of this
  55  *vertex
  56  */
  57 static Int is_u_maximal(directedLine* v)
  58 {
  59   if (compV2InX(v->getPrev()->head(), v->head()) == -1 &&
  60       compV2InX(v->getNext()->head(), v->head()) == -1)
  61     return 1;
  62   else
  63     return 0;
  64 }
  65
  66 /*a vertex is u_minimal if both of its two neightbors are to the right of this
  67  *vertex
  68  */
  69 static Int is_u_minimal(directedLine* v)
  70 {
  71   if (compV2InX(v->getPrev()->head(), v->head()) == 1 &&
  72       compV2InX(v->getNext()->head(), v->head()) == 1)
  73     return 1;
  74   else
  75     return 0;
  76 }
  77
  78 /*poly: a v-monotone polygon
  79  *return: a linked list of uv-monotone polygons.
  80  */
  81 directedLine* monoPolyPart(directedLine* polygon)
  82 {
  83   //handle special cases:
  84   if(polygon == NULL)
  85     return NULL;
  86   if(polygon->getPrev() == polygon)
  87     return polygon;
  88   if(polygon->getPrev() == polygon->getNext())
  89     return polygon;
  90   if(polygon->getPrev()->getPrev() == polygon->getNext())
  91     return polygon;
  92
  93   //find the top and bottom vertexes
  94   directedLine *tempV, *topV, *botV;
  95   topV = botV = polygon;
  96   for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
  97     {
  98       if(compV2InY(topV->head(), tempV->head())<0) {
  99         topV = tempV;
 100       }
 101       if(compV2InY(botV->head(), tempV->head())>0) {
 102         botV = tempV;
 103       }
 104     }
 105
 106   //initilization
 107   directedLine *A, *B, *C, *D, *G, *H;
 108   //find A:the first u_maximal vertex on the left chain
 109   //and C: the left most vertex between top and A
 110   A = NULL;
 111   C = topV;
 112   for(tempV=topV->getNext(); tempV != botV; tempV = tempV->getNext())
 113     {
 114       if(tempV->head()[0] < C->head()[0])
 115         C = tempV;
 116
 117       if(is_u_maximal(tempV))
 118         {
 119           A = tempV;
 120           break;
 121         }
 122     }
 123   if(A == NULL)
 124     {
 125       A = botV;
 126       if(A->head()[0] < C->head()[0])
 127         C = A;
 128     }
 129
 130   //find B: the first u_minimal vertex on the right chain
 131   //and  D: the right most vertex between top and B
 132   B = NULL;
 133   D = topV;
 134   for(tempV=topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
 135     {
 136       if(tempV->head()[0] > D->head()[0])
 137         D = tempV;
 138       if(is_u_minimal(tempV))
 139         {
 140           B = tempV;
 141           break;
 142         }
 143     }
 144   if(B == NULL)
 145     {
 146       B = botV;
 147       if(B->head()[0] > D->head()[0])
 148         D = B;
 149     }
 150
 151   //error checking XXX
 152   if(C->head()[0] >= D->head()[0])
 153     return polygon;
 154
 155   //find G on the left chain that is right above B
 156   for(tempV=topV; compV2InY(tempV->head(), B->head()) == 1;  tempV=tempV->getNext());
 157   G = tempV->getPrev();
 158   //find H on the right chain that is right above A
 159   for(tempV=topV; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev());
 160   H = tempV->getNext();
 161
 162   //Main Loop
 163   directedLine* ret = NULL;
 164   directedLine* currentPolygon = polygon;
 165   while(1)
 166     {
 167       //if both B and D are equal to botV, then this polygon is already
 168       //u-monotone
 169       if(A == botV && B == botV)
 170         {
 171           ret = currentPolygon->insertPolygon(ret);
 172           return ret;
 173         }
 174       else //not u-monotone
 175         {
 176           directedLine *ret_p1, *ret_p2;
 177           if(compV2InY(A->head(),B->head()) == 1) //A is above B
 178             {
 179               directedLine* E = NULL;
 180               for(tempV = C; tempV != D; tempV = tempV->getPrev())
 181                 {
 182                   if(tempV->head()[0] >= A->head()[0])
 183                     {
 184                       E = tempV;
 185                       break;
 186                     }
 187                 }
 188
 189               if(E == NULL)
 190                 E = D;
 191               if(E->head()[0]> H->head()[0])
 192                 E = H;
 193               //connect AE and output polygon ECA
 194               polygon->connectDiagonal_2slines(A, E,
 195                                                &ret_p1,
 196                                                &ret_p2,
 197                                                NULL);
 198               ret = ret_p2->insertPolygon(ret);
 199               currentPolygon = ret_p1;
 200
 201               if(E == D)
 202                 D = ret_p1;
 203               if(E == H)
 204                 H = ret_p1;
 205               if(G->head()[1] >= A->head()[1])
 206                 G = A;
 207               //update A to be the next u-maxiaml vertex on left chain
 208               //and C the leftmost vertex between the old A and the new A
 209               C = A;
 210               for(tempV = A->getNext(); tempV != botV; tempV = tempV->getNext())
 211                 {
 212
 213                   if(tempV->head()[0] < C->head()[0])
 214                     C = tempV;
 215                   if(is_u_maximal(tempV))
 216                     {
 217                       A = tempV;
 218                       break;
 219                     }
 220                 }
 221
 222               if(tempV == botV)
 223                 {
 224                   A = botV;
 225                   if(botV->head()[0] < C->head()[0])
 226                     C = botV;
 227                 }
 228               //update H
 229
 230               if(A == botV)
 231                 H = botV;
 232               else
 233                 {
 234                   for(tempV = H; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev());
 235                   H = tempV->getNext();
 236                 }
 237
 238             }
 239           else //A is below B
 240             {
 241
 242               directedLine* F = NULL;
 243               for(tempV = D; tempV != C; tempV = tempV->getNext())
 244                 {
 245                   if(tempV->head()[0] <= B->head()[0])
 246                     {
 247                       F = tempV;
 248                       break;
 249                     }
 250                 }
 251               if(F == NULL)
 252                 F = C;
 253               if(F->head()[0] < G->head()[0])
 254                 F = G;
 255
 256               //connect FB
 257               polygon->connectDiagonal_2slines(F, B,
 258                                                &ret_p1,
 259                                                &ret_p2,
 260                                                NULL);
 261               ret = ret_p2->insertPolygon(ret);
 262               currentPolygon = ret_p1;
 263               B = ret_p1;
 264               if(H ->head()[1] >= B->head()[1])
 265                 H = ret_p1;
 266
 267               //update B to be the next u-minimal vertex on right chain
 268               //and D the rightmost vertex between the old B and the new B
 269               D = B;
 270               for(tempV = B->getPrev(); tempV != botV; tempV = tempV->getPrev())
 271                 {
 272                   if(tempV->head()[0] > D->head()[0])
 273                     D = tempV;
 274                   if(is_u_minimal(tempV))
 275                     {
 276                       B = tempV;
 277                       break;
 278                     }
 279                 }
 280               if(tempV == botV)
 281                 {
 282                   B = botV;
 283                   if(botV->head()[0] > D->head()[0])
 284                     D = botV;
 285                 }
 286               //update G
 287               if(B == botV)
 288                 G = botV;
 289               else
 290                 {
 291                   for(tempV = G; compV2InY(tempV->head(), B->head()) == 1;  tempV = tempV->getNext());
 292                   G = tempV->getPrev();
 293                 }
 294             } //end of A is below B
 295         } //end not u-monotone
 296     } //end of main loop
 297 }
 298
 299
 300