1/* 2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) 3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a 6 * copy of this software and associated documentation files (the "Software"), 7 * to deal in the Software without restriction, including without limitation 8 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 9 * and/or sell copies of the Software, and to permit persons to whom the 10 * Software is furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice including the dates of first publication and 13 * either this permission notice or a reference to 14 * http://oss.sgi.com/projects/FreeB/ 15 * shall be included in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 20 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 22 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 23 * SOFTWARE. 24 * 25 * Except as contained in this notice, the name of Silicon Graphics, Inc. 26 * shall not be used in advertising or otherwise to promote the sale, use or 27 * other dealings in this Software without prior written authorization from 28 * Silicon Graphics, Inc. 29 */ 30/* 31*/ 32 33#ifndef _MONO_TRIANGULATION_H 34#define _MONO_TRIANGULATION_H 35 36#include "definitions.h" 37#include "primitiveStream.h" 38#include "directedLine.h" 39#include "arc.h" 40 41class Backend; 42 43class reflexChain{ 44 Real2 *queue; 45 /*the order of the polygon vertices: either q[0],q[1].., or 46 * q[n-1], q[n-2], ..., q[0] 47 *this order determines the interior of the polygon, so it 48 *also used to determines whether a chain is reflex or convex 49 */ 50 Int isIncreasing; 51 Int index_queue; 52 Int size_queue; /*allocated size*/ 53 54public: 55 reflexChain(Int size, Int isIncreasing); 56 ~reflexChain(); 57 58 void insert(Real u, Real v); 59 void insert(Real v[2]); 60 61 void processNewVertex(Real v[2], primStream* pStream); 62 void outputFan(Real v[2], primStream* pStream); 63 64 void processNewVertex(Real v[2], Backend* backend); 65 void outputFan(Real v[2], Backend* backend); 66 67 void print(); 68}; 69 70/*dynamic array of pointers to reals. 71 *Intended to store an array of (u,v). 72 *Notice that it doesn't allocate or dealocate the space 73 *for the (u,v) themselfs. So it assums that someone else 74 *is taking care of them, while this class only plays with 75 *the pointers. 76 */ 77class vertexArray{ 78 Real** array; 79 Int index; 80 Int size; 81public: 82 vertexArray(Int s); 83 vertexArray(Real vertices[][2], Int nVertices); 84 ~vertexArray(); 85 void appendVertex(Real* ptr); /*the content (pointed by ptr is NOT copied*/ 86 Real* getVertex(Int i) {return array[i];} 87 Real** getArray() {return array;} 88 Int getNumElements() {return index;} 89 Int findIndexAbove(Real v); 90 Int findIndexAboveGen(Real v, Int startIndex, Int EndIndex); 91 Int findIndexBelowGen(Real v, Int startIndex, Int EndIndex); 92 Int findIndexStrictBelowGen(Real v, Int startIndex, Int EndIndex); 93 Int findIndexFirstAboveEqualGen(Real v, Int startIndex, Int endIndex); 94 Int skipEqualityFromStart(Real v, Int start, Int end); 95 //return i such that fron [i+1, end] is strictly U-monotone (left to right 96 Int findDecreaseChainFromEnd(Int begin, Int end); 97 void print(); 98}; 99 100void monoTriangulation(directedLine* monoPolygon, primStream* pStream); 101 102void monoTriangulationRec(Real* topVertex, Real* botVertex, 103 vertexArray* inc_chain, Int inc_current, 104 vertexArray* dec_chain, Int dec_current, 105 primStream* pStream); 106 107void monoTriangulationRec(directedLine* inc_chain, Int inc_index, 108 directedLine* dec_chain, Int dec_index, 109 directedLine* topVertex, Int top_index, 110 directedLine* botVertex, 111 primStream* pStream); 112 113/*the chain could be increasing or decreasing, although we use the 114 * name inc_chain. 115 *the argument is_increase_chain indicates whether this chain 116 *is increasing (left chain in V-monotone case) or decreaing (right chain 117 *in V-monotone case). 118 */ 119void monoTriangulation2(Real* topVertex, Real* botVertex, 120 vertexArray* inc_chain, Int inc_smallIndex, 121 Int inc_largeIndex, 122 Int is_increase_chain, 123 primStream* pStream); 124void monoTriangulationRecGen(Real* topVertex, Real* botVertex, 125 vertexArray* inc_chain, Int inc_current, Int inc_end, 126 vertexArray* dec_chain, Int dec_current, Int dec_end, 127 primStream* pStream); 128 129void monoTriangulationRecGenOpt(Real* topVertex, Real* botVertex, 130 vertexArray* inc_chain, Int inc_current, Int inc_end, 131 vertexArray* dec_chain, Int dec_current, Int dec_end, 132 primStream* pStream); 133 134void triangulateXYMonoTB(Int n_left, Real** leftVerts, 135 Int n_right, Real** rightVerts, 136 primStream* pStream); 137 138void monoTriangulationRecGenTBOpt(Real* topVertex, Real* botVertex, 139 vertexArray* inc_chain, Int inc_current, Int inc_end, 140 vertexArray* dec_chain, Int dec_current, Int dec_end, 141 primStream* pStream); 142 143void monoTriangulationRecOpt(Real* topVertex, Real* botVertex, 144 vertexArray* left_chain, Int left_current, 145 vertexArray* right_chain, Int right_current, 146 primStream* pStream); 147 148void monoTriangulationRecFunGen(Real* topVertex, Real* botVertex, 149 vertexArray* inc_chain, Int inc_current, Int inc_end, 150 vertexArray* dec_chain, Int dec_current, Int dec_end, 151 Int (*compFun)(Real*, Real*), 152 primStream* pStream); 153 154void monoTriangulationRecFun(Real* topVertex, Real* botVertex, 155 vertexArray* inc_chain, Int inc_current, 156 vertexArray* dec_chain, Int dec_current, 157 Int (*compFun)(Real*, Real*), 158 primStream* pStream); 159void monoTriangulationFun(directedLine* monoPolygon, 160 Int (*compFun)(Real*, Real*), primStream* pStream); 161 162 163 164 165void monoTriangulationRec(Real* topVertex, Real* botVertex, 166 vertexArray* inc_chain, Int inc_current, 167 vertexArray* dec_chain, Int dec_current, 168 Backend* backend); 169 170void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend); 171 172void monoTriangulationRecFunBackend(Real* topVertex, Real* botVertex, 173 vertexArray* inc_chain, Int inc_current, 174 vertexArray* dec_chain, Int dec_current, 175 Int (*compFun)(Real*, Real*), 176 Backend* backend); 177 178void monoTriangulationOpt(directedLine* poly, primStream* pStream); 179 180#endif 181 182 183 184 185