Flow fields

Flow fields are sparse arrays of vectors (i.e., directions), normally spaced apart in a grid across a 2D plane or within a 3D volume. The spacing of the vectors is not necessarily uniform. As the camera (or other object) passes through the flow field, vectors that are close to the camera affect its motion by applying a force in the direction of their orientation. The strength of force may be dependent upon the distance of the camera from the plane or some other factor.

The name derives from the fact that the array of vectors is akin to a stream or other moving body of water that flows around objects. By adjusting the direction of the vectors, we can ensure that the camera will move around obstacles in much the same manner.

Thus, it is important to ensure that the direction of the vectors will not cause situations to arise where the camera remains stationary as competing vectors cancel out their influence, or prevent the camera from clearing obstacles.

The use of flow fields is usually applied as an additional influence on camera motion, rather than the sole factor. In addition, it is necessary to determine when the additional influence should be applied. For example, the vectors could be uni- or bi-directional.

If the camera is able to navigate through the flow field in different directions relative to the flow field vector directions, the influence might only be applied when the camera motion is parallel to the direction of the vector. Additionally, the amount of influence may also be proportional to the velocity of the camera.

Influence maps

Influence maps are another sparse array, similar to flow fields in some regards. However, the mapping of the camera position from the influence map is normally based upon the position of the target object relative to the influence map rather than the camera itself. Each position on the influence map corresponds to a different position in space for the camera to occupy.

The desired position derived from the influence map is used as an interpolant so that the motion of the camera from its current position will be smooth. In some ways, spline motion can be considered a one-dimensional variant of the influence map. In this case, the target object position relative to the spline maps back to a position that the camera should occupy on the same (or a different) spline. Influence maps may be explicitly positioned or generated offline from collision or visibility information.

Potential fields

Derived from research into robot navigation, potential fields are a promising approach to dynamic camera navigation and collision avoidance. While this is an advanced topic beyond the scope of this book, a brief overview might be helpful. Potential fields are based on the principle of electrostatic forces; that is, forces whose effect on objects is proportional to the distance of the object from the force applier.

Essentially, these forces are applied to the active camera to prevent its approach toward collision or render geometry. Additionally these force components are added to the motion of the camera, aiding navigation through confined spaces and often avoiding many of the problems caused when the camera might be in collision with geometry.

The forces may be defined explicitly as points or plane surfaces and thus placed within the environment by designers in a similar manner to attractors and repulsors as previously mentioned. Alternatively, their position and orientation may also be automatically generated as part of the cooking of world data.

Similarly, the collision geometry may be used to generate forces. However, the complex nature of collision geometry would likely make determination of the forces closest to the camera computationally expensive. One possible solution is to generate an implicit surface that approximates the collision geometry in a smooth and continuous manner and facilitates rapid determination of the closest positions to the camera. See Bloomenthal for an introduction to implicit surfaces.

Robotics research has explored these techniques with mixed results (e.g., see Koren). There are some notable limitations regarding the complexity of the environments, especially regarding dead-ends. There may also be oscillation problems when the forces are applied from opposite directions simultaneously (e.g., in a narrow corridor).

Refer to Stout for more information on the practical application of potential fields within games. An alternative and very promising solution is offered in Borenstein, using vector field histograms (VFH). Briefly, VFHs store information regarding the distance of obstacles from the object determined by infrared or other sensors.

These sensors are typically mounted either at fixed angular offsets or rotate around a central point, effectively casting rays into the environment. The distance information returned at each angular offset may then be analyzed over time. A histogram of known obstacles is thus constructed, providing sufficient information to determine potential collisions.

Bibliography

[Bloomenthal97] Bloomenthal, Jules (ed.). Introduction to Implicit Surfaces. Morgan Kaufmann Publishers, 1997.

[Borenstein90] Borenstein, J. Koren, Y. (1990). "Realtime Obstacle Avoidance for Fast Mobile Robots in Cluttered Environments." The 1990 IEEE International Conference on Robotics and Automation, Cincinnati, Ohio, May 13-18, pp. 572-577.

[Ericson05] Ericson, Christer. Real-Time Collision Detection. Morgan Kaufmann Publishers, 2005.

[Halper01] Halper, Nicolas, Helbing, Ralf, Strothotte, Thomas. "A Camera Engine for Computer Games: Managing the Trade-Off Between Constraint Satisfaction and Frame Coherence." Proceedings of EUROGRAPHICS 2001 (Volume 20, Number 3). Blackwell Publishers, 2001.

[Koren91] Koren, Y. Borenstein, J. (1991). "Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation." Proceedings of the IEEE Conference on Robotics and Automation, Sacramento, California, April 7-12, pp. 1398-1404.

[Stout04] Stout, Bryan. "Artificial Potential Fields for Navigation and Animation." Presentation at Game Developers Conference 2004, San Jose, 2004. Written GDC 2004 proceedings.

[VandenBergen04] Van den Bergen, Gino. Collision Detection in Interactive 3D Environments. Morgan Kaufmann Publishers, 2004.