diff options
author | Reinhard Tartler <siretart@tauware.de> | 2011-10-10 17:43:39 +0200 |
---|---|---|
committer | Reinhard Tartler <siretart@tauware.de> | 2011-10-10 17:43:39 +0200 |
commit | f4092abdf94af6a99aff944d6264bc1284e8bdd4 (patch) | |
tree | 2ac1c9cc16ceb93edb2c4382c088dac5aeafdf0f /nx-X11/extras/ogl-sample/main/gfx/lib/glu/libnurbs/nurbtess/monoPolyPart.cc | |
parent | a840692edc9c6d19cd7c057f68e39c7d95eb767d (diff) | |
download | nx-libs-045ad1ef854b60942711d14c3d17d9fadc21dad4.tar.gz nx-libs-045ad1ef854b60942711d14c3d17d9fadc21dad4.tar.bz2 nx-libs-045ad1ef854b60942711d14c3d17d9fadc21dad4.zip |
Imported nx-X11-3.1.0-1.tar.gznx-X11/3.1.0-1
Summary: Imported nx-X11-3.1.0-1.tar.gz
Keywords:
Imported nx-X11-3.1.0-1.tar.gz
into Git repository
Diffstat (limited to 'nx-X11/extras/ogl-sample/main/gfx/lib/glu/libnurbs/nurbtess/monoPolyPart.cc')
-rw-r--r-- | nx-X11/extras/ogl-sample/main/gfx/lib/glu/libnurbs/nurbtess/monoPolyPart.cc | 300 |
1 files changed, 300 insertions, 0 deletions
diff --git a/nx-X11/extras/ogl-sample/main/gfx/lib/glu/libnurbs/nurbtess/monoPolyPart.cc b/nx-X11/extras/ogl-sample/main/gfx/lib/glu/libnurbs/nurbtess/monoPolyPart.cc new file mode 100644 index 000000000..e8c233fc4 --- /dev/null +++ b/nx-X11/extras/ogl-sample/main/gfx/lib/glu/libnurbs/nurbtess/monoPolyPart.cc @@ -0,0 +1,300 @@ +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** $Date: 2004/03/14 08:29:11 $ $Revision: 1.1.1.4 $ +*/ +/* + *monoPolyPart.C + * + *To partition a v-monotone polygon into some uv-monotone polygons. + *The algorithm is different from the general monotone partition algorithm. + *while the general monotone partition algorithm works for this special case, + *but it is more expensive (O(nlogn)). The algorithm implemented here takes + *advantage of the fact that the input is a v-monotone polygon and it is + *conceptually simpler and computationally cheaper (a linear time algorithm). + *The algorithm is described in Zicheng Liu's paper + * "Quality-Oriented Linear Time Tessellation". + */ + +#include <stdlib.h> +#include <stdio.h> +#include "directedLine.h" +#include "monoPolyPart.h" + +/*a vertex is u_maximal if both of its two neightbors are to the left of this + *vertex + */ +static Int is_u_maximal(directedLine* v) +{ + if (compV2InX(v->getPrev()->head(), v->head()) == -1 && + compV2InX(v->getNext()->head(), v->head()) == -1) + return 1; + else + return 0; +} + +/*a vertex is u_minimal if both of its two neightbors are to the right of this + *vertex + */ +static Int is_u_minimal(directedLine* v) +{ + if (compV2InX(v->getPrev()->head(), v->head()) == 1 && + compV2InX(v->getNext()->head(), v->head()) == 1) + return 1; + else + return 0; +} + +/*poly: a v-monotone polygon + *return: a linked list of uv-monotone polygons. + */ +directedLine* monoPolyPart(directedLine* polygon) +{ + //handle special cases: + if(polygon == NULL) + return NULL; + if(polygon->getPrev() == polygon) + return polygon; + if(polygon->getPrev() == polygon->getNext()) + return polygon; + if(polygon->getPrev()->getPrev() == polygon->getNext()) + return polygon; + + //find the top and bottom vertexes + directedLine *tempV, *topV, *botV; + topV = botV = polygon; + for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext()) + { + if(compV2InY(topV->head(), tempV->head())<0) { + topV = tempV; + } + if(compV2InY(botV->head(), tempV->head())>0) { + botV = tempV; + } + } + + //initilization + directedLine *A, *B, *C, *D, *G, *H; + //find A:the first u_maximal vertex on the left chain + //and C: the left most vertex between top and A + A = NULL; + C = topV; + for(tempV=topV->getNext(); tempV != botV; tempV = tempV->getNext()) + { + if(tempV->head()[0] < C->head()[0]) + C = tempV; + + if(is_u_maximal(tempV)) + { + A = tempV; + break; + } + } + if(A == NULL) + { + A = botV; + if(A->head()[0] < C->head()[0]) + C = A; + } + + //find B: the first u_minimal vertex on the right chain + //and D: the right most vertex between top and B + B = NULL; + D = topV; + for(tempV=topV->getPrev(); tempV != botV; tempV = tempV->getPrev()) + { + if(tempV->head()[0] > D->head()[0]) + D = tempV; + if(is_u_minimal(tempV)) + { + B = tempV; + break; + } + } + if(B == NULL) + { + B = botV; + if(B->head()[0] > D->head()[0]) + D = B; + } + + //error checking XXX + if(C->head()[0] >= D->head()[0]) + return polygon; + + //find G on the left chain that is right above B + for(tempV=topV; compV2InY(tempV->head(), B->head()) == 1; tempV=tempV->getNext()); + G = tempV->getPrev(); + //find H on the right chain that is right above A + for(tempV=topV; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev()); + H = tempV->getNext(); + + //Main Loop + directedLine* ret = NULL; + directedLine* currentPolygon = polygon; + while(1) + { + //if both B and D are equal to botV, then this polygon is already + //u-monotone + if(A == botV && B == botV) + { + ret = currentPolygon->insertPolygon(ret); + return ret; + } + else //not u-monotone + { + directedLine *ret_p1, *ret_p2; + if(compV2InY(A->head(),B->head()) == 1) //A is above B + { + directedLine* E = NULL; + for(tempV = C; tempV != D; tempV = tempV->getPrev()) + { + if(tempV->head()[0] >= A->head()[0]) + { + E = tempV; + break; + } + } + + if(E == NULL) + E = D; + if(E->head()[0]> H->head()[0]) + E = H; + //connect AE and output polygon ECA + polygon->connectDiagonal_2slines(A, E, + &ret_p1, + &ret_p2, + NULL); + ret = ret_p2->insertPolygon(ret); + currentPolygon = ret_p1; + + if(E == D) + D = ret_p1; + if(E == H) + H = ret_p1; + if(G->head()[1] >= A->head()[1]) + G = A; + //update A to be the next u-maxiaml vertex on left chain + //and C the leftmost vertex between the old A and the new A + C = A; + for(tempV = A->getNext(); tempV != botV; tempV = tempV->getNext()) + { + + if(tempV->head()[0] < C->head()[0]) + C = tempV; + if(is_u_maximal(tempV)) + { + A = tempV; + break; + } + } + + if(tempV == botV) + { + A = botV; + if(botV->head()[0] < C->head()[0]) + C = botV; + } + //update H + + if(A == botV) + H = botV; + else + { + for(tempV = H; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev()); + H = tempV->getNext(); + } + + } + else //A is below B + { + + directedLine* F = NULL; + for(tempV = D; tempV != C; tempV = tempV->getNext()) + { + if(tempV->head()[0] <= B->head()[0]) + { + F = tempV; + break; + } + } + if(F == NULL) + F = C; + if(F->head()[0] < G->head()[0]) + F = G; + + //connect FB + polygon->connectDiagonal_2slines(F, B, + &ret_p1, + &ret_p2, + NULL); + ret = ret_p2->insertPolygon(ret); + currentPolygon = ret_p1; + B = ret_p1; + if(H ->head()[1] >= B->head()[1]) + H = ret_p1; + + //update B to be the next u-minimal vertex on right chain + //and D the rightmost vertex between the old B and the new B + D = B; + for(tempV = B->getPrev(); tempV != botV; tempV = tempV->getPrev()) + { + if(tempV->head()[0] > D->head()[0]) + D = tempV; + if(is_u_minimal(tempV)) + { + B = tempV; + break; + } + } + if(tempV == botV) + { + B = botV; + if(botV->head()[0] > D->head()[0]) + D = botV; + } + //update G + if(B == botV) + G = botV; + else + { + for(tempV = G; compV2InY(tempV->head(), B->head()) == 1; tempV = tempV->getNext()); + G = tempV->getPrev(); + } + } //end of A is below B + } //end not u-monotone + } //end of main loop +} + + + |