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