数学专业毕业论文-三维物体的固定支架生成算法研究

致谢时光荏苒，转眼间，我已临近毕业，回顾过往四年，心中对这所校园，充满感激之情。记得当初走进这所学校时，心中充满了激动与彷徨，如今我的本科生涯已近尾声，感谢科大，给我一个这样良好的学习生活的氛围，让我收获了成长，让我留下了许许多多值得珍藏的美好的记忆。首先我要感谢我的导师刘利刚老师。我十分庆幸，在大三的时候上了刘老师的计算机图形学课程，让我得以看到我未曾见到的数学，开阔了视野，找到了自己的学习方向。在刘老师的教导下，我的编程能力有了很大的提高，从前我只会用C语言写一些简单的程序，现在我学会了用C+语言来写程序，对图像和网格的编辑也有了一定的了解。刘老师更是传递给我一个做研究的人应有的好奇与严谨的精神，让我成长了许多，并且对这世界抱有更大的好奇心。我由衷地感激刘老师给予我的引导支持和巨大帮助，做刘老师的学生，我感到非常荣幸！其次我要感谢欧阳文清同学，在完成毕业设计的过程中，欧阳文清同学耐心地解答了我许多疑惑，告诉我如何去寻找问题的解决方法。我没有学过优化，是欧阳同学告诉我应该用怎样的优化方法，并且指导我如何将程序运行的更加快速高效。欧阳同学学习态度十分认真，做起问题来十分严谨，他还会热心帮助同学，从他身上我学到了许多东西。也要感谢宿建平同学在做毕设的期间给予我的帮助和支持！能在本科最后半年，认识欧阳文清和宿建平同学，我十分的高兴。我还要感谢所有曾经教授过我基础课程的老师们，尤其是陈老师，许老师。入学第一年，我还在跟着少年班学院的课程体系上课，没有扎实的数学分析线性代数的基础，在大二上学期的时候，是这两位老师，教授我知识，并且帮助我补上前一年的基础课程的不足，让我得以更好的学习后续的数学课程。我也要感谢应用数学的老师们，告诉我应用数学的模样。我学习了数学建模，学到了小波分析，学到了组合学等等课程，感谢他们教授给我的专业知识，为我今后的学业做了很好的铺垫。感谢科大的师兄师姐和同学们对我学业的帮助，感谢金鹏飞同学和我的室友们，还有我的家人对我学习生活上的支持！希望在今后的学习中，我和所有本科的同学们，都能够努力向上，不忘初心，收获不断！目录摘要 2Abstract 3第1章绪论 41.1介绍 41.2本文工作安排 6第2章固定支架的生成算法 72.1计算固定支架的壳 72.2可固定性 82.2.1三角面接触阻碍与网格区域阻碍 82.2.2定义“可固定性” 92.3保留物体自由运动方向 92.4结果与分析 10第3章固定支架的变形 143.1理想目标与理论假设 143.2变形区域的划分 153.2.1对于具有凸表面的模型的简单划分规则 153.2.2对于表面凹凸不平的模型的划分规则 173.3变形优化模型 183.3.1求空间中散点在某个平面上的投影凸包 193.3.2变形方式与约束条件 213.3.3目标函数 253.3.4求解优化问题 263.4简单结果与分析 27第4章总结与展望 30参考文献 321中国科学技术大学本科毕业论文摘要用户如何自己生成一个三维物体的固定支架模型，再利用3D打印，将其创造出来，是一类3D打印的问题。固定支架，顾名思义，就是可以固定住物体的一个支架，比如一个手机支架，一个茶杯支架。本文介绍了一种生成物体固定支架的方法，可以将物体完全固定住，并且完全匹配物体表面。为了满足表面匹配的要求，我们提取物体表面的一部分，作为固定支架的表面，为其定义对物体的接触阻碍和可固定性并量化。从一个中心点出发，进行表面区域扩张，对我们扩张到的表面计算可固定性的值，达到一定阈值时停止扩张，提取出我们扩张到的表面，以此生成固定支架即可。不过只生成出固定支架还不能作为一个可用的模型，我们日常生活中见到的固定支架都是方便物体放进拿出的，而我们生成的固定支架是完全固定住物体的、一体化的设计。为了满足这个需求，考虑如何将固定支架变形到方便物体离开的形状。根据4D打印的相关知识，我们可以使用形状记忆材料来制造我们的支架，从而使其可以变形。这样的话，我们需要放进或者拿出物体时候，就先把支架变形，然后放进或拿出物体，再将其恢复原状即可。为了使得支架变形前后的形状可以相互转换，所以支架变形前后要保证拓扑一致，不可改动网格顶点和面的数量，也不可发生模型自交，所以我们将从初始的支架出发，划分出变形区域，不限制其中顶点的移动方式，也就是说把变形区域的所有顶点的3个坐标均作为变量，将顶点约束到不会阻碍物体运动的区域之外，在目标函数中加以顶点位移量、三角面变形度、顶点拉普拉斯坐标的约束，先通过简单的沿法向移动的方法给出满足约束条件的初值，利用内点惩罚函数法与LBFGS算法求解这个极小化问题，即可得到变形后的固定支架。对于凸模型，可以得到较好的固定支架与变形后的固定支架模型。关键词：制造变形凸包约束2中国科学技术大学本科毕业论文AbstractHow to design and fabricate a holder for 3D objects is a common problem in the3D printing field. A holder which can grip its corresponding object like a holder of amobile phone or a mug. In this paper, we will introduct an algorithm of designing aholder of a 3D object which matching the object on the surface completely. To meetthe requirements of the surface matching, we extract a part of the object surface as ourholder area and then we define its subregion blockage and holdability. To get a holderarea, we start from a seed triangle and then expansion the holder area along the objectsurface. We compute its holdability every time we add a triangle into the current holderarea and terminate the process when the holdability becomes greater than a threshold.Finally we gernerate a 3D-holder from the holder area.But holders that we have seen in our daily life are convient for people to put in ortakeoutobjects, whileourholdersareintegrativetogipobjectsrigidly. Inordertomeetthis requirment, we consider a deformation of our holder. Based on 4D printing, we canuse SMP to fabricate our holder and then we can change the holders shape to free theobjects. There also exists a obvious requirement for a holders that the two shapes of aholdercanbetransformedtoeachother. Sothetwoholderswithtwotransferableshapesshouldhaveasamenumberofverticesandtriangleswheretrianglescantintersectwitheach other. We start the deformation process from the original holder, and divide itssuface into a deformation area and a fix area. All of the vertices in the deformationarea are our variables. Instead of constraining the moving way of a vertex, we constrainits final position so that the vertex cannot hinder the movement of the object. We usevertex displacement, triangle deformation, and the Laplacian coordinate of a vertexas our objective function, and move vertices along their normal vectors to give initialvalues which satisfies the constraints. Finally we solve the minimization problem bythe internal penalty function method and LBFGS algorithm. We can get a reasonableresult for some objects which have ”good” shapes.Key Words: fabrication deformation convex constraints3中国科学技术大学本科毕业论文第1章绪论1.1介绍现代新型制造工艺例如3D打印，支持用户自己创造3D模型。然而，许多时候，设计一个有作用的3D模型并不是一件容易的事情，这需要足够的相关知识，通常用户只能去寻找现有的模型，而不是自己设计。所以如何满足普通用户想要自定义模型的需求，这是一大问题。用户的需求可能有千万种，其中一类就是，如何设计生成一个可以固定住普通物体的支架？日常生活中也经常可以用到一个物体的固定支架，比如，当我们需要一个连接器将手机固定到自行车把上，那么我们首先需要设计一个可以固定住手机的支架；当我们坐在椅子上看电视的时候，或许想把手中的水杯放在椅子上，但普通的椅子没有可以稳稳地放置水杯的地方，这时我们就需要一个水杯的固定支架了。如图1.1所示，是普通的手机和杯子的固定支架，加上一个连接装置，便可以将手机和杯子固定在我们想要放置它的位置上了。这里我们所说的固定支架，只是可以固定住物体的支架，如图上橙色部分，并不包括连接装置。对于一个普通的手机，或许可以买到相匹配的支架，然而，对于一个一般的物体，比如我们的茶杯，就要有很多种外形，我们很难找到一个与其匹配的固定支架。而本文将介绍一种一般的方法，可以生成完全匹配物体表面的固定支架！如图1.1所示的固定支架，很显然，可以将物体固定住。然而，对于杯子的固定支架，从外表看来，我们可以将其放进拿出，而对于手机的固定支架，要怎样把手机放进去或者拿出来呢？作为一个固定支架，不仅要能完全固定住物体，还有一个基本的要求是，支持物体放进拿出。那么，我们要如何实现这一点呢？参考文献1提出了一种方法，将这个固定支架进行分割，装以“搭扣”，使得它可以被拆分，从而支持物体放进拿出，如图1.2，这个方法是可行的，当我们需要放进手机时，就把它拆开，把手机放进去再把它合上就好了。不过本文并没有采取这种方法。4中国科学技术大学本科毕业论文图1.1固定支架1图1.2含有搭扣的固定支架1支持自定义模型的制造工艺不止3D打印一种，在3D打印的基础上，结合记忆合金，人们提出了4D打印。所谓4D打印，确切的说，就是用一种能够自动变形的材料，即形状记忆聚合物（Shape Memory Polymers，简称SMP)，代替传统材料的新型的打印技术。使用SMP材料，具有初始形状的物体，在改变其形状并固定后，加以一定的外界条件作用（如热、电、光等），可以恢复其初始形状（介绍来自百度百科）。考虑到4D打印的物体可变形的性质，或许我们可以做到不拆分固定支架，完全一体化的设计，使其可以满足物体放进拿出的要求。传统材料不具有可变形的性质，于是我们考虑使用SMP材料，生成固定支架，如果需要放进或者拿出物体时，我们将它变形到可以使物体离开的形状，称之为变形支架，需要固定物体时，使其变形到初始的固定支架形状，称之为初始支架。一个显而易见的事实是，假如我们全部使用SMP材料，那么对于这种可以随意变形的支架，我们总有办法使其变形到满足物体离开的需求。但是，SMP材料价格昂贵，并且一个固定支架的大部分区域是无需变形的，于是考虑影响物5中国科学技术大学本科毕业论文体运动的部分，也即需要变形的部分，使用SMP材料，其它固定部分可以使用传统材料。因此，我们研究如何从固定支架变形到可以使物体离开的形状，就有了意义。所以我们的问题就转化成为如何生成初始支架和变形支架。论文1中介绍了如何生成初始支架的方法，我们将在文中加以叙述，最重要的问题就是如何匹配模型的表面，而很显然，假如我们有一个和物体表面形状完全一模一样的空心支架，把物体放进去肯定能把物体固定住，但这样的话就太浪费材料并且很难变形，因此我们考虑直接提取表面的一部分作为固定支架，从一个中心点出发进行区域扩张，直到满足我们的固定准则就停止，将扩张到的表面作为固定支架的外形就可以了。而如何生成变形支架，满足物体放进拿出的要求，这个问题并不显然。由于初始支架和变形支架要能够相互转换，所以从三角网格的角度考虑，它们相互转换的过程不可以增加点或者面，并且支架的变形前后要保证拓扑关系一致。基于这个要求，我们只能从初始支架出发，考虑一个保证拓扑的变形技术，这个问题还比较难，本文将对于一般的具有凸表面的物体，介绍了生成变形后的固定支架的方法。1.2本文工作安排本文将通过一些物体表面网格数据，给出实验结果。正文第二章将介绍生成固定支架的方法，包括如何提取物体表面的一部分，为其定义可固定性，如何判定是否满足固定性质，以及如何从初始的部分表面，也就是壳，到完整的固定支架。第三章将介绍如何将固定支架变形到满足物体放进拿出需求的形状，因为我们只需要对阻碍物体移动的部分变形就可以了，所以我们将介绍怎样划分固定区域与变形区域，怎样给以满足物体离开需求的约束。最后，我们将会对已完成的工作进行总结，并对可使得结果更加合理的算法进行展望。6中国科学技术大学本科毕业论文第2章固定支架的生成算法为了便于表达，接下来我们将称固定支架为Holder。以下算法内容参考自文献1。对于一个自由形状的物体，我们将基于它的表面来生成一个可以阻碍物体自由运动的Holder，注意，这里提到的物体的自由运动指的是物体在三维空间中的平移运动。我们需要先生成一个壳（Shell），考虑从一个物体表面的一个种子三角面（Seed face）开始，进行区域扩张，每次扩张一圈领域，直到超过可固定性的阈值（Holdability criterion）。最后将这个Shell变成具有厚度的Holder，那么将可以被3D打印出来，作为固定支架。2.1计算固定支架的壳计算一个固定支架的壳（Shell），我们需要从以下3个方面考虑：(1)目标Shell的形状如何匹配物体的表面？(2)如何选取Seed face？(3)从Seed face开始如何进行区域扩张？对于(1)，我们很自然的可以想到，假如选取的Shell就是物体完全外表面，那么将一定满足我们的需求。然而，我们可以设想一下，假如我们需要一个手机的固定支架，固定住手机，方便我们用手机看视频，那么，如果要是把手机的外表面全部包住了，即使它可以固定住手机，也依然不满足实际问题的需求。因此，从实际问题和节省材料的角度出发，希望被包括的物体外表面越少越好，我们的问题便有了意义；对于(2)，Seed face是Shell的中心点，我们希望它可以尽量靠近用户所希望的Shell位置的中心，如果物体具有局部对称性的话我们选取的Seed face的位置应当尽量靠近局部对称中心，这里我们设置Seed face用户自选；对于(3)，我们需要对三角面定义扩张优先级，根据与Seed face的测地距离，在物体中的局部对称性等来定义。为了简单起见，只选择了与Seed face的测地距离作为扩张优先级，对于表面接近凸面的普通物体效果较好。如果表面形状亏格较高，可以考虑使用物体的凸包来近似物体。7中国科学技术大学本科毕业论文2.2可固定性为了给三角面扩张一个终止条件，我们利用“可固定性”的度量（Holdabilitymeasure）。Holdability可以衡量Holder与物体的接触区域是否可以阻碍物体的移动。我们每往Shell中加入一个三角面，就计算一次Holdability，直到大于我们给定的阈值。2.2.1三角面接触阻碍与网格区域阻碍为了定义Holdability，我们考虑物体的三维运动，令p为物体表面的一个点，位置坐标为x，其外法向为n。给定p与，我们可以计算p沿着它的外法向移动了多少，可以衡量当物体沿着微微移动时，p所经历的阻碍大小。我们将这个量称为接触阻碍（Contact blockage），记作b(p;)。如果点沿其外法向移动，那么b将取非负值。那么，具体如何计算b(p;)呢？给定 2 R3为位移方向，我们定义物体表面点p的接触阻碍为：b(p;) = max(nT;0): (2.1)如果b 0，那么p沿着其外法向移动，因此p将阻碍物体在方向上的移动。若b = 0，那么p将不会阻碍物体在这个方向上的移动。对于物体表面网格的三角面，我们通常取它的重心代表它在网格上的位置，从而我们可以使用重心的接触阻碍来表示一个三角面的接触阻碍。当Shell的区域在扩张时，Shell与物体的接触面在增加。令T为当前Shell所包含的所有三角面的集合。给定T与，我们定义网格区域阻碍（Subregionblockage）如下：B(T ;) =ib(pi;); (2.2)这里pi为第i个三角面的重心。由B的定义式可见，B表示当物体沿着移动时，Shell所包括的所有三角面对其的阻碍。显然的，B是一个非负的量。若B = 0，那么Shell中的所有三角形对物体在方向上移动均无阻碍，因此是物体的一个自由运动方向。在这种情况下，由T定义的Holder就无法固定住物体；若B 0，那么T中至少有一个三角面，在方向上阻碍了物体的运动。8中国科学技术大学本科毕业论文2.2.2定义“可固定性”对于一个Holder，我们希望它可以在任意方向上都阻碍了物体的移动。也就是说，对于任意的，均有B(T ;) 0。对于由T定义的Holder，我们定义它的“可固定性”如下：H(T ) = minB(T ;); subject to jjjj = 1; (2.3)其中 2 R3，我们将其限制在R3中的单位球面上。根据H(T )的定义，显然的，H(T ) 0等价于对于8 ，均有B(T ;) 0，如此，目标物体至少有一个三角面被Holder完全固定住，无法不碰撞地从Holder中取出。但是，这样定义的Holder，我们无法给不同的目标物体一个比较统一的阈值。因此我们考虑将H(T )标准化。考虑到一件比较平凡的事情，假如T =物体整个表面网格，那么H(T )可以取到最大值。因此我们对其做如下标准化：eH(T ) = H(T )H(whole mesh ): (2.4)做了标准化之后，显见0 eH 1，注意这里我们还需要排除缩放对Holdability的影响，我们将输入的网格也做统一化，限制在相同的Bounding box中。我们可以选择比较统一的阈值来给区域扩张一个终止条件。可以想到，若eH 0，那么Holder几乎无法固定住物体，而若eH 1，Holder将会牢牢地固定住物体。为了求解式(2.3)与式(2.4)的优化问题，我们利用COBYLA算法2。每当我们往当前T中添加一个三角面，就求解一次优化问题，直到eH(T )大于给定阈值，一般取为0.1。2.3保留物体自由运动方向(a) (b)图2.1保留球的自由移动方向9中国科学技术大学本科毕业论文用户有时需要保留物体的一个自由运动方向，比如对于一个球来说，也许用户并不想完全固定住它，正如本文绪论中提到的，留一个方向方便用户放进拿出，记作free，如图2.1 (b)所示。当我们求解式(2.4)的优化问题时，我们对加以如下约束： free : (2.5)上式约束了在绕free的“锥”之外，也就是说与free有一定距离。参数控制了这个“锥”的大小，由于我们无法确定一个一般形状的物体，所需要的“锥”的大小，我们取 0; (3.1)那么我们认为，三角面f在方向上影响了物体的移动。如图3.2所示，球面是凸的，当物体要沿着移动时，显然地，三角面f1会阻碍它的移动，而f2不会。15中国科学技术大学本科毕业论文图3.2凸表面的阻碍判定。若与三角形法向的内积大于0，则该三角形阻碍物体在方向的运动，否则不阻碍。如图3.3所示，我们列出了两个根据式(3.1 )所划分的Holder的变形区域与非变形区域的例子，其中，蓝色区域为变形区域，绿色区域为非变形区域。从图中可以看出，对于这样比较“好”的形状，我们可以较好的划分它的变形与非变形区域。(a) (b)图3.3具有凸表面Holder的变形区域划分。其中(a)中物体整个具有凸表面，而(b)中的Holder是一个凸物体表面的一部分。不过由于坐标都是绝对值小于1的小数，判断 n与0的大小关系时，如果内积得数接近0，则会产生误差，图3.3 (b)就是出现了误差，如图3.4中红色圆圈中标出的，本来划分界线不应该出现一块“锯齿”状的部分。不过这个并不影响我们的计算，我们认为这样的结果还是好的。其实只要不是凹凸不平的表面，这种规则都是适用的。如图3.5所示，(a)图的Eight模型，式(3.1 )的划分规则也是适用的；而(b)中的Bunny模型，其表面16中国科学技术大学本科毕业论文图3.4区域划分误差，如图中红色圆圈圈出的部分。凹凸不平，按照这种方式划分出来的变形区域不连通，根据我们的假设(4)，这是无效的。(a) Eight (b) Bunny图3.5非凸Holder的变形区域划分。其中蓝色区域为Holder中的变形区域，绿色为非变形区域。3.2.2对于表面凹凸不平的模型的划分规则我们在2.3节曾讨论了如何保留物体的一个自由运动方向，那么我们考虑，保留物体的自由运动方向，根据情况，缩小一点可固定性阈值（Holdabilitycriterion），再次生成一个Holder，记为Holder1，最开始的完全固定支架记为Holder0。那么我们定义的划分是这样的：变形区域= Holder1扩张到的所有三角面；非变形区域= Holder0扩张到的所有三角面-变形区域。如图3.6所示，我们列了两个例子，一个是局部凸表面情况下的Torus模型，一个是表面凹凸不平情况下的Bunny模型。从图中可以看出，由于我们在第2章中说明的Shell区域扩张方式比较粗浅，利用这种划分规则，变形区域均为“环”17中国科学技术大学本科毕业论文状。从Bunny的例子中可以看出，这样的划分规则对于表面凹凸不平的模型，效果比利用3.2.1中所阐述的划分规则要好，至少可以保证变形区域是连通的。而从Torus的例中可以看出，这种划分的效果并不好，其中红色圆圈标出来需要变形而未被包括到变形区域的部分，橙色圆圈标出来不需要被包括到变形区域的部分。前者是因为，即使是保留了一个自由运动方向，区域扩张方式仍然不变，只是计算Holdability的方式变化了而已，而我们在生成Holder1时，将Holdabilitycriterion取为0.05了，这也仍然是个大于0的数（直接取为0会造成不必要的浪费），因此还会有稍阻碍物体移动的三角面没有被包括到变形区域中去；而后者是因为扩张方式决定了变形区域只能是“环”状的，因此对于这种比较“好”的形状的模型，我们还是采用3.2.1中的利用面法向与移动方向内积来对Holder进行变形与非变形区域的划分。(a) Bunny (b) Torus图3.6凹凸不平的表面Holder的变形区域划分。其中蓝色区域为Holder中的变形区域，绿色为非变形区域。为了简单起见，我们采取的约束是凸包约束，将在3.3.2中具体说明，因此对于非凸的Holder不够适用。以下我们将阐述的算法只对具有凸表面的Holder的变形适用。3.3变形优化模型在介绍优化方法之前，我们先介绍将要用到的一个算法。其中3.3.1是为了给变形区域的点，一个充分的约束条件。在3.3.2与3.3.3中，将给出将Holder变形的具体算法内容。18中国科学技术大学本科毕业论文3.3.1求空间中散点在某个平面上的投影凸包问题描述：空间中有一些散点fPig，给定过原点的平面 ，其法向为N。求这些散点在平面 上的投影点的凸包。想要求这个凸包，我们首先要求出空间中散点在 上的投影点。也就是说，给定点P与过原点的面 ，求出P在 上的投影点。为了方便下一步在平面上求凸包，我们先要以 为xOy平面，N为z方向，记其基向量分别为 、 、N，建立空间直角坐标系O N。然后计算P(x0;y0;z0)的投影点P1在该坐标系下的坐标(x1;y1;0)。图3.7平面上的投影点计算P1(x1;y1;0)方法如下：Setp1.求基向量 、 。记N = (A;B;C)，则平面方程为Ax + By + Cz = 0，我们想要求平面上非原点的一点，假设jAj jBj;jCj，则A = 0，令z = 0，则Ax+By = 0，从而x = BA，可得到一非原点的点( BA;1;0)。将其标准化，则可得到= ( BpA2 + B2; ApA2 + B2;0): (3.2)若jBj jAj;jCj，则可求出 = (0; CpB2 + C2; BpB2 + C2)；否则的话，可求出 = ( CpA2 + C2;0; ApA2 + C2)。这里要判断出最大值的原因是，我们要保证在分母上的平方和项不能过小，否则会增大误差。求出 后，根据 和N，与坐标系右手规则，我们可以求出= N :若取式(3.2 )中的 ，则我们最终计算出的 为：= ( ACpA2 + B2; BCpA2 + B2;pA2 + B2): (3.3)19中国科学技术大学本科毕业论文Setp2.求x1、y1。只需计算P与 、 的内积即可，即：x1 = P ;y1 = P : (3.4)所以P的投影点P1在坐标系O N下的坐标为(P ;P ;0)，我们接下来只在平面上考虑问题，那么不考虑竖坐标，记P1 = (x1;y1) = (P ;P )。(a) (b)(c) (d)图3.8 Graham扫描算法过程求出O 坐标系下散点在 上的投影坐标后，我们只需要考虑如何求出 上一些点的凸包即可，问题现在转化为了求平面上散点集的凸包，通过Graham扫描算法完成3, 13。算法通过维护一个“凸壳”，按照一定次序不断往凸壳中添加凸多边形的点，具体内容如下：Setp1.预处理步骤。对于平面上的散点集fpig，我们要将其顺序排列。取y坐标最小的点记为p0，若有相同则取再x坐标最小的点作为p0；然后计算p0与其他所有点连线与x轴的夹角（计算余弦值即可），然后按照逆时针顺序排序。排序结果如图3.8 (a)所示，注意，若是出现夹角相同的点，那么我们只取与p0距离较远的点，其余点舍弃；Setp2.定义集合F为凸包顶点集。首先加入p0到F中，根据p0的取法与排序方式，p1一定是凸包的顶点，我们再加入p1到F中，n = 1；20中国科学技术大学本科毕业论文Setp3.对于pn+1，记F中最后加入的两点为q0和q1，若 !q0q1 !q1pn+1 0，则加入该点到F中，否则删除点pn，更新q0;q1，再次进行判断，直到满足加入条件。如图3.8 (b)中 !p4p5与 !p3p4的关系，那我们就删除p4，再判断p3p5与p2p3的关系，加入p5，如图3.8 (c)；Setp4. n = n+1，若n等于点个数，终止算法，输出F中的点，否则继续Step3。如图3.8 (d)为算法终止时的结果。3.3.2变形方式与约束条件我们在前面曾假设过，我们处理的Holder具有凸的表面，那么对于这样的情况，考虑Holder沿着free方向的挤出，根据3.2.1中的划分规则，可以知道变形区域在以free为法向的平面 上的投影凸包上的点，一定是由变形区域与非变形区域边界上的三角面上的点组成。我们希望变形区域的顶点可以移动到物体沿free运动的挤出区域之外，从而我们约束变形后的顶点在 上的投影，在原变形区域顶点集凸包C之外，这样的话变形后的顶点就不阻碍物体沿着free运动。记原来的顶点位置为v，变形后的顶点位置为v1，记投影算子为Proj( )，即Proj(v) = v在 上的投影坐标。那么我们的约束可以描述为：Proj(v1) =2 C: (3.5)那么v1怎么用v来表示呢？有两种方法，我们先介绍法一。只给顶点位置变量一个自由度。我们曾用过的方法是给这些顶点一个沿外法向的自由度，让他们沿其自身的外法向移动，直到它的投影满足我们的凸包约束。记nv为v的外法向，我们可以得到v1 = v + nv; (3.6)其中 0为顶点沿其外法向移动的距离。从式(3.5 )可以给出 的取值范围，我们利用凸多边形的性质来判断一个点是否在多边形外。如图3.9，多边形的每一条有向边（逆时针方向）都将平面分成了“左”“右”两个部分，从图中可见，若点P在每条有向边 !PkPk+1的左侧，那么P在多边形内部，反之则在外部（多边形上算作外部）。所以约束点在凸包之外，只需要存在一条有向边，点在该边右侧即可4。21中国科学技术大学本科毕业论文图3.9点与凸多边形位置关系而P在 !PkPk+1右边可以表示为!PkPk+1 !PkP 0: (3.7)由式(3.6 )、(3.4 )与(3.7 )，记Pk = (xk;yk)，我们可将式(3.5 )转化为：9k;(v + nv) xk;(v + nv) yk) (xk+1 xk;yk+1 yk) 0: (3.8)我们对每个k求解(3.8 )，该式是线性的，我们可以得到 的取值范围为av或 bv，其中av;bv为与v有关的常数。从而问题转化为区间约束优化问题，我们取f vg的2模作为优化函数。如图3.10为我们的结果，可见结果并不好。因为有些顶点的法向与free夹角较小，可能 要取很大的值才能满足约束，那么点移动的距离就非常远，考虑到这一点，我们又约束了点在free上的坐标不变，让它不要跑的太远，(c)(d)是这样约束后(a)(b)的结果，可见(c)的结果还可以接受，但(d)的结果仍然不太好。22中国科学技术大学本科毕业论文(a) (b)(c) (d)图3.10 Torus模型沿法向移动变形结果。其中其中(a)(b)为取不同Holdabilitycriterion时的结果，(c)(d)是修正后的结果。综上可见这个沿法向移动的方法效果不好，点的移动方式太过单一，对于图示的很简单地模型也不适用，而且不确定能否保证拓扑。基于这样的结果，我们考虑到对点的移动方式不好加以限制，提出了法二。详述如下。不限制变形区域顶点的移动方式。我们想要写好这个约束条件，仍然需要考虑如何约束点在C，在法一中我们已经叙述了一种判断点与凸多边形位置关系的方法，但那个约束条件是求解许多个不等式的并集，难以表达成一个光滑函数的约束，在法一里面采用是因为对于一个顶点只对应一个变量，容易求解不等式的并集。这里我们不采用这种方法，而是采用“面积法“。引入如下引理：引理3.1设C为凸多边形，顶点为P1; ;Pn，平面上有一点P，连接P与所有顶点，则P =2 C（严格在C外部）与下列条件等价：iSPPiPi+1 SC: (3.9)23中国科学技术大学本科毕业论文(a)点在凸多边形内(b)点在凸多边形外图3.11面积法判断点与多边形位置关系注意引理中要求严格大于，若我们采用内点惩罚函数法，变量无法到达边界。考虑到这一点，再考虑到计算误差，我们取一个很小的数“ 0，记S0 = SC +“，将式(3.9 )转化为：iSPPiPi+1 S0: (3.10)接下来我们需要计算每个SPPiPi+1。注意到对于三角形PPiPi+1来说，记Pi = (xi;yi)，P = (s;t)，它的面积可以利用边向量的叉积计算：SPPiPi+1 = 12j !PPi !PPi+1j= 12j(xi s)(yi+1 t) (yi t)(xi+1 s)j= 12jais + bit + cij:再回来考虑我们的问题。设v为一变量顶点，其坐标为(x;y;z)，它在平面上的投影坐标记为Proj(v) = (s;t) = (v ;v )。那么v =2 C等价于SProj(v)PiPi+1 = 12jais + bit + cij= 12jaix + biy + ciz + dijS0; i 2 f1;2; ;ng;(3.11)其中ai;bi;ci;di均为与i有关的常数。这是个可以被求导的约束函数，我们只需要对所有的变量顶点，都加以式(3.11 )的约束即可。下面我们就采用法二的顶点移动方式与凸包约束条件。24中国科学技术大学本科毕业论文3.3.3目标函数我们利用了3.3.2法二的约束条件，已经可以保证点可以移动到不阻碍物体运动的区域之外了。现在我们需要考虑的是如何选取目标函数，来保证变形前后物体的拓扑一致。一种简单的考虑是保点与点间的距离，但是这样的目标函数非线性程度很高。参考文献5中引入了一种简单的能量来代替保距离的能量，将三角形的变形看成是四面体的变形，衡量四面体的变形从而衡量三角形的变形。记变形区域三角面集合为T0，对于任一三角形f 2 T0，f的3个顶点记为(v1 v2 v3)，引入v4于f的重心加上单位外法向量的位置，变形后的f顶点记为(v1 v2 v3)，同样地，引入v4。然后我们将三角形的变形看成是四面体的变形，引入四面体意义下的f到f形变Jacobi矩阵6，解释如图3.12：T = (v1 v4;v2 v4;v3 v4) (v1 v4;v2 v4;v3 v4) 1: (3.12)一般情况下，T并不是一个刚体变换，最接近它的刚体变换记为R，R可从T的SVD分解中提取出。将T进行分解，T = U V T，去掉T中缩放矩阵 ，则R = UV T:图3.12对于形变矩阵T的解释。其中R是利用SVD分解从T中提取出的旋转变换矩阵5。我们用如下度量来衡量四面体的变形程度：jjT Rjj2F:因此目标函数可以表示为f(x) =k2T0jjTk Rkjj2F:25中国科学技术大学本科毕业论文而我们也希望能够减少移动量，因此在目标函数中再添加位移量2模的约束。同时，根据需要，选择性地加入保Laplacian坐标项，即：jjL(vi) L(vi)jj2;其中Laplacian坐标的计算参考7，对于顶点vi，其Laplacian坐标计算公式如下：L(vi) = 14A