  We consider path planning for a rigid spatial robot moving amidst polyhedral
obstacles. Our robot is either a rod or a ring. Being axially-symmetric, their
configuration space is R^3 x S^2 with 5 degrees of freedom (DOF). Correct,
complete and practical path planning for such robots is a long standing
challenge in robotics. While the rod is one of the most widely studied spatial
robots in path planning, the ring seems to be new, and a rare example of a
non-simply-connected robot. This work provides rigorous and complete algorithms
for these robots with theoretical guarantees. We implemented the algorithms in
our open-source Core Library. Experiments show that they are practical,
achieving near real-time performance. We compared our planner to
state-of-the-art sampling planners in OMPL.
  Our subdivision path planner is based on the twin foundations of
\epsilon-exactness and soft predicates. Correct implementation is relatively
easy. The technical innovations include subdivision atlases for S^2,
introduction of \Sigma_2 representations for footprints, and extensions of our
feature-based technique for "opening up the blackbox of collision detection".
