Ann. Univ. Ferrara - Sez. VII - S . Mat.
Supplemento al Vol. XLV, 1-0 (2000)

x model: an aCADemi system ( )G. CASCIOLA( ) - S. MORIGI( )x model e un sistema CAD realizzato e utilizzabile in ambito a ademi o. E'
omposto da quattro pa hetti: un modellatore 2D, un modellatore 3D, un ompositore di oggetti e un pa hetto per la resa realisti a di s ene; questi sottosistemi
sono in ostante evoluzione. Il sistema riassume le nostre ompetenze ed esperienze
nella modellazione geometri a e sulle urve e super i NURBS a quisite in oltre
die i anni di ri er a. x model e i suoi sottosistemi sono stati progettati per essere
un laboratorio di ri er a e di didatti a, per sperimentare e imparare; e un ambiente ideale per sviluppare, mettere a punto e onfrontare metodi ed algoritmi dellamodellazione geometri a e della gra a.

Sunto -

x model is a CAD system realized and usable in an a ademi environment.
It integrates four pa kages: a 2D and a 3D modeller, an obje t omposer and arealisti s ene renderer; these subsystems an be regarded as being in onstantevolution i.e. a ontinuous work in progress. The system summarises our knowledge
and experien e in geometri modelling and NURBS urves and surfa es a quired
over ten years of resear h. x model and its subsystems were designed to represent a
resear h and tea hing laboratory to experiment and learn; it is an ideal environment
to develop, perfe t and ompare methods and algorithms in geometri modellingand graphi visualization.

Abstra t -1. { Introdu tion
x model is an intera tive graphi s system based on NURBS (Non Uniform
Rational B-Splines) with the power of a professional CAD (Computer Aided
Design) system, but realized and usable in an a ademi environment.
x model was designed to experiment and evaluate new and well-known methods for modelling and graphi s visualization. The system has been developed and( )This work was supported by MURST, Co n97, Numeri al Analysis: Methods and Mathemati al Software.
( )Indirizzo dell'autore: Department of Mathemati s, University of Bologna, P.zza di Porta
S.Donato 5, Bologna, Italy. as ioladm.unibo.it( )Indirizzo dell'autore: Department of Mathemati s, University of Bologna, P.zza di Porta
S.Donato 5, Bologna, Italy. morigidm.unibo.it.

2g.

as iola - s. morigi

grown with the ontribution of many graduates and undergraduates in mathemati s and omputer s ien e. Thus the system has been adopted in many
university ourses in geometri modelling and omputer graphi s as a laboratory to experiment and learn. One of the edu ational pe uliarities of x model
making it di erent from a ommer ial system whi h uses a high level design
philosophy, is that it assumes the users are familiar with the mathemati s of therepresentations used in the modelling system and let them intera t with every
single operator or parameter governing the shape of the obje t he/she has inmind. As a onsequen e, we expe t the user to be a resear her or a student.
x model integrates four pa kages: a 2D and a 3D free form modeller, an obje t omposer and a realisti s ene renderer. They over the main steps in themodelling and rendering pro ess. These subsystems an be regarded as being inonstant evolution, i.e. a ontinuous work in progress.
The following se tions do not intend to be exhaustive in this des ription of
the wide variety of operators and algorithms for NURBS geometri modelling
and rendering. They fo us on those new and well-known methods that are
implemented and experimented in x model. Moreover, we will not go into detailabout the mathemati s or algorithms; rather the reader will be referred to an
extensive bibliography for more detailed information.
Se tion 2 des ribes the requirements of the x model system. In Se tion 3
some basi de nitions about the modelling primitives involved in the system aregiven; Se tion 4 onsiders some geometri tools that are fundamental for the
more omplex modelling te hniques des ribed in Se tion 5. Se tion 6 deals withthe des ription of a virtual s ene. Finally the rendering methods implemented
in x model are presented in Se tion 7.

2. { x model requirements
The x model fun tional stru ture, in Figure 1, shows how the four mainintera tive graphi subsystems are integrated:

 x urv: performs the modelling of 2D NURBS urves [21℄; x surf: performs the modelling of 3D NURBS urves and surfa es [22℄; x bool: performs boolean operations on solids [23℄; x rayt: performs the des ription and rendering of modelled s enes by a
ray-tra ing algorithm [24℄.

The ellipses represent x model input/output data. The arrows indi ate the dataow, while the re tangular blo ks represent the main subsystems whi h are totally independent of one another. The dashed ar separates the modelling part(left) from the rendering part (right).

x model: an aCADemi

3system

XCSURF

texturescurves2d
curves3d
XCCURVsurfaces

XCRAYT

objectsmodelsXCBOOL
Figure 1: x model fun tional s heme

XCMODEL(control panel)

XCCURVXCSURFXCBOOLXCSSI

XCRAYTXHRAYT/HRAYTXCDBEXFRAMEDESCRIPTOR

TRIM

MATRIXXMOVIEXTOOLS
Xlib
XPM

Figure 2: x model system ar hite ture4g.

as iola - s. morigi

At the present time, the x model system runs on UNIX platforms su h as
Sun SPARC (Solaris), SGI (Irix), and Intel (Linux), but we expe t problems tobe minimal under other environments. The system is a olle tion of modules
and libraries entirely implemented in C ANSI programming language.
Figure 2 shows the x model system ar hite ture. The graphi al user interfa eof the environment is realized using the xtools library [28℄, built on the top of
Xlib, the lowest level library of the XWindow System. The graphi i ons in
the user interfa e make use of the XPM (XPixMap) library whi h allows us
to deal with pixmaps. Together with the xtools library, other three libraries
have been implemented in the system: the MATRIX library [25℄, for ve tor
and matrix omputation, the des riptor library [26℄, for s ene setting, and thetrim library [27℄ for the visualization of trimmed NURBS surfa es in real time.
The s ene des riptor and rendering x rayt pa kage makes use of two modules:
xhrayt/hrayt for ray-tra ing and xframe for visualizing the rendered s ene. The
solid omposer x bool module makes use of two independent subsystems: x ssi,
for surfa e/surfa e interse tion and x dbe, a onversion tool for trimmed surfa es.
Animation is managed by xmovie tool [24℄ that allows for the visualization ofimages and image sequen es. The x model software pa kage is available [20℄ anda freely distributed version (x model ver. 1.0) as well as user's guides, data,
models and images, an be downloaded from the web page:
http://www.dm.unibo.it/ as iola/html/x model.html

3. { x model modelling primitives
This se tion provides some basi de nitions of the NURBS modelling primitive on whi h x model is based. The system assumes NURBS as the uniqueanoni al form for modelling.
To de ne rational B-splines we make use of homogeneous oordinates. If
P = (x; y; z ) is a point in 3D Eu lidean spa e, we denote a orresponding pointin 4D homogeneous spa e by P w = (wx; wy; wz; w), where w > 0. A B-spline
urve of order p in homogeneous spa e an be de ned by the equation+X
P N (t)

p
w

(t) =

i

L

=1

w
i

i;p

where Pw
are the ontrol points in homogeneous spa e,i
T = (t1 ;    ; tp ; tp+1 ;    ; tp+L ; tp+L+1 ;    ; t2p+L )| {z }
p

|

{z
p

}

x model: an aCADemi

5systemis a nonde reasing sequen e of real numbers alled knots, and Ni;p (t) are theorder p B-splines de ned over the knot ve tor T . The NURBS urve (t) asso iated with w (t) is obtained by the proje tion of w (t) into a 3D spa e, that is, bydividing the rst three oordinates of ea h point by its homogeneous oordinate,thus obtaining the following de nition:

P + w P N (t) X+
P R (t);(t) = P=1+=
=1 w N (t)
p

L

i

i

p

i

p

L

i

=1

i;p

L

j

j

j;p

with

i

i;p

P =1+w Nw N(t) (t)Ri;p (t) =

i

p

i;p

L

j

j

j;p

rational basis fun tions. Proje tions of NURBS surfa es of order (m; n) are
obtained analogouslyr (u; v) =+ X+
X
P N (u)N (v)

n

w

i

H m

K

w
ij

=1 =1

i;n

j;m

j

or, equivalently,

P =1+ P =1+ w P N (u)N (v) X+ X+
P R ; (u; v)r(u; v) = P + P +==1=1 w N (u)N (v)
n

H

m

i

K

ij

j

n
i

H

m

ij

i;n

j;m

n

H m

i

=1 =1

K

j

ij

Ri;n;j;m (u; v ) =

i;n

j;m

K

ij

i;n j;mj

P + Pw N+ w(u)NN ((uv))N (v)
n
i

H

=1

ij

i;n

m

K

j

j;m

=1

ij

i;n

j;m

where wij > 0 are the weights, Pij are the ontrol points,
U = (u1 ;    ; un ; un+1 ;    ; un+H ; un+H +1 ;    ; u2n+H );| {z }
n

|

{z
n

}

V = (v1 ;    ; vm ; vm+1 ;    ; vm+K ; vm+K +1 ;    ; v2m+K ):| {z }
m

|

{z
m

}

are nonde reasing sequen es of knots, and Ni;n (u); Nj;m (v ) are the order n andm B-splines, respe tively, de ned over the knot ve tors U and V .
For a detailed dis ussion of the properties of NURBS urves and surfa es werefer the reader to [66℄.
One of the main reasons for the hoi e of NURBS for x model is their wide
range of expression. A detail dis ussion of the widespread a eptan e and popularity of NURBS in CAD/CAM and graphi s systems is given in [62℄.
x model has general hara teristi s, whi h is unusual for ommer ial CAD
systems. For example, x model allows the user to set the urve (surfa e) order6g.

as iola - s. morigi

up to a value of ten. As a result the algorithms implemented are as general
as possible. x model provides some prede ned knot ve tors su h as "equally
spa ed", "uniform" (the interior knots are equally spa ed and the exteriors oin ide), "periodi ", " hord length" [35℄, but also "manually", where the user sets
any knot position and multipli ity. x model manages ollapsed ontrol points andthe relative degenerate parametrizations. The rational urves and surfa es are
omputed via non-rational urves and then by proje tion; a spline is omputedby its B-splines representation, applying the well known re urren e relation provided by Cox-de Boor [11, 33℄.
The most useful NURBS paradigm is limited by the requirement that thesurfa es are de ned over re tangular regions and this leads to topologi al re tangular pat hes. This limit of NURBS surfa es is over ome by the trimmed
NURBS, that is NURBS surfa es de ned on arbitrary restri ted parametri domains. A trimmed NURBS surfa e an be de ned by a NURBS surfa e and aset of trimming urves in the parametri spa e of the surfa e. This set of planar, losed, non-interse ting urves an be onveniently represented as NURBS
urves, whi h are simply redu ed to a losed polygonal when the degree is equal
to 1.
A trimmed NURBS surfa e is given by the restri tion of r(u; v ) to a subdomain D  U  V of the parametri spa e, named trimmed region. This domain
D is de ned as the set of regions on U  V whose boundaries are spe i ed bytrimming urves. This allows us to identify the part of the surfa e that remains
when dis arding all the holes de ned by the trimming urves.
In x model the trimmed domain is represented by a 2D CSG tree equivalent
to the CSG tree presented in [36, 13℄, but di erently represented. Ea h nodeof the CSG tree stru ture is an embedded non-interse ting losed urve thatde nes a limited region built starting from the 2D tree. Regions at the samelevel are disjoint to ea h other. At alternate levels these regions are ombinedusing union and di eren e boolean operators. The trimmed region looks like a
set of islands and lakes, where the islands represent part of the trimmed region,
while the lakes are the holes in it. The algorithm used, forms a union of islands(Ri ), and subtra ts from ea h island all of its lakes (Sij ) starting from a 2D tree:D=[ (R \( [ S ));
Li

I

i

=1

i

j

=1

ij

where I is the number of islands and Li is the number of the lakes Sij hildren of
island i. The trimmed region that is obtained an be determined by lassifying
a single point. Conventions an be assumed to onsider alternate levels of thetree to be island and lake regions, starting from an island/lake top level.
Another approa h implemented in x model for representing a trimmed domain D is based on the idea of de omposing U  V D using a list of planar
subregions, whose union de nes the entire omplementary domain U  V D,x model: an aCADemi

system7

thus allowing the user to manage a set of surfa es, de ned on an irregular domain, that does not ontain any trimming urves. This approa h is implemented
as a parti ular ase of a 2D CSG with all rst-level hildren starting from an
island top level.
The representation s heme used in x model for modelling a solid obje t is theso- alled B-rep (Boundary representation). In this s heme a 'primitive solid' isdetermined by its boundary, that onsists of a single losed surfa e, in order toseparate the spa e into two parts, one of whi h will be en losed. A ording toonvention, the boundary surfa e must be parametrized in su h a way that thesurfa e normal ve tor indi ates the area outside the solid. For example, spheres,
ylinders, et . are in luded in this de nition, as well as losed s ulptured solids.
Primitive solids an also be ombined by boolean operations, su h as interse tion,
union and di eren e, in order to reate a omplex solid.
The boundary of a solid obje t S is de ned in terms of trimmed surfa es asfollows:bS =[ r (D )
k

i

=1

i

i

where Di is the trimmed region asso iated with the surfa e ri . A primitive solidis then de ned by k = 1 and D1 = U  V . The boundary of the solid S is alosed surfa e.
As a ademi system x model does not provide any ontrol on the topologyof the built obje ts, thus it does not ensure that the solid reated orresponds
to a phisi ally realizable obje t.

4. { Basi geometri tools
In this se tion we present four tools for urves whi h are fundamental in spline
urve and surfa e modelling in general and in x model in parti ular; these areknot-insertion, knot-removal, degree elevation and reparametrization. Note that
all these tools only a e t urve or surfa e representations, while geometri ally
the urves or surfa es remain un hanged.
4.1. { Knot-insertion. { This is the pro ess of expressing a parti ular urve(t) in terms of a related spline representation that has one or more additionalknots. This pro ess is also known as re nement, sin e new knots (s  1) are
inserted into the original knot ve tor T to produ e a proper re nement T .
Then ontrol points Qwi exist su h that
w

p
w

(t) =

X Q N (t):

+ +
L

i

=1

s

w
i

i;p

8

g.

as iola - s. morigi

In 1980, Boehm [8℄ and Cohen et al. [29℄ independently found two di erent
algorithms to ompute the new ontrol points Qwi . EÆ ient algorithms for implementing both the spe ial ase of single knot insertion [8℄ and the general ase[10, 54℄ have been proposed. Performan es are analyzed in [9, 31℄. In x model
this tool is used in: evaluating points and derivatives on urves and surfa es;
 subdividing urves and surfa es (splitting);
 adding ontrol points in order to in rease exibility in shape ontrol (intera tive design and hierar hi al design);

 de omposition of spline urves and surfa es into their onstituent (Bezier)polynomial pie es; onverting a periodi knot ve tor into a uniform one; merging two or more knot ve tors in order to obtain a set of urves whi h
are de ned on a ommon knot ve tor (see se tion 5);

 obtaining polygon (polyhedral) approximations to urves (surfa es) by rening knot ve tors; this makes the ontrol polygon (net) onverge to theurve (surfa e).

4.2. { Knot-removal. { This is the reverse pro ess of knot insertion. We an
say that, given a knot ve tor T , a knot t is removable if w (t) has a pre ise representation in the B-spline basis N i;p (t) de ned over the knot ve tor T withoutt. A knot-removal algorithm must determine if a knot is removable and how
many times (s  1), then ompute the new ontrol points Qwi su h that the newurve representation is
p
w

(t) =

X Q N (t):

+

L

i

=1

s

w
i

i;p

Details an be found in [75℄. In x model knot-removal is used to obtain the mostompa t representation of the urve/surfa e in: adjusting knot ve tor after ontrol point insertion/displa ement; joining spline urves together to form omposite urves.

x model: an aCADemi

system9

4.3. { Degree elevation. { This tool allows us to represent a spline urve w (t)as a urve with an elevated degree s > p 1:
w

(t) =

XQN

+1+

s

i

=1

L

w
i

i;s

+1 (t):

EÆ ient but mathemati ally ompli ated methods to ompute the new ontrol
points Qwi are given by Prautzs h in [68℄, by Cohen et al. in [30, 32℄ and by
Prautzs h and Piper [69℄. The algorithm provided by Prautzs h and Piper isthe most eÆ ient for the general ase, but Cohen et al. also give simple andeÆ ient algorithms for low-degrees, su h as linear to quadrati and quadrati to
ubi . All these algorithms raise the degree by 1. In 1994 Piegl and Tiller [64℄presented another algorithm whi h is mathemati ally simpler, and ompetitive
with that given in [69℄, parti ularly in the ase where the degree is to be raisedby more than 1. In x model degree elevation is used to: make ompatible se tion urves in the "surfa e from urves" modellingte hnique (see se tion 5.3);

 obtain "bi-p-i " parametri surfa es (where e.g. p=4 for bi ubi ) in sur-fa es from urves modelling te hniques (see se tion 5.3), where the orderof the pro le and traje tory urves may be required to be the same.

4.4. { Reparametrization. { Let (t) be a parametri urve on t 2 [a; b℄ andassume that t = f (s) is a s alar-valued fun tion on s 2 [ ; d℄ satisfying: f 0(s) > 0 for all s 2 [ ; d℄, a = f ( ) and b = f (d),the omposition of (t) and f (s), given by (s) = (f (s)) is alled a reparametrization of (t). (s) is geometri ally the same urve as (t), but parametri ally they
are di erent.
In x model we onsider only reparametrization fun tions that keep the urve a
NURBS. In parti ular, for a rational linear reparametrization fun tion in [2℄ and[52℄, an expli it expression for the reparametrized NURBS urve is given.
The most ommon and useful parametrization is the ar length. Su h a parametrization is unfortunately almost never possible for NURBS, unless for straight lines[37℄. Therefore x model o ers several reparametrization te hniques that best t
the ar length parametrization [18℄.
A reparametrization an be required be ause of the e e ts that the hange of
weights and ontrol points have on the parametrization of the urve. Moreover,any numeri al method, or simply the rendering pro edure, is a e ted by their
parti ular parametrization in terms of omputational omplexity and numeri alstability.

10

g.

as iola - s. morigi

5. { Modelling
x model o ers a set of design tools for modelling urves, surfa es and solid
obje ts that an be lassi ed into four lasses: basi onstru tors, shape modiers, surfa es from urves and obje t omposer. Basi onstru tors build models
intera tively or automati ally, together with the possibility of using, as initial
shapes, lassi al primitive obje ts, su h as spheres, torus, boxes or more omplex
obje ts like revolution surfa es. Intera tive modelling tools for shape modi ation aim to modify the shape of an existing obje t. In addition, we an de neoperators on urves to reate surfa es. Finally, boolean operators are available
for building omplex obje ts.
Ea h of these tools an be used alone or in pipeline fashion in order to get
the nal geometri model ready to be rendered.

5.1. { Basi onstru tors. { In this se tion we deal with the apabilitiesof x model alled "shape approximation" and "data tting" to reate 2D or 3D
shapes ab initio.

- Shape approximation -B-splines provide a geometri ally intuitive basis, one in whi h the shape of theurve or surfa e has a predi table and omprehensible relationship to the oeÆients (i.e. ontrol points). This is a spe ial approximation s heme named shape
approximation, whi h is extremely attra tive for geometri design. A ording tothis approximation s heme, an individual ontrol point only has a lo al e e t,
and does not a e t a design beyond the lo alized region of in uen e. In x model,
design tools are provided to give 2D points for a ontrol polygon (for urves) and3D points for a ontrol net (for surfa es) intera tively and a set of parameters tode ne the urve or surfa e shape approximation of the ontrol polygon or net.

- Data tting -In this paragraph we deal with tting, i.e. the onstru tion of NURBS urves
and surfa es whi h t a rather arbitrary set of geometri data, su h as points
and derivative ve tors. We distinguish two types of tting, interpolation andapproximation by the least square te hnique. There are several mathemati al
methods for interpolating or approximating a single-valued fun tion from a given
set of values, but their appli ation to urve tting sometimes results in a urvethat is very di erent from what the designer intended. Input to a tting problem
onsists of geometri data, su h as points and derivatives. Output is a NURBS
urve or surfa e, i.e. ontrol points, knots and weights. Furthermore, either theorder p (or (m; n) for surfa es) must be the input or the algorithm must sele t
an appropriate order. Very little has been published on setting the weights inthe tting pro ess. Most often, all the weights are simply set to 1. Finally, there
are many methods for hoosing the knots, most of them heuristi .
The tting algorithms an be global or lo al. With a global algorithm, a systemof equations is set up and resolved. Sin e the given data onsists only of points

x model: an aCADemi

11

systemand derivatives, and the ontrol points are the only unknowns (order, knots andweights have been presele ted or pre omputed), the system is linear and hen eeasy to solve. Lo al algorithms are more geometri in nature, onstru ting theurve or surfa e segment-wise, using only lo al data at ea h step. These algorithms are usually omputationally less expensive than global methods and andeal with lo al data anomalies better; however, a hieving desired levels of global
ontinuity is not a standard matter and lo al methods often result in multiple
internal knots. In what follows we present the global and lo al methods for urve
and surfa e interpolation and approximation implemented in x model.

 Global urve interpolation to point and derivative data

Let Qli ; i = 1; : : : ; n and l = 0; : : : ; li , be the interpolation points andderivative ve tors; we want to interpolate these data with a p-th order
NURBS urve. Note that if li = 0 8i, then we have a Lagrange interpolation, otherwise we have an Hermite interpolation. If we assign aparameter value ti , to ea h Q0i , sele t an appropriate knot ve tor T andsele t a positive weight ve tor W , we an set up the (p + L)  (p + L)
system of linear equations+X
P R (t ) = Q i = 1; : : : ; n l = 0; : : : ; l

p

P

i

L

=1

i

l
i;p

i

l
i

i

with L = ni=1 (li + 1) p. The ontrol points Pi are the unknowns. The
problem of hoosing the ti , T and W remains, and their hoi e a e ts
the shape and parametrization of the urve. x model provides four methods of hoosing the ti : hord length, uniform, entripetal and exponential[51, 55℄. The knot ve tor T is omputed in a heuristi way, so that the
S hoenberg-Whitney and Karlin-Ziegler onditions are satis ed in orderto have a unique solution for the interpolation problem [58℄. The positive
weight ve tor W hara terizes a rational interpolation from a non-rationalby setting manually or equal weights respe tively. In the ase of Hermite
interpolation, derivative ve tors have to be spe i ed as input data. For the
more ommon ase of rst derivative ve tors, x model provides the Akima
te hnique [1℄ for an automati derivative omputation. In the ubi ase
there is the possibility of interpolating the given points with a periodi
urve or with a rational C 1 urve. In the latter ase the NURBS weights
an be used as tension parameters [44℄.

 Global surfa e interpolation to point data
Given a set of (n + H )  (m + K ) data points Q

k = 1; : : : ; n + H andkll = 1; : : : ; m + K , we want to onstru t a non rational (m; n)-order 3D

12

g.

as iola - s. morigi

spline surfa e interpolating these points, i.e.
(1)

+
+ X
X
P N (u )N (v ) = Q :

n

H m

K

i

=1 =1

ij

i;n

k

j;m

l

kl

j

In x model this is a hieved by setting rw (uk ; v l ) = Qwkl , with all weights
equal. Again, the rst thing to do is to ompute reasonable values for the(uk ; v l ) and the knot ve tors U and V . A ommon way is to use one of theprevious methods for urves to ompute parameters ul1 ; : : : ; uln+H for ea hl, and then to obtain ea h uk by averaging a ross all ulk for l = 1; : : : ; m + K[62℄. Using the parameter points omputed, we get the U and V ve tors
in exa tly the same way as with urves. Clearly the equations (1) represent a linear system for the unknowns Pij . However, sin e the surfa e istensor produ t, the Pij an be obtained more simply and eÆ iently as asequen e of urve interpolations. At the moment, x model provides only
bi ubi spline surfa e interpolation.

 Lo al urve interpolation to point and derivative data

Let Qli ; i = 1; : : : ; n and l = 0; 1, be the interpolation points and rst
derivative ve tors given. By lo al urve interpolation we mean a method
whi h onstru ts n polynomials or rational urve segments i (t); i =0; : : : ; n 1, su h that Q0i and Q0i+1 are the end points of i (t). Neighboring segments are joined with some pres ribed level of ontinuity, andthe onstru tion pro eeds segment-wise. x model provides, at the moment,
only a lo al method, whi h interpolates point and rst derivative data witha rational globally C 1 ( ubi over quadrati ). The NURBS weights play
the role of tension parameters and for wi ! 1 8i, the urve onverges
to the polygonal de ned by the interpolation points. It is a NURBS adaptation of an algorithm by Gregory and Sarfraz [44℄.

 Weighted and onstrained least square urve tting

Let Qi ; i = 1; : : : ; n, be the points to be approximated. If we assign
a parameter value ti , to ea h Qi , hoose a urve order p, an appropriate
knot ve tor T , and sele t a positive NURBS weight ve tor W , we an set
up the n  (p + L) overdetermined system of linear equations+X
P R (t ) = Q i = 1; : : : ; n:

p

L

i

=1

i

i;p

i

i

Most often, all these weights are simply set to 1. Indeed, for approximation,
there is little reason to do otherwise.
Optionally the rst and last given points an be onstrained (pre isely

x model: an aCADemi

system13

interpolated) or the urve an be onstrained to be losed and periodi .
We also allow a positive weight to be assigned to ea h un onstrained item.
In reasing a weight in reases the tightness of the approximation to that
item, whereas de reasing the weight looses the approximation to that item.
Noti e that these weights have nothing to do with weights in the NURBS
sense. x model also provides a method to approximate the weighted andonstrained data in the least-squares sense.
5.2. { Shape modi ers. { The purpose of some methods implemented in
x model is to provide tools whi h allow a user to intera tively make lo al modi ation to an existing NURBS urve or surfa e. A NURBS urve or surfa e isde ned by its ontrol points, weights, knots and orders; modifying one or moreof these parameters, an a e t and hange the shape of the urve or surfa e [66℄.
Sin e x model is an edu ational system and assumes the user are experimenting and learning, it allows the user to modify all these parameters intera tively.
Generally CAD systems on the market do not allow the user to modify su hparameters; they apply many prede ned shape operators to the urve or surfa e. Following [60, 61℄, x model implements some of these operators, su h as
onstraining a urve point to pass over a given point by one ontrol point repositioning, by one weight modi ations or by two weight modi ation, warping,attening, et . The result of applying a transformation to the whole spline
urve or surfa e, gives rise to a spline de ned by the transformed ontrol points
together with the original knot ve tor and urve (surfa e) order. Formally+X
AP N (t)

p
w
A

(t) =

i

L

=1

w
i

i;p

is the result of applying the transformation matrix A to the urve w (t). In
the ase where A is an aÆne transformation, this strategy produ es exa tly thesame urve (surfa e) whi h would have been produ ed if A had been applied toea h point on the urve (surfa e).
In 1988 Forsey and Bartels [39℄ proposed the Hierar hi al Spline Surfa es(HSS) enabling a surfa e to be re ned and detail added, using a hierar hy, whoselevels orrespond to the di erent levels of re nement of the surfa e pat hes. This
proposal enables us to restri t the in uen e of re nement to the relevant partof the surfa e. In x model we implemented the HSS idea by using the trimmed
NURBS surfa es power and pre isely de ning a "re tangular trimmed NURBS
surfa es hierar hy" [19℄.
5.3. { Surfa e from urves. { As intera tive te hniques for the s ulpturing of surfa e shapes on a two dimensional display involve obvious diÆ ulties,
additional tools are available for the designer to model the desired surfa e using
operators on urves. The most frequently used te hniques, su h as skinning,
sweeping, and swinging, are adopted in x model.

14

g.

as iola - s. morigi

NURBS skinning is a spe ial surfa e interpolation te hnique by whi h anordered set of NURBS urves ( alled se tion urves) is interpolated to forma NURBS surfa e. The se tion urves have to be made ompatible, i.e. same
degree and knot ve tor, by means of the basi geometri tools des ribed in se tion
4. If this is the ase they will also have the same number of ontrol points, andthey an be de ned as follows:
w
j

(u) =

+
X
Q N (u); j = 1; : : : ; m + K:

n

i

H

w
ij

=1

i;n

For ea h index i, their ontrol verti es Qwij ; j = 1; : : : ; m + K; in v dire tion
are interpolated using global urve interpolation te hnique in homogeneous spa e(see se tion 5.1) obtaining the following urveswi(v ) =

X+ P N (v); i = 1; : : : ; n + H;

m

j

K

w
ij

=1

j;m

that pass through Qwij at ertain ui values.
The ontrol polygons of the interpolation urves together form a ontrol meshthat de nes a skinned surfa e:r(u; v) =
w

+ X
+
X
P N (u)N (v):

n

i

H m

K

=1 =1

w
ij

i;n

j;m

j

The above skinning algorithm is a fairly straightforward generalization to rational urves of the skinning algorithm for polynomial B-spline urves des ribed in[78, 79℄, whi h has the desirable property that the reated surfa e is as smoothas the se tion urves. Now, as for the rational ase, the algorithm works in
the homogeneous spa e, even if, for example, a rational urve is C 1 in 3D, its
asso iated urve in 4D may be only C 0 , that is, the algorithm an produ e a
C 0 surfa e in 4D whose asso iated surfa e in 3D will exhibit dis ontinuities.
This smoothness problem is addressed in [47℄ and [62℄. The positioning of these tion urves in the spa e is another riti al problem dis ussed in [79℄: unevenly
positioned se tion urves an lead to unsatisfa tory surfa e shapes.
NURBS sweeping te hnique is a spe ial ase of skinning that uses a onstantse tion urve and sweeps it along another urve ( alled spine or traje tory urve)
in order to reate a NURBS surfa e. The positioning points for sweeping an
be hosen as the spine knot points (ui ); i = 1; : : : ; m + K . Automati ally thesystem will pla e the se tion urves in the 3D spa e in su h a way that thepositioning points are mat hed and ea h 2D plane on whi h ea h se tion urvelies is aligned to the normal of the spine at that point. Then the se tion urves
an be arbitrarily rotated on their planes until the desired position is obtained.

x model: an aCADemi

15systemThe swept surfa e will also interpolate the spine urve whenever the referen epoint with whi h the se tion urve is mat hed to the spine knot points lies on
the se tion urve itself.
A revolution surfa e is generated using a NURBS urve whi h lies in theplane. A full revolution surfa e is obtained by revolving this urve 2 aroundthe z axis. The resulting surfa e has the formr(u; v) =X9 X+ P R (u)R (v):
m

i

K

ij

=1 =1

i;

4

j;m

j

NURBS swinging is a generalization of the revolution te hnique, where thetraje tory urve is not ne essarily ir ular. Given a pro le urve P(u) in thex; z plane

P(u) =+X
P R (u)

p

L

i

=1

i

i;p

with Pi = (Pxi ; 0; Pzi )T , and a traje tory urve T(v ) in the x; y plane+X
T R (v)
T(v) =
q

L

j

=1

j

j;q

with Tj = (Txj ; Tyj ; 0)T , swinging the pro le around the z axis along the traje tory urve yields the surfa e:r(u; v) = [sP (u)T (v); sP (u)T (v); P (u)℄
x

x

x

y

z

with ontrol points and weights:

Q = [sP i T j ; sP i T j ; P i ℄
ij

x

x

x

y

z

T

wij = wi  wj ;where s is an arbitrary s aling fa tor.

5.4. { Obje t omposer. { Solid onstru tions an be a omplished byombining, using a set of boolean operations, two or more solids; this pro ess
is known as the set operation algorithm. Consider, for example, the two solids
A and B , respe tively de ned by their boundary surfa es. The boundaries ofthe solids A B , A B , A B are determined starting from bA and bB , andtrimming away the portion of the pat hes that does not belong to the resulting
solid. The boundary of the resulting solid is given by the equations known as
the boundary formula [70℄:

S

T

S
T

b(A B ) = (bA
b(A B ) = (bA
b(A B ) = (bA

T B) S(bB T A)
T S T iA)T iBB)) S((bBT
bB iA)

16g.

as iola - s. morigi

where iX and X represent, respe tively, the interior and the omplement of thesolid X .
In [13℄ and [14℄, a set operation algorithm is given, that operates on solids
modelled with trimmed pat hes. The proposal given in [14℄ is onsidered andadapted for NURBS surfa es in [15℄ and implemented in the x model system.
The basi idea in [14℄ onsists in avoiding the interse tions between trimmed
pat hes by onsidering the interse tions between the pat hes over the wholedomain. In this way, we an then determine the resulting trimmed regions (2D
CSG tree) from the interse tion between the trimmed regions of the solids andthe trimmed regions obtained by the pat h/pat h interse tion operations.
A detailed des ription of the set operation algorithm implemented in the system is te hni ally omplex. In the following, we will give a brief des ription of
the basi steps involved in this pro ess: the untrimmed surfa e/surfa e interse tion (SSI), the 2D and 3D Point Membership Classi ation (PMC), and the 2D
urve/ urve interse tion (CCI).

- SSI -The SSI pro edure implemented in x model is a modi ed version of the proposal
given in [3℄; details an be found in [17℄. The method exploits the advantageso ered by the two most frequently used SSI approa hes, urve following andsubdivision, in order to get a good balan e between robustness and eÆ ien y.
The urve following method begins by nding some points of interse tion.
Then, the interse tion urve is followed using a numeri al method [3, 4℄. The
subdivision method divides the problem into smaller problems by approximating
the pat h into simpler linear or quadrati sub-pat hes [48, 14℄. The pat hes
are interse ted, resulting in urves that are then re ned by another numeri al
method. The proposed modi ed algorithm roughly pro eeds through the fourmain steps that follow:

 Adaptive mesh generation; approximate adaptively ea h of the surfa es bya grid of isoparametri urves, approximated by pie ewise linear urves
within a given toleran e. From this grid we easily obtain a surfa e triangulation;

 Initial interse tion point generation; ompute the interse tions between thegrid segments of a surfa e and the triangles of the other surfa e, in orderto obtain at least one starting point for ea h interse tion urve;

 Following an interse tion urve; starting from an initial point on the interse tion urve, move along the urve by steps. This is done by rst
nding an estimate for the next point on the interse tion urve, and thenevaluating an exa t interse tion within a given toleran e; Sorting; nally, link together the urve interse tion segments found in the
pre eding step in order to obtain lose interse tion urves.

x model: an aCADemi

system17- 2D and 3D PMC -PMC is a fun tion that takes, as its input, a point P and a losed set S, andreturns one of three possible out omes: P is inside S, P is on the boundary ofS, or P is outside S. The set operation algorithm makes extensive use of PMC
in both two and three dimensions. During the onstru tion of the 2D CSG tree
resulting from a boolean operation, a single 3D point is lassi ed with respe t
to the opposing solid. The result will be used for further 2D lassi ations inorder to build a olle tion of half-spa es whi h, ultimately, be ome the leaves ofthe 2D CSG tree [13, 14℄.
A ommon on ept is used for both 2D and 3D lassi ation: a ray is extended from the point to be lassi ed, and the number of interse tions of the raywith the boundary of the set determines the membership status of the point.
An even number of interse tions means that the point is outside the set,
while an odd number implies that the point is inside.
While the on ept is the same, its implementation is very di erent for two or
three dimensions. In the 2D ase, the ray is interse ted with polygons or urved
boundaries. In the 3D ase, the boundary onsists of trimmed pat hes, and a
ray/pat h method is required [57℄.

- CCI -

This problem an either be ta kled geometri ally, that is, using subdivision te hniques for the urves, thus exploiting the onvex-hull property of the NURBS
urves [50, 72℄, or numeri ally. In x model the geometri approa h is implemented.

6. { S ene des ription
On e the geometri models of the obje ts have been reated, the modellingof a realisti s ene is based on positioning, orientating the obje ts in the s ene,hara terizing their materials, and de ning the light sour es illuminating them.
This an be realized by applying an illumination model and some textures.
An illumination model is designed to determine the intensity of light re e tedby an observer's eye at ea h point (pixel) in an image. In a global illumination model the intensity of the light re e ted from a point to the observer isdetermined by the light that rea hes a point by re e tion from, or transmission
through, other obje ts in the s ene, as well as the light in ident from any lightsour es.
The illumination model implemented in the system is based on the global illumination model proposed by Whitted [77℄. This model derives from the te hniques
introdu ed previously by Phong [12℄ and Blinn [7℄.
The two traditional methods of texturing implemented in x model are texture
maps and pro edural textures. By a texture mapping, an image is mapped onto
an obje t. This map is realized by positioning the obje t to be mapped on

18

g.

as iola - s. morigi

the image spa e and applying an orthogonal proje tion [7, 38℄. A pro edural
texture is an analyti al fun tion de ned in 3D spa e, that is, a fun tion thatassigns some visual properties to every point in the 3D texture spa e. The
result of the appli ation of a pro edural texture on an obje t is given by pla ing
the obje t in the texture spa e.

7. { Rendering
The rendering of NURBS surfa es as well as urves is a very important task
in an intera tive graphi s system, su h as x model. We distinguish between low
and high level rendering quality.
7.1. { Low level or real time rendering. { A low level rendering quality algorithm uses a pie ewise planar approximation of the surfa e in order to produ ereasonable images in a reasonable time. x model provides two strategies: a uniform approximation and an adaptive approximation within a given toleran e.
The adaptive approximation adopted by the system is not the well known re ursive pro edure that subdivides the surfa e until it is " at enough". In fa t thispro edure is very time and spa e onsuming. Instead we have implemented theadaptive mesh generation proposed in [3℄ as the initial step for an SSI method.
This onsists in a surfa e approximation using an adaptive grid of isoparametriurves within a given toleran e.
If the surfa e is trimmed, on e the adaptive mesh for the whole surfa e has
been omputed, we need to merge the trimming urves and the mesh to yield
losed domain polygons and then triangulate them. The triangulation algorithm
implemented in x model was inspired by [63℄ and [67℄. The latter proposal is
not parametrization dependent and pro eeds with di erent toleran es for thetrimming urves and the surfa e. Our implementation di ers in the adaptive
approximation and in the domain polygon triangulation; in this latter ase weadopted a simple but faster heuristi approa h than a Delaunay triangulation.
On e a suitable, planar approximation for the surfa e is obtained, x model provides four di erent low level rendering quality methods:

 a wire frame representation of the grid surfa e;
 a wire frame representation of the grid surfa e following the strategy ofdrawing ea h grid segment with a di erent grey level in a ordan e withthe distan e from the observer (depth ueing);

 a wire frame representation of the grid surfa e following the hidden line
strategy. The implemented hidden line method was derived from [59℄ thenimproved in [53℄. An optimization performan e strategy was proposed in[16℄. This proposal onsists of a quasi exa t hidden line algorithm highly
suitable for a real time visualization.

x model: an aCADemi

system19

 a shading algorithm (Gouraud or Phong) of planar approximation. It

onsists in evaluating the illumination model at various lo ations: on e
per vertex for Gouraud shading, and on e per pixel for Phong shading[12, 38℄.

7.2. { High level or realisti rendering. { High quality rendering algorithms
use an exa t representation. x model provides a ray tra ing algorithm spe ialized
for NURBS surfa es. The basi problem in a ray-tra ing surfa e algorithm is the
ray/pat h interse tion. If the surfa e is trimmed, it follows a step to determine
whether the interse tion point lies inside or outside a trimmed region using a
2D PMC algorithm. In x model three methods for ray/pat h interse tion are
implemented:

 Toth [76℄Toth's algorithm is based on interval Newton iteration. It works robustly
on any parametri surfa e for whi h bounds onto the surfa e and its rst
derivative an be obtained.

 Bezier Clipping [57℄This algorithm uses the onvex-hull property in a powerful manner, bydetermining parameter ranges whi h guarantee that they do not in lude
points of interse tion. Bezier Clipping has the avor of a geometri ally
based interval Newton method, and thus may be ategorized as partly a
subdivision based algorithm and partly a numeri al method.

 Toth speed [56, 74℄

A new approa h, following one of our ideas, was alled Toth speed. It is aombination of the Toth and Bezier Clipping algorithms that outperforms
their performan es. The idea is to redu e the appli ation of the interval
Newton iterations of the Toth method, trying to nd the solution using
a simple Newton, in the knowledge that, if a solution exists, it is unique.
If this fails, an interval Newton iteration is applied. Moreover, when theToth algorithm is for ed to use binary subdivision, our method uses Bezier
Clipping.

Our ray tra ing implementation exploits a ertain number of optimization
te hniques [42℄ in order to speed up performan e, su h as subdividing a 3D s ene
into a uniform grid of voxels [41℄, subdividing the NURBS surfa es in rational
Bezier pat hes, further subdividing ea h rational Bezier pat h until a given attoleran e is rea hed and introdu ing a se ond level of subdivision of the surfa ebounding boxes [56℄.
In Fig.3, some modelling examples produ ed using x model system by undergraduates in Computer S ien e at the University of Bologna, are shown.

20

g.

as iola - s. morigi

Figure 3: S enes modelled and rendered with the x model system

x model: an aCADemi

system21

8. { A knowledgements
The system has developed over several years, and thanks are due to a numberof people who made signi ant and minor ontributions to its development andtesting.

REFERENCES[1℄ I. Akima, A new method of interpolation and smooth urve tting based onlo al pro edures, Journal of ACM, 17 (1970), pp. 589{602.
[2℄ L. Alt, Rational linear reparametrization of NURBS and the blossoming
prin iple, Computer Aided Geometri Design, 10 (1993), pp. 465{467.
[3℄ R.E. Barnhill - G. Farin - M. Jordan - B.R. Piper, Surfa e Surfa eInterse tion, Computer Aided Geometri Design, 4 (1987), pp. 3{16.
[4℄ R.E. Barnhill - S.N. Kersey, A mar hing method for parametri surfa e/surfa e interse tion, Computer Aided Geometri Design, 7 (1990), pp.
257{280.
[5℄ B.A. Barsky - D.P. Greenberg, Determining a set of B-spline ontrol
verti es to generate an interpolation surfa e, Computer Graphi s and Image
Pro essing, 14 (1980), pp. 203{226.
[6℄ R.H. Bartels - J.C. Beatty - B.A. Barsky, An introdu tion to splines
for use in omputer graphi s and geometri modelling, Morgan Kaufman
publishers, (1987).
[7℄ J.F. Blinn - M.E. Newell, Texture and re e tion in omputer generated
images, Communi ation of ACM, 19 (1976), pp. 542{547.
[8℄ W. Boehm, Inserting new knots into B-spline urves, Computer Aided Design, 12 (1980), pp. 199{201.
[9℄ W. Boehm, On the eÆ ien y of knot insertion algorithms, Computer Aided
Geometri Design, 2 (1985) pp. 141{143.
[10℄ W. Boehm - H. Prautzs h, The insertion algorithm, Computer-Aided
Design, 17 (1985), pp. 58{59.
[11℄ C. deBoor, On al ulating with B-splines, Journal of Approximation Theory, 6 (1972), pp. 50{62.
[12℄ Bui-Tuong - Phong, Illumination for omputer generated pi tures, Communi ation of ACM, 18 (1975), pp. 449{455.

22

g.

as iola - s. morigi[13℄ M.S. Casale, Free-form solid modeling with trimmed surfa e pat hes,
IEEE Computer Graphi s & Appli ations, Jan. (1987), pp. 33{43.
[14℄ M.S. Casale - J.E. Bobrow, A set operation algorithm for s ulptured
solids modeled with trimmed pat hes, Computer Aided Geometri Design, 6(1989), pp. 235{247.
[15℄ G. Cas iola - B. Quaquarelli, Primitive solide, operazioni Booleane e
NURBS, Pro eedings of ICO-GRAPHICS'90, (1990).
[16℄ G. Cas iola - S. Morigi, Graphi s in parallel omputation for rendering
3D modelled s enes, Parallel Computing, 21 (1994), pp. 1365{1382.
[17℄ G. Cas iola - S. Morigi, Il problema SSI nella modellazione solida onsuper i NURBS, Atti dell'A ademia delle S ienze dell'Istituto di Bologna,
Serie V (1995), pp. 107{127.
[18℄ G. Cas iola - S. Morigi, Reparametrization of NURBS urves, International Journal Shape Modelling, 2 (1996), pp. 103{116.
[19℄ G. Cas iola - S. Morigi, The trimmed NURBS age, submitted, (1999).
[20℄ G. Cas iola, x model: a system to model and render NURBS urves andsurfa es, User's Guide - Version 1.0, Progetto MURST: "Analisi Numeri a:
Metodi e Software Matemati o", Ferrara (2000)
http://www.dm.unibo.it/ as iola/html/x model.html[21℄ G. Cas iola, x urv: the 2D modeller, User's Guide - Version1.0, Progetto MURST: "Analisi Numeri a: Metodi e Software Matemati o", Ferrara(2000)
http://www.dm.unibo.it/ as iola/html/x model.html[22℄ G. Cas iola, x surf: the 3D modeller, User's Guide - Version 1.0, Progetto MURST: "Analisi Numeri a: Metodi e Software Matemati o", Ferrara(2000)
http://www.dm.unibo.it/ as iola/html/x model.html[23℄ G. Cas iola - G. DeMar o, x bool: the obje t omposer, User's Guide- Version 1.0, Progetto MURST: "Analisi Numeri a: Metodi e Software
Matemati o", Ferrara (2000)
http://www.dm.unibo.it/ as iola/html/x model.html[24℄ G. Cas iola, x rayt: the s ene des riptor, User's Guide - Version 1.0,
Progetto MURST: "Analisi Numeri a: Metodi e Software Matemati o", Ferrara (2000)
http://www.dm.unibo.it/ as iola/html/x model.html

x model: an aCADemi

system23[25℄ G. Cas iola, MATRIX library: Programming Guide - Version 1.0, (1999)
http://www.dm.unibo.it/ as iola/html/x model.html[26℄ G. Cas iola - S. Bonetti, des riptor library: Programming Guide - Version 1.0, (1999) http://www.dm.unibo.it/ as iola/html/x model.html[27℄ G. Cas iola - G. DeMar o, trim library: Programming Guide - Version
1.0, (1999) http://www.dm.unibo.it/ as iola/html/x model.html[28℄ G. Cas iola - S. Bonetti, xtools library: Programming Guide - Version
1.0, (1999) http://www.dm.unibo.it/ as iola/html/x model.html[29℄ E. Cohen - T. Ly he - R.F. Riesenfeld, Dis rete B-splines and subdivision te hniques in omputer-aided geometri design and omputer graphi s,
Computer Graphi s and Image Pro essing, 14 (1980), pp. 87{111.
[30℄ E. Cohen - T. Ly he - L.L. S humaker, Algorithms for degree-raisingof splines, Transa tion On Graphi s, 4 (1985), pp. 171{181.
[31℄ E. Cohen - T. Ly he - K. Morken, Knot line re nement algorithms
for tensor produ t B-splines surfa es, Computer Aided Geometri Design, 2(1985), pp. 133{139.
[32℄ E. Cohen - T. Ly he - L.L. S humaker, Degree raising for splines,
Journal of Approximation Theory, 46 (1986), pp. 170{181.
[33℄ M.G. Cox, The numeri al evaluation of B-splines, J. Inst. Math. Appl.,
10 (1972), pp. 134{149.
[34℄ T. Dokken, Finding interse tions of B-spline represented geometries using re ursive subdivision te hniques, Computer Aided Geometri Design, 2(1985), pp. 189{195.
[35℄ G. Farin, Curves and surfa es for CAGD: a pra ti al guide, A ademi
Press In ., (1993).
[36℄ R.T. Farouki, Trimmed-surfa e algorithms for the evaluation and interrogation of solid boundary representations, IBM J.RES.DEVELOP., 31 (1987),
pp. 314{333.
[37℄ R.T. Farouki - T. Sakkalis, Real rational urves are not 'unit speed',
Computer Aided Geometri Design, 8 (1991), pp. 151{157.
[38℄ J.D. Foley - A. VanDam - S.K. Feiner - J.F. Hughes, Computer
Graphi s prin iples and pra ti e, II Edition, Addison Wesley, (1990).
[39℄ D.R. Forsey - R.H. Bartels, Hierar hi al B-spline re nement, Pro eeding SIGGRAPH'88, In Computer Graphi s, 22 (1988), pp. 205{212.

24

g.

as iola - s. morigi[40℄ R.D. Fuhr - M. Kallay, Monotone linear rational spline interpolation,
Computer Aided Geometri Design, 9 (1992), pp. 313{319.
[41℄ A. Fujimoto - T. Tanaka - K. Iwata, ARTS: a elerated ray-tra ing
system, IEEE Comp. Graphi s and Appl., April (1986), pp. 16{26.
[42℄ A. Glassner ed., Introdu tion to ray tra ing, A ademi Press, (1989).
[43℄ A. Grandine, Computing zeroes of spline fun tions, Computer-Aided Geometri Design, 6 (1989), pp. 129{136.
[44℄ J.A. Gregory - M. Sarfraz, A rational ubi spline with tension, Computer Aided Geometri Design, 7 (1990), pp. 1{13.
[45℄ Ch.M. Hoffmann, Geometri and Solid Modeling. An Introdu tion, Morgan Kaufmann Publishers, (1989).
[46℄ M.E. Hohmeyer - B.A. Barsky, Rational ontinuity: parametri , geometri and frenet frame ontinuity of rational urves, ACM Transa tion on
Computer Graphi s, 8 (1989), pp. 335{359.
[47℄ M.E. Hohmeyer - B.A. Barsky, Skinning rational B-spline urves to
onstru t an interpolatory surfa e, CVGIP: Graphi al Models and Image
Pro essing, 53 (1991), pp. 511{521.
[48℄ E.G. Houghton - R.F. Emnett - J.D. Fa tor - C.L. Sabharwal,
Implementation of a divide-and- onquer method for interse tion of parametri surfa es, in R.E.Barnhill, W.Boehem, eds. Surfa es in Computer Aided
Geometri Design, North-Holland, (1984).
[49℄ P. Lan aster - K. Salkauskas, Curve and surfa e tting, an introdu tion, A ademi Press, (1986).
[50℄ J.M. Lane - R.F. Riesenfeld, A theoreti al development for the omputer
generation and display of pie ewise polynomial surfa es, IEEE Transa tion
on PAMI, 2 (1980), pp. 35{46.
[51℄ E.T.Y. Lee, Choosing nodes in parametri
Aided Design, 21 (1989), pp. 363{370.

urve interpolation, Computer-[52℄ E.T.Y. Lee - M.L. Lu ien, Mobius reparametrization of rational Bsplines, Computer Aided Geometri Design, 8 (1991), pp. 213{215.
[53℄ L. Li, Hidden-line algorithm for urved surfa es, Computer-Aided Design,
20 (1988), pp. 466{470.
[54℄ T. Ly he - K. Morken, Making the Oslo algorithm more eÆ ient, SIAM
J. Numer. Anal., 23 (1986), pp. 663{675.

x model: an aCADemi

system25[55℄ W. MA - J.P. Kruth, Parametrization of randomly measured points forleast square tting of B-spline urves and surfa es, Computer-Aided Design,
27 (1995), pp. 663{675.
[56℄ M. Marini - D. Grilli, Un algoritmo di ray-tra ing per super i spline
razionali trimmate, Master Thesis in Computer S ien e, University of
Bologna, (1995).
[57℄ T. Nishita - T.W. Sederberg - M. Kakimoto, Ray tra ing trimmed
rational surfa e pat hes, ACM Computer Graphi s, 24 (1990), pp. 337{345.
[58℄ G. Nurnberger, Approximation by Spline Fun tions, Springer Verlag,(1989).
[59℄ Y. Ohno, A hidden line elimination method for urved surfa es, ComputerAided Design, 15 (1983), pp. 209{216.
[60℄ L.A. Piegl, Modifying the shape of rational B-splines. Part 1:
Computer-Aided Design, 21 (1989), pp. 509{518.

urves,[61℄ L.A. Piegl, Modifying the shape of rational B-splines. Part 2: surfa es,
Computer-Aided Design, 21 (1989), pp. 538{546.
[62℄ L.A. Piegl, On NURBS: a survey, IEEE Comput. Graph. and Appl., 10(1991), pp. 55{71.
[63℄ L.A. Piegl - A.M. Ri hard, Tessellating trimmed NURBS surfa es,
Computer-Aided Design, 27 (1995), pp. 16{26.
[64℄ L.A. Piegl - W. Tiller, Software-engineering approa h to degree elevation of B-spline urves, Computer-Aided Design, 26 (1994), pp. 17{28.
[65℄ L.A. Piegl - W. Tiller, Algorithm for approximate NURBS skinning,
Computer-Aided Design, 28 (1996), pp. 699{706.
[66℄ L.A. Piegl - W. Tiller, The NURBS book, Springer, (1995).
[67℄ L.A. Piegl - W. Tiller, Geometry-based triangulation of trimmed
NURBS surfa es, Computer-Aided Design, 30 (1998), pp. 11{18.
[68℄ H. Prautzs h, Degree elevation of B-spline urves, Computer Aided Geometri Design, 1 (1984), pp. 193{198.
[69℄ H. Prautzs h - B. Piper, A fast algorithm to raise the degree of splineurves, Computer Aided Geometri Design, 8 (1991), pp. 253{265.
[70℄ A.A.G.Requi ha, Mathemati al models of rigid solids, Te h. Memo. 28,
Produ tion Automation Proje t, University of Ro heste (1977).

26

g.

as iola - s. morigi[71℄ S. Roth, Ray asting for solid modeling, Computer Graphi s and Image
Pro essing, 18 (1982), pp. 109{144.
[72℄ T.W. Sederberg - T. Nishita, Curve interse tion using Bezier- lipping,Computer-Aided Design, 24 (1990), pp. 538{549.
[73℄ T.W. Sederberg - S.R. Parry, Comparison on three urve interse tion
algorithm, Computer-Aided Design, 18 (1986), pp. 58{63.
[74℄ S. Spagna, Analisi, sviluppo e appli azione di metodi di intersezione per
spline razionali, Master Thesis in Compuer S ien e, University of Bologna,(1998).
[75℄ W. Tiller, Knot-removal algorithms for NURBS urves and surfa es,
Computer-Aided Design, 24 (1992), pp. 445{453.
[76℄ D. Toth, On ray tra ing parametri surfa es, Pro eeding of SIGGRAPH'85, In Computer Graphi s, 19 (1985), pp. 171{179.
[77℄ T. Whitted, An improved illumination model for shaded display, Communi ation ACM, 23 (1980), pp. 96{102.
[78℄ C.D. Woodward, Cross-se tional design of B-spline surfa es, Computer& Graphi s, 11 (1987), pp. 193{201.
[79℄ C.D. Woodward, Skinning te hniques for intera tive B-spline surfa e interpolation, Computer-Aided Design, 20 (1988), pp. 441{451.