| /* |
| * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) |
| * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice including the dates of first publication and |
| * either this permission notice or a reference to |
| * http://oss.sgi.com/projects/FreeB/ |
| * shall be included in all copies or substantial portions of the Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS |
| * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
| * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF |
| * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
| * SOFTWARE. |
| * |
| * Except as contained in this notice, the name of Silicon Graphics, Inc. |
| * shall not be used in advertising or otherwise to promote the sale, use or |
| * other dealings in this Software without prior written authorization from |
| * Silicon Graphics, Inc. |
| */ |
| /* |
| ** $Header: /cvs/bao-parsec/pkgs/libs/mesa/src/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.h,v 1.1.1.1 2012/03/29 17:22:17 uid42307 Exp $ |
| */ |
| |
| #ifndef _MONO_TRIANGULATION_H |
| #define _MONO_TRIANGULATION_H |
| |
| #include "definitions.h" |
| #include "primitiveStream.h" |
| #include "directedLine.h" |
| #include "arc.h" |
| |
| class Backend; |
| |
| class reflexChain{ |
| Real2 *queue; |
| /*the order of the polygon vertices: either q[0],q[1].., or |
| * q[n-1], q[n-2], ..., q[0] |
| *this order determines the interior of the polygon, so it |
| *also used to determines whether a chain is reflex or convex |
| */ |
| Int isIncreasing; |
| Int index_queue; |
| Int size_queue; /*allocated size*/ |
| |
| public: |
| reflexChain(Int size, Int isIncreasing); |
| ~reflexChain(); |
| |
| void insert(Real u, Real v); |
| void insert(Real v[2]); |
| |
| void processNewVertex(Real v[2], primStream* pStream); |
| void outputFan(Real v[2], primStream* pStream); |
| |
| void processNewVertex(Real v[2], Backend* backend); |
| void outputFan(Real v[2], Backend* backend); |
| |
| void print(); |
| }; |
| |
| /*dynamic array of pointers to reals. |
| *Intended to store an array of (u,v). |
| *Notice that it doesn't allocate or dealocate the space |
| *for the (u,v) themselfs. So it assums that someone else |
| *is taking care of them, while this class only plays with |
| *the pointers. |
| */ |
| class vertexArray{ |
| Real** array; |
| Int index; |
| Int size; |
| public: |
| vertexArray(Int s); |
| vertexArray(Real vertices[][2], Int nVertices); |
| ~vertexArray(); |
| void appendVertex(Real* ptr); /*the content (pointed by ptr is NOT copied*/ |
| Real* getVertex(Int i) {return array[i];} |
| Real** getArray() {return array;} |
| Int getNumElements() {return index;} |
| Int findIndexAbove(Real v); |
| Int findIndexAboveGen(Real v, Int startIndex, Int EndIndex); |
| Int findIndexBelowGen(Real v, Int startIndex, Int EndIndex); |
| Int findIndexStrictBelowGen(Real v, Int startIndex, Int EndIndex); |
| Int findIndexFirstAboveEqualGen(Real v, Int startIndex, Int endIndex); |
| Int skipEqualityFromStart(Real v, Int start, Int end); |
| //return i such that fron [i+1, end] is strictly U-monotone (left to right |
| Int findDecreaseChainFromEnd(Int begin, Int end); |
| void print(); |
| }; |
| |
| void monoTriangulation(directedLine* monoPolygon, primStream* pStream); |
| |
| void monoTriangulationRec(Real* topVertex, Real* botVertex, |
| vertexArray* inc_chain, Int inc_current, |
| vertexArray* dec_chain, Int dec_current, |
| primStream* pStream); |
| |
| void monoTriangulationRec(directedLine* inc_chain, Int inc_index, |
| directedLine* dec_chain, Int dec_index, |
| directedLine* topVertex, Int top_index, |
| directedLine* botVertex, |
| primStream* pStream); |
| |
| /*the chain could be increasing or decreasing, although we use the |
| * name inc_chain. |
| *the argument is_increase_chain indicates whether this chain |
| *is increasing (left chain in V-monotone case) or decreaing (right chain |
| *in V-monotone case). |
| */ |
| void monoTriangulation2(Real* topVertex, Real* botVertex, |
| vertexArray* inc_chain, Int inc_smallIndex, |
| Int inc_largeIndex, |
| Int is_increase_chain, |
| primStream* pStream); |
| void monoTriangulationRecGen(Real* topVertex, Real* botVertex, |
| vertexArray* inc_chain, Int inc_current, Int inc_end, |
| vertexArray* dec_chain, Int dec_current, Int dec_end, |
| primStream* pStream); |
| |
| void monoTriangulationRecGenOpt(Real* topVertex, Real* botVertex, |
| vertexArray* inc_chain, Int inc_current, Int inc_end, |
| vertexArray* dec_chain, Int dec_current, Int dec_end, |
| primStream* pStream); |
| |
| void triangulateXYMonoTB(Int n_left, Real** leftVerts, |
| Int n_right, Real** rightVerts, |
| primStream* pStream); |
| |
| void monoTriangulationRecGenTBOpt(Real* topVertex, Real* botVertex, |
| vertexArray* inc_chain, Int inc_current, Int inc_end, |
| vertexArray* dec_chain, Int dec_current, Int dec_end, |
| primStream* pStream); |
| |
| void monoTriangulationRecOpt(Real* topVertex, Real* botVertex, |
| vertexArray* left_chain, Int left_current, |
| vertexArray* right_chain, Int right_current, |
| primStream* pStream); |
| |
| void monoTriangulationRecFunGen(Real* topVertex, Real* botVertex, |
| vertexArray* inc_chain, Int inc_current, Int inc_end, |
| vertexArray* dec_chain, Int dec_current, Int dec_end, |
| Int (*compFun)(Real*, Real*), |
| primStream* pStream); |
| |
| void monoTriangulationRecFun(Real* topVertex, Real* botVertex, |
| vertexArray* inc_chain, Int inc_current, |
| vertexArray* dec_chain, Int dec_current, |
| Int (*compFun)(Real*, Real*), |
| primStream* pStream); |
| void monoTriangulationFun(directedLine* monoPolygon, |
| Int (*compFun)(Real*, Real*), primStream* pStream); |
| |
| |
| |
| |
| void monoTriangulationRec(Real* topVertex, Real* botVertex, |
| vertexArray* inc_chain, Int inc_current, |
| vertexArray* dec_chain, Int dec_current, |
| Backend* backend); |
| |
| void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend); |
| |
| void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex, |
| vertexArray* inc_chain, Int inc_current, |
| vertexArray* dec_chain, Int dec_current, |
| Int (*compFun)(Real*, Real*), |
| Backend* backend); |
| |
| void monoTriangulationOpt(directedLine* poly, primStream* pStream); |
| |
| #endif |
| |
| |
| |
| |