Wolfram Library Archive


Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title

A BSP-Based Algorithm for Dimensionally Nonhomogeneous Planar Implicit Curves with Topological Guarantees
Authors

Abel J. Gomes
Jose F. M. Morgado
Edgar S. Pereira
Journal / Anthology

ACM TRANSACTIONS ON GRAPHICS
Year: 2009
Volume: 28
Issue: 2
Page range: 17:1-17:24
Description

Mathematical systems (e. g., Mathematica, Maple, Matlab, and DPGraph) easily plot planar algebraic curves implicitly defined by polynomial functions. However, these systems, and most algorithms found in the literature, cannot draw many implicit curves correctly; in particular, those with singularities (self-intersections, cusps, and isolated points). They do not detect sign-invariant components either, because they use numerical methods based on the Bolzano corollary, that is, they assume that the curve-describing function f flips sign somewhere in a line segment (AB) over bar that crosses the curve, or f (A). f (B) < 0. To solve these problems, we have generalized the False Position ( FP) method to determine two types of zeros: (i) crossing zeros and (ii) extremal zeros (local minima and maxima without function sign variation). We have called this method the Generalized False Position (GFP) method. It allows us to sample an implicit curve against the Binary Space Partitioning (BSP), say bisection lines, of a rectangular region of R-2. Interestingly, the GFP method can also be used to determine isolated points of the curve. The result is a general algorithm for sampling and rendering planar implicit curves with topological guarantees.
Subject

*Mathematics
Keywords

Implicit curves, binary space partitioning, numerical algorithms, geometric computing