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."