## ray with bicubic patch intersection problem

### ray with bicubic patch intersection problem

Time for a hard problem.  Anyone have a great idea on how to compute the
a ray intersection with a general bicubic patch?  The methods I've found in
papers so far tend to be very slow.  Seems like most papers take one of two
approaches:

1. Sub-divide the patch in many small polygons and ray-trace that.  Works
but when you have thousands of patches you can end up with millions of
polygons.

2. An Iterative numerical approach, chosing a x,y,z point on the ray and
checking to see if it intersects the patch by using the x,y,z values
in the system of equations given by the four cubic equations forming
the patch.  This of coarse normally requires many trys.

Does anyone have any better ideas?

Thank you,
Wayne Knapp

### ray with bicubic patch intersection problem

Quote:>Time for a hard problem.  Anyone have a great idea on how to compute the
>a ray intersection with a general bicubic patch?  The methods I've found in
>papers so far tend to be very slow.

Check out the book "An Introductiron to Splines for use in Computer
Graphics & Geometric Modeling", by Richard H. Bartels, John C. Beatty,
and Brian A. Barsky. (Morgan Kaufmann Publishers, 1987).  It has
a section entitled Ray-Tracing B-Spline Surfaces (p. 414).  It goes into
several steps to speed up the intersection:

(I have not read this yet.  I'm summarizing as I read.)

1.  Refinement Preprocessing - This breaks the image down into
many smaller splines.  Each spline covers several 100 pixels.
2.  Tree Construction - Break the new (smaller) spline into a bunch
of boxes, starting with one box for the whole spline, then
break that down (put all this into a tree).  Intersection
with boxes is easy.  You can find out which of these
boxes (check only the leaves of the tree) intersects the ray.
This will give you the starting point for Newton's iterations.
3.  Do newton's iteration to find the exact distance.

I'm sorry if I've made any errors in the above description.  You're
going to have to get the book, of course, to implement it.  I'm going to
implement it in my own ray-tracing program in the next few weeks, so
I'll post the source if anyone is interested.  It seems like a
complicated algorithm, but it may speed things up quite a bit.

### ray with bicubic patch intersection problem

Well, there is another solution to this problem which people haven't fleshed
out a great deal: generate triangles and raytrace those.

I hear groans from the audience, but let me put forth the following reasons:

1.      ray/bicubic patch intersection IS floating point intensive.  The
best figures I have seen quote around 3K floating point operations
per ray/patch intersection.  I have a hard time believing you
couldn't do better with a good hierarchy scheme + good triangle code.

2.      Even if you can convince me that your bicubic patch intersector
worked faster than my combination, dicing into triangles is very simple
and easy to implement.  The same code could also be used to generate
views of nearly any parametric surface with minimal modification.

There are (of course) some difficulties.  You would like to subdivide
appropriately, which means being careful about silhouette edges and shadow
edges.  Barr and Von Herzen had an excellent paper in the 1989 siggraph to
illustrate how to implement subdivision.  You might want to check it out.

(Of course, all this is moot, cuz I never HAVE managed to implement
real ray/patch intersection code)

Mark

### ray with bicubic patch intersection problem

Quote:

> Time for a hard problem.  Anyone have a great idea on how to compute the
> a ray intersection with a general bicubic patch?  The methods I've found in
> papers so far tend to be very slow.  Seems like most papers take one of two
> approaches:

>     1. Sub-divide the patch in many small polygons and ray-trace that.  Works
>        but when you have thousands of patches you can end up with millions of
>        polygons.

>     2. An Iterative numerical approach, chosing a x,y,z point on the ray and
>        checking to see if it intersects the patch by using the x,y,z values
>        in the system of equations given by the four cubic equations forming
>        the patch.  This of coarse normally requires many trys.

I did my MS thesis on comparing techniques #1 and #2.  #1 was definitly the
winner, both in terms of speed and robustness.  #2 requires root finding,
which can have convergence problems (not finding a root, finding the wrong
root, etc).  Also, it performs the surface evaluation (which is expensive)
in the very inner loop of the ray tracing process where it is executed
literally billions of times for a complex image.

Reducing to polygons first allows the ray tracer to deal strictly with
simple, fast and stable linear math.  It also does the surface
evaluation (to generate the polygons) only once as a pre-process.
Once the polygons are generated, there are several very effective
schemes for reducing the ray-surface search problem for large
quantities of small, simple primitives (e.g., octrees, bounding volume
trees, 5D space, etc).

For the*details, see "PRT - A System for High Quality Image Synthesis
of B-Spline Surfaces", MS Thesis, University of Utah, 1988.

Cheers,
jp

### ray with bicubic patch intersection problem

Quote:C Knapp) writes:

|>
|> Time for a hard problem.  Anyone have a great idea on how to compute the
|> a ray intersection with a general bicubic patch?  The methods I've found in
|> papers so far tend to be very slow.  Seems like most papers take one of two
|> approaches:
|>
|>     1. Sub-divide the patch in many small polygons and ray-trace
that.  Works
|>        but when you have thousands of patches you can end up with
millions of
|>        polygons.
|>
|>     2. An Iterative numerical approach, chosing a x,y,z point on the ray and
|>        checking to see if it intersects the patch by using the x,y,z values
|>        in the system of equations given by the four cubic equations forming
|>        the patch.  This of coarse normally requires many trys.
|>
|> Does anyone have any better ideas?
|>
|>                                          Thank you,
|>                                            Wayne Knapp
|>
last summer Tom Sederberg (Brigham Young U.) gave a seminar here at
SGI and he spoke *very breifly* on a fast algorithm for ray-tracing
patches.  The work was still in progress, but I wouldn't be suprised
if his up-coming paper at Siggraph this year was the completed result.
You will probably be able to get the correct info from the paper, if
you can wait until August.

He showed us in image with 100's of teapots (28 patches each)
raytraced in ~20 minutes on a Personal Iris.  (Well, the numbers are
very approximate, but I remember it was impressive.)

I don't remember the details of the algorithm, but I do remember it was
pretty simple and very elegant.  He was able to narrow the ray/patch
intersection down to a sub-region(s) (in u-v) of the patch by examining the
ray.  The possible intersection area was then defined as a new patch.
After a few iterations, the intersection area was very small and the
actual intersection could be approximated by any point in the area.

(my appologies to Tom if I've totally mangled his algorithm.  Maybe he
will post a pre-view of the paper.)

Robert Skinner

"Everything under the sun is in tune,
but the sun is eclipsed by the moon."

### ray with bicubic patch intersection problem

>Well, there is another solution to this problem which people haven't fleshed
>out a great deal: generate triangles and raytrace those.
> [deleted]
>There are (of course) some difficulties.  You would like to subdivide
>appropriately, which means being careful about silhouette edges and shadow
>edges.  Barr and Von Herzen had an excellent paper in the 1989 siggraph to
>illustrate how to implement subdivision.  You might want to check it out.
> [deleted]
>Mark

Another problem which I haven't seen solved is subdivision for
reflections or transmissions which magnify the surface intersection
of this secondary ray.  For example, what is a suitable subdivision
algorithm for surfaces seen through a magnifing glass?  Adaptive techniques
that use gradient differentials can generate gillions of uneeded polygons.
Also the continuity you lose by approximating surfaces with triangles for
curved objects with more than one transmitting surface (like a bottle,
or thick glass) can cause some pretty horrible arrifacts.  If it is
important to avoid these problems the only way I know that you can do
it it with ray-surface intersection.

-thaw-

---
Thomas Williams
{ucbvax|sun}!pixar!thaw
---

### ray with bicubic patch intersection problem

Quote:>Another problem which I haven't seen solved is subdivision for
>reflections or transmissions which magnify the surface intersection
>of this secondary ray.  For example, what is a suitable subdivision
>algorithm for surfaces seen through a magnifing glass?  Adaptive techniques
>that use gradient differentials can generate gillions of uneeded polygons.
>Also the continuity you lose by approximating surfaces with triangles for
>curved objects with more than one transmitting surface (like a bottle,
>or thick glass) can cause some pretty horrible arrifacts.  If it is
>important to avoid these problems the only way I know that you can do
>it it with ray-surface intersection.

The problems you list are legitimate.  However, I would counter with the
following arguments:

1. How often do scenes which have magnifications through reflection or
refraction REALLY occur.  The answer to this question for me was: never.
Much more difficult is to solve problems with shadow edges, which can
project edges which are irritatingly linear.  Two things will help
soften/alleviate problems which shadow edges:

a.      using distributed raytracing to implement penumbras.
fuzzy boundaries can be more piecewise without causing
noticeable effects.
b.      We can help eliminate artifacts by treating light sources
specially, and subdividing on silhouettes with respect
to the light source as well as the eye.

2.  Remember, your screen has on the order of 1M pixels.  Each patch
will probably cover only a vanishingly small fraction of these pixels.
If a patch covers 100 pixels, any subdivision beyond 10x10 is probably
overkill.  Use expected screensize as a heuristic to guide subdivision.

Mark

### ray with bicubic patch intersection problem

Quote:>2.  Remember, your screen has on the order of 1M pixels.  Each patch
>will probably cover only a vanishingly small fraction of these pixels.
>If a patch covers 100 pixels, any subdivision beyond 10x10 is probably
>overkill.  Use expected screensize as a heuristic to guide subdivision.

Don't forget problems with areas of high curvature.  Especially
animated sequences where specular highlights "dance" on sharply curved
edges.  A hybrid approach works might work well expect that you had better
have a _lot_ of memory for all the polygons you generate.  Thrashing brings
the fastest machines to their knees. So, I still think there is a place for
ray-surface intersections.

Of course, I guess which approach you take depends on the audience your
playing to.

-thaw-

---
Thomas Williams
{sun|ucbvax}!pixar!thaw

### ray with bicubic patch intersection problem

>edges.  A hybrid approach works might work well expect that you had better

:0)
Yow!  My brain must have been thrashing when I posted this!  It should
have read:

A hybrid approach might work well but, you had better have ....

-thaw-

---
Thomas Williams
{ucbvax|sun}!pixar!bozo

Hi, it's me (again?)

I'd like to know if there was a simple (and slow, I don't care) algorithm to
develop, which would take a line, and the parametric representation of a
bezier patch (= bicubic patch), and which would return the intersections
(like a list of (u,v)) if they exist.

Any idea where I can find some informations?

I read about someone called Kajiya's method, and others, but I can't find
much information about how to use them, and I'm afraid they're a bit
complicated (I say it again: I'm not looking for speed at all)

nb: I don't want to use a subdivision method (got my reasons :p)
thx in advance for your help, if any