Synchronize with trunk's revision r57629.
[reactos.git] / dll / opengl / glu32 / src / libnurbs / nurbtess / monoTriangulation.h
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
41 class Backend;
42
43 class 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
54 public:
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 */
77 class vertexArray{
78 Real** array;
79 Int index;
80 Int size;
81 public:
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
100 void monoTriangulation(directedLine* monoPolygon, primStream* pStream);
101
102 void monoTriangulationRec(Real* topVertex, Real* botVertex,
103 vertexArray* inc_chain, Int inc_current,
104 vertexArray* dec_chain, Int dec_current,
105 primStream* pStream);
106
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);
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 */
119 void monoTriangulation2(Real* topVertex, Real* botVertex,
120 vertexArray* inc_chain, Int inc_smallIndex,
121 Int inc_largeIndex,
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);
128
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);
133
134 void triangulateXYMonoTB(Int n_left, Real** leftVerts,
135 Int n_right, Real** rightVerts,
136 primStream* pStream);
137
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);
142
143 void monoTriangulationRecOpt(Real* topVertex, Real* botVertex,
144 vertexArray* left_chain, Int left_current,
145 vertexArray* right_chain, Int right_current,
146 primStream* pStream);
147
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);
153
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);
161
162
163
164
165 void monoTriangulationRec(Real* topVertex, Real* botVertex,
166 vertexArray* inc_chain, Int inc_current,
167 vertexArray* dec_chain, Int dec_current,
168 Backend* backend);
169
170 void monoTriangulationFunBackend(Arc_ptr loop, Int (*compFun)(Real*, Real*), Backend* backend);
171
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*),
176 Backend* backend);
177
178 void monoTriangulationOpt(directedLine* poly, primStream* pStream);
179
180 #endif
181
182
183
184