About a year ago, I started on a game engine that uses raytracing for the graphics. I have a LOT of code now and I am writing the raytracer. Now I need to know what kind of partitioning algorithm will be fastest for raytracing. BSP or Octrees? Is there more than these two? Are there any web-sites on this subject?

Look here: http://www.flipcode.com/harmless/

Second issue, I suppose...


... no magic ... just coding

I believe an Octree but I''m really not sure. The nice thing about an Octree is that you would always check your ray against an axis aligned bounding box, which is an extremelly easy and efficient check. A BSP tree on the other hand created irregularly shaped cell''s (although I believe you can use a BSP tree to exactly emulate an Octree).

An Octree btw is a subset of BSP Tree''s (although some people say the other way around). They are both virtually the same speed by the way pre-processing (it''s an offline process), but it really depends on your implementation. Um, you could use a portal too (flipcode has a great article on those as well), but that''s really only good for very enclosed area''s (lotsa rooms).

If I were you I''d go for the Octree (I have a tutorial on intersecting a line with an Octree on my Website, www.CodeFortress.com). Use a BSP tree though if you are going to be using mostly interior area''s though.

Right now I am using Quake 3 maps until I can make my own map format. Once I do that, my levels will be outdoor/indoor. Thanks for the help.

There's another partitioning based on a uniform set of voxels, pioneered by ARTS: Accelerated Ray Tracing System. Each ray is essentially processed via a 3DDA, a 3d version of a 2d line rasterizer.

Ultimately though, hybrids are best, drawing the best elements from all partitioning methods for each type of primitive where appropriate.

Height fields are best processed with grid tracing to start. Octrees can be placed in voxels, etc.

[edited by - bishop_pass on June 9, 2002 4:40:11 AM]

Can you explain it a little more. I know what voxels are but HOW can they be used to speed up ray-triangle intersection test?

Divide and conquer would work but will be too much subdivision and preprocessing for real-time raytracing. I decided to simply load triangle data into an octree, put bounding boxes around triangles, and do simple math to get intersections.