- They define the BSH of a set of halfspaces and samples as the half space bounded by some parts of the input halfspaces that:
- (1) respects the orientation (in/out) of each input halfspace, where it coincides with its boundary
- (2) is sample-connected, meaning that each connected component of the intersection of an input halfspace with the BSH contains a sample (to avoid “short cuts”)
- (3) Minimizes the total boundary area
- (4) Minimizes the number of input samples that are not part of the final boundary
- To satisfy (1, 3, 4), they pose the constrained minimization as an directed graph cut to define the in/out labelling.
- To satisfy (2) or approximate it, they do a best-first search
- Starting from an optimal solution for (1, 3, 4) as a result from a graph cut, they look at which patches could potentially be removed
- For each removable set of patches, they do the graph cut to compute the energy (3, 4) after forbidding a cut at the removed patches (setting some edge weights to infinity) and place the result in a priority queue, and will then consider the removable sets of the result, etc.
- In practice they do a greedy beam search where they only look at the best (lowest energy) state
- They stop when the result is sample-connected
- They show that they can convert other representations like a triangle mesh to a BSH, to do reverse engineering
- First get a feature-algined segmentation of the shape
- For each patch, fit a halfspace representation, for example a simple primitive by RANSAC or a VIPSS implicit surface (with increasingly more control points)
- Generate samples by incrementally adding samples until the BSH matches with the input surface
A new representation for solid shape design, where the shapes are composed of a set of halfspaces along with samples on the boundary that indicate which parts of the halfspaces boundaries define the boundary of the final shape. Compared to CSG representation, this is more flexible and does not need additional separating halfspaces to define some of the shapes bounded by the halfspaces