What is the fastest way to do raycasting?
I am currently trying to use a depth map to compare depth against z value, however this is not accurate enough :(.
So i need to do about 100,000 – 500,000 ray casts.
Which is fastest?
- RayGridIntersect
- intersectray
- intersectrayex
- meshprojintersect <- what is this one?
The RayGridIntersect is currently the fastest working shipping method.
Intersectray and intersectrayex use no acceleration structure, so they are slow and get slower as mesh complexity increases.
meshprojintersect is relatively fast for finding the closest point on surface and is used by the texture projection system of Max, but its ray casting functionality is officially considered broken (according to its developer), so it should not be used for ray intersections. Also, in my benchmarks it does not scale well at all, and nobody can explain why because it is supposed to use some advanced acceleration structure.
RayGridIntersect uses some basic voxel grid acceleration and can be relatively fast, especially if you care about the DISTANCE to a hit and don’t care about the geometry data. There are methods to get the actual face index, normal and bary coords etc. of the hits, but if you are testing just the distance to a hit, it can save a lot of hassle.
We have an inhouse ray intersection system which leaves them all in the dust (and I am talking orderS of magnitude faster), but it is not likely to be released to public.
oh Bobo, you tease.
ok im testing using RayGridIntersect at 512×512(which is 262,144 casts)
Edit, Total time was 14.8263 mins
What does the voxel grid size do?
In short, the faces of the mesh get registered on a voxel grid. When a ray is cast, it goes through voxels and only considers faces registered in them as potential hit targets to test. So the smaller the voxels, the less faces per voxel will be stored (thus the time to test a voxel would be shorter), but the preparation time and memory consumption would go up. Thus, you have to play with the voxel value to find out what value gives you the best results.
The gridSize value is the number of subdivisions along each axis. The resulting voxels are thus dependent on the size of the meshes’ bounding box. 10 seems to be a good value to start with. This will give you a 10x10x10 voxel grid and shooting a ray along a single axis will intersect only faces registered in up to 10 voxels instead of testing the whole mesh.
Here are some benchmark results of a test with 200K faces geosphere and various methods, number of rays and grid sizes:
–INTERSECTRAY 200K FACES
–100: TOTAL 4390 ms
–1000: TOTAL 44219 ms
–INTERSECTRAYEX 200K FACES
–100: TOTAL 4407 ms
–1000: TOTAL 44156 ms
–RAYMESHGRIDINTERSECT 200K FACES, GRID SIZE 50
–100: TOTAL 735 ms, Grid Building: 438 ms , TOTAL-Tree: 297 ms
–1000: TOTAL 3328 ms, Grid Building: 422 ms , TOTAL-Tree: 2906 ms
–10000: TOTAL 29454 ms, Grid Building: 469 ms , TOTAL-Tree: 28985 ms
–100000: TOTAL 301657 ms, Tree Building: 485 ms , TOTAL-Tree: 301172 ms
–RAYMESHGRIDINTERSECT 200K FACES, GRID SIZE 20
–100: TOTAL 843 ms, Grid Building: 421 ms , TOTAL-Tree: 422 ms
–1000: TOTAL 4594 ms, Grid Building: 422 ms , TOTAL-Tree: 4172 ms
–10000: TOTAL 42219 ms, Grid Building: 422 ms , TOTAL-Tree: 41797 ms
–RAYMESHGRIDINTERSECT 200K FACES, GRID SIZE 10
–100: TOTAL 984 ms, 359 ms Grid Building, 625 ms
–1000: TOTAL 6594 ms, 375 ms Grid Building, 6219 ms
–10000: TOTAL 61766 ms, 375 ms Grid Building, 61391 ms
–RAYMESHGRIDINTERSECT 200K FACES, GRID SIZE 5
–100: TOTAL 1250 ms, Grid Building: 328 ms , TOTAL-Tree: 922 ms
–1000: TOTAL 9672 ms, Grid Building: 312 ms , TOTAL-Tree: 9360 ms
–10000: TOTAL 93875 ms, Grid Building: 328 ms , TOTAL-Tree: 93547 ms
–RAYMESHGRIDINTERSECT 200K FACES, GRID SIZE 1
–100: TOTAL 1375 ms, Grid Building: 94 ms , TOTAL-Tree: 1281 ms
–1000: TOTAL 12782 ms, Grid Building: 94 ms , TOTAL-Tree: 12688 ms
–10000: TOTAL 127516 ms, Grid Building: 110 ms , TOTAL-Tree: 127406 ms
Our internal method does the 100,000 intersections in 844 ms after 4156 ms acceleration structure building. The ray casting scales linearly, so one million intersections took 8,5 seconds. Its speed is limited by the performance of the MAXScript FOR loop though, internally it is a lot faster.
ah okay cool,
Thanks for the benchies btw!
Bobo can you explain at all how your in house system is working then? What it might be doing different? This is just more of a curiosity wondering how some thing like this can get that much faster.
It is based on the kdtree we use to raytrace particles in Krakatoa.
(Edit): I don’t want to take credit for the implementation, since I was not involved in it. I just did the benchmarks. No ketchup involved
it’s like intersection porn, that.
@ harefort: Hihihi
the trick is to do it in N-dimensional space, throw in some Joey’s calamari, add ketchup, lower ambient temperatures to well below -30C, factor the King’s Head into it, and it’s done.
Relatively quicker than any other XD
Jokes apart, wouldn’t explaining it just give it away?
I did use the voxel based raycasting (thanks to Martijn suggestion) to do some mad intersecting on superdense, very big surfaces.
That by itself, tuned properly (there is also the tree traversal time to take into account if the voxel grid is too dense), was extremely quick already, but did not scale linearly, so i had to break down the casting in passes, which is a very minor hassle.
This, for those without a direct access to the krakatoa KDTree code
Thanks guys, I just like to know what is possible, not that I’m ever going to get to trying it myself but I like to try and understand some the ideas that are used.