Archived

This topic is now archived and is closed to further replies.

Deebo

Realtime Raytracing

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Suppose there are 2 objects (A and B).
When i construct a BSP tree.

- Do for A then B
- Merge them both.

or

- Merge A''s faces and B''s faces
- Construct the tree.

Which one is better? or another way?

Now, in topic.
From above, if A and/or B move, do i have to reconstruct tree?
or another way?

In my compinion, maybe uses divide and conquer to partition the screen for ray-tracing.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites