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"
52 /*the order of the polygon vertices: either q[0],q[1].., or
53 * q[n-1], q[n-2], ..., q[0]
54 *this order determines the interior of the polygon, so it
55 *also used to determines whether a chain is reflex or convex
59 Int size_queue
; /*allocated size*/
62 reflexChain(Int size
, Int isIncreasing
);
65 void insert(Real u
, Real v
);
66 void insert(Real v
[2]);
68 void processNewVertex(Real v
[2], primStream
* pStream
);
69 void outputFan(Real v
[2], primStream
* pStream
);
71 void processNewVertex(Real v
[2], Backend
* backend
);
72 void outputFan(Real v
[2], Backend
* backend
);
77 /*dynamic array of pointers to reals.
78 *Intended to store an array of (u,v).
79 *Notice that it doesn't allocate or dealocate the space
80 *for the (u,v) themselfs. So it assums that someone else
81 *is taking care of them, while this class only plays with
90 vertexArray(Real vertices
[][2], Int nVertices
);
92 void appendVertex(Real
* ptr
); /*the content (pointed by ptr is NOT copied*/
93 Real
* getVertex(Int i
) {return array
[i
];}
94 Real
** getArray() {return array
;}
95 Int
getNumElements() {return index
;}
96 Int
findIndexAbove(Real v
);
97 Int
findIndexAboveGen(Real v
, Int startIndex
, Int EndIndex
);
98 Int
findIndexBelowGen(Real v
, Int startIndex
, Int EndIndex
);
99 Int
findIndexStrictBelowGen(Real v
, Int startIndex
, Int EndIndex
);
100 Int
findIndexFirstAboveEqualGen(Real v
, Int startIndex
, Int endIndex
);
101 Int
skipEqualityFromStart(Real v
, Int start
, Int end
);
102 //return i such that fron [i+1, end] is strictly U-monotone (left to right
103 Int
findDecreaseChainFromEnd(Int begin
, Int end
);
107 void monoTriangulation(directedLine
* monoPolygon
, primStream
* pStream
);
109 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
110 vertexArray
* inc_chain
, Int inc_current
,
111 vertexArray
* dec_chain
, Int dec_current
,
112 primStream
* pStream
);
114 void monoTriangulationRec(directedLine
* inc_chain
, Int inc_index
,
115 directedLine
* dec_chain
, Int dec_index
,
116 directedLine
* topVertex
, Int top_index
,
117 directedLine
* botVertex
,
118 primStream
* pStream
);
120 /*the chain could be increasing or decreasing, although we use the
122 *the argument is_increase_chain indicates whether this chain
123 *is increasing (left chain in V-monotone case) or decreaing (right chain
124 *in V-monotone case).
126 void monoTriangulation2(Real
* topVertex
, Real
* botVertex
,
127 vertexArray
* inc_chain
, Int inc_smallIndex
,
129 Int is_increase_chain
,
130 primStream
* pStream
);
131 void monoTriangulationRecGen(Real
* topVertex
, Real
* botVertex
,
132 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
133 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
134 primStream
* pStream
);
136 void monoTriangulationRecGenOpt(Real
* topVertex
, Real
* botVertex
,
137 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
138 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
139 primStream
* pStream
);
141 void triangulateXYMonoTB(Int n_left
, Real
** leftVerts
,
142 Int n_right
, Real
** rightVerts
,
143 primStream
* pStream
);
145 void monoTriangulationRecGenTBOpt(Real
* topVertex
, Real
* botVertex
,
146 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
147 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
148 primStream
* pStream
);
150 void monoTriangulationRecOpt(Real
* topVertex
, Real
* botVertex
,
151 vertexArray
* left_chain
, Int left_current
,
152 vertexArray
* right_chain
, Int right_current
,
153 primStream
* pStream
);
155 void monoTriangulationRecFunGen(Real
* topVertex
, Real
* botVertex
,
156 vertexArray
* inc_chain
, Int inc_current
, Int inc_end
,
157 vertexArray
* dec_chain
, Int dec_current
, Int dec_end
,
158 Int (*compFun
)(Real
*, Real
*),
159 primStream
* pStream
);
161 void monoTriangulationRecFun(Real
* topVertex
, Real
* botVertex
,
162 vertexArray
* inc_chain
, Int inc_current
,
163 vertexArray
* dec_chain
, Int dec_current
,
164 Int (*compFun
)(Real
*, Real
*),
165 primStream
* pStream
);
166 void monoTriangulationFun(directedLine
* monoPolygon
,
167 Int (*compFun
)(Real
*, Real
*), primStream
* pStream
);
172 void monoTriangulationRec(Real
* topVertex
, Real
* botVertex
,
173 vertexArray
* inc_chain
, Int inc_current
,
174 vertexArray
* dec_chain
, Int dec_current
,
177 void monoTriangulationFunBackend(Arc_ptr loop
, Int (*compFun
)(Real
*, Real
*), Backend
* backend
);
179 void monoTriangulationRecFunBackend(Real
* topVertex
, Real
* botVertex
,
180 vertexArray
* inc_chain
, Int inc_current
,
181 vertexArray
* dec_chain
, Int dec_current
,
182 Int (*compFun
)(Real
*, Real
*),
185 void monoTriangulationOpt(directedLine
* poly
, primStream
* pStream
);