Debian Codegraph @

lib/database/src/so/nodes/nurbs/libnurbs/monotonizer.c++

raw
1 /*
2 *
3 * Copyright (C) 2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * Further, this software is distributed without any warranty that it is
16 * free of the rightful claim of any third person regarding infringement
17 * or the like. Any license provided herein, whether implied or
18 * otherwise, applies only to this software file. Patent licenses, if
19 * any, provided herein do not apply to combinations of this program with
20 * other software, or any other product whatsoever.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
27 * Mountain View, CA 94043, or:
28 *
29 * http://www.sgi.com
30 *
31 * For further information regarding this notice, see:
32 *
33 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/
34 *
35 */
36
37 /*
38 * monotonizer.c++ - $Revision: 1.1.1.1 $
39 * Derrick Burns - 1991
40 */
41
42 #include "glimports.h"
43 #include "mystdio.h"
44 #include "myassert.h"
45 #include "arc.h"
46 #include "arctess.h"
47 #include "bezierarc.h"
48 #include "bin.h"
49 #include "mapdesc.h"
50 #include "nurbsconsts.h"
51 #include "subdivider.h"
52
53 /*-----------------------------------------------------------------------------
54 * Subdivider::decompose - break all curves into monotone arcs
55 *-----------------------------------------------------------------------------
56 */
57 int
58 Subdivider::decompose( Bin& bin, REAL geo_stepsize )
59 {
60 Arc_ptr jarc;
61 for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
62 if( ! jarc->isTessellated() ) {
63 /* points have not been transformed, therefore they may be either
64 homogeneous or inhomogeneous */
65 tessellate( jarc, geo_stepsize );
66 if( jarc->isDisconnected() || jarc->next->isDisconnected() )
67 return 1;
68 }
69 }
70
71 for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
72 monotonize( jarc, bin );
73 }
74
75 #ifndef NDEBUG
76 for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) {
77 assert( isMonotone( jarc ) );
78 }
79 #endif
80
81 return 0;
82 }
83
84 void
85 Subdivider::tessellate( Arc_ptr jarc, REAL geo_stepsize )
86 {
87 BezierArc *b = jarc->bezierArc;
88 Mapdesc *mapdesc = b->mapdesc;
89
90 if( mapdesc->isRational() ) {
91 REAL max = mapdesc->calcVelocityRational( b->cpts, b->stride, b->order );
92 REAL arc_stepsize = (max > 1.0) ? (1.0/max) : 1.0;
93 if( jarc->bezierArc->order != 2 )
94 arctessellator.tessellateNonlinear( jarc, geo_stepsize, arc_stepsize, 1 );
95 else {
96 arctessellator.tessellateLinear( jarc, geo_stepsize, arc_stepsize, 1 );
97 }
98 } else {
99 REAL max = mapdesc->calcVelocityNonrational( b->cpts, b->stride, b->order );
100 REAL arc_stepsize = (max > 1.0) ? (1.0/max) : 1.0;
101 if( jarc->bezierArc->order != 2 )
102 arctessellator.tessellateNonlinear( jarc, geo_stepsize, arc_stepsize, 0 );
103 else {
104 arctessellator.tessellateLinear( jarc, geo_stepsize, arc_stepsize, 0 );
105 }
106 }
107 }
108
109 /*-------------------------------------------------------------------------
110 * Subdivider::monotonize - break up a jordan arc into s,t-monotone
111 * components. This code will remove degenerate segments, including
112 * arcs of only a single point.
113 *-------------------------------------------------------------------------
114 */
115 void
116 Subdivider::monotonize( Arc_ptr jarc, Bin& bin )
117 {
118 TrimVertex *firstvert = jarc->pwlArc->pts;
119 TrimVertex *lastvert = firstvert + (jarc->pwlArc->npts - 1);
120 long uid = jarc->nuid;
121 arc_side side = jarc->getside();
122 dir sdir = none;
123 dir tdir = none;
124 int degenerate = 1;
125
126 int nudegenerate;
127 int change;
128 TrimVertex *vert;
129
130 for( vert = firstvert; vert != lastvert; vert++ ) {
131
132 nudegenerate = 1;
133 change = 0;
134
135 /* check change relative to s axis, clear degenerate bit if needed */
136 REAL sdiff = vert[1].param[0] - vert[0].param[0];
137 if( sdiff == 0 ) {
138 if( sdir != same ) {
139 sdir = same;
140 change = 1;
141 }
142 } else if( sdiff < 0.0 ) {
143 if( sdir != down ) {
144 sdir = down;
145 change = 1;
146 }
147 nudegenerate = 0;
148 } else {
149 if( sdir != up ) {
150 sdir = up;
151 change = 1;
152 }
153 nudegenerate = 0;
154 }
155
156 /* check change relative to t axis, clear degenerate bit if needed */
157 REAL tdiff = vert[1].param[1] - vert[0].param[1];
158 if( tdiff == 0 ) {
159 if( tdir != same ) {
160 tdir = same;
161 change = 1;
162 }
163 } else if( tdiff < 0.0 ) {
164 if( tdir != down ) {
165 tdir = down;
166 change = 1;
167 }
168 nudegenerate = 0;
169 } else {
170 if( tdir != up ) {
171 tdir = up;
172 change = 1;
173 }
174 nudegenerate = 0;
175 }
176
177 if( change ) {
178 if( ! degenerate ) {
179 /* make last segment into separate pwl curve */
180 jarc->pwlArc->npts = vert - firstvert + 1;
181 jarc = (new(arcpool) Arc( side, uid ))->append( jarc );
182 jarc->pwlArc = new(pwlarcpool) PwlArc();
183 bin.addarc( jarc );
184 }
185 firstvert = jarc->pwlArc->pts = vert;
186 degenerate = nudegenerate;
187 }
188 }
189 jarc->pwlArc->npts = vert - firstvert + 1;
190
191 if( degenerate ) {
192 /* remove jarc from circularly linked list */
193 jarc->prev->next = jarc->next;
194 jarc->next->prev = jarc->prev;
195
196 assert( jarc->prev->check( ) );
197 assert( jarc->next->check( ) );
198
199 /* remove jarc from bin */
200 bin.remove_this_arc( jarc );
201
202 jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0;
203 jarc->deleteMe( arcpool );
204 }
205 }
206
207 /*-------------------------------------------------------------------------
208 * Subdivider::isMonotone - return true if arc is monotone AND non-degenerate
209 *-------------------------------------------------------------------------
210 */
211 int
212 Subdivider::isMonotone( Arc_ptr jarc )
213 {
214 TrimVertex *firstvert = jarc->pwlArc->pts;
215 TrimVertex *lastvert = firstvert + (jarc->pwlArc->npts - 1);
216
217 if( firstvert == lastvert ) return 1;
218
219 TrimVertex *vert = firstvert;
220 enum dir sdir;
221 enum dir tdir;
222
223 REAL diff = vert[1].param[0] - vert[0].param[0];
224 if( diff == 0.0 )
225 sdir = same;
226 else if( diff < 0.0 )
227 sdir = down;
228 else
229 sdir = up;
230
231 diff = vert[1].param[1] - vert[0].param[1];
232 if( diff == 0.0 )
233 tdir = same;
234 else if( diff < 0.0 )
235 tdir = down;
236 else
237 tdir = up;
238
239 if( (sdir == same) && (tdir == same) ) return 0;
240
241 for( ++vert ; vert != lastvert; vert++ ) {
242 diff = vert[1].param[0] - vert[0].param[0];
243 if( diff == 0.0 ) {
244 if( sdir != same ) return 0;
245 } else if( diff < 0.0 ) {
246 if( sdir != down ) return 0;
247 } else {
248 if( sdir != up ) return 0;
249 }
250
251 diff = vert[1].param[1] - vert[0].param[1];
252 if( diff == 0.0 ) {
253 if( tdir != same ) return 0;
254 } else if( diff < 0.0 ) {
255 if( tdir != down ) return 0;
256 } else {
257 if( tdir != up ) return 0;
258 }
259 }
260 return 1;
261 }
262