CollisionDetectionEngine

From WorldForgeWiki

Contents 1 Overview 2 Requirements 3 Non-Requirements 4 Assumptions 5 Principles 6 Design 7 Links

Overview

This is a quick spec on possible design for an updated collision detection engine.

The primary motivation right now is to improve the performance and capabilities of Cyphesis' collision detection. But a general engine may be handy on both the client and server.

Requirements

What should a collision detection engine be able to do? This is intended to be a prioritized list of capability requirements.

1. Fast (O(logN) or better) collision detection for moving objects.
2. Support for thousands of objects (should be tested for tens of thousands of objects).
3. Support for fully dynamic objects (that is, objects can come and go, and change properties such as size).
4. Fast neighborhood-based lookups (the query "find all objects within radius R of point P" should be fast).
5. Full arbitrary 3D collision support (rectangles could be rotated in any direction/degree, etc.).
6. Locality/visibility optimization so that clients only receive data for objects relevant to their rendering.
7. Provide topology information about the world, i.e. "how are points P and Q connected?". (this is at the bottom of the list--it is more of a side-benefit of collision detection datastructures than a core requirement).

Non-Requirements

1. This is not intended to be a physics engine. If a physics engine is needed, open source engines such as ODE or Bullet could be used.

Assumptions

1. Only simple polygons or basic convex objects (rectangles, spheres, etc.) will be supported. More complex objects (buildings with walls + ceilings, arbitrary 3D shapes) must be decomposed into basic convex objects for the purposes of collision detection.

Principles

As with all search problems, the way to achieve performance is through some sort of space partitioning.

Common partitioning schemes are Binary Space Partitioning (BSP) or Octrees. Those are generic space-partitioning schemes: given an artibrary set of polygons (or simple convex objects), a datastructure is constructed which evenly partitions the space. Performing lookups based on position or locality are now a tree lookup O(logN) instead of a traversal of all objects O(N).

However, even generic space-partitioning schemes are not enough in some cases. Often game or world designers can use additional information to speed lookups. For instance, a game designer may know that room A is not at all visible from any location in room B (for instance, they are connected only by a zig-zag corridor). In that case, while rendering a view from a point in room B, no information about room A's objects is necessary at all. Likewise, for collision detection in room B, no information about room A's objects is needed.

The solution for that is to use Potentially Visible Sets (PVS). In the case above, room A would be in one set (A), room B would be in another set (B), and the corridor connecting them could be in a third set (C). Set A and B are both visible from C (that is, you might be able to see room A or B or possibly both from various points in the corridor C), but A is not visible from B and vice-versa.

This is represented as a graph: nodes are PVSets, and edges mean that the nodes are potentially visible from each other. The example above is a simple graph with three nodes (A, B, C) and two edges (A-C, B-C).

This graph is useful for more than just rendering and collision detection. It also (typically) encapsulates the topology of the world. In this case, the way to get from A to B is to go through corridor C. So Artificial Intelligence algorithms can also exploit the PVS graph for route-finding operations if necessary.

This sort of PVS approach is also referred to as Portal Rendering.

There is one weakness of the PVS approach: it is difficult to determine PVS graphs on-the-fly. That is, given an arbitrary set of polygons and/or objects, decomposing them into a PVS tree is computationally intensive. I suspect world authors will have to specify PVS nodes ahead of time (or in code). If no PVS structure is specified at all, the engine can keep all objects in the same node. But world authors that know about topology (valley A is not visible from canyon B, cave C is not visible from tower D, etc) can exploit that information to make the world more scalable (that is, support more objects).

Design

The proposed design is to use a graph of Possibly Visible Sets. Each node in the graph (PVSet) has a bounding 3D rectangle, and it would contain an Octree which stored all objects contained in the PVS. PVS nodes would also be held in some higher-level Octree so that questions like "what PVS node contains point P" can be answered quickly.

Why use an Octree instead of a BSP tree? Octrees are simple structures and adapt well to dynamic objects. BSP trees are excellent for static environments, but for dynamic environments I think Octrees will be more straightforward to use.

What are common operations the engine will be asked to perform? I think these will likely determine the API.

1. Create/remove a new PVS node.
2. Add/remove an edge between these two PVS nodes (A is now visible from B and vice-versa).
3. Add/Remove this object from the world (will add the object to the Octree of the proper PVS node).
4. Tell me what PVS node contains point P.
5. Tell me all objects within radius R of point P.
6. Given object X at point P moving with velocity V, tell me the first collision that occurs (object Y hit at time T). [Velocity V includes direction and speed, and "first" means first in time, not the first collision the engine happens to come across].
7. How are points P and Q connected? (could return a set of graph walks, so AI algorithms could plan routes between points)

Links

This page is part of a registered blueprint, see the Launchpad Blueprint.