Constructive solid geometry
methods
Sunu Fathima T.H
Asst. Professor, IT, SOE
1
COURSE OUTCOMES
1. Understand the fundamental principles that underline the computer
graphics algorithms.
2. Develop and implement two and three dimensional graphical
structures.
3. Design two and three dimensional graphical structures.
4. Implement graphics programming using OpenGL.
5. Understand computer animation.
2
Constructive Solid-geometry methods
❏ Combine the volumes occupied by overlapping three-dimensional
objects using set operations.
❏ Constructive solid geometry (CSG) modeling method
❏ Creates a new volume by applying the union, intersection, or
difference operation to two specified volumes.
3
❏ A block and pyramid are placed
adjacent to each other.
❏ Specifying the union operation,
we obtain the combined object
4
❏ A block and a cylinder with
overlapping volumes.
❏ Using the intersection operation,
we obtain the resulting solid in
(b)
❏ With a difference operation, we
can get the solid shown in (c)
5
Constructive Solid-geometry methods
❏ CSG application-starts with an initial set of three-dimensional
objects (primitives)
❏ Blocks
❏ Pyramids
❏ Cylinders
❏ Cones
❏ Spheres
❏ Closed spline surfaces
6
Constructive Solid-geometry methods
❏ Select two primitives and drag them into position in some region of
space.
❏ Select an operation for combining the volumes of the two primitives.
❏ Union
❏ Intersection
❏ Difference
7
Constructive Solid-geometry methods
❏ Union: New volume is the combined interior regions occupied by
either or both primitives.
❏ Intersection: New volume is the-interior region common to both
primitives.
❏ Difference: Subtracts the volume of one primitive from the other.
8
Constructive Solid-geometry methods
❏ Now we have a new object, in addition to the primitives.
❏ Use it to form other objects.
❏ Continue to construct new shapes, using combinations of primitives
and the objects created at each step, until we have the final shape.
❏ An object designed with this procedure is represented with a binary
tree.
9
Constructive Solid-geometry methods
10
Constructive Solid-geometry methods
❏ Ray-casting methods are commonly used to implement constructive
solid geometry operations.
❏ Apply ray casting by constructing composite objects in world
coordinates with the xy plane corresponding to the pixel plane of a
video monitor.
❏ This plane is then referred to as the "firing plane"
❏ Since we fire a ray from each pixel position through the objects
that are to be combined.
11
❏ Determine surface intersections
along each ray path.
❏ Sort the intersection points
according to the distance from
the firing plane.
❏ Surface limits for the composite
object are then determined by
the specified set operation.
12
Constructive Solid-geometry methods
13
OCTREES
❏ An octree is a tree data structure in which each internal node has
exactly eight children.
❏ Used to partition a three-dimensional space by recursively
subdividing it into eight octants.
❏ Octrees are the three-dimensional analog of quadtrees.
❏ Each node in an octree subdivides the space it represents into eight
octants.
14
OCTREES
❏ The tree structure is organized so that each node corresponds to a
region of three-dimensional space.
❏ This representation for solids takes advantage of spatial coherence to
reduce storage requirements for three-dimensional objects.
❏ It also provides a convenient representation for storing information
about object interiors.
15
OCTREES
16
OCTREES
❏ Regions can be considered to be homogeneous in terms of colour,
material type, density or any other physical characteristics.
17
OCTREES
❏ Octrees are based on a two dimensional representation scheme called
quadtree encoding.
❏ Divides a square region of space into four equal areas until
homogeneous regions are found.
❏ These regions can then be arranged in a tree.
❏ Each node in the quadtree has four data elements, one for each of the
quadrants in the region.
18
OCTREES
19
OCTREES
❏ If all pixels within a quadrant have the same color (a homogeneous
quadrant), the corresponding data element in the node stores that
color in addition.
❏ A flag is set in the data element to indicate that the quadrant is
homogeneous.
20
OCTREES
❏ Suppose all pixels in quadrant 2 are found to be red.
❏ Color code for red is then placed in data element 2 of the node.
❏ Otherwise, the quadrant is said to be heterogeneous, and that
quadrant is itself divided into quadrants.
❏ Corresponding data element in the node now flags the quadrant
as heterogeneous and stores the pointer to the next node in the
quadtree.
❏ Successive subdivisions into quadrants continue until all
quadrants are homogeneous.
21
OCTREES
❏ An octree takes the same approach as quadtrees.
❏ But divides a cube region of 3D space into octants.
❏ Each region within an octree is referred to as a volume element or a
voxel.
❏ Division is continued until homogeneous regions are discovered.
22
BSP TREES
❏ Binary Space Partitioning is implemented for recursively
subdividing a space into two convex sets by using hyperplanes as
partitions.
❏ Gives rise to the representation of objects within the space in the
form of tree data structure known as BSP Tree.
23
BSP TREES
24
BSP TREES
❏ Structure of a BSP tree allows for spatial information about the
objects in a scene that is useful in rendering.
❏ Such as objects being ordered from front-to-back with respect to
a viewer at a given location.
25
BSP TREES
26
THANK YOU
27