Fine visibility via clipping

This is the third 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)

Now we have a first estimate of portal-to-leaf visibility stored in each portal’s mightsee array. Computing what’s exactly visible through a series of portals is hard and we use a “conservative” approximation instead. It never hides a leaf that should stay visible.

Let’s get started.

“It’s just a clipping problem”

Suddenly the lights go out. You are sitting in a spacious conference room and someone has turned on the overhead projector. It’s Michael Abrash himself! This must be the famous Quake Postmortem session of GDC 1997.

He’s talking about portals.

You take the clipping planes that delimit the maximum amount you could see and you keep clipping them against farther and farther portals until they go away

Then he sketches the following diagram:

He draws two lines that pass through the opposite edges of the two portals and fills in the region between the lines that lies to the right of the second portal:

The filled in region is what’s proven visible from the first two portals. It’s getting tense. Finally, he draws two new lines in the same way through the edges of the second and third portals:

The leaf the second portal leads to has been marked visible with the letter P. However, the two filled in regions don’t overlap, so the third portal is proven invisible from the first one and the process terminates:

but that space [top] is completely excluded from this space [bottom], therefore we can’t see any of this [bottom] therefore this is not in the potentially visible set, we don’t go through that portal that’s the end of it. And that’s really all there is to it [–]

Thunderous applause. The man next you stands up and begins stomping his feet in excitement. Wait, who’s singing We Are the Champions?

OK that’s enough. Back to the present day.

So. All there is to it? He did admit that “the implementation is a little tougher” but continued that “it’s just a clipping problem.” Let’s see what he meant.

Portal clipping in 2D

The fundamental idea is to construct a volume that definitely contains all sightlines that pass through a sequence of portals. If a portal is outside the volume, it can’t be seen through the portals in the sequence so far.

Clipping happens when a portal is only partially visible. The diagram below illustrates this. There are three portals: the source portal of the originating leaf, a pass portal we are seeing through, and the target portal that we’d like to prove invisible if possible.

Just like in the drawings earlier, we have two lines that pass through the opposite ends of the source and pass portals. Only the yellow region between the lines is visible through both portals. So now we clip away the parts of the target portal that we know to be invisible.

As Michael Abrash demonstrated above, the process continues until the target portal is completely clipped away. We consider the clipped target portal the new pass portal, and choose a fresh new target portal farther away in the graph.

This is an approximation. We are never testing visibility through more than three portals, even if there are more on the path from source to target. The three portals do get smaller due to clipping but still there are false positives, sightlines kept that don’t actually pass through every portal. That’s why we actually do a lot of clipping, as will be seen later.

How to find separating planes

In the 2D case it was simple to draw a line through the opposite ends of portals. The line obviously put the two portals on different sides. In 3D, it’s more involved since we must generate planes instead of lines.

The diagram below shows how it can be done. First pick an edge of the source portal (line segment AB). Then pick a vertex from the pass portal (C). Fit a plane to the three points A, B and C.

The plane should put the source and pass portals on opposite sides. After fitting the plane, we test every point of the pass portal against the plane. None of the points should be behind the plane and at least in one should be in front. The source portal will be behind it by construction.

We don’t know beforehand which planes will be actually separating planes, so we need to test every edge and vertex combination of the two portals. The target portal is clipped with every separating plane found. The diagram below shows another plane.

Sometimes the point C may be behind the source portal. This is not an error but may happen if the pass portal is only partially in front of the source portal:

In this case it’s enough to flip the plane normal.

We can construct even more separating planes if we swap the roles of the source and pass portals. Now we pick an edge AB of the pass portal and a point C of the source portal. Since the clipping function’s arguments are swapped, it will incorrectly but consistently orient the plane towards the source portal. Perhaps you already guessed what we’ll do.

There’s another, optional, plane normal flip before clipping.

It can get pretty confusing but that’s how it works.

Separating planes in Python

Here’s the code. The two nested for loops below are really the main invention in the algorithm. At least I couldn’t find any mention of this in Teller’s work. My Python code is pretty close to the C++ one in ericw-tools. The backside argument is set to true when source and pass portal roles are swapped.

# Separator plane selection and clipping

def clip_to_separators(
  first_poly: Winding,
  first_plane: Plane,
  second_poly: Winding,
  clipped_poly: Winding,
  backside=False,
) -> Winding:
  clipped = clipped_poly

  for i in range(len(first_poly)):
    j = (i + 1) % len(first_poly)
    A = first_poly[i]
    B = first_poly[j]
    AB = B - A

    # Try different points C on the second portal
    for k, C in enumerate(second_poly):
      # Test on which side of the first portal point C is
      d = first_plane.distance_to(C)
      if d < -ON_EPSILON:
        # A separating plane must have the second portal on
        # its front side by definition. Here C is behind the
        # first portal, so this will not be the case after
        #   normal = cross(AB, AC)
        # below and we'll have to flip the plane later.
        flip_towards_first = True
      elif d > ON_EPSILON:
        flip_towards_first = False
      else:
        continue  # Point C is on the first polygon's plane

      AC = C - A
      normal = np.cross(AB, AC)
      mag = np.linalg.norm(normal)

      if mag < ON_EPSILON:
        continue  # Portals might share vertices so there's no plane
      normal /= mag

      plane = Plane(normal, normal.dot(C))

      if flip_towards_first:
        plane = -plane

      # Check if the plane is actually a separator
      if not test_if_points_in_front(second_poly, plane):
        continue

      # The 'backside' flag is set if source and pass portals are swapped.
      # In that case, second_poly == source_poly, so the plane normal
      # points to the source and not the pass portal!
      # We'll flip the plane so that correct side gets clipped below.
      if backside:
        plane = -plane

      clipped = clip_winding(clipped, plane)

      if not clipped:
        return None

  return clipped

Also clip the source portal

The final extension is to also clip the source portal. The target portal now acts as the source. The pass portal stays the same. In the end, clipping is done in four configurations when we combine this with the source and pass portal swap.

That’s a lof a lot planes and clipping! I’ve still yet to process the full first map of Quake with vis.py because it’s just so slow.

In the final part (to be published) we’ll use what we learned to recursively clip a sequence of portals smaller and smaller, and resolve the final leaf visibilities.

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

---

Mastodon Bluesky YouTube Feed

30fps.net