Building binary orientation octree for an arbitrary scattered point set

• We extend the binary orientation tree (BOT) data structure by extending the ‘in/out’ labels to ‘front/back/NA’ labels.
• Apply a global propagation process to get the consistent labels.
• It’s useful for both open and closed point sets.

The binary orientation tree (BOT), proposed in [Chen, Y.-L., Chen, B.-Y., Lai, S.-H., and Nishita, T. (2010). Binary orientation trees for volume and surface reconstruction from unoriented point clouds. Comput. Graph. Forum, 29(7), 2011–2019.], is a useful spatial hierarchical data structure for geometric processing such as 3D reconstruction and implicit surface approximation from an input point set. BOT is an octree in which all the vertices of the leaf nodes in the tree are tagged with an ‘in/out’ label based on their spatial relationship to the underlying surface enclosed by the octree. Unfortunately, such a data structure in [Chen, Y.-L., Chen, B.-Y., Lai, S.-H., and Nishita, T. (2010). Binary orientation trees for volume and surface reconstruction from unoriented point clouds. Comput. Graph. Forum, 29(7), 2011–2019.] is only valid for watertight surfaces, which restricts its application. In this paper, we extend the ‘in/out’ relationship to ‘front/back/NA’ relationship to either a closed or an open surface, and propose a new method to build such a spatial data structure from a given arbitrary point set. We first classify the edges of the leaf nodes into two different categories based on whether their two end points are in the same side of the surface or not, and attach respective labels to the edges accordingly. A global propagation process is then applied to get the consistent labels of those end points that are in the same side of the surface. Experiments show that our BOT building method is much more robust, efficient and applicable to various input compared to existing methods, and the applications of BOT when doing RBF reconstructions and envelope surface computations of given 3D objects are shown in the experimental part.

Figure optionsDownload as PowerPoint slide