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.
40 #include "glimports.h"
45 #include "simplemath.h"
46 #include "bezierarc.h"
47 #include "trimvertex.h"
48 #include "trimvertpool.h"
52 #define steps_function(large, small, rate) (max(1, 1+ (int) ((large-small)/rate)));
54 /*-----------------------------------------------------------------------------
55 * ArcTessellator - construct an ArcTessellator
56 *-----------------------------------------------------------------------------
59 ArcTessellator::ArcTessellator( TrimVertexPool& t, Pool& p )
60 : pwlarcpool(p), trimvertexpool(t)
64 /*-----------------------------------------------------------------------------
65 * ~ArcTessellator - destroy an ArcTessellator
66 *-----------------------------------------------------------------------------
69 ArcTessellator::~ArcTessellator( void )
73 /*-----------------------------------------------------------------------------
74 * bezier - construct a bezier arc and attach it to an Arc
75 *-----------------------------------------------------------------------------
79 ArcTessellator::bezier( Arc *arc, REAL s1, REAL s2, REAL t1, REAL t2 )
82 assert( ! arc->isTessellated() );
85 switch( arc->getside() ) {
108 TrimVertex *p = trimvertexpool.get(2);
109 arc->pwlArc = new(pwlarcpool) PwlArc( 2, p );
114 assert( (s1 == s2) || (t1 == t2) );
119 /*-----------------------------------------------------------------------------
120 * pwl_left - construct a left boundary pwl arc and attach it to an arc
121 *-----------------------------------------------------------------------------
125 ArcTessellator::pwl_left( Arc *arc, REAL s, REAL t1, REAL t2, REAL rate )
129 /* if(rate <= 0.06) rate = 0.06;*/
130 /* int nsteps = 1 + (int) ((t1 - t2) / rate ); */
131 int nsteps = steps_function(t1, t2, rate);
134 REAL stepsize = (t1 - t2) / (REAL) nsteps;
136 TrimVertex *newvert = trimvertexpool.get( nsteps+1 );
138 for( i = nsteps; i > 0; i-- ) {
139 newvert[i].param[0] = s;
140 newvert[i].param[1] = t2;
143 newvert[i].param[0] = s;
144 newvert[i].param[1] = t1;
146 arc->makeSide( new(pwlarcpool) PwlArc( nsteps+1, newvert ), arc_left );
149 /*-----------------------------------------------------------------------------
150 * pwl_right - construct a right boundary pwl arc and attach it to an arc
151 *-----------------------------------------------------------------------------
155 ArcTessellator::pwl_right( Arc *arc, REAL s, REAL t1, REAL t2, REAL rate )
159 /* if(rate <= 0.06) rate = 0.06;*/
161 /* int nsteps = 1 + (int) ((t2 - t1) / rate ); */
162 int nsteps = steps_function(t2,t1,rate);
163 REAL stepsize = (t2 - t1) / (REAL) nsteps;
165 TrimVertex *newvert = trimvertexpool.get( nsteps+1 );
167 for( i = 0; i < nsteps; i++ ) {
168 newvert[i].param[0] = s;
169 newvert[i].param[1] = t1;
172 newvert[i].param[0] = s;
173 newvert[i].param[1] = t2;
175 arc->makeSide( new(pwlarcpool) PwlArc( nsteps+1, newvert ), arc_right );
179 /*-----------------------------------------------------------------------------
180 * pwl_top - construct a top boundary pwl arc and attach it to an arc
181 *-----------------------------------------------------------------------------
185 ArcTessellator::pwl_top( Arc *arc, REAL t, REAL s1, REAL s2, REAL rate )
189 /* if(rate <= 0.06) rate = 0.06;*/
191 /* int nsteps = 1 + (int) ((s1 - s2) / rate ); */
192 int nsteps = steps_function(s1,s2,rate);
193 REAL stepsize = (s1 - s2) / (REAL) nsteps;
195 TrimVertex *newvert = trimvertexpool.get( nsteps+1 );
197 for( i = nsteps; i > 0; i-- ) {
198 newvert[i].param[0] = s2;
199 newvert[i].param[1] = t;
202 newvert[i].param[0] = s1;
203 newvert[i].param[1] = t;
205 arc->makeSide( new(pwlarcpool) PwlArc( nsteps+1, newvert ), arc_top );
208 /*-----------------------------------------------------------------------------
209 * pwl_bottom - construct a bottom boundary pwl arc and attach it to an arc
210 *-----------------------------------------------------------------------------
214 ArcTessellator::pwl_bottom( Arc *arc, REAL t, REAL s1, REAL s2, REAL rate )
218 /* if(rate <= 0.06) rate = 0.06;*/
220 /* int nsteps = 1 + (int) ((s2 - s1) / rate ); */
221 int nsteps = steps_function(s2,s1,rate);
222 REAL stepsize = (s2 - s1) / (REAL) nsteps;
224 TrimVertex *newvert = trimvertexpool.get( nsteps+1 );
226 for( i = 0; i < nsteps; i++ ) {
227 newvert[i].param[0] = s1;
228 newvert[i].param[1] = t;
231 newvert[i].param[0] = s2;
232 newvert[i].param[1] = t;
234 arc->makeSide( new(pwlarcpool) PwlArc( nsteps+1, newvert ), arc_bottom );
237 /*-----------------------------------------------------------------------------
238 * pwl - construct a pwl arc and attach it to an arc
239 *-----------------------------------------------------------------------------
243 ArcTessellator::pwl( Arc *arc, REAL s1, REAL s2, REAL t1, REAL t2, REAL rate )
246 /* if(rate <= 0.06) rate = 0.06;*/
248 int snsteps = 1 + (int) (glu_abs(s2 - s1) / rate );
249 int tnsteps = 1 + (int) (glu_abs(t2 - t1) / rate );
250 int nsteps = max(1,max( snsteps, tnsteps ));
252 REAL sstepsize = (s2 - s1) / (REAL) nsteps;
253 REAL tstepsize = (t2 - t1) / (REAL) nsteps;
254 TrimVertex *newvert = trimvertexpool.get( nsteps+1 );
256 for( i = 0; i < nsteps; i++ ) {
257 newvert[i].param[0] = s1;
258 newvert[i].param[1] = t1;
262 newvert[i].param[0] = s2;
263 newvert[i].param[1] = t2;
265 /* arc->makeSide( new(pwlarcpool) PwlArc( nsteps+1, newvert ), arc_bottom ); */
266 arc->pwlArc = new(pwlarcpool) PwlArc( nsteps+1, newvert );
273 /*-----------------------------------------------------------------------------
274 * tessellateLinear - constuct a linear pwl arc and attach it to an Arc
275 *-----------------------------------------------------------------------------
279 ArcTessellator::tessellateLinear( Arc *arc, REAL geo_stepsize, REAL arc_stepsize, int isrational )
281 assert( arc->pwlArc == NULL );
284 //we don't need to scale by arc_stepsize if the trim curve
285 //is piecewise linear. Reason: In pwl_right, pwl_left, pwl_top, pwl_left,
286 //and pwl, the nsteps is computed by deltaU (or V) /stepsize.
287 //The quantity deltaU/arc_stepsize doesn't have any meaning. And
288 //it causes problems: see bug 517641
289 REAL stepsize = geo_stepsize; /* * arc_stepsize*/;
291 BezierArc *b = arc->bezierArc;
294 s1 = b->cpts[0] / b->cpts[2];
295 t1 = b->cpts[1] / b->cpts[2];
296 s2 = b->cpts[b->stride+0] / b->cpts[b->stride+2];
297 t2 = b->cpts[b->stride+1] / b->cpts[b->stride+2];
301 s2 = b->cpts[b->stride+0];
302 t2 = b->cpts[b->stride+1];
306 pwl_right( arc, s1, t1, t2, stepsize );
308 pwl_left( arc, s1, t1, t2, stepsize );
311 pwl_bottom( arc, t1, s1, s2, stepsize );
313 pwl_top( arc, t1, s1, s2, stepsize );
315 pwl( arc, s1, s2, t1, t2, stepsize );
318 /*-----------------------------------------------------------------------------
319 * tessellateNonlinear - constuct a nonlinear pwl arc and attach it to an Arc
320 *-----------------------------------------------------------------------------
324 ArcTessellator::tessellateNonlinear( Arc *arc, REAL geo_stepsize, REAL arc_stepsize, int isrational )
326 assert( arc->pwlArc == NULL );
328 REAL stepsize = geo_stepsize * arc_stepsize;
330 BezierArc *bezierArc = arc->bezierArc;
332 REAL size; //bounding box size of the curve in UV
335 REAL min_u, min_v, max_u,max_v;
336 min_u = max_u = bezierArc->cpts[0];
337 min_v = max_v = bezierArc->cpts[1];
338 for(i=1, j=bezierArc->stride; i<bezierArc->order; i++, j+= bezierArc->stride)
340 if(bezierArc->cpts[j] < min_u)
341 min_u = bezierArc->cpts[j];
342 if(bezierArc->cpts[j] > max_u)
343 max_u = bezierArc->cpts[j];
344 if(bezierArc->cpts[j+1] < min_v)
345 min_v = bezierArc->cpts[j+1];
346 if(bezierArc->cpts[j+1] > max_v)
347 max_v = bezierArc->cpts[j+1];
350 size = max_u - min_u;
351 if(size < max_v - min_v)
352 size = max_v - min_v;
355 /*int nsteps = 1 + (int) (1.0/stepsize);*/
357 int nsteps = (int) (size/stepsize);
361 TrimVertex *vert = trimvertexpool.get( nsteps+1 );
362 REAL dp = 1.0/nsteps;
365 arc->pwlArc = new(pwlarcpool) PwlArc();
366 arc->pwlArc->pts = vert;
369 REAL pow_u[MAXORDER], pow_v[MAXORDER], pow_w[MAXORDER];
370 trim_power_coeffs( bezierArc, pow_u, 0 );
371 trim_power_coeffs( bezierArc, pow_v, 1 );
372 trim_power_coeffs( bezierArc, pow_w, 2 );
374 /* compute first point exactly */
375 REAL *b = bezierArc->cpts;
376 vert->param[0] = b[0]/b[2];
377 vert->param[1] = b[1]/b[2];
379 /* strength reduction on p = dp * step would introduce error */
381 #ifndef NOELIMINATION
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];
395 vert->param[0] = u/w;
396 vert->param[1] = v/w;
397 #ifndef NOELIMINATION
398 REAL ds = glu_abs(vert[0].param[0] - vert[-1].param[0]);
399 REAL dt = glu_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;
403 if( ocanremove && canremove ) {
406 if( nds<geo_stepsize && ndt<geo_stepsize ) {
407 // remove previous point
409 vert[0].param[0] = vert[1].param[0];
410 vert[0].param[1] = vert[1].param[1];
415 ocanremove = canremove;
420 ocanremove = canremove;
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];
433 REAL pow_u[MAXORDER], pow_v[MAXORDER];
434 trim_power_coeffs( bezierArc, pow_u, 0 );
435 trim_power_coeffs( bezierArc, pow_v, 1 );
437 /* compute first point exactly */
438 REAL *b = bezierArc->cpts;
439 vert->param[0] = b[0];
440 vert->param[1] = b[1];
442 /* strength reduction on p = dp * step would introduce error */
444 #ifndef NOELIMINATION
447 register long order = bezierArc->order;
448 for( step=1, ++vert; step<nsteps; step++, vert++ ) {
449 register REAL p = dp * step;
450 register REAL u = pow_u[0];
451 register REAL v = pow_v[0];
452 for( register int i = 1; i < bezierArc->order; i++ ) {
453 u = u * p + pow_u[i];
454 v = v * p + pow_v[i];
458 #ifndef NOELIMINATION
459 REAL ds = glu_abs(vert[0].param[0] - vert[-1].param[0]);
460 REAL dt = glu_abs(vert[0].param[1] - vert[-1].param[1]);
461 int canremove = (ds<geo_stepsize && dt<geo_stepsize) ? 1 : 0;
462 REAL ods=0.0, odt=0.0;
464 if( ocanremove && canremove ) {
467 if( nds<geo_stepsize && ndt<geo_stepsize ) {
468 // remove previous point
470 vert[0].param[0] = vert[1].param[0];
471 vert[0].param[1] = vert[1].param[1];
476 ocanremove = canremove;
481 ocanremove = canremove;
488 /* compute last point exactly */
489 b += (order - 1) * bezierArc->stride;
490 vert->param[0] = b[0];
491 vert->param[1] = b[1];
493 arc->pwlArc->npts = vert - arc->pwlArc->pts + 1;
495 for( TrimVertex *vt=pwlArc->pts; vt != vert-1; vt++ ) {
496 if( tooclose( vt[0].param[0], vt[1].param[0] ) )
497 vt[1].param[0] = vt[0].param[0];
498 if( tooclose( vt[0].param[1], vt[1].param[1] ) )
499 vt[1].param[1] = vt[0].param[1];
504 const REAL ArcTessellator::gl_Bernstein[][MAXORDER][MAXORDER] = {
506 {1, 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 {0, 0, 0, 0, 0, 0, 0, 0 },
513 {0, 0, 0, 0, 0, 0, 0, 0 }
516 {-1, 1, 0, 0, 0, 0, 0, 0 },
517 {1, 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 {0, 0, 0, 0, 0, 0, 0, 0 },
523 {0, 0, 0, 0, 0, 0, 0, 0 }
526 {1, -2, 1, 0, 0, 0, 0, 0 },
527 {-2, 2, 0, 0, 0, 0, 0, 0 },
528 {1, 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 {0, 0, 0, 0, 0, 0, 0, 0 },
533 {0, 0, 0, 0, 0, 0, 0, 0 }
536 {-1, 3, -3, 1, 0, 0, 0, 0 },
537 {3, -6, 3, 0, 0, 0, 0, 0 },
538 {-3, 3, 0, 0, 0, 0, 0, 0 },
539 {1, 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 {0, 0, 0, 0, 0, 0, 0, 0 },
543 {0, 0, 0, 0, 0, 0, 0, 0 }
546 {1, -4, 6, -4, 1, 0, 0, 0 },
547 {-4, 12, -12, 4, 0, 0, 0, 0 },
548 {6, -12, 6, 0, 0, 0, 0, 0 },
549 {-4, 4, 0, 0, 0, 0, 0, 0 },
550 {1, 0, 0, 0, 0, 0, 0, 0 },
551 {0, 0, 0, 0, 0, 0, 0, 0 },
552 {0, 0, 0, 0, 0, 0, 0, 0 },
553 {0, 0, 0, 0, 0, 0, 0, 0 }
556 {-1, 5, -10, 10, -5, 1, 0, 0 },
557 {5, -20, 30, -20, 5, 0, 0, 0 },
558 {-10, 30, -30, 10, 0, 0, 0, 0 },
559 {10, -20, 10, 0, 0, 0, 0, 0 },
560 {-5, 5, 0, 0, 0, 0, 0, 0 },
561 {1, 0, 0, 0, 0, 0, 0, 0 },
562 {0, 0, 0, 0, 0, 0, 0, 0 },
563 {0, 0, 0, 0, 0, 0, 0, 0 }
566 {1, -6, 15, -20, 15, -6, 1, 0 },
567 {-6, 30, -60, 60, -30, 6, 0, 0 },
568 {15, -60, 90, -60, 15, 0, 0, 0 },
569 {-20, 60, -60, 20, 0, 0, 0, 0 },
570 {15, -30, 15, 0, 0, 0, 0, 0 },
571 {-6, 6, 0, 0, 0, 0, 0, 0 },
572 {1, 0, 0, 0, 0, 0, 0, 0 },
573 {0, 0, 0, 0, 0, 0, 0, 0 }
576 {-1, 7, -21, 35, -35, 21, -7, 1 },
577 {7, -42, 105, -140, 105, -42, 7, 0 },
578 {-21, 105, -210, 210, -105, 21, 0, 0 },
579 {35, -140, 210, -140, 35, 0, 0, 0 },
580 {-35, 105, -105, 35, 0, 0, 0, 0 },
581 {21, -42, 21, 0, 0, 0, 0, 0 },
582 {-7, 7, 0, 0, 0, 0, 0, 0 },
583 {1, 0, 0, 0, 0, 0, 0, 0 }
587 /*-----------------------------------------------------------------------------
588 * trim_power_coeffs - compute power basis coefficients from bezier coeffients
589 *-----------------------------------------------------------------------------
592 ArcTessellator::trim_power_coeffs( BezierArc *bez_arc, REAL *p, int coord )
594 register int stride = bez_arc->stride;
595 register int order = bez_arc->order;
596 register REAL *base = bez_arc->cpts + coord;
598 REAL const (*mat)[MAXORDER][MAXORDER] = &gl_Bernstein[order-1];
599 REAL const (*lrow)[MAXORDER] = &(*mat)[order];
601 /* WIN32 didn't like the following line within the for-loop */
602 REAL const (*row)[MAXORDER] = &(*mat)[0];
603 for( ; row != lrow; row++ ) {
604 register REAL s = 0.0;
605 register REAL *point = base;
606 register REAL const *mlast = *row + order;
607 for( REAL const *m = *row; m != mlast; m++, point += stride )
608 s += *(m) * (*point);