Transcript Lecture notes.

Today
• Collision detection packages
• Time critical collision detection
• Networking for Games
12/11/2001
CS 638, Fall 2001
Algorithms for 3D Objects
• OBB-Tree
– A hierarchy of OBBs
– Reports all collisions between triangle soup
• Voronoi-Region Methods (Lin-Canny and V-Clip)
– Only works for convex manifold objects, but extremely robust
– Actually a closest features algorithm - gives closest features even if
objects do not intersect
12/11/2001
CS 638, Fall 2001
OBB-Trees (Gottschalk, Lin, Manocha: SIGGRAPH 96)
• Represent an object (collection of triangles) with a hierarchy
of OBBs
– Leaves are triangles
– Each box bounds its children
• Do collision testing between two objects by doing collision
testing between two trees
– Test two boxes, one from each tree. If they intersect, recursively test
4 combinations of child boxes (binary trees)
– Start with root boxes, base case is triangle-triangle tests
– Result is a list of triangle pairs that intersect
• Proof that a class project can go a long way
12/11/2001
CS 638, Fall 2001
Building the Trees
• Assume the objects are rigid, so the tree is built as a preprocessing step
• Tree is built top down:
– Start with all the triangles, and put an OBB around them
– Subdivide the box along the biggest dimension, classify triangles,
and recurse on the two sets (just like building a BSP tree)
– Child boxes don’t bear any specific relation to the parents – different
orientations and sizes
– Parents don’t even have to bound child boxes
• Basic operation is fitting an OBB to a collection of
triangles…
12/11/2001
CS 638, Fall 2001
OBB-Tree Construction
12/11/2001
CS 638, Fall 2001
Fitting OBBs
• The OBB fitting problem requires finding the orientation of the box that
best fits the data
• Ideally, you want the minimum volume for the box, but that’s hard
• Instead, turn to an idea from statistics and AI (academic AI): principal
components
–
–
–
–
Point sample the convex hull of the geometry to be bound
Find the mean and covariance matrix of the samples
The mean will be the center of the box
The eigenvectors of the covariance matrix are the principal directions – they
are used for the axes of the box
– The principle directions tend to align along the longest axis, then the next
longest that is orthogonal, and then the other orthogonal axis
12/11/2001
CS 638, Fall 2001
Principle Components
12/11/2001
CS 638, Fall 2001
OBB-Tree Evaluation
• OBB-Trees are the method of choice for unstructured geometry
• Important analysis: Cost of detection, for two phases, is NbCb+NnCn
– Number of broad tests times cost of broad test + number of narrow tests
times cost of each narrow test
– Cb and Nn depend on broad phases scheme – OBB-Tree is good at Nn and not bad at Cb, whereas AABB is good at Cb but
not so good at Nn
• Biggest way to improve it would be to exploit coherence, but it is not
clear how to do so
• Faster algorithms are restricted to more structured geometry …
• Available as RAPID (just OBB-Trees) and V-COLLIDE (OBB-Trees
and dimension reduction broad phase)
12/11/2001
CS 638, Fall 2001
Closest Features
• Recall Voronoi regions and closest point problems
– Find the closest point by finding out which Voronoi region the test point lies
in
• Closest features algorithms find the shortest distance between two
convex objects by first finding the closest features
– The objects must be convex for the closest point to be uniquely defined
– Convexity also makes greedy search sure to succeed
– Closest features may be vertex-vertex, vertex-edge, vertex-face, edge-edge other cases are degenerate (but must be handled)
• Key theorem: If f1 is the closest feature on object 1, and f2 is the closest
feature on object 2, then f1 lies in f2 ’s Voronoi region and vice versa
12/11/2001
CS 638, Fall 2001
Lin-Canny
• Lin-Canny closest features uses the same walk through Voronoi regions
that we saw for closest point computations
• Iterative procedure:
– Start with previous closest features (exploit coherence)
– Test each feature against other’s Voronoi region
– If an error, walk to neighboring feature and repeat
• Only works for convex, polygonal, closed objects
• Voronoi regions are built as a pre-process, but not an expensive task, so
could be done in real time
• Available as I-COLLIDE (along with a dimension reduction broadphase and methods for managing hierarchies of convex objects)
12/11/2001
CS 638, Fall 2001
V-Clip (Mirtich 98)
• Lin-Canny has problems with infinite looping under bad cases, an
inability to handle penetration, and general instability
– The problem is in choosing which region to step to next
– Historic note: Lin and Canny described the algorithm, but Mirtich was the
first to implement it (Canny was the common thread)
• V-Clip fixes the problems with Lin-Canny by rethinking the rules for
transitioning from one region to the next
– Uses derivative information to figure out which region to walk to next
– Works in cases of penetration (detects it and returns negative distance)
– In my experience, it has never crashed with valid input and always gives
sensible output (every other collision detection package fails on some count)
• If you ever need it, I have an implementation that also does closest point
12/11/2001
CS 638, Fall 2001
V-Clip Analysis
• Very very fast if the conditions for using it can be met, particularly if
coherence exists
– Note that higher frame rates lead to greater coherence
– Brief digression: the evil feedback loop for dynamics
• As frame time increases, the amount of work to compute each frame increases,
increasing the frame time even more, …
• Can be very easily modified to handle affinely deforming objects
• It is really a primitive collision test - the primitives are convex rigid
bodies
– It can be used as the base case for algorithms like OBB-Trees
– To my knowledge, no-one has tried using k-dop trees with V-Clip, or OBBTrees with V-Clip as the primitive test
12/11/2001
CS 638, Fall 2001
Time-Critical Collision Detection
• Time-critical collision detection gives the best approximate answer it
can in a fixed amount of time
– In theory, useful for games
• Sphere-Trees (Hubbard 96) use hierarchies of spheres to approximate
objects
– Lower levels of the hierarchy represent better and better approximations
– Basically the volumetric equivalent of progressive LOD trees
• To do time-critical rendering, keep performing tests, working down the
hierarchy, until you run out of time
• Report collisions if indicated by the most accurate tests performed
• In principle, could use any form of bounding volume hierarchy (OBBs
in particular), but for some reason no-one has done it
12/11/2001
CS 638, Fall 2001
Networking for Games
• You need networking for multi-player gaming
• There are persistent games, like EverQuest, where state remains
regardless whether or not anyone is playing
• There are transient games that exist only while people are playing, and
reset each time the server-side is reset
• There are four primary concerns in building networks for games:
–
–
–
–
Latency: How long does it take for state to be transmitted
Reliability: How often is data lost or corrupted
Bandwidth: How much data can be transmitted in a given time
Security: How is the game-play protected from tampering
• All of these considerations interact, and trade-offs must be made
12/11/2001
CS 638, Fall 2001
Latency in Games
• Recall that latency is the time between when the user acts and when they
see the result
• Latency is arguably the most important aspect of a game network
– Too much latency makes the game-play harder to understand because the
player cannot associate cause and effect
– It makes it harder to target objects (the lead becomes to large)
– There is significant psychological research on this topic
• Latency is not the same as bandwidth
– A freeway has higher bandwidth than a country road, but the speed limit,
and hence the latency, can be the same
– Excess bandwidth can reduce the variance in latency, but cannot reduce the
minimum latency (queuing theory)
12/11/2001
CS 638, Fall 2001
Sources of Latency
• Consider a client sending and receiving data from a server
• There are four sources of latency in a game network
– Frame rate latency: Data only goes out on or comes in from the network
layer once per frame, and user interaction is only sampled once per frame
– Network protocol latency: It takes time for the operating system to put data
onto the physical network, and time to get it off a physical network and to
an application
– Transmission latency: It takes time for data to be transmitted to the receiver
– Processing latency: The time taken for the server (or client) to compute a
response to the input
• You cannot make any of these sources go away
– You don’t even have control over some of them
– Remember Amdahl’s law when trying to improve latency
12/11/2001
CS 638, Fall 2001
Reducing Latency
• Frame rate latency:
– Increase the frame rate (faster graphics, faster AI, faster physics)
• Network protocol latency:
– Switch to a protocol with lower latency
– But may have impact on reliability and security
• Transmission latency:
– Upgrade your physical network (from dial-up to DSL, for instance)
• Processing latency:
– Make your server faster
• The sad fact is, networking researchers and practitioners are almost
never concerned with latency
– Most applications can handle higher latency (who else cares about latency?)
– When did you last hear a DSL/Cable add that promised lower latency?
12/11/2001
CS 638, Fall 2001
Working With Latency
• If you can’t get rid of latency, you can try to hide it
• Any technique will introduce errors in some form - you
simply cannot provide immediate, accurate information
• Option 1: Sacrifice accurate information, and show
approximate positions
– Ignore the lag and show a given player “old” information about the
other players
– Try to improve upon this by guessing where the other players are.
But if your guess is wrong, incorrect information is shown
• Option 2: Sacrifice game-play:
– Deliberately introduce lag into the local player’s experience, so that
you have enough time to deal with the network
12/11/2001
CS 638, Fall 2001
Dead Reckoning
• Dead reckoning uses prediction to move objects about even when their
positions are not precisely known, reducing the appearance of lag
– Each client maintains precise state for some objects (the local player, for
instance)
– Each client receives periodic updates of the position of everyone else, along
with velocity information, and maybe acceleration
– On each frame, the non-local objects are updated by extrapolating their
most recent position using the given velocity
– There are other variants with different extrapolating schemes, particularly if
you know more about how an object moves
• With a client-server model, each player runs their own version of the
game, while the server maintains absolute authority
12/11/2001
CS 638, Fall 2001
Fixing Extrapolation Errors
• What do you do when using dead reckoning, and a new
position arrives for another player?
– The position that just came in will not agree with the place you have
the object, due to extrapolation errors
• Two options:
– Jump to the correct position
– Interpolate the two positions over some period
• Path followed will never be exact, but will match reasonably well
Target Path
Your Guess
Actual
12/11/2001
New Data
CS 638, Fall 2001
Extrapolations from new data
Network Reliability
• Some protocols attempt to ensure that every packet is
delivered
– It costs, in latency and bandwidth, to ensure delivery
• Others try less hard to ensure delivery, and will not tell you
if packets get lost
– Latency and bandwidth requirements are lower for such protocols
• Other aspects of reliability are error checking (do the right
bits arrive) and order consistency (do things arrive in the
same order they were sent)
• In a game, does everything need to be completely reliable?
• Are all aspects of reliability equally important?
12/11/2001
CS 638, Fall 2001
Reliability Requirements
• Some information must be communicated:
– Discrete changes in game state - if they go missing, there is no chance to
recapture them
– Information about payments, joining, dropping, etc…
• Some information does not need to be reliably communicated:
– Information that rapidly becomes out of date, and will hence be sent
frequently
– All aspects of reliability are less important in such cases
– For example, player position information, maybe even weapon firing
information
• The good part is, the data that goes out of date quickly is also sent more
often, so you get big payoffs for reducing the cost of sending it
12/11/2001
CS 638, Fall 2001
Internet Protocols
• There are only two internet protocols that are widely
deployed and useful for games: UDP and TCP/IP
– TCP/IP (Transmission Control Protocol/Internet Protocol) is most
commonly used
– UDP (User Datagram Protocol) is also widely deployed and used
• Other protocols exist:
– Proprietary standards
– Broadcast and Multicast are standard protocols with some useful
properties, but they are not widely deployed
– If the ISPs don’t provide it, you can’t use it
12/11/2001
CS 638, Fall 2001
TCP/IP Overview
• Advantages:
–
–
–
–
Guaranteed packet delivery
Ordered packet delivery
Packet checksum checking (some error checking)
Transmission flow control
• Disadvantages:
– Point-to-point transport
– Bandwidth and latency overhead
– Packets may be delayed to preserve order
• Uses:
– Data that must be reliably sent, or requires one of the other properties
– Games that can tolerate latency
12/11/2001
CS 638, Fall 2001
UDP Overview
• Advantages:
– Packet based - so works with the internet
– Low overhead in bandwidth and latency
– Immediate delivery - as soon as it arrives it goes to the client
• Disadvantages:
–
–
–
–
–
Point to point connectivity
No reliability guarantees
No ordering guarantees
Packets can be corrupted
Can cause problems with some firewalls
• Uses:
– Data that is sent frequently and goes out of date quickly
12/11/2001
CS 638, Fall 2001
Choosing a Protocol
• The best way to do it is decide on the requirements and find
the protocol to match
– In most cases, that means TCP/IP
• You can also design your own “protocol” by designing the
contents of packets
– Add cheat detection or error correction, for instance
– You then wrap you protocol inside TCP/IP or UDP
12/11/2001
CS 638, Fall 2001
Reducing Bandwidth Demands
• Bandwidth is plentiful on the internet today, so it only
becomes an issue with large environments
– Even “slow” modems have more impact through high latency than
low bandwidth (due to compression, error checking and
analogue/digital conversion)
• Regardless, smaller packets reduce both bandwidth and
latency
– Latency is measured from the time the first bit leaves to the time the
last bit arrives - so fewer bits have lower latency
• There are two primary ways to reduce bandwidth demands:
– Dead reckoning allows you to send state less frequently
– Area of interest management avoids sending irrelevant data
12/11/2001
CS 638, Fall 2001
Area of Interest Management
• Area of interest management is the networking equivalent of visibility only send data to the people who need it
• There is a catch, however: In a network you may not know where
everyone is, so you don’t know what they can see
– A chicken-and-egg problem
• Hence, area-of-interest schemes are typically employed in client-server
environments:
– The server has complete information
– It decides who needs to receive what information, and only sends
information to those who need it
• Two approaches: grid methods and aura methods
– Sound familiar? (replace aura with bounding box)
12/11/2001
CS 638, Fall 2001
Grid and Aura Methods
• Grid methods break the world into a grid
–
–
–
–
Associate information with cells
Associate players with cells
Only send information to players in the same, or neighboring, cells
This has all the same issues as grid based visibility and collision detection
• Aura methods associate an aura with each piece of information
– Only send information to players that intersect the aura
– Just like broad-phase collision detection with bounding volumes
• Players need to find out all the information about a space when they
enter it, regardless how long ago that information last changed
– Hence, the important thing is changes in association, not the moment to
moment picture
12/11/2001
CS 638, Fall 2001
Next time
• Last lecture: Cheating and how to discourage it
12/11/2001
CS 638, Fall 2001