map representation
**Map Representation** defines the **fundamental spatial data structure that a robotic perception system or autonomous vehicle uses to mathematically encode, store, and continuously update its internal geometric model of the surrounding physical world — with each representation format offering radically different trade-offs between memory efficiency, surface reconstruction quality, query speed, and compatibility with downstream planning algorithms.**
**The Core Representational Formats**
1. **Point Cloud**: The rawest, most direct output of a 3D sensor (LiDAR, depth camera). A point cloud is simply an unordered list of millions of individual $(x, y, z)$ coordinate tuples floating in three-dimensional space.
- **Advantage**: Captures the precise geometry of every laser return. No discretization error.
- **Catastrophic Weakness**: A point cloud is just a scatter of dots. It contains zero surface information — you cannot determine if two adjacent points belong to the same wall or represent opposite sides of a thin object. Reconstructing a continuous surface for collision checking requires expensive post-processing (Poisson Reconstruction, Ball Pivoting).
2. **Voxel Grid / OctoMap**: The 3D equivalent of a bitmap image. The entire world volume is subdivided into a regular three-dimensional grid of tiny cubes (voxels). Each voxel stores a binary occupancy state (occupied = 1, free = 0) or a continuous occupancy probability.
- **Advantage**: Trivial collision checking — simply query whether a voxel is occupied. Compatible with volumetric path planners.
- **Catastrophic Weakness**: Memory consumption scales cubically with resolution ($O(n^3)$). Mapping a $100m imes 100m imes 10m$ space at $1cm$ resolution requires $10^{11}$ voxels — utterly impossible. OctoMap alleviates this using a recursive Octree structure that only subdivides occupied regions, achieving massive compression of empty space.
3. **TSDF (Truncated Signed Distance Function)**: Each voxel stores not a binary occupancy flag, but the signed distance to the nearest physical surface. Positive values indicate free space in front of the surface, negative values indicate the solid interior behind the surface, and zero marks the exact surface location.
- **Advantage**: Produces extraordinarily high-quality surface meshes via Marching Cubes extraction. Naturally fuses multiple noisy depth observations into a smooth, consistent model.
- **Usage**: The backbone of KinectFusion and most real-time 3D reconstruction systems.
4. **Surfel (Surface Element)**: Each measurement is stored as a small oriented disk (a "surfel") in 3D space, defined by its position $(x, y, z)$, surface normal vector $(n_x, n_y, n_z)$, radius, and optionally color.
- **Advantage**: Efficient for large-scale outdoor environments (ElasticFusion). No fixed-resolution grid needed. Naturally represents surface orientation, enabling photorealistic rendering and illumination calculations.
**Map Representation** is **the world's file format** — the architectural decision determining whether a robot perceives reality as a cloud of disconnected dots, a rigid grid of cubes, a smooth mathematical field, or a mosaic of oriented disks.