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
=2; 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
);