# CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization

arXiv: https://arxiv.org/abs/1705.01167 · HTML: https://mlsanity.com/paper/1705.01167/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 May 2017.

## Built on by (most cited first, 9 of 9)

- [Autonomous Driving Small-Scale Cars: A Survey of Recent Development](https://mlsanity.com/paper/2404.06229/) (2024)
- [Train a Real-world Local Path Planner in One Hour via Partially Decoupled Reinforcement Learning and Vectorized Diversity](https://mlsanity.com/paper/2305.04180/) (2023)
- [ShelfAware: Real-Time Semantic Localization in Quasi-Static Environments with Low-Cost Sensors](https://mlsanity.com/paper/2512.09065/) (2025)
- [An Empirical Analysis of the Use of Real-Time Reachability for the Safety Assurance of Autonomous Vehicles](https://mlsanity.com/paper/2205.01419/) (2022)
- [PoseINN: Realtime Visual-based Pose Regression and Localization with Invertible Neural Networks](https://mlsanity.com/paper/2404.13288/) (2024)
- [MIND-Stack: Modular, Interpretable, End-to-End Differentiability for Autonomous Navigation](https://mlsanity.com/paper/2505.21734/) (2025)
- [Adaptive Control in Autonomous Driving via Real-Time Recurrent RL](https://mlsanity.com/paper/2602.02236/) (2026)
- [Learning to Tune Pure Pursuit in Autonomous Racing: Joint Lookahead and Steering-Gain Control with PPO](https://mlsanity.com/paper/2602.18386/) (2026)
- [Dynamic Lookahead Distance via Reinforcement Learning-Based Pure Pursuit for Autonomous Racing](https://mlsanity.com/paper/2603.28625/) (2026)

## Abstract (arXiv)

Localization is an essential component for autonomous robots. A well-established localization approach combines ray casting with a particle filter, leading to a computationally expensive algorithm that is difficult to run on resource-constrained mobile robots. We present a novel data structure called the Compressed Directional Distance Transform for accelerating ray casting in two dimensional occupancy grid maps. Our approach allows online map updates, and near constant time ray casting performance for a fixed size map, in contrast with other methods which exhibit poor worst case performance. Our experimental results show that the proposed algorithm approximates the performance characteristics of reading from a three dimensional lookup table of ray cast solutions while requiring two orders of magnitude less memory and precomputation. This results in a particle filter algorithm which can maintain 2500 particles with 61 ray casts per particle at 40Hz, using a single CPU thread onboard a mobile robot.