Jiang, Di ;
Stewart, Neil
Robustness of Boolean operations on subdivisionsurface models
Abstract
This work was presented in two parts at Dagstuhl seminar 08021.
The two presentations described work in
progress, including a ``backward bound'' for a combined backward/forward
error analysis for the problem mentioned in the title.
We seek rigorous proofs that representations of computed sets, produced by
algorithms to compute Boolean operations, are well formed, and that the
algorithms are correct. Such proofs should eventually take account of the use of
finiteprecision arithmetic, although the proofs presented here do not.
The representations studied are based on subdivision surfaces. Such
representations are being used more and more frequently in place of trimmed
NURBS representations, and the robustness analysis for these new representations
is simpler than for trimmed NURBS.
The particular subdivisionsurface representation used is based on the Loop
subdivision scheme. The analysis is broken into three parts. First, it is
established that the input operands are wellformed twodimensional manifolds
without boundary. This can be done with existing methods.
Secondly, we introduce the socalled ``limit mesh'', and view the
limit meshes corresponding to the input sets as defining an approximate problem
in the sense of a backward error analysis. The presentations mentioned above
described a proof of the corresponding error bound. The third part of the
analysis corresponds to the ``forward bound'': this remains to be done.
BibTeX  Entry
@InProceedings{jiang_et_al:DSP:2008:1443,
author = {Di Jiang and Neil Stewart},
title = {Robustness of Boolean operations on subdivisionsurface models},
booktitle = {Numerical Validation in Current Hardware Architectures},
year = {2008},
editor = {Annie Cuyt and Walter Kr{\"a}mer and Wolfram Luther and Peter Markstein},
number = {08021},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1443},
annote = {Keywords: Robustness, finiteprecision arithmetic, Boolean operations, subdivision surfaces}
}
Keywords: 

Robustness, finiteprecision arithmetic, Boolean operations, subdivision surfaces 
Seminar: 

08021  Numerical Validation in Current Hardware Architectures

Issue date: 

2008 
Date of publication: 

22.04.2008 