View Full Version : raytracing question

 YourDaftPunk11 November 2005, 06:52 AMI just learned about vectors and such online and I was looking at raytracing math to see how it is done and a question popped into my head: If you start tracing a ray and you want to see if it intersects a sphere, or plane or polygon there is a nice neat equation that I understand (or kinda understand). But what if you have a large model- for every ray you shoot do you have to test for intersection against all the model's faces till one hits? And, since I'm becoming interested in this, what books should I be looking at? Thanks -shawn
Per-Anders
11 November 2005, 07:05 AM
Basically yes. But that's why you use things like bounding boxes, Voxel Grids, BSP's and Octree's or even Spherical Space in order to speed things up and minimize the number of calculations needed.

As for books, well the Graphics Gems series are worth seeking out, mostly I've found there's enough material online to keep me going :).

arnecls
11 November 2005, 11:49 AM
For beginners "Fundamentals of Computer Graphics" by Peter Shirley is a good choice. Once you've gotten into it, get "Realtime Rendering" (aka. "the bible") by Möller/Haines.

For your question - as mdme_sadie already said - yes, you have to test against (almost) every primitve in your scene. If you want to work with models and not just primitves (like spheres), I would focus on a fast ray/triangle test (described in Realtime Rendering) and a bounding volume hierarchy (BVH) based on axis aligned bounding boxes (ray/aabb test, also described in Realtime Rendering).

As a BVH-generation algorithm I would suggest Goldsmith and Salmon or better still the technique described by Ng and Trifonov (see paper "Automatic Bounding Volume Hierarchy Generation Using Stochastic Search Methods"), but you should not worry about those before you understood the basics of raytracing and space subdivision.
In the first place (for understanding) a list of primitves will work fine, although that's very slow.

playmesumch00ns
11 November 2005, 03:59 PM
As a rule of thumb you should aim to be testing against no more than 3 to 5 triangles each ray, regardless of scene size.

Although obviously different structures perform better in different situations, the best general-purpose acceleration structure for ray-tracing is a kd-tree.

http://www.openrt.de is a great reference for fast raytracing (they're trying to do it in real time), and you can download this year's siggraph RTRT course notes which has some good informatino on building fast kdtrees.

YourDaftPunk
11 November 2005, 04:25 PM
Thanks! Very thorough answers and prompt too!

DIMO
11 November 2005, 01:19 PM
Hi,

This gives a good start for raytracing (With a lot of code and a sample project for download):
http://www.flipcode.com/articles/article_raytrace02.shtml

Best Regards,

Dieter

YourDaftPunk
11 November 2005, 09:57 PM
Thanks Dimo!

CGTalk Moderation
11 November 2005, 09:57 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.

1