2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
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:
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.
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
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.
33 #ifndef _MONO_TRIANGULATION_H
34 #define _MONO_TRIANGULATION_H
36 #include "definitions.h"
37 #include "primitiveStream.h"
38 #include "directedLine.h"
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
52 Int size_queue
; /*allocated size*/
55 reflexChain(Int size
, Int isIncreasing
);
58 void insert(Real u
, Real v
);
59 void insert(Real v
[2]);
61 void processNewVertex(Real v
[2], primStream
* pStream
);
62 void outputFan(Real v
[2], primStream
* pStream
);
64 void processNewVertex(Real v
[2], Backend
* backend
);
65 void outputFan(Real v
[2], Backend
* backend
);
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
83 vertexArray(Real vertices
[][2], Int nVertices
);
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
);
100 void monoTriangulation(directedLine
* monoPolygon
, primStream
* pStream
);
102 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
103 vertexArray
* inc_chain
, Int inc_current
,
104 vertexArray
* dec_chain
, Int dec_current
,
105 primStream
* pStream
);
107 void 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
);
113 /*the chain could be increasing or decreasing, although we use the
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).
119 void monoTriangulation2(Real
* topVertex
, Real
* botVertex
,
120 vertexArray
* inc_chain
, Int inc_smallIndex
,
122 Int is_increase_chain
,
123 primStream
* pStream
);
124 void 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
);
129 void 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
);
134 void triangulateXYMonoTB(Int n_left
, Real
** leftVerts
,
135 Int n_right
, Real
** rightVerts
,
136 primStream
* pStream
);
138 void 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
);
143 void monoTriangulationRecOpt(Real
* topVertex
, Real
* botVertex
,
144 vertexArray
* left_chain
, Int left_current
,
145 vertexArray
* right_chain
, Int right_current
,
146 primStream
* pStream
);
148 void 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
);
154 void 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
);
159 void monoTriangulationFun(directedLine
* monoPolygon
,
160 Int (*compFun
)(Real
*, Real
*), primStream
* pStream
);
165 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
166 vertexArray
* inc_chain
, Int inc_current
,
167 vertexArray
* dec_chain
, Int dec_current
,
170 void monoTriangulationFunBackend(Arc_ptr loop
, Int (*compFun
)(Real
*, Real
*), Backend
* backend
);
172 void monoTriangulationRecFunBackend(Real
* topVertex
, Real
* botVertex
,
173 vertexArray
* inc_chain
, Int inc_current
,
174 vertexArray
* dec_chain
, Int dec_current
,
175 Int (*compFun
)(Real
*, Real
*),
178 void monoTriangulationOpt(directedLine
* poly
, primStream
* pStream
);