CODEWITHSUNDEEP
intersectionraytracingkdtreebounding-volume
Luecx
Luecx

Reputation: 160

Reduce calculations while Raytracing

I've written my own 3D Game Engine (it took me a year) and I wanted to create a Raytracer that runs on my CPU (not the GPU!!)

For now, the ray tracing process is simplified like this:

  1. Cast a ray for each output pixel.
  2. If the current ray hits an object, set the output pixel color to "white"
  3. Otherwise set it to black

To increase the speed of the ray tracer, I added a spherical bounding box to each Entity. If the current ray intersects the bounding box, it will run the intersection tests with each triangle of the Entity.

I am using the quickest methods on ray-triangle-intersection and ray-point-distance but still each ray has to test every single triangle of each Entity that might be intersected.

As a result, it takes me over 5 minutes to render an object (1920x1080) with around 10000 polygons and I think that's not what I want.

Is there any way of reducing the amount of triangles that I need to check?

Greetings, Finn

Upvotes: 0

Views: 404

Answers (1)

Daniel A. Thompson
Daniel A. Thompson

Reputation: 1924

Is there any way of reducing the amount of triangles that I need to check?

Yes.

It sounds like your scene consists of a list of triangles, and you're iterating linearly through the list and checking every triangle to find the closest one. This is linear search and has O(n) runtime, n = number of triangles.

You can reduce this to average O(log(n)) time by using volumetric kd-trees or bounding volume hierarchies to store your triangles. Personally, I prefer kd-trees, but either approach works. Note that BVH typically performs better in animated scenes.

Note that acceleration structures can contain subtle bugs in how they are constructed or traversed, so you'll probably want to develop some way to render the same scene using the naive list approach (for a reference image) and a structured approach. In my hobby tracer, I organize it like this:

AbstractScene - base class for all scene types. Most code interacts only with AbstractScene fields and methods.

KDScene - derived class that implements the scene as a kd-tree.

BVHScene - derived class that implements the scene as a BVH.

NaiveScene - derived class that implements the scene as a list of triangles.

There are also other acceleration structures like grids (aka voxels).

Upvotes: 2

Related Questions