Abstract: We present a novel approach for interactive navigation in complex 3D synthetic environments using path planning. Our algorithm precomputes a global roadmap of the environment by using a variant of randomized motion planning algorithm along with a reachability-based analysis. At runtime, our algorithm performs graph searching and automatically computes a collision-free and constrained path between two user specified locations. It also enables local user-steered exploration, subject to motion constraints and integrates these capabilities in the control loop of 3D interaction. Our algorithm only requires the scene geometry, avatar orientation, and parameters relating the avatar size to the model size. The performance of the preprocessing algorithm grows as a linear function of the model size. We demonstrate its performance on two large environments: a power plant and a factory room.