Debian Codegraph @

lib/database/src/so/nodes/nurbs/libnurbs/arctess.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 * arctessellator.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 "arctess.h"
46 #include "bufpool.h"
47 #include "simplemath.h"
48 #include "bezierarc.h"
49 #include "trimvertex.h"
50 #include "trimvertpool.h"
51
52 #define NOELIMINATION
53
54 #define steps_function(large, small, rate) (max(1, 1+ (int) ((large-small)/rate)));
55
56 /*-----------------------------------------------------------------------------
57 * ArcTessellator - construct an ArcTessellator
58 *-----------------------------------------------------------------------------
59 */
60
61 ArcTessellator::ArcTessellator( TrimVertexPool& t, Pool& p )
62 : trimvertexpool(t), pwlarcpool(p)
63 {
64 }
65
66 /*-----------------------------------------------------------------------------
67 * ~ArcTessellator - destroy an ArcTessellator
68 *-----------------------------------------------------------------------------
69 */
70
71 ArcTessellator::~ArcTessellator( void )
72 {
73 }
74
75 /*-----------------------------------------------------------------------------
76 * bezier - construct a bezier arc and attach it to an Arc
77 *-----------------------------------------------------------------------------
78 */
79
80 void
81 ArcTessellator::bezier( Arc *arc, REAL s1, REAL s2, REAL t1, REAL t2 )
82 {
83 assert( arc != 0 );
84 assert( ! arc->isTessellated() );
85
86 #ifndef NDEBUG
87 switch( arc->getside() ) {
88 case arc_left:
89 assert( s1 == s2 );
90 assert( t2 < t1 );
91 break;
92 case arc_right:
93 assert( s1 == s2 );
94 assert( t1 < t2 );
95 break;
96 case arc_top:
97 assert( t1 == t2 );
98 assert( s2 < s1 );
99 break;
100 case arc_bottom:
101 assert( t1 == t2 );
102 assert( s1 < s2 );
103 break;
104 case arc_none:
105 (void) abort();
106 break;
107 }
108 #endif
109
110 TrimVertex *p = trimvertexpool.get(2);
111 arc->pwlArc = new(pwlarcpool) PwlArc( 2, p );
112 p[0].param[0] = s1;
113 p[0].param[1] = t1;
114 p[1].param[0] = s2;
115 p[1].param[1] = t2;
116 assert( (s1 == s2) || (t1 == t2) );
117 arc->setbezier();
118 }
119
120
121 /*-----------------------------------------------------------------------------
122 * pwl_left - construct a left boundary pwl arc and attach it to an arc
123 *-----------------------------------------------------------------------------
124 */
125
126 void
127 ArcTessellator::pwl_left( Arc *arc, REAL s, REAL t1, REAL t2, REAL rate )
128 {
129 assert( t2 < t1 );
130
131 /* if(rate <= 0.06) rate = 0.06;*/
132 /* int nsteps = 1 + (int) ((t1 - t2) / rate ); */
133 int nsteps = steps_function(t1, t2, rate);
134
135
136 REAL stepsize = (t1 - t2) / (REAL) nsteps;
137
138 int i;
139 TrimVertex *newvert = trimvertexpool.get( nsteps+1 );
140 for( i = nsteps; i > 0; i-- ) {
141 newvert[i].param[0] = s;
142 newvert[i].param[1] = t2;
143 t2 += stepsize;
144 }
145 newvert[i].param[0] = s;
146 newvert[i].param[1] = t1;
147
148 arc->makeSide( new(pwlarcpool) PwlArc( nsteps+1, newvert ), arc_left );
149 }
150
151 /*-----------------------------------------------------------------------------
152 * pwl_right - construct a right boundary pwl arc and attach it to an arc
153 *-----------------------------------------------------------------------------
154 */
155
156 void
157 ArcTessellator::pwl_right( Arc *arc, REAL s, REAL t1, REAL t2, REAL rate )
158 {
159 assert( t1 < t2 );
160
161 /* if(rate <= 0.06) rate = 0.06;*/
162
163 int i;
164 /* int nsteps = 1 + (int) ((t2 - t1) / rate ); */
165 int nsteps = steps_function(t2,t1,rate);
166 REAL stepsize = (t2 - t1) / (REAL) nsteps;
167
168 TrimVertex *newvert = trimvertexpool.get( nsteps+1 );
169 for( i = 0; i < nsteps; i++ ) {
170 newvert[i].param[0] = s;
171 newvert[i].param[1] = t1;
172 t1 += stepsize;
173 }
174 newvert[i].param[0] = s;
175 newvert[i].param[1] = t2;
176
177 arc->makeSide( new(pwlarcpool) PwlArc( nsteps+1, newvert ), arc_right );
178 }
179
180
181 /*-----------------------------------------------------------------------------
182 * pwl_top - construct a top boundary pwl arc and attach it to an arc
183 *-----------------------------------------------------------------------------
184 */
185
186 void
187 ArcTessellator::pwl_top( Arc *arc, REAL t, REAL s1, REAL s2, REAL rate )
188 {
189 assert( s2 < s1 );
190
191 /* if(rate <= 0.06) rate = 0.06;*/
192
193 int i;
194 /* int nsteps = 1 + (int) ((s1 - s2) / rate ); */
195 int nsteps = steps_function(s1,s2,rate);
196 REAL stepsize = (s1 - s2) / (REAL) nsteps;
197
198 TrimVertex *newvert = trimvertexpool.get( nsteps+1 );
199 for( i = nsteps; i > 0; i-- ) {
200 newvert[i].param[0] = s2;
201 newvert[i].param[1] = t;
202 s2 += stepsize;
203 }
204 newvert[i].param[0] = s1;
205 newvert[i].param[1] = t;
206
207 arc->makeSide( new(pwlarcpool) PwlArc( nsteps+1, newvert ), arc_top );
208 }
209
210 /*-----------------------------------------------------------------------------
211 * pwl_bottom - construct a bottom boundary pwl arc and attach it to an arc
212 *-----------------------------------------------------------------------------
213 */
214
215 void
216 ArcTessellator::pwl_bottom( Arc *arc, REAL t, REAL s1, REAL s2, REAL rate )
217 {
218 assert( s1 < s2 );
219
220 /* if(rate <= 0.06) rate = 0.06;*/
221
222 int i;
223 /* int nsteps = 1 + (int) ((s2 - s1) / rate ); */
224 int nsteps = steps_function(s2,s1,rate);
225 REAL stepsize = (s2 - s1) / (REAL) nsteps;
226
227 TrimVertex *newvert = trimvertexpool.get( nsteps+1 );
228 for( i = 0; i < nsteps; i++ ) {
229 newvert[i].param[0] = s1;
230 newvert[i].param[1] = t;
231 s1 += stepsize;
232 }
233 newvert[i].param[0] = s2;
234 newvert[i].param[1] = t;
235
236 arc->makeSide( new(pwlarcpool) PwlArc( nsteps+1, newvert ), arc_bottom );
237 }
238
239 /*-----------------------------------------------------------------------------
240 * pwl - construct a pwl arc and attach it to an arc
241 *-----------------------------------------------------------------------------
242 */
243
244 void
245 ArcTessellator::pwl( Arc *arc, REAL s1, REAL s2, REAL t1, REAL t2, REAL rate )
246 {
247
248 /* if(rate <= 0.06) rate = 0.06;*/
249
250 int snsteps = 1 + (int) (abs(s2 - s1) / rate );
251 int tnsteps = 1 + (int) (abs(t2 - t1) / rate );
252 int nsteps = max(1,max( snsteps, tnsteps ));
253
254 REAL sstepsize = (s2 - s1) / (REAL) nsteps;
255 REAL tstepsize = (t2 - t1) / (REAL) nsteps;
256 TrimVertex *newvert = trimvertexpool.get( nsteps+1 );
257 long i;
258 for( i = 0; i < nsteps; i++ ) {
259 newvert[i].param[0] = s1;
260 newvert[i].param[1] = t1;
261 s1 += sstepsize;
262 t1 += tstepsize;
263 }
264 newvert[i].param[0] = s2;
265 newvert[i].param[1] = t2;
266
267 /* arc->makeSide( new(pwlarcpool) PwlArc( nsteps+1, newvert ), arc_bottom ); */
268 arc->pwlArc = new(pwlarcpool) PwlArc( nsteps+1, newvert );
269
270 arc->clearbezier();
271 arc->clearside( );
272 }
273
274
275 /*-----------------------------------------------------------------------------
276 * tessellateLinear - constuct a linear pwl arc and attach it to an Arc
277 *-----------------------------------------------------------------------------
278 */
279
280 void
281 ArcTessellator::tessellateLinear( Arc *arc, REAL geo_stepsize, REAL arc_stepsize, int isrational )
282 {
283 assert( arc->pwlArc == NULL );
284 REAL s1, s2, t1, t2;
285
286 //we don't need to scale by arc_stepsize if the trim curve
287 //is piecewise linear. Reason: In pwl_right, pwl_left, pwl_top, pwl_left,
288 //and pwl, the nsteps is computed by deltaU (or V) /stepsize.
289 //The quantity deltaU/arc_stepsize doesn't have any meaning. And
290 //it causes problems: see bug 517641
291 REAL stepsize = geo_stepsize; /* * arc_stepsize*/;
292
293 BezierArc *b = arc->bezierArc;
294
295 if( isrational ) {
296 s1 = b->cpts[0] / b->cpts[2];
297 t1 = b->cpts[1] / b->cpts[2];
298 s2 = b->cpts[b->stride+0] / b->cpts[b->stride+2];
299 t2 = b->cpts[b->stride+1] / b->cpts[b->stride+2];
300 } else {
301 s1 = b->cpts[0];
302 t1 = b->cpts[1];
303 s2 = b->cpts[b->stride+0];
304 t2 = b->cpts[b->stride+1];
305 }
306 if( s1 == s2 )
307 if( t1 < t2 )
308 pwl_right( arc, s1, t1, t2, stepsize );
309 else
310 pwl_left( arc, s1, t1, t2, stepsize );
311 else if( t1 == t2 )
312 if( s1 < s2 )
313 pwl_bottom( arc, t1, s1, s2, stepsize );
314 else
315 pwl_top( arc, t1, s1, s2, stepsize );
316 else
317 pwl( arc, s1, s2, t1, t2, stepsize );
318 }
319
320 /*-----------------------------------------------------------------------------
321 * tessellateNonlinear - constuct a nonlinear pwl arc and attach it to an Arc
322 *-----------------------------------------------------------------------------
323 */
324
325 void
326 ArcTessellator::tessellateNonlinear( Arc *arc, REAL geo_stepsize, REAL arc_stepsize, int isrational )
327 {
328 assert( arc->pwlArc == NULL );
329
330 REAL stepsize = geo_stepsize * arc_stepsize;
331
332 BezierArc *bezierArc = arc->bezierArc;
333
334 REAL size; //bounding box size of the curve in UV
335 {
336 int i,j;
337 REAL min_u, min_v, max_u,max_v;
338 min_u = max_u = bezierArc->cpts[0];
339 min_v = max_v = bezierArc->cpts[1];
340 for(i=1, j=2; i<bezierArc->order; i++, j+= bezierArc->stride)
341 {
342 if(bezierArc->cpts[j] < min_u)
343 min_u = bezierArc->cpts[j];
344 if(bezierArc->cpts[j] > max_u)
345 max_u = bezierArc->cpts[j];
346 if(bezierArc->cpts[j+1] < min_v)
347 min_v = bezierArc->cpts[j+1];
348 if(bezierArc->cpts[j+1] > max_v)
349 max_v = bezierArc->cpts[j+1];
350 }
351
352 size = max_u - min_u;
353 if(size < max_v - min_v)
354 size = max_v - min_v;
355 }
356
357 /*int nsteps = 1 + (int) (1.0/stepsize);*/
358
359 int nsteps = (int) (size/stepsize);
360 if(nsteps <=0)
361 nsteps=1;
362
363 TrimVertex *vert = trimvertexpool.get( nsteps+1 );
364 REAL dp = 1.0/nsteps;
365
366
367 arc->pwlArc = new(pwlarcpool) PwlArc();
368 arc->pwlArc->pts = vert;
369
370 if( isrational ) {
371 REAL pow_u[MAXORDER], pow_v[MAXORDER], pow_w[MAXORDER];
372 trim_power_coeffs( bezierArc, pow_u, 0 );
373 trim_power_coeffs( bezierArc, pow_v, 1 );
374 trim_power_coeffs( bezierArc, pow_w, 2 );
375
376 /* compute first point exactly */
377 REAL *b = bezierArc->cpts;
378 vert->param[0] = b[0]/b[2];
379 vert->param[1] = b[1]/b[2];
380
381 /* strength reduction on p = dp * step would introduce error */
382 int step;
383 int ocanremove = 0;
384 register long order = bezierArc->order;
385 for( step=1, ++vert; step<nsteps; step++, vert++ ) {
386 register REAL p = dp * step;
387 register REAL u = pow_u[0];
388 register REAL v = pow_v[0];
389 register REAL w = pow_w[0];
390 for( register int i = 1; i < order; i++ ) {
391 u = u * p + pow_u[i];
392 v = v * p + pow_v[i];
393 w = w * p + pow_w[i];
394 }
395 vert->param[0] = u/w;
396 vert->param[1] = v/w;
397 #ifndef NOELIMINATION
398 REAL ds = abs(vert[0].param[0] - vert[-1].param[0]);
399 REAL dt = abs(vert[0].param[1] - vert[-1].param[1]);
400 int canremove = (ds<geo_stepsize && dt<geo_stepsize) ? 1 : 0;
401 REAL ods=0.0, odt=0.0;
402
403 if( ocanremove && canremove ) {
404 REAL nds = ds + ods;
405 REAL ndt = dt + odt;
406 if( nds<geo_stepsize && ndt<geo_stepsize ) {
407 // remove previous point
408 --vert;
409 vert[0].param[0] = vert[1].param[0];
410 vert[0].param[1] = vert[1].param[1];
411 ods = nds;
412 odt = ndt;
413 ocanremove = 1;
414 } else {
415 ocanremove = canremove;
416 ods = ds;
417 odt = dt;
418 }
419 } else {
420 ocanremove = canremove;
421 ods = ds;
422 odt = dt;
423 }
424 #endif
425 }
426
427 /* compute last point exactly */
428 b += (order - 1) * bezierArc->stride;
429 vert->param[0] = b[0]/b[2];
430 vert->param[1] = b[1]/b[2];
431
432 } else {
433 REAL pow_u[MAXORDER], pow_v[MAXORDER];
434 trim_power_coeffs( bezierArc, pow_u, 0 );
435 trim_power_coeffs( bezierArc, pow_v, 1 );
436
437 /* compute first point exactly */
438 REAL *b = bezierArc->cpts;
439 vert->param[0] = b[0];
440 vert->param[1] = b[1];
441
442 /* strength reduction on p = dp * step would introduce error */
443 int step;
444 int ocanremove = 0;
445 register long order = bezierArc->order;
446 for( step=1, ++vert; step<nsteps; step++, vert++ ) {
447 register REAL p = dp * step;
448 register REAL u = pow_u[0];
449 register REAL v = pow_v[0];
450 for( register int i = 1; i < bezierArc->order; i++ ) {
451 u = u * p + pow_u[i];
452 v = v * p + pow_v[i];
453 }
454 vert->param[0] = u;
455 vert->param[1] = v;
456 #ifndef NOELIMINATION
457 REAL ds = abs(vert[0].param[0] - vert[-1].param[0]);
458 REAL dt = abs(vert[0].param[1] - vert[-1].param[1]);
459 int canremove = (ds<geo_stepsize && dt<geo_stepsize) ? 1 : 0;
460 REAL ods=0.0, odt=0.0;
461
462 if( ocanremove && canremove ) {
463 REAL nds = ds + ods;
464 REAL ndt = dt + odt;
465 if( nds<geo_stepsize && ndt<geo_stepsize ) {
466 // remove previous point
467 --vert;
468 vert[0].param[0] = vert[1].param[0];
469 vert[0].param[1] = vert[1].param[1];
470 ods = nds;
471 odt = ndt;
472 ocanremove = 1;
473 } else {
474 ocanremove = canremove;
475 ods = ds;
476 odt = dt;
477 }
478 } else {
479 ocanremove = canremove;
480 ods = ds;
481 odt = dt;
482 }
483 #endif
484 }
485
486 /* compute last point exactly */
487 b += (order - 1) * bezierArc->stride;
488 vert->param[0] = b[0];
489 vert->param[1] = b[1];
490 }
491 arc->pwlArc->npts = vert - arc->pwlArc->pts + 1;
492 /*
493 for( TrimVertex *vt=pwlArc->pts; vt != vert-1; vt++ ) {
494 if( tooclose( vt[0].param[0], vt[1].param[0] ) )
495 vt[1].param[0] = vt[0].param[0];
496 if( tooclose( vt[0].param[1], vt[1].param[1] ) )
497 vt[1].param[1] = vt[0].param[1];
498 }
499 */
500 }
501
502 const REAL ArcTessellator::gl_Bernstein[][MAXORDER][MAXORDER] = {
503 {
504 {1, 0, 0, 0, 0, 0, 0, 0 },
505 {0, 0, 0, 0, 0, 0, 0, 0 },
506 {0, 0, 0, 0, 0, 0, 0, 0 },
507 {0, 0, 0, 0, 0, 0, 0, 0 },
508 {0, 0, 0, 0, 0, 0, 0, 0 },
509 {0, 0, 0, 0, 0, 0, 0, 0 },
510 {0, 0, 0, 0, 0, 0, 0, 0 },
511 {0, 0, 0, 0, 0, 0, 0, 0 }
512 },
513 {
514 {-1, 1, 0, 0, 0, 0, 0, 0 },
515 {1, 0, 0, 0, 0, 0, 0, 0 },
516 {0, 0, 0, 0, 0, 0, 0, 0 },
517 {0, 0, 0, 0, 0, 0, 0, 0 },
518 {0, 0, 0, 0, 0, 0, 0, 0 },
519 {0, 0, 0, 0, 0, 0, 0, 0 },
520 {0, 0, 0, 0, 0, 0, 0, 0 },
521 {0, 0, 0, 0, 0, 0, 0, 0 }
522 },
523 {
524 {1, -2, 1, 0, 0, 0, 0, 0 },
525 {-2, 2, 0, 0, 0, 0, 0, 0 },
526 {1, 0, 0, 0, 0, 0, 0, 0 },
527 {0, 0, 0, 0, 0, 0, 0, 0 },
528 {0, 0, 0, 0, 0, 0, 0, 0 },
529 {0, 0, 0, 0, 0, 0, 0, 0 },
530 {0, 0, 0, 0, 0, 0, 0, 0 },
531 {0, 0, 0, 0, 0, 0, 0, 0 }
532 },
533 {
534 {-1, 3, -3, 1, 0, 0, 0, 0 },
535 {3, -6, 3, 0, 0, 0, 0, 0 },
536 {-3, 3, 0, 0, 0, 0, 0, 0 },
537 {1, 0, 0, 0, 0, 0, 0, 0 },
538 {0, 0, 0, 0, 0, 0, 0, 0 },
539 {0, 0, 0, 0, 0, 0, 0, 0 },
540 {0, 0, 0, 0, 0, 0, 0, 0 },
541 {0, 0, 0, 0, 0, 0, 0, 0 }
542 },
543 {
544 {1, -4, 6, -4, 1, 0, 0, 0 },
545 {-4, 12, -12, 4, 0, 0, 0, 0 },
546 {6, -12, 6, 0, 0, 0, 0, 0 },
547 {-4, 4, 0, 0, 0, 0, 0, 0 },
548 {1, 0, 0, 0, 0, 0, 0, 0 },
549 {0, 0, 0, 0, 0, 0, 0, 0 },
550 {0, 0, 0, 0, 0, 0, 0, 0 },
551 {0, 0, 0, 0, 0, 0, 0, 0 }
552 },
553 {
554 {-1, 5, -10, 10, -5, 1, 0, 0 },
555 {5, -20, 30, -20, 5, 0, 0, 0 },
556 {-10, 30, -30, 10, 0, 0, 0, 0 },
557 {10, -20, 10, 0, 0, 0, 0, 0 },
558 {-5, 5, 0, 0, 0, 0, 0, 0 },
559 {1, 0, 0, 0, 0, 0, 0, 0 },
560 {0, 0, 0, 0, 0, 0, 0, 0 },
561 {0, 0, 0, 0, 0, 0, 0, 0 }
562 },
563 {
564 {1, -6, 15, -20, 15, -6, 1, 0 },
565 {-6, 30, -60, 60, -30, 6, 0, 0 },
566 {15, -60, 90, -60, 15, 0, 0, 0 },
567 {-20, 60, -60, 20, 0, 0, 0, 0 },
568 {15, -30, 15, 0, 0, 0, 0, 0 },
569 {-6, 6, 0, 0, 0, 0, 0, 0 },
570 {1, 0, 0, 0, 0, 0, 0, 0 },
571 {0, 0, 0, 0, 0, 0, 0, 0 }
572 },
573 {
574 {-1, 7, -21, 35, -35, 21, -7, 1 },
575 {7, -42, 105, -140, 105, -42, 7, 0 },
576 {-21, 105, -210, 210, -105, 21, 0, 0 },
577 {35, -140, 210, -140, 35, 0, 0, 0 },
578 {-35, 105, -105, 35, 0, 0, 0, 0 },
579 {21, -42, 21, 0, 0, 0, 0, 0 },
580 {-7, 7, 0, 0, 0, 0, 0, 0 },
581 {1, 0, 0, 0, 0, 0, 0, 0 }
582 }};
583
584
585 /*-----------------------------------------------------------------------------
586 * trim_power_coeffs - compute power basis coefficients from bezier coeffients
587 *-----------------------------------------------------------------------------
588 */
589 void
590 ArcTessellator::trim_power_coeffs( BezierArc *bez_arc, REAL *p, int coord )
591 {
592 register int stride = bez_arc->stride;
593 register int order = bez_arc->order;
594 register REAL *base = bez_arc->cpts + coord;
595
596 REAL const (*mat)[MAXORDER][MAXORDER] = &gl_Bernstein[order-1];
597 REAL const (*lrow)[MAXORDER] = &(*mat)[order];
598
599 /* WIN32 didn't like the following line within the for-loop */
600 REAL const (*row)[MAXORDER] = &(*mat)[0];
601 for( ; row != lrow; row++ ) {
602 register REAL s = 0.0;
603 register REAL *point = base;
604 register REAL const *mlast = *row + order;
605 for( REAL const *m = *row; m != mlast; m++, point += stride )
606 s += *(m) * (*point);
607 *(p++) = s;
608 }
609 }