0
101 Jan 25, 2013 at 20:42

Hi, im currently working in a very simple C implementation of a Ray Tracer; basically all I have to do is, given a set of triangles and a ray, find out where is the intersection point if it exists. I have some questions regarding the design and handling of some stuff (I’m gonna use a kd-tree to manage the tracing):

1) What is a good way to store the triangles? I made a “Point” structure to store the x, y, z coordinates of a point. Would a Point vector be a good idea?
2) What should the kd-tree structure contain? I’ve read some papers and that could be the set of triangles (and maybe the quantity), the bounding box, the left and right nodes, maybe a leaf flag, maybe some depth indicator. Am I missing anything?

#### 4 Replies

0
165 Jan 25, 2013 at 21:03
1. I’d probably make a triangle struct containing an array of three points, then keep an std::vector of triangles. This allows you to add additional data like normals and UVs later.

2. Rather than storing a list of triangles in every kd-tree node - which will lead to a lot of duplicated data in memory and cache thrashing - I would rather keep all the triangles in a vector, and sort it as you build the kd-tree, so that the triangles in a single node are adjacent to each other in the vector. Then in the node, you can just store the beginning and ending indices where its triangles are in the vector. This will be a trickier data structure to build, but it will be worth it when rendering complicated scenes, as it will greatly improve performance.

It’s also a neat trick to store the kd-tree nodes in an array in a similarly sorted order. The root node is at element 1 (element 0 is unused) and for any given node, if it’s at element N in the array, then its two children are at 2N and 2N+1. So the root is at 1, its children are 2 and 3, their children are 4, 5, 6, and 7, and so on. Keeping the nodes together in an array like this will also yield performance gains. And it removes the need for a node to store pointers to its child or parent nodes.

0
117 Jan 26, 2013 at 01:00

Hello,

1. I oppose to standard 3 point storage. We’re using multiple kinds of storage throughout our ray tracer. For checking ray-triangle intersection and barycentric coordinates computation you want to test ray vs triangle in least instructions possible - we’re currently using Sven Woop’s triangle storage, another good one is Ingo Wald’s triangle storage (google their theses for more information about how to use their triangles).
For shading we already have barycentric coordiates for each intersection, so basically we use only those data needed for shading (normals, texcoords), position of hitpoint can be easily computed.

Our renderer is thus GPU friendly. Our intersection code (and basically all rendering code) is persistent-thread based. We basically have buffer of To-Do rays, we fetch single rays from this buffer on GPU threads, and compute intersection information (storing it to another buffer), when thread computation is finished, fetch another ray, until there are rays left.
Shading code is another kernel taking intersection information buffer and computing resulting color. The kernels can also be run iteratively (generate primary rays -> compute primary rays intersection -> shade primary rays & generate secondary rays -> compute secondary rays intersection -> shade secondary rays -> blend the result -> … -> finished). Everything done completely in several small OpenCL kernels. … This could get you the idea why you could use more different structures, one for triangle positions in some good layout for intersections, another one for shading (normals + UV), etc. - basically you don’t want large structures to gain faster access to memory while actually doing intersection & shading (overally reducing cache misses).

1. It depends - for realtime ray tracers you want your Kd-tree node as small as possible, and accessing as linear as possible. Linearizing tree so left node is at ‘current_node_address + 1’ is also good thing. It should contain whether the node is leaf or interior node, somehow primitives inside (basically you can re-arrange your triangles and store id of 1st triangle and their count), and also splitting plane is important (axis = 1|2|3 and position).

For more information on Kd-tree google for PBRT chapter about them (I think it’s 4th - plus you don’t need to buy the book, this chapter is free afaik). There is huge amount of informations on Kd-trees, BVHs and acceleration structures generally. I could elaborate further, but the book is really a lot better than anything I could write here.

0
101 Jan 30, 2013 at 11:29

@Reedbeta

I would rather keep all the triangles in a vector, and sort it as you build the kd-tree, so that the triangles in a single node are adjacent to each other in the vector.

To make the code simpler, you could just use lists of triangles when you build the KD tree, and build a vector from the lists when you are done.

0
101 Jan 31, 2013 at 01:18

Thanks for the answers, they’ve been very helpful. I’m checking out that PBRT chapter and its full of useful info
I’ll let you know if I have any more doubts.