LiDAR and Point Clouds

A LiDAR (Light Detection and Ranging) unit fires a short laser pulse and measures the time-of-flight (ToF) until the return arrives at the detector:

$d = \frac{c \cdot \Delta t}{2}$

where $c \approx 3 \times 10^8$ m/s is the speed of light and $\Delta t$ is the round-trip time. A 10 ns timing resolution gives 1.5 m range resolution — too coarse. Modern sensors interpolate the return pulse shape to achieve 2-4 cm range precision. Rotating mechanical LiDARs (Velodyne VLP-16, HDL-64) spin a mirror to sweep multiple laser beams through 360°; solid-state units (Livox MID-360, Ouster OS1) use MEMS mirrors or optical phased arrays. Typical specs: 10-20 Hz scan rate, 0-100 m range, ±2 cm accuracy, 16-128 beams (channels). Sparsity is the fundamental limitation: at 20 m a 16-beam unit has roughly 0.5 m vertical spacing between rings.

A single LiDAR scan produces a point cloud: an unordered set of 3D points $\{\mathbf{p}_i\} \subset \mathbb{R}^3$, each with optional attributes (intensity, ring ID, timestamp). This is fundamentally different from images — there is no regular grid. Two representations dominate in practice:

• Flat array (float32[N, 4] with columns $[x, y, z, \text{intensity}]$): cache-friendly, easy to broadcast; spatial queries are $O(N)$.
• KD-tree (built with scipy.spatial.KDTree or FLANN): $O(\log N)$ radius / nearest-neighbour queries; amortised over many lookups.
• Voxel hash map: buckets space into a 3D grid; $O(1)$ insert and lookup, but memory spikes for large scenes.

For real-time robotics (10 Hz, $N \approx 10^5$ points), the KD-tree rebuild per scan is a bottleneck — prebuilding an incremental variant or using GPU-accelerated libraries (cuPCL) is common.

Raw LiDAR scans are dense near the sensor and sparse far away. Voxel downsampling normalises density: partition 3D space into a grid of cubes of side length $v$, then replace all points inside a voxel with their centroid (or any representative point). This reduces $N$ by 3-10× with minimal loss of structure at the chosen scale $v$.

import open3d as o3d
import numpy as np

# Load raw scan
pcd = o3d.io.read_point_cloud("scan.pcd")
print(f"Before: {len(pcd.points)} points")

# Voxel downsample at 10 cm resolution
down = pcd.voxel_down_sample(voxel_size=0.10)   # metres
print(f"After: {len(down.points)} points")

# Estimate surface normals for ICP / segmentation
down.estimate_normals(
    search_param=o3d.geometry.KDTreeSearchParamHybrid(
        radius=0.3, max_nn=30
    )
)

Choosing $v$: too large destroys thin objects (fences, poles); too small and you gain nothing. For urban outdoor SLAM, 10-20 cm is typical; for warehouse robots, 2-5 cm.

Registration aligns two overlapping point clouds — the core primitive in LiDAR odometry. Iterative Closest Point (ICP) is the classic algorithm:

1. For each point $\mathbf{p}_i$ in the source cloud, find its nearest neighbour $\mathbf{q}_i$ in the target cloud.
2. Solve for the rigid transform $(R, \mathbf{t})$ that minimises $\sum_i \|R\mathbf{p}_i + \mathbf{t} - \mathbf{q}_i\|^2$ (closed-form via SVD of the cross-covariance matrix).
3. Apply the transform and repeat until convergence.

ICP converges to the correct answer only if the initial alignment is close (typically within 1-2 m and 10°). In practice, LiDAR SLAM front ends use NDT (Normal Distributions Transform) or feature-based matching (LOAM: extract edge and planar features) for coarse alignment, then refine with ICP. Convergence failure modes: symmetrical scenes (long straight corridors), degenerate geometries (flat ground only), and dynamic objects (pedestrians move between scans).

Separating the drivable ground from obstacles is a foundational operation. The simplest method is RANSAC plane fitting: repeatedly sample 3 non-collinear points, fit a plane, count inliers within distance threshold $\epsilon$, and keep the best hypothesis:

import open3d as o3d

pcd = o3d.io.read_point_cloud("scan.pcd")

# RANSAC plane segmentation
plane_model, inliers = pcd.segment_plane(
    distance_threshold=0.15,  # metres
    ransac_n=3,
    num_iterations=200
)
[a, b, c, d] = plane_model
print(f"Plane equation: {a:.2f}x + {b:.2f}y + {c:.2f}z + {d:.2f} = 0")

ground = pcd.select_by_index(inliers)
obstacles = pcd.select_by_index(inliers, invert=True)

Limitations: sloped terrain breaks a single-plane assumption (use multi-plane fitting or normal-based region growing); bridge decks and ramps require elevation maps (costmaps). After ground removal, Euclidean cluster extraction groups remaining points into obstacle candidates for downstream detection.

Engineers love to debate this. Here is an honest comparison:

The verdict for autonomous vehicles: both. Cameras provide semantic richness (reading signs, traffic lights); LiDAR provides reliable metric structure. Fusing them — LiDAR-camera fusion — is the dominant architecture in serious production stacks.

LiDAR odometry uses scan-to-scan (or scan-to-submap) registration to estimate robot motion. The pipeline:

1. Receive new scan at time $t$.
2. Downsample and extract features (edges on high-curvature points, planes on low-curvature patches — LOAM's insight).
3. Register features against the local map to get relative pose $\Delta T$.
4. Compose: $T_t = T_{t-1} \cdot \Delta T$.
5. Add scan to local map, keyframe if motion exceeds threshold.

A flat featureless floor is the death scenario: all points are coplanar, so the cross-covariance SVD loses one singular value, and the component along the floor normal is unobservable. Good systems detect this degeneracy by checking the condition number of the information matrix and fuse IMU data to constrain the missing DOFs. Without loop closure, LiDAR odometry drifts at roughly 0.5-2% of distance travelled — better than camera VO, but still non-zero.

From raw scan to obstacle list — the standard stack.

Classical methods treat points as geometry. Deep approaches learn directly from point clouds:

• PointNet (Qi et al., 2017): applies a shared MLP per point, then a global max-pool — permutation-invariant and order-independent. Simple, fast, misses local structure.
• PointNet++: adds hierarchical grouping with ball-query radius sampling to capture local context. Better accuracy, slower.
• VoxelNet / PointPillars: voxelise or pillarise the cloud, apply 2D convolutions, use as a detection backbone. PointPillars runs in $< 10$ ms on a GPU — fast enough for 10 Hz LiDAR.
• Range image CNNs: project the spin-scan onto a cylindrical range image, apply 2D segmentation. Extremely fast; loses 3D structure.

Production stacks (Waymo, Cruise) use ensemble approaches combining pillars-based detection with classical clustering and tracking filters. No single network handles all edge cases — the stack depth is the point.