YouTube Transcript:
Quake's PVS: A hidden gem of rendering optimization
Skip watching entire videos - get the full transcript, search for keywords, and copy with one click.
Share:
Video Transcript
Available languages:
View:
before Hardware acceleration
revolutionized gaming every pixel had to
be drawn by the CPU a few hundred
texture map polygons at low resolution
pushed the computers off the era to
their limits one of the problems
developers faced was overdraw wasting
computation on rendering polygons that
were hidden behind other polygons one of
the techniques Quakes program is used to
tackle this is PBS or potentially
visible set to pre-calculation PVS was
revolutionary and was one of the key
innovations that made the game possible
in this video we'll explore the inner
workings of PVS featuring Dynamic
animations that unveil some of the
Hidden structures driving Quake so let's
dive in and see how Quake made history
our journey starts with a bsp tree the
bsp tree is useful since it breaks the
level down into convex regions called
leaves Each of which is either entirely
solid or entirely empty check out my
video on collision detection for a bit
more background on bsp trees for the
purposes of visibility we're only
interested in the empty leaves our goal
is to work out which empty leaves can
see each other and store this
information in the compiled map
each empty Leaf has a set of triangles
associated with it at run time the game
works out which Leaf the player is in
and draws only triangles from the leaves
that are in the pre-computed visibility
list for the Player's lead
in order to calculate these visibility
lists a new data structure is required
known as a portal graph
any pair of empty leaves that are
touching implicitly have a polygon at
the surface on which they join
this polygon is called a portal since it
represents a route for patting from one
leaf to the other
the compiler extracts these portals and
Associates them with the respective
leaves building up a graph structure
with leaves as nodes and portals as edges
edges
the stage is now set to begin populating
the visibility lists
for illustration let's consider a level
with a linear portal graph
we're going to be working out which
leaves can be seen from the leftmost leaf
leaf
given a Target Leaf we want to know if
there is a line segment from some point
in the source Leaf to some point in the
Target leaf that does not pass through
any solids
the requirement of not passing through
solids is equivalent to saying that the
line passes through a portal when moving
between leaves
every leaf can always see itself
and any immediate Neighbors
in this case and almost all cases the
third Leaf can be seen as well the
exception to this is if the two portals
are coplanar
things start to get interesting with the
fourth Leaf in this case the source and
Target leaves are separated by three
portals the portal on the source Leaf
the portal on the target leaf and the
portal between the two which is referred
to as the pass portal
in this case the targeted portal isn't
visible but how can this be proved it's
not possible to exhaustively try all
possible lines since there are
infinitely many instead the map compiler
uses the concept of separators
a separator is any plane that lies
between the source portal and the pass
portal with the pass portal lying
entirely in front of the plane
and the source portal lying entirely behind
behind
any line that starts on the source
portal and goes through the pass portal
must remain in front of the plane once
past the pass portal
this means that any part of the target
portal that lies behind the plane must
not be visible
with three portals it is possible to get
an exact visibility check by generating
a separator for each edge of the source
portal and a separator for each edge of
the pass portal
each plane is inclined so that it just
touches the other portal while still
being on the opposite side
as each plane is added the target portal
is clipped so that the portion on the
back side of the plane is removed [Music]
[Music]
if none of the target portal Remains the
target Leaf isn't visible and the
process stops otherwise the leak is
added to the source Leaf's visibility
list and we can proceed to the next Leaf
in the chain
with the fifth leaf an exact visibility
test would require us to check whether a
line exists that passes through all four portals
portals
in general calculating exact visibility
for arbitrary numbers of portals is
incredibly complex in terms of
computation time theory and
implementation instead Quake takes a
conservative approach rather than asking
whether a line passes through all four
portals it simply asks whether a line
passes through the source portal the
clipped portal from the previous step
and the new targets portal which can be
done using the same separator technique
from the previous step any line that
passes through all four portals must
necessarily pass through the restricted
set of portals therefore any leaf that
is truly visible will always be marked
visible by this method on the other hand
there may exist lines that pass through
the restricted set that do not pass
through all four portals meaning that
leaves that are invisible may be marked
as visible
this process continues repeatedly until
an invisible Leaf is encountered [Music]
[Music]
the above approach can be adapted for a
real level with a non-linear portal
graph by means of a recursive search
given a source Leaf a depth first search
through all possible portal sequences is
performed with each sequence terminating
as soon as a leaf is determined to be invisible
invisible
the final visibility data for quake's
first level looks like this
with run length encoding it consumes
about 40 kilobytes of disk space about
three percent of the vinyl Map size
the realvis program has some
optimizations to cut down on the search
base a little
nevertheless this program was very
taxing even for powerful computers of
the time there is an even more
aggressive mode used for final builds
that involves clipping The Source Portal
2 making the search take even longer but
all this computation happens during
development and is in the aid of
reducing the amount of work required on
the end user's machine pre-computation
is a major theme of quakes development
visibility cooling Collision data
structures as well as lighting
pre-calculations were all necessary to
get this groundbreaking game running on
Click on any text or timestamp to jump to that moment in the video
Share:
Most transcripts ready in under 5 seconds
One-Click Copy125+ LanguagesSearch ContentJump to Timestamps
Paste YouTube URL
Enter any YouTube video link to get the full transcript
Transcript Extraction Form
Most transcripts ready in under 5 seconds
Get Our Chrome Extension
Get transcripts instantly without leaving YouTube. Install our Chrome extension for one-click access to any video's transcript directly on the watch page.
Works with YouTube, Coursera, Udemy and more educational platforms
Get Instant Transcripts: Just Edit the Domain in Your Address Bar!
YouTube
←
→
↻
https://www.youtube.com/watch?v=UF8uR6Z6KLc
YoutubeToText
←
→
↻
https://youtubetotext.net/watch?v=UF8uR6Z6KLc