Quote:Original post by Raghar
Spanish moss is often better.
I never heard of that one. Could you elaborate?
Octrees
I never heard of that one. Could you elaborate?
Quote:Original post by TachikomaDon't feel bad, no one else has either!Quote:Original post by Raghar
Spanish moss is often better.
I never heard of that one.
Quote:Could you elaborate?Apparently it refers to what's described here: http://mindprod.com/jgloss/hangingmoss.html
What's described therein is just a uniform grid and a not particularly clever algorithm for finding the point in a set of points closest to a given query point.
The "hanging/Spanish moss algorithm" is likely to work okay for point sets that are reasonably uniform, but will fail miserably on others. For nearest-point queries of this kind, a k-d tree is generally the data structure of choice and the nearest-neighbor algorithm on a k-d tree is described in e.g. the original paper on k-d trees (link is not quite to the original paper, but a tech report version of same). Of course, you don't need to use the algorithm on a k-d tree; you could equally well use it on e.g. a uniform grid (or an octree, perhaps linear), and it would perform much better than that mossy algorithm.
Edit: added missing quote in URL, thus fixing funny formatting.
[Edited by - Christer Ericson on January 12, 2007 2:05:29 AM]
Thank you, that makes more sense now! :)
(I'm also investigating various space partitioning methods for my future implementation.)
(I'm also investigating various space partitioning methods for my future implementation.)
Quote:Original post by Christer EricsonApparently it refers to what's described here: http://mindprod.com/jgloss/hangingmoss.html
What's described therein is just a uniform grid and a not particularly clever algorithm for finding the point in a set of points closest to a given query point.
Actually it's an implicit grid, it doesn't need to be uniform. (as long as there is a working mapping function) Inside of each node of the grid is a structure with real objects, or whatever programmer wants. In fact it could have a different structure in each node, like quadtree, BSP tree, patricia trie, arrays of sorted objects.
Now the main advantage is: loading data from HD into RAM is straightforward and nice for cache. In fact it works wonders for continuous worlds.
Have you ever tried to create a destructible terrain?
Quote:Original post by RagharNo, what is described on that page is exactly what I said: a uniform grid. Furthermore, each grid cell contains a linked list of the objects mapped to that cell. These two observations follow immediately from the statement "The heads of each of the grid chains live in a matrix" (as well as from other statements on that page).
Actually it's an implicit grid, it doesn't need to be uniform.
An implicit grid has no explicitly dedicated per-cell storage. Therefore, what is described on that webpage could not possibly be an implicit grid as the use of the word "matrix" ascertains he's talking about explicit storage.
Quote:Original post by Christer Ericson
You should just search for "location code" but, in short, a location code is a "street address" of a node in an octree/quadtree. You can form the location code in several different ways, but a simple one (for this particular purpose) is to concatenate, each time you move to an octree cublet, three bits representing which cubelet you moved to (000, 001, through 111). These are concatenated into a bitstring that's initially 1, so as not to lose leading zero bits if your first move is to e.g. 010.
I've done some experimenting.
A slight variation on this removes the need for the root '1' prefix
childNodeKey = (thisNodeKey << 3) + i;
where i = 1..8
In your method, i = 0..7, creating the need for a that root stop bit.
This matches my previous array-based implicit tree methodology.
The advantage is that without the root stop bit, you can move between a hash-based strategy and an array-based strategy without changing the key.
The upshot is that for the nodes near the root (say up to depth 6) you can work directly off an array, avoiding any hashing. Since the nodes near the root are accessed the most when doing queries, it might make sense to avoid both the hashing and random memory accesses involved at the top levels.
It certainly seemed to have a performance impact on my test algorithm (nearest neighbor query) which was seeded with a uniform distribution of random points in 3-space. This was with managed code under .NET 2.0 using the generic hash table so milage may vary.
Probably premature optmisation on my part.. but thats more or less what I do! :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
