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 "knotvector.h"
47 /* local type definitions */
48 struct Breakpt
{ /* breakpoints */
49 Knot value
; /* value */
50 int multi
; /* multiplicity */
51 int def
; /* deficit */
54 struct Knotspec
{ /* knotvector format */
55 long order
; /* order of spline */
56 Knot_ptr inkbegin
; /* input knot sequence */
57 Knot_ptr inkend
; /* location after last knot */
58 Knot_ptr outkbegin
; /* in-process knot subsequence */
59 Knot_ptr outkend
; /* location after last knot */
61 Knot_ptr kright
; /* */
62 Knot_ptr kfirst
; /* */
64 Knot_ptr sbegin
; /* conversion factor values */
65 Breakpt
* bbegin
; /* in-process breakpoints */
66 Breakpt
* bend
; /* last breakpoint */
67 int ncoords
; /* coordinates per control point */
68 int prestride
; /* stride between input points */
69 int poststride
; /* stride between output points */
70 int preoffset
; /* scaled point offset */
71 int postoffset
; /* scaled point offset */
72 int prewidth
; /* width of dimension */
73 int postwidth
; /* width of dimension */
74 int istransformed
; /* was dimension transformed */
75 Knotspec
* next
; /* next knotspec */
76 Knotspec
* kspectotrans
; /* knotspec in transformation direction */
81 void insert( REAL
* );
84 void copy( INREAL
*, REAL
* );
85 void breakpoints( void );
87 void transform( REAL
* );
88 void showpts( REAL
* );
90 void pt_io_copy( REAL
*, INREAL
* );
91 void pt_oo_copy( REAL
*, REAL
* );
92 void pt_oo_sum( REAL
*, REAL
*, REAL
*, Knot
, Knot
);
95 struct Splinespec
{ /* a non-uniform tensor element */
98 Knotspec
*kspec
; /* format of each param. dir. */
99 int dim
; /* domain dimension */
100 REAL
* outcpts
; /* Bezier control points */
102 void kspecinit( Knotvector
& );
103 void kspecinit( Knotvector
&, Knotvector
& );
106 void setupquilt( Quilt_ptr
);
107 void copy( INREAL
* );
108 void transform( void );
111 /*-----------------------------------------------------------------------------
112 * Quilt::toBezier - convert from NURBS to rational Bezier
113 *-----------------------------------------------------------------------------
118 Knotvector
& knotvector
, /* a knot vector */
119 INREAL
*ctlpts
, /* input contol points */
120 long ncoords
) /* number of coordinates per control point */
122 Splinespec
spline( 1 );
123 spline
.kspecinit( knotvector
);
125 spline
.layout( ncoords
);
126 spline
.setupquilt( this );
127 spline
.copy( ctlpts
);
133 Knotvector
& sknotvector
, /* a knot vector */
134 Knotvector
& tknotvector
, /* a knot vector */
135 INREAL
*ctlpts
, /* input contol points */
136 long ncoords
) /* number of coordinates per control point */
138 Splinespec
spline( 2 );
139 spline
.kspecinit( sknotvector
, tknotvector
);
141 spline
.layout( ncoords
);
142 spline
.setupquilt( this );
143 spline
.copy( ctlpts
);
146 Splinespec::Splinespec( int dimen
)
151 Splinespec::~Splinespec( void )
153 /* Note: do NOT delete 'outcpts' here since its address (not contents)
154 * is copied in 'cpts' in this file in function Splinespec::setupquilt().
155 * This block of memory will eventually be deleted in file quilt.c++ in
156 * function Quilt::deleteMe() through 'cpts' so do NOT delete it here!
158 Knotspec
*ktrav
= kspec
; //start at beginning of list
159 while (ktrav
!= 0) { //any items to delete?
160 Knotspec
*deleteThis
= ktrav
; //remember to delete this
161 ktrav
= ktrav
->next
; //go to next item if any
162 delete deleteThis
; //delete it
164 } /* ~Splinespec() */
166 /*-----------------------------------------------------------------------------
167 * Splinespec::kspecinit - initialize Splinespec structure
169 * Client: Quilt::toBezier
170 *-----------------------------------------------------------------------------
174 Splinespec::kspecinit( Knotvector
& knotvector
)
176 kspec
= new Knotspec
;
177 kspec
->inkbegin
= knotvector
.knotlist
;
178 kspec
->inkend
= knotvector
.knotlist
+ knotvector
.knotcount
;
179 kspec
->prestride
= (int) knotvector
.stride
;
180 kspec
->order
= knotvector
.order
;
185 Splinespec::kspecinit( Knotvector
& sknotvector
, Knotvector
& tknotvector
)
187 kspec
= new Knotspec
;
188 Knotspec
*tkspec
= new Knotspec
;
190 kspec
->inkbegin
= sknotvector
.knotlist
;
191 kspec
->inkend
= sknotvector
.knotlist
+ sknotvector
.knotcount
;
192 kspec
->prestride
= (int) sknotvector
.stride
;
193 kspec
->order
= sknotvector
.order
;
194 kspec
->next
= tkspec
;
196 tkspec
->inkbegin
= tknotvector
.knotlist
;
197 tkspec
->inkend
= tknotvector
.knotlist
+ tknotvector
.knotcount
;
198 tkspec
->prestride
= (int) tknotvector
.stride
;
199 tkspec
->order
= tknotvector
.order
;
204 /*-----------------------------------------------------------------------------
205 * Splinespec::select - select the subsegments to copy
207 * Client: gl_quilt_to_bezier
208 *-----------------------------------------------------------------------------
212 Splinespec::select( )
214 for( Knotspec
*knotspec
= kspec
; knotspec
; knotspec
= knotspec
->next
) {
215 knotspec
->preselect();
220 /*-----------------------------------------------------------------------------
221 * Splinespec::layout -
223 * Client: gl_quilt_to_bezier
224 *-----------------------------------------------------------------------------
228 Splinespec::layout( long ncoords
)
231 long stride
= ncoords
;
232 for( Knotspec
*knotspec
= kspec
; knotspec
; knotspec
=knotspec
->next
) {
233 knotspec
->poststride
= (int) stride
;
234 stride
*= ((knotspec
->bend
-knotspec
->bbegin
)*knotspec
->order
+ knotspec
->postoffset
);
235 knotspec
->preoffset
*= knotspec
->prestride
;
236 knotspec
->prewidth
*= knotspec
->poststride
;
237 knotspec
->postwidth
*= knotspec
->poststride
;
238 knotspec
->postoffset
*= knotspec
->poststride
;
239 knotspec
->ncoords
= (int) ncoords
;
241 outcpts
= new REAL
[stride
];
242 assert( outcpts
!= 0 );
245 /*-----------------------------------------------------------------------------
246 * Splinespec::copy - copy the control points of current subobject
248 * Client: gl_quilt_to_bezier
249 *-----------------------------------------------------------------------------
253 Splinespec::copy( INREAL
*incpts
)
255 kspec
->copy( incpts
, outcpts
);
258 /*-----------------------------------------------------------------------------
259 * Splinespec::setupquilt - assign all quilt variables from knotspec
261 * Client: gl_quilt_to_bezier
262 *-----------------------------------------------------------------------------
266 Splinespec::setupquilt( Quilt_ptr quilt
)
268 Quiltspec_ptr qspec
= quilt
->qspec
;
269 quilt
->eqspec
= qspec
+ dim
;
270 for( Knotspec
*knotspec
= kspec
; knotspec
; knotspec
=knotspec
->next
, qspec
++ ) {
271 qspec
->stride
= knotspec
->poststride
;
272 qspec
->width
= knotspec
->bend
- knotspec
->bbegin
;
273 qspec
->order
= (int) knotspec
->order
;
274 qspec
->offset
= knotspec
->postoffset
;
276 qspec
->bdry
[0] = (knotspec
->kleft
== knotspec
->kfirst
) ? 1 : 0;
277 qspec
->bdry
[1] = (knotspec
->kright
== knotspec
->klast
) ? 1 : 0;
278 qspec
->breakpoints
= new Knot
[qspec
->width
+1];
279 Knot_ptr k
= qspec
->breakpoints
;
280 for( Breakpt
*bk
= knotspec
->bbegin
; bk
<= knotspec
->bend
; bk
++ )
283 quilt
->cpts
= outcpts
;
287 /*-----------------------------------------------------------------------------
288 * Splinespec::transform - convert a spline to Bezier format
290 * Client: gl_quilt_to_bezier
291 *-----------------------------------------------------------------------------
295 Splinespec::transform( void )
298 for( knotspec
= kspec
; knotspec
; knotspec
=knotspec
->next
)
299 knotspec
->istransformed
= 0;
301 for( knotspec
= kspec
; knotspec
; knotspec
=knotspec
->next
) {
302 for( Knotspec
*kspec2
= kspec
; kspec2
; kspec2
=kspec2
->next
)
303 kspec2
->kspectotrans
= knotspec
;
304 kspec
->transform( outcpts
);
305 knotspec
->istransformed
= 1;
310 /*-----------------------------------------------------------------------------
311 * Knotspec::Knotspec - constuct a knot spec
312 *-----------------------------------------------------------------------------
315 Knotspec::Knotspec( void )
322 /*-----------------------------------------------------------------------------
323 * Knotspec::copy - copy the control points along minor direction
325 * Client: Splinespec::copy
326 *-----------------------------------------------------------------------------
330 Knotspec::copy( INREAL
*inpt
, REAL
*outpt
)
332 inpt
= (INREAL
*) (((char *) inpt
) + preoffset
);
335 for( REAL
*lpt
=outpt
+prewidth
; outpt
!= lpt
; outpt
+= poststride
) {
336 next
->copy( inpt
, outpt
);
337 inpt
= (INREAL
*) (((char *) inpt
) + prestride
);
340 for( REAL
*lpt
=outpt
+prewidth
; outpt
!= lpt
; outpt
+= poststride
) {
341 pt_io_copy( outpt
, inpt
);
342 inpt
= (INREAL
*) (((char *) inpt
) + prestride
);
347 /*-----------------------------------------------------------------------------
348 * Knotspec::showpts - print out points before transformation
350 * Client: Knotspec::select
351 *-----------------------------------------------------------------------------
354 Knotspec::showpts( REAL
*outpt
)
357 for( REAL
*lpt
=outpt
+prewidth
; outpt
!= lpt
; outpt
+= poststride
)
358 next
->showpts( outpt
);
360 for( REAL
*lpt
=outpt
+prewidth
; outpt
!= lpt
; outpt
+= poststride
)
361 _glu_dprintf( "show %g %g %g\n", outpt
[0], outpt
[1], outpt
[2] );
365 /*-----------------------------------------------------------------------------
366 * Knotspec::factors - precompute scale factors
367 * - overwrites knot vector, actual new knot vector is NOT produced
369 * Client: Knotspec::select
370 *-----------------------------------------------------------------------------
374 Knotspec::factors( void )
376 Knot
*mid
= (outkend
- 1) - order
+ bend
->multi
;
377 Knot_ptr fptr
= sbegin
;
379 for( Breakpt
*bpt
= bend
; bpt
>= bbegin
; bpt
-- ) {
380 mid
-= bpt
->multi
; // last knot less than knot to insert
381 int def
= bpt
->def
- 1; // number of knots to insert
382 if( def
<= 0 ) continue;
383 Knot kv
= bpt
->value
; // knot to insert
385 Knot
*kf
= (mid
-def
) + (order
-1);
386 for( Knot
*kl
= kf
+ def
; kl
!= kf
; kl
-- ) {
388 for( kt
=kl
, kh
=mid
; kt
!= kf
; kh
--, kt
-- )
389 *(fptr
++) = (kv
- *kh
) / (*kt
- *kh
);
395 /*-----------------------------------------------------------------------------
396 * Knotspec::insert - convert subobject in direction of kspec into Bezier
398 * Client: Knotspec::transform
399 *-----------------------------------------------------------------------------
403 Knotspec::insert( REAL
*p
)
405 Knot_ptr fptr
= sbegin
;
406 REAL
*srcpt
= p
+ prewidth
- poststride
;
407 REAL
*dstpt
= p
+ postwidth
+ postoffset
- poststride
;
410 for( REAL
*pend
= srcpt
- poststride
*bpt
->def
; srcpt
!= pend
; pend
+=poststride
) {
412 for( REAL
*p2
= srcpt
-poststride
; p2
!= pend
; p1
= p2
, p2
-= poststride
) {
413 pt_oo_sum( p1
, p1
, p2
, *fptr
, 1.0-*fptr
);
418 for( --bpt
; bpt
>= bbegin
; bpt
-- ) {
420 for( int multi
= bpt
->multi
; multi
> 0; multi
-- ) {
421 pt_oo_copy( dstpt
, srcpt
);
426 for( REAL
*pend
= srcpt
- poststride
*bpt
->def
; srcpt
!= pend
; pend
+=poststride
, dstpt
-=poststride
) {
427 pt_oo_copy( dstpt
, srcpt
);
430 for( REAL
*p2
= srcpt
-poststride
; p2
!= pend
; p1
=p2
, p2
-= poststride
) {
431 pt_oo_sum( p1
, p1
, p2
, *fptr
, 1.0-*fptr
);
438 /*-----------------------------------------------------------------------------
439 * Knotspec::preselect - initialize kspec for processing
441 * Client: Splinespec::select
442 *-----------------------------------------------------------------------------
446 Knotspec::preselect( void )
450 /* position klast after last knot of "last" breakpoint */
451 for( klast
= inkend
- order
, kval
= *klast
; klast
!= inkend
; klast
++ )
452 if( ! identical( *klast
, kval
) ) break;
454 /* position kfirst after last knot of "first" breakpoint */
455 for( kfirst
= inkbegin
+order
-1, kval
= *kfirst
; kfirst
!= inkend
; kfirst
++ )
456 if( ! identical( *kfirst
, kval
) ) break;
458 /* compute multiplicity of first breakpoint */
460 for( k
= kfirst
- 1; k
>= inkbegin
; k
-- )
461 if( ! identical( kval
, *k
) ) break;
464 /* allocate space for breakpoints -
465 use worst case estimate on number of breakpoints */
467 bbegin
= new Breakpt
[(klast
- kfirst
)+1];
468 /* record multiplicity and value of first breakpoint */
469 bbegin
->multi
= kfirst
- k
;
470 bbegin
->value
= kval
;
473 kleft
= kright
= kfirst
;
477 /*-----------------------------------------------------------------------------
478 * Knotspec::select - Knotspec::select segments and precompute scale factors
480 * Client: Splinespec::select
481 *-----------------------------------------------------------------------------
485 Knotspec::select( void )
491 preoffset
= kleft
- (inkbegin
+ order
);
492 postwidth
= (int)((bend
- bbegin
) * order
);
493 prewidth
= (int)((outkend
- outkbegin
) - order
);
494 postoffset
= (bbegin
->def
> 1) ? (bbegin
->def
-1) : 0;
497 /*-----------------------------------------------------------------------------
498 * Knotspec::breakpoints - compute breakpoints for knotspec
500 * Client: Knotspec::select
501 *-----------------------------------------------------------------------------
505 Knotspec::breakpoints( void )
507 Breakpt
*ubpt
= bbegin
;
508 Breakpt
*ubend
= bend
;
511 ubpt
->value
= ubend
->value
;
512 ubpt
->multi
= ubend
->multi
;
516 for( ; kright
!= klast
; kright
++ ) {
517 if ( identical(*kright
,ubpt
->value
) ) {
520 ubpt
->def
= (int) (order
- ubpt
->multi
);
521 nfactors
+= (ubpt
->def
* (ubpt
->def
- 1)) / 2;
522 (++ubpt
)->value
= *kright
;
526 ubpt
->def
= (int) (order
- ubpt
->multi
);
527 nfactors
+= (ubpt
->def
* (ubpt
->def
- 1)) / 2;
532 sbegin
= new Knot
[nfactors
];
539 /*-----------------------------------------------------------------------------
540 * Knotspec::knots - copy relevant subsequence of knots into temporary area
542 * Client: Knotspec::select
543 *-----------------------------------------------------------------------------
547 Knotspec::knots( void )
549 Knot_ptr inkpt
= kleft
- order
;
550 Knot_ptr inkend
= kright
+ bend
->def
;
552 /* allocate space for knots and factors */
553 outkbegin
= new Knot
[inkend
-inkpt
];
555 for( outkpt
= outkbegin
; inkpt
!= inkend
; inkpt
++, outkpt
++ )
562 /*-----------------------------------------------------------------------------
563 * Knotspec::transform - convert a spline along a given direction
565 * Client: Splienspec::transform
566 *-----------------------------------------------------------------------------
570 Knotspec::transform( REAL
*p
)
573 if( this == kspectotrans
) {
574 next
->transform( p
);
576 if( istransformed
) {
578 for( REAL
*pend
= p
+ postwidth
; p
!= pend
; p
+= poststride
)
579 next
->transform( p
);
581 REAL
*pend
= p
+ prewidth
;
582 for( ; p
!= pend
; p
+= poststride
)
583 next
->transform( p
);
587 if( this == kspectotrans
) {
590 if( istransformed
) {
592 for( REAL
*pend
= p
+ postwidth
; p
!= pend
; p
+= poststride
)
593 kspectotrans
->insert( p
);
595 REAL
*pend
= p
+ prewidth
;
596 for( ; p
!= pend
; p
+= poststride
)
597 kspectotrans
->insert( p
);
603 /*-----------------------------------------------------------------------------
604 * Knotspec::~Knotspec - free space alocated for knotspec
605 *-----------------------------------------------------------------------------
608 Knotspec::~Knotspec( void )
610 if( bbegin
) delete[] bbegin
;
611 if( sbegin
) delete[] sbegin
;
612 if( outkbegin
) delete[] outkbegin
;
616 /*-----------------------------------------------------------------------------
617 * pt_io_copy - make internal copy of input cntrl pt. of x coords
618 *-----------------------------------------------------------------------------
622 Knotspec::pt_io_copy( REAL
*topt
, INREAL
*frompt
)
626 topt
[3] = (REAL
) frompt
[3];
628 topt
[2] = (REAL
) frompt
[2];
630 topt
[1] = (REAL
) frompt
[1];
632 topt
[0] = (REAL
) frompt
[0];
635 for( int i
= 0; i
< ncoords
; i
++ )
636 *topt
++ = (REAL
) *frompt
++;
641 /*-----------------------------------------------------------------------------
642 * pt_oo_copy - make internal copy of internal cntrl pt. of x coords
643 *-----------------------------------------------------------------------------
647 Knotspec::pt_oo_copy( REAL
*topt
, REAL
*frompt
)
660 memcpy( topt
, frompt
, ncoords
* sizeof( REAL
) );
664 /*-----------------------------------------------------------------------------
665 * pt_oo_sum - compute affine combination of internal cntrl pts
666 *-----------------------------------------------------------------------------
670 Knotspec::pt_oo_sum( REAL
*x
, REAL
*y
, REAL
*z
, Knot a
, Knot b
)
674 x
[3] = a
* y
[3] + b
* z
[3];
676 x
[2] = a
* y
[2] + b
* z
[2];
678 x
[1] = a
* y
[1] + b
* z
[1];
680 x
[0] = a
* y
[0] + b
* z
[0];
683 for( int i
= 0; i
< ncoords
; i
++ )
684 *x
++ = a
* *y
++ + b
* *z
++;