koobas.hobune.stream
Raytracing through an octree?
Some background...
I have a bunch of sprites in 3D space. They turn to face the camera, and also change size with distance from the camera. Think placemark icons in Google Earth: http://3.bp.blogspot.com/_z7-vhCWfk-w/SpPydh_fI_I/AAAAAAAAAHU/doIRYZvunjg/s1600-h/colsize.jpg
I want to determine when the user is hovering their mouse over a sprite, and I want to do it very quickly, because I can easily have 20,000+ sprites. I haven't found any way to just apply a collider to each point without murdering framerate. I also can't just linearly check all the sprites in a row - since the calculation time linearly increases, that really only works up to a couple thousand sprites with my most pared down algorithm.
So the logical next step seems to be to use an octree, which as I understand it is what colliders would be using anyway. To the uninitiated (myself included), an octree is a way to organize your objects in 3D space so you can quickly narrow down the number of objects you need to check based on where you are. The picture in the Wikipedia article pretty much says it all: http://en.wikipedia.org/wiki/Octree
So here's my question:
If I were to use octrees, I would quickly need to find (in order) all of the cells that the ray passes through, out to an arbitrary distance. In other words, I split the space into a bunch of cubes, say 16x16x16; I then want to find all the cubes that the ray passes through.
This is a very common problem, and I've found a number of good papers on it (e.g. http://chiranjivi.tripod.com/octrav.html ). Before I begin, I just wanted to make sure that a) there isn't a demonstrably better way of checking the sprites (kD-trees, BSP, etc.), and b) that someone hasn't already implemented this exact algorithm in Unity, so I don't have to reinvent the wheel.
Just out of interest a linear space mapping can work quite well with a sparse collision grid. Basically mapping the points onto a 2D sparse grid. This makes finding an object O(1) for the grid and O(m) where m is the number of points in the same grid cell. If you're interested I've got a script for it, I use it to keep hundreds of agents apart without using colliders.
How about taking another approach: Render the scene into a Rendertexture, with materials replaced so that other geometry is black, and the sprites in questions are of different colors, corresponding to unique IDs (so one unique color per sprite). Check the pixel under the mouse to see what id the user is hovering over.
I like whydoidoit's and Philipp's suggestions; they'll be simpler to implement.
If you pursue octrees, note that you don't subdivide space evenly into cubes (nodes) that are all the same size. You divide only as necessary to keep the desired number of objects in each node, and objects never span nodes. If you only have one object, you'll only have one node that encompasses the entire space.
So I've run a couple of tests and my approach would work well with 20k things if the following things are true:
The camera doesn't change angle/move often
The objects don't move often
On my mac it costs about 8ms to map 20000 items into buckets so that would be a fairly costly per frame calculation. Obviously if the above conditions are true then this would be spread out over frames. The lookup is almost negligible.
And yes, I'm suggesting mapping things into buckets - there are two approaches:
$$anonymous$$ap them in their screen space
$$anonymous$$ap them in some arbitrary plane space
2 has the advantage of only needing processing when something moves (not the camera). But it does require you to cast a ray through the mapped grid. 1 has the advantage of almost instantaneous lookup, but suffers if the screen position of everything changes every frame.
