The goal of this project was to port my existing map data structure from a uniform occupancy grid to a uniform octree. The existing framework takes a CSV representation of sonar data and generates a map from it based on the location of the robot at the time of collecting the data. When generating lage 3D maps and using over 200 particles, the memory usage was exceedingly high (>2 GB). By using an octree, we can cut back on the memory usage which in turn would allow for higher resolution maps.
The existing data struture used a uniform occupancy grid where the size was fixed by the set resolution and dimension. The occupancy grid was allocated at the start of the program as a standard 3D array. The problem with this is that memory is allocated for all the cells in the map even is the cell is never used. This because a problem when the map generated is organically shaped which caused an excess of unused cells.
Using an octree fixes this problem because now memory is allocated on the fly when needed. This is very efficient and and allows for a more flexible environment and finer resolution.
Before compiling, the resolution of the octree is defined based on the desired cell size and dimensions (although the dimensions should not be a limiting factor). A maximum depth is calculated using the equation:
As cell positions are calculated in the global frame based on the position of the robot at time of data collection, the cells are added to the map as probabilities represented with unsigned shorts. The map is drawn using OpenGL and a DFS algorithm that traverses the octree and draws occupied leaves with a white color thats intensity is directly related to the probabilities of that cell with a solid white cell being very likely of a wall.
The sonar data used comes from a cistern at the Malta's National Archives in Mdina, Malta. There were 40 horizontal 2D scans where each beam in a scan extends 5 meters and contains anywhere from 170-192 bins, which comes out to ~3 cm/cell on average. This resolution was used in generated the size of our map. The dimensions set for the map were 5m x 5m x 5m, but the data covers about 3m x 3m x 6m. The images above in the gallery are the resulting images.
I also explored an alternate method by using a hash map to store the data. The key was the x,y,z of the cell and the value was the probability of the cell. An image of this map can be seen in the gallery as well as the results are found below.
Octree numbers:
1 particle
Runtime: 127.521 s
Number of elements in Octree: 64,340
Size of application in memory: 71,056 KB
Cell size of 0.03 m/cell
Hash Map numbers:
1 particle
Runtime: 163.47 s
Number of elements in Octree: 99,544
Size of application in memory: 51,540 KB
Cell size of 0.03 m/cell
The octree ran faster than the hash map which is probably due to the octree having to rehash the map when it gets too large as well as probing occurring. There is also some bug in the insertion part of the octree (at least I think that is where it is) since the number of elements is different when ran using my octree. I believe this is related to the way I bin the cells. The octree map also looks to have casting/rounding issues since the cells are grouped together more. This is largely due to my positions of the cells being integers (non-floating point)