aboutsummaryrefslogtreecommitdiff
path: root/mesalib/src/glu/sgi/libnurbs/nurbtess/monoPolyPart.cc
diff options
context:
space:
mode:
Diffstat (limited to 'mesalib/src/glu/sgi/libnurbs/nurbtess/monoPolyPart.cc')
-rw-r--r--mesalib/src/glu/sgi/libnurbs/nurbtess/monoPolyPart.cc299
1 files changed, 0 insertions, 299 deletions
diff --git a/mesalib/src/glu/sgi/libnurbs/nurbtess/monoPolyPart.cc b/mesalib/src/glu/sgi/libnurbs/nurbtess/monoPolyPart.cc
deleted file mode 100644
index 8391205bf..000000000
--- a/mesalib/src/glu/sgi/libnurbs/nurbtess/monoPolyPart.cc
+++ /dev/null
@@ -1,299 +0,0 @@
-/*
-** 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.
-**
-*/
-/*
- *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
-}
-
-
-
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-01 13:40:53 +0000