versão em português

CIC 116521 Estudos em Computação Multimídia prof. Aluizio Arcela author: Danilo Balby Silva Castanheira

The Boolean Set Operations Project The boolean set operations The problem approach Implementation in Java 3D Gallery Bibliography

The boolean set operations   The boolean set operations are intuitive and popular ways to combine solids based on the set operations. The three main are: Union (u): The resulting solid corresponds to all the volume from the operand solids. Intersection (n): The resulting solid corresponds to the coincident volume from the operand solids. Difference (-): The resulting solid corresponds to the volume from one of the operand solids outside the other ones. The boolean set operations idea is similar to the one of the set operations - having a solid as a set and the solid volume as the set content, the boolean set operations act as the set operations. So, this idea doesn't have relation to the one related originally to the boolean operation, that concerns with binary operations. Due to its simplicity and efficiency, the boolean set operations were implemented on the most of the 3D modelling tools, being used as a resource to compose 3D models.

The problem approach   The constructive solid geometry (CSG) is a representation model based on the boolean set operations. Solids represented in that manner result from boolean set operations applications on elementary solids, called primitives. Spheres, cones, cylinders and rectangular solids are forms commonly used as primitives. A CSG solid is represented in function of the primitives and operations used in its composition. Its structure is a tree where these operations are hierarchized, called CSG tree. Each operation applied is represented as a internal node (no leaf), and each primitive as a leaf node. The constructive solid geometry needs another representation, its internal representation, in order to the solid represented in that manner can be renderized. The data necessary to view a CSG solid are obtained by its tree traversion. So, the CSG tree must keep appropriate data, that may vary depending on the internal representation. An internal node must keep a reference to the boolean operation it refers. A leaf node must keep the corresponding primitive structure on internal representation or data to be used on its creation (depending on what is its form). The CSG tree traversion is in depth first search. That's because using this strategy the nodes are visited in order of application of its operations. Data relative to the primitives are obtained on the leaf nodes, and combinations are made on the internal nodes. The b-rep representation may be used as CSG internal representation, what is a quite robust and flexible approach to represent solids composed by boolean set operations. When it is used, the b-rep solid corresponding to a CSG tree is obtained when its renderization is required. It is created by the primitives combinations according to the operations applied. The tree is traversed in depth first search, in a way that b-rep primitives are created when leaf nodes are visited and solids obtained from the descending nodes are combined (according the corresponding boolean operation) when internal nodes are visited. Is necessary an approach to combine b-rep solids with boolean set operations. There are some, being on of them described at [LAI86]. The algorithm described in it is applied to two solids simultaneously. First, it subdivides the faces of the solids in a way that there isn't faces intersection among them. Then, the faces of a solid are classified based on the surface of the other as being, inside, outside or on its boundary. Depending on how the faces were classified, they will or will not be used on the new solid (depending on what boolean operation is being applied). Click here to download a document that detail the subject (in portuguese).

Implementation in Java 3D   UnBBoolean Application based on the constructive solid geometry (CSG), combines primitives using the boolean set operations download   UnBBoolean's API for Boolean Set Operations API to apply boolean set operations for Java3D download jar download source download javadoc

Gallery

Bibliography   [CAR02] Carrara V. Manual de computacao grafica. 2002. Available at http://www.directnet.com.br/users/val/tutor/tutor.html [FOL92] Foley J. D. et. al. Van Dam A.; Feiner S. K.; Hughes J. F. Computer graphics - principles and practice. 2. ed. Addison-Wesley, 1992. [LAI86] Laidlaw D. H.; Trumbore W. B.; Hughes J. F. Constructive solid geometry for polyhedral objects. SIGGRAPH Proceedings, 1986. p.161. [MAR98] Martin, J. Voxel based CSG modeler. Graz, Austria: Institute for Computer Graphics and Vision, University of Technology, 1998. Available at http://www.icg.tu-graz.ac.at/~Education/Seminar_Projekt/fertig/martin/project.html [MEL98] Melax S. A simple, fast, and effective polygon reduction algorithm, Game Developer Magazine, 1998. Available at http://www.melax.com/polychop/gdmag.pdf [PIO] Pio J. L. S. Modelagem de solidos. Available at http://www.dcc.ufmg.br/~josepio/discp/modgeo/modgeo.html [SUN03] Sunday, D. Geometry Algorithms, 2001-2003. Available at http://geometryalgorithms.com/index.htm [SWO95] Swokowski, E. W. Calculo com Geometria Analitica. 2. ed. Sao Paulo: Makron Books do Brasil, 1995. v.2. [WAT93] Watt A. 3D Computer graphics. 2 ed. Addson-Wesley, 1993.