Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 89
PROCEEDINGS OF THE SIXTH INTERNATIONAL CONFERENCE ON ENGINEERING COMPUTATIONAL TECHNOLOGY
Edited by: M. Papadrakakis and B.H.V. Topping
Paper 150

Application of Binary Spatial Partitioning to Computer Aided Design

A.A. Stamos

School of Civil Engineering, National Technical University of Athens, Greece

Full Bibliographic Reference for this paper
A.A. Stamos, "Application of Binary Spatial Partitioning to Computer Aided Design", in M. Papadrakakis, B.H.V. Topping, (Editors), "Proceedings of the Sixth International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 150, 2008. doi:10.4203/ccp.89.150
Keywords: binary spatial partitioning, computer aided design.

Summary
Computer aided design (CAD) applications usually need to store and process dynamically and efficiently various drawing elements. Typically the quad-tree data structure is used in two dimensions and the octant-tree data structure in three dimensions. Here the binary spatial partitioning (BSP) tree data structure is proposed for CAD applications. BSP scales better in irregular geometries such as long narrow engineering drawings, it has less overhead, it is easier to implement, and it is easily extended to three and higher dimensions. Modifications to BSP are proposed to adapt it better to interactive environments. Elements are not broken when a BSP node is split keeping the BSP size small. Physical elements size limit the depth and the fragmentation of the BSP trees. Semi-infinite BSP nodes delay the BSP structure finalization, improving the BSP balance. The knowledge of drawing extents ensures BSP balance when the BSP structure is rebuilt after a drawing regeneration. Finally implementation related issues are addressed.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)