Spatial hasing back

(L) [2007/10/11] [bitshit] [Spatial hasing] Wayback!

Hi all,


I recently came across this paper about spatial hasing as an alternative to spatial hierarchies:

[LINK http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf]


It sounds as it could be applicable to rtrt too, has anyone ever considered using spatial hashing instead of BVH and KD's ?


Martijn

(L) [2007/10/11] [jogshy] [Spatial hasing] Wayback!

Interesting paper!

Nop, personally I have been implemented only uniform grids, BV and KDs.
_________________
I know I ask too much... but i'm on panic mode and there is no panic button to press [SMILEY stick out tongue]

(L) [2007/10/11] [Kletterer] [Spatial hasing] Wayback!

Hi there -


At first it does seem like an interesting idea, however, you could consider a uniform grid for ray tracing to be a perfect hashing scheme with a near-zero time hash function.  


I suppose there could be some aspect of the hashing scheme that I am missing that would make it better than uniform grids?

(L) [2007/10/12] [lycium] [Spatial hasing] Wayback!

yes, you don't need to store every voxel, just the ones which contain geometry. i haven't looked closely at the paper but i did try this some years ago (2004 iirc) when i was first learning about hashing, basically i just popped the occupied ugrid voxels into a hashtable, using some very simple double-hashing scheme; it was a lot slower than my (so-so) k-d tree implementation, so i quickly forgot about my "silly idea".


btw, welcome to the forums :)

(L) [2007/10/12] [bitshit] [Spatial hasing] Wayback!

Well I've been googling some more on spatial hashing and raytracing, but couldn't find much... This could mean two things; that it is a stupid idea or noone really bothered trying it out [SMILEY Smile]

(L) [2007/10/24] [sig] [Spatial hasing] Wayback!

Interesting approach.


To what i see, it could be modified to not using a grid, but using a projected grid to eye-space coordinates.

Then we can have 2-dimensional grid, where each cell containing list of objects intersecting with given screen cell. And also, since we project anyways, we can store a z-index as well.


So, each frame we iterating through each object in scene, clipping by frustum, and everything that inside a frustum going to cells of our table.

For each ray we already know, from what cell we need to start and given a z-index we simply looking for first intersection with object from nearest to farthest.