mesh partitioning and fast lookup

I am writing a raytracer and I am trying to partition some mesh data (points and faces) so i can calculate intersections.

Currently I for every intersection calculation i have to look up every face and see if the ray intersect with it. I am trying to find a faster way to do that, namely only lookup relevant faces.

What is a good data structure for storing the graph data (kd tree? equally partitioned space?) How can i look up relevant spaces/faces given a ray?

PS: Im using C++

Solution

A spatial partitioning data structure (a BSP tree, a k-D tree or an octree), or even more generally a bounding volume hierarchy (AABB tree) should do the job. See this answer to a related question for the construction of a BSP tree from a mesh and its traversal. The C++ library CGAL provides an AABB tree data structure with the required construction and query.

When did C allow casting constants and variables to struct for assignment?
Why in C can I initialize more values than the size of an array?
Using c to create a file and write+read to it, what went wrong?
Does write system call need the data to be read to give >-1 return?
Difference between fgetc() and read() function in C
How can I get to know the IP address for interfaces in C?
read fails with EFAULT
In this case, how to achieve modularity and information hiding at the same time?
Are global variables always initialized to zero in C?
OpenGL function calls seemingly affecting unrelated data
What Values of Variables x and y Will Produce Incorrect Results When Testing for Overflow After Subtraction of x-y in the Following Program?
How to write a general-type queue library in c?
Which gcc and g++ version support which standard of c and c++?
How to dereference a member in a struct whose definition is not visible?
How to name a type in a meaningful way?
What are Vectors and < > in C?
Why does 1.0/100.0 == 0.1/10.0 give True?
How to organize the receive msg and user current input in C network such that it's clean
Using inclusive scan syntax in OpenMP in the C language
Unable to understand context in book "OOP in C" by Axel Schreiner
variable-length array in struct with TI compiler in C (socket programming)
A faster way to test 32bpp DDBs for a valid Alpha channel
How can I compile the zephyr example-application as a freestanding application?
Why does my forked process sometimes overwrite data in a file?
_Generic in C needs typecasting?
Declaring/defining an unused variable changes the output from an unrelated variable
How to use gdb to explore the stack/heap?
How can I read an input string of unknown length?
Confused by difference between expression inside if and expression outside if
Fast Arc Cos algorithm?