From: thinman@netcom.com (Lance Norskog)
Subject: TECH: More on object collisions
Date: Mon, 24 Feb 92 11:27:31 PST



I forgot another point in my previous response on this topic:
object collision must definitely be computationally integrated
into the rendering phase, just as various rendering algorithms
currently mush the distinct tasks of polygon occlusion and polygon
painting into one large arithmetic exercise.

It's possible that the object collision operation can be
expressed as a set of N equations in N unknowns, and can
thus be tackled with well-known methods like determinants.
I don't know the computational requirements; it's probably
not useful for real-time work if implemented in software.
But for this research work, it's important first to
find algorithms with guaranteed predictable running
times, with known worst-case times.  After that,
making it real-time is just a hardware problem.

There's been a project in Japan (the word "Freedom"
is in all their article titles, see "Visual Computer"
sometime in 1988) to build a series of floating point
chips which just do determinants.  The researchers use
these chips to write very fast ray-tracers running on PC's!
Their articles include laundry lists of graphical interaction 
problems expressed as determinants; point-on-line, point-in-sphere,
etc.

A floating point or fixed-point arithmetic unit that did large
arbitrary-sized determinants would be a very useful tool in
a VR hardware setup.  Here's another use: several problems 
in computer graphics and robotics can be expressed by systems
of polynomial equations.  Until recently you had to solve these
systems via symbolic manipulation, which was fantistically slow
and quite error-prone.  Dinesh Manocha did a colloquium
last Friday at UCSC detailing his work (I think with John Canny at UCB)
that allows you to take such an equation set and solve it with linear
algebra using, you guessed it, determinants.  This would also use
a determinant chip.  His benchmarks were vague, but claimed that
robot arm movement problems went from 10 minutes on a 3090
to several milliseconds on an RS6000.

This is all beyond my math knowledge; here's the colloquium description:

Dinesh Manocha from UC Berkeley will speak on:

"NON-LINEAR GEOMETRY AND  LINEAR ALGEBRA"

Many problems in computer graphics, geometric and solid modeling, robotics,
vision, symbolic  and scientific computation are reduced to manipulating
system of polynomial equations.  In particular, sets of equations are used
for object representation and constraints formulation.  Typical applications
include curve and surface intersections, robot motion planning, ray tracing,
cusps and loops detection, inverse kinematics, symbolic elimination and
solving systems of non--linear equations.  Earlier approaches to deal with 
these problems can be classified into symbolic and numeric methods.
Symbolic techniques, like Groebner bases, are too slow and suffer from
numerical accuracy problems in the context of floating point computation.
At the same time numerical methods based on subdivision, iterative techniques
and continuation are far from being robust and slow in practice as well.

In this talk we present multipolynomial resultants and show their
effectiveness for manipulating system of polynomial equations.  The resultant 
is represented in terms of matrices and determinants.  As a result, we 
use algorithms from linear algebra for their application.  These include 
multivariate interpolation and modular computation for symbolic applications 
and Gauss elimination, singular value decomposition and eigendecomposition 
for numeric methods.  Based on multipolynomial resultants we present 
efficient algorithms for implicitizing rational parametric surfaces and 
eliminating a set of variables from a system of equations to obtain a 
symbolically smaller system. We also apply the results to the problem 
of curve and surface intersections and present efficient and robust 
representations and algorithms for geometric and solid modeling systems. 
The technique can also be specialized for ray tracing and detecting cusps 
and loops.  Finally we present a real time algorithm for the inverse 
kinematics of general six revolute and serial manipulators.  Inverse 
kinematics of general six revolute manipulators had been an open problem 
in industrial robotics for more than three decades and had significant 
impact on the design of robot manipulators.  Other applications of inverse 
kinematics algorithm include goal directed computer animation and physical 
based modeling.