ZTE

ZTE Communications ›› 2015, Vol. 13 ›› Issue (3): 57-66.DOI: 10.3969/j.issn.1673-5188.2015.03.007

• Research Paper • Previous Articles    

Fast, Exact and Robust Set Operations on Polyhedrons Using Localized Constructive Solid Geometry Trees

Ping Lu1, Xudong Jiang2, Wei Lu2, Ran Wei1, Bin Sheng3   

  1. 1. ZTE Corporation, Nanjing 210012, China;
    2. Autodesk China Research & Development Center, Shanghai 200061, China;
    3. Shanghai Jiao Tong University, Shanghai 200240, China
  • Received:2015-06-05 Online:2015-09-25 Published:2015-09-25
  • About author:Ping Lu (lu.ping@zte.com.cn) received his ME degree in automatic control theory and applications from South East University. He is the chief executive of the Cloud Computing and IT Institute of ZTE Corporation. His research interests include augmented reality and multimedia services technologies.
    Xudong Jiang (denny.jiang@gmail.com) received his master’s degree in computer science and technology from Shanghai Jiao Tong University. He is currently working at the Autodesk China Research & Development Center. His research interests include computer graphics and solid modeling.
    Wei Lu (ddhansh@gmail.com) received her PhD degree in computer science and technology from Nanjing University. She is currently working at the Autodesk China Research & Development Center. Her research interests include computer graphics, mesh deformation, and virtual reality
    Ran Wei (wei.ran233@zte.com.cn) received his master’s degree in communications and electronic information from Chongqing University of Posts and Telecommunications. He is currently a pre-research engineer of ZTE Corporation. His research interests include machine vision and graphics and image processing.
    Bin Sheng (shengbin@cs.sjtu.edu.cn) received his MS degree in software engineering from University of Macau in 2007, and PhD degree in computer science from The Chinese University of Hong Kong in 2011. He is currently an associate professor at Department of Computer Science and Engineering, Shanghai Jiao Tong University. He also works with the Institute of Software, Chinese Academy of Sciences. His research interests include virtual reality, computer graphics, and image based techniques.
  • Supported by:
    The work is supported by the Natural Science Foundation of China under Grant No. 61202154 and No. 61133009, the National Basic Research Project of China under Grant No. 2011CB302203, Shanghai Pujiang Program under Grant No.13PJ1404500, the Science and Technology Commission of Shanghai Municipality Program under Grant No. 13511505000, and the Open Project Program of the State Key Lab of CAD&CG of Zhejiang University under Grant No. A1401.

Fast, Exact and Robust Set Operations on Polyhedrons Using Localized Constructive Solid Geometry Trees

Ping Lu1, Xudong Jiang2, Wei Lu2, Ran Wei1, Bin Sheng3   

  1. 1. ZTE Corporation, Nanjing 210012, China;
    2. Autodesk China Research & Development Center, Shanghai 200061, China;
    3. Shanghai Jiao Tong University, Shanghai 200240, China
  • 作者简介:Ping Lu (lu.ping@zte.com.cn) received his ME degree in automatic control theory and applications from South East University. He is the chief executive of the Cloud Computing and IT Institute of ZTE Corporation. His research interests include augmented reality and multimedia services technologies.
    Xudong Jiang (denny.jiang@gmail.com) received his master’s degree in computer science and technology from Shanghai Jiao Tong University. He is currently working at the Autodesk China Research & Development Center. His research interests include computer graphics and solid modeling.
    Wei Lu (ddhansh@gmail.com) received her PhD degree in computer science and technology from Nanjing University. She is currently working at the Autodesk China Research & Development Center. Her research interests include computer graphics, mesh deformation, and virtual reality
    Ran Wei (wei.ran233@zte.com.cn) received his master’s degree in communications and electronic information from Chongqing University of Posts and Telecommunications. He is currently a pre-research engineer of ZTE Corporation. His research interests include machine vision and graphics and image processing.
    Bin Sheng (shengbin@cs.sjtu.edu.cn) received his MS degree in software engineering from University of Macau in 2007, and PhD degree in computer science from The Chinese University of Hong Kong in 2011. He is currently an associate professor at Department of Computer Science and Engineering, Shanghai Jiao Tong University. He also works with the Institute of Software, Chinese Academy of Sciences. His research interests include virtual reality, computer graphics, and image based techniques.
  • 基金资助:
    The work is supported by the Natural Science Foundation of China under Grant No. 61202154 and No. 61133009, the National Basic Research Project of China under Grant No. 2011CB302203, Shanghai Pujiang Program under Grant No.13PJ1404500, the Science and Technology Commission of Shanghai Municipality Program under Grant No. 13511505000, and the Open Project Program of the State Key Lab of CAD&CG of Zhejiang University under Grant No. A1401.

PDF

Abstract: Regularized Boolean operations have been widely used in 3D modeling systems. However, evaluating Boolean operations may be quite numerically unstable and time consuming, espe?cially for iterated set operations. A novel and unified tech?nique is proposed in this paper for computing single and iter?ated set operations efficiently, robustly and exactly. An adap?tive octree is combined with a nested constructive solid geom?etry (CSG) tree by this technique. The intersection handling is restricted to the cells in the octree where intersection actu?ally occurs. Within those cells, a CSG tree template is in?stanced by the surfaces and the tree is converted to plane?based binary space partitioning (BSP) for set evaluation;More?over, the surface classification is restricted to the cells in the octree where the surfaces only come from a model and are within the bounding?boxes of other polyhedrons. These two ways bring about the efficiency and scalability of the opera?tions, in terms of runtime and memory. As all surfaces in such a cell have the same classification relation, they are clas?sified as a whole. Robustness and exactness are achieved by integrating plane?based geometry representation with adaptive geometry predicate technique in intersection handling, and by applying divide?and?conquer arithmetic on surface classifica?tion. Experimental results demonstrate that the proposed ap?proach can guarantee the robustness of Boolean computations and runs faster than other existing approaches.

Key words: Boolean operations, polyhedrons, constructive solid geometry, binary space partitioning tree

摘要： Regularized Boolean operations have been widely used in 3D modeling systems. However, evaluating Boolean operations may be quite numerically unstable and time consuming, espe?cially for iterated set operations. A novel and unified tech?nique is proposed in this paper for computing single and iter?ated set operations efficiently, robustly and exactly. An adap?tive octree is combined with a nested constructive solid geom?etry (CSG) tree by this technique. The intersection handling is restricted to the cells in the octree where intersection actu?ally occurs. Within those cells, a CSG tree template is in?stanced by the surfaces and the tree is converted to plane?based binary space partitioning (BSP) for set evaluation;More?over, the surface classification is restricted to the cells in the octree where the surfaces only come from a model and are within the bounding?boxes of other polyhedrons. These two ways bring about the efficiency and scalability of the opera?tions, in terms of runtime and memory. As all surfaces in such a cell have the same classification relation, they are clas?sified as a whole. Robustness and exactness are achieved by integrating plane?based geometry representation with adaptive geometry predicate technique in intersection handling, and by applying divide?and?conquer arithmetic on surface classifica?tion. Experimental results demonstrate that the proposed ap?proach can guarantee the robustness of Boolean computations and runs faster than other existing approaches.

关键词: Boolean operations, polyhedrons, constructive solid geometry, binary space partitioning tree