Good Reference for Ray-Object Intersection?

Good Reference for Ray-Object Intersection?

Post by grendelkha » Thu, 17 Jul 2003 10:07:03



I'm in the process of writing my own raytracer, and have run up against a
lack of easily google-able algorithms for ray-object intersection. I got the
bounding-box, sphere and polygon algorithms from a chapter in Glassner's
book, but there must be a reference for bilinear/bicubic patches, NURBS,
subdivision surfaces, maybe even those lightweight point and curve
primitives that RenderMan has. What's the best reference for this?

Also, I'm currently using a linked-list for my geometric database. This
can't possibly be a sane way to implement it; I've been told that I should
use a BSP-tree, but does this mean I have to split my primitives? (I'd
prefer not to have yet another operation that needs to be implemented for
all primitives.) If not a BSP-tree, what do people generally use for their
geometric databases in a modern raytracer, and where can I find a thorough
description of it?

Thanks everyone in advance.

--grendelkhan

 
 
 

Good Reference for Ray-Object Intersection?

Post by Stephen H. West » Thu, 17 Jul 2003 23:30:32



> I'm in the process of writing my own raytracer, and have run up against a
> lack of easily google-able algorithms for ray-object intersection. I got the
> bounding-box, sphere and polygon algorithms from a chapter in Glassner's
> book, but there must be a reference for bilinear/bicubic patches, NURBS,
> subdivision surfaces, maybe even those lightweight point and curve
> primitives that RenderMan has. What's the best reference for this?

For traditional tensor-product patches (NURBS and all
subsets/equivalents), I currently favor the Bezier clipping approach
of Nishita, Sederberg, et al.  presented at SIGGRAPH 90. A brief
description of the algorithm is on the Web at
<http://www-courses.cs.uiuc.edu/~cs319/patches.pdf>.

That said, the general consensus is that tesselation is more
efficient: simply tile the surface with polygons and intersect
those. This gets sticky with trimmed surfaces, as tesselation gets
harder to do right, and can run into problems where the ray hits the
front side of a polygon, but the interpolated normal faces away from
it.

Quote:> Also, I'm currently using a linked-list for my geometric database. This
> can't possibly be a sane way to implement it; I've been told that I should
> use a BSP-tree, but does this mean I have to split my primitives? (I'd
> prefer not to have yet another operation that needs to be implemented for
> all primitives.) If not a BSP-tree, what do people generally use for their
> geometric databases in a modern raytracer, and where can I find a thorough
> description of it?

People use all sorts of space subdivision schemes for
acceleration. You don't have to split primitives to do this; just
include the primitive in every region that it sticks into. What I know
of these schemes is:

1. Hierarchical bounding volumes. Bound each primitive with some
   simple primitive (bounding box or sphere), then lump these together
   and compute bounding volumes. Repeat, getting a tree structure where
   (we hope) most of the model can be ruled out early.

2. Regular grid subdivision. Find the bounding box of the entire
   model, then chop it up into a predetermined number of cells. This
   is a very easy structure to step through, but it will be
   inefficient if many of your primitives are lumped close
   together. Many use a couple of levels of this: divide once, then
   take the densest cells and chop each one into a predetermined
   number of cells.

3. BSP, kd-tree, or octree. This takes the whole volume of the model
   and chops it in a predetermined fashion. For an octree, just divide
   in half along each axis, getting 8 child cells. Sort the primitives
   into each of these and keep subdividing adaptively until you either
   have only a small number of primitives in each cell or you run out
   of memory. The kd-tree is similar, but splits along one axis at a
   time, trying to select a plane that divides the cell evenly to keep
   the tree balanced. I think BSP-tree methods are similar.

4. 5D ray classification. This does a similar adaptive subdivision,
   but in 5 dimensions (3 Cartesian coordinates in space, 2 for ray
   direction). BUt there's an important difference: it subdivides in a
   lazy fashion, so there's no preprocessing step and unused parts of
   the space (which is most of the 5D space) never get subdivided. It
   was presented by Jim Arvo and Dave Kirk at SIGGRAPH 87.

Those are all I can think of; you probably want to browse through old
issues of the Ray Tracing News, available at
<http://www.acm.org/tog/resources/RTNews/html/>.

--
-Stephen H. Westin
Any information or opinions in this message are mine: they do not
represent the position of Cornell University or any of its sponsors.

 
 
 

Good Reference for Ray-Object Intersection?

Post by Just d' FAQ » Fri, 18 Jul 2003 03:04:37




>For traditional tensor-product patches (NURBS and all
>subsets/equivalents), I currently favor the Bezier clipping approach
>of Nishita, Sederberg, et al.  presented at SIGGRAPH 90. A brief
>description of the algorithm is on the Web at
><http://www-courses.cs.uiuc.edu/~cs319/patches.pdf>.

Nishita's site has more detail on Bezier clipping.

<http://www.eml.hiroshima-u.ac.jp/member/jrs/nis/javaexampl/demoBclp.htm>

 
 
 

Good Reference for Ray-Object Intersection?

Post by John Lync » Fri, 18 Jul 2003 03:25:02




Quote:> I'm in the process of writing my own raytracer, and have run up against a
> lack of easily google-able algorithms for ray-object intersection. I got the
> bounding-box, sphere and polygon algorithms from a chapter in Glassner's
> book, but there must be a reference for bilinear/bicubic patches, NURBS,
> subdivision surfaces, maybe even those lightweight point and curve
> primitives that RenderMan has. What's the best reference for this?

For many of your ray(or other object)-object intersection needs:
http://www.realtimerendering.com/int/
 
 
 

1. Ray tracing: ray-object intersection

A simple method for fast ray tracing has occurred to me,
and I haven't seen it in the literature, particularly
Procedural Elements for Computer Graphics.
It is a way to trivially reject rays that don't
intersect with objects. It works for primary
rays only (from the eye).  It is:

Do once for each object:
   compute its minimum 3D bounding box. Project
   the box's 8 corners unto pixel space. Surround the
   cluster of 8 pixel points with a minimum 2D bounding box.
   (a tighter bounding volume could be used).

To test a ray against an object, check if the pixel
through which the ray goes is in the object's 2D box.
If not, reject it.

It sure beats line-sphere minimum distance calculation.

Surely this has been tried, hasn't it?

--
       The ultimate realization: everything is everything. (I should know.)
   Jack Ritter, S/W Eng. Versatec, 2805 Bowers Av, Santa Clara, CA 95051
   Mail Stop 1-7.  (408)982-4332, or (408)988-2800 X 5743
   UUCP: {pyramid,mips,vsi1,arisia}!versatc!ritter

2. FS: LW 5.5, books & Oxygen 102

3. looking for references on ray tracing and volume intersection

4. line intersection

5. Read my thesis (ray object intersections) -- my reaction

6. For all you guys screaming about LW 4 Linux

7. Read My Thesis! Ray-Object Intersections (Raytracing)

8. Summary of replies to vectorizing ray-object intersection query

9. Vectorizing ray-object intersection calculations

10. Read my thesis (ray object intersections) -- my reaction

11. Read My Thesis! Ray-Object Intersections (Raytracing)

12. how to implement ray intersection to detect object