Full-Text PDF    Submission   Back

Abstract
A robust and efficient Boolean operation algorithm for point sampled models is presented in this paper. First, a surfel with a certain size of radius is reconstructed at each sample point on the models. And all of the surfels are classified into one of the following categories: in, out and intersect with respect to the other solid model. Then the intersection curves are estimated under the control of a given global error through adaptively subdividing and re-sampling of the intersect surfels. Besides, a hierarchical structure k-d tree is built for each point model to accelerate the test of efficient classifying the surfel's in/out/intersect test. The experimental results show that this Boolean operation algorithm can robustly handle point models with different sampling resolution and non-uniform sampled point models.

Miao LF, Peng QS. Boolean operation for point sampled models. Journal of Software, 2006,17(Suppl.):57-63. 
http://www.jos.org.cn/1000-9825/17/s57.htm


摘要
提出了一种快速而鲁棒的点模型布尔运算算法.在进行布尔运算之前,首先将点模型中的每个点表示成具有一定半径的面元,并确定它相对于另一个模型表面的内、外及相交关系;然后对相交面元进行全局误差控制下的自适应加密重采样,以求取交线;为了加速面元的内、外及相交关系的检测,对每个模型建立层次结构k-d树.实验结果表明,该方法对于具有不同分辨率以及采样不均匀的点模型也能进行稳定可靠的布尔运算.

基金项目：Supported by the National Grand Fundamental Research 973 Program of China under Grant No.2002CB312101 (国家重点基础研究发展计划(973))

References: 

[1] Pauly M, Keiser R, Kobbelt L, Gross M. Shape modeling with point-sampled geometry. ACM Trans. on Graphics (Proc. of the SIGGRAPH), 2003,22(3):641-650.

[2] Ohtake Y, Belyaev A, Alexa M, Turk G, Seidel H. Multi-Level partition of unity implicits. In: Proc. of the Siggraph 2003. San Diego: ACM Press, 2003. 463-470.

[3] Adams B, Dutre P, 2003. Interactive Boolean operations on surfel-bounded solids. In: Proc. of the Siggraph 2003. San Diego: ACM Press, 2003. 651-656. 

[4] Pfister H, Zwicker M, Van Baar J, Gross M. Surfels: Surface elements as rendering primitives. In: Proc. of the Siggraph 2000. New Orleans: ACM Press, 2000. 335-342.

[5] Yang CY. Shape Modeling of point-sample geometry [MS. Thesis]. Hangzhou: Zhejiang University, 2004 (in Chinese with English abstract).

[6] Miao LF, Huang J, Zheng WT, Bao HJ, Peng QS. Local geometry reconstruction and ray tracing for point models. Journal of Computer-Aided Design and Computer Graphics. 2006,18(6):805-811 (in Chinese with English abstract).

[7] Zhu XX. Modeling Technology of Free Curves and Surfaces. Beijing: Science Press, 2000 (in Chinese).

附中文参考文献:
[5] 杨振羽.基于点表示几何体的造型技术[硕士学位论文].杭州:浙江大学,2004.

[6] 苗兰芳,黄劲,郑文庭,鲍虎军,彭群生.点模型的局部几何重建和光线跟踪.计算机辅助几何设计和图形学学报,2006,18(6): 805-811.

[7] 朱心雄.自由曲线和曲面造型技术.北京:科学出版社,2000.