ReactOS 0.4.16-dev-106-g10b08aa
monotonizer.cc
Go to the documentation of this file.
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 */
55int
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
82void
83Subdivider::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 */
113void
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 */
209int
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
void tessellateNonlinear(Arc_ptr, REAL, REAL, int)
Definition: arctess.cc:324
void tessellateLinear(Arc_ptr, REAL, REAL, int)
Definition: arctess.cc:279
Definition: arc.h:55
Definition: bin.h:44
int isRational(void)
Definition: mapdesc.h:192
REAL calcVelocityNonrational(REAL *, int, int)
Definition: mapdesc.cc:744
REAL calcVelocityRational(REAL *, int, int)
Definition: mapdesc.cc:723
Definition: pwlarc.h:44
int decompose(Bin &, REAL)
Definition: monotonizer.cc:56
ArcTessellator arctessellator
Definition: subdivider.h:113
int isMonotone(Arc_ptr)
Definition: monotonizer.cc:210
Pool pwlarcpool
Definition: subdivider.h:116
Pool arcpool
Definition: subdivider.h:114
void tessellate(Arc_ptr, REAL)
Definition: monotonizer.cc:83
void monotonize(Arc_ptr, Bin &)
Definition: monotonizer.cc:114
REAL param[2]
Definition: trimvertex.h:45
long nuid
Definition: trimvertex.h:50
class Arc * Arc_ptr
Definition: arc.h:50
arc_side
Definition: arc.h:52
float REAL
Definition: types.h:41
#define assert(x)
Definition: debug.h:53
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
static void append(struct dump_context *dc, const void *data, unsigned size)
Definition: minidump.c:397
static struct _PeImage bin
#define max(a, b)
Definition: svc.c:63