Page 196 - Geometric Modeling and Algebraic Geometry

11

Subdivision Methods for the Topology of 2d and 3d
Implicit Curves

Chen Liang, Bernard Mourrain, and Jean-Pascal Pavone

GALAAD, INRIA
BP 93, 06902 Sophia Antipolis, France
{mourrain, jppavone}@sophia.inria.fr
Summary. In this paper, we describe a subdivision method for handling algebraic implicit
curves in 2d and 3d. We use the representation of polynomials in the Bernstein basis asso-
ciated with a given box, to check if the topology of the curve is determined inside this box,
from its points on the border of the box. Subdivision solvers are used for computing these
points on the faces of the box, and segments joining these points are deduced to get a graph
isotopic to the curve. Using envelop of polynomials, we show how this method allow to handle
efficiently and accurately implicit curves with large coefficients. We report on implementation
aspects and experimentations on 2d curves such as ridge curves or self intersection curves of
parameterized surfaces, and on silhouette curves of implicit surfaces, showing the interesting
practical behavior of this approach.

11.1 Introduction

In this paper, we address the problem of computing the topology of 3D curves result-
ing from the intersection of two algebraic surfaces. Algebraic curves and surfaces
are compact representations of shapes, which can be complex and have numerous
advantages over parametric ones, such as easy determination of inside/outside of the
surface. This is particularly useful when we have to apply logical operations (union,
subtraction, etc.) between two solid objects, defined implicitly. In such problems,
computing the intersection of two surfaces is a critical operation, which has to be
performed efficiently and accurately. Implicit curves and surfaces have also disad-
vantages such as difficulty in performing graphical display, but the method that we
propose in this paper is step towards handling such problems, since it allows fast dis-
play of this implicitly 2d and 3d curves. On the other hand, dealing with parameter-
ized surfaces naturally leads to the computation of implicit curves. Let us mention in
particular, the computation of the intersection curve of two surfaces, self-intersection
curves, plane sections and ridge curves (which are defined implicitly on these para-
meterised surfaces, though they are usually approximated by parameterised curves).
Such problems reduce to the analysis of a curve defined by n − 1 polynomial equa-
tions, in a space of dimension n (here n =2, 3, 4).