Transcript Lecture notes.

Last Time
•
•
•
•
Triangle-Triangle collision testing
Separating planes/axes
Collision detection systems, Part 1
Final project stage
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Today
• More collision detection packages
• Time critical collision detection
• Introduction to networking for games
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Evaluating Collision Schemes
• Most sensible collision detection packages are multi-phase
– First phase: Detecting which bounding boxes might collide
– Second phase: Detecting which bounding boxes do collide
– Third phase: Detecting which objects collide and where
• Important analysis: Cost of detection, for two phases, is
NbCb+NnCn
– Number of broad tests  cost of broad test + number of narrow tests
 cost of each narrow test
• Cb and Nn depend on broad phase’s scheme
– Cheap test reduces Cb, but might result in an increased Nn
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
OBB-Tree Evaluation
• OBB-Trees are the method of choice for unstructured
geometry
• 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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Lin-Canny
• Lin-Canny was originally proposed as an algorithm
– The authors never implemented it!!
• It has problems with infinite looping under some 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)
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
V-Clip (Mirtich 98)
• 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 closest point package has crashed for me)
• If you ever need it, I have an implementation that also does closest point
– But it’s patented, so legally you cannot use it without a license from
Mitsubishi Electric
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
V-Clip Analysis
• Very very fast if the conditions for using it can be met, particularly if
coherence exists
– 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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Time-Critical Collision Detection
• Time-critical collision detection gives the best approximate answer it
can in a fixed amount of time
• 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
• Could use any form of bounding volume hierarchy (OBBs in particular)
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Collision Detection Summary
• This course has only touched on the many options for
collision detection
– One missing option: Brute force, which can be faster for very simple
objects
– See Moller and Haines for a more complete overview
• The gains from some quantitative analysis can be immense
– How many tests succeed? How expensive is each test? …
• There is a lot of misinformation about collision detection
– For almost any method, there is some case where it is faster, but that
doesn’t mean it’s always faster
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Reducing Latency (1)
• Frame rate latency:
– Increase the frame rate (faster graphics, faster AI, faster physics)
• Network protocol latency:
– Send less stuff (less stuff to copy and shift around)
– Switch to a protocol with lower latency
– But may have impact on reliability and security
• Transmission latency:
– Send less stuff – less time between when the first bit and the last bit
arrive
– Upgrade your physical network (from dial-up to DSL, for instance)
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Reducing Latency (2)
• Processing latency:
– Make your server faster
– Have more servers
• 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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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 (e.g. local
player)
– 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 available information
• With a client-server model, each player runs their own
version of the game, while the server maintains absolute
authority
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
New Data
Extrapolations from new data
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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, …
• Some information does not need to be reliably
communicated:
– Information that rapidly becomes out of date, and hence is sent
frequently
– Player position information, weapon firing information, …
• The data that goes out of date quickly is also sent more
often; big payoffs for reducing the cost of sending it
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Todo
• By Wednesday, Dec 10, Final Demo
• Monday, Dec 15, Final Exam, 2:45 P.M, RM 1221 CS
12/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin