ray with bicubic patch intersection problem

ray with bicubic patch intersection problem

Post by Wayne C Kna » Mon, 14 May 1990 04:56:45



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

Post by Lawrence Kestelo » Tue, 15 May 1990 07:40:46



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

Post by Mark VandeWetteri » Tue, 15 May 1990 23:59:51


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

Post by John Peters » Wed, 16 May 1990 02:55:36



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

Post by Robert Skinn » Thu, 17 May 1990 02:27:56



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

Post by Tom Willia » Thu, 17 May 1990 08:45:52



>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

Post by Mark VandeWetteri » Thu, 17 May 1990 12:44:55


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

Post by Tom Willia » Sat, 19 May 1990 08:45:30


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

Post by Tom Willia » Sat, 19 May 1990 09:05:48



>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

 
 
 

1. looking for a slow bicubic patch / ray intersection

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

2. Thumbnail Images

3. Ray Tracing bicubic parametric patches

4. Really newbie question (slightly long)

5. pov-ray & bicubic patch objects

6. Version differences

7. Bicubic Bezier - Ray intersection

8. ray - bicubic surface intersections

9. problem with bicubic patch in BMRT

10. ray/patch intersection....

11. Intersection of ray and spline patch

12. Ray/patch intersection