RE: [Algorithms] infinite precision spatial database
Brought to you by:
vexxed72
From: Tom F. <tom...@bl...> - 2003-12-22 03:05:32
|
The 2D version is often called "swizzling" and is used in pretty much all graphics chips to store and access textures. Gets good cache behaviour with locality of reference, whatever the direction of travel. It's almost exactly the access pattern you get by linearly storing the result of a depth-first quad/octree traverse. But it has no advantages beyond good caching (though that is a pretty good advantage). TomF. -----Original Message----- From: gda...@li... [mailto:gda...@li...] On Behalf Of Sven Forstmann Sent: 22 December 2003 02:25 To: gda...@li... Subject: Re: [Algorithms] infinite precision spatial database hm.. it might be possible to encode a 3D-coordinate 1D by using bit-interleaving for integer. but no idea how to make any transformation on this, and if it would be an advantage... as far I know, databases are using this technique too,to keep data better cacheable for multiple key values. So if x,y,z are the coordinates, the bits for the 1D value would be like bit:012345678... val:xyzxyzxyzxyz.. but already 32bit x,y,z integer values would require a 96bit 1D-value. sven Jonathan Henckel wrote: Are you looking for a continuous mapping from 3D to 1D? If so, you won't find it, because it is impossible. Suppose M is the distance between two points in 3D and N is the distance between their images in the 1D encoding. You can ensure that whenever N is small, M is small, but not the opposite. If you choose your neighborhood radius to be N the ratio M/N can be arbitrarily small, so you will need a very dense fog. John Is there a way of encoding a neighbourhood kind of location along with a LOD/magnitude kind of measure in a single binary word (or a text string)? This is only used as a first step in locating/gauging a 3D object (in a bucket, not within a scene graph). Just as a postcode zooms in on a few houses, but an additional number often pinpoints the precise door. This enables us to do away with the position/bounding box triples being used as the primary selection criteria (whether they're SSE2 or not). So the string would be something like "<magnitude><big zone><sub-zone><sub-sub-zone><etc.>" But, ideally, with typical text search patterns, it would be good to utilise them such that if you search for a string containing 'ergt2' you know that it will intersect with a particular zone. Maybe it's better looking at it from another perspective. If you are presenting a scene from a particular magnitude (view frustrum), you are interested in objects that will be visible. However, let's just remove the directional aspect of the view frustrum, and change it to the set of all potential view frustrums from a particular position and at a particular magnitude (assuming that these are the slowest changing aspects of a view). So we get a view sphere. We're interested in all objects in a particular vicinity, but also the magnitude of the interesting object changes according to distance, i.e. we're interested in big objects far away, but not small ones far away, we're interested in small objects nearby, but not microscopic ones. There's also a kind of fog bounding that's likely to go on, i.e. we may not be interested in potentially visible planets or stars far away, because the atmosphere renders them invisible. Similarly, it might be desirable to discount insects even though they're potentially visible, simply because they're not visually important. I'm wondering if there's a code, perhaps similar to Gray code, where locations in the same vicinity share a high degree of similarity in their encoding pattern? In other words, there are no discontinuities in the location code; there are no co-ordinates that change from (99,00,55) to (00,99,54) even though they are neighbours. So the further apart objects are, the less similarity there is in the patterns representing their location. Similarly, the more different in magnitude objects are, the less similar the patterms representing their magnitude are. ------------------------------------------------------- This SF.net email is sponsored by: IBM Linux Tutorials. Become an expert in LINUX or just sharpen your skills. Sign up for IBM's Free Linux Tutorials. Learn everything from the bash shell to sys admin. Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 |