468,513 Members | 1,881 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,513 developers. It's quick & easy.

Efficient implementation of spatial occupancy grid

Hello,

I'm working on mapping the car's environment by updating an occupancy
grid. An occupancy grid dicretizes the 3D space in small grid elements
(voxels). A grid element contains informations about the space it's
representing.

I need to map a space of the dimensions 50m * 5m * 3m with grid
elements of size 1cm * 1cm * cm (= 750 000 000 grid elements).

My question is how to implement such a data structure in an efficient
way. I need to access fast by indizes. Access by iterators is not
needed. The implentation has to be dynamic because of the iterative
mapping process.

My idea was to store all voxels in a long std::vector<doubleand let
pointing a kd-tree's leafs on the vector elements. But this would have
the drawback that the kd-tree has to be reorganized during the update
process to avoid a degeneration to a linear list.

Does anybody has an other idea? Or exemplary code?

Best regards,

Marco Körner
Feb 13 '08 #1
2 3892
On Feb 13, 8:38*am, "Marco Körner" <marcokoer...@gmx.dewrote:
I'm working on mapping the car's environment by updating an occupancy
grid. An occupancy grid dicretizes the 3D space in small grid elements
(voxels). A grid element contains informations about the space it's
representing.
I recently did something similar to this in 6D where I used my own
datastructures.
I need to map a space of the dimensions 50m * 5m * 3m with grid
elements of size 1cm * 1cm * cm (= 750 000 000 grid elements).
Does every element in the grid contain data? In my case they didn't,
and I found a sparse matrix was the best data structure to use.
My question is how to implement such a data structure in an efficient
way. I need to access fast by indizes. Access by iterators is not
needed. The implentation has to be dynamic because of the iterative
mapping process.
I'd consider a 3D matrix or 3D sparse matrix. I've not used them, but
google shows there are some free implementations.
My idea was to store all voxels in a long std::vector<doubleand let
pointing a kd-tree's leafs on the vector elements. But this would have
the drawback that the kd-tree has to be reorganized during the update
process to avoid a degeneration to a linear list.
Are there any advantages to using a kd-tree that can't be done by
indexing a 3D matrix (this is a genuine question)?

Saul
Feb 13 '08 #2
Hi Saul,

thank you for your reply.

On 13 Feb., 13:18, shaz...@gmail.com wrote:
On Feb 13, 8:38*am, "Marco Körner" <marcokoer...@gmx.dewrote:>
I'm working on mapping the car's environment by updating an occupancy
grid. An occupancy grid dicretizes the 3D space in small grid elements
(voxels). A grid element contains informations about the space it's
representing.

I recently did something similar to this in 6D where I used my own
datastructures.
I need to map a space of the dimensions 50m * 5m * 3m with grid
elements of size 1cm * 1cm * cm (= 750 000 000 grid elements).

Does every element in the grid contain data? In my case they didn't,
and I found a sparse matrix was the best data structure to use.
Yes, normally it does. I would like to implement a probabilistic
approach, so every grid element is initialized with probability 0.5.
My question is how to implement such a data structure in an efficient
way. I need to access fast by indizes. Access by iterators is not
needed. The implentation has to be dynamic because of the iterative
mapping process.

I'd consider a 3D matrix or 3D sparse matrix. I've not used them, but
google shows there are some free implementations.
My idea was to store all voxels in a long std::vector<doubleand let
pointing a kd-tree's leafs on the vector elements. But this would have
the drawback that the kd-tree has to be reorganized during the update
process to avoid a degeneration to a linear list.

Are there any advantages to using a kd-tree that can't be done by
indexing a 3D matrix (this is a genuine question)?
I don't know. My idea was to create a grid element if it's not
allready stored in the vector. The kd-tree would be used to find and
access each grid element in logarithmic time O(log N) instead of
search linear through the vector of grid elements in O(N). The
advantage would be, that I just manage cells I've previously touched.
Queries for all other grid elements would return the initial value.
Feb 13 '08 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

reply views Thread by Michele Locati | last post: by
reply views Thread by Kiyoung Yang | last post: by
reply views Thread by Gijsbert Noordam | last post: by
2 posts views Thread by Belinda | last post: by
2 posts views Thread by peter.prib | last post: by
3 posts views Thread by san1014 | last post: by
1 post views Thread by yneeraja | last post: by
reply views Thread by NPC403 | last post: by
1 post views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.