Progressive Conversion from B-rep to BSP for Streaming Geometric Modeling

We introduce a novel progressive approach to generate a Binary Space Partition (BSP) tree and a convex cell decomposition for any input triangles boundary representation (B-rep), by utilizing a fast calculation of the surface inertia. We also generate a solid model at progressive levels of detail. This approach relies on a variation of standard BSP tree generation, allowing for labeling cells as in, out and fuzzy, and which permits a comprehensive representation of a solid as the Hasse diagram of a cell complex. Our new algorithm is embedded in a streaming computational framework, using four types of dataflow processes that continuously produce, transform, combine or consume subsets of cells depending on their number or input/output stream. A varied collection of geometric modeling techniques are integrated in this streaming framework, including polygonal, spline, solid and heterogeneous modeling with boundary and decompositive representations, Boolean set operations, Cartesian products and adaptive refinement. The real-time B-rep to BSP streaming results we report in this paper are a large step forward in the ultimate unification of rapid conceptual and detailed shape design methodologies.