2026-07-20T12:09:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1440 2024-03-06T11:07:52Z ddc:004 open_access

A Note on Some Applications of Interval Arithmetic in Hierarchical Solid Modeling Dyllong, Eva Reliable solid modeling hierarchical data structure 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eva Dyllong 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.08021.5 urn:nbn:de:0030-drops-14408 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.5 eng https://creativecommons.org/licenses/by/4.0/legalcode