0:01 before Hardware acceleration
0:04 revolutionized gaming every pixel had to
0:06 be drawn by the CPU a few hundred
0:08 texture map polygons at low resolution
0:10 pushed the computers off the era to
0:12 their limits one of the problems
0:15 developers faced was overdraw wasting
0:17 computation on rendering polygons that
0:19 were hidden behind other polygons one of
0:21 the techniques Quakes program is used to
0:23 tackle this is PBS or potentially
0:26 visible set to pre-calculation PVS was
0:28 revolutionary and was one of the key
0:29 innovations that made the game possible
0:32 in this video we'll explore the inner
0:34 workings of PVS featuring Dynamic
0:36 animations that unveil some of the
0:38 Hidden structures driving Quake so let's
0:40 dive in and see how Quake made history
0:47 our journey starts with a bsp tree the
0:49 bsp tree is useful since it breaks the
0:51 level down into convex regions called
0:53 leaves Each of which is either entirely
0:56 solid or entirely empty check out my
0:58 video on collision detection for a bit
1:00 more background on bsp trees for the
1:02 purposes of visibility we're only
1:05 interested in the empty leaves our goal
1:06 is to work out which empty leaves can
1:08 see each other and store this
1:10 information in the compiled map
1:12 each empty Leaf has a set of triangles
1:15 associated with it at run time the game
1:16 works out which Leaf the player is in
1:19 and draws only triangles from the leaves
1:21 that are in the pre-computed visibility
1:23 list for the Player's lead
1:25 in order to calculate these visibility
1:28 lists a new data structure is required
1:30 known as a portal graph
1:32 any pair of empty leaves that are
1:35 touching implicitly have a polygon at
1:37 the surface on which they join
1:39 this polygon is called a portal since it
1:41 represents a route for patting from one
1:43 leaf to the other
1:46 the compiler extracts these portals and
1:47 Associates them with the respective
1:49 leaves building up a graph structure
1:52 with leaves as nodes and portals as edges
1:53 edges
1:55 the stage is now set to begin populating
1:57 the visibility lists
1:59 for illustration let's consider a level
2:01 with a linear portal graph
2:03 we're going to be working out which
2:05 leaves can be seen from the leftmost leaf
2:06 leaf
2:08 given a Target Leaf we want to know if
2:10 there is a line segment from some point
2:12 in the source Leaf to some point in the
2:14 Target leaf that does not pass through
2:16 any solids
2:18 the requirement of not passing through
2:20 solids is equivalent to saying that the
2:22 line passes through a portal when moving
2:23 between leaves
2:26 every leaf can always see itself
2:29 and any immediate Neighbors
2:32 in this case and almost all cases the
2:34 third Leaf can be seen as well the
2:36 exception to this is if the two portals
2:39 are coplanar
2:41 things start to get interesting with the
2:43 fourth Leaf in this case the source and
2:45 Target leaves are separated by three
2:47 portals the portal on the source Leaf
2:49 the portal on the target leaf and the
2:51 portal between the two which is referred
2:53 to as the pass portal
2:55 in this case the targeted portal isn't
2:59 visible but how can this be proved it's
3:00 not possible to exhaustively try all
3:02 possible lines since there are
3:05 infinitely many instead the map compiler
3:07 uses the concept of separators
3:10 a separator is any plane that lies
3:11 between the source portal and the pass
3:13 portal with the pass portal lying
3:15 entirely in front of the plane
3:17 and the source portal lying entirely behind
3:18 behind
3:20 any line that starts on the source
3:22 portal and goes through the pass portal
3:24 must remain in front of the plane once
3:27 past the pass portal
3:28 this means that any part of the target
3:31 portal that lies behind the plane must
3:32 not be visible
3:35 with three portals it is possible to get
3:37 an exact visibility check by generating
3:39 a separator for each edge of the source
3:41 portal and a separator for each edge of
3:42 the pass portal
3:45 each plane is inclined so that it just
3:47 touches the other portal while still
3:49 being on the opposite side
3:52 as each plane is added the target portal
3:53 is clipped so that the portion on the
3:55 back side of the plane is removed [Music]
3:57 [Music]
3:59 if none of the target portal Remains the
4:01 target Leaf isn't visible and the
4:03 process stops otherwise the leak is
4:05 added to the source Leaf's visibility
4:07 list and we can proceed to the next Leaf
4:09 in the chain
4:12 with the fifth leaf an exact visibility
4:14 test would require us to check whether a
4:16 line exists that passes through all four portals
4:18 portals
4:20 in general calculating exact visibility
4:22 for arbitrary numbers of portals is
4:24 incredibly complex in terms of
4:27 computation time theory and
4:30 implementation instead Quake takes a
4:32 conservative approach rather than asking
4:34 whether a line passes through all four
4:37 portals it simply asks whether a line
4:39 passes through the source portal the
4:40 clipped portal from the previous step
4:43 and the new targets portal which can be
4:45 done using the same separator technique
4:47 from the previous step any line that
4:49 passes through all four portals must
4:51 necessarily pass through the restricted
4:54 set of portals therefore any leaf that
4:56 is truly visible will always be marked
4:58 visible by this method on the other hand
5:00 there may exist lines that pass through
5:02 the restricted set that do not pass
5:05 through all four portals meaning that
5:07 leaves that are invisible may be marked
5:08 as visible
5:11 this process continues repeatedly until
5:13 an invisible Leaf is encountered [Music]
5:15 [Music]
5:17 the above approach can be adapted for a
5:19 real level with a non-linear portal
5:21 graph by means of a recursive search
5:24 given a source Leaf a depth first search
5:27 through all possible portal sequences is
5:29 performed with each sequence terminating
5:31 as soon as a leaf is determined to be invisible
5:33 invisible
5:35 the final visibility data for quake's
5:37 first level looks like this
5:39 with run length encoding it consumes
5:42 about 40 kilobytes of disk space about
5:45 three percent of the vinyl Map size
5:46 the realvis program has some
5:48 optimizations to cut down on the search
5:50 base a little
5:52 nevertheless this program was very
5:55 taxing even for powerful computers of
5:56 the time there is an even more
5:58 aggressive mode used for final builds
6:00 that involves clipping The Source Portal
6:03 2 making the search take even longer but
6:05 all this computation happens during
6:06 development and is in the aid of
6:08 reducing the amount of work required on
6:10 the end user's machine pre-computation
6:12 is a major theme of quakes development
6:15 visibility cooling Collision data
6:17 structures as well as lighting
6:19 pre-calculations were all necessary to
6:21 get this groundbreaking game running on
Chrome Extension