Name
Abstract | ||
|---|---|---|
This paper presents a new method for evaluating boolean set operations between Binary Space Partition (BSP) trees. Our algorithm has many desirable features, including both numerical robustness and O(n) output sensitive time complexity, while simultaneously admitting a straightforward implementation. To achieve these properties, we present two key algorithmic improvements. The first is a method for eliminating null regions within a BSP tree using linear programming. This replaces previous techniques based on polygon cutting and tree splitting. The second is an improved method for compressing BSP trees based on a similar approach within binary decision diagrams. The performance of the new method is analyzed both theoretically and experimentally. Given the importance of boolean set operations, our algorithms can be directly applied to many problems in graphics, CAD and computational geometry. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.cad.2008.11.002 | Computer-Aided Design |
Keywords | Field | DocType |
computational geometry,binary decision diagram,linear programming,binary space partition,desirable feature,constructive solid geometry,improved method,compressing bsp tree,tree merging,tree splitting,new method,bsp tree,improved binary space partition,boolean set operation,linear program,time complexity | Binary space partitioning,Mathematical optimization,Threaded binary tree,Self-balancing binary search tree,Binary tree,Optimal binary search tree,Binary decision diagram,Random binary tree,Binary expression tree,Mathematics | Journal |
Volume | Issue | ISSN |
40 | 12 | Computer-Aided Design |
Citations | PageRank | References |
3 | 0.40 | 30 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikola Lysenko | 1 | 74 | 6.13 |
| Roshan D'Souza | 2 | 98 | 7.60 |
| Ching-Kuang Shene | 3 | 251 | 33.18 |