精确高效的线性布尔运算：超越CGAL的新突破

布尔运算

mesh

需积分: 10 137 浏览量更新于2024-09-01 收藏 2.71MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

资源详情

资源推荐

Eurographics Symposium on Geometry Processing 2009

Marc Alexa and Michael Kazhdan

(Guest Editors)

Volume 28 (2009), Number 5

Fast, Exact, Linear Booleans

Gilbert Bernstein

and Don Fussell

University of Texas at Austin, United States

Abstract

We present a new system for robustly performing Boolean operations on linear, 3D polyhedra. Our system is exact,

meaning that all internal numeric predicates are exactly decided in the sense of exact geometric computation. Our

BSP-tree based system is 16-28× faster at performing iterative computations than CGAL’s Nef Polyhedra based

system, the current best practice in robust Boolean operations, while being only twice as slow as the non-robust

modeler Maya. Meanwhile, we achieve a much smaller substrate of geometric subroutines than previous work,

comprised of only 4 predicates, a convex polygon constructor, and a convex polygon splitting routine. The use of

a BSP-tree based Boolean algorithm atop this substrate allows us to explicitly handle all geometric degeneracies

without treating a large number of cases.

Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Computing

Methodologies—Computational Geometry and Object Modeling;

1. Introduction

Despite a long history of robustness issues, Boolean set op-

erations (aka. constructive solid geometry or CSG for short)

remain a popular choice in most 3d modeling systems avail-

able. The operation conforms nicely to architectural concep-

tions of positive and negative space in building massing, the

machining of mechanical parts in CAD/CAM, and general

purpose “sculpting” operations of adding and removing vir-

tual stuff from a shape, to mention a few applications. We

built the system described here to address such sculpting ap-

plications, for which we found existing Boolean operations

lacking in speed and robustness, particularly when perform-

ing iterated operations, such as repeated gouging of an ob-

ject with a tool. Sculpting is a particularly challenging appli-

cation, since even moderate success requires fast(real-time)

and completely robust(zero failure) solutions in order to be

usable. We demonstrate that Boolean operations on polyhe-

dra can be made fast and robust enough to be a viable com-

ponent of such applications, contrary to the expectations of

many in the computer graphics community.

One of the ﬁrst and biggest motivations for research into

robust geometry was the not uncommon experience of see-

ing a system crash in response to attempting to perform

Boolean operations. However, despite 20 years of research

on the problem, state of the art robust Boolean operations

[HK05] may run up to 20 times slower than non-robust op-

erations. In our experiments(§4), these performance char-

acterizations are actually optimistic. We see cases where

the state of the art (CGAL) takes more than 50 times as

long as non-robust Booleans. When we spoke to practition-

ers who implement Boolean operations in entertainment and

architectural design modelers, none were aware of any re-

search into geometric robustness. They believed that there

are no solutions to their robustness problems short of using

Matlab/Mathematica-style big number computation, which

they deem prohibitively expensive. Given that the aforemen-

tioned Hachenberger et al. paper [HK05] constitutes the only

experiment with more than a single test in the last 20 years,

it is easy to see how this impression persists.

Contribution We demonstrate a system capable of comput-

ing completely robust (i.e. exact §2.1) linear Boolean opera-

tions only twice as slowly as the non-robust (i.e. fragile §2.1)

modeler Maya, providing the ﬁrst empirical evidence that

geometric robustness techniques are actually practical for

computing Boolean operations. This constitutes the second

and largest comparative test between non-robust commer-

cial Booleans and robust Boolean systems ever conducted

and published as far as we are aware. We accomplish this

using a novel synthesis(§3) of techniques mostly 15 − 20

years old(§2). In addition to a number of small but important

changes to these techniques, we present a new plane-based

convex polygon splitting algorithm(§3.2).

 2009 The Author(s)

Journal compilation

 2009 The Eurographics Association and Blackwell Publishing Ltd.

Published by Blackwell Publishing, 9600 Garsington Road, Oxford OX4 2DQ, UK and

350 Main Street, Malden, MA 02148, USA.

下载后可阅读完整内容，剩余9页未读，立即下载

你好，Albert

粉丝: 5978
资源: 26

精确高效的线性布尔运算：超越CGAL的新突破

Booleans

Fast exact shortest-path distance queries on large networks

什么是PELT ( Pruned Exact Linear Time)算法？它的原理是什么

INTER_LINEAR_EXACT

django __exact

SCHEDULE_EXACT_ALARM

怎么使用apoc.number.exact\

--save-exact

怎么使用apoc.number.exact

nuxt-link属性有to、exact、active-class、exact-active-class等，详细说下。

OrdinaryKriging(self.GX, self.GY, self.GAngVal, variogram_function = 'linear', variogram_parameters = [1,9], nlags = 6, exact_values=False)解释一下

react路由中的exact

风光光度仪exact使用原理

Qregexp exactMatch函数

no exact pin location

print-color-adjust: exact;怎么兼容火狐和ie

Exact Match

CGAL::Exact_predicates_tag

最新资源