2 ** License Applicability. Except to the extent portions of this file are
3 ** made subject to an alternative license as permitted in the SGI Free
4 ** Software License B, Version 1.1 (the "License"), the contents of this
5 ** file are subject only to the provisions of the License. You may not use
6 ** this file except in compliance with the License. You may obtain a copy
7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10 ** http://oss.sgi.com/projects/FreeB
12 ** Note that, as provided in the License, the Software is distributed on an
13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
21 ** Copyright in any portions created by third parties is as indicated
22 ** elsewhere herein. All Rights Reserved.
24 ** Additional Notice Provisions: The application programming interfaces
25 ** established by SGI in conjunction with the Original Code are The
26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
31 ** published by SGI, but has not been independently verified as being
32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
38 #ifndef _MONO_TRIANGULATION_H
39 #define _MONO_TRIANGULATION_H
41 #include "definitions.h"
42 #include "primitiveStream.h"
43 #include "directedLine.h"
50 /*the order of the polygon vertices: either q[0],q[1].., or
51 * q[n-1], q[n-2], ..., q[0]
52 *this order determines the interior of the polygon, so it
53 *also used to determines whether a chain is reflex or convex
57 Int size_queue
; /*allocated size*/
60 reflexChain(Int size
, Int isIncreasing
);
63 void insert(Real u
, Real v
);
64 void insert(Real v
[2]);
66 void processNewVertex(Real v
[2], primStream
* pStream
);
67 void outputFan(Real v
[2], primStream
* pStream
);
69 void processNewVertex(Real v
[2], Backend
* backend
);
70 void outputFan(Real v
[2], Backend
* backend
);
75 /*dynamic array of pointers to reals.
76 *Intended to store an array of (u,v).
77 *Notice that it doesn't allocate or dealocate the space
78 *for the (u,v) themselfs. So it assums that someone else
79 *is taking care of them, while this class only plays with
88 vertexArray(Real vertices
[][2], Int nVertices
);
90 void appendVertex(Real
* ptr
); /*the content (pointed by ptr is NOT copied*/
91 Real
* getVertex(Int i
) {return array
[i
];}
92 Real
** getArray() {return array
;}
93 Int
getNumElements() {return index
;}
94 Int
findIndexAbove(Real v
);
95 Int
findIndexAboveGen(Real v
, Int startIndex
, Int EndIndex
);
96 Int
findIndexBelowGen(Real v
, Int startIndex
, Int EndIndex
);
97 Int
findIndexStrictBelowGen(Real v
, Int startIndex
, Int EndIndex
);
98 Int
findIndexFirstAboveEqualGen(Real v
, Int startIndex
, Int endIndex
);
99 Int
skipEqualityFromStart(Real v
, Int start
, Int end
);
100 //return i such that fron [i+1, end] is strictly U-monotone (left to right
101 Int
findDecreaseChainFromEnd(Int begin
, Int end
);
105 void monoTriangulation(directedLine
* monoPolygon
, primStream
* pStream
);
107 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
108 vertexArray
* inc_chain
, Int inc_current
,
109 vertexArray
* dec_chain
, Int dec_current
,
110 primStream
* pStream
);
112 void monoTriangulationRec(directedLine
* inc_chain
, Int inc_index
,
113 directedLine
* dec_chain
, Int dec_index
,
114 directedLine
* topVertex
, Int top_index
,
115 directedLine
* botVertex
,
116 primStream
* pStream
);
118 /*the chain could be increasing or decreasing, although we use the
120 *the argument is_increase_chain indicates whether this chain
121 *is increasing (left chain in V-monotone case) or decreaing (right chain
122 *in V-monotone case).
124 void monoTriangulation2(Real
* topVertex
, Real
* botVertex
,
125 vertexArray
* inc_chain
, Int inc_smallIndex
,
127 Int is_increase_chain
,
128 primStream
* pStream
);
129 void monoTriangulationRecGen(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 monoTriangulationRecGenOpt(Real
* topVertex
, Real
* botVertex
,
135 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
136 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
137 primStream
* pStream
);
139 void triangulateXYMonoTB(Int n_left
, Real
** leftVerts
,
140 Int n_right
, Real
** rightVerts
,
141 primStream
* pStream
);
143 void monoTriangulationRecGenTBOpt(Real
* topVertex
, Real
* botVertex
,
144 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
145 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
146 primStream
* pStream
);
148 void monoTriangulationRecOpt(Real
* topVertex
, Real
* botVertex
,
149 vertexArray
* left_chain
, Int left_current
,
150 vertexArray
* right_chain
, Int right_current
,
151 primStream
* pStream
);
153 void monoTriangulationRecFunGen(Real
* topVertex
, Real
* botVertex
,
154 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
155 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
156 Int (*compFun
)(Real
*, Real
*),
157 primStream
* pStream
);
159 void monoTriangulationRecFun(Real
* topVertex
, Real
* botVertex
,
160 vertexArray
* inc_chain
, Int inc_current
,
161 vertexArray
* dec_chain
, Int dec_current
,
162 Int (*compFun
)(Real
*, Real
*),
163 primStream
* pStream
);
164 void monoTriangulationFun(directedLine
* monoPolygon
,
165 Int (*compFun
)(Real
*, Real
*), primStream
* pStream
);
170 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
171 vertexArray
* inc_chain
, Int inc_current
,
172 vertexArray
* dec_chain
, Int dec_current
,
175 void monoTriangulationFunBackend(Arc_ptr loop
, Int (*compFun
)(Real
*, Real
*), Backend
* backend
);
177 void monoTriangulationRecFunBackend(Real
* topVertex
, Real
* botVertex
,
178 vertexArray
* inc_chain
, Int inc_current
,
179 vertexArray
* dec_chain
, Int dec_current
,
180 Int (*compFun
)(Real
*, Real
*),
183 void monoTriangulationOpt(directedLine
* poly
, primStream
* pStream
);