source: trunk/src/opengl/glu/nurbs/internals/tobezier.cpp

Last change on this file was 2689, checked in by jeroen, 26 years ago

* empty log message *
File size: 20.3 KB
Line 
1/* $Id: tobezier.cpp,v 1.1 2000-02-09 08:50:29 jeroen Exp $ */
2/*
3** License Applicability. Except to the extent portions of this file are
4** made subject to an alternative license as permitted in the SGI Free
5** Software License B, Version 1.0 (the "License"), the contents of this
6** file are subject only to the provisions of the License. You may not use
7** this file except in compliance with the License. You may obtain a copy
8** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
9** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10**
11** http://oss.sgi.com/projects/FreeB
12**
13** Note that, as provided in the License, the Software is distributed on an
14** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
15** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
16** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
17** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18**
19** Original Code. The Original Code is: OpenGL Sample Implementation,
20** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
21** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
22** Copyright in any portions created by third parties is as indicated
23** elsewhere herein. All Rights Reserved.
24**
25** Additional Notice Provisions: The application programming interfaces
26** established by SGI in conjunction with the Original Code are The
27** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
28** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
29** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
30** Window System(R) (Version 1.3), released October 19, 1998. This software
31** was created using the OpenGL(R) version 1.2.1 Sample Implementation
32** published by SGI, but has not been independently verified as being
33** compliant with the OpenGL(R) version 1.2.1 Specification.
34*/
35
36/*
37 * tobezier.c++
38 *
39 * $Date: 2000-02-09 08:50:29 $ $Revision: 1.1 $
40 * $Header: /home/ktk/tmp/odin/2007/netlabs.cvs/odin32/src/opengl/glu/nurbs/internals/tobezier.cpp,v 1.1 2000-02-09 08:50:29 jeroen Exp $
41 */
42
43#include "glimports.h"
44#include "myassert.h"
45#include "mystdio.h"
46#include "mystring.h"
47#include "quilt.h"
48#include "knotvector.h"
49
50/* local type definitions */
51struct Breakpt { /* breakpoints */
52 Knot value; /* value */
53 int multi; /* multiplicity */
54 int def; /* deficit */
55};
56
57struct Knotspec { /* knotvector format */
58 long order; /* order of spline */
59 Knot_ptr inkbegin; /* input knot sequence */
60 Knot_ptr inkend; /* location after last knot */
61 Knot_ptr outkbegin; /* in-process knot subsequence */
62 Knot_ptr outkend; /* location after last knot */
63 Knot_ptr kleft; /* */
64 Knot_ptr kright; /* */
65 Knot_ptr kfirst; /* */
66 Knot_ptr klast; /* */
67 Knot_ptr sbegin; /* conversion factor values */
68 Breakpt * bbegin; /* in-process breakpoints */
69 Breakpt * bend; /* last breakpoint */
70 int ncoords; /* coordinates per control point */
71 int prestride; /* stride between input points */
72 int poststride; /* stride between output points */
73 int preoffset; /* scaled point offset */
74 int postoffset; /* scaled point offset */
75 int prewidth; /* width of dimension */
76 int postwidth; /* width of dimension */
77 int istransformed; /* was dimension transformed */
78 Knotspec * next; /* next knotspec */
79 Knotspec * kspectotrans; /* knotspec in transformation direction */
80
81 Knotspec( void );
82 ~Knotspec( void );
83 void factors( void );
84 void insert( REAL * );
85 void preselect();
86 void select( void );
87 void copy( INREAL *, REAL * );
88 void breakpoints( void );
89 void knots( void );
90 void transform( REAL * );
91 void showpts( REAL * );
92
93 void pt_io_copy( REAL *, INREAL * );
94 void pt_oo_copy( REAL *, REAL * );
95 void pt_oo_sum( REAL*, REAL*, REAL*, Knot, Knot );
96};
97
98struct Splinespec { /* a non-uniform tensor element */
99 Splinespec( int );
100 ~Splinespec(void);
101 Knotspec *kspec; /* format of each param. dir. */
102 int dim; /* domain dimension */
103 REAL * outcpts; /* Bezier control points */
104
105 void kspecinit( Knotvector & );
106 void kspecinit( Knotvector &, Knotvector & );
107 void select( void );
108 void layout( long );
109 void setupquilt( Quilt_ptr );
110 void copy( INREAL * );
111 void transform( void );
112};
113
114/*-----------------------------------------------------------------------------
115 * Quilt::toBezier - convert from NURBS to rational Bezier
116 *-----------------------------------------------------------------------------
117 */
118
119void
120Quilt::toBezier(
121 Knotvector& knotvector, /* a knot vector */
122 INREAL *ctlpts, /* input contol points */
123 long ncoords ) /* number of coordinates per control point */
124{
125 Splinespec spline( 1 );
126 spline.kspecinit( knotvector );
127 spline.select();
128 spline.layout( ncoords );
129 spline.setupquilt( this );
130 spline.copy( ctlpts );
131 spline.transform();
132}
133
134void
135Quilt::toBezier(
136 Knotvector& sknotvector, /* a knot vector */
137 Knotvector& tknotvector, /* a knot vector */
138 INREAL *ctlpts, /* input contol points */
139 long ncoords ) /* number of coordinates per control point */
140{
141 Splinespec spline( 2 );
142 spline.kspecinit( sknotvector, tknotvector );
143 spline.select();
144 spline.layout( ncoords );
145 spline.setupquilt( this );
146 spline.copy( ctlpts );
147 spline.transform();
148}
149Splinespec::Splinespec( int dimen )
150{
151 dim = dimen;
152}
153
154Splinespec::~Splinespec( void )
155{
156 /* Note: do NOT delete 'outcpts' here since its address (not contents)
157 * is copied in 'cpts' in this file in function Splinespec::setupquilt().
158 * This block of memory will eventually be deleted in file quilt.c++ in
159 * function Quilt::deleteMe() through 'cpts' so do NOT delete it here!
160 */
161 Knotspec *ktrav= kspec; //start at beginning of list
162 while (ktrav != 0) { //any items to delete?
163 Knotspec *deleteThis= ktrav; //remember to delete this
164 ktrav= ktrav->next; //go to next item if any
165 delete deleteThis; //delete it
166 }
167} /* ~Splinespec() */
168
169/*-----------------------------------------------------------------------------
170 * Splinespec::kspecinit - initialize Splinespec structure
171 *
172 * Client: Quilt::toBezier
173 *-----------------------------------------------------------------------------
174 */
175
176void
177Splinespec::kspecinit( Knotvector& knotvector )
178{
179 kspec = new Knotspec;
180 kspec->inkbegin = knotvector.knotlist;
181 kspec->inkend = knotvector.knotlist + knotvector.knotcount;
182 kspec->prestride = (int) knotvector.stride;
183 kspec->order = knotvector.order;
184 kspec->next = NULL;
185}
186
187void
188Splinespec::kspecinit( Knotvector& sknotvector, Knotvector& tknotvector )
189{
190 kspec = new Knotspec;
191 Knotspec *tkspec = new Knotspec;
192
193 kspec->inkbegin = sknotvector.knotlist;
194 kspec->inkend = sknotvector.knotlist + sknotvector.knotcount;
195 kspec->prestride = (int) sknotvector.stride;
196 kspec->order = sknotvector.order;
197 kspec->next = tkspec;
198
199 tkspec->inkbegin = tknotvector.knotlist;
200 tkspec->inkend = tknotvector.knotlist + tknotvector.knotcount;
201 tkspec->prestride = (int) tknotvector.stride;
202 tkspec->order = tknotvector.order;
203 tkspec->next = NULL;
204}
205
206
207/*-----------------------------------------------------------------------------
208 * Splinespec::select - select the subsegments to copy
209 *
210 * Client: gl_quilt_to_bezier
211 *-----------------------------------------------------------------------------
212 */
213
214void
215Splinespec::select( )
216{
217 for( Knotspec *knotspec = kspec; knotspec; knotspec = knotspec->next ) {
218 knotspec->preselect();
219 knotspec->select();
220 }
221}
222
223/*-----------------------------------------------------------------------------
224 * Splinespec::layout -
225 *
226 * Client: gl_quilt_to_bezier
227 *-----------------------------------------------------------------------------
228 */
229
230void
231Splinespec::layout( long ncoords )
232{
233
234 long stride = ncoords;
235 for( Knotspec *knotspec = kspec; knotspec; knotspec=knotspec->next ) {
236 knotspec->poststride = (int) stride;
237 stride *= ((knotspec->bend-knotspec->bbegin)*knotspec->order + knotspec->postoffset);
238 knotspec->preoffset *= knotspec->prestride;
239 knotspec->prewidth *= knotspec->poststride;
240 knotspec->postwidth *= knotspec->poststride;
241 knotspec->postoffset *= knotspec->poststride;
242 knotspec->ncoords = (int) ncoords;
243 }
244 outcpts = new REAL[stride];
245 assert( outcpts != 0 );
246}
247
248/*-----------------------------------------------------------------------------
249 * Splinespec::copy - copy the control points of current subobject
250 *
251 * Client: gl_quilt_to_bezier
252 *-----------------------------------------------------------------------------
253 */
254
255void
256Splinespec::copy( INREAL *incpts )
257{
258 kspec->copy( incpts, outcpts );
259}
260
261/*-----------------------------------------------------------------------------
262 * Splinespec::setupquilt - assign all quilt variables from knotspec
263 *
264 * Client: gl_quilt_to_bezier
265 *-----------------------------------------------------------------------------
266 */
267
268void
269Splinespec::setupquilt( Quilt_ptr quilt )
270{
271 Quiltspec_ptr qspec = quilt->qspec;
272 quilt->eqspec = qspec + dim;
273 for( Knotspec *knotspec = kspec; knotspec; knotspec=knotspec->next, qspec++ ) {
274 qspec->stride = knotspec->poststride;
275 qspec->width = knotspec->bend - knotspec->bbegin;
276 qspec->order = (int) knotspec->order;
277 qspec->offset = knotspec->postoffset;
278 qspec->index = 0;
279 qspec->bdry[0] = (knotspec->kleft == knotspec->kfirst) ? 1 : 0;
280 qspec->bdry[1] = (knotspec->kright == knotspec->klast) ? 1 : 0;
281 qspec->breakpoints = new Knot[qspec->width+1];
282 Knot_ptr k = qspec->breakpoints;
283 for( Breakpt *bk = knotspec->bbegin; bk <= knotspec->bend; bk++ )
284 *(k++) = bk->value;
285 }
286 quilt->cpts = outcpts;
287 quilt->next = 0;
288}
289
290/*-----------------------------------------------------------------------------
291 * Splinespec::transform - convert a spline to Bezier format
292 *
293 * Client: gl_quilt_to_bezier
294 *-----------------------------------------------------------------------------
295 */
296
297void
298Splinespec::transform( void )
299{
300 Knotspec *knotspec;
301 for( knotspec = kspec; knotspec; knotspec=knotspec->next )
302 knotspec->istransformed = 0;
303
304 for( knotspec = kspec; knotspec; knotspec=knotspec->next ) {
305 for( Knotspec *kspec2 = kspec; kspec2; kspec2=kspec2->next )
306 kspec2->kspectotrans = knotspec;
307 kspec->transform( outcpts );
308 knotspec->istransformed = 1;
309 }
310}
311
312
313/*-----------------------------------------------------------------------------
314 * Knotspec::Knotspec - constuct a knot spec
315 *-----------------------------------------------------------------------------
316 */
317
318Knotspec::Knotspec( void )
319{
320 bbegin = 0;
321 sbegin = 0;
322 outkbegin = 0;
323}
324
325/*-----------------------------------------------------------------------------
326 * Knotspec::copy - copy the control points along minor direction
327 *
328 * Client: Splinespec::copy
329 *-----------------------------------------------------------------------------
330 */
331
332void
333Knotspec::copy( INREAL *inpt, REAL *outpt )
334{
335 inpt = (INREAL *) (((char *) inpt) + preoffset);
336
337 if( next ) {
338 for( REAL *lpt=outpt+prewidth; outpt != lpt; outpt += poststride ) {
339 next->copy( inpt, outpt );
340 inpt = (INREAL *) (((char *) inpt) + prestride);
341 }
342 } else {
343 for( REAL *lpt=outpt+prewidth; outpt != lpt; outpt += poststride ) {
344 pt_io_copy( outpt, inpt );
345 inpt = (INREAL *) (((char *) inpt) + prestride);
346 }
347 }
348}
349
350/*-----------------------------------------------------------------------------
351 * Knotspec::showpts - print out points before transformation
352 *
353 * Client: Knotspec::select
354 *-----------------------------------------------------------------------------
355 */
356void
357Knotspec::showpts( REAL *outpt )
358{
359 if( next ) {
360 for( REAL *lpt=outpt+prewidth; outpt != lpt; outpt += poststride )
361 next->showpts( outpt );
362 } else {
363 for( REAL *lpt=outpt+prewidth; outpt != lpt; outpt += poststride )
364 dprintf( "show %g %g %g\n", outpt[0], outpt[1], outpt[2] );
365 }
366}
367
368/*-----------------------------------------------------------------------------
369 * Knotspec::factors - precompute scale factors
370 * - overwrites knot vector, actual new knot vector is NOT produced
371 *
372 * Client: Knotspec::select
373 *-----------------------------------------------------------------------------
374 */
375
376void
377Knotspec::factors( void )
378{
379 Knot *mid = (outkend - 1) - order + bend->multi;
380 Knot_ptr fptr = sbegin;
381
382 for( Breakpt *bpt = bend; bpt >= bbegin; bpt-- ) {
383 mid -= bpt->multi; // last knot less than knot to insert
384 int def = bpt->def - 1; // number of knots to insert
385 if( def <= 0 ) continue;
386 Knot kv = bpt->value; // knot to insert
387
388 Knot *kf = (mid-def) + (order-1);
389 for( Knot *kl = kf + def; kl != kf; kl-- ) {
390 Knot *kh, *kt;
391 for( kt=kl, kh=mid; kt != kf; kh--, kt-- )
392 *(fptr++) = (kv - *kh) / (*kt - *kh);
393 *kl = kv;
394 }
395 }
396}
397
398/*-----------------------------------------------------------------------------
399 * Knotspec::insert - convert subobject in direction of kspec into Bezier
400 *
401 * Client: Knotspec::transform
402 *-----------------------------------------------------------------------------
403 */
404
405void
406Knotspec::insert( REAL *p )
407{
408 Knot_ptr fptr = sbegin;
409 REAL *srcpt = p + prewidth - poststride;
410 REAL *dstpt = p + postwidth + postoffset - poststride;
411 Breakpt *bpt = bend;
412
413 for( REAL *pend = srcpt - poststride*bpt->def; srcpt != pend; pend +=poststride ) {
414 REAL *p1 = srcpt;
415 for( REAL *p2 = srcpt-poststride; p2 != pend; p1 = p2, p2 -= poststride ) {
416 pt_oo_sum( p1, p1, p2, *fptr, 1.0-*fptr );
417 fptr++;
418 }
419 }
420
421 for( --bpt; bpt >= bbegin; bpt-- ) {
422
423 for( int multi = bpt->multi; multi > 0; multi-- ) {
424 pt_oo_copy( dstpt, srcpt );
425 dstpt -= poststride;
426 srcpt -= poststride;
427 }
428
429 for( REAL *pend = srcpt - poststride*bpt->def; srcpt != pend; pend +=poststride, dstpt-=poststride ) {
430 pt_oo_copy( dstpt, srcpt );
431 REAL *p1 = srcpt;
432
433 for( REAL *p2 = srcpt-poststride; p2 != pend; p1=p2, p2 -= poststride ) {
434 pt_oo_sum( p1, p1, p2, *fptr, 1.0-*fptr );
435 fptr++;
436 }
437 }
438 }
439}
440
441/*-----------------------------------------------------------------------------
442 * Knotspec::preselect - initialize kspec for processing
443 *
444 * Client: Splinespec::select
445 *-----------------------------------------------------------------------------
446 */
447
448void
449Knotspec::preselect( void )
450{
451 Knot kval;
452
453 /* position klast after last knot of "last" breakpoint */
454 for( klast = inkend - order, kval = *klast; klast != inkend; klast++ )
455 if( ! identical( *klast, kval ) ) break;
456
457 /* position kfirst after last knot of "first" breakpoint */
458 for( kfirst = inkbegin+order-1, kval= *kfirst; kfirst != inkend; kfirst++ )
459 if( ! identical( *kfirst, kval ) ) break;
460
461 /* compute multiplicity of first breakpoint */
462 Knot_ptr k;
463 for( k = kfirst - 1; k >= inkbegin; k-- )
464 if( ! identical( kval, *k ) ) break;
465 k++;
466
467 /* allocate space for breakpoints -
468 use worst case estimate on number of breakpoints */
469
470 bbegin = new Breakpt[(klast - kfirst)+1];
471 /* record multiplicity and value of first breakpoint */
472 bbegin->multi = kfirst - k;
473 bbegin->value = kval;
474 bend = bbegin;
475
476 kleft = kright = kfirst;
477}
478
479
480/*-----------------------------------------------------------------------------
481 * Knotspec::select - Knotspec::select segments and precompute scale factors
482 *
483 * Client: Splinespec::select
484 *-----------------------------------------------------------------------------
485 */
486
487void
488Knotspec::select( void )
489{
490 breakpoints();
491 knots();
492 factors();
493
494 preoffset = kleft - (inkbegin + order);
495 postwidth = (int)((bend - bbegin) * order);
496 prewidth = (int)((outkend - outkbegin) - order);
497 postoffset = (bbegin->def > 1) ? (bbegin->def-1) : 0;
498}
499
500/*-----------------------------------------------------------------------------
501 * Knotspec::breakpoints - compute breakpoints for knotspec
502 *
503 * Client: Knotspec::select
504 *-----------------------------------------------------------------------------
505 */
506
507void
508Knotspec::breakpoints( void )
509{
510 Breakpt *ubpt = bbegin;
511 Breakpt *ubend = bend;
512 long nfactors = 0;
513
514 ubpt->value = ubend->value;
515 ubpt->multi = ubend->multi;
516
517 kleft = kright;
518
519 for( ; kright != klast; kright++ ) {
520 if ( identical(*kright,ubpt->value) ) {
521 (ubpt->multi)++;
522 } else {
523 ubpt->def = (int) (order - ubpt->multi);
524 nfactors += (ubpt->def * (ubpt->def - 1)) / 2;
525 (++ubpt)->value = *kright;
526 ubpt->multi = 1;
527 }
528 }
529 ubpt->def = (int) (order - ubpt->multi);
530 nfactors += (ubpt->def * (ubpt->def - 1)) / 2;
531
532 bend = ubpt;
533
534 if( nfactors ) {
535 sbegin = new Knot[nfactors];
536 } else {
537 sbegin = NULL;
538 }
539}
540
541
542/*-----------------------------------------------------------------------------
543 * Knotspec::knots - copy relevant subsequence of knots into temporary area
544 *
545 * Client: Knotspec::select
546 *-----------------------------------------------------------------------------
547 */
548
549void
550Knotspec::knots( void )
551{
552 Knot_ptr inkpt = kleft - order;
553 Knot_ptr inkend = kright + bend->def;
554
555 /* allocate space for knots and factors */
556 outkbegin = new Knot[inkend-inkpt];
557 Knot_ptr outkpt;
558 for( outkpt = outkbegin; inkpt != inkend; inkpt++, outkpt++ )
559 *outkpt = *inkpt;
560
561 outkend = outkpt;
562}
563
564
565/*-----------------------------------------------------------------------------
566 * Knotspec::transform - convert a spline along a given direction
567 *
568 * Client: Splienspec::transform
569 *-----------------------------------------------------------------------------
570 */
571
572void
573Knotspec::transform( REAL *p )
574{
575 if( next ) {
576 if( this == kspectotrans ) {
577 next->transform( p );
578 } else {
579 if( istransformed ) {
580 p += postoffset;
581 for( REAL *pend = p + postwidth; p != pend; p += poststride )
582 next->transform( p );
583 } else {
584 REAL *pend = p + prewidth;
585 for( ; p != pend; p += poststride )
586 next->transform( p );
587 }
588 }
589 } else {
590 if( this == kspectotrans ) {
591 insert( p );
592 } else {
593 if( istransformed ) {
594 p += postoffset;
595 for( REAL *pend = p + postwidth; p != pend; p += poststride )
596 kspectotrans->insert( p );
597 } else {
598 REAL *pend = p + prewidth;
599 for( ; p != pend; p += poststride )
600 kspectotrans->insert( p );
601 }
602 }
603 }
604}
605
606/*-----------------------------------------------------------------------------
607 * Knotspec::~Knotspec - free space alocated for knotspec
608 *-----------------------------------------------------------------------------
609 */
610
611Knotspec::~Knotspec( void )
612{
613 if( bbegin ) delete[] bbegin;
614 if( sbegin ) delete[] sbegin;
615 if( outkbegin ) delete[] outkbegin;
616}
617
618
619/*-----------------------------------------------------------------------------
620 * pt_io_copy - make internal copy of input cntrl pt. of x coords
621 *-----------------------------------------------------------------------------
622 */
623
624void
625Knotspec::pt_io_copy( REAL *topt, INREAL *frompt )
626{
627 switch( ncoords ) {
628 case 4:
629 topt[3] = (REAL) frompt[3];
630 case 3:
631 topt[2] = (REAL) frompt[2];
632 case 2:
633 topt[1] = (REAL) frompt[1];
634 case 1:
635 topt[0] = (REAL) frompt[0];
636 break;
637 default: {
638 for( int i = 0; i < ncoords; i++ )
639 *topt++ = (REAL) *frompt++;
640 }
641 }
642}
643
644/*-----------------------------------------------------------------------------
645 * pt_oo_copy - make internal copy of internal cntrl pt. of x coords
646 *-----------------------------------------------------------------------------
647 */
648
649void
650Knotspec::pt_oo_copy( REAL *topt, REAL *frompt )
651{
652 switch( ncoords ) {
653 case 4:
654 topt[3] = frompt[3];
655 case 3:
656 topt[2] = frompt[2];
657 case 2:
658 topt[1] = frompt[1];
659 case 1:
660 topt[0] = frompt[0];
661 break;
662 default:
663 memcpy( topt, frompt, ncoords * sizeof( REAL ) );
664 }
665}
666
667/*-----------------------------------------------------------------------------
668 * pt_oo_sum - compute affine combination of internal cntrl pts
669 *-----------------------------------------------------------------------------
670 */
671
672void
673Knotspec::pt_oo_sum( REAL *x, REAL *y, REAL *z, Knot a, Knot b )
674{
675 switch( ncoords ) {
676 case 4:
677 x[3] = a * y[3] + b * z[3];
678 case 3:
679 x[2] = a * y[2] + b * z[2];
680 case 2:
681 x[1] = a * y[1] + b * z[1];
682 case 1:
683 x[0] = a * y[0] + b * z[0];
684 break;
685 default: {
686 for( int i = 0; i < ncoords; i++ )
687 *x++ = a * *y++ + b * *z++;
688 }
689 }
690}
Note: See TracBrowser for help on using the repository browser.