John VanSickle wrote:
> 
> Alexander Enzmann wrote:
> >
> > John VanSickle wrote:
> > >
> > > David Curtis wrote:
> > > >
> > > > Questions, questions, questions, ...
> > > >
> > > > I've just read from the docs that POV converts the bicubic patch into
> > > > triangles. My question is why? It seems obvious that it must have something
> > > > to do with computation time, and the fact that there is no great advantage
> > > > to spending the time calculating a intersection point for every ray. Does
> > > > that sound right?
> > >
> > > Yes.
> > >
> > > A bicubic patch would have to be represented by a sixth-degree polynomial.
> >
> > 18th degree polynomial.
> 
> I recall the 3.0 docs as saying that it was six.  What's your source
> for 18?

Wrote the Bezier code, didn't write the docs.  Hard to say where the 6
came from.

A few years ago, I spend way too much time trying to find a general way
to implicitize a bicubic patch (although I did get a result for bilinear
patches).  If you start digging you find that a two variable parametric
surface with degree n in one variable and degree m in the other can be
implicitized to a function of degree 2 * n * m.  [Therefore 2 * 3 * 3 =
18.]  Techniques for doing the implicitization are pretty well
understood, but tend to be applied to a single equation with fixed
coefficients, not to an arbitrary one (heaven forbid you move the
control points of your Bezier...).

There are, of course, specialized ways to implicitize things that have
simplifying characteristics.  However, I couldn't find anything to help
in this regard with bicubic Beziers.

After spending time on that (got some big equations from Mathematica if
you are really interested...), I realized that a) direct numerical
solution of that high order a poly wasn't going to be particularly
accurate, and b) Using an initial tesselation to find an approximate
solution, coupled with a few N-R iterations would be way better.

The tesselation/iteration process can be very accurate and reasonably
fast.  Bezier surfaces have a really nice property that the surface is
completely contained within the convex hull of their control points.  By
using the bounding box of the ctl points (yes - it's bigger than the
convex hull) and looking for intersections, you can feed those to the
N-R iterator.  Keep the u/v bounds of the subpatch within the box so you
can ensure the iterator doesn't go too far.  A couple of subdivisions of
the patch are usually enough to ferret out any folds or bubbles in the
surface - leading to a way easier solution.

Xander

Post a reply to this message