Map Representations
A robot can store what it knows about space in many ways. Raw points are simple but large and unordered. Grids are easy to query. Trees save memory in empty space. Meshes and distance fields describe surfaces directly. Each suits different jobs.
Five ways to store a room
A point cloud is just the measured points: no structure, and no record of free space. A voxel grid, or occupancy grid in 2D, splits space into equal cells marked occupied or free, so lookups are instant but memory grows with the volume. A quadtree, or octree in 3D as in OctoMap, splits cells only where there is detail, saving memory in big empty areas. A mesh stores surfaces as connected faces, ideal for display and contact. A signed distance field stores, in each cell, the distance to the nearest surface, negative inside objects, which makes collision checks and smooth surfaces easy, as used in KinectFusion and in many planners.
What to notice
Halve the cell size and a grid needs four times the cells in 2D, eight times in 3D. The quadtree grows much more slowly, since it only refines near walls. The distance field shades every cell by how close it is to a wall: that gradient is what lets a planner push a path away from obstacles.