Constructive Solide Geometry and Binary representation

Modelling In CAD

1. CSG and B-Rep
Prof. R.B.Chadge

2. Constructive solid geometry (CSG)
•Primitive based: It is based on the notion that a
physical object can be divided into a set of primitives
– basic elements or shapes that can be combined in a
certain order following a set of rules (Boolean
operations) to create the object.
• Primitives themselves are considered valid CSG
models. Each primitives is bounded by closed and
orientable surfaces.

3. Constructive solid geometry (CSG)
•CSG model is fundamentally and topologically
different from a B-rep model in that it does not store
faces, edges and vertices explicitly. Instead it
evaluates them whenever needed by algorithms.
•CSG representation is of considerable importance for
manufacturing

4. Constructive solid geometry (CSG)
Boolean operation
•Each primitive solid is assumed to be a set of points,
a boolean operation is performed on point sets and
the result is a solid model.
•Boolean operation  union, intersection and
difference
•The relative location and orientation of the two
primitives have to be defined before the boolean
operation can be performed.
• Boolean operation can be applied to two solids other
than the primitives.

5. Constructive solid geometry (CSG) -
Boolean Operation

6. Constructive solid geometry (CSG)-
Boolean Operation

7. Constructive solid geometry (CSG)-
Boolean Operation

8. •Boolean operation
–Are intuitive to user
–Are easy to use and understand
–Provide for the rapid manipulation of large
amounts of data.
•Because of this, many non-CSG systems also use
Boolean operations

Constructive solid geometry (CSG)-
Boolean Operation

9. Data Structure of CSG
•Like in B-rep, the database stores topology and
geometry.
• The validity checking in CSG scheme occurs
indirectly. The each primitive that is combined using
a Boolean operations (r-sets) to build the CSG model
is checked for its validity.
• The common data structures used for CSG are graphs
and trees

10. CSG Data Structure
•Graph: A graph is defined as a set of nodes
connected by a set of branches or lines.
•Path: Each node in a tree belongs to a path E.g. A to
G
•Cycle: If starting and ending nodes are the same the
path is called a cycle.

11. CSG Data Structure
•Cyclic Graph: If a graph contains a cycle it is called
cyclic otherwise it is acyclic.
•Path: Each node in a tree belongs to a path E.g. A to
G.
•Cycle: If starting and ending nodes are the same the
path is called a cycle

12. Tree and Binary Tree
•Tree: A tree is an acyclic digraph in which a single
node called root node has a zero in degree and every
other nodes has an in degree of one.
•Binary Tree: In a tree if the descendent of each node
are in order (from left to right) and each node except
the leaf node has two decedents (left and right), then
the tree is called a binary tree.

13. Inverted Binary Tree for CSG Model
•Inverted Binary Tree: If the direction of each
connector (arrow) are reversed then we get an
inverted binary tree wherein each node has one
outdegree except the root node.
•Root node: A node with outdegree = 0. Any node
that does not have descendent.
•Leaf node: Any node that does not have a
predecessor or indegree = 0.

14. Inverted Binary Tree for CSG Model
• Interior node: Any node with outdegree > 0
is an interior node.

15. Inverted Binary Tree as CSG Tree
•CSG Tree: The inverted binary tree is very
convenient to represent the CSG operations.
•Here each of the leaf nodes is a valid solid primitive.
The intermediate nodes are the transition states of the
solid modeling (r-set) operations.
•The root node is the resulting solid from the set
operations.
•Here n primitives require (n-1) Boolean operations to
complete the construction of the object.

16. Inverted Binary Tree as CSG Tree

17. Inverted Binary Tree as CSG Tree

18. Tree Traversal

19. Tree Traversal

20. Tree Traversal

21. Tree Traversal

22. Tree Traversal

23. Tree Traversal

24. Tree Traversal