Robust and efficient ray intersection of implicit surfaces
type: Item
instance of: scholarly article
title: Robust and efficient ray intersection of implicit surfaces
zbMATH Open document ID: 0965.65042
DOI: 10.1023/A:1009921806032
author: Yanyan Li
published in: Reliable Computing
publication date: 2000-03-22T00:00:00Z
review text: The generation of ray traced images of surfaces plays a central role in computer graphics. One of the main operations in ray tracing is the calculation of intersections between rays and surfaces. In case of implicitly given surfaces the intersection problem can be formulated as that of finding the smallest nonnegative root of an equation in one variable. If the root finding is carried out by means of conventional numerical methods based on point sampling (such as bisection, regula-falsi, Newton) the resulting image can be wrong, when the surface is thin the ray may miss the surface, which may result in an image with holes. In this paper robust methods are obtained with interval inclusions in a variant of Alefeld-Hansen's globally convergent method for computing and bounding all the roots of a single equation. Alefeld-Hansen's method has been modified so instead of searching for all roots, a recursive depth-first search is carried out to obtain the smallest nonnegative root. When compared to other methods, it is found that this variant of Alefeld-Hansen's method is not only robust but also an efficient method for finding the ray intersection.
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 65G30
Mathematics Subject Classification ID: 65H05
zbMATH DE Number: 1421498
zbMATH Keywords: ray intersection of implicit surfaces
zbMATH Keywords: computer graphics
zbMATH Keywords: ray tracing
zbMATH Keywords: interval arithmetic
zbMATH Keywords: global convergence
zbMATH Keywords: root finding
zbMATH Keywords: Alefeld-Hansen's method
reviewed by: Herbert Fischer
describes a project that uses: PROFIL/BIAS
MaRDI profile type: Publication
full work available at URL: a:1009921806032
OpenAlex ID: W33640052
Recommended article: Q4823823
Recommended article: General, robust, and efficient polyhedron intersection in the interface reconstruction library
Recommended article: Q3034875
Recommended article: Q4434835
Recommended article: A second order geometric method for ray/parametric surface intersection
Recommended article: Robust interval algorithm for surface intersections
description: scientific article; zbMATH DE number 1421498