UNIT

3
NURBS- Basics- curves, lines, arcs, circle and bi
linear surface. Regularized Boolean set
operations - primitive instancing - sweep
representations - boundary representations -
constructive solid Geometry - comparison of
representations - user interface for solid
modeling.
• NURBS (nonuniform rational B-"splines) are almost
exclusively used by CAD/CAM systems as the internal
representation of all geometric entities that these systems
provide.
• NURBS provide a unified approach to formulate and
represent curves and surfaces.
• NURBS provide a convenient design tool to create smooth
curves and surfaces interactively.
• The development of NURBS dates back to the late 1970s
when Boeing developed the Tiger CAD system based on
rational B-splines.
• These splines were developed by integrating the
representations of B-splines with rational Bezier curves.
• In 1983, SDRC released the first NURBS-based commercial
modeler, Geomod.
 NURBS have many advantages.
• Any curve or surface can be formulated using
NURBS.
• NURBS are considered a unified canonical
representation that can define both synthetic
(Bezier, B-splines) and analytic (circles and conics)
curves and surfaces.
• The premise is that they can represent all curve,
surface, and solid entities, allowing unification and
conversion from one CAD system to another via
exchange standards (STEP and IGES).
• Their related algorithms are stable and
accurate.
• They enhance manufacturing and machining
accuracy and speed.
• They are intuitive and flexible to use in design
and geometric modeling.
• NURBS are also invariant under affine and
perspective transformations such as
translation, rotation, and projections.
• NURBS have some problems.
• The definition of simple curves such as arcs,
circles, and conics is verbose; they require more
data to define as NURBS than the traditional
way.
• For example, the traditional definition of a circle
is a center (x, y, z), radius and the circle plane
defined by a normal vector (nx, ny, nz); that is a
total of seven numbers.
• The NURBS definition requires 38 numbers.
• The loss of information on simple shapes is
another problem.
• For example, if a circular cylinder (hole) is represented by a
B-spline, some data on the specific curve type may be lost
unless it is carried along.
• Data, including that the part feature was a cylinder, would
be useful in manufacturing to identify it as a hole to be
drilled or bored rather than a Surface to
be milled.
• The improper use of the extra flexibility that NURBS offer
(such as weights, as we cover later) can produce ill-behaved
NURBS.
• Moreover, some algorithms. such as surface/surface
intersection and inverse-point solution, work better under
the non-NURBS representation.
• Nonetheless, NURBS advantages far outweigh their
disadvantages.
 Basics
• The key to understanding NURBS comes from the
name itself: nonuniform (NU). Rational (R), and
B-splines (BS).
• we need to understand rational and nonuniform.
• A rational curve is defined by the algebraic ratio
of two polynomials while a nonrational curve is
defined by one polynomial.
• Rational curves draw their theories from
projective geometry.
• They are important because of their invariance
under projective transformation, that is, the
perspective shape of arational curve is a rational
curve.
• Rational Bezier curves, rational B-spline curves.
rational conic sections, rational cubics, and
rational surfaces have been formulated.
• The most widely used rational curves are NURBS.
• The formulation of rational curves requires the
introduction of homogeneous space and the
homogeneous [Link] homogeneous space
is four-dimensional (4D) space.
• A point in E3 with coordinates (x, y, z) is represented
in the homogeneous space by the coordinates (x*,
y*, z*, h) where h is a scalar factor. When h = l,we
obtain the point in E3.
• Thus, the homogeneous coordinates of a point in E3
is (x, y, z, 1).
• The relationship between the two types of
coordinates is obtained by normalizing h to 1.
• where Ni,k(u) are the B-spline basis functions
given by Eqs.
• wi are weights associated with the control points,
Pi, of the rational B"-spline curve.
• Each control point has an associated weight, wi
with it.
• These weights serve the same purpose as h in Eq.

• The control point Pi has the homogeneous

coordinates (wixi, wiyi, wizi, wi) in the 4D projective
space, and the coordinates (xi, yi, zi, 1) in the 3D
Euclidean space.
• Ri,k(u) are a generalization of the nonrational basis functions
Ni,k(u).
• If we substitute wi = 1 in the equation and use the partition-of-
unity property of Ni,k(u), Ri,k(u) = Ni,k(u), and the rational curve
becomes nonrational.
• The rational basis functions Ri,k(u) have nearly all the analytic
and geometric properties of their nonrational B-spline
counterparts, Ni,k(u).
• where Bi,k(u) is the Bernstein basis functions of
Bezier curve.
• The generality property that nonrational B-spline
and Bezier curves are special cases of NURBS.
• The main difference between rational and nonrational B-
spline curves is the ability to use wi at each control point
to control the behavior of the rational curves.
• Thus, similar to the knot vector, one can define a
homogeneous coordinate or weight vector W = [w0w1 w2
w3 ... wn]T at the control points P0, P1, P2, P3, . .., Pn of the
rational B-spline curve.
• Each control point, Pi, has a weight, wi, associated with
it.
• The weights are usually positive numbers.
• The choice of the weight vector controls the behavior of
the curve.
• When a curves control points all have the same weight
(usually 1), the curve becomes nonrational.
 The Knot Vector
• The B-spline curve is uniform.
• That means that the knots in the knot vector are evenly
spaced over the range of u with unit separation ( u = 1)
between noncoincident knots.
• Multiple (coincident) knots for certain values of u may
exist.
• Relation (n + k + 1) knots are needed to create a (k - 1)
degree curve defined by (n + 1) control points.
• The nonunifoml B-spline curve uses knots and has a knot
vector expressed as:
• where the number of knots (length of the knot vector)
m = n + k + 1.

• Above equation applies to both uniform and

nonuniform B-splines.
• For the uniform B-spline curve, the knot values of Eq. KV
depend on whether the curve is open (nonperiodic) or
closed(periodic).
• The knot values are equally spaced in the u space by a
unit value, that is, u = 1.
• For example,
• The knot vector [0 0 0 1 2 3 4 4 4]T is uniform
• while the knot vector [0 0 0 1 2 5 6 6 6]T is nonuniform.
• The knot values for a nonuniform B-spline curve
are not uniform (not equally spaced in the u
space), thus the name nonuniform B-splines.
• A common form for the knot vector of nonuniform
B-splines is for the first k knots to be 0 and the last
k to be 1, that is,
• Examples of a uniform knot vector are
KV=[0 0 0 1/3 2/3 1 1 1]T
• KV=[0 0 0 1/4 1/2 3/4 1 1 1]T,
• KV=[0 0 0 0 1/5 2/5 3/5 4/5 1 1 1 1]T,
KV=[0 0 0 1/8 2/8 3/8 4/8 5/8 6/8 7/8 1 1 1]T and
so forth.
• These knot vectors are also known as open knot
vectors because the knot spacing is uniform
along the curve except at the end points
to ensure that the curve interpolates the first and
the last control point.
• In contrast, nonuniform knot vectors have
unequally spaced knot values.
• Knot multiplicity determines the degree of the
segment of the NURBS curve that passes
through the first and the last data points.
• For example, the multiplicity of 3 ensures that a
thlrid-degree B-spline passes through the end
points.
• Multiplicities of 2 and 4 produce second and
fourth degrees, respectively.
 Effect of changing the weight wi
• The weights provide CAD designers with an
effective design tool to control NURBS curves locally.
• Weights are normally chosen to be positive.
• The effect of wi on a NURBS curve is that a higher
(lower) value of wi at control point Pi pulls the curve
closer to (farther away from) Pi as shown in Figure.
• Thus, increasing the
value of wi tightens the
curve or increases the
pull toward Pi.
• Each weight wi affects
the curve in the
parametric interval
defined by
• The movement of the NURBS curve P(u) for a fixed value
of u and a changing value of wi is linear as shown in
Figure .
• Let us assume that point Pwi has a fixed u value. Pwi
moves along a straight line when wi changes as shown in
Figure .
 Three classes of B-spline curves
• Uniform nonrational B-splines.
• Nonuniform, nonrational B-splines. This class is
similar to class 1 , but it uses nonuniform knot
values.
• Uniform rational B-splines. This class is similar to
NURBS but it uses uniform knot values.
• NURBS curves.
 Curves
• To determine the curve order (k), curve degree
(k-1), its number of control points (n + I), the
length of the knot vector (m), the values of the
knots, and the weights at the control points.
• The curve degree, k -1 (or order k) and its
control points (n + 1) are given data.
• The length of the knot vector (m) is determined
by Equ.
• Following steps to develop the NURBS equation of any curve:

1. Find curve order, k. The curve degree is (k-1) and is always

given.
2. Find the number of control points, n + 1. The number of data
points given in the problem is equal to (n + 1).
3. Find the length of the knot vector, m.
4. Calculate the knot values (end and interior) of the knot
vector.
5. Calculate the B-spline basis functions Ni,k(u).
6. Calculate the rational B-spline basis functions Ri,k(u).
7. Find the equation of the NURBS curve.
8. Test the NURBS equation.
 Lines
• A line defined by two end points, P0 and P1 , as
shown in Figure.
• we have k = 2 and n = 1 and so, m = 4.
• The knot vector as KV = [u0 u1 u2 u3]T =[0 0 1 1]T.
• In this case, all the knot values are end values
because m = 4 and k = 2.
• To calculate Ni,k(u) as follows:
 Arcs
• A circular arc is considered part of
a circle.
• It has the same quadratic
equation as a circle
but with a limited angle.
• A NURBS circular arc has Its own
equation.
• The NURBS equation for the right
arc (quarter of a circle) shown in
Figure.
• The arc is defined by three points
P0, P1 , and P2 that have weights
w1, w2, and w3, respectively.
KV = [u0 u1 u2 u3 u4 u5]T
• This data suggests that k = 3, = [0 0 0 1 1 1]T - all the knots
n = 2, and the length of the knot are end knots.
vector m = 6.
• Let us assume a unit arc in the XY coordinate system
shown below. Substituting the (x, y)
coordinates of the control points shown below in Eq.,
the arc equation becomes:

• Above equation satisfies the boundary conditions; at

u = 0, P = P0, and u = 1, P = P2.
 Circles
• A circle defined by a center and a
radius R as shown in Figures . Here,
we develop the NURBS formulation of
a circle with a center at (0, 0) and a
radius R = 1.
• The formulation of a NURBS circle
requires a set of control points that
forms a closed polygon, as shown in
Figures .
• As the forthcoming formulation
shows, a NURBS circle consists of arc
segments that are pieced together.
• The number of segments depends on
the number of the control points used
in the development. Both the Figures
show two cases: eight and five control
points. develop the NURBS equation
for eight points in this section.
• the circle equation becomes:

• Based on Figure, k = 3 (circle is quadratic degree),

n = 8, and m = 12.
• The knot vector as KV = [u0 u1 u2 u3 u4 u5 u6 u7 u8
u9 u10 u11 ]T = [0 0 0 I/7 2/7 3/7 4/7 5/7 6/7 1 1 1]T.
Here, we have six interior knots.
• The pyramid of the basis functions Ni,k(u) is three
stories high as shown in Figure.
• The sum of the two indexes of the last basis function
in each story must equal 11 (n + k).
 UNIT

3
NURBS- Basics- curves, lines, arcs, circle and bi
linear surface. Regularized Boolean
set operations - primitive instancing - sweep
representations - boundary representations -
constructive solid Geometry - comparison of
representations - user interface for solid
modeling.
 Solid Modeling-Introduction
Solid Modeling (Volumetric modeling) techniques begun to develop in the late
1960s and early 1970s.

 It is developed to eliminate all kinds of ambiguities in representation and

manipulations of the objects.

 The completeness of the information contained in a solid model allows

the automatic production of realistic images of a shape.

 The model can also serve as a means of geometric input for finite element
analysis or even manufacturing tasks as the generation of instructions for
numerically controlled machining.

 It produces accurate designs

 It provides complete three dimensional definition. It improves the

quality of the design

 It improves visualization. It has potential for functional automation and

integration.
52
• Are a more complete representation than its surface model.

• Contain geometric data as well as topological information unlike

wireframes or surfaces.

53
Use of Solid Modeling in design and manufacturing increasing due
to

 Reduced computing costs

 Fast computing hardware

 Improved user interface

 Software improvements

 Solid modeling is the solution to automating and integrating

design and manufacturing.

 The complete definition of part shape through solid models is a key

to CIM.

 Solid modeling store more information than wire frame or

surface modelers.
 Geometry and Topology in Solid Models

• The data base for a solid

model should have two types
of information.

• The first is the metric or

geometric data which relate
to the 3D coordinate
positions of the object in
space.
• Second is the connectivity or topological data which relate
objects with each other.

• Both information are necessary, as different shapes can result with

Same geometry- different topology
Different geometry-same topology
 Geometry and Topology in Solid Models

• The geometry is the actual

dimensions that define the entities
of the object.

• The length of lines L1, L2, L3 and

the angles between the lines, and
the radius R and the center P1 of
the half circle.

• Topology is the connectivity of the object entities.

• L1 shares a vertex with L2 and C1 , L2 shares a vertex with L1 and L3,

L3 shares a vertex with L2 and C1, L1 and L3 do not overlap, and P1 lies
outside the object.

56
 UNIT

3
NURBS- Basics- curves, lines, arcs, circle and bi
linear surface. Regularized Boolean set
operations - primitive instancing - sweep
representations - boundary representations -
constructive solid Geometry - comparison of
representations - user interface for solid
modeling.
 Solid Models-Primitives Approach

• Using primitive approach, one can construct the solid model of the object by
dividing it into blocks and cylinders.

58
 Solid Models-Features Approach

• In feature approach the designer can create different cross sections and
extrude them.

59
 Solid Entities
 Primitives (building blocks) are simple basic shapes and are
considered the solid modeling entities which can be combined by a
mathematical set of Boolean operations to create the solid.
The most common primitives are:-
 Block
 Cylinder
 Cone
 Sphere
 Wedge
 Torus

 A primitives requires a set of location data, a set of geometric

data and a set of orientation data.

 Primitives are usually translated or rotated to position and

oriented properly before applying Boolean operations.
60
Various Solid Modeling Primitives

61
Most Common Primitives

62
 Primitives

 Two or more primitives can be combined to form the desired solid.

 The relationships between primitives are achieved via Boolean

operations.

Boolean operations are

 Union

 Intersection

 Difference

63
Boolean Operations of a Block A and Cylinder B

64
65
Solid Modeling using 3D Primitives

66
 UNIT

3
NURBS- Basics- curves, lines, arcs, circle and bi
linear surface. Regularized Boolean set
operations - primitive instancing - sweep
representations - boundary representations -
constructive solid Geometry - comparison of
representations - user interface for solid
modeling.
 Sweep Representation
 Sweeping is based on by moving a point, curve, or a surface along
a given path.

 There are three types of sweep:

 Linear, non linear and hybrid sweeps

 In linear sweep, the path is a linear or circular.

 In nonlinear sweep, the path is a curve.

 Hybrid sweep combines linear and nonlinear sweep.

 Extruded solids are created via linear sweep or translational sweep.

 Solids of revolution can be created by rotational sweep.

 Sweeping is used in B-rep or CSG based modelers.

 Linear Sweep
 Linear sweep can be divided into
translational and rotational sweep.

 In translational sweep, a planar two

dimensional contour can be moved a
given distance in a perpendicular
direction called directrix.

 The contour should be closed, otherwise

invalid solids result.

 In rotational sweep, the contour is rotated

about an axis of rotation by a given
angle.
 Non linear Sweep

 Non linear sweep is similar to linear

sweep. But with the directrix being a
curve .

 In hybrid sweep two contours are swept

in two different directions and the two
resulting swept volumes are glued
together to form the final object.

 Invalid solids may result if the sweeping

direction is not chosen properly.
 UNIT

3
NURBS- Basics- curves, lines, arcs, circle and bi
linear surface. Regularized Boolean set
operations - primitive instancing - sweep
representations - boundary representations -
constructive solid Geometry - comparison of
representations - user interface for solid
modeling.
 Solid Representation
• A solid model of an object is defined
mathematically as a point set S in 3-D
Euclidean space.

• The interior, the boundary and

exterior of the solid is denoted by iS,
bS and cS respectively

• Then the object is represented by the

relation
S  bS  iS
• The universal set W is represented by

W  bS  iS  cS S  kS kS  bS  iS
Where kS is the geometric closer, which implies that the interior of the
solid is geometrically closed by its boundary.
72
 Solid Model-Properties
Rigidity- shape of model is invariant and does not depend on the model location or
orientation in space.

Homogenous Three Dimensionality – boundaries must be in contact with interior.

No isolated or dangling boundaries should be permitted.

Finiteness and Finite Describability – Size of the solid is not infinite and a limited
amount of information can describe the solid.

Closure Under Rigid Motion and Regularized Boolean

Operations –
Manipulation of solids by moving them in space or
changing them via Boolean operations must produce other
valid solids.

Boundary Determinism –
The boundary of a solid must contain the solid and hence
must determine distinctively the interior of the solid.
73
The properties of representation schemes
Domain –
 Class of objects that the scheme can represent or it is the geometric
coverage of the scheme.

Validity –
 Validity of a representation scheme is determined by its range, i.e.,
the set of valid representations or models it can produce.

Completeness or Unambiguousness –
 This properties determines the ability of the scheme to support
analysis and other engineering applications.

Uniqueness –
 Used to determine object equality.

74
 Solid Representation
Representation scheme is defined as a relation that maps a valid point set
into a valid model.

One model produced by the

scheme represents only one
object.

More than one model

represent the object.

One model can represent

more than one object.

75
Positional and permutational nonuniqueness

76
Other properties of representation schemes

Conciseness
 Measure of the size of data a scheme requires to
describe an object.
 The scheme generates compact databases, convenient
to store and efficient to transmit from one system to
another.

Ease of operation
 Determines the user-friendliness of a scheme.

Efficacy
 Measures how accessible a representation is by
downstream applications.
 Good representation schemes should permit the use of a
wide variety of application algorithms for evaluating
various functions.

77
Various representation schemes
The nine solid representation schemes are
 Half-spaces
 Boundary Representation (B-rep)
 Constructive Solid Geometry (CSG)
 Sweeping
 Analytical Solid Modeling (ASM)
 Cell decomposition
 Spatial enumeration
 Octree encoding and
 Primitive instancing

78
 Algorithms

 Representation of solids are built and invoked

via algorithms (processors)

 Algorithm is a procedure that takes certain

input and produces a desired output.

Three types of algorithms

 a: data → rep (algorithm a is defined as
taking data and producing representation) –
these algorithms build, maintain and manage
representations.

 a: rep → data (compute property values - by

taking a representation and producing data)
– application algorithms belong to this type.

 a: rep→rep (take representations and

produce representations) – algorithm that
converts CSG to B-rep.
79
 UNIT

3
NURBS- Basics- curves, lines, arcs, circle and bi
linear surface. Regularized Boolean set
operations - primitive instancing - sweep
representations - boundary representations -
constructive solid Geometry - comparison of
representations - user interface for solid
modeling.
 Boundary Representation (B-rep)
• It is based on the topological notion that a physical
object is bound by a set of faces.

• A boundary model comprised of faces, vertices and

edges linked together.

• Each face is bounded by edges and each edge is

bounded by vertices.

• The database of a B-rep model consists of both the

geometry as well as the topology of the object.

81
• Topology – by Euler operations.
• Geometry- by Euclidean calculations.

82
• Euler operations - to create, manipulate and edit the faces,
edges and vertices.

• Geometry – includes coordinates of vertices, rigid motion

and transformation (translation, rotation) and metric
information (distances, angles, areas, volumes).

• Geometry and topology are interrelated and cannot be

separated.

• The primitives used by the B-rep system are faces, edges

and vertices.

83
 Basic Elements of B-rep

• Primitives are used to create both polyhedral as well as

curved objects.
• A polyhedral object consists of planar faces (or sides)
connected by straight (linear) edges, which in turn are
connected at the vertices.
• A curved object is like a polyhedron but with curved faces
and edges

Classification of Polyhedral objects

 Simple Polyhedron (no inner loops, holes or handles)
 Polyhedrons with inner loops.
 Polyhedrons that have holes but not through holes.
 Polyhedrons with handles or genus

84
Types of polyhedral objects

85
86
 Object Faces Edges Vertices Inner Bodies Genus
No (F) (E) (V) Loop (B) (G)
(L)
4 1 6 12 8 0 1 0

2 5 8 5 0 1 0

3 10 24 16 0 1 0

4 16 36 24 2 1 0

5 11 24 16 1 1 0

6 12 24 16 0 2 0

5 7 10 24 16 2 1 1

8 20 48 32 4 1 1

9 14 36 24 2 1 1

8 9
1 7
2 3
87
 Euler’s Law

• Any polyhedron that satisfies the following equation has a

valid topology

F  E  V  L  2( B  G )

• Any open surface objects satisfies the following equation

F  E V  L  B  G

88
Open Polyhedral Objects

89
Exact B-rep of a cylinder and a sphere

90
Approximate B-rep or Faceted B-rep

 Curved face is divided

into planar facets.

 Faceted cylinder is
generated by rotating a
line incrementally about
the axis.

91
General data structure for B-rep

 It should have both

topological and
geometrical information.

 Lists for bodies, faces,

loops, edges and vertices
are generated and stored in
tables.

92
Euler Operations

93
94
Topology Creation via Euler Operators

95
96
Create the boundary model of solid S as shown in the
figure

97
98
99
Boundary Model of Solid S

100
Rotational Sweep Boundary Model

101
Advantages of B-rep

 It is very appropriate to construct solid models of unusual

shapes that are difficult to build using primitives.

 e.g., Aircraft and Automobile body

 It is relatively simple to convert a B-rep model into a

wireframe model because the model’s boundary definition is
similar to the wireframe definition.

Disadvantage

 The disadvantage of B-rep is that it requires large amounts of

storage because it stores the definition of the model boundaries.

 B-rep do not have a CSG compatible user interface.

102
 UNIT

3
NURBS- Basics- curves, lines, arcs, circle and bi
linear surface. Regularized Boolean set
operations - primitive instancing - sweep
representations - boundary representations -
constructive solid Geometry - comparison of
representations - user interface for solid
modeling.
 Constructive Solid Geometry (CSG)
 CSG and B-rep schemes are very popular schemes and best
understood representations so far.

 CSG representations are easy to create, store and easy to check

for validity.

 A CSG model is based on the topological notion

physical object can be divided into a set of primitives
(basic elements or shapes)

and that can be combined in a certain order following a

set of rules (Boolean operations) to form the object.

 Each primitive is bounded by a set of surfaces, it is combined via

a boundary evaluation process to form the boundary of the object.
104
 TYPES OF CSG SCHEMES
There are two main types of CSG schemes:

 r-sets: Based on bounded solid primitives.

 Non r-sets: Based on generally unbounded half spaces.

(lower level primitives)

Half-spaces
 It is a basic representation scheme for bounded solids. By
combining half-spaces (using set operations) in a building
block fashion, various solids can be constructed.

 Half spaces are usually unbounded geometric entities.

105
 Bounded and Unbounded Primitives

The solid model is represented by three bounded primitives and

seven half spaces

106
 Data Base of CSG
• The Database of CSG model stores its topology and
geometry.

• Topology is created via regularized set (Boolean)

operations that combine primitives.

• The geometry stored in the database of a CSG model

includes configuration parameters of its primitives and
rigid motion and transformation.

• Data structures of CSG representations are based on the

concept of graphs and trees.

107
 Graph
• A graph is defined as a set of nodes connected by a set of
branches or lines.
• Each branch in a graph is specified by a pair of nodes.
• The set of nodes is  A, B, C, D, E, F , G
• The set of branches or pairs is

 A, B , A, C , B, C , B, E , B, F , B, G, C, D, C, E

These pairs are unordered, that is,

no relation exist between the
elements of each pair.

Pair  A, B can also be B, A

108
 Directed Graph or Digraph

Pairs of nodes that make up the branches are ordered pairs

 Branches have directions and

arrows going from one node
to another.

 The tail of each arrow

represents the first node in the
pair and its head represents the
second node.

The set of ordered pairs are

 A, B , A, C , C, B , B, E, F , B, B, G, D, C, E, C

109
 Path in Digraph
 Each node in digraph has an
Indegree (number of arrow heads entering the
node)

Outdegree (number of arrow tails leaving the

node)

Path (sequence of nodes)

 Node B has an indegree of 3 and an outdegree of 2 while node D has a
zero indegree and an outdegree of 1.

 Each node in a digraph belongs to a path.

 The path from node A to node G is A, B, G or A, C, B, G.

 If the start and end nodes of a path are the same, the path is a cycle.

 If a graph contains a cycle, it is cyclic; otherwise it is acyclic.

110
 Tree
• A tree is defined as an acyclic digraph in which only a single
node, called the root, has a zero indegree and every other
node has an indegree of one.

• This implies that any node in the tree except the root has
predecessors or ancestors.

 Node A is the root of the tree

and nodes E, F, G have node
B as their predecessor.

 If the descendants of each

node are in order, then the tree
is an ordered one.

111
 Binary and Inverted Binary Tree
• If the ordered tree has two descendants, the tree is called a
binary tree.
 Any node in a tree that does not have
descendants, that is, with an out degree
equal to zero, is called a leaf node
(D,E,F,G).

 Any node that does have descendants

(out degree greater than zero) is an
interior node (B,C).

 If the arrow directions in a binary

tree are reversed such that every node,
except the root, in the tree has an out
degree of 1 and the root has a zero out
degree, the tree is called an inverted
binary tree.
112
 Sub-Tree
 Every node of a tree (T) is a root of another tree, called a sub tree
of T, contained in the original tree T.

 The tree consists of seven nodes with

A as its root.

 Its left sub tree is rooted at B and its

right sub tree is rooted at C.

 The absence of a branch indicates an

empty sub tree.

 The binary tree rooted at the leaves D,

E, F, G have empty left and right
sub trees.

113
 Typical solid and its primitives

A block and a cylinder primitive are enough to create CSG model of the solid.

114
• A user can construct the CSG model using the following steps:
B1= block positioned properly
B2= block positioned properly
B3= block
B4= B3 moved properly in X direction
C1= cylinder positioned properly
C2= C1 moved properly in X direction
C3= cylinder positioned properly
C4= C3 moved properly in X direction

115
S1  B1 *B3
S 2  S1 *C1
S3  S 2 *C3
S 4  B2 *B4
S 5  C2 *S 4
S 6  C4 *S5
S  S3 *S6

116
 CSG graph

S1  B1 *B3
S 2  S1 *C1
S3  S 2 *C3
S 4  B2 *B4
S 5  C2 *S 4
S 6  C4 *S5
S  S3 *S6

117
Data structure of a Primitive solid

118
• Create the CSG model of solid S as shown in the figure

119
Constructive Solid Geometry

120