Transcript Q - Loria

Robust Intersection of
Two Quadric Surfaces
Laurent Dupont - Daniel Lazard - Sylvain Lazard - Sylvain Petitjean
Loria (Univ. Nancy 2, Inria, CNRS) - LIP6 (Univ. Paris 6)
UNIVERSITE
PIERRE & MARIECURIE
Given: P and Q, quadric surfaces (ellipsoids, hyperboloids,
paraboloids,...) with rational coefficients.
Problem: Find a parametric form for the intersection of P and Q.
Applications:
- Boundary evaluation (CSG to Brep)
- Convex hull of quadric patches
Previous work: J. Levin (1976)
In affine space, find a simple ruled
quadric R in the pencil R() = P- Q,
 real, such that  is a solution of the
degree 3 equation det(Ru()) = 0.
 x²+ y²+ z+=0 ( or  =0)
The use of a projective formalism simplifies
the algorithm and its implementation (fewer
types of quadrics, no infinite branches).
In projective space, find a ruled
quadric R in the pencil R() = P-  Q,
 real, such that det(R())  0 and  is
rational.
A rational  can usually be found after computing
an approximation of the roots of det(R()).
P Q = R Q
P Q = R Q
Compute the orthogonal transformation
that sends R into canonical form:
Advantages
Our algorithm
R has rational coefficients.
Using Gauss’ reduction method for quadratic
forms, compute the linear transformation that
sends R into canonical form:
The coefficients of the linear transformation
and , , ,  are rational.
 x²+ y²+ z²+ w²=0
These new parameterizations of canonical
projective quadric surfaces are, in general,
optimal in the number of radicals.
Parameterize R in the local frame.
Parameterize R in its canonical frame.
Ex: hyperbolic paraboloid
 x² -  y² +  z=0, ,  >0
 x
 u + v u - v uv 
 
,
, , (u,v)
 y  = 



2
2
 z


 
Ex: signature (2,2) (corresponds to a hyperboloid
of one sheet or a hyperbolic paraboloid, in affine
space)
Q has rational coefficients in the local frame.
 x² +  y² -  z² -  w²=0, , , ,  >0
T
 x
 
 y   ut +  vs us -  vt ut -  vs us +  vt 
=
,
,
,
z  







  
 
 w
T
2
(u,v),(t,s)
1
Main contributions
Compute the equation of Q in the local frame of R and substitute the parametrization
into this equation.
We get a degree 2 equation in v:
a(u)v²+b(u)v+c(u)=0
where a,b,c are degree 2
polynomials in u.
Solve for v  v (u)
where u is such that b²-4ac 0.
We get a degree 2 homogeneous equation in s,t:
a(u,v)s²+b(u,v)st+c(u,v)t²=0
where a,b,c are degree 2 homogeneous
polynomials in u,v.
Solve for (s,t)  (s (u,v), t (u,v))
where (u,v) is such that b²-4ac  0.
Substitute the solution of the degree 2 equation into the parametrization.
Transform this solution from the local frame to the initial frame.

The coefficients of the parametric form of
P  Q lie in an extension of
which is, in
general, of minimal degree.

In this extension of , the parametric form
does not contain nested radicals.

The exact explicit form of the parametric
solution has manageable size.

Theorem: If P and Q intersect in more than
2 points, then there exists a rational number
such that det(R())  0.