Graphics Reference
In-Depth Information
1
2
3
A
C
4
5
B
Figure 7.22
There are no objects in the cells overlapped by
A
, and thus object
A
does not
need to test against any objects. Objects
B
and
C
must be tested against each other, as
C
crosses the portal between cells 3 and 5 and thus lies partly in the same cell as
B
.
// If portal is not completely clipped its contents must be partially
// visible, so recursively render other side through the reduced portal
if (!EmptyRegion(visiblePart))
RenderCell(visiblePart, pl->pAdjoiningCell);
}
// Now render all polygons (done last, for back-to-front rendering)
for (Polygon *p = c.pPolygonList; p != NULL;p=p->pNextPolygon)
RenderPolygon(p);
}
}
The same cells-and-portals structure can be used to optimize collision detection
queries. Initially, objects are associated with the cells containing their center point. As
objects move, a ray test determines whether the object has moved out of the current
cell. If it has, connected portals are tested against to find which neighboring cell the
object moved into.
For object-object queries, given an object
A
only the objects in
A
's assigned cell
and those in adjoining cells whose portal
A
overlaps must now be checked against.
Similarly, for object-world collisions only the polygons in the current cell and those
of any overlapped cells must be checked against (Figure 7.22).
The BSP trees of Chapter 8 serve to divide the world into convex regions and the
resulting spatial partitioning can be used for collision detection in a manner similar
to the cells-and-portals method. In fact, BSP trees are often used in the automated
generation of cells and portals.
