爱华网·研究与探讨· 1997.7 计算机工程与应用
最优化方法及其在计算机图形学中的应用
浙江大学CAD&CG国家重点实验室 马小虎 潘志庚 石教英
摘 要
最优化方法是对极值问题进行数值分析的有效手段,它在计算机图形学中已获得广泛应用。本文概述了最优化方法并简要介绍了最优化方法在计算机图形学中已有的若干应用,阐述了作者把最优化方法用于
限时计算和限时图形绘制所做的研究工作。
关健词
1 引言
最优化方法是对极值问题进行数值分析的有效手段[1]。极值问题历史悠久而其内容不断地更新,它来源于科学和技术的各个方面,问题的深度和广度也随着各个不同阶段的科学技术水平而有所发展。
近2、30年来,由于科学技术的需要,以及计算机技术的飞速发展,为求解各种极值问题的最优化方法和理论提供了坚实的基础和有效手段。最优化的应用范围愈来愈广,几乎在设计、操作、工业过程、生产装置分析乃至生产计划之类的有关问题中,最后都归结为确定某个目标函数的最优值——极大或极小。随着计算机运算能力的增强,使得我们有可能在资源(计算资源、存储资源等)容许的条件下追求最优解,在计算机图形学中的许多问题(光照、曲面、动画设计;动画的运动合成;几何造型等)可以用最优化方法来求解[2]。
本文第二节对最优化方法作一简要介绍,第三节介绍了最优化方法在计算机图形学中已有的几个典型实例,第四节简单介绍作者把最优化方法用于限制计算和限时图形绘制方面所做的工作,最后是结论。
最优化方法 限时计算 网格优化 曲面设计
数,D为f(x)的定义域。也可以写成更一般的形式:
min f(x)
x∈D
…… (2-2)
ψ(x)≤0
满足: φ(x)=0其中,x=(x1,x2,…,xn)T,
T
φ(x)=(φ1(x),φ2(x),…,φp(x)),Tψ(x)=(ψ1(x),ψ2(x),…,ψq(x))。
在(2-1)中,自变量x可以取遍定义域D内的值而不受限制,故称为无约束极值问题。而在(2-2)中,x∈D必须受到一定的约束,即:
φi(x)=0, i=1,2,…,p=1,2,…,qψj(x)≤0, j
…… (2-2a)…… (2-2b)
故称(2-2)为约束极值问题.(2-2a)、(2-2b)都称为约束条件,其中(2-2a)是等式约束,(2-2b)是不等式约束。
2.1.2 分类 上述问题又统称为数学规划,按目标函数以及约束条件中约束函数的类型和自变量取值状态,还可以区分为不同形式的数学规划。
当f(x)、φi(x)、ψj(x)均为线性函数时,称为线性规划,当其中任一个为非线性函数时,称为非线性规划;当f(x)为二次函数,φi(x)、ψj(x)均为线性函数时,称为二次规划;当x的各个分量全部或部分只取离散值(如取整数值)称为整数规划;在整数规划中,若x的各个分量只取0、1两个值时,称为0-1规划。还有几何规划,动态规划等等。
求解问题(2-1)或(2-2)的目的,是要确定一个
*
向量x,
2 最优化方法概述
2.1 最优化问题的提法及分类
2.1.1 描述 最优化问题通常可以表示为目标函数的极值问题,其形式化表示为:
min f(x)
X∈D
……(2-1)
其中,f(x):D Rn→R为实值函数,称为目标函
本研究课题得到国家自然科学基金资助
计算机工程与应用 1997.7 ·研究与探讨·
满足f(x*)=min f(x)。对于(2-2),还要满足:φ
x∈D
*
(x*)=0,ψ(x)=0我们称x*为最优点。
3.1.2 求解方法 网格优化的目的是获得一个能够较好地拟合给定的数据点集合X,并且只有少量顶点的网格。为此只要求得一个简单复合形K和一组顶点V,即求出一个网格M=(K,V)使得如下构造的能量函数[5]:
E(K,V)=Edist(K,V)+Erep(K)+Espring(K,V)
…(3-1)
达到极小。
在(3-1)中,V={v1,v2,…vm},vi∈R3,i=1,2,…,n。K是表示顶点、边、面之间连接性的简单复合形,它决定了网格的拓扑类型。于是网格M可形式化表示为二元组(K,V)。(3-1)式右边的每一项分别为:
·Edist(K,V)=
对于极大问题maxF(x),如果令f(x)=-F(x),则转化为极小问题。因此,最优化问题表示为(2-1)或(2-2)的形式不失其普遍意义。
2.2 最优化问题的计算方法
实际问题中多数极值问题都是以约束问题的形式出现。对于约束最优化问题,尽管早已有了La-grange函数法,但现实生活中大量出现的问题远远地超出了古典极值方法研究的范围。继Kuhn-Tucker(1951)的工作之后,约束最优化问题引起了学者们的广泛重视,得到了极大的发展。约束最优化问题中常用的算法包括二次规划法、直接法、系列无约束最优化方法、容许方向法、简约梯度法、约束变尺度法
[3]
∑d(x,ψ(|K|)),其表示点集
2
i=1
i
v
n
虽然实际问题中多数极值问题都是以约束问题的形式出现的,但是研究无约束最优化问题的解法仍有现实意义,这是因为:
(1)实际中存在着大量的平方和极小问题,求这类问题不带约束的更为普遍。
(2)解约束问题又常常转化为解一系列无约束问题。
正因为如此,近20年来,人们极为重视无约束最优化问题算法的研究,作出了很多有意义的成果[4]。无约束最优化问题的算法包括下降算法、梯度法或最速下降法、Newton方法及其改进、共轭方向法[1]
X中每一点到网格M的距离平方和。
·Erep(K)=Crep*·Espring(K,V)=
m,Crep是用户设定的常数。
{j,k}∈K
∑κ||v-j
2
|,κ为一个弹vk|
性常量,随着求解过程逐渐收敛其解,Espring项的值逐渐减少。Crep与κ的值对网格优化结果的影响如图1所示
。
3 最优化方法在计算机图形学中的若干应用3.1 网格优化
3.1.1 问题的描述 网格表示法是一种重要的数据表示法,在三维图形、动画、科学计算可视化和虚拟环境中有广泛的应用。然而,在这种方法中,当场景复杂时,描述场景的面片数量非常大,这时就会影响图形绘制的速度。在实际应用中,有些情况下,用户希望先观察一下场景的概貌和大致形状,增加交互性,这时就需要对网格描述进行简化,即网格优化问题。该问题可描述如下:
已知空间中一组散乱点以及由它产生的初始三角形面片网格M0,要求产生一个新的网格M,满足三个条件:(1)M与M0具有相同的拓扑类型;(2)M与原数据集有更好的逼近程度;(3)M应由尽可能少的顶点与三角形面片组成。
网格优化例子
3.2 光滑曲面设计的函数最优化
3.2.1 设计目标 曲面设计的方法已有多种,而采
·研究与探讨· 1997.7 计算机工程与应用
用函数最优化方法可以提供一种容易使用的方法来构造具有任何拓扑类型的复杂的光滑曲面。所要设计曲面的形状通过被插值的几何约束给出,几何约束包括点的位置、曲面的法向量和曲面的曲率。从设计者的观点来看,这样的形状说明是非常自然的。3.2.2 求解方法 使用非线性最优化方法使得基于曲率变分的修正函数达到极小。对于曲面,修正函数为法向曲率在主方向上变分的平方和的积分,即
效果。ChrisSchoeneman[7]等人提出了一种新的解决方法,利用约束最小二乘方法来自动确定光源的强度和颜色。
(2)动画的运动合成 基于物理模型的计算机动画中常常用到局部和全局最优化方法。局部最优化方法,例如求时空约束问题[8]的梯度下降法,可得到该类问题比较合理的解。然而,由于搜索空间是多模式的,能够进行全局搜索的全局最优化新方法开始在运动合成中发挥愈来愈重要的作用,全局最优化方法可以产生新的、预想不到的结果。其中选择适当的表示通常是使得全局搜索能顺利完成的关键。例如,An-drewWitkin[8]等人提出了进行角色动画设计的新方法。动画师只需描述角色做什么、如何执行运动、角色的物理结构和角色完成运动可用的物理资源。以上描述中所包含的需求与牛顿运动定律相结合形成一个约束最优化问题。该问题的解即为满足给定约束并使目标函数达到最优的物理上合法的动画设计。(3)布局类应用 CAD的一种典型应用是空间布局,如建筑CAD中的空间布局问题、电子CAD中的自动布线和地下管网布局设计等,这类问题都可归结为约束最优化问题,从而用最优化方法来求解。最优化除了用在上面提及的各种应用类型外,还可用于多点碰撞检测[9]、形状分析和几何特性计算等方面。
dkn2dkn2
+dA…… (3-2)de1de2
通过曲率的变分最小化而导出的曲线和曲面通
常分别称为最小变分曲线(MVC)和最小变分曲面(MVS)[6]。
3.2.3 求解步骤 通过插值一组几何约束来创建曲面可看成是一个散乱点插值问题,而插值问题可分3个步骤:
(1)连接性定义、(2)曲线网格计算、(3)曲面片拼接。
与所要设计曲面的拓扑类型相一致,几何约束首先连接成直线边的网络。在网络的每条边放置一条曲线,并计算由MVC组成的最优网络,满足初始说明的几何约束并在两条曲线拼接处满足二阶几何连续性G2,最后通过插值具有切线连续的MVC网络计算出MVS。
3.2.4 该方法的优缺点
优点 ①所产生的曲面质量高(G连续),并且具有可判定的直观行为。②可用简单的形状比如:园柱体、球体、锥体等拼接成复杂的几何体。
缺点 计算量大
值得指出的是,随着计算机运算能力的进一步增强以及更加有效的最优化算法的提出,这里提到的曲面设计方法将提供一类新的实用的可交互的几何造型工具。
2
4 最优化方法与限时计算
在未来几年内,随着计算机处理能力和网络功能的日益增强,将会开发出一系列新的分布式应用,这些应用的一个主要特征是有更强大有效的人机界面。新一代的人机界面将利用限时计算,把可视和可听数据显现在用户面前,对人体动作及姿势进行限时感知[10]。
在限时计算中,计算必须能在规定的时间内完成,否则认为计算结果是错误的(传统的计算正确性与完成计算的时间无关)。显然限时计算与传统的计算概念不一样,在这里把时间作为第一要素,这就要求在向操作系统提交计算任务时,还必须指定完成这种计算所允许的时间,操作系统就必须进行有效的资源调度,从而保证满足应用的要求。
限时计算用在图形绘制中也称限时图形绘制,它的基本思想是根据现有的资源在可能的情况下,利用近似计算,以质量换取时间,保证计算在规定的时间内完成,从而增加系统的交互性和实时性,限时计算
3.3 其它方面的应用
(1)光照设计 在图像合成的光照设计中,要解决的问题是给定一组具有固定位置的光源,如何确定光的强度和颜色,使其与设计者所要绘制的目标图像最匹配,这个问题并不能由全局光照算法来解决。全局光照算法能产生真实感的图像,但是当把它用于光照设计时,则非常困难。原因在于设计者必须构造几何模型、设置光源、赋颜色和光强,最后才得到设计结果。这一过程必须多次重复,而且往往得不到用户所需的
计算机工程与应用 1997.7 ·研究与探讨·
的应用领域包括多媒体系统、虚拟现实环境和交互式科学计算可视化系统。例如在walk-through类的虚拟现实应用中,计算必须在指定时间内完成,否则头盔显示器中显示的图像将会与实际不符,从而导致出错。
限时图形绘制可采用如下方法实现:(1)采用不同细节层次的场景模型;(2)采用不同计算复杂度的图形绘制算法;(3)采用并行处理技术。
限时计算或限时图形绘制问题的求解可使用本文前面介绍的最优化方法来求解,下面就其中的多细节层次的自动选取和自动建立这两个问题作简要介绍。
次构造。(2)基于取样数据的表面重构和细节层次构造。
上述这两类细节层次构造过程中,都要用到最优化方法,并且已在3.1中有较详细的介绍。
5 结论
随着计算机运算能力的增强,最优化方法在计算机图形学中的应用已成为一种新的趋势。而限时计算又是计算机图形新技术——虚拟现实中的一种关键性技术[12],把最优化方法用于限时计算是我们正在进行的有益尝试。目前,已得到初步结果,相信不久会取得更令人满意的结果。
4.1 多细节层次的自动选取
4.1.1 问题的提出
假定每个可见的物体能以多个细节层次、采用不同的图形绘制算法进行绘制。那么在某个细节层次和某种绘制算法下,绘制一组物体需要一定的计算时间才能产生其图像,一个自然产生的问题是如何选取细节层次和绘制算法在限定的计算时间内产生所有可见物体的最佳图像结果。
4.1.2 问题的最优化求解方法 为了便于描述,我们引入物体三元组(O,L,R)表示,其中:O是物体的一个实例,L是被绘制的细节层次,R是采用的绘制算法。另外,引入两个物体三元组的启发式函数:Cost(O,L,R)和Benefit(O,L,R)。其中:Cost函数表示绘制一个物体三元组所需的时间,Benefit函数表示一个被绘制物体三元组对整个目标图像视觉效果的贡献量。那么,多细节层次自动选取问题可表示为如下的约束最优化问题[11]:
参考文献
1.张光澄等编,“最优化计算方法”,成都科技大学出版社,
1989。
2.JoeMarkset.al,"Optimization——AnEmergeringToolinComputerGraphics",ComputerGraphics(siggraph'94),Aug.,1994,pp483—484.
3.赵风治,尉继英等著,“约束最化化方法”,科学出版社,1991。
4.席少霖,“无约束最优化方法简介”,计算机应用与应用数学,11(1976)。
5.H.Hoppe,T.DeRose,T.Duchamp,J.McDonald,andW.Stuetzle,"MeshOptimization",ComputerGraphics,27(2):pp19—25,Aug,1993.
6.H.P.MoretonandC.H.Sequin,"FunctionalOptimizationforFairSurfaceDesign",ComputerGraphics,26(2):pp167—176,July,1992.
7.C.Schoeneman,J.Dorsey,B.Smiths,J,Arvo,andD.Greenberg,"PaintingwithLight",ComputerGraphics(siggraph'93),Aug.,1993,pp143—146.
8.AndrewWitkin,"SpacetimeConstraints",ComputerGraphics,22(4),Aug.,88,pp159—168.
9.J.M.Snyder,A.R.Woodbury,K.Fleischer,B.currin,andA.H.Barr,"IntervalMethodsforMulti-PointCollisionsbetweenTime-DependentCurvedSurfaces",ComputerGraphics,27(2),Aug.,1993,pp321—334.
10.潘志庚,“分布式图形处理的理论与应用研究”,浙江大
学博士学位论文,1993.6
11.ThomasA.FunkhouserandCarloH.Sequin,"Adaptive
DisplayAlgorithmforInteractiveFrameRatesDuringVisualizationofComplexVirtualEnvironments",Com-puterGraphics(siggraph'93),Aug.,1993,pp247—254.12.PanZhigenget.al,"Time-CriticalComputinginVirtu-alEnvironment",ProceedingsCAD/Graphics'95,1995.10.5.
∑Benefit(O,L,R)
满足:∑Cost(O,L,R)≤t
Max
SS
其中,s是每一帧中被绘制的物体三元组的集合,t为目标帧允许绘制的时间。
4.2 复杂场景多细节层次的自动建立
要在限定的计算时间内绘制出复杂的场景,必须采用多个细节层次来描述同一场景。很自然,如何自动建立场景的多细节层次成了限时计算和限时图形绘制的又一个关键问题。目前,我们正在就以下两种方法进行研究:(1)基于三角面片网格优化的细节层
百度搜索“爱华网”,专业资料,生活学习,尽在爱华网
