Coarse base visibility

This is the second installment in the “Demystifying the PVS” series.

1. Portals and Quake
2. Coarse base visibility
3. Fine visibility via clipping
4. Portal flow brings it all together (to be published)

We now have a directed graph with leaves connected by portals.

As mentioned in the high-level overview, we first compute which leaves each portal may see and then only at the end aggregate those results for each leaf. We begin by checking which leaves are even theoretically visible from any given portal.

Here I say that portal A can “see” a leaf if there exists a sightline through portal B that leads to that leaf. A sightline must cross the portals in the right direction:

The leaves are convex, and we can use this fact to make some quick decisions. A leaf can always see its immediate neighbors. It will also see through two portals into its neighbor’s neighbors too, unless the two portals are coplanar:

For the rest of the portals we actually need to do some tests.

Portal A may have a sightline through portal B if at least the following conditions are met:

1. B’s polygon has at least one point in front of A,
2. A’s polygon has at least one point behind B, and
3. A and B are not directly facing each other.

The three conditions are illustrated below. You can imagine drawing a sightline through portal A and note how it can’t pass through B from back to front.

Remember the convention chosen here: a portal points to the direction it leads to, so you effectively see through its “back” side. That’s why two portals facing each other are considered impassable.

Recursive flooding with geometric checks

Next we do a depth-first traversal over leaves from each portal. We start from the destination leaf of the first portal and enter other leaves through portals, but only if they are seen by the first one. The result is a list of leaves for each portal that might even theoretically be visible.

For example, let’s say we are computing the coarse visibility for portal A that leads to leaf 9.

Coarse visbility computation for portal A:

• First we enter leaf 9 and mark it visible.
• Then we consider entering leaf 9’s two portals B and D:
  • B is coplanar with the source portal A. Trivially fails the coarse test #2. Skip.
  • D looks good so the recursion enters leaf 8.
• Leaf 8 is marked visible.
• We then consider each portal of leaf 8: C, F and G:
  • C leads back to a visible leaf 9. Skip.
  • F is behind the source portal A (coarse test #1). See the orange dashed line. Skip.
  • G is in the same situation as F. Skip.
• We return to leaf 9 but it has no more portals to enter. The traversal is done.

The result for portal A: leaves 9 and 8 might be visible. It’s neat that we could hide the rest of the map behind portal F with just some basic geometric tests.

Coarse visibility code

Here’s how the above process looks in Python:

# Naming convention:
# 'pi' is a portal index in the global 'portals' array
# 'Pi' is a Portal object instance

def base_portal_flow(pi: int) -> np.ndarray:
  mightsee = np.zeros(num_leaves, dtype=bool) # The result array

  def simple_flood(leafnum: int):
    if mightsee[leafnum]:
      return

    # Portal 'pi' sees leaf 'leafnum'
    mightsee[leafnum] = True

    # Do the three coarse tests for pi->pk visibility for each portal 'pk'
    for pk in leaves[leafnum].portals:
      if portal_might_see_other(portals[pi], portals[pk]):
        simple_flood(portals[pk].leaf)

  # Start the DFS from this portal's target leaf
  simple_flood(portals[pi].leaf)
  return mightsee

# Compute coarse visibility for all portals
for pi, Pi in enumerate(portals):
  Pi.mightsee[:] = base_portal_flow(pi)

Where each portal has a bool array that stores which leaves it may see:

class Portal:
  ...
  mightsee: np.ndarray  # bool array for roughly visible leaves
  ...                   # (other class attributes omitted)

This coarse result is already usable in game. If we place the camera in leaf 10 (yellow), the leaves behind the orange portal shouldn’t be rendered:

The wireframe model confirms this is the case:

The original vis runs only the coarse pass if given the -fast command line option.

The full visibility is calculated by filtering these portal.mightsee lists with more accurate tests. It’s time to do some polygon clipping.

In the next part we’ll refine the visibility results further.

I’m also thinking of writing a book. Sign up here if you’re interested.

---

Mastodon Bluesky YouTube Feed

30fps.net