真实感图形生成

真实感图形生成第一页，共七十五页，2022年，8月28日真实感图形生成的步骤场景造型取景变换、透视投影视域裁剪、消除隐藏面光亮度计算

第二页，共七十五页，2022年，8月28日光亮度计算1．依据：光照明模型局部光照明模型：朗伯模型、Phong模型整体光照明模型：Whitted模型，光能辐射度方程（隐式）追求目标：光照效果的真实感

第三页，共七十五页，2022年，8月28日扫描线方法光线跟踪方法光能辐射度方法追求目标：画面生成的实时性

2．计算方法：绘制算法第四页，共七十五页，2022年，8月28日本讲座内容一、光照明模型的基本原理二、快速光线跟踪算法1.平行2n面包围盒算法2.空间分割算法

三、光能辐射度方法1.形状因子计算2.逐步求精算法

第五页，共七十五页，2022年，8月28日一、光照明模型的基本原理1.概述视觉的形成物体的颜色漫反射和镜面反射第六页，共七十五页，2022年，8月28日2．Phong光照明模型为计算方便，镜面高光分量可改写成:漫反射分量泛光镜面高光分量LiNRiViθiθiPHi第七页，共七十五页，2022年，8月28日3．光度学的基本概念光通量：单位时间内通过某一面积的光能量发光强度：沿给定方向单位立体角发出的光通量光亮度：面光ds沿给定方向的光亮度为在该方向上单位投影面积的发光强度照度:单位面积表面所接受的光通量第八页，共七十五页，2022年，8月28日朱一宁模型

目标：计算面元dSj朝观察者方向v的光亮度,先计算dSj所接受来自周围环境的入射光能jjiNiSidjNjdiSjdSjdSir第九页，共七十五页，2022年，8月28日由dSi发出并到达dSj的光通量为：面元dSj所接受的照度:第十页，共七十五页，2022年，8月28日到达dSj的光能除一部分被表面吸收外，大部分通过反射和折射继续向空间辐射。令K为光通量辐射比，D为未被吸收的光能向空间任一方向立体角辐射的概率密度，则dSj朝观察者方向内辐射的光能为:第十一页，共七十五页，2022年，8月28日dSj朝观察者方向的光亮度为:dVNθdSi第十二页，共七十五页，2022年，8月28日设对dSj有光能贡献的发光面元集合为S，则表面朝V方向的光亮度为:第十三页，共七十五页，2022年，8月28日第十四页，共七十五页，2022年，8月28日当D取不同的分布函数时，可得朗伯模型，Phong模型，Cook-Torrance模型……

当S取发光面元集合时得各种局部光照明模型；当S包括所有周围环境表面时，可得整体光照明模型当S取不同的几何形状时，可得线光源光照模型和面光源光照模型第十五页，共七十五页，2022年，8月28日第十六页，共七十五页，2022年，8月28日二、快速光线跟踪1.光线跟踪的基本原理问题：1）如何寻找B，D：光线跟踪2）如何计算IB，ID：递归过程3）受遮挡时的计算：阴影测试

眼睛

第十七页，共七十五页，2022年，8月28日光线跟踪终止条件光线射出画面，不再与场景中的景物相交被跟踪的结点对屏幕象素显示光亮度的贡献小于一定阈值达到光线跟踪的最大深度第十八页，共七十五页，2022年，8月28日算法描述1．由视点向屏幕上所有象素中心发射光线；2．每一根光线与场景中所有景物求交，找到最近的交点；3．计算该点处由光源直接照射产生的光亮度Il；4．若该点处表面为镜面或透射面，则作递归光线跟踪，计算周围环境通过该点向观察者方向投射的整体镜面反射光亮度Ir和透射光亮度It；5．显示每一象素处的光亮度第十九页，共七十五页，2022年，8月28日算法分析：1．求交计算量占整个光线跟踪计算量90%以上减少求交计算量的方法包围盒方法空间剖分方法2．点采样容易导致画面走样 方法：自适应超级采样基于层次包围盒的快速光线跟踪算法第二十页，共七十五页，2022年，8月28日2.基于层次包围盒的快速光线跟踪算法包围盒：以简单的测试代替光线对包围盒内所含景物的复杂求交运算目标：快速剔除不交的物体对包围盒形状的要求：包裹要紧密求交测试要简便第二十一页，共七十五页，2022年，8月28日平行2n面包围盒优点：多面体可以较紧密地逼近一个物体平面求交计算较为简单表示方法：平面方程Ax+By+Cz-d=0其中d表达了平面与原点之间的距离为节省存贮量，平面法向A，B，C隐含表示同一景物的三种平行包围体(a)(b)(c)第二十二页，共七十五页，2022年，8月28日景物的平行2n面包围盒的确定 —确定各平行面的d值1）多面体的平行2n面包围盒设几何造型变换矩阵为M（3×3），平移矢量为T将变换后顶点矢量投影到平面法矢上对于一组平行平面第二十三页，共七十五页，2022年，8月28日2）隐函数曲面的平行2n面包围盒 隐函数曲面曲面上任一点投影到包围盒平面法矢上现欲求在满足约束条件下的条件极值。运用拉格朗日乘数法可求出第二十四页，共七十五页，2022年，8月28日平移矢量T对的影响

——附加一个沿T方向的平移量组合物体的平行2n面包围盒第二十五页，共七十五页，2022年，8月28日光线与包围盒边界面的求交给定一光线代入平面方程由于Ni预先设定，对于给定光线，a，b为常数令则（一次减法，一次乘法）第二十六页，共七十五页，2022年，8月28日光线与平行2n面包围盒的求交由于平行2n包围盒为凸体，只需求光线位于各组平行面之间区段的交若则光线位于之间的区段为光线与包围盒的交第二十七页，共七十五页，2022年，8月28日注：算法并行地计算当前区段与前面区段公共段的交。若无交，则不必再继续计算下去。当为负时，光线投射方向与平面法向相反，交换的位置第二十八页，共七十五页，2022年，8月28日场景的层次包围盒结构求交测试计算量由降至同一层次的结点按光线与其包围盒入口点的t值（）排序存入一链表中

总是取光线最先进入的包围盒内所含景物作进一步测试由于链表中相邻结点的包围盒可能重迭，只有当求得的光线与包围盒内景物交点的t值小于光线与下一相邻结点包围盒入口点的t值时，才能停止进一步的求交测试。

光线第二十九页，共七十五页，2022年，8月28日基于空间剖分的快速光线跟踪算法将空间划分为网格，光线只与它所穿过的空间网格中所含景物进行求交。利用空间网格的邻接性质，引导光线从一个网格进入它将穿过的下一网格。一旦发现光线与景物的第一个交点，即结束求交。第三十页，共七十五页，2022年，8月28日现有的空间分割光线跟踪算法3DDDA算法将空间划分为均匀的立方体网格，利用光线的线性几何，采用增量算法，求得光线与当前网格的出口点，并直接查取光线进入的下一网格。

问题：1.不适合于景物分布稀疏的场景2.占用大量存贮空间第三十一页，共七十五页，2022年，8月28日Glassner算法将空间按景物实际分布划分成八叉树结构，每一网格仅包含一定数量的景物表面，空网格不再细分。求出光线与当前空间网格出口点的t值，再向前移动Δt，生成光线位于下一网格内的一点（x，y，z）。利用Hash查找技术，找到包含这一点的下一八叉树网格。

问题：1.求下一网格定位点涉及9次乘法2.存贮全部八叉树结点，包括空网格结点第三十二页，共七十五页，2022年，8月28日空间索引算法采用线性八叉树结构存贮包含景物面片的空间八叉树结点，占用存贮小。采用启发式方法求取光线与当前网格出口点，大大减少了计算量。利用线性八叉树结点编码性质，直接由出口点查找下一空间网格。第三十三页，共七十五页，2022年，8月28日问题：如何快速求取光线与当前空间网格的出口点？思路：根据光线的前进方向，优先选取最有可能与光线相交的网格边界面与光线进行求交测试。为此引入光线前进主方向，次方向，第三方向概念，其相应坐标分量分别以L、S、T标识，显然光线从垂直于主方向的空间网格边界面出口的可能性最大，应优先测试第三十四页，共七十五页，2022年，8月28日若光线沿主方向边界面射出，出口点应位于边界面正方形内即设出口点为IP则第三十五页，共七十五页，2022年，8月28日若则光线沿次方向边界面射出否则光线可能沿次方向或第三方向边界面射出取S-T坐标系算出：第三十六页，共七十五页，2022年，8月28日否则光线沿第三方向边界面射出第三十七页，共七十五页，2022年，8月28日问题：如何高效查找光线将要进入的下一空间网格？思路：利用线性八叉树结点的编码性质，确定下一相邻网格第三十八页，共七十五页，2022年，8月28日沿x轴正向，相邻兄弟结点编码增加1沿y轴正向，相邻兄弟结点编码增加2沿z轴正向，相邻兄弟结点编码增加4线性八叉树结点的编码方式将一空间沿x，y，z中分面一分为八01134576xyz第三十九页，共七十五页，2022年，8月28日设立方体空间为，该空间中任一Voxel结点编码为为八进制数，纪录了对空间第i次分割时，含该Voxel的子结点在其父结点中的方位。表示一个只分割到第i层的空间结点，子空间边长为。第四十页，共七十五页，2022年，8月28日八叉树结点的原点坐标与其结点编码的关系设某一八叉树结点编码为且则其局部原点坐标为：反过来，若已知某一八叉树结点的局部原点坐标，则可推导出其线性八叉树结点（Voxel）编码第四十一页，共七十五页，2022年，8月28日线性八叉树结点按编码顺序以线性链表方式存贮。结点的父子、兄弟邻接关系反映在编码上，同胞兄弟的结点具有相同的前缀。第四十二页，共七十五页，2022年，8月28日由出口点查找下一空间网格的步骤1.首先由出口点确定下一空间网格的局部坐标原点（先假定Voxel结点）对Ip[L],Ip[S],Ip[T]分别取整得O[L,S,T]若step[L]<0且光线沿L方向边界面入口,O[L]=O[L]-1若step[S]<0且光线沿S方向边界面入口,O[S]=O[S]-1若step[T]<0且光线沿T方向边界面入口,O[T]=O[T]-1第四十三页，共七十五页，2022年，8月28日对原点坐标进行分解、拼合，求出其最小的Voxel结点编码则，其中第四十四页，共七十五页，2022年，8月28日搜索场景空间线性八叉树，找出包含此Voxel的八叉树结点全部数码相同，该结点为一Voxel结点求光线与Voxel内所含景物的交点

部分数码相同，下一未匹配数码为F此结点为Voxel的祖先，包含该Voxel，且为终结点，求光线与该结点内所含景物的交第四十五页，共七十五页，2022年，8月28日部分数码相同，但下一未匹配数不是F设匹配部分编码为，则结点为包含该Voxel的最大空结点，求光线对该空结点网格的出口点。如何构造场景的空间线性八叉树（略）第四十六页，共七十五页，2022年，8月28日第四十七页，共七十五页，2022年，8月28日三、光能辐射度方法1．漫射场景的光能辐射度方程假定场景为一封闭的理想漫反射环境对于场景中任一面片j,Bj=Ej+ρjHj其中：为面片j向四周辐射的总的辐射度为面片j向外均匀发射的光能为面片j的漫反射系数为面片j从周围环境接受的总的光能

第四十八页，共七十五页，2022年，8月28日现在考虑如何计算:是周围环境其它面片辐射度()的函数，面片i向四周辐射的总的光能为BiAi,其中一部分到达面片j，记为BiAiFij，到达面片j单位面积上的光能为BiAiFij/Aj，故第四十九页，共七十五页，2022年，8月28日Fij的计算

Fij称为面片i对面片j的形状因子，

现在考虑面元dAi对面元dAj的形状因子，面元dAi向四周辐射的总的光能BidAi在无遮挡的情况下，面元dAi向面元dAj的辐射的光能为第五十页，共七十五页，2022年，8月28日由定义

对Aj积分得对Ai取平均，即第五十一页，共七十五页，2022年，8月28日推论:1．

即故（标准辐射度方程）2．

3．标准辐射度方程两端同除以，得场景各面片的光亮度方程

第五十二页，共七十五页，2022年，8月28日计算形状因子的半立方体方法形状因子计算公式的几何解释：dAj对单位半球面作中心投影，其投影区域为

该区域垂直投影到半球的底平面上，其投影面积为与底平面圆面积之比为，即。NiidSiSjSj取Ai的中心点为球心，在Ai上方建立一单位半球面。第五十三页，共七十五页，2022年，8月28日引申：对任何在半球面上占据相同投影区域的面片Ak，面片Ai对它们具有相同的形状因子，即

思路：寻找面片Ak，Ak的表面形状，朝向较为规范，计算比较容易，从而将Fij的计算转换为Fik的计算。

第五十四页，共七十五页，2022年，8月28日最规范的表面是围绕Ai，位于Ai上方的半立方体，立方体顶平面与面片Ai的法向垂直。因此，只要将面片Aj投影到半立方体表面上，Ai对其投影面积的形状因子即为Fij。将半立方体各表面离散为均匀网格，假定每一网格上各点的形状因子不变。面片Ai对每一网格的形状因子称为半立方体表面的微形状因子。面片Ai对Aj的形状因子归结为两个问题。第一，确定Aj在半立方体表面上所占网格；第二，计算每一网格的微形状因子。第五十五页，共七十五页，2022年，8月28日确定Aj在半立方体表面上的投影

取景变换和背面标志，将Aj变换到以Ai为中心的半立方体局部坐标系中。dSiQSjq对Aj作区域裁剪，以确定它投影到半立方体哪些表面上。 裁剪平面：z=x,z=-x,z=y,z=-y,x=y,x=-y。z-buffer消隐z-buffer中存储各网格的可见面号，而不是其深度值，故又称item-buffer。被遮挡的表面形状因子为零。第五十六页，共七十五页，2022年，8月28日xtopxsidezxyAsidezsiderijdSiyside=1ytopztop=1rijAtopqq计算每一网格的形状因子对于位于半立方体顶面网格第五十七页，共七十五页，2022年，8月28日对于位于半立方体侧面网格（以左侧面为例）由于半立方体表面各网格与其中心的相对方位是固定的，故可预先将半立方体表面各网格的微形状因子计算好，存储在一查找表中备用。

xtopxsidezxyAsidezsiderijdSiyside=1ytopztop=1rijAtopqq第五十八页，共七十五页，2022年，8月28日辐射度方程的求解（1）由形状因子组成的系数矩阵主对角占优，可迭代求解。可取各面片之Ei作为迭代初值，一般迭代6－8次即可收敛。（2）对红、绿、蓝三原色分别求解辐射度方程（Ej,ρj与光谱分布有关）。（3）采用插值与平均方法将各面片中心的辐射度转换为各面片顶点处的辐射度。注意：景物面片的辐射度解与视点无关第五十九页，共七十五页，2022年，8月28日画面绘制选定视点和视线方向，对场景中的景物作取景变换。采用光线投射或扫描线算法，确定屏幕上每一象素中的可见面。采用双线性插值方法，确定象素中心处表面采样点的辐射度。画面显示。第六十页，共七十五页，2022年，8月28日计算量分析例：某画面包含1740个面片图1图2图3形状因子计算180min00解辐射度方程10min10min0画面绘制16min16min16min总计206min26min16min第六十一页，共七十五页，2022年，8月28日3.光能辐射度逐步求精算法图形学发展的两根主线:追求画面生成的真实感和实时性.在追求真实感方面由线画图形->消隐图形->连续色调光栅图形由多边形图形->Gouraudshading->Phongshading由朗伯模型->Phong模型->整体光照模型由扫描线算法->光线跟踪算法->光能辐射度方法第六十二页，共七十五页，2022年，8月28日在追求画面实时生成方面硬件支持绘制处理。景物细节简化技术。基于图象的绘制。逐步求精的画面生成算法。第六十三页，共七十五页，2022年，8月28日逐步求精画面的绘制算法的特点一开始就生成画面,包含有用的视觉信息。画面由粗糙逐步变得精细,真实感不断增强。每一步的计算都利用了前面步骤的计算结果。第六十四页，共七十五页，2022年，8月28日基于光能辐射度的画面计算和生成过程场景辐射度方程:Bi=Ei+ρi∑BjFij1)计算形状因子,确定系数矩阵,计算量存储量均为O(N2)2)迭代法求解方程组,获得环境中的光能分布3)取景变换,确定可见面,计算并显示每一象素上可见面的光亮度值问题:第一步计算量占整个方法的90%,任何有用的结果和画面显示都必须在系数矩阵确定后才能生成第六十五页，共七十五页，2022年，8月28日光能辐射度方程的迭代形式令则第六十六页，共七十五页，2022年，8月28日分析:上述方程表明,每一面片的辐射度增量应为其他面片向它入射的光能的线性组合,这一过程称之为Gathering。每一步迭代的代价 在接受面片i上建立一个半立方体，计算n个形状因子（所有Fij）。更新一个面片(i)的辐射度。第六十七页，共七十五页，2022年，8月28日改进 在方程右侧的和式中，选择对刷新贡献最大的一项，取面片j作为辐射源，则(Dueto)=每一步迭代的效果在辐射源面片j上建立一个半立方体，计算n个形状因子（所有Fji）,场景中大部分面片的辐射度均有所更新。这一过程称之为Shooting。第六十八页，共七十五页，2022年