Find generic item in 1D array based on world position?

Question

I have an array of data (generic vertexdata). I need to be able to search for elements of the array based on a position. Currently, each vertex element records its own position and I simply use a for-loop to search through every element and compare the positions. I have to do this a LOT in my program and it's fairly performance-critical. Looping through every single element seems really, really inefficient.

I using C++, btw.

My question is this: Is there a better way? That is, is there a way of accessing the necessary element directly based on a 3D position? The positions are ints, so that might help.

I thought about simply using a 3D array (ie. vertex[256][256][256]), but I can't afford the wasted memory, since only about 30-50% of the vertex positions actually contain a vertex. Maybe this could be achieved with pointers? Do they use memory when not assigned?

The other problem with a 3D array is that the vertices can be spread across a virtually infinite area, which would make for a very, very large array. Also, the vertices are effectively added dynamically which means they could be added at a <0 position, meaning the array would have to be shifted backwards and every element reassigned.

If anyone has any suggestions, I'd be very grateful :)

Answer 1

A solution you may consider would be to use a sparse grid as your ADT.

The std::unordered_map is a hashed map which can be used to create the sparse grid data structure. If you write a good hash for the 3d-vectors, you can get great O(1) read performance which will get close to the performance of a the raw array.

The hashed map will also allow you to use a "virtually infinite" area as well (of course the constraint would be in the underlying data type.

---

Sorry for the delay.

For unordered_map, this is a good resource for information: unordered_map hash function c++

I implemented in my own project using a pair of ints, but I'm sure that it could be used for three dimensional coordinates.

namespace std {
    template <class T>
    inline void hash_combine(std::size_t & seed, const T & v) {
        std::hash<T> hasher;
        seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
    }

    template<> struct hash<pair<int, int> > {size_t operator()(pair<int, int> x) const { size_t seed=0; hash_combine(seed, x.first); hash_combine(seed, x.second); return(seed); } };
}

And then you can declare your unordered_map

std::unordered_map<std::pair<int, int>, [VALUE] > my_map; //[VALUE] being the data type of vertex

After this, you can treat the structure like a regular std::map. If you are not sure how to use one, there are lots of examples out there.

For 3d coordinates, you can declare your own struct

struct vector
{
    int i,j,k;
};

And then modify the hash function (formatted for readability)

template<> struct hash<vector > {
    size_t operator()(vector x) const {
        size_t seed=0;
        hash_combine(seed, x.i);
        hash_combine(seed, x.j);
        hash_combine(seed, x.k);
        return(seed);
    }
};

Answer 2

Octree is probably best solution to voxel based terrain (or model for that matter). Basic concept of octree consists of nodes and leafs. Each node (and leaf) represent cubical space and each node contains 8 subnodes (or leafs) such that each subnode takes 1/8 of space of its parent (see picture).

Leafs are different from nodes by not having more subnodes but containing the data itself - in your case array of vertices.

The depth of a octree is up to you, it really depends on the level of detail your terrain has. Now if you want to organize your vertices to the tree, for each vertex you will start by sending it to the main node (node which is root of the tree i.e. contains all the other nodes) which will then determine to which subnode the vertex belongs based on a position. The vertex is then passed on recursively until it reaches leaf node where it is stored in array.

For simplicty, here is 2D example with quad tree:

                (4,4)
-----------------
|   3   |   4   |
|       |       |
-----------------
|   1   |   2   |
|       |       |
-----------------
(0,0)

Lets say the size of the terrain is 4x4. In this example we use only the main node as the node containing leaf nodes. If we now have vertex at lets say (0.2, 3.2). Vertex is passed to the root node. since 0.2 < 4/2 and 3.2 > 4/2, the node sends the vertex to the leaf no. 3 where it is stored. If you were searching for a position in a space (or plane in this example), you would do it in similar manner as storing described.

In your implementation you can use pointers represent subnodes/leafs of a node. If you want to optimize for space, you do not have to store dimensions and position of each node at all and instead implitictly say that dimensions of each node are 1x1x1 and then transform each vertex accordingly before you pass it on. I.e. you have terrain of size 1000x1000x1000 and vertex at position (600,600,100). Now you divide the position by the size so you get position (0.6,0.6,0.1) which you pass to the node. Since 0.6 > 1/2 and 0.1 < 1/2 you will pass it to the node accordingly but before you will transform it so it is again by subtracting 1/2 from the high components and then multiplying all components by 2 (as the subnode is twice smaller in all dimensions) to get position (0.2, 0.2, 0.2) which you will pass on...and so on. This bit more advanced however as you need to count on it each time you use the tree.

It is really hard to find tutorials on the internet on the topic but there are many implementations to learn from. Here are couple I found:

http://www.flipcode.com/archives/Octree_Implementation.shtml https://github.com/brandonpelfrey/SimpleOctree

And one actual tutorial (but it is very heavy): http://www.xbdev.net/maths_of_3d/octree/tutorial/