隐式曲面形状交互调整的新方法
计算机学报2009 年 6 期一种隐式曲面交互调整的新方法1周元峰1 伯彭波3 张彩明1，21. 山东大学 计算机科学与技术学院，济南，2501012. 山东经济学院 计算机科学与技术学院，济南，2500143. 香港大学 计算机科学系，香港摘摘 要要：提出了一种对隐式曲面形状进行交互调整的新方法, 为隐式曲面的调整提供了两种交互工具, 分别是对曲面上点的位置调整和法向调整. 该方法以调整后的位置和法向为新曲面的插值条件建立目标函数, 极小化该目标函数求解曲面参数的变化量, 从而确定新的隐式曲面. 从优化角度对极小化问题进行研究, 分别采用牛顿法和 SQP（Sequential Quadratic Programming）方法求解该非线性优化问题. 在调整过程中用粒子的方法对隐式曲面进行绘制, 实现了对隐式曲面形状进行实时交互调整. 最后用实例说明了新方法的有效性.关关键词键词：隐式曲面；交互调整；优化; 粒子系统; 目标函数1 引 言随着计算机图形学、辅助几何设计、计算机建模技术的发展，隐式曲面得到了更为广泛的关注和应用。在曲面建模中，隐式曲面的优势在于表达形式简单，用户可方便地判定空间点与隐式曲面的相对位置，而且其光滑性非常高。隐式曲面能够容易的表示复杂拓扑的曲面，并且可以很容易的改变曲面拓扑结构。相对于参数曲面建模来说，隐式曲面的系数对于曲面形状的影响往往是不直观的，例如，对于代数曲面，给定代数曲面的系数之后很难预计它的形状。因此，隐式曲面模型的一个主要缺点是难以直观地控制和调整曲面的形状1。近年来对于隐式曲面建模和控制的研究有很多2-10。目前使用较多隐式曲面类型主要包括代数曲面4和 blobby 曲面5。后者提供了一种方便的隐式曲面的交互设计方法。用户可通过交互修改各个 blobby 元素来局部修改隐式曲面，进而生成复杂形状的光滑曲面。blobby 曲面是一张由一些 blobby 基本元素所定义的标量场的等值面。但由于 blobby 元素的单一性，由 blobby 系统构造一张曲面需要大量基本元素，且用户对此难以有效控制，这给交互设计带来了极大的困难。对于隐式曲面形状的交互调整一直是曲面建模绘制研究中一个比较难的问题。Witkin51本课题得到国家“九七三”重点基础研究发展规划项目基金(2006CB303102)和国家自然科学基金(60673003，60573180)资助.计算机学报2009 年 6 期提出了一种基于粒子化的方法对隐式曲面进行采样和控制。该方法约束一组粒子在曲面上，这些粒子自动对曲面进行采样。粒子之间的排斥力使粒子均匀地分布在曲面上。而且，该方法能够允许用户交互调整指定粒子的位置，从而改变曲面的形状。但是该方法所用的参数太多难以控制，且文章中仅实现了对于曲面上点的位置的调整。Turk10提出了一种利用变分曲面进行插值建模的造型方法，该方法简单有效，得到的曲面插值为线性插值，构造出来的曲面形状较好，易于调整，但是该方法仅适用于变分曲面造型，对于一般的隐式曲面并不适用。Hart6改进了文献5中的方法, 给出了一种自动确定参数的方法，能够对较为复杂的隐式曲面的形状进行调整。但这种调整方式也仅实现了对顶点位置的调整，交互调整方式过于单一。如何实时调整隐式曲面形状是隐式曲面应用中的难点问题。对于隐式曲面形状的调整问题实质上是如何基于约束条件确定新的隐式曲面表达式的系数。基于上述问题，本文提出了一种隐式曲面形状交互调整的新方法。该方法实现了对于隐式曲面上指定点进行位置调整和法向调整两种曲面形状调整方式。基于粒子系统对曲面进行实时绘制。根据用户希望的位置和法向建立目标函数和约束，利用优化方法极小化目标函数求解出调整后的隐式曲面系数。本文余下部分安排如下：第二节介绍曲率自适应的隐式曲面粒子采样方法；交互调整方法的基本思想将在第三节中给出；目标函数建立和优化方法求解在第四节中进行了详细讨论；实验结果与数据说明在第五节给出；结论和进一步的工作在第六节中讨论。2基于粒子的隐式曲面显示本文提出了交互调整曲面形状的方法，在显示的时候用 Witkin5的粒子表示方法（如图 1 所示） ，这里先简短介绍 Witkin 的粒子方法。Witkin 的隐式曲面建模方法是基于粒子采样系统来显示和控制一个隐式曲面。在隐式曲面上约束一个圆点使得：( , )0fx qip(, )0ifp q此处可以看作是浮动于隐式曲面上的一个粒ip子（particle） ，利用粒子之间的互斥力将粒子均匀的分布于曲面表面，简单的互斥能够使得静态曲面得到很好的粒子分布，但是需要一个较好的采样作为前提条件。Witkin 采样方法图 1 Blobby 曲面上的点位置和法向控制手柄计算机学报2009 年 6 期采用粒子动态分裂/死亡机制将粒子约束在曲面上，初始给定一个随机粒子和一个比较大的互斥半径，用迭代方法对粒子进行分裂或者死亡，若粒子的互斥半径大于设定的半径阈值或者粒子能量大于设定的能量阈值，则将该粒子一分为二，并减少粒子之间的互斥半径；反之，若粒子的互斥半径过小，则该粒子死亡。迭代重复上述步骤，直至所有粒子满足能量和互斥半径约束条件。该方法可以很好的达到收敛效果，这样隐式曲面的调整可以通过调整粒子来实现，达到了交互的目的。隐式曲面的形变根据隐式曲面系数的变化速度确定：jjjfqqQInteractive control; Optimization; Blobby surface; Particle systemBackgroundAs the developments of computer graphics and computer aided design, implicit surfaces have been increasingly used for modeling, visualizing and animation. In geometric modeling, comparing with parametric surfaces, implicit surface has three obvious advantages: one is implicit surface's simple expression form which can be described in the form of , another is it is easy to ( )0fxjudge the relative position to a special point, and the third is implicit surface has high smoothness. Implicit surfaces are useful for describing continuous and smoothly blend surfaces with complex topology, and can change the topology of surfaces easily. However, effect of coefficients of an implicit surface is not intuitive. So the main drawback of implicit surfaces is difficult to control and model implicit surfaces interactively. Based on above problems, a new interactive controlling method for implicit surfaces is presented. For general implicit surfaces, shape controlling is essential on how to determine the coefficients of the new implicit surfaces. Position and normal of a selected vertex on surface controlling are used as two interactive tools in new method. Based on the desired position and normal vector offered by user, constraint objective functions are established based on interpolating conditions. Freedom degrees are determined by minimizing objective functions via optimization. Particle system is used for rendering implicit surfaces. This method is computationally efficient and easy to implement. Experimental results show that our method can produce ideal mesh simplification results. This work was supported by the National Basic Research Program (973 Program) of China (No. 2006CB303102) and the National Nature Science Foundation of China (60673003, 60573180).Zhou Yuan-Feng, born in 1980, Ph.D. candidate. His research interests include computer graphics, 计算机学报2009 年 6 期geometric modeling and processing.Tel: (0531)88390178, E-mail:yfzhoumail.sdu.edu.cn.周元峰周元峰，男，1980年生，博士研究生，主要研究方向为计算机图形学，几何造型与处理.Bo Peng-Bo, born in 1978, Ph.D. candidate. His research interests include computer graphics, Geometric Modeling.伯彭波伯彭波，男，1978年生，博士研究生，主要研究方向为计算机图形学，几何造型.Zhang Cai-Ming, born in 1955, professor, Ph.D. supervisor. His research interests include computer graphics, computer aided geometric design, and medical image processing. E-mail:czhangsdu.edu.cn.张彩明张彩明，男，1955年生，博士，教授，博士生导师，主要研究领域为计算机图形学，计算机辅助几何设计和医学图像处理.
