java - Reduce calculations while Raytracing -

i've written own 3d game engine (it took me year) , wanted create raytracer runs on cpu (not gpu!!)

for now, ray tracing process simplified this:

1. cast ray each output pixel.
2. if current ray hits object, set output pixel color "white"
3. otherwise set black

to increase speed of ray tracer, added spherical bounding box each entity. if current ray intersects bounding box, run intersection tests each triangle of entity.

i using quickest methods on ray-triangle-intersection , ray-point-distance still each ray has test every single triangle of each entity might intersected.

as result, takes me on 5 minutes render object (1920x1080) around 10000 polygons , think that's not want.

is there way of reducing amount of triangles need check?

greetings, finn

is there way of reducing amount of triangles need check?

yes.

it sounds scene consists of list of triangles, , you're iterating linearly through list , checking every triangle find closest one. linear search , has o(n) runtime, n = number of triangles.

you can reduce average o(log(n)) time using volumetric kd-trees or bounding volume hierarchies store triangles. personally, prefer kd-trees, either approach works. note bvh typically performs better in animated scenes.

note acceleration structures can contain subtle bugs in how constructed or traversed, you'll want develop way render same scene using naive list approach (for reference image) , structured approach. in hobby tracer, organize this:

abstractscene - base class scene types. code interacts abstractscene fields , methods.

kdscene - derived class implements scene kd-tree.

bvhscene - derived class implements scene bvh.

naivescene - derived class implements scene list of triangles.

there other acceleration structures grids (aka voxels).