Special Course on Networked Virtual Environments
February 13, 2004
Jouni Smed 1
Single
Single- -Thread NVE Thread NVE
Compute State Changes Compute State Changes
from Inputs
from Inputs Read NetworkRead Network Compute State ChangesCompute State Changes from Net Reads from Net Reads Computational Computational Modelling Modelling Post State Changes Post State Changes
to Network to Network Generate New
Generate New Picture Picture
Read Input Read Input Devices Devices Initialization Initialization
Event Loop Event Loop
Multiple Subsystems, Multiple Threads Multiple Subsystems, Multiple Threads
Post State Post State Changes Changes Net Write Net Write Subsystem Subsystem
Generate Generate New Picture New Picture Display Display Subsystem Subsystem
Read Network Read Network
Compute State Compute State Changes from Changes from Net Reads Net Reads
Net Read Net Read Subsystem Subsystem Read Input
Read Input Devices Devices
Compute State Compute State Changes from Changes from
Inputs Inputs
Input Input Subsystem Subsystem
Modelling Modelling Subsystem Subsystem
Shared Shared Memory Memory
Computational Computational Modelling Modelling
Real
Real- -Time Rendering Time Rendering
Key problem: limitations in the performance of graphics Key problem: limitations in the performance of graphics hardware
hardware
frames per secondframes per second
polygons per secondpolygons per second
Polygon Polygon culling culling
Level Level- -of of- -detail detail processing processing
Polygon Culling Polygon Culling
Reduce the number of processed polygonsReduce the number of processed polygons
determine which polygons do not need to be drawn determine which polygons do not need to be drawn
A wealth of research and methods existsA wealth of research and methods exists
Assumes that the underlying 3D model remains quite staticAssumes that the underlying 3D model remains quite static
changes in the model changes in the model ⇒⇒changes in the culling data structureschanges in the culling data structures
Draw all polygons Draw all polygons Culling
Culling Draw visible polygonsDraw visible polygons
Time Time
?
?
Culling Tree Culling Tree
Room 1,1;
Room 1,1;
BV BV
Virtual World Virtual World Bounding Volume (BV) Bounding Volume (BV)
Floor 1; BV
Floor 1; BV Floor 2; BVFloor 2; BV Floor 3; BVFloor 3; BV
Room 1,2;
Room 1,2;
BV BV
Room 1,1;
Room 1,1;
BV BV
ViewView Volume Volume
Potentially Visible
Potentially Visible Sets (PVSs) Sets (PVSs) of of Polygons Polygons
Room 1 Room 1
Room 2
Room 2 Room 3Room 3 y y = 1= 1 y y = 2= 2
x x = 1= 1
y y= 1= 1
xx= 1= 1
Room
Room22 Room 3Room 3 Room 1 Room 1 Binary space partitioning Binary space partitioning treetree
PVS
PVS PVSPVS
PVSPVS
Special Course on Networked Virtual Environments
February 13, 2004
Jouni Smed 2
Levels of Detail (LOD) Levels of Detail (LOD)
Why to draw a large number of Why to draw a large number of polygons if they cover only few polygons if they cover only few pixels?
pixels?
LevelLevel--ofof--detaildetaildecision: how much decision: how much to draw
to draw
Distance to the object Distance to the object Viewer
Viewer Complete SetComplete Set of Polygons of Polygons
Medium Set Medium Set of Polygons of Polygons
Minimum Set Minimum Set of Polygons of Polygons
Real- Real -Time Collision Detection and Response Time Collision Detection and Response
Interacting Interacting with with the VE the VE
touching, grasping, standing,…touching, grasping, standing,…
Take some action in response to the collision Take some action in response to the collision
Is there an intersection with the polygons of an object Is there an intersection with the polygons of an object and the polygons of any other object?
and the polygons of any other object?
test bounding boxestest bounding boxes
utilize hierarchical data structuresutilize hierarchical data structures
Where are the precise contact points? Where are the precise contact points?
Real
Real- -Time Collision Detection Solutions Time Collision Detection Solutions
Approaches to collision detection Approaches to collision detection
geometric reasoninggeometric reasoning
bounding volume hierarchybounding volume hierarchy
analytical methodsanalytical methods
hybridhybrid
Fast Fast, , approximate approximate collision collision detection detection
ownship:ownship:staticstaticobjectobjectcollisionscollisions
ownship:ownship:movingmovingobjectobjectcollisionscollisions
Fast Fast, , accurate accurate collision collision detection detection
Fast, Approximate Collision Detection Fast, Approximate Collision Detection
Important to recognize that a collision has occurred Important to recognize that a collision has occurred
The precise location of the collision is unimportant The precise location of the collision is unimportant
Example: NPSNET Example: NPSNET
moving objects can collide with each other and with fixed, statimoving objects can collide with each other and with fixed, static c objects
objects
upon collision over a certain speed upon collision over a certain speed ⇒⇒the moving object diesthe moving object dies
no sophisticated physicsno sophisticated physics
Ownship = the local player in the VE Ownship = the local player in the VE
1.1. Moving object (ownship) against static objectsMoving object (ownship) against static objects
2.2. Moving object (ownship) against moving objects (other players)Moving object (ownship) against moving objects (other players)
Up to the ownship to report its collisions and its death Up to the ownship to report its collisions and its death
Ownship: Static
Ownship: Static Object Collisions Object Collisions
Occurs when an object has moved Occurs when an object has moved and its position is updated and its position is updated
Reduce the set of static objects Reduce the set of static objects that must be considered that must be considered
1.
1.Is theIs theownshipownshipbelow the a below the a threshold elevation?
threshold elevation?
2.
2.Calculate 2D distance to all Calculate 2D distance to all objects in the grid square objects in the grid square 3.3.Is theIs theownship’sownship’sground ground
elevation less than the height of elevation less than the height of the static object?
the static object?
Issue a detonation PDU or an Issue a detonation PDU or an entity state PDU entity state PDU
Ownship: Moving
Ownship: Moving Object Collisions Object Collisions
The The ownship ownship did not did not collidecollidewith with any static
any staticobjectobject
Reduce the collision comparison Reduce the collision comparison space
space 1.
1.Check current and Check current and neighbouringneighbouring squares
squares 2.
2.Calculate 3D distances to objectsCalculate 3D distances to objects 3.
3.Cast a ray from theCast a ray from theownship’sownship’s origin to the moving origin to the moving object’sobject’s origin
origin
The host managing moving The host managing moving object also performs collision object also performs collision detection and issues detection and issues PDUsPDUs
Special Course on Networked Virtual Environments
February 13, 2004
Jouni Smed 3
Fast, Accurate Collision Detection Fast, Accurate Collision Detection
SweepSweep--andand--pruneprunealgorithmalgorithm
An axially aligned 3D bounding An axially aligned 3D bounding box for each object
box for each object
Sort the bounding boxesSort the bounding boxes
Are the bounding boxes Are the bounding boxes overlapping?
overlapping?
for 3Dfor 3Dbounding bounding boxes to boxes to collide, their
collide, theirprojections mustprojections must overlap
overlap
Are the the convexAre the the convexhulls hulls overlapping?
overlapping?
Compute the actual area of Compute the actual area of collision
collision
Problems of Collision
Problems of Collision Detection in NVEs Detection in NVEs
Who determines collision in Who determines collision in an an NVE? NVE?
The object that has collided The object that has collided
DIS DIS does not require that the hosts usedoes not require that the hosts usethe same collision detection the same collision detection algorithm
algorithm
what if onewhat if onedecides decides to die,to die,whilst anotherwhilst anotherdecides that there was no decides that there was no collision
collision
fair play requires a standard for collision detectionfair play requires a standard for collision detection
What about collisions What about collisions that happen that happen
in betweenin betweentime time steps, or steps, or
for deadfor dead--reckoned reckoned objects?objects?
Collisions in between
Collisions in between Time Steps Time Steps
The objects are moving too The objects are moving too fast
fast
The time steps between The time steps between frames are too large frames are too large
Requires Requires additional additional computation computation
Collisions for Dead
Collisions for Dead- -Reckoned Reckoned Objects Objects
The The ownship ownship may determine collision with may determine collision with a dead a dead- -reckoned reckoned object and issue a packet
object and issue a packet
The object collided with is at The object collided with is at a slightly a slightly different
different actual position actual position
no collisionno collision
collision with different resultscollision with different results
Mechanism for establishing an agreement on which Mechanism for establishing an agreement on which the objects the objects reach
reach an acceptable conclusion an acceptable conclusion
Recognize arriving packets that indicate mutual collision Recognize arriving packets that indicate mutual collision
the object that missed the collision the object that missed the collision must also realizemust also realizeitit
problemproblembetween the time of real collision and the learning between the time of real collision and the learning timetime
how to correct the past?how to correct the past?
Computational Resource Management Computational Resource Management
How to allocate processor time How to allocate processor time for the for the processes processes
do we leave it to the operatingdo we leave it to the operatingsystem?system?
A blocked thread A blocked thread should yield should yield the processor to the threads in the processor to the threads in waiting
waiting
Subsystems in separate Subsystems in separate threads
threads
inputinputsubsystemsubsystem
netnetread subsystemread subsystem
displaydisplaysubsystemsubsystem
netnetwrite subsystemwrite subsystem
modellingmodellingsubsystemsubsystem
Post State Post State Changes Changes Generate Generate New Picture New Picture
Read Network Read Network
Compute State Compute State Changes from Changes from Net Reads Net Reads Read Input Read Input Devices Devices
Compute State Compute State Changes from Changes from Inputs Inputs
Computational Computational Modeling Modeling
Shared Shared Memory Memory
