Transcript 3D Game Engine

3D游戏引擎介绍
Engine
游戏引擎：用于控制所有游戏功能的主程序，从计算
碰撞、物理系统和物体的相对位置，到接受玩家的输
入，以及按照正确的音量输出声音等等
History of 3D Game Engine
引擎的诞生（1992年~1993年）
– 1992年，3D Realms公司/Apogee公司
Wolfenstein 3D 《德军司令部》
– 1992年，Origin公司 Ultima Underworld 《创世纪：地下世界》
– id Software公司 Doom 《毁灭战士》 （Doom引擎是第一个被用于授权的引擎）
引擎的转变（1994年~1997年）
– 1994年为3D Realms公司 《毁灭公爵》（Duke Nukem 3D）
– 1994年id Software公司的《雷神之锤》（Quake） （Quake引擎是当时第一款
完全支持多边形模型、动画和粒子特效的真正意义上的3D引擎）
– 1995年，id Software公司推出《雷神之锤2》 （Quake2）
– Epic Megagames公司（即现在的Epic游戏公司）的《虚幻》（Unreal）
（Unreal引擎的应用范围不限于游戏制作，还涵盖了教育、建筑等其它领域。Digital
Design公司曾与联合国教科文组织的世界文化遗产分部合作采用Unreal引擎制作过巴黎圣母
院的内部虚拟演示，Zen Tao公司采用Unreal引擎为空手道选手制作过武术训练软件 ）
History of 3D Game Engine
引擎的革命（1998年~2000年）
– 1998年， Valve公司的《半条命》（Half-Life） 《半条命》采用的是
Quake 和 Quake II引擎的混合体
– LookingGlass工作室《神偷：暗黑计划》（Thief：The Dark Project）在
人工智能方面真正取得突破的游戏是Looking Glass工作室的《神偷：暗黑计划》
– 2000年，3D引擎朝着两个不同的方向分化。一是如《半条命》、《神
偷》和《杀出重围》那样通过融入更多的叙事成分和角色扮演成分以
及加强游戏的人工智能来提高游戏的可玩性，二是朝着纯粹的网络模
式发展 id Software 《雷神之锤3竞技场》（Quake III Arena），它与
Epic公司稍后推出的《虚幻竞技场》（Unreal Tournament）
History of 3D Game Engine
– Monolith公司的LithTech引擎，这款引擎最初是用在机甲射击游戏《升
刚》（Shogo）
引擎的今天（2001年~）
– 由于受到技术方面的限制，把第一人称射击游戏放入大型网络环境中
的构想至少在目前还很难实现。因此，id Software公司重新把目光放
在了单人模式上，《雷神之锤4》和《毁灭战士3》将重新建构一个以
单人游戏为主的引擎 ，同时Epic游戏公司也在紧锣密鼓地开发新一代
Unreal引擎和《虚幻竞技场2》的引擎
3D Game Engine
The Render
Character Skeletal Animation
Natural Physics Simulation
我国的3D网络游戏的现状
The Renderer
How models and worlds are stored is a part of the function of the
render, more than it is part of the application / game. The game logic
doesn't need to know how objects are represented in memory, or how
the render is going to go about displaying them. The game simply
needs to know that the renderer is going to represent objects using the
correct view, and displaying the correct models in their correct frames
of animation.
The Render
3D world
3D space partition
– BSP-tree(Binary Space Partitioning)
Hidden surface remove
– Portal
– PVS(Potentially Visible Set)
3D world
3D objects are stored as points in the 3D
world (called vertices)
Lines of these points form many triangles
These triangles create the while 3D world
Creating the 3D world
3D space partition
What a BSP-tree is?
– A Binary Space Partitioning-tree is a structure that, as
the name suggests, subdivides the space into smaller sets.
Why to use BSP-trees in the 3D engine?
– Optimize a wide variety of areas, such as radiosity
calculations, drawing of the world,portal.
BSP-tree
BSP-tree
BSP-tree algorithm:
The original idea for the creation of a BSP-tree is that
you take a set of polygons that is part of a scene and divide
them into smaller sets, where each subset is a convex set
of polygons.
BSP-tree
Convex(cell):
each polygon in this subset is in front
of every other polygon in the same set.
BSP-tree
A problem: (unbalance)
– You can choose an arbitrary plane in space and divide
the polygons by putting the one son the positive side of the
plane in the right sub tree and the polygons on the negative
side in the left sub tree. The problem with this approach is
that it is very difficult to find a plane that divides the
polygons into two approximately equally sized sets.
(approximately balance)
BSP-tree
A unbalance tree
BSP-tree
The solution: splitting such a polygon into two
polygons.
BSP-tree
A example: how a BSP-tree is generated
BSP-tree
Choose polygon 16 as the divider.
|negative|= 15 and |positive| = 13
approximate balance
BSP-tree
Choose polygon 4 as the divider.
|negative|= 7 and |positive| = 8
approximate balance
Choose polygon 21 as the divider.
|negative|= 6 and |positive| = 8.
approximate balance
BSP-tree
Hidden surface remove
Is it necessary that each hidden polygon is
drawn ?
Answer: unnecessary.
Hidden surface remove
Portal
PVS(Potentially Visibility Set)
Portal rending
The common technique:
– Portal rendering
The basic idea:
– When you render a scene from a viewer’s position with
a viewing frustum and encounter a portal polygon, the
portal clips the viewing frustum. Then the adjacent sector
is rendered from the same viewer’s position but with the
new viewing frustum.
Portal rending
Portal rending
How to know if an object is in the viewing
frustum?
If it is on the completely
negative side of any one of
those planes the object is
not visible
Placing the portals
How to place the portals is one of the big
problems in a portal engine.
A solution need to use BSP-tree.
Placing the portal
The general idea:
1.each portal in the tree must be coinciding with a plane defined by a
dividing polygon in the tree. Out of each of these planes a portal
polygon is created.
2.each portal polygon is pushed down the sub trees of the node it is in.
3.If a polygon is clipped, the two resulting parts are sent down from
the top of the tree. When a portal polygon is not in need of any
clipping, it is sent down to the sub trees of the node currently visiting.
This means that if it is on the positive side of the plane it will be sent
down the right sub tree, and if it is on the negative side it will be sent
down the left sub tree.
Placing the portal
An example of the algorithm
s2
s4 s3
Placing the portal
1. Portal polygon 1 (s1) enters node n1.
In n1 the splitting polygon will be clipped
to fit and one part will
be removed since it
coincides with one of
the polygons in the
pillar. p1 and p2 replace s1.
Placing the portal
2. p1
and p2 enters node s2
In node s2 p1 since it is on the positive side of s2 together
with splitting polygon s2 will be sent to node n2. p2
together with s2 will be sent further down to s3, none of
them will be clipped since they do not cross splitting
polygon s2.
Placing the portal
3. p1 and s2 enters node n2
In n2 p1 is accepted as a portal, so it is not changed in
node n1 either,Polygon s2 that was sent down to s3 in the
previous step is now called p3.
Placing the portal
4. p3 and s3 enters node n3.
Since neither of p2 or p3 is clipped they are pushed
downwards together with s3. P3 and s3 goes down to
node n3 and p2 and s3 is pushed down to node s4.
Placing the portal
5. p3 and s3 enters node n3
6. p2 and p4 enters node s4
Placing the portal
7. p2, p4 and s4 enters node n4
Neither of p2 or p4 need clipping, except for that to fit the
node. But s4 is completely coinciding with a polygon in
the pillar so it is removed.
Placing the portal
8. Nothing enters node n5.
9. The result
Portal p1 is in both n1 and n2.
Portal p2 is in both n1 and n4.
Portal p3 is in both n2 and n3.
Portal p4 is in both n3 and n4.
PVS(Potential Visibility Set)
This PVS is the set of convexes that is visible from the
first convex; it is not only of use during the drawing phase.
The PVS is calculated
during the prerendering of the map.
PVS(Potential Visibility Set)
TRACE-VISIBILITY
Input: Tree – The BSP-tree to trace visibility in.
Output: None
Effect:
– For each leaf in the tree it traces visibility to that leaf’s
connected nodes. Every node that is found visible is added
to the PVS of that node.When a visible leaf is found we
have to trace for visibility to the visible nodes connected
nodes.
PVS(Potential Visibility Set)
PVS(Potential Visibility Set)
TRACE-VISIBILITY (Tree)
1 for (each leaf L in Tree)
2
for (each leaf C that is connected to L)
3
Add C to L’s PVS
4 for (each leaf L1 in Tree)
5
while (there exist a leaf L2 in L’s PVS which’s connected nodes
hasn’t been checked for visibility yet)
5
for (each leaf C that is connected to L2)
6
if (C isn’t in L1’s PVS already and CHECKVISIBILITY (L1, C))
7
Add C to L1’s PVS
7
Add L1 to C’s PVS
3D Game Engine
The Render
Character Skeletal Animation
Natural Physics Simulation
我国的3D网络游戏的现状
Character Animation Techniques
Layered Model
Deformation Techniques
Animation
Layered Model
1.Two layers
skeletal and skin
2.Three layers
skeletal,muscle and skin
3.Four layers
skeletal,muscle,skin
and clothes
Layered Model
Three layers
1. Skeletal
2. Muscle/fatty
3. Skin
Layered Model
Skeletal
– A method to animate articulated objects by
determining
the position of the different elements by the influence of a
series of bones and joints.
How to store skeletal?
1. Positional information of joints
2. Relationship between those joints
3. Bones do not have to be saved in the file
Layered Model
Muscle/fatty
is applied by attaching geometric primitives to the
underlying skeleton.
Skin
Mesh (vertices) or skin is attached to the muscle/fatty
Layered Model
Advantage:
1. The smooth transitions while changing from one
animation to the other.
2.A number of animations can be added whereas the
mesh remains constant.
3.Use a relative small memory footprint.
Deformation Techniques
By using the layered approach for character animation, the
animator can rely on the skeletal layer to control the
motion of the character.
In order to achieve perceptually realistic movement, the
higher layers must deform in accordance with the
surrounding layers.
Deformation Techniques
Joint Dependant Local Deformations
Non-linear Global Deformation
Implicit Surfaces
Free Form Deformations
Joint Dependant Local
Deformations
Joint Dependant Local Deformations
This animation technique, which uses a polygonal mesh
skin digitized from a sculpture, maps each vertex point to a
particular point on the skeleton using JLD operators.
Depend on the nature of the joints, and control the
evolution of the surface.
Joint Dependant Local
Deformations
Disadvantage:
this method relies on data that is specific to a given
joint.
Non-linear Global Deformation
• General idea:
– Changing the transformation matrix while it is being
applied to the object. Thus the way in which the matrix is
altered becomes a function of the position at which it is
applied.
(X,Y,Z) = F(x,y,z)
(X,Y,Z) represent the new tapered vertex., F represent the tapering operation
the vertex (x,y,z)
Implicit Surfaces
Implicit Surfaces
Surface representation through a function:
F(P) – Iso=0
F(P): the implicit function
Iso: threshold value at which
the surface is defined.
Implicit Surfaces
Advantages
Smoother and more precise
More compact
Easier to interpolate and deform
Disadvantages
More difficult to display in real time
Implicit Surfaces
Types of Implicit Surfaces
Mathematic
– Polynomial or Algebraic
– Non polynomial or Transcendental
Exponential, trigonometric, etc.
Implicit Surfaces
Algebraic Surfaces
Cubic
Degree 4
Degree 6
Implicit Surfaces
• Non-Algebraic Surfaces
Implicit Surfaces
Compression with mesh
Mesh of 473,000 vertices
and 871,000 facets
Implicit function of 32,000 terms
Free Form Deformations
Instead of applying deformations to the object directly, the
object is embedded in a space that is then deformed using
Bezier theory
Free Form Deformations
Advantage:
– Generality
– Naturally
Disadvantage:
– In the co-ordinate
Free Form Deformations
Extended FFD
– Alter the control point mesh from a parallelepiped
arrangement to a different shape (cylindrical) that results in
a more closely fitting lattice.
–
Avoids unusual deformations
Free Form Deformations
Free Form Deformations
In this way the EFFD and the object become disassociated
from one another.This overcomes the problem of
unwanted global deformations which occur as a result of
changes to the co-ordinate system.
Animation
Method 1:(Traditional Method)
– An articulated figure in computer graphics involves
specifying each particular part at certain key locations in
space, and then using some interpolation technique to
animate the in between frames for the motion in question.
(key framing and the manual input of poses)
Animation
Method 2:
inverse-kinematics:
– Determines the position and orientation of all joints in the hierarchy
given an end-effectors state. accelerations. It does allow for a more
dynamic approach to character animation, however, since specific
motions do not have to be predefined.
forward-kinematics:
– The process of explicitly specifying all joint motions in order to
determine the position of the free end of a chain.
Animation
Method 3: (Popular technique)
– Realistic motion is generated by capturing the motion of
a real world actor, either by optically tracking special
sensors attached to key points on the actor’s body or by
tracking them magnetically.
(motion capture)
3D Game Engine
The Render
Character Skeletal Animation
Natural Physics Simulation
我国的3D网络游戏的现状
Natural Physics Simulation
Why Physics?
Games based on the real world should look realistic,
meaning realistic action and reaction.It is easy to get it
right, or at least approximately such as Newton’s Laws and
Gravity but not easy Deformable bodies, Cloth and Fluid
dynamics.
Natural Physics Simulation
Particles
Rigid bodies
Particles
Kinematics of Particles
– Position
– Velocity
– Acceleration
x
v = dx/dt
a = dv/dt = d2x/dt2
Motion Under Uniform Acceleration
– Acceleration
– Velocity
– Position
a=a0
v   a dt  a 0 t  v 0
1
x   v dt  a 0 t 2  v 0 t  x 0
2
Particles
• Mass & Momentum
– Mass
– Momentum
– Force
m
p = mv
f = dp/dt = m(dv/dt) = ma
• Gravity
– Gravity near Earth’s surface is constant:
f=mg
(g = -9.8 m/s2)
– Gravity for distant objects:
f=Gm1m2/r2
(G=6.673×10-11 m3/kg·s2)
Particles
• Newton’s Laws
1. A body at rest tends to stay at rest, and a body in motion
tends to stay in motion, unless acted upon by some force.
2. Forces lead to changes in momentum and therefore
accelerations:
f=ma
3. Every action has an equal and opposite reaction.
fij=-fji
Particle Simulation
UpdateParticle(float time) {
Force=ComputeTotalForce();
Momentum=Momentum+Force*time;
Velocity=Momentum/Mass;
Position=Position+Velocity*time;
}
Rigid Bodies
Angular Momentum
L=Iω = AI0A-1ω
– L=angular momentum – I=rotational inertia
– ω=angular velocity – A=3x3 orientation matrix
Forces & Torques
τ=dL/dt
A torque is a change in angular momentum (similar to a force which is a
change in linear momentum)
Rigid Bodies
Offset Forces
Torque resulting from offset force: τ=r×f
Total force:
f cg   f i
Total torque:
 cg   (ri  fi )
(r:质点的位置方程)
Rigid Bodies
Rigid Body Simulation
UpdateRigidBody(float time) {
Force=ComputeTotalForce();
Torque=ComputeTotalTorque();
Momentum=Momentum+Force*time;
Velocity=Momentum/Mass;
Position=Position+Velocity*time;
AngMomentum=AngMomentum+Torque*time;
Matrix34 I=Matrix*RotInertia*Matrix.Inverse();
AngVelocity=I.Inverse()*AngMomentum;
Matrix.Rotate(AngVelocity*time);
Collision Direction
The objects must be encapsulated in one or
more simple geometric shapes.(sphere,ellipse)
Different types of collisions
– Circle/sphere against a fixed object
– Two circles/spheres
Circles and Planes
Simplest case
–
Assume circle hitting an immovable barrier
• Detect that a collision occurred
–
If the distance from the circle to the line < circle
radius
Circles and Planes
Circles and Planes
Facing value: the value that tells how a polygon is
directed compared to an object
Calculation:
the dot product of the normalized
movement vector for the object and the normal for the
polygon
Result:
a value between –1 and 1
Circles and Planes
What if more complex background:
–For complex surfaces, pre-compute and fill an array with
collision points (and surface normals).
Circles and Spheres
If the distance between two objects is less
than twice their radii
– (r1 + r2)2 > ((x1 –x2) 2 + (y1 –y2) 2)
Other Simulation technologies
Deformable bodies
Fluid dynamics
Vehicle dynamics
Characters
Others technologies
Highly flexible AI system
Real time 3D dynamic lighting and shadows
Real time 3D particle system
Real time 3D sound processing
Cross platform internet TCP/IP based network protocols
Client-Server based on-line game network architecture
3D Game Engine
The Render
Character Skeletal Animation
Natural Physics Simulation
我国的3D网络游戏的现状
我国的3D网络游戏的发展状况
2003年7月科技部将网络游戏纳入863项目。
2004年，国家新闻出版总署明确指出，支持具有自主知识产权的数字娱
乐软件的开发，并对网络游戏的进口采取了部分限制。
2004年2月25日，金山在京召开“技术立业决胜网游——金山公司2004新
架构新战略发布会”。金山公司决定在３年内投资２亿元用于产品研发，
2004年预计投入7000万元。《剑侠情缘网络版》后续版本，《剑侠情缘
外传》，《剑侠情缘网络版》的全新３Ｄ版《封神争霸》
2004年8月18日，信息产业部电子教育中心联合香港职业训练局和北京汇
众益智科技有限公司，共同推出了本次的游戏专业人才培训项目，组建
游戏学院，以期将它发展成为亚洲最大的游戏人员培训基地。9月8日信
息产业部组织了90名专家对2004年信息产业发展基金重点招商项目进行
了评标，结果网络游戏成为今年信息产业发展基金19个重点招商项目之
一。
2004年9月8日信息产业部组织了90名专家对2004年信息产业发展基金重
点招商项目进行了评标，结果网络游戏成为今年信息产业发展基金19个
重点招商项目之一。