THE TRIMMED NURBS AGE

G. CASCIOLA y AND S. MORIGI z

Abstra t. In this work we report our experien e in the geometri modeling eld, using trimmed
NURBS surfa es and we des ribe how these surfa es an be used both for solid and surfa e modelingpurposes. Our experien e is based on the design and implementation of x model, an intera tive
graphi s system merging new and well-known methods for modeling.
Key words. trimmed NURBS, rendering, surfa e modeling, solid modeling.
AMS subje t lassi ations. 65D17, 65Y25, 65Y20
1. Introdu tion. In geometri modeling there are two fundamental representation s hemes whi h have been su essful and have been in orporated in the mostpopular CAD/CAM software pa kages: solid modeling and surfa e modeling. A solid
modeler represents an obje t unambiguously by des ribing its surfa e boundary andby topologi ally orienting it, so that we an tell, at ea h surfa e point, on whi h side
the solid interior lies. Whereas, a surfa e modeler gives only a geometri al des riptionof the obje t boundary without any topologi al information.
The Non-Uniform Rational B-Splines (NURBS) is a well-established tool for geometri design. NURBS have be ome the de fa to industry standards for the representation, design, and data ex hange of geometri information. NURBS have been
added to several international standards, and many pa kages in lude NURBS as theprimitive for designing simple and free form urves and surfa es. However, the mostuseful NURBS paradigm is limited by the requirement that the surfa es are de ned
over re tangular regions and this leads to topologi al re tangular pat hes. A generalization for an arbitrary topology an be obtained by ollapsing some of the ontrol
mesh edges, but this reates surfa es with ambiguous surfa e normal and degenerated
parametrization.
The introdu tion of a 'trimmed surfa e' data type in the des ription of free form
obje ts or parts of solids has provided greater power and exibility to these representational s hemes. A trimmed surfa e is an ordinary tensor produ t surfa e that has
a restri ted parameter domain, thus over oming the limit of tensor produ t surfa es
de ned over re tangular regions, and allowing for arbitrary domains.
This work is not intended as an exhaustive survey on trimmed NURBS surfa es,
but as a des ription of our experien e of geometri modeling using trimmed NURBS
surfa es. Our experimental testbed is x model, a system developed at the Universityof Bologna [9℄ that is based on trimmed NURBS surfa es, whi h tests new modelingideas and where te hniques an easily be experimented and evaluated. This systemis the result of our experien e of over 10 years in NURBS resear h and development
and it ombines new and well-tried approa hes. In fa t, our work methods are well
expressed by the following senten e from Voelker and Requi ha [44℄:"It is important to do both theoreti al resear h and experimental system building.
They are synergisti , and the ex lusive pursuit of either an lead to sterile theory or
quirky, opaque systems."

 This work was supported by MURST, Co n97, Numeri al Analysis: Methods and Mathemati al
Software.
y Dept. of Mathemati s, University of Bologna, Italy; E-mail: as ioladm.unibo.it.
z Dept. of Mathemati s, University of Bologna, Italy; E-mail: morigidm.unibo.it.
12

G. CASCIOLA AND S.MORIGI

Everyone agrees with this idea, although, in the a ademi world, it is hardly everrewarded.
The paper is stru tured as follows: in Se tion 2 the basi de nitions of trimmed
NURBS surfa e are given. In Se tion 3 we address the problem of representing thetrimmed regions, while Se tion 4 deals with several approa hes used for rendering
trimmed surfa es. In Se tion 5 and 6 we des ribe how these surfa es an be used forsolid and surfa e modeling purposes.
2. Trimmed NURBS surfa es. A trimmed NURBS surfa e an be de ned
by a tensor produ t NURBS surfa e and a set of trimming urves in the parametri
spa e of the surfa e.
A NURBS surfa e of order (m; n) de ned in the parametri domain U  V =[0; 1℄  [0; 1℄, an be represented as:

P =1+ P =1+)= P + P +
=1
=1
n

(

(2.1)

r u; v

H

m

i

K

j

n

H

m

i

( )
( )
wij Ni;n (u)Nj;m (v )wij Pij Ni;n u Nj;m v

Kjwhere wij are the weights, Pij are the ontrol points, and Ni;n (u); Nj;m (v ) are theorder n and m B-splines, respe tively, de ned over the knot ve tors
= (0;    ; 0; un+1 ;    ; un+H ; 1;    ; 1)

| {z }

U| {z }nVn= (0;    ; 0; vm+1 ;    ; vm+K ; 1;    ; 1):| {z }| {z }

mm

Asso iated with a NURBS surfa e is a set of planar, losed, non-interse ting urves
that an be onveniently represented as NURBS urves de ned in the parameterdomain [0; 1℄ by(2.2)

k (t) = (xk (t); yk (t)) =

P =1+
P =1+
pk

Lk

i

pk

i

()
;
()

wi Pi Ni;pk t

Lkk

wi Ni;pk t= 1;    ; M;with the knot ve tors
Tk

= (0;    ; 0; tpk +1 ;    ; tpk +Lk ; 1;    ; 1):| {z }| {z }pk

pk

A trimmed NURBS surfa e is given by the restri tion of r(u; v ) to a subdomain  , of the parametri spa e, named trimmed region. This domain is de ned
as the set of regions on  whose boundaries are spe i ed by the trimming urves

D

U

V

D

U

V

and a given riteria. This riteria allows us to identify the part of the surfa e thatremains when dis arding all the holes de ned by the trimming urves. The trimmed
surfa e boundaries are obtained by mapping the 2D trimming urves onto the surfa e,that is,
( ()

( ));

r xk t ; y k tk= 1;    ; M:

THE TRIMMED NURBS AGE

3

Trimmed NURBS surfa es have been adopted by the CAD/CAM industry, andin luded in graphi s standards. As su h, trimmed NURBS surfa es are provided asmodeling primitives in several geometri modeling software systems, and the rendering of trimmed NURBS surfa es is supported by international standards, su h as
PHIGS+, as well as graphi s programming interfa es, su h as Iris-GL and OpenGL(Sili on Graphi s, In .), Starbase (Hewlett-Pa kard Corp.), and Renderman (Pixar).
Trimmed surfa es are essential for the modeling of non-regular boundary obje ts,
generated by trimming away part of the re tangular pat h. Trimming pat hes also
play a fundamental role in the boundary des ription of solid models where the trimmed
surfa es an give a omplete representation of the boundary of a s ulptured solid
primitive by means of the union of surfa es restri ted to suitable domains. They are
the result of Boolean operations on solid obje ts bounded by NURBS surfa es [17℄.
3. Representing of trimmed NURBS surfa es. We fo us now on the problem of representing the trimmed region D, providing three di erent representations
that de ne the same domain D.
De nition 1: handedness rule of trimming
The urves k (t) are onsidered all properly oriented and joined to form a N < M
numbers of outer or inner loops. Outer loops are oriented ounter- lo kwise, whereas
inner loops are oriented lo kwise. The domain of the trimmed surfa e is de ned
as the ommon region within the outer boundary ( orresponding to the outer loops)
and outside the inner boundaries ( orresponding to inner loops), in luding boundaryurves [32℄. Figure 3.1a presents an example of trimmed region obtained by this rule;
the area that is part of the trimmed region is shaded.
De nition 2: winding rule of trimming
The urves k (t) are onsidered all properly joined to form N < M losed loops(see Figure 3.1b). The set of ontours divides the supporting surfa e into an inneror retained region and an outer or dis arded region based on the odd-winding rule.
A ording to this rule, the region of the surfa e that is en losed by an even numberof loops is trimmed out [29℄.
De nition 3: 2D CSG tree
The trimmed domain is represented by the 2D equivalent of a CSG (Constru tive
Solid Geometry) tree [5℄, whi h, like its 3D ounterpart, is a olle tion of half-spa es
and Boolean operation symbols [17, 5℄. Ea h leaf of the CSG tree stru ture is anembedded non-interse ting losed urve. Curves at the same level are disjoint to ea hother.
The trimmed region that is kept an be determined by lassifying a single point.
Conventions an be assumed to onsider alternate levels of the tree to be outer andinner loops, starting from an inner/outer top level. In Figure 3.1 the 2D CSG tree
representing the trimmed region illustrated in Figure3.1a is shown with the top levelset to be outer.
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 to build a 2D CSG tree T for a given trimmed region forms a union of islands(Ri ), and subtra ts from ea h island all of its lakes (Sij ):T=[ ( \( [
Li

I

i

=1

Ri

j

=1

Sij

));

4

G. CASCIOLA AND S.MORIGI

where I is the number of islands and Li is the number of the lakes Sij hildren of
island i.
Another approa h for representing a trimmed surfa e is based on the idea ofde omposing the domain D of the parameter spa e using a set of planar subregions,whose union de nes the entire domain D (see Figure 3.1d). This approa h does notfollow an intuitive idea of trimming out the part of the entire pat h bounded by thetrimming urves, that is preserved somehow in the previous de nitions, but it allows
us to manage a set of surfa es, de ned on an irregular domain, that do not ontain any
trimming urves. This an represent an advantage during the evaluation/rendering
phase, as well as in the mesh generation phase, be ause it allows for a representationof a trimmed tensor produ t pat h as a olle tion of untrimmed pat hes. In [22℄the authors onsider this approa h by de ning a trimmed surfa e as the union of aset of planar, ruled (four-sided) subregions, addressing the problem of data ex hange
between systems. More generally, this approa h an be applied using S-pat hes [28,45℄. S-pat hes are rational generalizations of Bezier-surfa es that admit any numberof boundary urves.
c2
c3

c1

c4

(a)

C1

(b)

C2

C3

C4
()

(d)

Fig. 3.1. Example of trimmed region obtained by: (a) de nition 1, (b) de nition 2, ( ) de nition 3, and by untrimmed regions approa h (d).

4. Rendering of trimmed NURBS surfa es. This se tion deals with the
problem of visualizing the trimmed NURBS surfa es. As we know, the visualiza-

THE TRIMMED NURBS AGE

5tion algorithms di er in rendering quality with a omputational ost that in reases
as the quality improves. A modeling system needs both medium/low-level quality
algorithms, allowing for real-time visualization (su h as depth ueing, hidden-lineor z-bu er), and high quality algorithms for a realisti nal rendering (su h as raytra ing).
Medium/low-level quality algorithms use a pie ewise planar approximation (tessellation or triangulation) of the trimmed surfa e within a given toleran e. Afterthe triangulation phase a surfa e an be rendered in real time using the triangle
rendering apabilities ommon in urrent graphi s systems. Several algorithms havebeen developed in the past to obtain a triangulation of a trimmed NURBS surfa e[26, 32, 35, 40, 29℄. These methods are parametrization dependent and use the same
toleran e to polygonize the trimming urves and to triangulate the surfa e. Only
Piegl and Tiller in [33℄ present an algorithm, whi h is not parametrization dependent,
that solves the problem with di erent toleran es for the trimming urves and the surfa e. The triangulation algorithm implemented in x model was inspired by the latter
proposal and onsists in the following steps:
 grid surfa e; a re tangular grid in the entire domain is reated adaptively.
By splitting ea h re tangular into two triangles, we obtain a pie ewise linear
approximation of the surfa e. The goal is to approximate urved regions using
more triangles than for the at regions, while ensuring that the approximation
satis es the requirements of a given toleran e [1℄;
 polygonize trimming urves; onsists in obtaining a pie ewise linear approximation of the trimming urves within a given toleran e.
 merge trimming polygon and re tangular grid; given a re tangle in the grid of
the parameter domain, along with its status and a set of trimming polygons,
the goal is to ompute a set of losed polygons that bound the trimmed
domain lying inside the given re tangle.
 triangulating domain polygons; this problem has been solved in a simple andheuristi way. Our approa h distinguishes two ases: the points on the re tangular grid may or may not be onse utive polygon verti es. In the rst
ase, the triangles open fanwise from one of the grid points; in the se ond
ase, where two grid points are opposite, the triangles form a seam.

Fig. 4.1. Rendering of trimmed NURBS sphere with a hidden-line algorithm; a triangulationof the trimmed domain (left), the rendered trimmed surfa e (right).

6

G. CASCIOLA AND S.MORIGI. Rendering of trimmed NURBS sphere with a ray-tra ing algorithm.

Fig. 4.2

Figure 4.1 illustrates an example of a trimmed NURBS sphere rendered by ahidden-line algorithm obtained using x model.
High quality rendering algorithms use an exa t representation. The history, theory and apabilities of ray-tra ing algorithms are well known and do umented [20℄.
The basi problems in ray-tra ing trimmed NURBS surfa es are the following: ray/pat h interse tion
 determining if the interse tion points belong to a trimmed pat h.
If the trimming is aused by a Boolean operation involving solid geometri models,the latter step an be performed using onventional CSG methods [37℄. Our x model
system manages boundary representations for solids by using trimmed surfa es andtherefore the se ond step determines wether an interse tion point lies inside or outside
a trimmed region using a 2D PMC (Point Membership Classi ation) algorithm (seese tion 5).
Solutions to the ray/pat h interse tion problem an be ategorized as being basedon subdivision, numeri al or hybrid te hniques. Subdivision approa hes are des ribedby Whitted [46℄, Rogers [36℄ and Woodward [47℄. These algorithms are based on the
onvex-hull properties of NURBS surfa es. If the ray does not interse t the onvexhull of the ontrol points, it does not interse t the pat h. By re ursively subdividing
the pat h and he king onvex-hulls, the interse tion points an be omputed at alinear onvergent rate amounting to a binary sear h. Whitted's algorithm operates inthree dimensions, whereas Rogers and Woodward map the problem in two dimensions.
Numeri al solutions of the ray/pat h interse tion problem in lude those developed by Toth [43℄, Sweeny and Bartels [42℄ and Joy and Bhetanabhotla [24℄. Toth's
algorithm is based on interval Newton iterations. It works robustly on any parametri surfa e for whi h bounds onto the surfa e and its rst derivative an be obtained.
Sweeny and Bartels proposed re ning the ontrol mesh using the Oslo algorithm [15℄until the mesh losely approximates the surfa e. The ray interse tion is then omputed
by interse ting the ontrol mesh with the ray, and using that interse tion point as astarting point for Newton iteration. Joy and Bhetanabhotla's algorithm uses quasi
Newton optimization to apture the point/s on the pat h nearest the ray, in luding
the interse tion points.
By hybrid solutions, we refer to Bezier lipping [31℄. This algorithm uses the
onvex-hull property in a more powerful manner, by determining parameter ranges
whi h guarantee that they do not in lude points of interse tion. Bezier lipping has the

7

THE TRIMMED NURBS AGE

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.
From a numeri al point of view all these methods nd the ray/pat h interse tions
by solving a non-linear system of equations. The above methods are global andwhen several solutions o ur, they split the problem. The only one whi h uses alo al onvergen e method after applying an initial global lo alization step is Toth's
algorithm. However, the lo alization step is very expensive from a omputational
point of view, as well as the fa t that, in the ase of near solutions in the parametri
domain this lo alization step an fail, requiring the appli ation of a binary subdivision
method of the fun tion.
In our system we implemented rst the Toth's proposal, then Bezier lipping andre ently we added a new algorithm following one of our ideas. This new approa h wasalled "Toth speed". It is a ombination of the Toth and Bezier lipping algorithms
that outperforms their performan es [30, 41℄. 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 the Toth algorithm is for ed
to use binary subdivision, our method uses Bezier lipping.
All these algorithms are in luded in the system and an be ompared on omplex
ray tra ed s enes. Note that a ray-tra ing algorithm exploits a ertain number of
optimization te hniques in order to speed up performan e, su h as subdividing a 3Ds ene in voxels, subdividing the NURBS surfa e in rational Bezier pat hes, further
subdividing ea h rational Bezier pat h until a given at toleran e is rea hed [19℄.
These optimizations an improve a ray/pat h interse tion in di erent ways.
The optimizations mentioned in the ase of trimmed surfa es, introdu e a new
problem: the subdivision of a pat h implies the rede nition of the trimmed domain.
The solution to this problem may be more or less omplex, depending on the type ofrepresentation used for the trimmed region.
Figure 4.2 shows an example of a trimmed NURBS sphere rendered by a raytra ing algorithm obtained by x model .
5. Solid modeling. Following the B-rep (Boundary representation) of a solid,
we an de ne as 'primitive solid' any solid that has, as its boundary, a single surfa ethat is simply losed in order to separate the spa e into two parts, one of whi h will
be en losed. A ording to onvention, the boundary surfa e must be parametrized
in su h a way that the surfa 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 diÆ ulties
posed by Boolean ombinations of free form obje ts have been over ome through theuse of trimmed surfa es.
The boundary of a solid obje t S is de ned as follows
(5.1)

[ ( )
=
k

bS

i

=1

ri D iwhere Di is the trimmed region asso iated with the surfa e ri . A primitive solid isthen de ned by k = 1 and D1 = U  V . The boundary of the solid S is a losed
surfa e.
Given two solids A and B , respe tively de ned by their boundary surfa es, theBoolean operation problem onsists in determining the boundaries of the solids A B ,

S

8

T ,

G. CASCIOLA AND S.MORIGIB A B starting from bA and bB . We will refer to this pro ess as the set operation
algorithm.
The boundary of the resulting solid is given by the equations known as the boundary formula [34℄:

A

(5.2)

(
b(A
b(A

b A

S ) = ( T ) S( T )T ) = ( T ) S( T )T ) S( T )
)=(
B

bA

B

bB

A

B

bA

iB

bB

iA

B

bA

B

bB

iA

where iX and X represent, respe tively, the interior and the omplement of the solid.
The trimmed pat hes of the resulting solid are the same as those of bA and bB ,ex ept for the portion of the pat hes that have been trimmed away (see Figure 5.1).
X

Fig. 5.1. Solid modeling; trimmed domains for the solid
nger disk in Fig.5.2; the ylinderpart of the solid (left), the disk part of the solid (right).

Fig. 5.2. Solid modeling; primitive solids to ompose thenger disk by di eren e (left), theresulting s ene (right).

In [5℄ and [6℄, a set operation algorithm is given, that operates on solids modelledwith trimmed pat hes. In [17℄, the trimmed pat h is represented by a dual represen-THE TRIMMED NURBS AGE

9tation, i.e. the trimmed pat h is given both by an impli it surfa e and a parametri
pat h, and a basi theory is presented for a set operation algorithm, whi h operates
on the dual representation. In [7℄ the proposal in [5℄ is taken up, adapted for NURBS
surfa es and implemented in the x model system. A omplete des ription and implementation of a set operation algorithm is te hni ally omplex. The basi idea in[7℄ onsists in avoiding the interse tions between trimmed pat hes by onsidering theinterse tions between the pat hes over the whole domain. After this, the trimmed
regions (2D CSG tree) resulting from the interse tion between the trimmed regions of
the solids and the trimmed regions obtained by the pat h/pat h interse tion operations, are determined. In the following, we will give a brief des ription of untrimmed
surfa e/surfa e interse tion (SSI), 2D and 3D PMC and 2D urve/ urve interse tion
(CCI), whi h represent the basi steps involved in this pro ess.
5.1. SSI. The methods available for interse ting pat hes an be divided into two
ategories: urve following and subdivision. Firstly, the urve following method nds
some points of interse tion. Then, the points on the interse tion urve are dete ted
using a numeri al method [1, 2℄. This method is espe ially useful for pro essing
singular ases of interse tion [3℄. The subdivision method divides the problem into
smaller problems by approximating the pat h into simpler linear or quadrati subpat hes [23, 6℄. The pat hes are interse ted, resulting in urves that are then re ned byanother numeri al method. A modi ed version proposed in [1℄ has been implemented
in the x model system [8℄. Here, the balan e between robustness and eÆ ien y, a
problem for SSI algorithms, is solved by a "little tri k". The four main steps are thefollowing: Adaptive mesh generation; this onsists in the approximation of ea h of thesurfa es using an adaptive grid of isoparametri urves, approximated bypie ewise linear urves within a given toleran e. From this grid we easily
obtain a surfa e triangulation;
 Initial interse tion point generation; the interse tions between the grid segments of a surfa e and the triangles of the other surfa e are determined inorder to obtain at least one starting point for ea h interse tion urve;
 Following an interse tion urve; with an initial point on the interse tion
urve, we move along the urve by steps. To do this, rst of all we nd an
estimate for the next point on the interse tion urve, and then we evaluate
an exa t interse tion within a given toleran e; Sorting; nally, the urve interse tion segments found in the pre eding step
are linked together in order to obtain omplete interse tion urves.
5.2. 2D and 3D PMC. Point Membership Classi
ation is a fun tion thattakes, as its input, a point P and a losed set S, and whi h returns one of threepossible out omes: P is inside S, P is on the boundary of S, 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, a single 3D point is lassi ed withrespe 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 of thetree. A single 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 ray with theboundary of the set determines the membership status of the point. An even numberof 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

10

G. CASCIOLA AND S.MORIGI

polygons or urved boundaries. In the ase of urved boundaries all the roots in theparametri interval [0,1℄ of the s alar NURBS fun tion resulting from the ray/ urveinterse tion must be found. To solve this problem the methods in [21, 27, 4, 31℄
are explored and ompared [41℄. In the 3D ase, the boundary onsists of trimmed
pat hes, and a ray/pat h method is required (see se tion 4).
5.3. CCI. This problem an either be ta kled geometri ally, that is, using subdivision te hniques for the urves, that exploit the onvex-hull property of the NURBS
urves [27, 25, 38℄, or numeri ally. The latter is done either by nding all the zerosof the fun tion resulting from the system, when a urve has been impli itized [39℄(this is pro tably appli able only for low degree urves), or by nding the zeros of theve tor fun tion in two variables (2D surfa e), obtained from the di eren e between
the urves [16℄. The problem of nding the zeros of a 2D surfa e an be solved using
the same methods as those used to determine the ray/pat h interse tions, (see se tion
4).
Figure 5.2 shows an example of solid modelling generated by the x model system.
6. Surfa e modeling. The re nement te hnique for spline surfa es is a wellknown tool used to represent a surfa e de ned by a ner ontrol mesh with thefeature that ea h single ontrol point will have a more lo al e e t on the surfa e.
This allows us to model small pat hes and to modify their shape without a e tingthe rest. This idea led to the de nition of Hierar hi al Spline Surfa es (HSS) [18℄,proposed in 1988 by Forsey and Bartels, enabling a surfa e to be re ned and details
added, using a hierar hy, whose levels orrespond to the varying levels of re nement of
the surfa e pat hes. This te hnique enables us to restri t the in uen e of re nement
to the relevant parts of the surfa e.
Our paper illustrates how the x model system uses trimmed NURBS surfa es
to represent HSS and enables modeling to be arried out with these surfa es. For
this purpose re tangular trimmed NURBS surfa es are de ned. They onsists ina parti ular lass of trimmed surfa e, whose trimmed away regions are de ned as
re tangular in the parametri domain.
We an represent an HSS as a NURBS surfa e r and a set of regions Di as follows:

[( )
n

i

=1

r Di

where ea h region Di represents the ith level of detail of an HSS and is de ned byDi= Ai 1Ai

with

0 = U  V;

A

Ai

=

[^
mi

j

S

=1

Aij

and where A^ij = [uaj ; ubj ℄  [v j ; vdj ℄ represents the j th re tangular trimmed region
at level i, and is a subset of Ai 1 . Note that ni=1 Di = U  V .
The modeling phase, by adding or editing details, onsists in rst sele ting there tangular pat h on the surfa e to be modi ed, then determining the orresponding
re tangular subdomain and trimming it so that the domain be omes restri ted tothe hosen pat h, whi h now a ts as an autonomous and untrimmed surfa e. The
appropriate re nement is arried out and the ontrol points that an be moved without
altering their order of ontinuity with the original surfa e are determined. In the initial
HSS work [18℄, the ontrol points that annot be altered in order to avoid losing theoriginal ontinuity are already learly spe i ed. These form a frame m 1 wide andTHE TRIMMED NURBS AGE

11

1 high in the ontrol mesh, where m and n are the NURBS surfa e orders. Any
hange in position and/or weight of all or only some of the ontrol points within
this frame results in a lo al modi ation of the pat h, while maintaining the original
ontinuity with the rest of the surfa e.
In Figure 6.1 we show an example of HSS modeling using trimmed NURBS.
nFig. 6.1. HSS modeling using trimmed NURBS; on the left three levels of re tangular pat hes
are shown, on the right the modeled surfa e is given.

Furthermore, in order to design multi-sided surfa es, it makes perfe t sense to
onsider a modeling pro edure that trims one surfa e by means of another surfa e,even if no set operation is indi ated. To do this, the x model system allows the user
to model the 2D trimming urves and de ne a 2D CSG tree for a given surfa e.
7. Con lusions and new trends. In this paper we have dis ussed the usefulness of the trimmed NURBS paradigm for modeling.
Trimmed NURBS present at least two diÆ ulties:
 trimming is expensive and prone to numeri al errors; it be omes diÆ ult to maintain smoothness at the seams of the pat hwork,when the model is animated.
Re ently, subdivision surfa es have been onsidered as a way of over oming NURBS
topologi al limitations without mesh degenera y. They do not require trimming, andmodel smoothness is automati ally guaranteed, even in animated models. The idea
is to re ne an irregular/regular mesh, by reating a new mesh that approximates theold one. By repeating this pro ess, a smooth surfa e is formed as the limit of the proess itself. Subdivision algorithms are quite simple, and are generally able to produ equite omplex obje ts, although the basi theoreti al modeling ba kground has yet to
be explored, and e e tive, intuitive user interfa e, designed to exploit the potential of
the representation to the full, requires further development. Although trends in geometri modeling ommunity resear h are moving towards an exhaustive exploration of
the subdivision paradigm, at the moment, trimming modeling still remains the mostomplete and powerful means for free form obje t modeling.

12

G. CASCIOLA AND S.MORIGIREFERENCES[1℄ R.E.Barnhill, G.Farin, M.Jordan, B.R.Piper, Surfa e Surfa e Interse tion, Computer Aided
Geometri Design, 4 (1987), pp. 3{16.
[2℄ R.E.Barnhill and S.N.Kersey, A mar hing method for parametri surfa e/surfa e interse tion,
Computer Aided Geometri Design, 7 (1990), pp. 257{280.
[3℄ C.L.Bajaj, J.E.Ho man, R.E.Lyn h, Tra king surfa e interse tion, Computer Aided Geometri
Design, 5 (1988), pp. 285{307.
[4℄ R.Brent, Algorithm for minimization without derivatives, Prenti e-Hall, 1973.
[5℄ M.S. Casale, Free-form solid modeling with trimmed surfa e pat hes, IEEE Computer Graphi s& Appli ations, Jan. (1987), pp. 33{43.
[6℄ M.S. Casale and J.E.Bobrow, A set operation algorithm for s ulptured solids modeled withtrimmed pat hes, Computer Aided Geometri Design, 6 (1989), pp. 235{247.
[7℄ G.Cas iola and B.Quaquarelli, Primitive solide, operazioni Booleane e NURBS, Pro eedingsof ICO-GRAPHICS'90, Milano, (1990).
[8℄ G.Cas iola and S.Morigi, Il problema SSI nella modellazione solida on super i NURBS, Atti
dell'A ademia delle S ienze dell'Istituto di Bologna, serie V, n.6, (1995).
[9℄ G.Cas iola and S.Morigi, x model: an aCADemi system, Pro eedings of Co n.97, Ferrara,
January 19-21, (2000).
[10℄ G.Cas iola, x model: a system to model and render NURBS urves and surfa es User's Guide(1999), http://www.dm.unibo.it/ as iola/html/x model.html[11℄ G.Cas iola, x urv: the 2D modeller User's Guide (1999),
http://www.dm.unibo.it/ as iola/html/x model.html[12℄ G.Cas iola, x surf: the 3D modeller User's Guide (1999),
http://www.dm.unibo.it/ as iola/html/x model.html[13℄ G.Cas iola, x bool: the obje t omposer User's Guide (1999),
http://www.dm.unibo.it/ as iola/html/x model.html[14℄ G.Cas iola, x rayt: the s ene des riptor User's Guide (1999),
http://www.dm.unibo.it/ as iola/html/x model.html[15℄ E.Cohen, T.Ly he, R.F.Riesenfeld, Dis rete B-splines and subdivision te hniques in omputeraided geometri design and omputer graphi s, Computer Graphi s and Image Pro essing,
14 (1980), pp. 87{111.
[16℄ T.Dokken, Finding interse tions of B-splines represented geometries using re ursive subdivision
te hniques, Computer Aided Geometri Design, 2 (1985), pp. 189{195.
[17℄ 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.
[18℄ D.R.Forsey and R.H.Bartels, Hierar hi al B-spline re nement, Pro eeding SIGGRAPH'88,(1988). In Computer Graphi s, 22 (1988), pp 205{212.
[19℄ A.Fujimoto, T. Tanaka, and K. Iwata, ARTS: a elerated ray-tra ing system, IEEE Comp.
Graphi s and Appl., Apr. (1986), pp. 16{26.
[20℄ A.Glassner ed., Introdu tion to ray tra ing, A ademi Press, 1989.
[21℄ A.Grandine, Computing zeroes of spline fun tions, Computer-Aided Geometri Design, 6(1989), pp 129{136.
[22℄ B.Hamann, P.-Y. Tsai, A tessellation algorithm for the representation of trimmed NURBS
surfa es with arbitrary trimming urves, Computer-Aided Design, 28 (1996), pp. 461{472.
[23℄ E.G.Houghton, R.F.Emnett, J.D.Fa tor, C.L.Sabharwal, Implementation of a divide-andonquer method for interse tion of parametri surfa es, in R.E.Barnhill, W.Boehem, eds.
Surfa es in Computer Aided Geometri Design (1984), North-Holland, Amsterdam.
[24℄ K.Joy, M.Bhetanabhotla, Ray tra ing parametri pat hes using numeri al te hniques andray oheren e, Pro eeding of SIGGRAPH'86, (1986). In Computer Graphi s, 20 (1986),
pp.279{285.
[25℄ P.A.Koparkar and S.P.Mudur, A new all of algorithms for the pro essing of parametri urves,
Computer-Aided Design, 15 (1983), pp 35{46.
[26℄ S.Kumar and D.Mano ha, EÆ ient rendering of trimmed NURBS surfa es, Computer-Aided
Design, 27 (1995), pp. 509{521.
[27℄ J.M.Lane, R.F.Riesenfeld, A theoreti al development for the omputer generation and displayof pie ewise polynomial surfa es, IEEE Transa tion on PAMI, 2 (1980), pp.35{46.
[28℄ C.T.Loop and T.D.DeRose, A multisided generalization of Bezier surfa es, ACM Transa tion
on Graphi s, 8 (1989), pp.204{234.
[29℄ W.L.Luken, Tessellation of trimmed NURBS surfa es, Computer Aided Geometri Design, 13(1996), pp 163{177.
[30℄ M.Marini, D.Grilli, Un algoritmo di ray-tra ing per super i spline razionali trimmate, MasterTHE TRIMMED NURBS AGE

13

Thesis in Compuer S ien e, University of Bologna, (1995).
[31℄ T.Nishita, T.W.Sederberg and M. Kakimoto, Ray tra ing trimmed rational surfa e pat hes,
ACM Computer Graphi s, 24 (1990), pp. 337{345.
[32℄ L.A.Piegl and A.M.Ri hard, Tessellating trimmed NURBS surfa es, Computer-Aided Design,
27 (1995), pp. 16{26.
[33℄ L.A.Piegl and W. Tiller, Geometry-based triangulation of trimmed NURBS surfa es,
Computer-Aided Design, 30 (1998), pp. 11{18.
[34℄ A.A.G.Requi ha, Mathemati al models of rigid solids, Te h. Memo. 28, Produ tion Automation
Proje t, University of Ro hester, (1977).
[35℄ A.Ro kwood, K.Heaton and T.Davis, Real time rendering of trimmed surfa es, Pro eeding of
SIGGRAPH'89, (1989). In Computer Graphi s, 23 (1989), pp. 107{116.
[36℄ D.Rogers, Pro edural elements for omputer graphi s, M Graw-Hill, 1985.
[37℄ S.Roth, Ray asting for solid modeling, Computer Graphi s and Image Pro essing, 18 (1982),
pp. 109{144.
[38℄ T.W.Sederberg and T.Nishita, Curve interse tion using Bezier- lipping, Computer-Aided Design, 24 (1990), pp. 538{549.
[39℄ T.W.Sederberg and Parry, Comparison on three urve interse tion algorithm, Computer-Aided
Design, 18 (1986), pp 58{63.
[40℄ X.Sheng and B.E.Hirs h, Triangulation of trimmed surfa es in parametri spa e, ComputerAided Design, 24 (1992), pp. 437{444.
[41℄ 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).
[42℄ M.Sweeney and R.Bartels, Ray tra ing free-form B-spline surfa es, IEEE Computer Graphi s& Appli ations, 6 (1986) pp.41{49.
[43℄ D.Toth, On ray tra ing parametri surfa es, Pro eeding of SIGGRAPH'85, (1985). In Computer Graphi s, 19 (1985) pp.171{179.
[44℄ H.B.Voel ker, A.G.Requi ha, Resear h in solid modelling at the University of Ro hester: 197287, in Fundamental developments of Computer-Aided Geometri Modeling, L.A.Piegl ed.,London, A ademi Press 1993.
[45℄ J.Warren, Creating multisided rational Bezier surfa es using base points, ACM Transa tion on
Graphi s, 11 (1992) pp.127{139.
[46℄ T.Whitted, An improved illumination model for shaded display, Communi ation ACM, 23(1980), pp. 96{102.
[47℄ C.Woodward, Ray tra ing parametri surfa es by subdivision in viewing plane, in W.Strasser
and H.-P.Seidel, eds. Theory and Pra ti e of Geometri Modeling, Springer Verlag (1989),
pp.273{290.