冯万泉给定边界的极小曲面生成算法研究

冯万泉数学科学学院概率统计专业PB12001107李新2016/5/20中国科学技术大学本科毕业论文自2012年入学以来，“中国科学技术大学”几个字就深深的烙印在我的心中。在完成论文临近毕业之际，心中感慨万千，所以在此必须要对本科阶段帮助过我的老师和同学表示感谢。首先要感谢导师李新老师对我的毕业论文的指导，让我得以顺利的完成毕业论文的工作。感谢刘利刚老师，得以让我施展对计算几何的兴趣，感谢其对我编程能力的提高还有对我视野的开阔，使我有了更强的探究欲望以及动手能力，得以在计算几何的路上跨越障碍迈出第一步。感谢我的所有基础课老师，尤其是史济怀老师，宋光天老师，还有任广斌老师。史济怀老师的数学分析课是一门让人打心里喜欢数学的课，也是大学开始后的第一大基础课。宋光天老师的线性代数课，条清缕析，幽默诙谐，让人无法不专心听讲，让人无法不喜欢。感谢任广斌老师字正腔圆声音洪亮的课堂，还有在我心中最漂亮的板书，让我喜欢上实分析这门课，虽然没有学习基础数学，但是从中受到的益处和感受到的乐趣是无穷的。还有感谢概统的老师们，给与我的专业知识。还有班主任夏晶老师，助理班主任刘畅师兄、曾凡怡学姐对我们的学习生活各方面的帮助。感谢科大四年来对我的教育和熏陶。成为一名中国科学技术大学的学生并一生拥有科大的气质，是我的万幸。最后要感谢本文引用到的论文作者，还有刘利刚老师提供的MINIMESHFRAME程序模板，让我们得以站在巨人的肩膀上看世界。感谢家人的支持，感谢朋友的陪伴，我的一切都是为了你们。感谢你们。遗憾的是，在文章中没能充分展示创新的内容。但是一篇深入投入的论文足以为本科阶段画上一个圆满句号。愿本科的同学今后各自努力，不断收获。愿今后的自己能永远保持单纯与热情，永远不放弃自己，永远走在进步的路上。由于本人水平有限，恳请各位师长们多多批评指正，以求进步完善冯万泉2016年5月中国科学技术大学本科毕业论文1目录1摘要2ABSTRACT3第一章绪论411极小曲面的背景应用412三角网格数据的简介5第二章预备知识721曲面的若干基本概念7211平均曲率及有关的重要公式7212极小曲面722极小曲面的离散表示8第三章算法详述1031局部法1032全局法11第四章实现与结果分析1341局部法14411结果呈现14412结果分析1542全局法16421结果呈现16422结果分析1743综合分析17第五章总结与展望19参考文献20中国科学技术大学本科毕业论文2本文的主要目的是研究在一条给定边界下的极小曲面的生成方法。极小曲面在数学上是指平均曲率处处为零的曲面。在生活中极小曲面也是非常常见，而且是具美感与用途与一体。科学家对极小曲面的兴趣与研究始于肥皂泡，而推广其用途到包括建筑领域在内的其他各个领域。而我们对于极小曲面使用的一个不可避免的问题就是需要有能力去建立任意给定边界下的极小曲面。而现在我们的给定边界以及待求曲面所采用的形式均为三角网格数据。原始数据为三角网格形式的带有一条边界曲面模型，我们将通过局部法和全局法两种方法来实现内部点的位置重建，并在保持固定边界的前提之下使之化为一个极小曲面。局部法采取迭代的思想。通过对极小曲面的性质的分析，我们可以得到离散情况下极小曲面的判别式即每个点“临点重心”的位置。然后计算出每个点“应有”的位置，之后所有点向“应有”位置移动一定比例，这就完成一次变换。同样的步骤迭代一定的次数，我们的曲面就可以不断地接近一个几乎标准的极小曲面。全局法采取解方程的思想。同样地，我们利用离散极小曲面的判别式，把每个非边界点的位置当做未知数，从而建立方程，利用计算出的结果重新建立非边界点的位置。根据这两种方法，我们会举出一些例子，来实践两种方法，并观察其结果。之后我们会比较两种方法的优劣，并对其结果做出总结与展望。极小曲面，三角网格数据，局部法，全局法中国科学技术大学本科毕业论文3THEMAINPURPOSEOFTHISPAPERISTOSTUDYTHEMETHODSOFGENERATINGMINIMALSURFACEWITHAGIVENBOUNDARYTHEMINIMALSURFACEISACURVEDSURFACEWITHZEROMEANCURVATUREEVERYWHEREMINIMALSURFACEISVERYCOMMONINOURDAILYLIFE,ANDITISTHECOMBINATIONOFTHEBEAUTIFULAPPEARANCEANDTHEWIDEUSESCIENTISTSINTERESTANDRESEARCHONMINIMALSURFACESBEGINSWITHSOAPBUBBLESTHENTHEYPROMOTEDITSUSETOOTHERAREASINCLUDINGTHECONSTRUCTIONFIELDIFWEWANTTOUSETHEMINIMALSURFACE,WECANNOTAVOIDTHEQUESTIONTHATHOWWECANGENERATEAMINIMALSURFACEWITHAGIVENBOUNDARYTHEDATATAKESTHEFORMOFTRIANGULARMESHESTHEGIVENDATAISASURFACEWITHABOUNDARYWEWILLTAKETWOMETHODSTORECONSTRUCTTHEINTERNALPOINTSANDMAKEITAMINIMALSURFACEWITHTHEBOUNDARYPOINTSFIXEDTHELOCALMETHODTAKESTHEIDEAOFITERATIONTHROUGHTHEANALYSISOFTHEPROPERTIESOFTHEMINIMALSURFACE,WECANOBTAINTHEDISCRIMINANTOFTHEMINIMALSURFACEINTHEDISCRETECASE,WHICHCANALSOBECONSIDEREDASTHEFOCUSOFNEIGHBORPOINTSTHENWECANCALCULATETHEPOSITIONWHERETHEPOINTSSHOULDBEANDWEMOVETHEPOINTSTOWARDSTHEPOSITIONSINSOMEPROPORTIONANDTHETRANSFORMISCOMPETEDFORONETIMEWHENWEREPEATTHEPROCESS,THESURFACEWILLAPPROACHANEARLYSTANDARDMINIMALSURFACETHELOCALMETHODTAKESTHEIDEAOFSOLVINGEQUATIONSHEREWEWILLALSOUSETHEDISCRIMINANTWECONSIDERTHEAMIDPOSITIONOFTHEINTERNALPOINTSASUNKNOWNNUMBERSTOESTABLISHEQUATIONSATLASTWEASSIGHTHESOLUTIONSTOTHEINTERNALPOINTSWEWILLGIVESOMEEXAMPLESACCORDINGTOTHESETWOMETHODS,TOPRACTICEANDOBSERVETHERESULTSANDTHENWEWILLCOMPARETHEMANDALSOTALKABOUTOUREXPECTATIONSKEYWORDSMINIMALSURFACE,LOCALMETHOD,GLOBALMETHOD中国科学技术大学本科毕业论文4极小曲面是一种集视觉美感与实际用途于一体的空间曲面。在日常的生活中，我们身边存在着不少极小曲面的例子。本章首先着手介绍一些极小曲面的例子和应用。而真实的应用中往往我们无法做到真正的极小曲面，只能去逼近它，而逼近的过程我们要用到空间数据的三角网格表示。为了将极小曲面和实际应用联系起来，第二节中我们再介绍一下空间曲面的三角网格表示的初步知识。11极小曲面的背景应用图1为将一个铁圈浸泡在肥皂水中又拿出之后铁圈上张起的肥皂泡。肥皂泡张成了一个光滑的形状，而这种形状的形成并不是偶然，而且这是一个有着特殊性质的形状。肥皂膜在这种形状中达成了两种“刚好”，一是此时曲面的总面积达到了刚好最小，二是曲面的表面张力达到了刚好处处相同。这对科学研究者来说有着非常重要的意义，所以也引来了数学，建筑学各方面的研究。在数学上，我们把这种曲面命名为极小曲面。从而，在以空间封闭曲线为边界的曲面中，寻找面积最小的曲面，这样的问题其实即为寻找极小曲面的问题。图1肥皂膜（图13来自1）图2斯图加特轻质研究所图3蒙特利尔世界博览会德国馆中国科学技术大学本科毕业论文5针对这个问题，首先要解决的就是极小曲面的存在性、唯一性问题。在文献2中，作者引用文献3中关于BROWDERHARTMANSTAMPACCHIA变分不等式解的存在惟一性定理，证明了极小曲面的存在惟一性，从而解决了这个问题。在保证唯一存在的前提下，人们需要做的只剩下通过考察极小曲面的必要条件，来试图寻找到这个面积最小的曲面。在建筑学上，极小曲面的寻找与构造有着极大的意义。图二为蒙特利尔世界博览会德国馆，其设计既是来源于肥皂泡的灵感。在这一方面最能代表的应属建筑学家弗赖奥托。弗赖奥托从1950年开始研究膜结构的形式特性，并认识到极小曲面不以人的意志而转移,而是一个拥有自己规律的整体，最终一定会归为某种不可变通的形式。奥托自创泡沫试验装置，将成果应用到建筑中，下面图2就是一个典型的例子。斯图加特轻质研究所是奥托所做的一个结构试验建筑，为了1967年蒙特利尔世界博览会德国馆（图3）做准备。总的来说，极小曲面的极小化原则，在建筑学和仿生学中的实际应用是非常有用的。但是奥托的的工作的出发点还仅仅是制作模型，测量记录并照搬重建，是需要真正的肥皂膜实验才能确定极小曲面的形状1。而本文的后面部分我们会用到具体的数学表达去表达和计算极小曲面。此外，文献4中举出了更多地极小曲面在建筑中的应用，如北京奥运会国家游泳馆水立方、世博轴阳光谷、韩国首尔大剧院、台中大都会歌剧院等等。文献5反过来阐述并反映了极小曲面在构造膜结构方面的巨大作用。12三角网格数据的简介三角网格是我们表达三维物体的手段。这里我们不把重点放在文件格式的细节里，而是重点放在三角网格数据表达的思想上。网格曲面的组成有下面的三个元素点，线，面。点与点之间的连接关系构成边，而这些边组成了许多的三角面片。三角面片的拼接构成了空间曲面。图4点图5边图6面中国科学技术大学本科毕业论文6我们要做的就是控制边界点不动的前提下，移动中间的点，使之转化成一个极小曲面。对于我们需要的三角网格数据，我们至少应该可以做到以下几件事情1判断一个点是否为边缘点；2按某种固定顺序查找一个点的所有临点（有公共边连接的点）；3在保持连线关系不变的前提下更改点的位置（线的位置相应更改）。我们本实验做的工作就是建立在此前提的基础上。其中，文献6给出了很好的判断边缘点的算法。本次试验所依托的实现环境为中国科学技术大学数学学院刘利刚老师提供的MINIMESHFRAME程序模板语言C开发环境VISUALSTUDIO2010文件格式OBJ中国科学技术大学本科毕业论文7本章为后面的算法和实现打下基础。主要分两方面的预备知识曲面的基本知识和这些数学内容在离散的三角网格数据中的表示。后者基本上是前者从连续控件到三维离散空间的直接翻译。21曲面的若干基本概念设参数曲面S是中一个连续曲面，写成U,V，假设的各个分量都有至少三阶的的连续偏导数。则据我们所知，有EU,VU,VU,V，FU,VU,VU,V，GU,VU,VU,V，为曲面S的第一基本形式。且有LU,VU,VU,V，MU,VU,VU,V，NU,VU,VU,V，为曲面S的第二基本形式。211平均曲率及有关的重要公式平均曲率的表达式为H，一个重要的公式如下,设为S上任一点，N为R处的法向量，则HRN212极小曲面平均曲率处处为零的曲面称作极小曲面。关于此定义与面积最小性的等价性可以参考文献7中的面积最小的曲面的平均曲率为零的证明过程。如文献1012所述，极小曲面的等价条件非常之多，也为我们提供了很多入手点可以解决构造问题。然而，经过观察，一种非常适合进入到离散状况的方法依据如下性质。设为极小曲面S上任一点，N为处的法向量，则HRN0。故根据221中最后的公式，我们可以得到，中国科学技术大学本科毕业论文8，而这个式子在离散情况下的推广可以成为我们固定边界构造极小曲面的关键性质。另外，关于曲面的基本形式、平均曲率还有极小曲面等相关的微分几何方面的知识可以参考文献810。22极小曲面的离散表示离散情况的极小曲面依然可以采取使平均曲率等于零的方法。这种方法的关键点在于用各个顶点的坐标数据来表示各种曲率。关于三角网格数据的曲率表示，文献1314给出了很好的例子。在这里，我们采取另一种方法，利用上一节提到的式子，写出其离散情况下的形式，并作为离散极小曲面的判别式。设S为三角网格数据构成的曲面，为S上任一非边缘点。假设的临点为,则，由于连续曲面中的，自然地，在现在的离散情况中，如果S是极小曲面，那么我们要求S作为一个极小曲面要满足即从公式上看，假设的临点为,则从指向,这N个临点的向量的矢量和为零。对于上式，我们其实可以理解为，中国科学技术大学本科毕业论文9即的位置应该位于临点重心处。这个公式将作为依据，来建立接下来的两种构造极小曲面的算法。中国科学技术大学本科毕业论文10近年来，构造极小曲面的问题反复多次地被人提及，并发展出了很多不同角度的方法。文献1518中给出了若干的构造极小曲面的方法。而本文中接下来的两种方法将依照第二章中给出的判别式来进行，通过达到或逼近判别式所述情形的方法来构造离散的近似极小曲面。31局部法局部法完全依据上一章提到的极小曲面的判别式，并将其理解为即的位置应该位于临点重心处。局部法的思想是用新的点不断代替旧的点，每次都向其当下所有临点的重心的方向移动一定比例的距离，执行到一定次数为止。STEP1对曲面中的所有点逐一检查，若为边缘点则不进行任何操作，若不为边缘点则进行如下“计算新位置”过程（注释对边缘点的判断对于三角网格数据是非常方便实现的。边缘点由于是要固定的，所以如果检测到边缘点，应该直接跳过。）计算新位置检测的所有临点,。用一个向量P来记录I从1到N时（）的和，最后令TP/N（注释我们希望每一个点都在临点重心处，但现在事实并不是这样的，所以要向临点重心处做位移。而T就是指向临点重心处的向量。）设一个新的点，令03T，图7点的更新中国科学技术大学本科毕业论文11（注释的作用是用来存储位移后的位置。但是注意在所有点都被处理完之前先不要把赋给，而是要等到所有非边界点的新位置都算出来以后统一替换。另外之所以比例取03而不是1是为了避免改变过猛引起的极端情况，所以我们采取少量多次的方法。）STEP2对STEP1中检测到的每一个非边界点赋新值，即对原曲面的所有非边界点统一做位置更新（注释一方面每个点的位移都是根据之前的临点计算，而现在临点的位置都有改变，另一方面之前改变比例较小，只有03，所以结合这两方面的因素，只有一次更新的情况下，图形还离极小曲面很远。）STEP3重复STEP2、3直到3000次（注释经测试03,3000次为效果较好的参数。）32全局法全局法的思想就是解方程。每个非边界点的位置设都是未知量，每个边界点的位置都是已知量，由极小曲面的限制条件来构成方程。每个点的X，Y，Z三个分量可以用同样的方法分别求解。STEP1建立系数矩阵记曲面共有的点数目为M，不妨把曲面中的所有点表示为,建立一个M阶方阵A来记录方程的系数。建立方法如下首先设A的所有元为0对于点，如果为边界点，则将AI，I改为1；如果不是边界点，则检测的临点，记临点数为N，记M个临点分别为为,，对于1JN，更改AI，为1，更改AI，I为N对于1M，进行上述步骤。STEP2建立常数阵建立CONX,CONY,CONZ三个M列向量，构成线性方程组的常数阵。建立方法如下建立X,Y,Z三个M列向量，记录待解点的三个坐标。首先设CONX,CONY,CONZ的所有元为0对于点，如果为边界点，则将CONX改为的X坐标，将CONY改为的Y坐标，将CONZ改为的Z坐标；如果不是边界点，令CONXCONY中国科学技术大学本科毕业论文12CONZ0对于1M，进行上述步骤。STEP3解方程分别解三个方程AXCONXAYCONYAZCONZ得到X,Y,Z三个列向量的解STEP4更新坐标对于1M，令CONX,CONY,CONZ,即完成点坐标的更新中国科学技术大学本科毕业论文13本章主要分析两种算法的实现还有优劣分析。为展示效果，将以以下四个模型为例BALLS,BUNNY_HEAD,CAT_HEAD,FACE以下是四个例子的原图，我们将在41和42中展示两种方法的处理结果。例一BALLS例二BUNNY_HEAD例三CAT_HEAD中国科学技术大学本科毕业论文14例四FACE41局部法411结果呈现以下四个例子均由局部法完成。例一BALLS例二BUNNY_HEAD中国科学技术大学本科毕业论文15例三CAT_HEAD例四FACE412结果分析原始模型点数适中，分布均匀，无尖锐部分，最终呈现结果非常好。可以看到，由于给定边界是位于平面上，所以最终得到的极小曲面结果就是平面，这是符合我们的几何直观的。由于原始模型点分布不是非常均匀，且有明显密集尖锐部分（兔耳朵），所以最后的结果也呈现了这一点。结果中两个突出部分说明局部法迭代的结果不是太好。此例的点数非常稀少，所以细节部分少，迭代的时候收敛到标准解的速度比较快，所以最终的效果呈现也非常好。中国科学技术大学本科毕业论文16情况类似例1，点数适中，分布均匀，无尖锐突出，故最终结果效果同样非常好。总的来说，从视觉上来看，极小曲面的目的基本达成了。经过了3000次的迭代，曲面被不断调整逼近极小曲面，最终达到了与极小曲面只差肉眼范围内难以分辨的误差。但是最后的结果仍然是有缺点的。如图二BUNNY_HEAD，兔子耳朵部分由于点比较密集，形状比较尖锐，直到迭代到最后仍然是看得出尖锐的两个突出。同样是耳朵部分，图三CAT_HEAD由于猫耳朵稍微平缓一些，而且图三的点数较稀疏，所以迭代到最后就没有图二中的两个尖锐突出。所以迭代次数是否足够还是一定程度上与点的个数与稀疏程度有关系。42全局法421结果呈现以下四个例子均由全局法完成。例一BALLS例二BUNNY_HEAD中国科学技术大学本科毕业论文17例三CAT_HEAD例四FACE422结果分析在全局法中，我们没有必要去逐个例子分析最终呈现的效果好不好，因为全局法解出的解是精准解，所以我们可以毫无意外地看到最终的结果就是标准的极小曲面。在运行速度方面，与局部法无太大差别。此外，全局法的速度基本由点数决定点数多时，耗时长；点数少时，耗时短。例如，例2的耗时会远远地高于例3。43综合分析从速度方面来看，两者并无太大差别。根据使用的感觉来看，在点数较少时（如CAT_HEAD），全局法较快一些；反之，在点数较多时，是全局法稍慢一些，局部法稍快一些（如BUNNY_HEAD）。中国科学技术大学本科毕业论文18从精确度方面来看，两者基本都能完成任务。局部法解出的结果用肉眼看上去基本与全局法解得的精确解一致，效果是可以的。但是也出现了一点特殊情况尖锐，点密集的地方出现了效果不好的情况（兔子的耳朵）。这个问题在提高迭代次数以后得到了解决，但是那会影响速度。下图为局部法中把次数调整到10000次之后BUNNY_HEAD的结果。由此可见，在实际的使用中，速度与精度，对一方的追求势必会影响对另一方的控制。对于两种方法，可根据对精度与速度的要求自行斟酌。如对精度要求非常高，则应不惜一切代价采取全局法或是迭代次数足够的局部法。若点数不多，且对精度要求一般，那么使用局部法也是可以完全满足需求的。图8BUNNY_HEAD结果左图只显示了点，明显看到两个密集处。右图显示了边，结果很光滑，效果不错。中国科学技术大学本科毕业论文19极小曲面是一类集聚美感与广泛用途与一体的曲面，这当然是毋庸置疑的事实。在本篇论文中，我们首先是在文章的前半段提及了非常多极小曲面的背景知识极其用途，在这个过程中我们了解了更多数学知识在现实生活中的作用与表现。在这里尤其是建筑方面，而且更重要的是，极小曲面，我们对它的认知开始越发的深刻。在试图利用边界构造极小曲面的过程中，我们有不同的选择。这是由于极小曲面丰富的性质，以及由这些优秀的性质衍生出的众多极小曲面的等价条件。最终在我们的文章中，我们选择了由连续曲面的一个性质推到离散情况中，作为我们的判别式，并做出了自己对它的解读。在这个过程中，我们发挥了合情推理的能力，而最终由我们的四个例子，我们也看到，最终的结果是非常好的，这也印证了我们方法的可行性。最终呈现出的两种方法的结果，基本都达到了我们的要求，但是有时候都会有缺陷。迭代次数不够时兔子的耳朵的呈现效果不佳，还有迭代次数足够时或是全局法点数太多时过慢的实现速度。两种方法，甚至细分到局部法的不同迭代次数，都有优势，也都不完美。这很遗憾，当然也在情理之中。在算法的实现过程中，我们用到了集成开发环境VS2010，以及语言C，还有MINIMESHFRAME程序模板，才可以读取并改造OBJ格式的三角网格数