[NTOS:KE] Fix 'Sert' typo, in a comment (#1929)
[reactos.git] / dll / opengl / glu32 / src / libnurbs / internals / monotonizer.cc
1 /*
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:
9 **
10 ** http://oss.sgi.com/projects/FreeB
11 **
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.
17 **
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.
23 **
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.
33 */
34
35 /*
36 * monotonizer.c++
37 *
38 */
39
40 //#include "glimports.h"
41 //#include "mystdio.h"
42 //#include "myassert.h"
43 #include "arc.h"
44 //#include "arctess.h"
45 #include "bezierarc.h"
46 //#include "bin.h"
47 #include "mapdesc.h"
48 //#include "nurbsconsts.h"
49 #include "subdivider.h"
50
51 /*-----------------------------------------------------------------------------
52 * Subdivider::decompose - break all curves into monotone arcs
53 *-----------------------------------------------------------------------------
54 */
55 int
56 Subdivider::decompose( Bin& bin, REAL geo_stepsize )
57 {
58 Arc_ptr jarc;
59 for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
60 if( ! jarc->isTessellated() ) {
61 /* points have not been transformed, therefore they may be either
62 homogeneous or inhomogeneous */
63 tessellate( jarc, geo_stepsize );
64 if( jarc->isDisconnected() || jarc->next->isDisconnected() )
65 return 1;
66 }
67 }
68
69 for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
70 monotonize( jarc, bin );
71 }
72
73 #ifndef NDEBUG
74 for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
75 assert( isMonotone( jarc ) != 0 );
76 }
77 #endif
78
79 return 0;
80 }
81
82 void
83 Subdivider::tessellate( Arc_ptr jarc, REAL geo_stepsize )
84 {
85 BezierArc *b = jarc->bezierArc;
86 Mapdesc *mapdesc = b->mapdesc;
87
88 if( mapdesc->isRational() ) {
89 REAL max = mapdesc->calcVelocityRational( b->cpts, b->stride, b->order );
90 REAL arc_stepsize = (max > 1.0) ? (1.0/max) : 1.0;
91 if( jarc->bezierArc->order != 2 )
92 arctessellator.tessellateNonlinear( jarc, geo_stepsize, arc_stepsize, 1 );
93 else {
94 arctessellator.tessellateLinear( jarc, geo_stepsize, arc_stepsize, 1 );
95 }
96 } else {
97 REAL max = mapdesc->calcVelocityNonrational( b->cpts, b->stride, b->order );
98 REAL arc_stepsize = (max > 1.0) ? (1.0/max) : 1.0;
99 if( jarc->bezierArc->order != 2 )
100 arctessellator.tessellateNonlinear( jarc, geo_stepsize, arc_stepsize, 0 );
101 else {
102 arctessellator.tessellateLinear( jarc, geo_stepsize, arc_stepsize, 0 );
103 }
104 }
105 }
106
107 /*-------------------------------------------------------------------------
108 * Subdivider::monotonize - break up a jordan arc into s,t-monotone
109 * components. This code will remove degenerate segments, including
110 * arcs of only a single point.
111 *-------------------------------------------------------------------------
112 */
113 void
114 Subdivider::monotonize( Arc_ptr jarc, Bin& bin )
115 {
116 TrimVertex *firstvert = jarc->pwlArc->pts;
117 TrimVertex *lastvert = firstvert + (jarc->pwlArc->npts - 1);
118 long uid = jarc->nuid;
119 arc_side side = jarc->getside();
120 dir sdir = none;
121 dir tdir = none;
122 int degenerate = 1;
123
124 int nudegenerate;
125 int change;
126
127 TrimVertex *vert;
128 for( vert = firstvert; vert != lastvert; vert++ ) {
129
130 nudegenerate = 1;
131 change = 0;
132
133 /* check change relative to s axis, clear degenerate bit if needed */
134 REAL sdiff = vert[1].param[0] - vert[0].param[0];
135 if( sdiff == 0 ) {
136 if( sdir != same ) {
137 sdir = same;
138 change = 1;
139 }
140 } else if( sdiff < 0.0 ) {
141 if( sdir != down ) {
142 sdir = down;
143 change = 1;
144 }
145 nudegenerate = 0;
146 } else {
147 if( sdir != up ) {
148 sdir = up;
149 change = 1;
150 }
151 nudegenerate = 0;
152 }
153
154 /* check change relative to t axis, clear degenerate bit if needed */
155 REAL tdiff = vert[1].param[1] - vert[0].param[1];
156 if( tdiff == 0 ) {
157 if( tdir != same ) {
158 tdir = same;
159 change = 1;
160 }
161 } else if( tdiff < 0.0 ) {
162 if( tdir != down ) {
163 tdir = down;
164 change = 1;
165 }
166 nudegenerate = 0;
167 } else {
168 if( tdir != up ) {
169 tdir = up;
170 change = 1;
171 }
172 nudegenerate = 0;
173 }
174
175 if( change ) {
176 if( ! degenerate ) {
177 /* make last segment into separate pwl curve */
178 jarc->pwlArc->npts = vert - firstvert + 1;
179 jarc = (new(arcpool) Arc( side, uid ))->append( jarc );
180 jarc->pwlArc = new(pwlarcpool) PwlArc();
181 bin.addarc( jarc );
182 }
183 firstvert = jarc->pwlArc->pts = vert;
184 degenerate = nudegenerate;
185 }
186 }
187 jarc->pwlArc->npts = vert - firstvert + 1;
188
189 if( degenerate ) {
190 /* remove jarc from circularly linked list */
191 jarc->prev->next = jarc->next;
192 jarc->next->prev = jarc->prev;
193
194 assert( jarc->prev->check( ) != 0 );
195 assert( jarc->next->check( ) != 0 );
196
197 /* remove jarc from bin */
198 bin.remove_this_arc( jarc );
199
200 jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
201 jarc->deleteMe( arcpool );
202 }
203 }
204
205 /*-------------------------------------------------------------------------
206 * Subdivider::isMonotone - return true if arc is monotone AND non-degenerate
207 *-------------------------------------------------------------------------
208 */
209 int
210 Subdivider::isMonotone( Arc_ptr jarc )
211 {
212 TrimVertex *firstvert = jarc->pwlArc->pts;
213 TrimVertex *lastvert = firstvert + (jarc->pwlArc->npts - 1);
214
215 if( firstvert == lastvert ) return 1;
216
217 TrimVertex *vert = firstvert;
218 enum dir sdir;
219 enum dir tdir;
220
221 REAL diff = vert[1].param[0] - vert[0].param[0];
222 if( diff == 0.0 )
223 sdir = same;
224 else if( diff < 0.0 )
225 sdir = down;
226 else
227 sdir = up;
228
229 diff = vert[1].param[1] - vert[0].param[1];
230 if( diff == 0.0 )
231 tdir = same;
232 else if( diff < 0.0 )
233 tdir = down;
234 else
235 tdir = up;
236
237 if( (sdir == same) && (tdir == same) ) return 0;
238
239 for( ++vert ; vert != lastvert; vert++ ) {
240 diff = vert[1].param[0] - vert[0].param[0];
241 if( diff == 0.0 ) {
242 if( sdir != same ) return 0;
243 } else if( diff < 0.0 ) {
244 if( sdir != down ) return 0;
245 } else {
246 if( sdir != up ) return 0;
247 }
248
249 diff = vert[1].param[1] - vert[0].param[1];
250 if( diff == 0.0 ) {
251 if( tdir != same ) return 0;
252 } else if( diff < 0.0 ) {
253 if( tdir != down ) return 0;
254 } else {
255 if( tdir != up ) return 0;
256 }
257 }
258 return 1;
259 }
260