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? Maybe there is another reason? Can a bezier surface be made with an
isosurface?

TIA.

--
Dave.
mic### [at] sympaticoca

Post a reply to this message

David Curtis <spa### [at] junkmailcom> wrote:
: 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?

  Well, the documentation says:

"The keyword type is followed by a float Patch_Type which currently
must be either 0 or 1. For type 0 only the control points are retained
within POV-Ray. This means that a minimal amount of memory is needed
but POV-Ray will need to perform many extra calculations when trying
to render the patch. Type 1 preprocesses the patch into many
subpatches. This results in a significant speedup in rendering at the
cost of memory."

  I understand this to mean that the patch is not converted to triangles if
it's of type 0 (at least at parse time).

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):5;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

On 10 Mar 2000 08:09:29 -0500, Nieminen Juha wrote:
>David Curtis <spa### [at] junkmailcom> wrote:
>: 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?

>  I understand this to mean that the patch is not converted to triangles if
>it's of type 0 (at least at parse time).

True, but it's still converted to triangles at render time.

I think MegaPOV still has the "type 2" bicubic patch, which evaluates the
bicubic directly.

-- 
These are my opinions.  I do NOT speak for the POV-Team.
The superpatch: http://www2.fwi.com/~parkerr/superpatch/
My other stuff: http://www2.fwi.com/~parkerr/traces.html

Post a reply to this message

Ron Parker <ron### [at] povrayorg> wrote:
: I think MegaPOV still has the "type 2" bicubic patch, which evaluates the
: bicubic directly.

  How is this done? How fast is it? Can it be done even nearly as fast as
with triangles?

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):5;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

On 10 Mar 2000 10:51:36 -0500, Nieminen Juha wrote:
>Ron Parker <ron### [at] povrayorg> wrote:
>: I think MegaPOV still has the "type 2" bicubic patch, which evaluates the
>: bicubic directly.
>
>  How is this done? How fast is it? Can it be done even nearly as fast as
>with triangles?

According to the comments, it uses "NSK (Nishita, Sederberg,Kakimoto)"
Whether it's faster or slower is something I've never investigated.  The
code (bezier2.c in the superpatch, presumably also in megaPOV) is also 
riddled with FIXME statements (and the accompanying comments are often
in Czech, as well, making it difficult to determine what needs fixed) 
so I'm not sure how well it all works in the real world.

-- 
These are my opinions.  I do NOT speak for the POV-Team.
The superpatch: http://www2.fwi.com/~parkerr/superpatch/
My other stuff: http://www2.fwi.com/~parkerr/traces.html

Post a reply to this message

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.
There are methods to calculate ray-surface intersections with a sixth-
degree surface, but they are slow and imprecise.  In most cases a bicubic
patch, with u_steps and v_steps set to three, provides just as good an
end product, but renders far more quickly.

Regards,
John

Post a reply to this message

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.

Xander

Post a reply to this message

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?

-- 
ICQ: 46085459

Post a reply to this message

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

Alexander Enzmann wrote:
> 
> 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.

I wrote a macro to generate the triangles for a bicubic bezier, so that
I could use Bezier patches inside of meshes.  The Ant people in one of
my IRTC entries were constructed from meshes done this way.

Regards,
John
-- 
ICQ: 46085459

Post a reply to this message