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.
34 ** $Date: 2001/03/17 00:25:41 $ $Revision: 1.1 $
37 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/nurbtess/monoTriangulation.h,v 1.1 2001/03/17 00:25:41 brianp Exp $
40 #ifndef _MONO_TRIANGULATION_H
41 #define _MONO_TRIANGULATION_H
43 #include "definitions.h"
44 #include "primitiveStream.h"
45 #include "directedLine.h"
53 /*the order of the polygon vertices: either q[0],q[1].., or
54 * q[n-1], q[n-2], ..., q[0]
55 *this order determines the interior of the polygon, so it
56 *also used to determines whether a chain is reflex or convex
60 Int size_queue
; /*allocated size*/
63 reflexChain(Int size
, Int isIncreasing
);
66 void insert(Real u
, Real v
);
67 void insert(Real v
[2]);
69 void processNewVertex(Real v
[2], primStream
* pStream
);
70 void outputFan(Real v
[2], primStream
* pStream
);
72 void processNewVertex(Real v
[2], Backend
* backend
);
73 void outputFan(Real v
[2], Backend
* backend
);
78 /*dynamic array of pointers to reals.
79 *Intended to store an array of (u,v).
80 *Notice that it doesn't allocate or dealocate the space
81 *for the (u,v) themselfs. So it assums that someone else
82 *is taking care of them, while this class only plays with
91 vertexArray(Real vertices
[][2], Int nVertices
);
93 void appendVertex(Real
* ptr
); /*the content (pointed by ptr is NOT copied*/
94 Real
* getVertex(Int i
) {return array
[i
];}
95 Real
** getArray() {return array
;}
96 Int
getNumElements() {return index
;}
97 Int
findIndexAbove(Real v
);
98 Int
findIndexAboveGen(Real v
, Int startIndex
, Int EndIndex
);
99 Int
findIndexBelowGen(Real v
, Int startIndex
, Int EndIndex
);
100 Int
findIndexStrictBelowGen(Real v
, Int startIndex
, Int EndIndex
);
101 Int
findIndexFirstAboveEqualGen(Real v
, Int startIndex
, Int endIndex
);
102 Int
skipEqualityFromStart(Real v
, Int start
, Int end
);
103 //return i such that fron [i+1, end] is strictly U-monotone (left to right
104 Int
findDecreaseChainFromEnd(Int begin
, Int end
);
108 void monoTriangulation(directedLine
* monoPolygon
, primStream
* pStream
);
110 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
111 vertexArray
* inc_chain
, Int inc_current
,
112 vertexArray
* dec_chain
, Int dec_current
,
113 primStream
* pStream
);
115 void monoTriangulationRec(directedLine
* inc_chain
, Int inc_index
,
116 directedLine
* dec_chain
, Int dec_index
,
117 directedLine
* topVertex
, Int top_index
,
118 directedLine
* botVertex
,
119 primStream
* pStream
);
121 /*the chain could be increasing or decreasing, although we use the
123 *the argument is_increase_chain indicates whether this chain
124 *is increasing (left chain in V-monotone case) or decreaing (right chain
125 *in V-monotone case).
127 void monoTriangulation2(Real
* topVertex
, Real
* botVertex
,
128 vertexArray
* inc_chain
, Int inc_smallIndex
,
130 Int is_increase_chain
,
131 primStream
* pStream
);
132 void monoTriangulationRecGen(Real
* topVertex
, Real
* botVertex
,
133 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
134 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
135 primStream
* pStream
);
137 void monoTriangulationRecGenOpt(Real
* topVertex
, Real
* botVertex
,
138 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
139 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
140 primStream
* pStream
);
142 void triangulateXYMonoTB(Int n_left
, Real
** leftVerts
,
143 Int n_right
, Real
** rightVerts
,
144 primStream
* pStream
);
146 void monoTriangulationRecGenTBOpt(Real
* topVertex
, Real
* botVertex
,
147 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
148 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
149 primStream
* pStream
);
151 void monoTriangulationRecOpt(Real
* topVertex
, Real
* botVertex
,
152 vertexArray
* left_chain
, Int left_current
,
153 vertexArray
* right_chain
, Int right_current
,
154 primStream
* pStream
);
156 void monoTriangulationRecFunGen(Real
* topVertex
, Real
* botVertex
,
157 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
158 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
159 Int (*compFun
)(Real
*, Real
*),
160 primStream
* pStream
);
162 void monoTriangulationRecFun(Real
* topVertex
, Real
* botVertex
,
163 vertexArray
* inc_chain
, Int inc_current
,
164 vertexArray
* dec_chain
, Int dec_current
,
165 Int (*compFun
)(Real
*, Real
*),
166 primStream
* pStream
);
167 void monoTriangulationFun(directedLine
* monoPolygon
,
168 Int (*compFun
)(Real
*, Real
*), primStream
* pStream
);
173 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
174 vertexArray
* inc_chain
, Int inc_current
,
175 vertexArray
* dec_chain
, Int dec_current
,
178 void monoTriangulationFunBackend(Arc_ptr loop
, Int (*compFun
)(Real
*, Real
*), Backend
* backend
);
180 void monoTriangulationRecFunBackend(Real
* topVertex
, Real
* botVertex
,
181 vertexArray
* inc_chain
, Int inc_current
,
182 vertexArray
* dec_chain
, Int dec_current
,
183 Int (*compFun
)(Real
*, Real
*),
186 void monoTriangulationOpt(directedLine
* poly
, primStream
* pStream
);