License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08021.5
URN: urn:nbn:de:0030-drops-14408
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1440/
Go to the corresponding Portal

Dyllong, Eva

A Note on Some Applications of Interval Arithmetic in Hierarchical Solid Modeling

pdf-format:
08021.DyllongEva.Paper.1440.pdf (0.1 MB)

Abstract

Techniques of reliable computing like interval arithmetic can be used to
guarantee a reliable solution even in the presence of numerical round-off
errors. The need to trace bounds for the error function separately can be
eliminated using these techniques. In this talk, we focus on some
demonstrations how the techniques and algorithms of reliable computing
can be applied to the construction and further processing of hierarchical
solid representations using the octree model as an example.

An octree is a common hierarchical data structure to represent 3D
geometrical objects in solid modeling systems or to reconstruct a real
scene. The solid representation is based on recursive cell decompositions
of the space. Unfortunately, the data structure may require a large amount
of memory when it uses a set of very small cubic nodes to approximate a
solid.

In this talk, we present a novel generalization of the octree model created
from a CSG object that uses interval arithmetic and allows us to extend the
tests for classifying points in space as inside, on the boundary or outside
the object to handle whole sections of the space at once. Tree nodes with
additional information about relevant parts of the CSG object are
introduced in order to reduce the depth of the required subdivision.
Furthermore, this talk is concerned with interval-based algorithms for
reliable proximity queries between the extended octrees and with further
processing of the structure. We conclude the talk with some examples of
implementations.


BibTeX - Entry

@InProceedings{dyllong:DagSemProc.08021.5,
  author =	{Dyllong, Eva},
  title =	{{A Note on Some Applications of Interval Arithmetic in Hierarchical Solid Modeling}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2008/1440},
  URN =		{urn:nbn:de:0030-drops-14408},
  doi =		{10.4230/DagSemProc.08021.5},
  annote =	{Keywords: Reliable solid modeling, hierarchical data structure}
}

Keywords: Reliable solid modeling, hierarchical data structure
Collection: 08021 - Numerical Validation in Current Hardware Architectures
Issue Date: 2008
Date of publication: 22.04.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI