Redirected Walking in Static and Dynamic Scenes Using Visibility Polygons

Niall L. Williams, Aniket Bera, Dinesh Manocha

Abstract

We present a new approach for redirected walking in static and dynamic scenes that uses techniques from robot motion planning to compute the redirection gains that steer the user on collision-free paths in the physical space. Our first contribution is a mathematical framework for redirected walking using concepts from motion planning and configuration spaces. This framework highlights various geometric and perceptual constraints that tend to make collision-free redirected walking difficult. We use our framework to propose an efficient solution to the redirection problem that uses the notion of visibility polygons to compute the free spaces in the physical environment and the virtual environment. The visibility polygon provides a concise representation of the entire space that is visible, and therefore walkable, to the user from their position within an environment. Using this representation of walkable space, we apply redirected walking to steer the user to regions of the visibility polygon in the physical environment that closely match the region that the user occupies in the visibility polygon in the virtual environment. We show that our algorithm is able to steer the user along paths that result in significantly fewer resets than existing state-of-the-art algorithms in both static and dynamic scenes.

Introduction

Natural walking remains the "gold standard" for immersion in Virtual Reality (VR). However, a fundamental discrepancy often exists between the scale and layout of virtual environments (VE) and the available physical environment (PE). Redirected Walking (RDW) addresses this by subtly manipulating the virtual camera—applying rotation, translation, or curvature gains—to steer the user away from physical obstacles while they perceive themselves as walking naturally in the virtual world.

The primary metric for RDW success is the minimization of "resets," which occur when a user approaches a physical boundary and must be manually reoriented, breaking immersion. Existing reactive controllers often struggle in complex, cluttered, or dynamic environments. This research proposes a novel RDW controller that treats redirection as a geometric alignment task using visibility polygons.

Methodology: Visibility-Based Redirection

The core of the proposed approach is the use of Visibility Polygons (or isovists), a concept borrowed from robot motion planning. A visibility polygon represents the set of all points visible from a specific location within an environment, effectively defining the immediate "walkable" space.

The system computes visibility polygons in both physical and virtual environments to identify walkable space.

The algorithm operates through several key steps:

  1. Visibility Computation: At each frame, the system calculates the 2D visibility polygon for the user's current position in both the PE and VE.
  2. Slicing and Selection: These polygons are decomposed into triangular "slices" radiating from the user. The system identifies the "active slice" in the VE—the direction the user is currently facing and most likely to traverse.
  3. Geometric Alignment: The controller searches the physical visibility polygon for a slice that best matches the geometric properties (e.g., area and depth) of the virtual active slice.
  4. Gain Application: Redirection gains are then applied to steer the user’s physical trajectory toward the selected physical space, aligning the affordances of the real world with the intended path in the virtual world.

Evaluation and Results

The algorithm was evaluated through extensive simulated user studies across four distinct scenarios, ranging from narrow corridors to cluttered rooms and dynamic environments with moving obstacles. The "Vis. Poly." method was compared against three baseline controllers: Alignment-based (ARC), Artificial Potential Fields (APF), and Steer-to-Center (S2C).

Comparison of the virtual path (red) and the redirected physical path (blue) as the user navigates around obstacles.

Key Findings

  • Reduced Interruptions: The visibility-based approach consistently outperformed existing methods. In a corridor navigation task, it reduced the median number of resets to 121, compared to 153 for the previous state-of-the-art (ARC).
  • Robustness in Clutter: In highly cluttered environments, the performance gap widened. The Vis. Poly. method achieved roughly 87 median resets, while traditional potential field methods exceeded 150.
  • Dynamic Adaptability: By updating the visibility polygon in real-time, the system naturally accounts for moving obstacles, such as other people in the physical space, without requiring complex intent prediction.

Discussion and Key Insights

The success of this method highlights a shift from "obstacle avoidance" to "feature alignment." By steering users toward physical spaces that mirror the open areas they see in VR, the system makes more efficient use of the available room geometry. This local geometric approach provides a robust "map" of environmental affordances without the need for global path planning.

Limitations and Future Work

While promising, the current implementation assumes a pre-mapped physical environment. Future consumer applications would require real-time environment sensing (e.g., via SLAM). Additionally, while area-based slice matching is effective, more sophisticated shape-matching metrics could further refine alignment. Finally, while simulation results are statistically significant, large-scale human trials are necessary to evaluate the perceptual impact and potential for motion sickness.

Conclusion

By integrating robot motion planning principles into VR navigation, this work provides a more robust framework for redirected walking. The use of visibility polygons allows for efficient, real-time redirection that significantly improves the continuity of the VR experience in complex and dynamic real-world settings.

Summary updated

Abstract

We present a new approach for redirected walking in static and dynamic scenes that uses techniques from robot motion planning to compute the redirection gains that steer the user on collision-free paths in the physical space. Our first contribution is a mathematical framework for redirected walking using concepts from motion planning and configuration spaces. This framework highlights various geometric and perceptual constraints that tend to make collision-free redirected walking difficult. We use our framework to propose an efficient solution to the redirection problem that uses the notion of visibility polygons to compute the free spaces in the physical environment and the virtual environment. The visibility polygon provides a concise representation of the entire space that is visible, and therefore walkable, to the user from their position within an environment. Using this representation of walkable space, we apply redirected walking to steer the user to regions of the visibility polygon in the physical environment that closely match the region that the user occupies in the visibility polygon in the virtual environment. We show that our algorithm is able to steer the user along paths that result in significantly fewer resets than existing state-of-the-art algorithms in both static and dynamic scenes. Our project website is available at https://gamma.umd.edu/vis_poly/.
BibTeX
@article{williams2021redirected,
  author = {Niall L. Williams and Aniket Bera and Dinesh Manocha},
  title = {{Redirected Walking in Static and Dynamic Scenes Using Visibility Polygons}},
  journal = {IEEE Trans. Vis. Comput. Graph.},
  year = {2021},
  doi = {10.1109/tvcg.2021.3106432},
}
Figure