三维物体的固定支架生成算法研究

学士学位论文 三维物体的固定支架 生成算法研究 作者姓名：邹倩芳 学科专业：数学与应用数学专业 导师姓名：刘利刚 教授 完成时间：二一七年五月 University of Science and Technology of China A dissertation for bachelors degree Designing Shell-Grippers for 3D Objects Authors Name:Qianfang Zou Speciality:Applied Mathematics Supervisor:Prof. Ligang Liu Finished Time:May, 2017 中国科学技术大学本科毕业论文 致谢 时光荏苒，转眼间，我已临近毕业，回顾过往四年，心中对这所校园，充满 感激之情。记得当初走进这所学校时，心中充满了激动与彷徨，如今我的本科生 涯已近尾声， 感谢科大， 给我一个这样良好的学习生活的氛围， 让我收获了成长， 让我留下了许许多多值得珍藏的美好的记忆。 首先我要感谢我的导师刘利刚老师。我十分庆幸， 在大三的时候上了刘老师 的计算机图形学课程，让我得以看到我未曾见到的数学，开阔了视野，找到了自 己的学习方向。在刘老师的教导下，我的编程能力有了很大的提高，从前我只会 用 C 语言写一些简单的程序，现在我学会了用 C+ 语言来写程序，对图像和网 格的编辑也有了一定的了解。刘老师更是传递给我一个做研究的人应有的好奇 与严谨的精神，让我成长了许多，并且对这世界抱有更大的好奇心。我由衷地感 激刘老师给予我的引导支持和巨大帮助，做刘老师的学生，我感到非常荣幸！ 其次我要感谢欧阳文清同学，在完成毕业设计的过程中，欧阳文清同学耐心 地解答了我许多疑惑，告诉我如何去寻找问题的解决方法。我没有学过优化，是 欧阳同学告诉我应该用怎样的优化方法，并且指导我如何将程序运行的更加快 速高效。欧阳同学学习态度十分认真，做起问题来十分严谨，他还会热心帮助同 学， 从他身上我学到了许多东西。也要感谢宿建平同学在做毕设的期间给予我的 帮助和支持！能在本科最后半年，认识欧阳文清和宿建平同学，我十分的高兴。 我还要感谢所有曾经教授过我基础课程的老师们，尤其是陈洪佳老师，许斌 老师。入学第一年，我还在跟着少年班学院的课程体系上课，没有扎实的数学分 析线性代数的基础，在大二上学期的时候，是这两位老师，教授我知识，并且帮 助我补上前一年的基础课程的不足，让我得以更好的学习后续的数学课程。我也 要感谢应用数学的老师们，告诉我应用数学的模样。我学习了数学建模，学到了 小波分析，学到了组合学等等课程，感谢他们教授给我的专业知识，为我今后的 学业做了很好的铺垫。 感谢科大的师兄师姐和同学们对我学业的帮助，感谢金鹏飞同学和我的室 友们，还有我的家人对我学习生活上的支持！希望在今后的学习中，我和所有本 科的同学们，都能够努力向上，不忘初心，收获不断！ 中国科学技术大学本科毕业论文 目录 摘要 2 Abstract3 第 1 章 绪论 4 1.1 介绍 4 1.2 本文工作安排 6 第 2 章 固定支架的生成算法7 2.1 计算固定支架的壳 7 2.2 可固定性 8 2.2.1 三角面接触阻碍与网格区域阻碍 8 2.2.2 定义“可固定性” 9 2.3 保留物体自由运动方向 9 2.4 结果与分析 10 第 3 章 固定支架的变形14 3.1 理想目标与理论假设 14 3.2 变形区域的划分 15 3.2.1 对于具有凸表面的模型的简单划分规则 15 3.2.2 对于表面凹凸不平的模型的划分规则 17 3.3 变形优化模型 18 3.3.1 求空间中散点在某个平面上的投影凸包 19 3.3.2 变形方式与约束条件 21 3.3.3 目标函数 25 3.3.4 求解优化问题 26 3.4 简单结果与分析 27 第 4 章 总结与展望 30 参考文献 32 1 中国科学技术大学本科毕业论文 摘要 用户如何自己生成一个三维物体的固定支架模型，再利用 3D 打印，将其创 造出来，是一类 3D 打印的问题。固定支架，顾名思义，就是可以固定住物体的 一个支架，比如一个手机支架，一个茶杯支架。本文介绍了一种生成物体固定支 架的方法，可以将物体完全固定住，并且完全匹配物体表面。为了满足表面匹配 的要求，我们提取物体表面的一部分，作为固定支架的表面，为其定义对物体的 接触阻碍和可固定性并量化。从一个中心点出发，进行表面区域扩张，对我们扩 张到的表面计算可固定性的值，达到一定阈值时停止扩张，提取出我们扩张到的 表面，以此生成固定支架即可。 不过只生成出固定支架还不能作为一个可用的模型，我们日常生活中见到 的固定支架都是方便物体放进拿出的，而我们生成的固定支架是完全固定住物 体的、一体化的设计。为了满足这个需求，考虑如何将固定支架变形到方便物体 离开的形状。根据 4D 打印的相关知识，我们可以使用形状记忆材料来制造我们 的支架，从而使其可以变形。这样的话，我们需要放进或者拿出物体时候，就先 把支架变形，然后放进或拿出物体，再将其恢复原状即可。为了使得支架变形前 后的形状可以相互转换，所以支架变形前后要保证拓扑一致，不可改动网格顶点 和面的数量，也不可发生模型自交，所以我们将从初始的支架出发，划分出变形 区域，不限制其中顶点的移动方式，也就是说把变形区域的所有顶点的 3 个坐标 均作为变量，将顶点约束到不会阻碍物体运动的区域之外，在目标函数中加以顶 点位移量、三角面变形度、顶点拉普拉斯坐标的约束，先通过简单的沿法向移动 的方法给出满足约束条件的初值，利用内点惩罚函数法与 LBFGS 算法求解这个 极小化问题，即可得到变形后的固定支架。对于凸模型，可以得到较好的固定支 架与变形后的固定支架模型。 关键词：制造变形凸包约束 2 中国科学技术大学本科毕业论文 Abstract How to design and fabricate a holder for 3D objects is a common problem in the 3D printing field. A holder which can grip its corresponding object like a holder of a mobile phone or a mug. In this paper, we will introduct an algorithm of designing a holder of a 3D object which matching the object on the surface completely. To meet the requirements of the surface matching, we extract a part of the object surface as our holder area and then we define its subregion blockage and holdability. To get a holder area, we start from a seed triangle and then expansion the holder area along the object surface. We compute its holdability every time we add a triangle into the current holder area 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 or take out objects, while our holders are integrative to gip objects rigidly. In order to meet this requirment, we consider a deformation of our holder. Based on 4D printing, we can use SMP to fabricate our holder and then we can change the holders shape to free the objects. There also exists a obvious requirement for a holders that the two shapes of a holdercanbetransformedtoeachother. Sothetwoholderswithtwotransferableshapes should have a same number of vertices and triangles where triangles cant intersect with each other. We start the deformation process from the original holder, and divide its suface into a deformation area and a fix area. All of the vertices in the deformation area are our variables. Instead of constraining the moving way of a vertex, we constrain its final position so that the vertex cannot hinder the movement of the object. We use vertex displacement, triangle deformation, and the Laplacian coordinate of a vertex as our objective function, and move vertices along their normal vectors to give initial values which satisfies the constraints. Finally we solve the minimization problem by the internal penalty function method and LBFGS algorithm. We can get a reasonable result for some objects which have ”good” shapes. Key Words: fabricationdeformationconvex constraints 3 中国科学技术大学本科毕业论文 第 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可固定性 为了给三角面扩张一个终止条件， 我们利用 “可固定性” 的度量 （Holdability measure）。Holdability 可以衡量 Holder 与物体的接触区域是否可以阻碍物体的 移动。我们每往 Shell 中加入一个三角面，就计算一次 Holdability，直到大于我 们给定的阈值。 2.2.1三角面接触阻碍与网格区域阻碍 为了定义 Holdability，我们考虑物体的三维运动 ，令 p 为物体表面的一个 点，位置坐标为 x，其外法向为 n。给定 p 与 ，我们可以计算 p 沿着它的外法 向移动了多少，可以衡量当物体沿着 微微移动时，p 所经历的阻碍大小。我们 将这个量称为接触阻碍（Contact blockage），记作 b(p,)。如果点沿其外法向 移动，那么 b 将取非负值。那么，具体如何计算 b(p,) 呢？ 给定 R3为位移方向，我们定义物体表面点 p 的接触阻碍为： b(p,) = max(nT,0).(2.1) 如果 b 0，那么 p 沿着其外法向移动，因此 p 将阻碍物体在 方向上的移动。 若 b = 0，那么 p 将不会阻碍物体在这个方向上的移动。对于物体表面网格的三 角面，我们通常取它的重心代表它在网格上的位置，从而我们可以使用重心的接 触阻碍来表示一个三角面的接触阻碍。 当 Shell 的区域在扩张时，Shell 与物体的接触面在增加。令 T 为当前 Shell 所包含的所有三角面的集合。给定 T 与 ，我们定义网格区域阻碍（Subregion blockage）如下： B(T ,) = i b(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 ) = min B(T ,), subject to | = 1,(2.3) 其中 R3，我们将其限制在 R3中的单位球面上。根据 H(T ) 的定义，显然的， H(T ) 0 等价于对于 ，均有 B(T ,) 0，如此，目标物体至少有一个三角 面被 Holder 完全固定住，无法不碰撞地从 Holder 中取出。 但是，这样定义的 Holder，我们无法给不同的目标物体一个比较统一的阈 值。因此我们考虑将 H(T ) 标准化。考虑到一件比较平凡的事情，假如 T = 物 体整个表面网格，那么 H(T ) 可以取到最大值。因此我们对其做如下标准化： e H(T ) = H(T ) H(whole mesh). (2.4) 做了标准化之后，显见 0 e H 1，注意这里我们还需要排除缩放对 Holdability 的影响，我们将输入的网格也做统一化，限制在相同的 Bounding box 中。我们可 以选择比较统一的阈值来给区域扩张一个终止条件。可以想到，若 e H 0，那么 Holder 几乎无法固定住物体，而若 e H 1，Holder 将会牢牢地固定住物体。为了 求解式 (2.3) 与式 (2.4) 的优化问题，我们利用 COBYLA 算法 2。每当我们往当 前 T 中添加一个三角面，就求解一次优化问题，直到 e H(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 时，将 Holdability criterion 取为 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求空间中散点在某个平面上的投影凸包 问题描述：空间中有一些散点 Pi，给定过原点的平面 ，其法向为 N。求 这些散点在平面 上的投影点的凸包。 想要求这个凸包，我们首先要求出空间中散点在 上的投影点。也就是说， 给定点 P 与过原点的面 ，求出 P 在 上的投影点。为了方便下一步在平面上 求凸包，我们先要以 为 xOy 平面，N 为 z 方向，记其基向量分别为 、N， 建立空间直角坐标系 ON。然后计算 P(x0,y0,z0) 的投影点 P1在该坐标系下 的坐标 (x1,y1,0)。 图 3.7平面上的投影点 计算 P1(x1,y1,0) 方法如下： Setp1. 求基向量 、。记 N = (A,B,C)，则平面方程为 Ax + By + Cz = 0，我 们想要求平面上非原点的一点，假设 |A| |B|,|C|，则 A = 0，令 z = 0， 则 Ax + By = 0，从而 x = B A ，可得到一非原点的点 (B A ,1,0)。将其标 准化，则可得到 = ( B A2 + B2 , A A2 + B2 ,0).(3.2) 若 |B| |A|,|C|， 则可求出 = (0, C B2 + C2 , B B2 + C2 )； 否则的话， 可 求出 = ( C A2 + C2 ,0, A A2 + C2 )。这里要判断出最大值的原因是，我 们要保证在分母上的平方和项不能过小，否则会增大误差。求出 后，根 据 和 N，与坐标系右手规则，我们可以求出 = N . 若取式 (3.2) 中的 ，则我们最终计算出的 为： = ( AC A2 + B2 , BC A2 + B2 , A2 + B2).(3.3) 19 中国科学技术大学本科毕业论文 Setp2. 求 x1、y1。只需计算 P 与 、 的内积即可，即： x1= P ,y1= P .(3.4) 所以 P 的投影点 P1在坐标系 ON 下的坐标为 (P ,P ,0)，我们接 下来只在平面上考虑问题，那么不考虑竖坐标，记 P1= (x1,y1) = (P ,P )。 (a)(b) (c)(d) 图 3.8Graham 扫描算法过程 求出 O 坐标系下散点在 上的投影坐标后，我们只需要考虑如何求出 上一些点的凸包即可，问题现在转化为了求平面上散点集的凸包，通过 Graham 扫描算法完成 3, 13。算法通过维护一个“凸壳” ，按照一定次序不断往凸壳中 添加凸多边形的点，具体内容如下： Setp1. 预处理步骤。对于平面上的散点集 pi，我们要将其顺序排列。取 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) / 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) 转化为： k,(v + nv) xk,(v + nv) yk) (xk+1 xk,yk+1 yk) 0. (3.8) 我们对每个 k 求解 (3.8)，该式是线性的，我们可以得到 的取值范围为 av或 bv，其中 av,bv为与 v 有关的常数。从而问题转化为区间约束优化 问题，我们取 v 的 2 模作为优化函数。如图3.10为我们的结果，可见结果并不 好。因为有些顶点的法向与 free夹角较小，可能 要取很大的值才能满足约束， 那么点移动的距离就非常远，考虑到这一点，我们又约束了点在 free上的坐标 不变，让它不要跑的太远，(c)(d) 是这样约束后 (a)(b) 的结果，可见 (c) 的结果还 可以接受，但 (d) 的结果仍然不太好。 22 中国科学技术大学本科毕业论文 (a)(b) (c)(d) 图 3.10Torus 模型沿法向移动变形结果。其中其中 (a)(b) 为取不同 Holdability criterion 时的结果，(c)(d) 是修正后的结果。 综上可见这个沿法向移动的方法效果不好，点的移动方式太过单一，对于图 示的很简单地模型也不适用，而且不确定能否保证拓扑。基于这样的结果，我们 考虑到对点的移动方式不好加以限制，提出了法二。详述如下。 不限制变形区域顶点的移动方式。我们想要写好这个约束条件， 仍然需要考 虑如何约束点在 C，在法一中我们已经叙述了一种判断点与凸多边形位置关系的 方法，但那个约束条件是求解许多个不等式的并集，难以表达成一个光滑函数的 约束，在法一里面采用是因为对于一个顶点只对应一个变量，容易求解不等式的 并集。这里我们不采用这种方法，而是采用“面积法“ 。引入如下引理： 引理 3.1设 C 为凸多边形，顶点为 P1, ,Pn，平面上有一点 P，连接 P 与所有顶点，则 P / C（严格在 C 外部）与下列条件等价： i SPPiPi+1 SC.(3.9) 23 中国科学技术大学本科毕业论文 (a) 点在凸多边形内(b) 点在凸多边形外 图 3.11面积法判断点与多边形位置关系 注意引理中要求严格大于， 若我们采用内点惩罚函数法， 变量无法到达边界。 考虑到这一点，再考虑到计算误差，我们取一个很小的数 0，记 S0= SC+， 将式 (3.9) 转化为： i SPPiPi+1 S0.(3.10) 接下来我们需要计算每个 SPPiPi+1。注意到对于三角形 PPiPi+1来说，记 Pi= (xi,yi)，P = (s,t)，它的面积可以利用边向量的叉积计算： SPPiPi+1= 1 2| PPi PPi+1| = 1 2|(xi s)(yi+1 t) (yi t)(xi+1 s)| = 1 2|ais + bit + ci|. 再回来考虑我们的问题。设 v 为一变量顶点，其坐标为 (x,y,z)，它在平面 上的投影坐标记为 Proj(v) = (s,t) = (v ,v )。那么 v / C 等价于 SProj(v)PiPi+1= 1 2|ais + bit + ci| = 1 2|aix + biy + ciz + di| S0,i 1,2, ,n, (3.11) 其中 ai,bi,ci,di均为与 i 有关的常数。这是个可以被求导的约束函数，我们只需 要对所有的变量顶点，都加以式 (3.11) 的约束即可。 下面我们就采用法二的顶点移动方式与凸包约束条件。 24 中国科学技术大学本科毕业论文 3.3.3目标函数 我们利用了 3.3.2 法二的约束条件，已经可以保证点可以移动到不阻碍物体 运动的区域之外了。现在我们需要考虑的是如何选取目标函数， 来保证变形前后 物体的拓扑一致。一种简单的考虑是保点与点间的距离， 但是这样的目标函数非 线性程度很高。参考文献 5 中引入了一种简单的能量来代替保距离的能量，将 三角形的变形看成是四面体的变形，衡量四面体的变形从而衡量三角形的变形。 记变形区域三角面集合为 T0，对于任一三角形 f T0，f 的 3 个顶点记为 (v1v2v3)，引入 v4于 f 的重心加上单位外法向量的位置，变形后的 f顶点记为 (v1v2v3)，同样地，引入 v 4。然后我们将三角形的变形看成是四面体的变形，引 入四面体意义下的 f 到 f形变 Jacobi 矩阵 6，解释如图3.12： T = (v 1 v 4,v 2 v 4,v 3 v 4) (v1 v4,v2 v4,v3 v4) 1. (3.12) 一般情况下，T 并不是一个刚体变换，最接近它的刚体变换记为 R，R 可从 T 的 SVD 分解中提取出。将 T 进行分解，T = UV T，去掉 T 中缩放矩阵 ，则 R = UV T. 图 3.12对于形变矩阵 T 的解释。其中 R 是利用 SVD 分解从 T 中提取出的旋转 变换矩阵 5。 我们用如下度量来衡