章3-角色(二、三维角色人体模型,场景建模).doc

第三章 角色
3.1 前言
“角色”一词的源于戏剧，自1934年米德（G.H.Mead）首先运用角色的概念来说明个体在社会舞台上的身份及其行以后，角色的概念被广泛应用于社会学与心理学的研究中。社会学对角色的定义是“与社会地位相一致的社会限度的特征和期望的集合体”。角色是一个抽象的概念，不是具体的个人，它本质上反映一种社会关系，具体的个人是一定角色的扮演者。
而在我们动漫产业中，角色更是一个非常重要的元素，没有一个吸引人的角色，就出不了一个好的作品。我们本章来介绍角色的建模。
3.2 骨骼动画原理
骨骼动画(Skeletal Animation)[9]又叫Bone Animation它与关键帧动画(Key-frame Animation)相比，占用空间小，因为它不需要像关键帧动画那样在每一帧中存储各个顶点的数据，而只需要存储骨骼变换数据，骨骼与顶点相比，当然要少得多。所以骨骼动画有很多优势，当然其技术难度也很高。骨骼动画在计算机图形学中是一个十分重要的内容，不管是在游戏、电影动画还是虚拟现实中，生动逼真的角色动画（人、动物等）会使其增色不少。
骨骼动画的实现思路是从人的身体的运动方式而来的。动画模型的身体是一个网格(Mesh)模型，网格的内部是一个骨架结构。当人物的骨架运动时，身体就会跟着骨架一起运动。骨架是由一定数目的骨骼组成的层次结构，每一个骨骼的排列和连接关系对整个骨架的运动有很重要的影响。每一个骨骼数据都包含其自身的动画数据。和每个骨架相关联的是一个“蒙皮”(Skin)模型，它提供动画绘制所需要的几何模型信息(Vertex信息,Normal信息等)和纹理材质信息。每个顶点都有相应的一组权值(Weight)，这些权值定义了骨骼的运动对有关顶点的影响因子。当把动画人物的姿势和全局运动信息作用到骨架上时，这个“蒙皮”模型就会跟随骨架一起运动。
3.2.1实时角色动画
由于骨骼动画是从另外两种实时角色动画发展演变而来，因此，为了更好的理解骨骼动画的原理，就很有必要对它们进行研究分析。角色动画是计算机动画技术的一个重要组成部分，也是计算机图形学的一个重要分支。在实时渲染环境下，主要应用于虚拟现实，视频游戏，甚至是建模软件，动画制作软件。现在，随着计算机硬件技术的发展，特别是带有硬件加速功能的显卡性能的提高，实时渲染的角色动画技术得到了较快的发展且被广泛的应用。目前，实时角色动画技术大体可分为三种类型。

图2-1关节动画组织结构图

第一类是关节动画（Joint Animation）。关节动画中的角色模型由若干相互独立的部分组成（如图2-1）。每一部分对应一个独立的网格模型，相应的对应于某一个身体关节，不同的部分按照角色的身体特征组织成一个层次结构。比如说，一个人体模型可以由头，身体，右上臂，右小臂，右手，左上臂，左小臂，左手,右大腿右小腿，右脚，左大腿，左小腿，左脚等各部分组成。而某个部分，可能是另一个部分的子节点，同时又是另一个部分的父节点。通过改变不同关节之间的相对位移和夹角等，就可以实现所需要的各种动画效果。这类动画的优点是：
在动画的每个关键帧中只需存储关节之间的相对变化，因此动画文件需要的存储空间很小。关节动画的缺点是：在关节之间的连接处往往会有很明显的接缝，这会对模型的真实感造成严重影响。目前关节动画的应用范围主要在辅助教学领域。
第二类是关键帧动画（Key-frame Animation）也叫顶点动画（Vertex Animation）。关键帧动画中的角色模型由一系列的渐变网格构成。在动画序列的每一关键帧中记录着每个顶点的当前位置信息。通过在相邻关键帧之间插值来更新网格模型中顶点的位置就可以实现动画效果。相对于关节动画，关键帧动画不存在关节动画的接缝问题，角色也更逼真。由于顶点的位置是直接获得的，相对于关节动画其计算量也很小。但是，这类动画的灵活性很差，很难来使角色实时
的与环境进行交互。另一方面，由于关键帧中要存储所有顶点的信息，动画文件的存储空间很大。目前，关键帧动画的主要应用对象是一些顶点数目有限的角色模型，并且需要的动画简单单一，比如游戏中的小动物等，此时用不大的空间开销来换取计算时间的节省，是比较有效的方法。
第三类是骨骼动画（SkeletalAnimation）。骨骼动画可以看作是关节动画和关键帧动画的结合。他同时兼有关节动画的灵活和关键帧动画的逼真。后面将详细介绍骨骼蒙皮动画的技术细节。
3.2.2 骨骼动画简介
骨骼动画(SkeletalAnimation，又叫BoneAnimation)可以看作是关节动画和关键帧动画的结合。骨骼动画兼具了两类动画的优点又克服了它们的缺点。骨骼动画的实现思路是从人身体的运动方式而来的，它基于面模型的方法把角色建模为两层：骨架层（Skeleton layer）和皮肤层（Skin layer），与基于层次式模型方法不同，骨骼动画建模不考虑中间的脂肪层（Fat layer）和肌肉层（Muslce layer）。
骨骼层描述了角色的骨架结构（如图2-2左），类似于关节动画中的关节，骨骼动画中的骨骼按照角色的身体特征组成一个层次结构。相邻的骨骼通过关节相连，并且可以做相对的运动。通过改变相邻骨骼间的夹角，位移，组成角色的骨骼就可以通过影响外面的皮肤层模拟出不同的动作，从而实现各种动画效果。

图2-2骨骼动画的骨骼结构图（左）和角色模型图（右）
蒙在骨骼之上的皮肤层，它是一个蒙皮（skin）模型（如图2-2右），它提供动画绘制所需要的几何模型信息，定义了角色的外观。这里的皮肤不是固定不变的刚性网格，而是可以在骨骼影响下可变形的网格。类似于关键帧中的顶点网格，每个角色模型只需要保存一个网格模型的数据；不同于关键帧动画，在动画文件中不需要在每个关键帧中保存顶点信息。
3.2.3 骨骼动画创建
骨骼动画的创建过程其实就是预处理的过程，这一过程是由美术创作者完成的，必要的时候可能会分别由3D建模工程师和3D动画工程师分别完成模型造型和动画制作工作。但也需要跟程序开发者有良好的沟通，比如模型的骨架层次定义、模型子网格划分等等。下面就对模型造型和动画制作分别予以讨论。因为本文的目的是研究骨骼动画技术，因此，本文完全没有涉及动画领域的艺术性问题。讨论美术创作者的工作也是为了便于讨论骨骼动画所涉及到的原始数据构成，以方便对骨骼动画有完整的理解。
角色模型的创建：角色静态模型一般是指骨骼动画中用来被骨骼动画参考的静态模型，它是一个单一网格模型。所有的动画将基于该静态模型创建，即动画数据中的平移旋转信息均是相对于该静态模型的。对于该网格的创建，有一些要求，比如在关节处的顶点数目应该多一些（如图2-2右）。角色骨骼层次也要对应的创建起来，并且骨骼的大小和位置关系应该与皮肤网格相适应。另外最重要的一点，还要指定网格上的顶点到骨骼的映射关系以及相应的影响权值。每块骨骼都一个影响范围，在这个范围内的顶点都要受到该骨骼的影响。每个顶点至少要受到一块骨骼的影响，但在关节处的顶点往往可能会受到多块骨骼的影响，这些骨骼通过对应的权值来叠加作用到该顶点。因此在指定权值时，一般需要有经验的动画师来实现。
动画的创建：即通过操作骨架结构的变换来构建角色动画。设置每块骨骼的运动信息，使其带动网格模型上各个顶点运动，从而形成动画。可见，动画的创建过程就是对骨骼变换的过程。
上述两种数据的创建都可以通过专业的3D动画编辑软件如3DMAX、Maya等实现，但合适逼真的角色动画工作需要建模师和动画师有相当多的经验。
3.2.3 骨骼动画数据信息
在美术师们完成了原始数据的创建之后，一般这些数据还是以3D动画编辑软件内部的数据结构进行存储，比如3DMAX采用的.max文件结构。要使得这些数据被应用程序使用，还需要程序开发者将它们转化为适合于程序使用的数据结构。这就需要编写导出插件，用于将原始数据转化为需要的形式。例如Panda XExporter就是一个广为人知的导出插件，它可以将.max文件转换为.x文件所要求的数据格式。一般来说，每个游戏厂商都会有自己的骨骼动画引擎，相应的就需要有对应的插件来实现数据结构的转换。由于这些涉及到3D动画编辑软件内部的数据存储管理，对本文讨论的主题没有太多的意义，因此本文不会涉及这些插件技术的内部细节。为了便于后面的讨论，下面将会对转换后的骨骼动画信息进行归纳总结。
对应于原始数据，在通过插件导出之后，一般通过两种不同的文件结构分别保存角色模型数据和角色动画数据，下面分别对它们进入分析。
一、角色模型数据
由于骨骼动画的需要，在静态角色模型中，不仅仅要包含角色网格模型信息，而且还要包含用于骨骼动画的相关信息。这些信息包括：
角色网格数据：包括所有皮肤顶点信息，每个蒙皮顶点中包含的信息至少包括：与该顶点相关联的骨骼索引组，以及每个骨骼的影响权重值组，顶点初始位置信息（注：还有可能包含其他的信息比如纹理坐标信息，顶点颜色信息，顶点法线信息等等，但本文在此只关注骨骼顶点相关的信息）。由于是单一网格模型，对每个顶点来说，对应的信息只需保存一次。
模型索引数据：索引数据主要是用来保存顶点之间的连接关系，每三个顶点构成一个三角形面，而三角形面即是用于渲染的基本图元，索引数据每三个为一组记录的这种三角面关系。
骨骼层次信息：每个角色都有一个骨架层次结构，一般是树形结构。对所有的骨骼要有一个统一的编号，每块骨骼都要记录其父骨骼。
二、角色动画数据
从动画师的角度看，动画就是可视化的骨骼变换操作。从程序开发者的角度来看，每个动画文件中要保存的信息如下：
1、每块骨骼的关键帧编号。对于一块骨骼而言，它的变换信息是通过关键帧的形式保存的，比如需要在第一、三、七、十帧中记录一块骨骼的变换信息，那么第一、三、七、十帧就是需要保存的关键帧。
2、每个关键帧的变换信息。对于一块特定骨骼的特定关键帧来说，需要记录其变换信息，一般是通过矩阵记录的。
3.2.3 骨骼动画的载入
1.先来看看静态模型的载入。
由上文的论述可知，静态模型的载入过程实际上是对网格数据、索引数据以
及骨架层次三类信息的载入过程。如何对这三个信息予以管理以便于骨骼动画的实现是骨骼动画实现的基础，因为骨骼动画的驱动过程就是依靠这些结构来实现的，下面将对它们分别予以分析。
1、网格数据的载入和管理
对于单个顶点来说，可能需要保持的信息是相当多的，比如纹理坐标信息，颜色信息，顶点信息等等，这用于渲染的顶点信息是对称的，即每个顶点所需要的存储空间是一样的。
此外，为了实现骨骼动画算法，顶点需要保持与骨骼动画相关的信息，如与该顶点相关联的骨骼索引组，以及每个骨骼的影响权值组等等。值得一提的是，并不是所有皮肤顶点所关联的骨骼数目都是统一的，比如在关节处的顶点所关联的骨骼数肯定要多于非关节处顶点所关联的骨骼数目。
因此可以通过两个不同的顶点结构来保存两者。这样做的好处在于，用于渲染的顶点结构，它直接记录了渲染所需要的信息；而用于骨骼动画计算的顶点信息，它包含了骨骼动画实时运算所需要的顶点数据。
2、索引数据的载入和管理
索引数据主要是用来保存顶点之间的连接关系，每三个顶点构成一个三角形面，而三角形面既是用于渲染的基本图元，索引数据每三个为一组记录了这种三角面关系。
3、骨骼层次信息的载入管理
为了实现骨骼动画，每个角色都有一个骨架层次结构，一般是树形结构。如图2-3所示是角色模型的骨架层次结构，按照不同的细节要求可以对骨架进行更细微的分解。其中向下箭头表示父子关系，向右箭头表示兄弟关系。

图2-3人体骨骼组织结构图
对所有的骨骼要有一个统一的编号。在载入过程中，只需记录每块骨骼的父骨骼信息和子骨骼信息，这实际上是一个双向链式树形结构。这样，当在应用程序实时运行的时候，一旦需要获得父骨骼的平移旋转信息，凭借父骨骼编号，就可以迅速的找到对应的父骨骼节点。
可以定义下面的数据结构予以保存
骨骼数据结构
{
骨骼编号；
父骨骼；
局部变换矩阵；
全局变换矩阵；
};
在后面的章节中将会看到，骨骼动画驱动的过程中，将通过动画数据更新该结构中的局部变换矩阵，借以更新全局变换矩阵，最终，通过该结构中的数据来更新皮肤顶点信息，实现动画效果。
2.再来看看动画数据的载入。
基于上节中讨论过的动画信息可知，要对以下几类信息进行管理。针对动画所涉及到的每块骨骼，要保存其关键帧数据。每个关键帧数据的内容包括：该帧的编号，该帧中该骨骼相对于父骨骼的平移信息以及旋转信息。由于此类信息上文中已经做出总结，这里就不再多加讨论。
动画数据可能有很多，比如在一个典型的高尔夫游戏中，其中一个角色，可能需要他的各种动画，比如走动、击球、推杆、捡球、庆祝动作等等。对于个人角色扮演类的游戏应用，可能需要的动作更多，如果每个动画对应于一个文件，那么就可能需要很多个文件来保存动画数据。对于这些数据，选择适当的时机对其进行载入是一个比较重要的问题，因为，一款游戏可能有许多不同的角色，如果是在应用程序启动的时候一次装载所有的数据，那么会造成比较慢的启动速度，最重要的，他们将会占用大量的内存，导致内存开销过大。有些角色可能从前到后就没有使用过，就造成了内存资源的浪费。因此，要在合适的时间内对数据进行载入。比如在游戏应用中，一般会有人物选择界面，可以根据用户的选择来动态的载入角色的全部动画或者部分动画。
3.2.3 骨骼动画的驱动
在应用程序播放某一具体的动画的过程中，骨骼动画引擎需要动态的根据指定的动画按照播放速度的要求正常驱动动画效果的产生，骨骼动画的驱动过程就是骨骼动画实时计算的过程。在交互式应用中，一般是在用户输入某些控制命令后，角色模型开始完成相应动画。这就要求应用程序在接受到命令后，需要动态实时的完成这些工作。
当确定了需要的动画之后，对于某一个具体的动画而言，在某一具体的时刻，其驱动步骤可以分为：
1、对骨骼局部变换信息进行更新。确定该动画在该该时刻的两个插值关键帧，即找到该时刻之前之后的两个关键帧。然后按照时间对这两个关键帧进行插值（应用中使用最多的是对其进行线性插值），从而确定每一块骨骼该时刻在父骨骼坐标系下的变换信息（平移和旋转信息）。
2、对骨骼全局变换信息进行更新。对骨架层次结构进行遍历，从根骨骼开始，计算每一块骨骼相对于身体坐标的全局变换信息（一般是用矩阵形式来表示），这一步骤是基于上一步骤完成的，由于第一步中已经得出了每一块骨骼的相对变换信息，本步骤中只需从根进行递归遍历即可。
3、对网格顶点进行更新。对于皮肤网格中的所有顶点，计算其在身体坐标系下的位置和法线信息。根据每个顶点所关联的骨骼以及对应的权值，就可以利用每块骨骼的全局变换信息来对顶点进行变换。
再来看看驱动的过程。
每根骨骼存在两个相关的变换矩阵：局部变换矩阵和全局变换矩阵。局部变换矩阵记录了该骨骼在父骨骼坐标系空间中的位置和朝向。全局变换矩阵用来决定该骨骼在整个角色空间中的位置和朝向。
在骨骼动画动画文件中存储的是骨骼的局部变换矩阵序列，骨骼的全局变换矩阵则需要通过另外的计算来获得。由于骨骼的运动实现是通过层次结构互相影响的，所以全局变换矩阵不能一步就能获得。

图2-4父子骨骼变换关系
下面举例说明一下全局变换矩阵的获得，如图2-4。首先看旋转变换，在图中有两块骨骼，左边的父骨骼和右边的子骨骼。要获得两个骨骼的全局变换矩阵来用于皮肤顶点的更新。子骨骼的局部变换矩阵保存的是它相对于父骨骼旋转信息。但其父骨骼也有自己的变换信息，也做了一些旋转，因此，要获得子骨骼对于整个角色的全局变换矩阵，就需要将其局部变换矩阵与父骨骼的变换矩阵相乘。
如果矩阵中加入了平移变换，同样的过程也要被执行。
从例子中可以了解到父骨骼的局部变换矩阵不仅会影响到其自身，而且还会影响到它的子骨骼。根骨骼的全局变换矩阵等于其自身的局部变换矩阵。这样旋转、平移变换在骨架层次结构中依次被继承下来。
一、骨骼局部变换更新
首先是查找关键帧，对于特定动画的某一骨骼而言，需要在该骨骼的所有关键帧序列中找到最合适的一个关键帧或者两个关键帧。
其次是对关键帧插值。如果合适关键帧为两个，就需要对其进行插值。插值的算法有很多，在这里采用（平移，旋转）对分别插值进行处理。对平移信息的插值采用简单的线性插值即可。对旋转信息而言，通过四元数[19]的球面线性插值（Slerp Linear interpolation）来实现，球面线性插值可以实现对旋转信息的线性插值。设p,q是需要插值的两个四元数，t为0到1之间的参数值。则球面插值（Slerp Linear interpolation）的公式为：
Slerpp,q,t=psin1-tθ+qsin(tθ)sinθ
插值工作完成之后，利用插值好的平移和旋转信息计算获得对应变换矩阵，保存在该骨骼数据结构的局部变换矩阵中。至此，对骨骼的局部变换更新已经完成。
二、骨骼全局变换更新
骨骼的全局变换依赖于局部变换，对于每一块骨骼来说，他的全局变换矩阵就等于父骨骼的全局变换矩阵乘以本骨骼的局部变换矩阵。因此，要计算骨骼的全局变换矩阵就要先计算其父骨骼的全局变换矩阵。可以通过对骨架层次的深度遍历计算得出所有骨骼的当前全局变换矩阵。下面给出一种通过递归遍历实现算法。
计算全局变换矩阵函数(骨骼数据结构)
{
如果骨骼没有父骨骼：
全局变换矩阵=本骨骼的局部变换矩阵;
否则
{
如果父骨骼全局变换矩阵没有计算：
计算全局变换矩阵函数(父骨骼)；
全局变换矩阵=本骨骼的局部变换矩阵*父骨骼全局变换矩阵;
}
}
从前面的论述可知，当局部变换矩阵更新完成之后，调用此函数对每个骨骼进行全局矩阵变换矩阵更新即可。
三、皮肤顶点更新
这里本文采用传统的“蒙皮”算法，该算法的缺陷以及改进将在后面的章节进行研究。这个过程对每个顶点而言，需要根据它所关联骨骼的全局变换矩阵基于骨骼影响权值对顶点进行变换.
“蒙皮”算法的本质是一种插值算法，它的基本思想是使关节处的皮肤顶点受到与关节邻近的几块关联骨骼的影响，影响的大小由权值确定。
其基本公式为：
v=i=1nωi∁ivi 其中 i=1nωi=1
其中，vi是顶点在第i个关联骨骼子空间的局部坐标，∁i是第i个关联骨骼的全局变换矩阵，ωi是第i个关联骨骼的权值，它们的和为1。
至此，骨骼动画顶点信息已更新完毕，可以对更新后的网格数据进行渲染。需要说明的一点是，本文之前的讨论并没有涉及到角色的材质以及纹理信息。骨骼蒙皮动画结合细腻的纹理甚至光照计算，会使角色更为生动逼真。
3.3 场景建模管理
如何很好地表示出包含着成千上万物体的复杂场景，是设计系统必须要考虑的。这也是场景管理需要做得，给场景提供良好的层次关系，以便更好地进行筛选和隐藏面消除。场景管理涉及到可视性处理和碰撞检测，系统需要判断场景的哪些部分在视见约束体之内，另外如果两个物体有碰撞关系，则需要计算碰撞点的值。
为了达到好的实时效果，传统的技术不可能适用，因为场景己经非常复杂，如果只采用Z缓冲的方法进行可见性处理是不现实的。目前己经有了将场景分层的方法，可以把辅助数据结构应用于场景中，先把场景分区，再分物体，甚至一直分割到多边形。如在室内场景管理中有两个经常用到的层次体系:BSP(Binary Space Partitioning)树，这是八叉树的推广，和包围体树(Boundingvolume tree)。前者用于加速剔除，而后者主要用于碰撞检测。
本节简单讨论如何使用层次体系进行更加高效的筛选以及可以采用什么样的数据结构来组织场景。
3.3.1 场景的组织和管理
场景的组织结构是渲染系统最基础和最重要的部分，也是一个实现的难点。它的决定会决定很多后续的工作，如碰撞检测，消隐，阴影等。
首先要涉及到的概念是空间细分，空间细分考虑整个物体空间并且根据物体的空间占有(Object occupancy)对空间中的每一个点进行分类。可以把世界空间中的物体细分为立方体素(voxel)，再对体素进行分类。八叉树(octree)是一种描述三维空间的树状数据结构，它可以描述一个三维场景内物体的分布情况，并简单地将体素安排在层次结构中。
因此场景管理可以在预处理的时候建立一棵树，这里可以忽略物体的表示方法，而把焦点集中在场景的划分上。在树建立起来之后，通过实时遍历这棵树来发现是否有两个物体占据了同一个空间而发生冲突，或者一个物体的空间是否不在视见约束体之内。这样，所有筛选等操作都可以简化为对树的遍历，这是一个线形时间的操作。
另一种表示场景的数据结构是BSP树，它被广泛应用于室内场景的处理中，它使用一个分离面(splitting plane)对每一层一分为二，从而实现对空间的划分，其中用于分割的平面可以出现在任何方位。BSP的想法最早在Fuchs(1980)中被提出，起初的目的是为了解决实时地消除隐藏面。BSP可以说是八叉树的一般化。前人在这方面已经做了很多有效的工作，Fuchs首次将BSP技术中剖分平面的定侧性质应用于多边形场景的剖分，建立起空间二叉树结构.该二叉树的每一结点表示一个子空间及空间内所包含的多边形。在每一结点空间中，选取其中一平面作为剖分平面，将该空间继续剖分成正负两子空间，分别作为该结点的两个子结点，其中与剖分平面有交的多边形被分割成两个多边形，分别归入相应的子空间中。上述过程是一个递归过程，直至每一子空间仅包含一个多边形为止。与八叉树剖分相比，BSP树具有内存耗费小，剖分方式灵活，产生的无效区域较小的优点;且对大部分场景来说，BSP树较八叉树更为平衡。
另外，由于是二分空间，因此方向性很强，在判断上要比八叉树容易，既可以代替Z-Buffer解决遮挡问题，因为BSP是可以确定物体的绘制顺序的，按照这个顺序就可以保证没有Z-Buffer也能够显示正确，还可以方便地执行碰撞检测。
3.3.2 三维场景编辑的基本操作
因为不同的数据对应不同的操作，所以要先将场景中的模型数据进行分类。各自的属性将场景数据分为以下4类:
(1)内部属性，各类对象自身所特有的属性，如物体的长、宽、高等属性。支持用户对几何模型的鼠标点取操作，在内部属性里保留了对模型对象的引样就可以根据用户点取的结果检索到相应的数据项，从而访问该物体的各性。同时，在内部属性里还为灯光对象提供了附加的几何形体，如用一个小格四面体来代表POINTHGHT，由此用户不仅可以明确场景中灯光的空间，也可以像操作普通几何体模型一样操作灯光对象。
(2)表面属性，场景对象的外观属性，这个属性主要针对三维场景中的基何实体。表面属性中的主要对象是ApPearance类型对象。APpearance对象了所有控制物体外观显示的属性值，包括几何体颜色、线框图、材质、纹理等。
(3)空间属性，指物体在空间的位置、方向等属性，这个属性也主要针对场景中的基本几何实体。在场景图中，物体的空间方位是由变换矩阵和组进理的。组通过设置变换矩阵，来改变组内所有物体的空间属性。
(4)附加属性，为了方便场景编辑软件等应用程序对场景模型进行快速的而设置的属性。包括模型名字、参数、D、属性索引等。主要目的是为了方据的检索，以便将应用程序的内部数据和三维场景中的数据对象有机地结合，有效地对场景对象进行管理。定义了这四种类型的场景数据后，用户可以进行如下的操作:
(1)创建，系统根据用户提供的参数创建场景对象，添加到场景中。并将节点分配到场景图一个组当中。
(2)选择，系统根据用户的选择条件，如选择的物体名称、点取的场景对信息，从场景图中检索到相应的条目，将此数据条目设置为选中对象。
(3)删除，系统就将选中的对象从场景中摘走，同时将场景图上对应该场节点删除。
(4)编辑修改，若修改不可重复设置的属性，系统首先将选中的对象从场中清除，然后创建新的对象，加入到场景中，同时在场景图建立对应的节点；若修改可以重复设置的属性，系统直接调用相应的方法，将新的属性传递给场景图上的属性节点进行替换。。
(5)三维变换，三维变换操作一般包括平移、旋转和缩放这3种操作。实现三维变换有两种方案，第一种方案是视点不动，变动整个场景的空间位置，虽然易于实现，但计算量比较大，效果不理想，且有可能出现空间上的错位；第二种方案是仅对视点的空间位置进行变换，虽然需要额外的对视点坐标进行变换计算，但效果比第一种方案好。
(6)多视图显示，在场景图中创建多个视图对象就可以实现对场景的多视
图显示，其中每个视图拥有独立设置的投影矩阵。
3.3.2 BSP Tree（Binary space partitioning）
首先，将整个场景包围在一个AABB（外包盒）中，然后以递归形式将此外包盒分为若干比较小的盒子。通常是选取盒子的一个轴，生成与之垂直的平面，将其分为两个小盒子。一般是将盒子分为完全相同的两个部分。与分割平面相交的物体，或存储在此层次上，成为两个子集中的一员；或被这个平面分割成两个不同的物体。重复这个平面分割过程，就可以对每个AABB进行递归细分，直到满足某个标准。通常这个标准是用户定义的树的最大深度，或者是盒子内所包含的集合图元数量低于用户定义的某个值，或是到达叶子节点（全部节点都为凸包–最小凸多边形）。
简单说来，这种思想就是以平面来递归分割场景的。场景中会有许多物体，我们以每个物体的每个Polygon当成一个平面，而每个平面会有正反两个面，就可把场景分两部分，先从第一个平面开始分，再从这分出的两部分各别再以同样方式细分……如此进行，就可把场景建构出一颗二叉树。
在三维场景的构造过程中，建模是主要工作。在单元级划分中，若使用八叉树表示法进行建模，存在空间浪费的情况。因为八叉树用三个相互垂直的平面递归地分割空间，在树的每一层上将空间等分成八份。这样的等分空间将造成存储空间的部分浪费，并且物体的表示精度直接依赖于划分的层次深度，也就是树的高度
BSP树可以看作是八叉树的一般化，只在需要进行划分的时候才进行，而不是每次都将三维空间等分。将划分的维度从三维降低到一维，并且将等量划分转变成按需划分，节省了很多操作和存储空间。
BSP树递归的把空间分成两个子空间，分割的平面可以是任意朝向和任意位置的。BSP树的每个中间节点对应一个平面，并且有两个子节点指针，指向平面的两侧。下面给出BSP树的形式化定义:
三维空间中的一个平面H:ax+by+cz+d=0确定了两个开的半空间，分别用环和H表示，其中H+={(x，y，z)|ax+by+cz+d>0;H-={(x，y，z)|ax+by+cz+d组成的场景S，对应的BSP树可以定义为一棵具有如下性质的二叉树T:
树T的叶子节点是物体或被分割面H切开的物体碎片。
树T的中间节点是分割平面Hi，左子树对应Hi-空间，右子树对应Hi+空间。即左子树空间中的物体s满足: ax+by+cz+dO。

图3.3场景及其BSP树表示
图3.3(a)表示一个场景，(b)是对应的BSP表示树。场景中包含三个物体AB、C和D与2个分割面P1和P2。Pl将物体AB分成A和B场景中包含三个物体AB、C和D与两个分割面Pl和P2。D一起处于BSP树的叶子中，而BSP两部分，树的中间节点就是分割面P，和P:。它们与C、分割后物体在树中的位置指示了物体在场景中所处的区域。
3.3.3 构造BSP树
1.先来看看用自动划分的方法构造BSP树。
虽然在建立BSP树的过程要尽量选择优化的分割面，使得最终生成的BSP树的规模较小，但划分时分割面的选取仍然具有很大的自由度和任意性。实际中常用的两种分割面的选取方式是:
(1)选择与某个轴垂直的平面作为分割面;
(2)直接使用场景图中物体的三角面片所在的平面作为分割面。
由于使用与轴垂直的平面作为分割面可能会引入更多的分割面，所以应当直接使用场景中物体的三角面片所在的平面作为BSP树的分割平面。
由三维场景中物体的三角面片生成BSP树的算法如下:
BSP树TalgorithmBSPConstnjct(场景图的三角面片集合s)
if(S包含1个三角面片)
{
直接生成BSP树T，S存储在T中
return T
}
else(将第一个三角面片S。所在平面P。作为分割面)
{
T+=algorithmBSPconstruct(位于扩空间的三角面片集合)
T-=algorithmBSPconstruct(位于环空间的三角面片集合)
H=S0
return T
}
}
上述算法能够根据三维场景的三角面片集合S得到对应的BSP树，但由于每次分割时，直接使用第一个三角面片S。所在的平面P。作为分割面，而这个平面的位置并不一定是最优的，这使得整个算法的稳定性大大下降。该算法生成BSP树的效率，或者说是生成的BSP树的规模，主要取决于三角面片集合的输入顺序。如果能够有一种较好的三角面片的选取策略，则可以提高生成BSP树的效率。
只要在每次分割的时候选取的分割面与其余的三角面的相交尽可能的少，就能保证整个算法的高效性和稳定性。现在有两种方法可以减小生成的BSP树规模:
(l)针对每次分割，预先计算所有分割面分割后的规模，选择分割最少的平面作为分割面。
(2)使用随机方法，在三角面片序列中，随机选择一个作为分割面。
对于第一种方法，需要进行许多的预计算，因为对于每一个可能的分割面，都要计算分割后的面片总数，使得整个算法的效率大大下降。另外由于每次选取只考虑树的当前层，所以整个算法只能保证局部最优而不是整体最优。
使用随机方法，虽然不能保证每次分割都是最优的，但可以保证构造出来的BSP树的期望规模非常小。
2.再来看看随机算法构造BSP树。
引入免费分割的概念:进行分割面选取时，若该平面可以直接跨越某个子区域，则该子区域中的其他面将不会被分割，所以在以后的计算中不用计算这些面。

图 3.5 免费分割
图3.5中，三角面片e直接将三角面片f分割成两部分，若三角面片f所在的平面中的其它三角面片也按照e进行分割，则以后计算中可以不用再考虑这些三角面片。

因为算法algorithmBSPConstruct中初始分割面总是选取三角面片集合的第一个面，所以使得算法的效率直接取决于三角面片集合的输入顺序。为了避免引入预计算而使BSP树建立速度过慢，可以考虑生成三角面片序列的随机排列，然后再进行分割。与随机算法相结合，可以使生成的BSP树的期望规模较小。算法的描述如下:
BSP树 TalgonthmBSPRandom(场景图中的三角面片集合s)
{
生成三角面片集合的随机排列S’
for(i=1 to n)
{
if(Si’包含1个三角面或碎片)
{
直接生成树T，Si’存储在T中
return T
}
else(将si’所在平面Pi作为分割面)
{
T+=algorithmBSPRandom(位于H+空间的三角面片集合)
T=algorithmBSPaRandom(位于环空间的三角面片集合)
H=Si’
return T
}
if(Si’育色构成免费分割)
进行所有的免费分割
}
}
若三维场景中包含n个三角面片，则全部可能的排列数目是川。对任意一个三角面片Si，它被分割的碎块数目的期望是O(i)，因此算法algorithrmBSPRandom生成的碎片期望数目为O(i=0ni)=O(n2)。