{"id":1163,"date":"2021-10-03T20:42:59","date_gmt":"2021-10-03T12:42:59","guid":{"rendered":"https:\/\/www.caiqinyi.cn\/?p=1163"},"modified":"2022-01-30T22:28:21","modified_gmt":"2022-01-30T14:28:21","slug":"digital_geometry_processing_course_notes","status":"publish","type":"post","link":"https:\/\/www.caiqinyi.cn\/index.php\/2021\/10\/03\/digital_geometry_processing_course_notes\/","title":{"rendered":"\u6570\u5b57\u51e0\u4f55\u5904\u7406\u8bfe\u7a0b\u7b14\u8bb0(\u5df2\u5b8c\u7ed3)"},"content":{"rendered":"<p><script type=\"text\/javascript\" async src=\"https:\/\/www.caiqinyi.cn\/wp-content\/MathJax\/MathJax.js?config=TeX-AMS_CHTML\">\n<\/script><br \/>\n<script type=\"text\/x-mathjax-config\">\n    MathJax.Hub.Config({\n        tex2jax: {inlineMath: [['$','$']]},\n        TeX: {equationNumbers: {autoNumber: [\"AMS\"], useLabelIds: true}},\n        \"HTML-CSS\": {linebreaks: {automatic: true}},\n        SVG: {linebreaks: {automatic: true}}\n    });\n<\/script><\/p>\n<p>\u672c\u6587\u4e3b\u8981\u7528\u4e8e\u8bb0\u5f55\u5b66\u4e60\u5085\u5b5d\u660e\u8001\u5e08\u7684\u6570\u5b57\u51e0\u4f55\u5904\u7406\u8bfe\u7a0b\u65f6\u5bf9\u81ea\u5df1\u6709\u6240\u542f\u53d1\u7684\u7b14\u8bb0~<br \/>\n\u89c6\u9891\u94fe\u63a5: <a href=\"https:\/\/www.bilibili.com\/video\/BV1B54y1B7Uc?p=1\">\u6570\u5b57\u51e0\u4f55\u5904\u7406-\u4e2d\u56fd\u79d1\u5b66\u6280\u672f\u5927\u5b66-\u5085\u5b5d\u660e<\/a><\/p>\n<p><!--more--><\/p>\n\n<p>P1\u4e3b\u8981\u4ecb\u7ecd\u4e86\u4e00\u4e9b\u6570\u5b57\u51e0\u4f55\u5904\u7406\u76f8\u5173\u7684\u9884\u5907\u77e5\u8bc6, \u5982\u7f51\u683c, \u7f51\u683c\u62d3\u6251\u7b49\u7684\u6982\u5ff5, \u534a\u8fb9\u6570\u636e\u7ed3\u6784\u53ca\u5e38\u89c1\u7684\u7f51\u683c\u6587\u4ef6\u683c\u5f0f, \u5176\u5b9e\u81ea\u5df1\u672c\u6765\u4e5f\u6e05\u695a\u8fd9\u4e9b\u4e1c\u897f, \u6240\u4ee5P1\u5e72\u8d27\u4e0d\u591a, \u6545\u6b64\u5904\u4e0d\u518d\u8d58\u8ff0.<\/p>\n<h3>P2: Discrete differential geometry<\/h3>\n<p>\u975e\u5e38\u91cd\u8981\u7684\u4e00\u8282\u57fa\u7840\u8bfe.<\/p>\n<h4>2.1 Local Averaging Region<\/h4>\n<p>\u5b9a\u4e49\u4e86\u7f51\u683c\u4e0a\u4e00\u4e2a\u70b9\u7684\u90bb\u57df, \u4e3b\u8981\u5206\u4e3a\u4e09\u79cd: Barycentric Cell, Voronoi Cell\u4ee5\u53caMixed Voronoi Cell. \u5176\u4e2d, Voronoi Cell\u4e0d\u4e00\u5b9a\u90fd\u5904\u5728\u8be5\u70b9\u76841-Ring\u533a\u57df\u91cc. \u975e\u5e38\u91cd\u8981\u7684\u4e00\u4e2a\u6982\u5ff5, \u540e\u7eed\u5f88\u591a\u6982\u5ff5\u90fd\u4f1a\u5b9a\u4e49\u5728Local Averaging Region\u4e0a.<\/p>\n<h4>2.2 Normal<\/h4>\n<p>\u5b9a\u4e49\u4e86\u9876\u70b9\u7684Normal, \u5e76\u4e0d\u662f\u4e00\u4e2aWell-Defined\u7684\u6982\u5ff5, \u4f46\u5b9a\u4e49\u5728\u9762\u4e0a\u7684Normal\u662fWell-Defined\u7684.<\/p>\n<h4>2.3 Gradient<\/h4>\n<p>\u5b9a\u4e49\u5728\u4e09\u89d2\u5f62\u4e0a\u7684\u68af\u5ea6\u662f\u901a\u8fc7\u9876\u70b9\u4e0a\u7684\u68af\u5ea6\u63d2\u503c\u5f97\u5230\u7684(\u91cd\u5fc3\u5750\u6807), \u5bf9\u4e8e\u540c\u4e00\u4e2a\u4e09\u89d2\u5f62\u9762\u7247\u800c\u8a00, \u68af\u5ea6\u662f\u4e00\u4e2a\u5e38\u503c\u51fd\u6570. \u8be6\u7ec6\u63a8\u5bfc\u53ef\u53c2\u8003: <a href=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/2_Differential_Geometry.pdf\">2_Differential_Geometry<\/a><\/p>\n<h4>2.4 Laplace Operator<\/h4>\n<p>\u672c\u8d28\u4e0a\u662f\u5bf9\u9876\u70b9\u7684\u68af\u5ea6\u518d\u6c42\u4e00\u6b21\u68af\u5ea6, \u5bf9\u4e8e\u540c\u4e00\u4e2a\u4e09\u89d2\u5f62\u9762\u7247\u800c\u8a00, Laplace\u7b97\u5b50\u4f5c\u7528\u540e\u5f97\u5230\u7684\u7ed3\u679c\u59cb\u7ec8\u4e3a0. Laplace\u7b97\u5b50\u4e3b\u8981\u5206\u4e3aUniform Laplace\u7b97\u5b50(\u5bf9\u5e94\u7684\u77e9\u9635\u4e00\u822c\u662f\u5bf9\u79f0\u6b63\u5b9a\u7684) \u548cCot Laplace\u7b97\u5b50.<\/p>\n<h4>2.5 Curvature<\/h4>\n<p>\u4e3b\u8981\u5206\u4e3a\u5e73\u5747\u66f2\u7387\u4e0e\u9ad8\u65af\u66f2\u7387. \u5176\u4e2d, \u5e73\u5747\u66f2\u7387\u662f\u4e24\u4e2a\u4e3b\u66f2\u7387\u7684\u5e73\u5747\u503c, \u53ef\u7528Laplace\u7b97\u5b50\u8ba1\u7b97\u5f97\u5230; \u800c\u9ad8\u65af\u66f2\u7387\u5219\u662f\u4e24\u4e2a\u4e3b\u66f2\u7387\u7684\u4e58\u79ef, \u53ef\u901a\u8fc71-Ring\u533a\u57df\u91cc\u7684\u89d2\u5ea6\u8ba1\u7b97\u5f97\u5230. <\/p>\n<h3>P3: Mesh Smoothing(1)<\/h3>\n<p>\u4e4b\u524d\u5176\u5b9e\u5b66\u8fc7\u597d\u51e0\u6b21\u5085\u91cc\u53f6\u53d8\u6362\u4e86, \u4f46\u611f\u89c9\u603b\u662f\u5b66\u4e86\u5c31\u5fd8, \u5f52\u6839\u7ed3\u5e95\u662f\u7406\u89e3\u5f97\u4e0d\u591f\u900f\u5f7b. \u5b66\u4e86\u8fd9\u8282\u4ee5\u540e, \u611f\u89c9\u72b9\u5982\u918d\u9190\u704c\u9876, \u5bf9\u5085\u91cc\u53f6\u53d8\u6362\u7684\u7406\u89e3\u53c8\u52a0\u6df1\u4e86\u8bb8\u591a~ \u4ee51\u7ef4\u7684\u5085\u91cc\u53f6\u53d8\u6362\u4e3a\u4f8b: $$F(\\omega)=\\int_{-\\infty}^{+\\infty} f(x)e^{-2 \\pi i \\omega x}dx, \\quad (1)\\\\f(x)=\\int_{-\\infty}^{+\\infty} F(\\omega)e^{2 \\pi i \\omega x}d\\omega. \\quad (2)$$\u4e0a\u8ff0\u4e24\u5f0f\u5b9a\u4e49\u4e86\u51fd\u6570$f(x)$\u5728\u7a7a\u95f4\u57df\u4e0e\u9891\u57df\u4e4b\u95f4\u7684\u8f6c\u6362\u5173\u7cfb.<\/p>\n<p>\u5f53\u628a\u4e00\u4e2a\u51fd\u6570$f(x)$\u653e\u5230\u9891\u57df\u4e2d\u8fdb\u884c\u8ba8\u8bba\u65f6, \u672c\u8d28\u4e0a\u5c31\u662f\u628a$f(x)$\u7528\u53e6\u5916\u4e00\u7ec4\u57fa\u51fd\u6570\u8868\u793a, \u6bd4\u8f83\u7279\u522b\u7684\u5c31\u662f, \u8fd9\u91cc\u7684\u57fa\u51fd\u6570\u5f62\u5982$$g(x)=e_\\omega(x):=e^{2 \\pi i \\omega x}=cos(2 \\pi \\omega x) + isin(2 \\pi \\omega x),\\omega \\in R.$$\u56e0\u6b64, \u4ece\u5185\u79ef\u7684\u89d2\u5ea6\u6765\u770b, (1)\u5f0f\u6c42\u5f97\u7684\u7ed3\u679c\u5c31\u662f\u51fd\u6570$f(x)$\u5728\u4e00\u4e2a\u57fa\u51fd\u6570$g(x)$\u4e0a\u7684\u6295\u5f71\u957f\u5ea6. (<$f,g$>$=\\int_{-\\infty}^{+\\infty}f(x)\\overline{g(x)}dx$, \u6ce8\u610f, \u6b64\u5904\u9700\u8981\u5bf9$g(x)$\u505a\u4e00\u6b21\u5171\u8f6d\u8fd0\u7b97.)<\/p>\n<p>\u8fd9\u6837\u4e00\u6765, (2)\u5f0f\u5373\u4e3a\u51fd\u6570$f(x)$\u7528\u4e00\u7ec4\u57fa\u51fd\u6570$\\{g(x)\\}_\\omega$\u8868\u793a\u7684\u7ed3\u679c. \u6b64\u5916, \u4ece(2)\u5f0f\u7684\u89d2\u5ea6\u6765\u770b, \u4f4e\u901a\u6ee4\u6ce2\u4e0e\u9ad8\u901a\u6ee4\u6ce2\u672c\u8d28\u4e0a\u53ea\u662f\u6539\u53d8\u4e86(2)\u5f0f\u7684\u79ef\u5206\u4e0a\u4e0b\u9650\u7f62\u4e86.<\/p>\n<h3>P4: Mesh Smoothing(2)<\/h3>\n<p>Mesh Smoothing(\u53c8\u79f0Mesh Denoising) \u7684\u7b97\u6cd5\u4e3b\u8981\u5206\u4e3a\u4e09\u7c7b: Filter-Based\u7b97\u6cd5, \u672c\u8d28\u4e0a\u5c31\u662f\u4e00\u7c7b\u8fed\u4ee3\u7b97\u6cd5, \u4e00\u822c\u91c7\u7528Gauss\u2013Seidel\u8fed\u4ee3\u6216\u8005Jacobi\u8fed\u4ee3, Laplace Filtering\u7b97\u6cd5\u662f\u4e00\u79cd\u5e38\u89c1\u7684Filter-Based\u7b97\u6cd5, \u88ab\u6ee4\u6ce2\u4f5c\u7528\u7684\u4fe1\u53f7\u4e0d\u4e00\u5b9a\u662f\u9876\u70b9\u4f4d\u7f6e, \u4e5f\u53ef\u4ee5\u5148\u628a\u6ee4\u6ce2\u4f5c\u7528\u5230Normal\u4e0a, \u7136\u540e\u518d\u901a\u8fc7\u7ecf\u6ee4\u6ce2\u4f5c\u7528\u540e\u7684Normal\u91cd\u65b0\u79fb\u52a8\u7f51\u683c\u9876\u70b9; Optimization-Based\u7b97\u6cd5, \u6839\u636e\u95ee\u9898\u80cc\u666f\u63d0\u51fa\u80fd\u91cf\u51fd\u6570, \u53ef\u4ee5\u91c7\u7528\u4ea4\u66ff\u4f18\u5316\u7684\u4f18\u5316\u7b97\u6cd5(ADMM) \u6765\u6c42\u89e3\u80fd\u91cf\u51fd\u6570\u7684\u6781\u5c0f\u503c; Data-Driven-Based\u7b97\u6cd5, \u6bd4\u5982\u6211\u4eec\u53ef\u4ee5\u62df\u5408\u4e00\u4e2a\u51fd\u6570, \u901a\u8fc7\u8fd9\u4e2a\u51fd\u6570\u6211\u4eec\u53ef\u4ee5\u63d0\u53d6\u51fa\u4e00\u4e2a\u7f51\u683c\u7684\u6cd5\u5411(Ground-Truth), \u7136\u540e\u518d\u6839\u636e\u6cd5\u5411\u91cd\u65b0\u79fb\u52a8\u7f51\u683c\u9876\u70b9\u8fbe\u5230\u53bb\u566a\u7684\u76ee\u7684.<\/p>\n<h3>P5: Mesh Parameterizations<\/h3>\n<p>\u53c8\u79f0Flattening\u6216\u8005Unfolding, \u672c\u8d28\u4e0a\u5c31\u662f\u4e00\u4e2a\u6620\u5c04, \u4e3b\u8981\u5206\u4e3aFlip-Free, Locally Bijective\u548cBijective\u4e09\u79cd, \u5176\u6761\u4ef6\u7684\u4e25\u683c\u7a0b\u5ea6\u662f\u4ece\u524d\u5f80\u540e\u5c42\u5c42\u9012\u8fdb\u7684. \u5176\u4e2d, Flip-Free\u7684\u53c2\u6570\u5316\u7b97\u6cd5\u4ec5\u8981\u6c42\u5f97\u5230\u7684\u4e09\u89d2\u7f51\u683c\u6ca1\u6709\u7ffb\u8f6c\u7684\u4e09\u89d2\u5f62; Locally Bijective\u7684\u53c2\u6570\u5316\u7b97\u6cd5\u4e0d\u4ec5\u4ec5\u8981\u6c42\u6ca1\u6709\u7ffb\u8f6c\u7684\u4e09\u89d2\u5f62, \u8fd8\u8981\u6c42\u5bf9\u4e8e\u539f\u59cb\u7f51\u683c\u7684\u8fb9\u754c\u70b9\u800c\u8a00, \u51761-Ring\u533a\u57df\u6620\u5c04\u52302D\u5e73\u9762\u4e0a\u4ee5\u540e\u65e0\u76f8\u4ea4\u7684\u8fb9\u754c\u8fb9; Bijective\u7684\u53c2\u6570\u5316\u7b97\u6cd5\u5219\u8981\u6c42\u6700\u4e3a\u4e25\u683c, \u76f4\u89c2\u4e0a\u53ef\u4ee5\u7406\u89e3\u4e3aBijective = Flip-Free + Locally Bijective, \u8981\u6c42\u539f\u59cb\u7f51\u683c\u4e0a\u7684\u6bcf\u4e2a\u70b9\u90fd\u548c\u53c2\u6570\u5316\u540e\u5f97\u5230\u7684\u7f51\u683c\u4e0a\u7684\u6bcf\u4e00\u4e2a\u70b9\u5b58\u5728\u53cc\u5c04. \u53c2\u6570\u5316\u662f\u4e00\u4e2a\u975e\u5e38\u57fa\u7840\u7684\u56fe\u5f62\u5b66\u5de5\u5177, \u5e94\u7528\u975e\u5e38\u5e7f\u6cdb, \u5982Texture Mapping, Normal Map, Remeshing, suface mapping, Mesh Generation\u7b49. <\/p>\n<p>P5\u8fd8\u4ecb\u7ecd\u4e86\u4e09\u7c7b\u5e38\u7528\u7684\u53c2\u6570\u5316\u7b97\u6cd5, \u5206\u522b\u662fTutte&#8217;s Barycentric Mapping, Least Squares Conformal Maps(LSCM, ASAP) \u4ee5\u53caAngel-Based Flattening(ABF).<br \/>\n$\\cdot$ Tutte&#8217;s Barycentric Mapping\u80fd\u591f\u4ece\u7406\u8bba\u4e0a\u4fdd\u8bc1\u53c2\u6570\u5316\u7ed3\u679c\u662fBijective\u7684, \u7b97\u6cd5\u7684\u4e3b\u8981\u601d\u8def\u662f\u5148\u628a\u8fb9\u754c\u70b9\u6620\u5c04\u5230\u4e00\u4e2a\u51f8\u591a\u8fb9\u5f62\u7684\u8fb9\u754c\u4e0a, \u7136\u540e\u5185\u90e8\u70b9\u662f\u5176\u90bb\u5c45\u70b9\u7684\u51f8\u7ec4\u5408, \u8fd9\u6837\u4fbf\u53ef\u4ee5\u901a\u8fc7\u6c42\u89e3\u4e00\u4e2a\u7ebf\u6027\u7cfb\u7edf\u6765\u5b9e\u73b0Bijective\u7684\u53c2\u6570\u5316, \u7136\u800c\u5b9e\u9645\u4e0a\u7531\u4e8e\u6570\u503c\u7cbe\u5ea6\u7684\u5f71\u54cd, \u7b97\u6cd5\u7ed3\u679c\u5bb9\u6613\u51fa\u73b0\u9000\u5316\u7684\u4e09\u89d2\u5f62.<br \/>\n$\\cdot$ LSCM\u5b9a\u4e49\u4e86\u4e00\u4e2a\u80fd\u91cf\u51fd\u6570, \u8be5\u80fd\u91cf\u51fd\u6570\u63cf\u8ff0\u4e86\u5f53\u524d\u7f51\u683c\u6bcf\u4e2a\u4e09\u89d2\u9762\u7247\u4e0a\u7684Jacobi\u77e9\u9635(2$\\times$2)\u4e0e\u76ee\u6807Jacobi\u77e9\u9635\u7684\u8ddd\u79bb, \u80fd\u91cf\u51fd\u6570\u7684\u6781\u5c0f\u503c\u53ef\u4ee5\u901a\u8fc7\u6c42\u89e3\u6cd5\u65b9\u7a0b\u5f97\u5230, \u4e3a\u4e86\u907f\u514d\u5e73\u51e1\u89e3, \u901a\u5e38\u9700\u8981\u56fa\u5b9a\u81f3\u5c11\u4e24\u4e2a\u70b9, \u800c\u8fd9\u4e24\u4e2a\u70b9\u7684\u9009\u53d6\u5bf9\u53c2\u6570\u5316\u7ed3\u679c\u5177\u6709\u4e00\u5b9a\u7684\u5f71\u54cd, \u8fd9\u662f\u6211\u4e0d\u5927\u770b\u597dLSCM\u7684\u539f\u56e0\u4e4b\u4e00.<br \/>\n$\\cdot$ ABF\u5219\u662f\u4ece\u89d2\u5ea6\u51fa\u53d1, \u4f7f\u5f97\u53c2\u6570\u5316\u7ed3\u679c\u7684\u6bcf\u4e2a\u4e09\u89d2\u9762\u7247\u7684\u89d2\u5ea6\u90fd\u6ee1\u8db3\u4e00\u5b9a\u7684\u6761\u4ef6, \u6700\u540e\u518d\u6839\u636e\u5f97\u5230\u7684\u89d2\u5ea6\u91cd\u65b0\u79fb\u52a8\u7f51\u683c\u9876\u70b9, \u8be5\u7b97\u6cd5\u4e5f\u5bb9\u6613\u53d7\u5230\u6570\u503c\u7cbe\u5ea6\u7684\u5f71\u54cd, \u5bfc\u81f4\u5728\u7b97\u6cd5\u8fed\u4ee3\u540e\u671f\u4f1a\u51fa\u73b0\u4e09\u89d2\u9762\u7247\u4e0d\u4e0a\u7684\u60c5\u51b5, \u56e0\u6b64\u4e3a\u4e86\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898, \u540e\u9762\u4e5f\u6709\u5b66\u8005\u5728ABF\u57fa\u7840\u4e4b\u4e0a\u901a\u8fc7\u4f18\u5316\u80fd\u91cf\u51fd\u6570\u7684\u624b\u6bb5\u89c4\u907f\u4e09\u89d2\u9762\u7247\u62fc\u63a5\u4e0d\u4e0a\u7684\u95ee\u9898.<\/p>\n<h3>P6: Mesh Parameterizations\u4e0eMesh Deformation<\/h3>\n<h4>6.1 Mesh Parameterizations<\/h4>\n<p>Mesh Parameterizations\u4e3b\u8981\u5206\u4e3a\u4e09\u7c7b, \u5206\u522b\u662fIsometric Mapping(\u65cb\u8f6c+\u5e73\u79fb), Conformal Mapping(\u76f8\u4f3c\u6027+\u5e73\u79fb), Area-Perserving Mapping(\u4fdd\u9762\u79ef+\u5e73\u79fb), \u5176\u4e2d, Conformal+Area-Perserving Mapping$\\Leftrightarrow$Isometric.<\/p>\n<p>\u5728\u5bf9\u539f\u59cb\u7f51\u683c\u7684\u6bcf\u4e2a\u4e09\u89d2\u9762\u7247\u5efa\u7acb\u5c40\u90e8\u5750\u6807\u7cfb\u4ee5\u540e, \u6211\u4eec\u53ef\u4ee5\u4eceJacobi\u77e9\u9635$J_t$\u53ca\u5176\u5947\u5f02\u503c$\\sigma_1, \\sigma_2$\u7684\u89d2\u5ea6\u6765\u533a\u5206\u4e0a\u8ff0\u4e09\u79cdMesh Deformation\u7684\u65b9\u5f0f.<br \/>\n$\\cdot$ Isometric Mapping, $J_t$\u662f\u4e00\u4e2a\u65cb\u8f6c\u77e9\u9635, $\\sigma_1=\\sigma_2=1$.<br \/>\n$\\cdot$ Conformal Mapping, $J_t$\u662f\u4e00\u4e2a\u76f8\u4f3c\u77e9\u9635, $\\sigma_1=\\sigma_2$.<br \/>\n$\\cdot$ Area-Preserving Mapping, $detJ_t=1$, $\\sigma_1 \\sigma_2=1$.<\/p>\n<p>\u8fd9\u6837\u4e00\u6765, \u53c2\u6570\u5316\u4fbf\u53ef\u4ee5\u91c7\u7528LSCM\u7684\u601d\u8def\u53bb\u505a, \u53ef\u4ee5\u6784\u9020\u51fa\u4e0b\u8ff0\u80fd\u91cf\u51fd\u6570:$$E(u,L)=\\sum_{t}A_t||J_t-L_t||^2_F,$$\u5176\u4e2d$L_t$\u4e3a\u76ee\u6807Transform\u77e9\u9635, \u5f53\u8981\u6c42Isometric Mapping\u65f6, $L_t$\u4e3a\u4e00\u4e2a\u65cb\u8f6c\u77e9\u9635; \u800c\u5f53\u8981\u6c42Conformal Mapping\u65f6, $L_t$\u5219\u4e3a\u4e00\u4e2a\u76f8\u4f3c\u77e9\u9635.<\/p>\n<h4>6.2 Mesh Deformation<\/h4>\n<p>\u901a\u5e38\u4f1a\u5728Mesh Deformation\u7684\u8fc7\u7a0b\u5f53\u4e2d\u628a\u4e00\u4e2a\u7f51\u683c\u5206\u4e3a\u4e09\u4e2a\u533a\u57df, \u5206\u522b\u662fFixed\u533a\u57df(\u56fa\u5b9a\u4e0d\u52a8\u7684\u533a\u57df), Handled\u533a\u57df(\u7528\u6237\u76f4\u63a5\u64cd\u4f5c\u7684\u533a\u57df) \u4e0eFree\u533a\u57df(\u53d7Handled\u533a\u57df\u5f71\u54cd), \u5b83\u4eec\u7684\u533a\u522b\u4e3b\u8981\u662f\u5185\u90e8\u9876\u70b9\u7684\u4f4d\u79fb\u91cf.<\/p>\n<h3>P7: Mesh Deformation<\/h3>\n<h4>7.1 Transformation Propagation\u4e0eMulti-Scale Deformation<\/h4>\n<p>\u7f51\u683c\u53d8\u5f62\u4e00\u822c\u4e0d\u6539\u53d8\u9876\u70b9\u4e4b\u95f4\u7684\u8fde\u63a5\u5173\u7cfb, \u4ec5\u6539\u53d8\u9876\u70b9\u7684\u4f4d\u7f6e. \u76ee\u524d\u4e3b\u8981\u6709\u4e24\u7c7b\u53d8\u5f62\u7b97\u6cd5: Transformation Propagation\u4e0eMulti-Scale Deformation. \u5176\u4e2d, Multi-Scale Deformation\u662f\u628a\u4e00\u4e2a\u7f51\u683c\u901a\u8fc7Encode\u7684\u64cd\u4f5c\u5206\u89e3\u6210\u4f4e\u9891\u90e8\u5206(Base Mesh) \u4e0e\u9ad8\u9891\u90e8\u5206(Detail), \u7136\u540e\u5728\u5bf9\u4f4e\u9891\u90e8\u5206\u53d8\u5f62\u4ee5\u540e, \u628a\u9ad8\u9891\u90e8\u5206\u52a0\u56de\u6765, \u4ece\u800c\u8fbe\u5230\u4e00\u4e2a\u4fdd\u7ec6\u8282\u7684\u6548\u679c.<\/p>\n<h4>7.2 Differential Coordinates<\/h4>\n<p>\u76f8\u6bd4\u8f83Transformation Propagation\u4e0eMulti-Scale Deformation\u800c\u8a00, Differential Coordinates\u66f4\u4fa7\u91cd\u4e8e\u5bf9\u9876\u70b9\u7684\u68af\u5ea6\u6216\u8005Laplace\u7b97\u5b50\u8fdb\u884c\u53d8\u5f62.<\/p>\n<h4>7.3 Deformation Transfer<\/h4>\n<p>\u5373\u628a\u4e00\u4e2a\u7f51\u683c\u7684\u53d8\u5f62\u64cd\u4f5c\u8fc1\u79fb\u5230\u53e6\u5916\u4e00\u4e2a\u7f51\u683c\u4e0a, \u672c\u8d28\u4e0a\u662f\u628a\u53d8\u5f62\u64cd\u4f5cEncode\u6210\u4e00\u7cfb\u5217\u7684\u4eff\u5c04\u53d8\u6362, \u9700\u8981\u5148\u627e\u51fa\u8fd9\u4e24\u4e2a\u7f51\u683c\u7684\u4e00\u4e00\u5bf9\u5e94\u5173\u7cfb.<\/p>\n<h4>7.4 As-Rigid-As-Possible Surface Deformation<\/h4>\n<p>\u672c\u8d28\u4e0a\u5b9a\u4e49\u4e86\u4e00\u4e2a\u80fd\u91cf\u51fd\u6570, \u8be5\u80fd\u91cf\u51fd\u6570\u8861\u91cf\u4e86\u53d8\u5f62\u524d\u540e\u7f51\u683c\u8fb9\u957f\u7684\u53d8\u5316\u91cf. \u5728\u8be5\u6846\u67b6\u4e0b, \u82e5\u53d8\u5f62\u524d\u540e\u540c\u4e00\u6761\u8fb9\u4ec5\u76f8\u5dee\u4e00\u4e2a\u65cb\u8f6c\u53d8\u6362, \u5219\u8ba4\u4e3a\u8be5\u8fb9\u7684\u53d8\u5316\u91cf\u6781\u5c0f. \u8be5\u80fd\u91cf\u51fd\u6570\u542b\u6709\u4e24\u4e2a\u53d8\u91cf, \u5206\u522b\u662f\u9876\u70b9\u4f4d\u7f6e\u4e0e\u65cb\u8f6c\u77e9\u9635, \u56e0\u6b64\u4e00\u822c\u91c7\u7528\u4ea4\u66ff\u4f18\u5316\u7684\u65b9\u6cd5.<\/p>\n<h3>P8: Freedom Deformation\u4e0eGeneralized Barycentric Coordinates<\/h3>\n<h4>8.1 Freedom Deformation(Space Deformation)<\/h4>\n<p>\u5373\u5bf9\u6574\u4e2a\u7a7a\u95f4\u8fdb\u884c\u53d8\u5f62, \u4ece\u800c\u95f4\u63a5\u5bf9\u5185\u542b\u6a21\u578b\u8fdb\u884c\u53d8\u5f62, \u5176\u5b9e\u548c\u6837\u6761\u7684\u601d\u60f3\u5f88\u63a5\u8fd1.<\/p>\n<h4>8.2 Generalized Barycentric Coordinates<\/h4>\n<p>\u4efb\u610f\u51fd\u6570$\\phi_i:P \\to R, i=1,\\cdots,n$\u88ab\u79f0\u4e3a\u5e7f\u4e49\u91cd\u5fc3\u5750\u6807, \u82e5$\\forall x \\in P,$$\\phi_i(x) \\ge 0, i=1,\\cdots,n$, \u4e14$$\\sum_{i=1}^{n} \\phi_i(x)=1,\\sum_{i=1}^{n} \\phi_i(x)v_i=x.$$\u5e7f\u4e49\u91cd\u5fc3\u5750\u6807\u8fd8\u5177\u5907\u5f88\u591a\u6027\u8d28, \u5982\u62c9\u683c\u6717\u65e5\u6027\u7b49.<\/p>\n<h3>P9: Mean Value Coordinates\u4e0eMesh Deformation<\/h3>\n<h4>9.1 Mean Value Coordinates(MVC)<\/h4>\n<p>\u63d0\u51faMVC\u7684\u76ee\u7684\u662f\u4e3a\u4e86\u903c\u8fd1\u4e00\u4e2a\u6ee1\u8db3\u72c4\u5229\u514b\u96f7\u8fb9\u754c\u6761\u4ef6$u|_{\\partial \\Omega}=u_0$\u7684\u8c03\u548c\u51fd\u6570$u$($u_{xx}+u_{yy}=0$, \u5373\u7ecfLaplace\u7b97\u5b50\u4f5c\u7528\u540e\u4e3a0, $Lu=0$.), \u901a\u5e38\u662f\u5229\u7528\u5b9a\u4e49\u5728$\\Omega$\u7684\u4e09\u89d2\u5256\u5206$T$\u4e0a\u7684\u5206\u7247\u7ebf\u6027\u51fd\u6570\u8fdb\u884c\u903c\u8fd1, \u5176\u7406\u8bba\u57fa\u7840\u662f\u5e73\u5747\u503c\u5b9a\u7406(Mean Value Theorem):$$u(v_0)=\\frac{1}{2\\pi r} \\int_{\\Gamma}u(v)ds.$$\u6839\u636e\u5e73\u5747\u503c\u5b9a\u7406, \u6211\u4eec\u53ef\u4ee5\u5f97\u5230\u8c03\u548c\u51fd\u6570$u$\u5728$\\Omega$\u7684\u4e09\u89d2\u5256\u5206$T$\u4e0a\u7684\u903c\u8fd1\u51fd\u6570$u_T$\u7684\u8868\u8fbe\u5f0f$$u_T(v_0)=\\sum_{i=1}^n\\phi_iu_T(v_i)$$\u5176\u4e2d$\\phi_i$\u662f\u4e0e\u89d2\u5ea6$\\alpha_i$\u76f8\u5173\u7684\u57fa\u51fd\u6570. \u8fd9\u6837\u4e00\u6765, \u6211\u4eec\u4fbf\u53ef\u4ee5\u6c42\u51fa\u903c\u8fd1\u51fd\u6570$u_T$\u5728\u7f51\u683c\u4e0a\u6bcf\u4e2a\u9876\u70b9\u7684\u503c, \u4ece\u800c\u5f97\u5230\u8c03\u548c\u51fd\u6570$u$\u7684\u6570\u503c\u903c\u8fd1\u8868\u8fbe\u5f0f(\u975e\u89e3\u6790\u8868\u8fbe\u5f0f). \u9700\u8981\u6ce8\u610f\u7684\u662f, \u6ee1\u8db3\u5e73\u5747\u503c\u5b9a\u7406\u7684\u51fd\u6570\u4e0d\u4e00\u5b9a\u662f\u8c03\u548c\u51fd\u6570.<\/p>\n<h4>9.2 Mesh Deformation<\/h4>\n<p>\u4e3b\u8981\u8bb2\u4e86\u4e09\u79cdDeformation\u7684\u65b9\u5f0f, \u5206\u522b\u662fHanded-Based Deformation, Cage-Based Deformation(\u601d\u60f3\u7c7b\u4f3c\u6837\u6761) \u4e0eSkeleton-Based Deformation(\u611f\u89c9\u4e3b\u8981\u5e94\u7528\u4e8e\u9aa8\u9abc\u52a8\u753b). \u8fd9\u4e09\u79cd\u65b9\u5f0f\u90fd\u5177\u6709\u5c40\u90e8\u7f16\u8f91\u7684\u7279\u70b9, \u5373\u5c40\u90e8\u7684\u7f16\u8f91\u5e76\u4e0d\u4f1a\u5f71\u54cd\u5230\u5168\u5c40\u7684\u6bcf\u4e2a\u70b9.<\/p>\n<h3>P10: Repairing<\/h3>\n<p>\u8fd9\u8282\u8bfe\u4ecb\u7ecd\u7684Mesh Repairing\u95ee\u9898\u66f4\u591a\u7684\u662f\u4e00\u4e2a\u5de5\u7a0b\u95ee\u9898, \u6240\u4ee5\u672c\u8282\u8bfe\u57fa\u672c\u6ca1\u6709\u4ecb\u7ecd\u7b97\u6cd5, \u4e3b\u8981\u4ecb\u7ecd\u4e86\u7f51\u683c\u7684\u5404\u79cd\u5e38\u89c1Artifact, \u5305\u62ecIsolated Vertices and Dangling Edges(\u5b64\u7acb\u70b9\u548c\u60ac\u6302\u8fb9), Singular Edges(\u6216\u79f0\u4e3aComplex Edges, nonmanifold Edges), Singular Vertices, Topological Noise, Orientation(\u9762\u7684\u671d\u5411), Surface Holes, Gaps, Degenerate Elements(\u9000\u5316\u7684\u4e09\u89d2\u5f62), Self-Interactions(\u6216Overlap), Sharp Feature Chamfering(Feature\u4e22\u5931) \u4e0eData Noise\u7b49. \u8fd9\u4e9b\u5b58\u5728\u95ee\u9898\u7684\u7f51\u683c\u6765\u6e90\u4e3b\u8981\u6709\u4e24\u4e2a, \u5206\u522b\u662fCAD\u9886\u57df\u6216\u8005FEM(Finite Element Method, \u6709\u9650\u5143\u65b9\u6cd5) \u4f7f\u7528NURPS(\u975e\u5747\u5300\u6709\u7406B\u6837\u6761) \u8bbe\u8ba1\u66f2\u9762\u4e0e\u4f7f\u75283D\u626b\u63cf\u4eea\u626b\u63cf3D\u5b9e\u4f53.<\/p>\n<p>\u5176\u4e2d, \u6211\u6700\u611f\u5174\u8da3\u7684\u4e00\u4e2aArtifact\u662fTopological Noise. \u5b83\u4e3b\u8981\u662f\u6307\u7f51\u683c\u7684\u4e8f\u683c\u6570\u91cf\u5f02\u5e38, \u76f8\u6bd4\u8f83Ground-Truth\u589e\u52a0\u4e86\u8bb8\u591a\u5c0f\u7684Handle\u6216\u8005Tunnel. \u8fd9\u6837\u4e00\u79cdArtifact\u4f1a\u5f71\u54cd\u5230\u4e00\u4e9b\u9700\u8981\u62d3\u6251\u7406\u8bba\u4fdd\u8bc1\u7684\u7b97\u6cd5\u7ed3\u679c, \u5982\u7403\u9762\u53c2\u6570\u5316\u7b97\u6cd5\u7684\u8f93\u51fa, \u8be5\u7b97\u6cd5\u4e00\u822c\u8981\u6c42\u8f93\u5165\u7684\u7f51\u683c\u80fd\u591f\u4e0e\u7403\u9762$S^2$\u540c\u80da(\u4e8f\u683c\u4e3a0).<\/p>\n<h3>P11: Mesh Repairing\u4e0eMappings<\/h3>\n<p>\u8fd9\u8282\u8bfe\u8bf4\u5b9e\u8bdd, \u4e2a\u4eba\u611f\u89c9\u6ca1\u4ec0\u4e48\u5e72\u8d27, \u8001\u5e08\u8fd8\u662f\u4e0d\u65ad\u5730\u5728\u5f3a\u8c03Mesh Repairing\u7684\u91cd\u8981\u6027, \u867d\u7136\u662f\u4e2a\u504f\u5de5\u7a0b\u7684\u90e8\u5206, \u4f46\u79c1\u4ee5\u4e3a\u8fd9\u79cd\u8bb2\u8bfe\u65b9\u5f0f\u8fd8\u662f\u592a\u5570\u55e6\u4e86\u70b9. <\/p>\n<h4>11.1 Mesh Repairing<\/h4>\n<p>\u672c\u8282\u91cd\u70b9\u4ecb\u7ecd\u4e86\u8f93\u5165\u7f51\u683c\u7684\u7c7b\u578b.<br \/>\n$\\cdot$ Registered Range Scans, \u5373Patch\u7684\u96c6\u5408, \u8fd9\u4e9bPatch\u5747\u5904\u4e8e\u540c\u4e00\u4e2a\u5750\u6807\u7cfb\u4e0b, \u4e14\u5747\u8868\u793a\u4e00\u4e2a\u626b\u63cf\u7269\u4f53\u7684\u66f2\u9762$S$\u7684\u4e00\u90e8\u5206, \u5b83\u4eec\u4e4b\u95f4\u53ef\u80fd\u5b58\u5728Overlaps;<br \/>\n$\\cdot$ Fused Range Scans, \u662f\u6307\u4e00\u79cd\u5e26\u8fb9\u754c\u7684\u6d41\u5f62\u7f51\u683c, \u901a\u5e38\u542b\u6709Gaps, Holes\u6216\u8005Islands, \u4e2a\u4eba\u7684\u7406\u89e3\u662fFused Range Scans\u662f\u5728Registered Range Scans\u7684\u57fa\u7840\u4e4b\u4e0a\u878d\u5408\u4e86\u76f8\u4e92\u91cd\u53e0\u7684\u90e8\u5206\u5f97\u5230\u7684;<br \/>\n$\\cdot$ Triangle Soups, \u5373\u4e00\u79cd\u4e09\u89d2\u7f51\u683c, \u4f46\u8fd9\u79cd\u4e09\u89d2\u7f51\u683c\u7684\u4e09\u89d2\u5f62\u4e4b\u95f4\u4ec5\u5b58\u5728\u8f83\u5f31\u7684\u8fde\u63a5\u5173\u7cfb;<br \/>\n$\\cdot$ Triangulated NURBS Patches, \u5373\u8fde\u901a\u7684\u4e09\u89d2\u7f51\u683c\u7684Patch\u7684\u96c6\u5408, \u8fd9\u4e9bPatch\u7684\u8fb9\u754c\u4e4b\u95f4\u53ef\u80fd\u5b58\u5728Gaps\u6216\u8005\u8f83\u5c0f\u7684Overlaps;<br \/>\n$\\cdot$ Contoured Meshes, \u5373\u901a\u5e38\u7531Marching Cubes, Dual Contouring\u6216\u8005\u5176\u5b83\u591a\u8fb9\u5f62\u7f51\u683c\u63d0\u53d6\u7b97\u6cd5\u5728\u4e00\u4e2a\u4f53\u7d20\u6570\u636e\u96c6\u4e0a, \u5982SDF\u7ed3\u679c, \u63d0\u53d6\u5f97\u5230\u7684\u4e00\u4e2a\u4e09\u89d2\u7f51\u683c, \u4f46\u8fd9\u79cd\u7f51\u683c\u901a\u5e38\u5305\u542b\u4e00\u4e9bTopological Artifacts, \u5982\u591a\u4f59\u7684Handles;<br \/>\n$\\cdot$ Badly Meshed  Manifolds, \u5373\u542b\u6709\u9000\u5316\u4e09\u89d2\u5f62\u7684\u7f51\u683c, \u5305\u62ec\u9762\u79ef\u4e3a0\u7684\u4e09\u89d2\u5f62, \u542b\u6709Caps\u7684\u4e09\u89d2\u5f62(\u5176\u4e2d\u4e00\u4e2a\u5185\u89d2\u63a5\u8fd1$\\pi$), \u542b\u6709Needles\u7684\u4e09\u89d2\u5f62(\u5176\u4e2d\u4e00\u6761\u8fb9\u957f\u63a5\u8fd10) \u4e0e\u7ffb\u8f6c\u7684\u4e09\u89d2\u5f62<strong>(\u5176\u6cd5\u5411\u4e0e\u76f8\u90bb\u9762\u7684\u6cd5\u5411\u5939\u89d2\u63a5\u8fd1$\\pi$)<\/strong>.<\/p>\n<p>\u63a5\u4e0b\u6765\u7b80\u8981\u4ecb\u7ecd\u4e86\u51e0\u79cdMesh Repairing\u7684\u7b97\u6cd5.<br \/>\n$\\cdot$ Surface-Oriented Algorithms, \u8fd9\u79cd\u7b97\u6cd5\u76f4\u63a5\u5bf9\u8f93\u5165\u6570\u636e\u8fdb\u884c\u64cd\u4f5c, \u4f46\u53ea\u5bf9\u7f51\u683c\u8fdb\u884c\u5c40\u90e8\u7684\u4fee\u8865, \u56e0\u6b64\u4ec5\u9002\u7528\u4e8e\u4ec5\u542b\u6709\u4e00\u4e9b\u5c40\u90e8Artifact\u7684Mesh Repairing, \u5982Gaps, Holes\u6216\u8005Intersections;<br \/>\n$\\cdot$ Consistent Normal Orientation, \u8fd9\u79cd\u7b97\u6cd5\u4ec5\u9488\u5bf9\u7f51\u683c\u7684\u671d\u5411\u95ee\u9898\u8fdb\u884c\u4fee\u590d, \u4e00\u4e2a\u5e38\u89c1\u7684\u5b9e\u73b0\u601d\u8def\u4fbf\u662f\u4ece\u4e00\u4e2a\u4e09\u89d2\u5f62\u5f00\u59cb\u5904\u7406, \u5224\u65ad\u5176\u6cd5\u5411\u4e0e\u76f8\u90bb\u9762\u7684\u6cd5\u5411\u5939\u89d2\u662f\u5426\u63a5\u8fd1$\\pi$, \u82e5\u63a5\u8fd1$\\pi$\u5219\u53cd\u8f6c\u5176\u6cd5\u5411, \u4e00\u8def\u4f20\u64ad\u4e0b\u53bb, \u4f46\u6211\u4e0d\u6e05\u695a\u8fd9\u79cd\u7b97\u6cd5\u6700\u540e\u662f\u5426\u80fd\u591f\u6536\u655b?<br \/>\n$\\cdot$ Surface-Based Hold Filling, \u5c3d\u53ef\u80fd\u5730\u91c7\u7528\u5149\u6ed1\u7684Patch\u586b\u8865\u6d1e;<br \/>\n$\\cdot$ Conversion to Manifolds, \u76ee\u6807\u662f\u53bb\u9664Singular Edges\u6216\u8005Singular Vertices, \u6700\u5e38\u89c1\u7684\u601d\u8def\u4fbf\u662f\u6cbf\u7740Complex Edges\u5207\u5f00, \u611f\u89c9\u975e\u5e38\u5730\u7b80\u5355\u7c97\u66b4;<br \/>\n$\\cdot$ Gap Closing, \u76f4\u63a5\u8865\u4e0aGap\u4e0d\u96be, \u96be\u70b9\u4e3b\u8981\u662f\u8865\u4e0aGap\u4ee5\u540e\u53ef\u80fd\u4f1a\u4f7f\u5f97\u7f51\u683c\u53d1\u751f\u7578\u53d8;<br \/>\n$\\cdot$ Topology Simplification, \u76ee\u6807\u662f\u5bf9Handles\u8fdb\u884c\u586b\u8865, \u6700\u5e38\u89c1\u7684\u601d\u8def\u662f\u68c0\u6d4b\u5230Handle\u4ee5\u540e\u6cbf\u7740Handle\u5207\u5f00, \u4ece\u800c\u8f6c\u5316\u4e3a\u4e24\u4e2a\u5206\u79bb\u7f51\u683c\u7684Hole Filling\u95ee\u9898;<br \/>\n$\\cdot$ Volumetric Algorithms, \u76ee\u6807\u662f\u5f97\u5230\u8f93\u5165\u7f51\u683c\u7684\u4f53\u7d20\u8868\u8fbe, \u5982Regular Cartesian Grids, Adaptive Octrees, KD-Trees, BSP-Trees\u4e0eDelaunay Triangulations. \u800c\u5f97\u5230\u7684\u4f53\u7d20\u8868\u8fbe\u901a\u5e38\u5df2\u7ecf\u53bb\u9664\u4e86\u539f\u7f51\u683c\u7684\u8bb8\u591aArtifact, \u5305\u62ecIntersections, Holes, Gaps, Overlaps, Inconsistent Normal Orientations, Singular Edges\u4e0eSingular Vertices. \u4f46\u4f53\u7d20\u8868\u8fbe\u4e5f\u4f1a\u5e26\u6765\u8bb8\u591a\u95ee\u9898, \u5305\u62ecHandles, \u7834\u574f\u8f93\u5165\u7f51\u683c\u7684\u8fde\u63a5\u5173\u7cfb\u4ee5\u53ca\u5185\u5b58\u95ee\u9898.<br \/>\n$\\cdot$ Volumetric Repair on Adaptive Grids, \u7b97\u6cd5\u4e3b\u8981\u5206\u4e3a\u4e09\u6b65: 1. \u521b\u5efa\u7f51\u683c\u7684\u81ea\u9002\u5e94\u516b\u53c9\u6811\u8868\u8fbe. 2. \u6267\u884c\u5f62\u6001\u5b66\u64cd\u4f5c. 3. \u4ece\u81ea\u9002\u5e94\u516b\u53c9\u6811\u8868\u8fbe\u4e2d\u63d0\u53d6\u51fa\u7f51\u683c.<\/p>\n<h4>11.2 Mappings<\/h4>\n<p>\u4e3b\u8981\u662f\u5f00\u4e86\u4e2a\u5934, \u4e3b\u8981\u5185\u5bb9\u5e94\u8be5\u8fd8\u662f\u653e\u5728P12\u4e2d\u4ecb\u7ecd. \u4ece\u6570\u5b66\u672c\u8d28\u4e0a\u6765\u770b, \u56fe\u5f62\u5b66\u7684\u7b97\u6cd5\u57fa\u672c\u90fd\u662f\u5728\u5bfb\u627e\u6ee1\u8db3\u8981\u6c42\u7684Mapping(\u65e0\u8bba\u662f\u7f51\u683c\u53c2\u6570\u5316\u8fd8\u662f\u7f51\u683c\u53d8\u5f62), \u56fe\u5f62\u5b66\u4e2d\u901a\u5e38\u5206\u4e3a\u4e24\u7c7b, \u5206\u522b\u662fMesh-Based Mapping\u4e0eMeshless Mapping(\u4e0e\u7f51\u683c\u65e0\u5173\u7684Mapping). \u5176\u4e2d, Mesh-Based Mapping\u901a\u5e38\u662f\u4ee5\u4eff\u5c04\u53d8\u6362\u7684\u5f62\u5f0f\u51fa\u73b0:$$f_t(x)=J_tx+b_t.$$\u800cMeshless Mapping\u5219\u901a\u5e38\u4ee5\u57fa\u51fd\u6570\u7684\u5f62\u5f0f\u51fa\u73b0:$$f(x)=\\sum^m_{i=1}c_iB_i(x).$$<\/p>\n<h3>P12: Mappings<\/h3>\n<p>\u76ee\u524d\u901a\u5e38\u4f1a\u628a\u6c42\u89e3Mapping\u7684\u95ee\u9898\u8f6c\u5316\u4e3a\u4e00\u4e2a\u6700\u4f18\u5316\u95ee\u9898, \u5176\u4e2d, \u80fd\u91cf\u51fd\u6570\u662f\u4e00\u4e2a\u4e0e\u7f51\u683c\u626d\u66f2\u7a0b\u5ea6\u76f8\u5173\u7684\u51fd\u6570, \u7ea6\u675f\u6761\u4ef6\u901a\u5e38\u662f\u8981\u6c42\u6240\u6709\u4e09\u89d2\u5f62\u5728\u7ecf\u8fc7\u6620\u5c04\u540e\u662f\u65e0\u7ffb\u8f6c\u7684, \u5f53\u7136, \u5728\u7279\u6b8a\u9886\u57df\u4e2d\u901a\u5e38\u4f1a\u6709\u989d\u5916\u7684\u9488\u5bf9\u6027\u7684\u7ea6\u675f\u6761\u4ef6, \u672c\u8282\u8bfe\u4e5f\u6ca1\u6709\u5bf9\u6b64\u8fdb\u884c\u7ec6\u8c08. \u80fd\u91cf\u51fd\u6570\u7684\u5f62\u5f0f\u901a\u5e38\u5982\u4e0b\u6240\u793a:$$\\min_{f}\\ D(f)\\\\s.t.\\ detJ(f(x))>0, \\forall x \\in M,\\\\S(f)\\le0,$$\u5176\u4e2d, $S(f)\\le0$\u662f\u9488\u5bf9\u7279\u5b9a\u9886\u57df\u7684\u7ea6\u675f, $D(f)$\u662f\u4e00\u4e2a\u4e0e\u7f51\u683c\u626d\u66f2\u7a0b\u5ea6\u76f8\u5173\u7684\u51fd\u6570, $M$\u4e3a\u4e00\u4e2a\u8f93\u5165\u7f51\u683c. \u6c42\u89e3\u8fd9\u79cd\u6700\u4f18\u5316\u95ee\u9898\u7684\u65b9\u6cd5\u4e3b\u8981\u5206\u4e3a\u4e09\u79cd,<br \/>\n$\\cdot$ \u7531Tutte&#8217;s Barycentric Mapping\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\u5df2\u7ecf\u6ee1\u8db3\u7ea6\u675f\u6761\u4ef6\u7684\u521d\u59cb\u89e3, \u4f46\u8be5\u521d\u59cb\u89e3\u7684\u626d\u66f2\u7a0b\u5ea6\u901a\u5e38\u662f\u6bd4\u8f83\u5927\u7684, \u9700\u8981\u8fdb\u884c\u8fdb\u4e00\u6b65\u8fed\u4ee3.<br \/>\n$\\cdot$ \u82e5\u8f83\u96be\u5f97\u5230\u4e00\u4e2a\u5df2\u7ecf\u6ee1\u8db3\u7ea6\u675f\u6761\u4ef6\u7684\u521d\u59cb\u89e3(\u5373\u521d\u59cb\u89e3\u53ef\u80fd\u4f9d\u65e7\u542b\u6709\u4e00\u90e8\u5206\u7ffb\u8f6c\u7684\u4e09\u89d2\u5f62), \u6709\u4e24\u79cd\u65b9\u5f0f\u8fdb\u884c\u5904\u7406, \u4e00\u79cd\u662f\u628a\u4f18\u5316\u95ee\u9898\u8f6c\u5316\u4e3a\u4e00\u4e2a\u51f8\u4f18\u5316\u95ee\u9898. \u5373\u628a\u5176\u7ea6\u675f\u6761\u4ef6\u8fdb\u884c\u51f8\u5316, \u53e6\u5916\u4e00\u79cd\u5219\u662f\u91c7\u7528Local-Global\u7684\u65b9\u6cd5(\u5176\u76f8\u5173\u7b97\u6cd5\u901a\u5e38\u5206\u4e3aLocal Step\u4e0eGlobal Step, Local Step\u901a\u5e38\u662f\u56fa\u5b9a\u6211\u4eec\u8981\u4f18\u5316\u7684\u53d8\u91cf, \u8f6c\u800c\u53bb\u4f18\u5316\u5176\u5b83\u8f85\u52a9\u53d8\u91cf), \u4e0d\u65ad\u5730\u628a\u5f53\u524d\u7ed3\u679c\u6295\u5f71\u5230\u4e00\u4e2a\u626d\u66f2\u7a0b\u5ea6\u6709\u754c\u7684\u7a7a\u95f4\u5f53\u4e2d, \u8fed\u4ee3\u8fdb\u884c, \u6700\u7ec8\u5f97\u5230\u4e00\u4e2a\u6ca1\u6709\u7ffb\u8f6c\u7684\u7ed3\u679c(\u81ea\u5df1\u7684\u7855\u58eb\u8bba\u6587\u7b97\u6cd5\u4e5f\u91c7\u7528\u4e86\u7c7b\u4f3c\u7684\u601d\u60f3). \u5f53\u7136, \u91c7\u7528Local-Global\u65b9\u6cd5\u7684\u7b97\u6cd5\u7684\u6536\u655b\u901f\u5ea6\u4e00\u822c\u662f\u6bd4\u8f83\u6162\u7684, \u76ee\u524d\u4e5f\u6709\u8bb8\u591a\u7b97\u6cd5\u6765\u9488\u5bf9\u5176\u6536\u655b\u901f\u5ea6\u8fdb\u884c\u4f18\u5316, \u6709\u7684\u662f\u5728\u6c42\u89e3\u5668\u4e0a\u505a\u6587\u7ae0, \u5982\u725b\u987f\u6cd5, \u62df\u725b\u987f\u6cd5(\u5982BFGS, L-BFGS)\u7b49; \u6709\u7684\u5219\u662f\u53e6\u8f9f\u8e4a\u5f84, \u5982\u4e2a\u4eba\u611f\u89c9\u8fd1\u4e4e\u4e07\u80fd\u7684\u5b89\u5fb7\u68ee\u52a0\u901f\u7b97\u6cd5(\u4ee5\u524d\u5728\u94c1\u8bd1\u5e08\u5144\u7684\u8ba8\u8bba\u73ed\u4e0a\u5b66\u8fc7, \u5176\u601d\u60f3\u8fd8\u662f\u975e\u5e38\u7b80\u5355\u6709\u6548\u7684, \u4e3b\u8981\u662f\u5728\u7ebf\u6027\u7a7a\u95f4\u4e0a\u505a\u6587\u7ae0)~<br \/>\n$\\cdot$ \u91c7\u7528\u53d8\u91cf\u8f6c\u5316\u7684\u601d\u60f3, \u628a\u4f18\u5316\u7f51\u683c\u9876\u70b9\u4f4d\u7f6e\u7684\u95ee\u9898\u8f6c\u5316\u4e3a\u4f18\u5316\u6bcf\u4e2a\u4e09\u89d2\u5f62\u7684\u4eff\u5c04\u53d8\u6362\u7684\u95ee\u9898, \u7b97\u6cd5\u7684\u4e3b\u8981\u601d\u8def\u662f\u4e00\u5f00\u59cb\u7ed9\u6bcf\u4e2a\u4e09\u89d2\u5f62\u8d4b\u4e88\u6ee1\u8db3\u7ea6\u675f\u6761\u4ef6\u7684\u4eff\u5c04\u53d8\u6362, \u4e0d\u65ad\u8fed\u4ee3, \u6700\u540e\u6839\u636e\u5f97\u5230\u7684\u6700\u4f18\u89e3\u628a\u7f51\u683c\u9876\u70b9\u6062\u590d\u51fa\u6765.<\/p>\n<h3>P13: PolyCube<\/h3>\n<p>PolyCube\u662f\u4e00\u79cd\u975e\u5e38\u7279\u6b8a\u7684\u51e0\u4f55\u7ed3\u6784(\u4e8c\u7ef4\u60c5\u5f62\u4e0b\u5219\u79f0\u4e3aPolySquare), \u5176\u8868\u9762\u7684\u6cd5\u5411\u662f\u8ddf\u5750\u6807\u8f74\u5411\u91cf\u5e73\u884c\u7684, \u4ec5\u67096\u4e2a\u65b9\u5411, \u5206\u522b\u662f+x, -x, +y, -y, +z\u4e0e-z, \u901a\u5e38\u4ee5\u7acb\u65b9\u4f53\u96c6\u5408\u7684\u5f62\u5f0f\u5448\u73b0, \u7c7b\u4f3c\u4e8e\u642d\u79ef\u6728\u4e00\u822c, \u4e3b\u8981\u662f\u5e94\u7528\u4e8e\u516d\u9762\u4f53\u7f51\u683c\u7684\u751f\u6210\u6216\u8005\u56db\u8fb9\u5f62\u7f51\u683c\u7684\u751f\u6210. \u7d27\u63a5\u7740\u672c\u8282\u8bfe\u4e3b\u8981\u4ecb\u7ecd\u4e862\u79cd\u7ecf\u5178\u7b97\u6cd5,<br \/>\n$\\cdot$ Deformation-Based Method, \u7b97\u6cd5\u7684\u4e3b\u8981\u601d\u8def\u662f\u5bf9\u5404\u4e2a\u7f51\u683c\u9762\u7684\u6cd5\u5411\u8fdb\u884c\u64cd\u4f5c, \u4f7f\u5176\u5c3d\u91cf\u4e0e\u5750\u6807\u8f74\u5e73\u884c.<br \/>\n$\\cdot$ Voxel-Based Methos, \u5148\u7528Deformation-Based Method\u5bf9\u8f93\u5165\u7f51\u683c\u8fdb\u884c\u9884\u5904\u7406\u5f97\u5230\u4e00\u4e2a\u5404\u4e2a\u7f51\u683c\u9762\u6cd5\u5411\u4e0e\u5750\u6807\u8f74\u8fd1\u4e4e\u5e73\u884c\u7684\u7c97\u7cd9\u7f51\u683c, \u7136\u540e\u5728\u8fd9\u4e2a\u7c97\u7cd9\u7f51\u683c\u4e0a\u6784\u5efa\u4e00\u4e2a\u521d\u59cb\u7684PolyCube, \u8fd9\u4e2a\u521d\u59cb\u7684PolyCube\u7684\u89d2\u70b9(Corner) \u9700\u8981\u5c3d\u53ef\u80fd\u5730\u5c11, \u4e14\u4e0e\u7c97\u7cd9\u7f51\u683c\u7684\u62d3\u6251\u7ed3\u6784\u9700\u8981\u5c3d\u53ef\u80fd\u5730\u4fdd\u6301\u4e00\u81f4, \u5982\u6ca1\u6709\u975e\u6d41\u5f62\u7684\u70b9, \u9762, \u4e8f\u683c\u6570\u91cf\u5c3d\u53ef\u80fd\u4e00\u81f4(\u6b64\u5904\u7684\u4e8f\u683c\u6570\u91cf\u53ef\u4ee5\u76f4\u63a5\u5229\u7528\u6b27\u62c9\u516c\u5f0f\u8fdb\u884c\u8ba1\u7b97, \u56e0\u4e3a\u662f\u5728\u4f53\u7f51\u683c\u4e0a\u7684, \u76f8\u6bd4\u8f83\u5728\u9762\u7f51\u683c\u4e0a\u7684\u4e8f\u683c\u6570\u91cf\u7684\u8ba1\u7b97\u8fd8\u662f\u65b9\u4fbf\u5f97\u591a). \u800c\u5bf9\u4e8e\u5982\u4f55\u6784\u5efaPolyCube, \u672c\u8282\u4e5f\u4ecb\u7ecd\u4e86\u4e24\u79cd\u7b97\u6cd5, \u5176\u4e2d\u4e00\u79cd\u7b97\u6cd5\u7684\u4e3b\u8981\u601d\u8def\u662f\u6c42\u89e3\u4e00\u4e2a\u5e26\u7ea6\u675f\u7684\u6700\u4f18\u5316\u95ee\u9898, \u628a\u51e0\u4f55\u4e0a\u7684\u76f8\u4f3c\u6027(\u8861\u91cf\u6784\u9020\u51fa\u6765\u7684PolyCube\u76f8\u6bd4\u8f83\u4e8e\u7c97\u7cd9\u7f51\u683c\u7684\u626d\u66f2\u7a0b\u5ea6) \u53ca\u62d3\u6251\u7684\u4e0d\u53d8\u6027\u90fd\u4f5c\u4e3a\u5176\u786c\u7ea6\u675f, \u628a\u6784\u9020\u51fa\u6765\u7684PolyCube\u7684\u89d2\u70b9\u6570\u91cf\u4f5c\u4e3a\u5176\u80fd\u91cf\u51fd\u6570.<\/p>\n<h3>P14: Surface Mapping<\/h3>\n<p>Surface Mapping\u65e8\u5728\u5bfb\u627e\u4e24\u4e2a\u7f51\u683c\u4e4b\u95f4\u7684\u4e00\u4e00\u6620\u5c04, \u672c\u8282\u4e3b\u8981\u4ecb\u7ecd\u4e86\u5bfb\u627eCompatible Meshes(\u5373\u9876\u70b9\u6570\u91cf\u4e0e\u8fde\u63a5\u5173\u7cfb\u5747\u76f8\u540c\u7684\u7f51\u683c\u96c6\u5408) \u4e4b\u95f4\u7684\u4e00\u4e00\u6620\u5c04\u7684\u7b97\u6cd5, \u5176\u5e94\u7528\u4e3b\u8981\u662fMorphing\u4e0eAttribute Transfer(\u5305\u62ec\u4f4d\u7f6e, \u7eb9\u7406\u7b49\u5c5e\u6027\u7684\u8fc1\u79fb) \u7b49. \u76f8\u5173\u7684\u7b97\u6cd5\u4e3b\u8981\u6709\u4e24\u7c7b, \u4e14\u5f97\u5230\u7684\u6620\u5c04\u4e0d\u4e00\u5b9a\u662fBijective\u7684, \u4e00\u822c\u662fLocally Injective\u7684.<br \/>\n$\\cdot$ Common Base Domain\u7b97\u6cd5, \u628a\u8f93\u5165\u7f51\u683c\u5206\u522b\u6620\u5c04\u5230\u4e24\u4e2a\u4e2d\u95f4\u533a\u57df, \u7136\u540e\u518d\u5bfb\u627e\u8fd9\u4e24\u4e2a\u4e2d\u95f4\u533a\u57df\u4e4b\u95f4\u7684\u6620\u5c04, \u6700\u540e\u628a\u5df2\u7ecf\u5f97\u5230\u7684\u6240\u6709\u6620\u5c04\u8fdb\u884c\u590d\u5408\u8fd0\u7b97\u5373\u53ef\u5f97\u5230\u8f93\u5165\u7f51\u683c\u4e4b\u95f4\u7684\u6620\u5c04. \u7b97\u6cd5\u7684\u7f3a\u70b9\u4e3b\u8981\u662fCommon Base Domain\u7684\u6784\u9020\u662f\u6bd4\u8f83\u590d\u6742\u7684, \u540c\u65f6\u7b97\u6cd5\u7ed3\u679c\u5f97\u5230\u7684\u6620\u5c04\u7684\u626d\u66f2\u7a0b\u5ea6\u53ef\u80fd\u6bd4\u8f83\u9ad8.<br \/>\n$\\cdot$ Parameterization-Based Method, \u4e2a\u4eba\u611f\u89c9\u672c\u8d28\u4e0a\u8fd8\u662fCommon Base Domain\u7b97\u6cd5, \u4e0d\u540c\u4e4b\u5904\u5728\u4e8eParameterization-Based Method\u7684\u521d\u59cb\u6b65\u9aa4\u4e2d\u5f97\u5230\u7684Common Base Domain\u4ec5\u6709\u4e00\u4e2a, \u6b64\u5904\u7684Common Base Domain\u901a\u5e38\u662f\u901a\u8fc7\u53c2\u6570\u5316\u5f97\u5230\u7684.<\/p>\n<h3>P15: Morphing\u4e0ePoint Set Registration<\/h3>\n<p>\u8fd9\u8282\u8bfe\u8fd8\u662f\u6709\u4e0d\u5c11\u5e72\u8d27\u7684, \u867d\u7136\u7b97\u6cd5\u7684\u5177\u4f53\u7ec6\u8282\u6ca1\u6709\u4ecb\u7ecd, \u4f46\u5176\u601d\u8def\u8fd8\u662f\u7ed9\u4e86\u6211\u4e0d\u5c11\u542f\u53d1.<\/p>\n<h4>15.1 Morphing<\/h4>\n<p>Morphing\u95ee\u9898\u901a\u5e38\u7528\u63d2\u503c\u7684\u601d\u8def\u53bb\u89e3\u51b3: \u7ed9\u5b9a\u6e90\u6a21\u578b$M^0$, \u76ee\u6807\u6a21\u578b$M^1$\u4e0e\u65f6\u95f4$t$, \u5982\u4f55\u8ba1\u7b97\u5f62\u72b6$M^t$? \u5f53$t \\in [0,1]$\u65f6\u8be5\u95ee\u9898\u4e3a\u4e00\u4e2a\u5185\u63d2\u95ee\u9898, \u53cd\u4e4b\u5219\u4e3a\u4e00\u4e2a\u5916\u63d2\u95ee\u9898. \u76f8\u5173\u7b97\u6cd5\u4e3b\u8981\u6709\u4e09\u7c7b,<br \/>\n$\\cdot$ \u5148\u5bf9\u4e00\u4e9b\u91cf\u8fdb\u884c\u63d2\u503c, \u5982\u89d2\u5ea6, \u957f\u5ea6, \u9762\u79ef, \u4f53\u79ef\u6216\u8005\u66f2\u7387\u7b49, \u5982\u4e0b\u6240\u793a.$$l^t_e = (1-t)l^0_e + tl^1_e, \\\\ \\theta^t_e = (1-t)\\theta^0_e + t\\theta^1_e, \\\\ V^t = (1-t)V^0 + tV^1,$$\u5176\u4e2d, $l_e$\u4e3a\u8fb9\u957f, $\\theta_e$\u4e3a\u4e24\u4e2a\u4e09\u89d2\u5f62\u4e4b\u95f4\u7684\u4e8c\u9762\u89d2, $V=\\frac{1}{6}\\sum_{f_{i,j,k}}(x_i \\times x_j) \\cdot x_k$\u4ee5\u67d0\u4e2a\u4e09\u89d2\u5f62\u4e3a\u5e95, \u539f\u70b9\u4e3a\u9876\u70b9\u6784\u6210\u7684\u690e\u4f53\u7684\u4f53\u79ef. \u6700\u540e\u6839\u636e\u8fd9\u4e9b\u91cf\u7684\u63d2\u503c\u7ed3\u679c\u6062\u590d\u9876\u70b9\u4f4d\u7f6e, \u8fd9\u4e2a\u7b97\u6cd5\u601d\u8def\u4e5f\u662f\u5728\u4e4b\u524d\u7684\u8bfe\u7a0b\u4e2d\u4ecb\u7ecd\u8fc7\u7684, \u901a\u5e38\u5c06\u5176\u8f6c\u5316\u4e3a\u6700\u4f18\u5316\u95ee\u9898, \u5f62\u5f0f\u5982\u4e0b\u6240\u793a.$$E_l = \\frac{1}{2} \\sum_e (l_e &#8211; l^t_e)^2, \\\\ E_a = \\frac{1}{2} \\sum_e (\\theta_e &#8211; \\theta^t_e)^2, \\\\ E_v = \\frac{1}{2} \\sum_e (V &#8211; V^t_e)^2, \\\\ E = \\lambda E_l + \\mu E_a + \\nu E_v.$$$\\cdot$ \u5bf9\u4eff\u5c04\u53d8\u6362\u8fdb\u884c\u63d2\u503c, \u5e38\u7528\u5f62\u5f0f\u662fAs-Rigid-Possible Shape Interpolation(\u5373ARAP). \u90a3\u4e48\u5982\u4f55\u5408\u7406\u5730\u5b9a\u4e49$t$\u65f6\u523b\u7684\u4eff\u5c04\u53d8\u6362$A(t)$\u5462? \u4e00\u79cd\u6700\u4e3a\u7b80\u5355\u7684\u5b9a\u4e49\u4fbf\u662f$$A(t) = (1-t)I + tA.$$\u663e\u7136, \u8fd9\u662f\u4e00\u79cd\u7ebf\u6027\u63d2\u503c, \u6700\u5927\u7684\u7f3a\u70b9\u4fbf\u662f\u5bb9\u6613\u5728Morphing\u7684\u8fc7\u7a0b\u4e2d\u4ea7\u751f\u7a7f\u6a21\u95ee\u9898. \u66f4\u4e3a\u5408\u7406\u7684\u5b9a\u4e49\u6709\u4e24\u79cd, \u5206\u522b\u662f<br \/>\n$\\quad \\cdot$ \u5229\u7528\u5947\u5f02\u503c\u5206\u89e3,$$A = U \\sum V^T, \\\\ A(t) = U(t)((1-t)I + t\\sum)V^T(t).$$$\\quad \\cdot$ \u5229\u7528\u6781\u5206\u89e3,$$A = U \\sum V^T=UV^TV \\sum V^T = RS, \\\\ A(t) = R(t)((1-t)I + tS).$$\u5373\u628a\u4eff\u5c04\u53d8\u6362\u77e9\u9635$A$\u5206\u89e3\u4e3a\u65cb\u8f6c\u77e9\u9635$R$\u4e0e\u7f29\u653e\u77e9\u9635$S$, \u7136\u540e\u5206\u522b\u8fdb\u884c\u7ebf\u6027\u63d2\u503c.<br \/>\n(PS: \u4e2a\u4eba\u89c9\u5f97\u6b64\u5904\u7684\u4eff\u5c04\u53d8\u6362\u5e94\u8be5\u79f0\u4e3a\u7ebf\u6027\u53d8\u6362\u66f4\u4e3a\u4e25\u8c28, \u56e0\u4e3a\u6839\u672c\u6ca1\u6709\u6d89\u53ca\u5e73\u79fb\u53d8\u6362\u5416\u2026\u2026)<br \/>\n\u7531\u4e0a\u8ff0\u5b9a\u4e49\u53ef\u77e5, \u6b64\u79cd\u7b97\u6cd5\u5e76\u6ca1\u6709\u5bf9\u5e73\u79fb\u53d8\u6362\u8fdb\u884c\u5904\u7406. \u56e0\u6b64\u5728\u7b97\u6cd5\u5904\u7406\u65f6, \u901a\u5e38\u8fd8\u9700\u8981\u56fa\u5b9a\u67d0\u4e2a\u70b9\u7684\u4f4d\u7f6e\u4fdd\u6301\u4e0d\u53d8.<br \/>\n$\\cdot$ \u6570\u636e\u9a71\u52a8\u7684Morphing. \u6b64\u5904\u5e76\u975e\u5229\u7528\u795e\u7ecf\u7f51\u7edc\u8fdb\u884cMorphing, \u800c\u662f\u5728\u7279\u5b9a\u7684\u6570\u636e\u5e93\u4e2d\u5bfb\u627e$M^0, M^1$\u5339\u914d\u7684\u6a21\u578b, \u56e0\u6b64\u7b97\u6cd5\u7684\u5173\u952e\u4fbf\u662f\u5bfb\u627e\u5408\u9002\u7684\u8861\u91cf\u4e24\u4e2a\u6a21\u578b\u4e4b\u95f4\u7684Difference\u7684\u91cf, \u901a\u5e38\u4fbf\u662f\u76f4\u63a5\u5229\u7528\u5339\u914d\u9876\u70b9\u7684\u4f4d\u7f6e\u4e4b\u95f4\u7684\u5dee, \u5982\u4e0b\u6240\u793a.$$\\bar{d}(M_i,M_j) = \\sqrt{\\frac{ {\\textstyle \\sum_{k=1}^{n}} \\left \\| v^i_k &#8211; v^j_k \\right \\| ^2  }{n} } ,$$\u5176\u4e2d, $v^i_k$\u662f\u7b2c$i$\u4e2a\u6a21\u578b$M_i$\u7684\u7b2c$k$\u4e2a\u9876\u70b9, $n$\u4e3a\u5f53\u524d\u6a21\u578b\u7684\u9876\u70b9\u6570\u91cf. \u4e3a\u4e86\u5f97\u5230$M_i,M_j$\u4e4b\u95f4\u7684\u771f\u6b63\u7684Difference, \u901a\u5e38\u8fd8\u9700\u8981\u8fdb\u884c\u9884\u6821\u51c6, \u56e0\u4e3a$M_i,M_j$\u6240\u5904\u7684\u5750\u6807\u7cfb\u53ef\u80fd\u662f\u4e0d\u76f8\u540c\u7684, \u5373\u9700\u8981\u8ba1\u7b97\u4e00\u4e2a\u4f7f\u5f97$M_i,M_j$\u4e4b\u95f4\u7684Difference\u6700\u5c0f\u7684\u4eff\u5c04\u53d8\u6362.<br \/>\n\u4e0a\u8ff0\u7b97\u6cd5\u7ed3\u679c\u5747\u6709\u53ef\u80fd\u5728\u6c42\u89e3\u671f\u95f4\u9677\u5165\u5c40\u90e8\u6700\u5c0f\u503c, \u53ef\u4ee5\u901a\u8fc7\u589e\u52a0\u91c7\u6837\u70b9\u7684\u65b9\u5f0f\u8fdb\u884c\u7f13\u89e3. \u5373\u5148\u5c06$[0,1]$\u5206\u4e3a$n$\u6bb5, \u82e5\u8981\u6c42\u5f97$t$\u65f6\u523b($t \\in (0,1)$) \u7684\u63d2\u503c\u7ed3\u679c, \u53ef\u5c06$[t\/n]$\u65f6\u523b(\u6b64\u5904$[x]$\u8868\u793a\u9ad8\u65af\u51fd\u6570) \u7684\u7ed3\u679c\u4f5c\u4e3a\u7b97\u6cd5\u8f93\u5165, \u800c\u975e\u76f4\u63a5\u628a\u6e90\u6a21\u578b$M^0$\u4f5c\u4e3a\u7b97\u6cd5\u8f93\u5165, \u76f8\u5f53\u4e8e\u4eba\u4e3a\u9650\u5236\u4e86\u4f18\u5316\u8def\u5f84. \u4e2a\u4eba\u8fd8\u6ca1\u60f3\u901a\u4e3a\u4f55\u8fd9\u6837\u7684\u5904\u7406\u80fd\u7f13\u89e3\u6c42\u89e3\u7ed3\u679c\u9677\u5165\u5c40\u90e8\u6700\u5c0f\u503c\u7684\u73b0\u8c61, \u4f46\u76f4\u89c2\u4e0a\u6765\u770b, \u80fd\u4f7f\u5f97\u63d2\u503c\u8fc7\u7a0b\u53d8\u5f97\u66f4\u4e3a\u8fde\u7eed(\u4e0d\u592a\u4e25\u683c\u7684\u8bf4\u6cd5233).<\/p>\n<h4>15.2 Point Set Registration<\/h4>\n<p>\u70b9\u4e91\u6ce8\u518c\u7684\u76ee\u7684\u662f\u4e3a\u4e86\u628a\u4e24\u4e2a\u4e0d\u540c\u7684\u70b9\u96c6\u653e\u81f3\u76f8\u540c\u7684\u5750\u6807\u7cfb\u4e2d, \u5176\u4e2d\u6700\u7ecf\u5178\u7684\u7b97\u6cd5\u4fbf\u662fIterative Closest Point\u7b97\u6cd5(ICP), \u901a\u5e38\u4f1a\u5c06\u5176\u8f6c\u5316\u4e3a\u6700\u4f18\u5316\u95ee\u9898\u8fdb\u884c\u6c42\u89e3, \u5373\u8981\u6781\u5c0f\u5316\u4e0b\u8ff0\u80fd\u91cf\u51fd\u6570,$$E(P,Q) = \\sum_{(p_i,q_i)} \\left \\| Rp_i + t &#8211; q_i \\right \\| ^2_2.$$\u8fd9\u4e2a\u80fd\u91cf\u51fd\u6570\u7684\u4f18\u5316\u8fc7\u7a0b\u8fd8\u662f\u5341\u5206\u5de7\u5999\u7684, \u8be6\u7ec6\u63a8\u5bfc\u53ef\u53c2\u8003\u89c6\u9891\u5185\u5bb9. <\/p>\n<h3>P16: Atlas Generation<\/h3>\n<p>\u672c\u8282\u8bfe\u5305\u542b\u672c\u4eba\u8bb8\u591a\u6bd4\u8f83\u611f\u5174\u8da3\u7684\u70b9, \u5176\u4e2d\u6d89\u53ca\u5230\u7684\u8bba\u6587\u4e5f\u591a\u6570\u662f\u81ea\u5df1\u66fe\u7ecf\u770b\u8fc7\u6216\u8005\u8ba1\u5212\u60f3\u770b\u7684, \u56e0\u6b64\u4f1a\u5c3d\u53ef\u80fd\u8bb0\u5f55\u4e0b\u672c\u8282\u8bfe\u4ecb\u7ecd\u7684\u91cd\u70b9\u5185\u5bb9. Atalas\u7684\u751f\u6210\u7b97\u6cd5\u901a\u5e38\u5305\u542b\u4e09\u6b65, \u5206\u522b\u662fMesh Cutting, Chart Parameterizations\u4e0eChart Packing, \u4e3b\u8981\u5e94\u7528\u4e8e\u4fe1\u53f7\u5b58\u50a8\u4e0e\u51e0\u4f55\u5904\u7406\u7b49\u9886\u57df. \u672c\u8282\u8bfe\u4ec5\u4ecb\u7ecd\u4e86\u524d\u4e24\u6b65, \u6700\u540e\u4e00\u6b65Packing\u5728\u672c\u8282\u4e2d\u4ec5\u4f5c\u7b80\u5355\u4ecb\u7ecd, \u5177\u4f53\u5185\u5bb9\u7684\u4ecb\u7ecd\u7559\u5f85\u4e0b\u8282.<\/p>\n<h4>16.1 Mesh Cutting<\/h4>\n<p>Mesh Cutting\u8fd9\u4e00\u6b65\u7684\u76ee\u6807\u662f\u7b97\u6cd5\u7ed3\u679c\u7684\u626d\u66f2\u7a0b\u5ea6\u5c3d\u53ef\u80fd\u4f4e, \u4e14\u5272\u7ebf\u957f\u5ea6\u5c3d\u53ef\u80fd\u5c0f. \u626d\u66f2\u7a0b\u5ea6\u5c3d\u53ef\u80fd\u4f4e\u7684\u76ee\u6807\u662f\u5bb9\u6613\u7406\u89e3\u7684, \u800c\u5272\u7ebf\u957f\u5ea6\u5c3d\u53ef\u80fd\u5c0f\u7684\u76ee\u6807\u5219\u662f\u56e0\u4e3a\u5728\u8fdb\u884c\u5b8cMesh Cutting\u8fd9\u4e00\u6b65\u4ee5\u540e, \u82e5\u60f3\u8fdb\u884c\u989c\u8272\u7f16\u8f91, \u9700\u8981\u4fdd\u8bc1\u5272\u7ebf\u4e24\u8fb9\u7684\u989c\u8272\u5dee\u5f02\u5c3d\u53ef\u80fd\u5730\u5c0f, \u5426\u5219\u5728\u7f51\u683c\u6e32\u67d3\u51fa\u6765\u4ee5\u540e, \u5272\u7ebf\u5c31\u4f1a\u8f83\u4e3a\u660e\u663e\u5730\u5448\u73b0\u5728\u7f51\u683c\u4e0a. \u56e0\u6b64, \u5272\u7ebf\u957f\u5ea6\u5c3d\u53ef\u80fd\u5c0f\u7684\u7b97\u6cd5\u7ed3\u679c\u80fd\u4f7f\u5f97\u989c\u8272\u7f16\u8f91\u7684\u6d41\u7a0b\u66f4\u4e3a\u987a\u7545. Mesh Cutting\u7684\u5b9e\u73b0\u65b9\u5f0f\u4e3b\u8981\u6709\u4e24\u7c7b.<\/p>\n<p>$\\cdot$ <strong>Points $\\to$ Paths.<\/strong> \u5176\u601d\u8def\u5f88\u7b80\u5355: \u627e\u51fa\u5f15\u8d77\u9ad8\u626d\u66f2\u7684\u70b9, \u7136\u540e\u628a\u8fd9\u4e9b\u70b9\u5728\u7f51\u683c\u8868\u9762\u4e0a\u8fde\u8d77\u6765(\u4e00\u822c\u4e3a\u6d4b\u5730\u7ebf), \u5219\u5f97\u5230\u76f8\u5e94\u7684\u7f51\u683c\u5272\u7ebf. \u4ee3\u8868\u8bba\u6587\u4fbf\u662f\u987e\u9669\u5cf0\u8001\u5e08\u4e8eSiggraph 2002\u4e0a\u53d1\u8868\u7684Geometry Images, \u8fd9\u7bc7\u8bba\u6587\u4e5f\u662f\u81ea\u5df1\u4e00\u76f4\u5f88\u60f3\u770b\u7684\u4e00\u7bc7\u8bba\u6587, \u53ea\u53ef\u60dc\u4e00\u76f4\u6ca1\u80fd\u62bd\u51fa\u65f6\u95f4\u6765. \u5085\u5b5d\u660e\u8001\u5e08\u8fd9\u91cc\u4e5f\u7b80\u5355\u5730\u4ecb\u7ecd\u4e86\u4e00\u4e0b\u8fd9\u7bc7\u6587\u7ae0\u7684\u7b97\u6cd5\u601d\u8def: \u4e3b\u8981\u91c7\u7528\u4e86\u8fed\u4ee3\u6cd5, \u9996\u5148\u5728\u7f51\u683c\u4e0a\u968f\u673a\u9009\u53d6\u4e00\u6761\u5272\u7ebf, \u5c06\u539f\u6765\u7684\u95ed\u7f51\u683c\u8f6c\u5316\u4e3a\u4e00\u4e2a\u5f00\u7f51\u683c, \u5229\u7528Tutte\u2019s Embedding\u5c06\u5f00\u7f51\u683c\u53c2\u6570\u5316\u4e3a\u5e73\u9762\u4e0a\u56fa\u5b9a\u8fb9\u754c(\u4e00\u822c\u4e3a\u5706\u5468) \u7684\u7f51\u683c, \u627e\u51fa\u5f15\u8d77\u9ad8\u626d\u66f2\u7684\u5272\u7ebf, \u5c06\u5176\u6dfb\u52a0\u5230\u521d\u59cb\u5272\u7ebf\u4e2d, \u63a5\u7740\u91cd\u590d\u4e0a\u8ff0\u6b65\u9aa4, \u4e0d\u65ad\u6269\u5c55\u5272\u7ebf, \u76f4\u5230\u5f97\u5230\u7684\u53c2\u6570\u5316\u7f51\u683c\u5185(\u9664\u53bb\u8fb9\u754c) \u4e0d\u518d\u542b\u6709\u5f15\u8d77\u9ad8\u626d\u66f2\u7684\u70b9. \u4f46\u8be5\u7b97\u6cd5\u6709\u4e00\u4e9b\u8f83\u4e3a\u660e\u663e\u7684\u7f3a\u70b9:<br \/>\n$\\quad$ $\\cdot$ \u53d7\u521d\u59cb\u503c\u7684\u5f71\u54cd\u8f83\u5927, \u4e00\u4e2a\u7f13\u89e3\u8be5\u95ee\u9898\u7684\u65b9\u6848\u4e3a, \u5728\u627e\u5230\u4e24\u4e2a\u5f15\u8d77\u9ad8\u626d\u66f2\u7684\u70b9\u4ee5\u540e, \u628a\u521d\u59cb\u5272\u7ebf\u4ece\u5f53\u524d\u5272\u7ebf\u4e2d\u79fb\u9664, \u518d\u628a\u8fd9\u4e24\u4e2a\u70b9\u8fde\u6210\u7684\u5272\u7ebf\u4f5c\u4e3a\u521d\u59cb\u5272\u7ebf\u7ee7\u7eed\u6267\u884c\u7b97\u6cd5\u5373\u53ef.<br \/>\n$\\quad$ $\\cdot$ \u82e5\u7b97\u6cd5\u8fdb\u884c\u8fc7\u7a0b\u4e2d\u5f15\u8d77\u9ad8\u626d\u66f2\u7684\u70b9\u57fa\u672c\u90fd\u843d\u5728\u5e73\u9762\u7f51\u683c\u8fb9\u754c\u4e0a, \u5219\u7b97\u6cd5\u4f1a\u8fc7\u65e9\u5730\u63d0\u524d\u7ed3\u675f, \u5c24\u5176\u5728\u5904\u7406\u8f83\u4e3a\u5706\u6ed1\u7684\u7f51\u683c\u65f6\u8fd9\u4e2a\u95ee\u9898\u5c06\u4f1a\u8868\u73b0\u5f97\u66f4\u4e3a\u660e\u663e.<br \/>\n$\\quad$ $\\cdot$ \u7b97\u6cd5\u5f97\u5230\u7684\u5272\u7ebf\u65e0\u6cd5\u4fdd\u8bc1\u5168\u5c40\u6700\u4f18.<\/p>\n<p>$\\cdot$ <strong>Segmentation.<\/strong> \u4ee3\u8868\u8bba\u6587\u662f\u53d1\u8868\u4e8eEG 2015\u7684D-Charts: Quasi-Developable Mesh Segmentation, \u5176\u7b97\u6cd5\u76ee\u6807\u662f\u5c06\u7f51\u683c\u5206\u5272\u4e3a\u82e5\u5e72\u5757$C$, \u4f7f\u5f97\u6bcf\u4e00\u5757$C$\u7684\u53c2\u6570\u5316\u7ed3\u679c\u7684\u626d\u66f2\u7a0b\u5ea6\u5c3d\u53ef\u80fd\u4f4e, \u5176\u4e2d\u6bcf\u4e00\u4e2a\u5757$C$&#8221;\u63a5\u8fd1&#8221;\u4e00\u4e2a\u53ef\u5c55\u66f2\u9762(Developable Surface, \u5373\u6bcf\u4e00\u70b9\u5904\u9ad8\u65af\u66f2\u7387\u4e3a\u96f6\u7684\u66f2\u9762, \u80fd\u591f\u7ecf\u5f2f\u66f2\u800c\u5c55\u5f00\u6210\u4e00\u7247\u5e73\u9762). \u7531\u4e8e\u53ef\u5c55\u66f2\u9762\u7684\u7c7b\u578b\u5f88\u591a, \u56e0\u6b64\u6587\u7ae0\u9009\u53d6\u7684\u76ee\u6807\u53ef\u5c55\u66f2\u9762\u662f\u4e00\u7c7b\u6700\u7b80\u5355\u7684\u53ef\u5c55\u66f2\u9762\u2014\u2014\u76f4\u7eb9\u66f2\u9762(\u6bcf\u4e00\u70b9\u5904\u6cd5\u5411\u4e0e\u5176\u8f74\u7684\u5939\u89d2\u4e3a\u5e38\u6570\u7684\u66f2\u9762), \u5e76\u79f0\u4e4b\u4e3aProxy(< axis, angle >, <$N_C,\\theta_C$>), \u800c\u8861\u91cf\u5757$C$\u4e0eProxy\u4e4b\u95f4\u7684\u8ddd\u79bb\u7684\u80fd\u91cf\u51fd\u6570\u5219\u5b9a\u4e49\u4e3a$$F(C,t)=(N_C \\cdot n_t, &#8211; cos\\theta_C)^2,$$\u5176\u4e2d$t$\u4e3a\u5757$C$\u4e2d\u7684\u4e09\u89d2\u5f62. \u6587\u7ae0\u7684\u7b97\u6cd5\u6b65\u9aa4\u5982\u4e0b\u6240\u793a(\u91c7\u7528Lloyd\u7b97\u6cd5\u7684\u601d\u60f3):<br \/>\n$\\quad$ 1) \u968f\u673a\u9009\u53d6\u4e09\u89d2\u5f62\u4f5c\u4e3a\u79cd\u5b50&#8221;\u70b9&#8221;.<br \/>\n$\\quad$ 2) \u5229\u7528\u8d2a\u5fc3\u7b97\u6cd5\u5f80\u79cd\u5b50\u70b9\u5468\u56f4\u6269\u5f20\u5f62\u6210\u5757$C$.<br \/>\n$\\quad$ 3) \u5728\u6bcf\u4e00\u5757$C$\u4e0a\u9009\u53d6\u65b0\u7684Proxy($F(C,t)$\u5e94\u4fdd\u8bc1\u6709\u754c).<br \/>\n$\\quad$ 4) \u91cd\u590d\u7b2c2, 3\u6b65\u76f4\u81f3\u7b97\u6cd5\u6536\u655b.<br \/>\n$\\quad$ 5) \u5728\u4e0a\u8ff0Lloyd\u7b97\u6cd5\u7ed3\u679c\u7684\u57fa\u7840\u4e4b\u4e0a\u8fdb\u884c\u6d1e\u7684\u586b\u8865, \u5176\u4e2d\u5c0f\u6d1e\u5219\u76f4\u63a5\u4e0e\u90bb\u5c45\u5757$C$\u5408\u5e76, \u5927\u6d1e\u5219\u4f5c\u4e3a\u4e00\u4e2a\u65b0\u7684\u5757$C$.<br \/>\n$\\quad$ 6) \u5408\u5e76\u4e0d\u540c\u7684\u5757$C$, \u5c3d\u53ef\u80fd\u5730\u51cf\u5c11\u5757$C$\u7684\u6570\u76ee, \u5408\u5e76\u51c6\u5219\u4e3a\u5408\u5e76\u540e\u7684$F(C,t)$\u5728\u53ef\u63a5\u53d7\u7684\u8303\u56f4\u5185.<br \/>\n$\\quad$ 7) \u540e\u5904\u7406\u4e0e\u53c2\u6570\u5316.<br \/>\n\u5176\u4e2d, \u7b2c3\u6b65\u4e2d\u9700\u8981\u4f18\u5316\u4e0b\u8ff0\u80fd\u91cf\u51fd\u6570,$$\\min_{N_C,\\theta_C} \\frac{1}{A_C} {\\textstyle \\sum_{t \\in C}} A_tF(C,t), s.t. \\left \\| N_C  \\right \\| =1.$$<\/p>\n<h4>16.2 Chart Parameterizations<\/h4>\n<p>Chart Parameterizations\u8fd9\u4e00\u6b65\u7684\u76ee\u6807\u662f\u6784\u9020\u53cc\u5c04(\u7b97\u6cd5\u7ed3\u679c\u7684\u8fb9\u754c\u4e0d\u4f1a\u81ea\u4ea4) \u4f7f\u5f97\u7b97\u6cd5\u7ed3\u679c\u7684\u7b49\u8ddd\u626d\u66f2\u7a0b\u5ea6\u5c3d\u53ef\u80fd\u4f4e, \u4ee3\u8868\u8bba\u6587\u4e3b\u8981\u6709\u4e09\u7bc7, \u5176\u4e2d\u6700\u540e\u4e00\u7bc7\u662f\u4e2d\u79d1\u5927\u7ec4\u5185\u7684Siggraph\u6587\u7ae0, \u4ec5\u4ec5\u662f\u7b80\u5355\u4ecb\u7ecd\u4e86\u4e00\u4e0b, \u6b64\u5904\u4fbf\u4e0d\u4f5c\u8bb0\u5f55.<br \/>\n$\\cdot$ Bijective Parameterization with Free Boundaries, Siggraph 2015. \u6838\u5fc3\u601d\u60f3\u662f\u5b9a\u4e49\u4e86\u5173\u4e8e\u8fb9\u754c\u70b9$U_i(i \\ne 1,2)$\u4e0e\u5176\u5b83\u8fb9\u754c(\u4e24\u7aef\u7aef\u70b9\u4e0d\u59a8\u8bbe\u4e3a$U_1, U_2$)\u7684\u969c\u788d\u51fd\u6570:$$max(0,\\frac{\\varepsilon}{dist(U_1,U_2,U_i)}-1)^2,$$\u5176\u4e2d$dist(U_1,U_2,U_i)$\u8861\u91cf\u4e86\u4e00\u4e2a\u8fb9\u754c\u70b9$U_i(i \\ne 1,2)$\u5230\u8fb9\u754c$(U_1,U_2)$\u7684\u8ddd\u79bb. \u6b64\u5904\u969c\u788d\u51fd\u6570\u4e2d\u5e73\u65b9\u7684\u4f5c\u7528\u53ef\u80fd\u662f\u4e3a\u4e86\u7b80\u5316\u6c42\u5bfc\u7684\u8fc7\u7a0b.<br \/>\n$\\cdot$ Simplicial Complex Augmentation Framework for Bijective Maps, Siggraph Asia 2017. \u6587\u7ae0\u4e2d\u4f7f\u7528\u4e86\u4e00\u79cd\u88ab\u79f0\u4e3a\u811a\u624b\u67b6\u7684\u5e73\u9762\u7f51\u683c\u7ed3\u6784, \u5c06\u7ecfTutte\u2019s Embedding\u5f97\u5230\u7684\u521d\u59cb\u5e73\u9762\u7f51\u683c\u4e0e\u811a\u624b\u67b6\u5e73\u9762\u7f51\u683c\u4f5c\u4e3a\u4e00\u4e2a\u6574\u4f53, \u5e76\u5c06\u8fd9\u4e2a\u6574\u4f53\u9650\u5236\u5728\u4e00\u4e2aBounding Box\u91cc. \u90a3\u4e48\u5728\u7b97\u6cd5\u7684\u4f18\u5316\u8fc7\u7a0b\u4e2d, \u5916\u8fb9\u754c\u663e\u7136\u662f\u4fdd\u6301\u4e0d\u52a8\u7684, \u5373\u4e0d\u4f1a\u53d1\u751f\u81ea\u4ea4, \u56e0\u6b64\u5bf9\u4e8e\u5185\u90e8\u7f51\u683c, \u4ec5\u9700\u4fdd\u8bc1\u4e09\u89d2\u5f62\u65e0\u7ffb\u8f6c\u5373\u53ef\u5f97\u5230\u8fb9\u754c\u4e0d\u81ea\u4ea4\u7684\u7ed3\u679c. \u6587\u7ae0\u7b97\u6cd5\u7684\u4e3b\u8981\u7f3a\u70b9\u5728\u4e8e, \u7b97\u6cd5\u8fdb\u884c\u7684\u8fc7\u7a0b\u4e2d\u811a\u624b\u67b6\u7f51\u683c\u4e2d\u7684\u4e09\u89d2\u5f62\u6709\u53ef\u80fd\u53d1\u751f\u7ffb\u8f6c, \u6b64\u65f6\u9700\u8981\u5bf9\u811a\u624b\u67b6\u7f51\u683c\u8fdb\u884cRemesh, \u8fd9\u6837\u4e00\u6765\u5c31\u4f1a\u6539\u53d8\u4e09\u89d2\u5f62\u7684\u6570\u76ee\u6216\u8005\u8fde\u63a5\u5173\u7cfb, \u4ece\u800c\u6c42\u89e3\u6240\u7528\u7684Hessian\u77e9\u9635\u7684\u975e\u96f6\u5143\u7ed3\u6784\u4e5f\u5728\u4e0d\u65ad\u5730\u53d1\u751f\u6539\u53d8, \u5bfc\u81f4\u8f83\u5927\u7684\u65f6\u95f4\u5f00\u9500.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Simplicial-Complex-Augmentation-Framework-for-Bijective-Maps\u8bba\u6587\u622a\u56fe.png\" alt=\"\" width=\"1519\" height=\"438\" class=\"alignnone size-full wp-image-1308\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Simplicial-Complex-Augmentation-Framework-for-Bijective-Maps\u8bba\u6587\u622a\u56fe.png 1519w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Simplicial-Complex-Augmentation-Framework-for-Bijective-Maps\u8bba\u6587\u622a\u56fe-300x87.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Simplicial-Complex-Augmentation-Framework-for-Bijective-Maps\u8bba\u6587\u622a\u56fe-768x221.png 768w\" sizes=\"(max-width: 1519px) 100vw, 1519px\" \/><\/p>\n<h4>16.3 Chart Packing<\/h4>\n<p>Chart Packing\u8fd9\u4e00\u6b65\u7684\u76ee\u6807\u662f\u7b97\u6cd5\u7ed3\u679c\u7684Packing\u6548\u7387\u5c3d\u53ef\u80fd\u5730\u9ad8, \u5373\u7f51\u683c\u5728\u8d34\u56fe\u4e0a\u5bf9\u5e94\u7684\u5757\u7684\u9762\u79ef\u603b\u548c\u4e0e\u8d34\u56fe\u9762\u79ef\u7684\u6bd4\u503c\u5c3d\u53ef\u80fd\u5730\u63a5\u8fd11.<\/p>\n<h3>P17: Chart Packing\u4e0eSimplification<\/h3>\n<p>\u672c\u8282\u4ecb\u7ecd\u7684\u5185\u5bb9\u81ea\u5df1\u90fd\u633a\u611f\u5174\u8da3\u7684, \u53ea\u53ef\u60dc\u5085\u5b5d\u660e\u8001\u5e08\u4ecb\u7ecd\u7684\u77e5\u8bc6\u70b9\u8fd8\u662f\u504f\u5165\u95e8, \u5e72\u8d27\u76f8\u6bd4\u8f83\u4e0a\u8282\u8bfe\u6765\u8bf4\u8fd8\u662f\u5c11\u4e00\u4e9b\u7684.<\/p>\n<h4>17.1 Chart Packing<\/h4>\n<p>\u4e3b\u8981\u4ecb\u7ecd\u4e86\u5085\u5b5d\u660e\u8001\u5e08\u4e0e\u5218\u5229\u521a\u8001\u5e08\u4e8eSiggraph 2019\u4e0a\u5408\u4f5c\u53d1\u8868\u7684\u6587\u7ae0, Atlas Refinement with Bounded Packing Efficiency. \u76ee\u524d\u4e0eChart Packing\u76f8\u5173\u7684\u7b97\u6cd5\u7684\u4e3b\u8981\u76ee\u6807\u5747\u975e\u63d0\u5347PE(Packing Efficiency), \u800c\u662f\u9488\u5bf9\u5176\u5b83\u7ea6\u675f, \u5982\u626d\u66f2\u7a0b\u5ea6\u8f83\u4f4e, \u5404\u4e09\u89d2\u9762\u7247\u671d\u5411\u4e00\u81f4, \u7f51\u683c\u65e0\u81ea\u4ea4, \u5272\u7ebf\u957f\u5ea6\u8f83\u77ed\u7b49, \u8fd9\u4e5f\u662f\u5085\u5b5d\u660e\u8001\u5e08\u8fd9\u7bc7\u6587\u7ae0\u7684\u4eae\u70b9\u4e4b\u4e00. \u7b97\u6cd5\u6d41\u7a0b\u5982\u4e0b\u56fe\u6240\u793a,<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Atlas-Refinement-with-Bounded-Packing-Efficiency.png\" alt=\"\" width=\"1920\" height=\"1080\" class=\"alignnone size-full wp-image-1310\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Atlas-Refinement-with-Bounded-Packing-Efficiency.png 1920w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Atlas-Refinement-with-Bounded-Packing-Efficiency-300x169.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Atlas-Refinement-with-Bounded-Packing-Efficiency-768x432.png 768w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Atlas-Refinement-with-Bounded-Packing-Efficiency-1536x864.png 1536w\" sizes=\"(max-width: 1920px) 100vw, 1920px\" \/><\/p>\n<p>\u8001\u5e08\u5e76\u6ca1\u6709\u4ecb\u7ecd\u7684\u5177\u4f53\u7684\u7b97\u6cd5\u7ec6\u8282, \u5305\u62ec\u81ea\u5df1\u66f4\u611f\u5174\u8da3\u7684PE\u4e0b\u786e\u754c\u8bc1\u660e=.= \u56e0\u6b64\u8fd9\u91cc\u4e5f\u4e0d\u518d\u4ecb\u7ecd, \u7b49\u65e5\u540e\u6709\u7a7a\u518d\u4ed4\u7ec6\u9605\u8bfb\u4e00\u4e0b\u8fd9\u7bc7\u8bba\u6587. PS: \u6587\u7ae0\u7b97\u6cd5\u7b2c\u4e00\u6b65\u7684\u601d\u60f3\u5176\u5b9e\u7c7b\u4f3c\u4e8e\u524d\u9762\u4ecb\u7ecd\u7684PolyCube\u7684\u76f8\u5173\u7b97\u6cd5\u601d\u60f3.<\/p>\n<h4>17.2 Simplification<\/h4>\n<p>$\\cdot$ <strong>Defination\u4e0eLocal Operations.<\/strong> Simplification\u662f\u628a\u4e00\u4e2a\u7ed9\u5b9a\u7684\u591a\u8fb9\u5f62\u7f51\u683c\u8f6c\u5316\u4e3a\u4e00\u4e2a\u542b\u6709\u66f4\u5c11\u7684\u70b9, \u7ebf\u4e0e\u9762\u7684\u7f51\u683c\u7684\u64cd\u4f5c, \u4e5f\u662f\u4e00\u79cd\u5728\u6e38\u620f\u5f00\u53d1\u4e2d\u5e94\u7528\u5341\u5206\u5e7f\u6cdb\u7684\u6280\u672f(\u5982LOD). <strong>\u5176\u8574\u542b\u7684Multi-Resolution\u601d\u60f3\u4e5f\u662f\u89e3\u51b3\u8bb8\u591a\u51e0\u4f55\u5904\u7406\u95ee\u9898\u7684\u5e38\u7528\u601d\u8def, \u5373\u628a\u5728\u4f4e\u5206\u8fa8\u7387\u7f51\u683c\u4e0a\u7684\u7ed3\u679c\u8fc1\u79fb\u81f3\u9ad8\u5206\u8fa8\u7387\u7f51\u683c\u4e0a.<\/strong><br \/>\n\u7531\u4e8e\u8bb8\u591aSimplification\u7b97\u6cd5\u662f\u8fed\u4ee3\u8fdb\u884c\u7684, \u5373\u5b83\u4eec\u901a\u8fc7\u6bcf\u6b21\u79fb\u9664\u4e00\u4e2a\u9876\u70b9\u6765\u5b9e\u73b0\u9010\u6b65\u7b80\u5316, \u56e0\u6b64\u8bb8\u591aSimplification\u7b97\u6cd5\u901a\u5e38\u662f\u53ef\u9006\u7684(\u5982Hierarchical Method), \u800c\u6bcf\u6b21\u79fb\u9664\u4e00\u4e2a\u9876\u70b9\u7684\u8fc7\u7a0b\u5219\u79f0\u4e4b\u4e3a\u4e00\u4e2a\u5c40\u90e8\u64cd\u4f5c(Local Operation). \u5c40\u90e8\u64cd\u4f5c\u7684\u65b9\u5f0f\u901a\u5e38\u6709Vertex Removal, Edge Collapse, Half-Edge Collapse\u7b49\u4e09\u79cd, \u5176\u4e2dEdge Collapse\u4e0eHalf-Edge Collapse\u5728\u62d3\u6251\u4e0a\u662f\u4e00\u81f4\u7684, \u533a\u522b\u53ea\u662f\u7ecfCollapse\u4ee5\u540e\u5f97\u5230\u7684\u65b0\u9876\u70b9\u7684\u4f4d\u7f6e\u4f1a\u6709\u6240\u4e0d\u540c.<\/p>\n<p>$\\cdot$ <strong>Quadric Error Metric(\u7b80\u79f0QEM).<\/strong> \u9996\u5148\u4e0d\u59a8\u6765\u770b\u770b\u5e73\u9762$P_i = (x_i, n_i)$\u4e0a\u7684QEM\u662f\u5982\u4f55\u5b9a\u4e49\u7684: \u70b9$x$\u5230\u5e73\u9762$P_i$\u7684\u8ddd\u79bb\u7684\u5e73\u65b9\u4e3a$$d(x,P_i) = (n^T_ix &#8211; d_i)^2,\\\\d_i = n^T_ix_i.$$\u91c7\u7528\u9f50\u6b21\u5750\u6807\u7684\u5f62\u5f0f\u8bb0$\\bar{x} = (x, 1), \\bar{n_i} = (n_i, -d_i)$. \u5219$$d(x, P_i) = (\\bar{n_i}^T\\bar{x})^2 = \\bar{x}^T\\bar{n_i}^T\\bar{n_i}\\bar{x} =: \\bar{x}^TQ_i\\bar{x}.$$\u800c\u9876\u70b9$v_i$\u4e0a\u7684QEM\u5219\u5b9a\u4e49\u4e3a$$Q^T_i = \\sum_{j \\in \\Omega(i)}Q_j.$$\u8fb9$e$\u4e0a\u7684QEM\u5b9a\u4e49\u4e3a$$Q^e = Q^v_1 + Q^v_2.$$\u8fd9\u6837\u4e00\u6765, \u6bcf\u4e00\u6b21\u5c40\u90e8\u64cd\u4f5c\u53ef\u4ee5\u8f6c\u5316\u4e3a\u4e00\u4e2a\u6700\u4f18\u5316\u95ee\u9898:$$\\bar{v} = arg \\min_{v} v^TQ^ev,$$\u5176\u4e2d, $Q^e$\u4e0d\u4e00\u5b9a\u662f\u4e00\u4e2a\u6ee1\u79e9\u77e9\u9635, \u5f53$Q^e$\u6ee1\u79e9\u65f6\u53ef\u76f4\u63a5\u91c7\u7528\u6700\u5c0f\u4e8c\u4e58\u6cd5\u6c42\u89e3, \u800c\u5f53$Q^e$\u4e0d\u6ee1\u79e9\u65f6\u5219\u6700\u5c0f\u4e8c\u4e58\u6cd5\u65e0\u6cd5\u751f\u6548\u4e86(\u6700\u5c0f\u5947\u5f02\u503c\u4e3a0), \u6b64\u65f6\u53d6\u8fb9$e$\u4e0a\u7684\u4e2d\u70b9\u4f5c\u4e3a\u5f53\u524d\u6700\u4f18\u5316\u95ee\u9898\u7684\u8fd1\u4f3c\u89e3\u5373\u53ef. \u540c\u65f6\u5b9a\u4e49\u65b0\u9876\u70b9$\\bar{v}$\u4e0a\u7684QEM\u4e3a$Q^e$. QEM\u7b97\u6cd5\u4f2a\u4ee3\u7801\u5982\u4e0b\u56fe\u6240\u793a,<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/QEM.png\" alt=\"\" width=\"708\" height=\"441\" class=\"alignnone size-full wp-image-1312\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/QEM.png 708w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/QEM-300x187.png 300w\" sizes=\"(max-width: 708px) 100vw, 708px\" \/><\/p>\n<p>$\\cdot$ <strong>Variational Shape Approximation(VSA).<\/strong> VSA\u662f\u4e00\u79cd\u4f7f\u7528\u5e73\u9762\u903c\u8fd1\u591a\u8fb9\u5f62\u7f51\u683c\u7684\u6280\u672f, \u4e0e\u524d\u9762\u4ecb\u7ecd\u7684Atlas Generation\u4e2d\u7684Segmentation\u601d\u60f3\u6bd4\u8f83\u7c7b\u4f3c. VSA\u672c\u8d28\u4e0a\u4fbf\u662f\u4e00\u79cdSegmentation\u65b9\u6cd5, \u53ea\u662f\u4f7f\u7528\u7684\u4ee3\u7406(\u53ef\u5c55\u66f2\u9762) \u88ab\u4e25\u683c\u9650\u5236\u4e3a\u5e73\u9762. VSA\u6240\u7814\u7a76\u7684\u95ee\u9898\u4e3a: \u7ed9\u5b9a$k \\in N$, \u4e09\u89d2\u7f51\u683c$M$\u4e0e\u8bef\u5dee\u5ea6\u91cf$E$($L^2$\u6216$L^{2,1}$), \u5bfb\u627e\u4e00\u4e2a\u533a\u57df\u96c6$R = \\{ R_1, \\cdots, R_k \\}$\u4e0e\u4e00\u4e2a\u4ee3\u7406\u96c6$P = \\{ P_1, \\cdots, P_k \\}$\u4f7f\u5f97\u4e0b\u8ff0\u5173\u4e8e\u626d\u66f2\u7a0b\u5ea6\u7684\u80fd\u91cf\u51fd\u6570\u6700\u5c0f,$$E(R, P) = \\sum^k_{i=1}E(R_i, P_i),$$\u5176\u4e2d,$$R_1 \\cup \\cdots \\cup R_k = M,\\\\P_i=(x_i, n_i), i \\in \\{ 1, \\cdots, k \\},$$\u800c$R_i$\u4e0e$P_i$\u4e4b\u95f4\u7684\u8bef\u5dee\u5ea6\u91cf\u6709\u4e24\u79cd\u5b9a\u4e49\u65b9\u5f0f, \u5206\u522b\u4e3a<br \/>\n$\\quad \\cdot$ $L^2$\u8bef\u5dee:$$L^2(R_i, P_i) = \\int_{x \\in R_i}(n^T_ix &#8211; n^T_ix_i)^2dx.$$$\\quad \\cdot$ $L^{2,1}$\u8bef\u5dee:$$L^{2,1}(R_i, P_i) = \\int_{x \\in R_i}\\left \\| n(x) &#8211; n_i \\right \\|^2 dx.$$\u5176\u4e2d, \u901a\u8fc7$L^2$\u8bef\u5dee\u5f97\u5230\u7684\u4ee3\u7406$P_i$\u4e3a\u4e00\u4e2a\u6700\u5c0f\u4e8c\u4e58\u62df\u5408\u5e73\u9762, \u800c\u901a\u8fc7$L^{2,1}$\u8bef\u5dee\u5f97\u5230\u7684\u4ee3\u7406$P_i$\u7684\u6cd5\u5411\u4e3a\u8f93\u5165\u7f51\u683c$M$\u7684\u6240\u6709\u9762\u6cd5\u5411\u7684\u52a0\u6743\u5e73\u5747\u503c. \u6c42\u89e3\u4e0a\u8ff0\u4f18\u5316\u95ee\u9898\u901a\u5e38\u91c7\u7528Lloyd\u7b97\u6cd5.<\/p>\n<h3>P18: Spherical Parameterizations<\/h3>\n<p>\u7403\u9762\u53c2\u6570\u5316\u662f\u4e00\u4e2a\u4e8f\u683c\u4e3a0\u7684\u95ed\u66f2\u9762\u4e0e\u7403\u9762\u4e4b\u95f4\u7684\u540c\u80da, \u5176\u7ea6\u675f\u4e3b\u8981\u6709\u4e09\u70b9, \u5206\u522b\u4e3a\u7403\u9762\u7ea6\u675f($x^2+y^2+z^2=r^2$, \u8fd9\u662f\u4e00\u4e2a\u975e\u7ebf\u6027\u4e14\u975e\u51f8\u7684\u7ea6\u675f), \u53cc\u5c04\u7ea6\u675f(\u53ef\u6839\u636e\u5b9e\u9645\u60c5\u51b5\u5f31\u5316\u4e3a\u65e0\u7ffb\u8f6c\u4e09\u89d2\u5f62\u7684\u7ea6\u675f) \u4e0e\u4f4e\u626d\u66f2\u7684\u7ea6\u675f. \u5728\u7403\u9762\u53c2\u6570\u5316\u9886\u57df, \u6700\u5927\u7684\u6311\u6218\u4e3b\u8981\u6709\u4e24\u4e2a: \u4e00\u4e2a\u662f\u65e0\u6cd5\u4f7f\u7528Tutte&#8217;s Embedding Method, \u56e0\u4e3a\u7403\u9762\u662f\u4e00\u4e2a\u95ed\u66f2\u9762; \u53e6\u5916\u4e00\u4e2a\u5219\u662f\u5f85\u6c42\u89e3\u7684\u6700\u4f18\u5316\u95ee\u9898\u662f\u975e\u7ebf\u6027\u4e0e\u975e\u51f8\u7684. \u76f8\u5173\u7b97\u6cd5\u4e3b\u8981\u6709\u4e24\u7c7b, \u5176\u5b9e\u672c\u8282\u6700\u540e\u8fd8\u63d0\u53ca\u4e86\u66f2\u7387\u6d41\u7684\u76f8\u5173\u7b97\u6cd5, \u4f46\u4ec5\u662f\u51e0\u53e5\u8bdd\u5e26\u8fc7, \u6545\u6b64\u5904\u4ea6\u4e0d\u4f5c\u8fc7\u591a\u8bb0\u5f55.<br \/>\n$\\cdot$ <strong>Hierarchical Method.<\/strong> \u4ee3\u8868\u8bba\u6587\u4e3aAdvanced Hierarchical Spherical Parameterizations, \u5176\u7b97\u6cd5\u6d41\u7a0b\u5982\u4e0b\u56fe\u6240\u793a,<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Advanced-Hierarchical-Spherical-Parameterizations.png\" alt=\"\" width=\"1537\" height=\"275\" class=\"alignnone size-full wp-image-1317\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Advanced-Hierarchical-Spherical-Parameterizations.png 1537w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Advanced-Hierarchical-Spherical-Parameterizations-300x54.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Advanced-Hierarchical-Spherical-Parameterizations-768x137.png 768w\" sizes=\"(max-width: 1537px) 100vw, 1537px\" \/><\/p>\n<p>\u5176\u4e2d, (a)-(d)\u5bf9\u5e94\u7684\u8fc7\u7a0b\u79f0\u4e3aDecimation(\u5373\u51cf\u9762), (e)-(g)\u5bf9\u5e94\u7684\u8fc7\u7a0b\u79f0\u4e3aRefinement(\u5373\u7ec6\u5206). \u672c\u8282\u91cd\u70b9\u4ecb\u7ecd\u4e86Decimation\u8fc7\u7a0b, Refinement\u8fc7\u7a0b\u8bb2\u5f97\u5341\u5206\u6a21\u7cca(\u7ec6\u8282\u53ef\u4ee5\u53c2\u8003\u6587\u7ae0Progressive Embedding\u9644\u5f55\u4e2d\u7684Vertex Split\u4e00\u8282). \u5728Decimation\u7684\u8fc7\u7a0b\u4e2d, \u4e3b\u8981\u6267\u884c\u4e86\u53bb\u9664\u9ad8\u66f2\u7387\u533a\u57df\u7684Simplicafation\u64cd\u4f5c, \u6240\u4f7f\u7528\u7684Curvature Error Metric(CEM) \u5b9a\u4e49\u5982\u4e0b,$$E^C_{jk}=\\frac{g(V_j)}{d_e(V_{kj}) \\cdot \\rho (V_{kj})},$$\u5176\u4e2d, \u5404\u7b26\u53f7\u5b9a\u4e49\u5982\u4e0b,<br \/>\n$\\quad \\cdot$ $g(V_j)$\u662f\u9876\u70b9$V_j$\u4e0a\u7684\u9ad8\u65af\u66f2\u7387;<br \/>\n$\\quad \\cdot$ $d_e(V_{kj}) = e^{(d(V_{kj})-6)^2}$, \u9876\u70b9$V_{kj}$\u662f\u7531\u9876\u70b9$V_k$\u4e0e\u9876\u70b9$V_j$\u574d\u7f29\u5f97\u5230\u7684\u65b0\u9876\u70b9, $d(V_{kj})$\u662f\u9876\u70b9$V_{kj}$\u7684\u5ea6;<br \/>\n$\\quad \\cdot$ $\\rho(V_{kj}) = \\sum_{f \\in \\Omega(V_{kj})} \\frac{c_r(f)}{2 \\times i_r(f)}$, $f$\u4e3a\u9876\u70b9$V_{kj}$\u8fde\u63a5\u7684\u9762, $c_r(f)$\u4e3a\u9762$f$\u7684\u5916\u63a5\u5706\u534a\u5f84, $i_r(f)$\u4e3a\u9762$f$\u7684\u5185\u5207\u5706\u534a\u5f84. \u5f53$f$\u6070\u4e3a\u6b63\u4e09\u89d2\u5f62\u65f6, $\\frac{c_r(f)}{2 \\times i_r(f)} = 1$, \u5426\u5219\u4e00\u822c\u5927\u4e8e1.<br \/>\n\u4ece\u4e0a\u8ff0\u5b9a\u4e49\u6613\u77e5, \u5f53\u9876\u70b9\u66f2\u7387\u8d8a\u9ad8\u6216\u8005\u9876\u70b9\u5468\u56f4\u7684\u4e09\u89d2\u9762\u5f62\u72b6\u8d8a&#8221;\u504f\u79bb&#8221;\u6b63\u4e09\u89d2\u5f62, \u8be5\u9876\u70b9\u8d8a\u5bb9\u6613\u5728Decimation\u7684\u8fc7\u7a0b\u5f53\u4e2d\u88ab\u79fb\u9664. \u6b64\u5916, \u82e5\u60f3\u5728Decimation\u7684\u8fc7\u7a0b\u5f53\u4e2d\u6267\u884c\u53bb\u9664\u4f4e\u66f2\u7387\u533a\u57df\u7684Simplicafation\u64cd\u4f5c, \u4ec5\u9700\u5c06\u4e0a\u8ff0CEM\u53d6\u5012\u6570\u4ee5\u540e\u4f5c\u4e3a\u65b0\u7684CEM\u5373\u53ef.<br \/>\n\u82e5Refinement\u8fc7\u7a0b\u7684\u8f93\u5165\u7f51\u683c\u5305\u542b\u8f83\u591a\u9ad8\u66f2\u7387\u533a\u57df, \u5219\u4f1a\u6781\u5927\u5730\u5f71\u54cd\u53c2\u6570\u5316\u7ed3\u679c\u7684\u9876\u70b9\u5206\u5e03(\u975e\u5747\u5300\u5206\u5e03). \u56e0\u6b64Decimation\u8fc7\u7a0b\u901a\u5e38\u4f7f\u7528Flat-to-Extrusive Decimation\u7b56\u7565: \u5148\u901a\u8fc7QEM\u8fdb\u884cSimplification, \u518d\u901a\u8fc7CEM\u53bb\u9664\u9ad8\u66f2\u7387\u533a\u57df.<\/p>\n<p>$\\cdot$ <strong>Two Hemisphers.<\/strong> \u6d41\u7a0b\u5982\u4e0b\u56fe\u6240\u793a:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Two-Hemisphers.png\" alt=\"\" width=\"1582\" height=\"673\" class=\"alignnone size-full wp-image-1322\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Two-Hemisphers.png 1582w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Two-Hemisphers-300x128.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Two-Hemisphers-768x327.png 768w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Two-Hemisphers-1536x653.png 1536w\" sizes=\"(max-width: 1582px) 100vw, 1582px\" \/><\/p>\n<p>\u5373\u628a\u4e00\u4e2a\u4e8f\u683c\u4e3a0\u7684\u95ed\u66f2\u9762\u4e00\u5206\u4e3a\u4e8c\u53d8\u6210\u4e24\u4e2a\u5f00\u7f51\u683c, \u5982\u6b64\u4e00\u6765\u53ef\u4ee5\u5229\u7528Tutte&#8217;s Embedding\u4e0e\u7403\u6781\u6295\u5f71\u5206\u522b\u6620\u5c04\u5230\u4e24\u4e2a\u534a\u7403\u9762\u4e0a, \u6700\u540e\u5c06\u4e24\u4e2a\u534a\u7403\u9762\u4e0a\u7684\u53c2\u6570\u5316\u7ed3\u679c\u62fc\u63a5\u8d77\u6765\u5373\u53ef, \u5982\u4e0b\u56fe\u6240\u793a. \u5176\u4e2d, \u4ece(b)\u5230(c)\u7684\u8fc7\u7a0b\u4e2d, \u7b97\u6cd5\u5229\u7528\u4e86\u590d\u53d8\u51fd\u6570$f(z) = \\frac{1}{\\bar{z}}$\u7684\u6027\u8d28, \u5c06\u5355\u4f4d\u5706\u5185\u7684\u70b9\u6620\u5c04\u81f3\u5355\u4f4d\u5706\u5916, \u8fd9\u662f\u4e2a\u5f88\u6709\u610f\u601d\u7684\u70b9.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Two-Hemisphers-1.png\" alt=\"\" width=\"1715\" height=\"894\" class=\"alignnone size-full wp-image-1323\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Two-Hemisphers-1.png 1715w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Two-Hemisphers-1-300x156.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Two-Hemisphers-1-768x400.png 768w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Two-Hemisphers-1-1536x801.png 1536w\" sizes=\"(max-width: 1715px) 100vw, 1715px\" \/><\/p>\n<p>\u7b97\u6cd5\u5b58\u5728\u4e24\u4e2a\u95ee\u9898, \u5206\u522b\u662f<br \/>\n$\\quad \\cdot$ \u5982\u4f55\u9009\u62e9\u5272\u7f1d? \u7b97\u6cd5\u4f7f\u7528\u4e86Metis\u5e93<strong>(\u8fd9\u4e5f\u662fUE5\u7684Nanite\u6240\u4f7f\u7528\u5230\u7684\u5e93, \u672a\u6765\u4e5f\u8bb8\u503c\u5f97\u7814\u7a76)<\/strong>, \u5c06\u8f93\u5165\u7f51\u683c\u5212\u5206\u4e3a\u9876\u70b9\u6570\u76ee\u5927\u81f4\u76f8\u5f53\u7684\u4e24\u90e8\u5206.<br \/>\n$\\quad \\cdot$ \u5982\u4f55\u5c06\u5e73\u9762\u4e0a\u7684\u53c2\u6570\u5316\u7ed3\u679c\u8fc1\u79fb\u81f3\u7403\u4e0a?<br \/>\n$\\quad \\quad \\cdot$ Moebius Inversion$f(z) = \\frac{1}{\\bar{z}}$, \u8be5\u51fd\u6570\u53ef\u5c06\u5355\u4f4d\u5706\u5185\u7684\u70b9\u6620\u5c04\u81f3\u5355\u4f4d\u5706\u5916.<br \/>\n$\\quad \\quad \\cdot$ \u4f7f\u7528\u7403\u6781\u6295\u5f71\u5c06\u7ed3\u679c\u6620\u5c04\u81f3\u5355\u4f4d\u7403\u4e0a, \u5f62\u5f0f\u5982\u4e0b:$$P(u,v) = \\frac{1}{1 + u^2 + v^2}(2u, 2v, 1 &#8211; u^2 &#8211; v^2).$$<\/p>\n<h3>P19: Directional Field<\/h3>\n<h4>19.1 Introduction<\/h4>\n<p>\u65b9\u5411\u573a\u662f\u4e00\u4e2a\u70b9\u7684\u96c6\u5408, \u5176\u4e2d\u6bcf\u4e2a\u70b9\u4e0d\u4ec5\u5305\u542b\u4f4d\u7f6e\u4fe1\u606f, \u8fd8\u5305\u542b\u7279\u5b9a\u7684\u65b9\u5411\u4fe1\u606f, \u5e38\u89c1\u7684\u65b9\u5411\u573a\u6709\u6cd5\u5411\u573a, \u66f2\u7387\u573a\u7b49. \u5177\u5907\u65cb\u8f6c\u5bf9\u79f0\u6027\u7684\u65b9\u5411\u573a\u79f0\u4e3a\u65cb\u8f6c\u5bf9\u79f0\u65b9\u5411\u573a(Rotationally-Symmetric Directional Field, \u7b80\u79f0RoSy\u573a), \u5373\u5176\u4e0a\u6bcf\u4e2a\u70b9\u7684\u65b9\u5411\u4e4b\u95f4\u7684\u89d2\u5ea6\u53ef\u80fd\u662f\u56fa\u5b9a\u7684, \u5e38\u89c1\u7684RoSy\u573a\u5982\u4e0b\u56fe\u6240\u793a.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field.png\" alt=\"\" width=\"766\" height=\"787\" class=\"aligncenter size-full wp-image-1336\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field.png 766w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field-292x300.png 292w\" sizes=\"(max-width: 766px) 100vw, 766px\" \/><\/p>\n<p>\u89c2\u5bdf\u4e0a\u56fe\u53ef\u4ee5\u53d1\u73b0, \u5bf9\u4e8e$a^b$-Vector(Directional) Field\u4e2d\u6bcf\u4e2a\u70b9\u4e0a\u7684$a \\times b$\u4e2a\u65b9\u5411, \u53ef\u5c06\u5176\u5206\u4e3a$b$\u4e2a\u7ec4, \u6bcf\u4e2a\u7ec4\u5185\u542b$a$\u4e2a\u65b9\u5411, \u4e14\u6bcf\u4e2a\u7ec4\u5185\u7684\u76f8\u90bb\u65b9\u5411\u76f8\u5bf9\u4e8e\u5e73\u9762\u4e0a\u67d0\u4e2a\u8f74\u7684\u89d2\u5ea6\u5747\u76f8\u5dee$2 \\pi \/ a$. \u5176\u4e2d, 4-Directional Field\u53c8\u88ab\u79f0\u4e3aCross Field, $2^2$-Vector Field\u53c8\u88ab\u79f0\u4e3aFrame Field, \u662f\u7ecf\u5e38\u4f7f\u7528\u7684\u4e24\u4e2a\u65b9\u5411\u573a.<br \/>\n\u4ece\u65b9\u5411\u573a\u7684\u89d2\u5ea6\u6765\u770b, \u7b49\u8ddd\u53c2\u6570\u5316\u5176\u5b9e\u4e5f\u662f\u4e00\u4e2a\u65b9\u5411\u573a\u7684\u62df\u5408\u8fc7\u7a0b, \u56de\u987eP6 6.1\u4e2d\u63d0\u5230\u7684LSCM\u7b97\u6cd5, LSCM\u5b9a\u4e49\u4e86\u4e00\u4e2a\u80fd\u91cf\u51fd\u6570, \u8be5\u80fd\u91cf\u51fd\u6570\u63cf\u8ff0\u4e86\u5f53\u524d\u7f51\u683c\u6bcf\u4e2a\u4e09\u89d2\u9762\u7247\u4e0a\u7684Jacobi\u77e9\u9635($2 \\times 2$) \u4e0e\u76ee\u6807\u65cb\u8f6c\u77e9\u9635\u7684\u8ddd\u79bb, \u6b64\u65f6\u76ee\u6807\u65cb\u8f6c\u77e9\u9635\u53ef\u4ee5\u770b\u6210\u662f\u4e24\u4e2a\u76f8\u4e92\u6b63\u4ea4\u7684\u5217\u5411\u91cf\u7684\u7ec4\u5408, \u6781\u5c0f\u5316\u8be5\u80fd\u91cf\u51fd\u6570\u7684\u8fc7\u7a0b\u4ea6\u662f\u4e00\u4e2a\u65b9\u5411\u573a\u7684\u62df\u5408\u8fc7\u7a0b. \u9664\u4e86\u5728\u53c2\u6570\u5316\u9886\u57df\u7684\u5e94\u7528\u4e4b\u5916, \u7f51\u683c\u751f\u6210, \u516d\u9762\u4f53\u7f51\u683c\u5316, \u53d8\u5f62, \u7eb9\u7406\u6620\u5c04\u4e0e\u5efa\u7b51\u51e0\u4f55\u7b49\u9886\u57df\u4e5f\u90fd\u80fd\u89c1\u5230\u65b9\u5411\u573a\u7684\u8eab\u5f71.<\/p>\n<h4>19.2 Discretization<\/h4>\n<p>\u672c\u5c0f\u8282\u4ecb\u7ecd\u7684\u6982\u5ff5\u662f\u4e3a\u4e86\u5f97\u5230\u7f51\u683c\u4e0a&#8221;\u8fde\u7eed&#8221;\u7684\u65b9\u5411\u573a. \u9996\u5148\u4ecb\u7ecd\u4e86\u5207\u7a7a\u95f4\u7684\u5b9a\u4e49, \u6b64\u5904\u5e76\u4e0d\u7ea0\u7ed3\u4e8e\u5207\u7ebf\u4e0e\u526f\u5207\u7ebf\u7684\u8ba1\u7b97, \u56e0\u6b64\u76f8\u6bd4\u8f83\u6e32\u67d3\u4e2d\u7684\u5207\u7a7a\u95f4, \u7406\u89e3\u96be\u5ea6\u8fd8\u662f\u4f4e\u5f88\u591a\u7684. \u5728\u8fdb\u884c\u4e24\u4e2a\u76f8\u90bb\u5207\u7a7a\u95f4\u7684\u65b9\u5411\u573a\u6bd4\u8f83\u524d, \u9700\u8981\u5efa\u7acb\u4e24\u4e2a\u5207\u7a7a\u95f4\u4e4b\u95f4\u7684Connection, \u6700\u5e38\u7528\u7684Connection\u662fLevi-Civita Connection, \u5efa\u7acb\u7684\u65b9\u6cd5\u4e5f\u5341\u5206\u7b80\u5355, \u76f4\u63a5\u5c06\u5176\u4e2d\u4e00\u4e2a\u5207\u7a7a\u95f4\u8fdb\u884c\u65cb\u8f6c, \u76f4\u81f3\u5176\u6cd5\u5411\u4e0e\u53e6\u5916\u4e00\u4e2a\u5207\u7a7a\u95f4\u7684\u6cd5\u5411\u4e00\u81f4\u5373\u53ef. \u4ece\u53c2\u6570\u5316\u7684\u89d2\u5ea6\u6765\u770b, \u8fd9\u4e2a\u64cd\u4f5c\u4e5f\u662f\u4e00\u79cd\u5c40\u90e8\u53c2\u6570\u5316, \u7ed3\u679c\u4fbf\u662f\u5c06\u4e24\u4e2a\u76f8\u90bb\u7684\u5207\u7a7a\u95f4\u644a\u5e73\u5230\u540c\u4e00\u4e2a\u5e73\u9762\u4e0a, \u4ece\u800c\u65b9\u5411\u573a\u7684\u6bd4\u8f83\u80fd\u5728\u540c\u4e00\u4e2a\u5750\u6807\u7cfb\u4e0b\u8fdb\u884c.<br \/>\n\u63a5\u4e0b\u6765\u5b9a\u4e49\u4e86\u65b9\u5411\u573a\u4e2d\u7684\u5947\u5f02\u70b9, \u5373\u8be5\u70b9\u5904\u7684\u65b9\u5411\u4e0d\u662fWell-Defined\u7684, \u7528\u6307\u6807\u7684\u8bed\u8a00\u63cf\u8ff0\u5373\u6307\u6807\u4e3a0\u7684\u70b9.<br \/>\n$\\cdot$ \u8fde\u7eed\u65b9\u5411\u573a\u4e2d\u70b9$p$\u7684\u6307\u6807\u5b9a\u4e49\u5982\u4e0b,$$index_p = \\frac{1}{2\\pi}(\\alpha(1) &#8211; \\alpha(0)),$$$\\alpha$\u901a\u5e38\u662f\u8fde\u7eed\u7684, $\\alpha(1) &#8211; \\alpha(0)$\u552f\u4e00\u4e14\u6070\u4e3a$2\\pi$\u7684\u500d\u6570. \u4e14\u7531Poincare-Hopf\u5b9a\u7406\u77e5\u95ed\u66f2\u9762\u4e0a\u7684\u5411\u91cf\u573a\u4e0a\u7684\u6240\u6709\u70b9\u7684\u6307\u6807\u4e4b\u548c\u4e3a$2-2g$, \u5176\u4e2d, $g$\u4e3a\u95ed\u66f2\u9762\u7684\u4e8f\u683c.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field-Singularity-Point.png\" alt=\"\" width=\"391\" height=\"375\" class=\"aligncenter size-full wp-image-1337\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field-Singularity-Point.png 781w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field-Singularity-Point-300x288.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field-Singularity-Point-768x738.png 768w\" sizes=\"(max-width: 391px) 100vw, 391px\" \/><\/p>\n<p>$\\cdot$ \u79bb\u6563$N$-RoSy\u573a\u4e2d, \u5bf9\u4e8e\u4e09\u89d2\u7f51\u683c\u4e0a\u7684\u540c\u4e00\u4e2a\u9762\u800c\u8a00, \u5176\u4e0a\u6bcf\u4e2a\u70b9\u7684\u65b9\u5411\u90fd\u662f\u4e00\u81f4\u7684(\u5747\u4e0e\u5f53\u524d\u9762\u5e73\u884c), \u5947\u5f02\u70b9\u4ec5\u80fd\u51fa\u73b0\u5728\u8fb9\u4e0a. \u6b64\u65f6\u70b9$p$\u7684\u6307\u6807\u5b9a\u4e49\u5982\u4e0b,$$index_p = \\frac{1}{2\\pi} \\sum (\\delta_{ij} + 2\\pi k),$$\u5176\u4e2d, $k \\in N$\u79f0\u4e3aPeriod Jump, $\\delta_{ij} \\in [-\\pi, \\pi)$\u662f\u7ecf\u5efa\u7acbLevi-Civita Connection\u540e\u5207\u7a7a\u95f4$X_i$\u4e0e\u5207\u7a7a\u95f4$X_j$($p \\in X_i \\cap X_j$) \u5bf9\u5e94\u65b9\u5411\u7684\u65cb\u8f6c\u89d2\u5ea6(\u5bf9\u5e94\u65b9\u5411\u7684\u65cb\u8f6c\u89d2\u5ea6\u90fd\u662f\u4e00\u6837\u7684?), \u5982\u4e0b\u56fe\u6240\u793a. \u9700\u8981\u6ce8\u610f\u7684\u662f, $\\delta_{ij}$\u4f1a\u53d7\u5207\u7a7a\u95f4$X_i$\u4e0e\u5207\u7a7a\u95f4$X_j$\u7684\u5bf9\u5e94\u65b9\u5411\u7684\u9009\u53d6\u65b9\u5f0f\u7684\u5f71\u54cd, \u5728\u4e0d\u540c\u7684\u9009\u53d6\u65b9\u5f0f\u4e4b\u95f4, \u4e0d\u540c\u7684$\\delta_{ij}$\u5c06\u76f8\u5dee$2\\pi k \/ N, k \\in N$, \u901a\u5e38\u9009\u53d6\u7684$k$\u503c\u9700\u8981\u4f7f\u5f97$\\delta_{ij}$\u6700\u5c0f.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field-Rotation.png\" alt=\"\" width=\"882\" height=\"815\" class=\"aligncenter size-full wp-image-1339\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field-Rotation.png 882w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field-Rotation-300x277.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Directional-Field-Rotation-768x710.png 768w\" sizes=\"(max-width: 882px) 100vw, 882px\" \/><\/p>\n<h4>19.3 Representation<\/h4>\n<p>\u7531\u4e0a\u8ff0\u8ba8\u8bba\u6574\u7406\u53ef\u5f97, \u79bb\u6563$N$-RoSy\u573a\u4e2d, \u8bbe\u5207\u7a7a\u95f4$X_i$\u4e0e\u5207\u7a7a\u95f4$X_j$\u4e0a\u7684\u5c40\u90e8\u6807\u67b6\u5206\u522b\u4e3a$\\{ e_{i1}, e_{i2}\\}, \\{ e_{j1}, e_{j2}\\}$, \u5219$X_i$\u4e0e$X_j$\u4e4b\u95f4\u7684$\\delta_{ij} \\in [-\\pi, \\pi)$\u53ef\u5b9a\u4e49\u5982\u4e0b$$\\delta_{ij} = \\phi_j &#8211; (\\phi_i + X_{ij} + \\frac{2\\pi}{N}k_{ij}),$$\u5176\u4e2d, $\\phi_i$\u4e3a$X_i$\u4e2d\u4efb\u4e00\u70b9$x_i$\u4e0a\u7684\u6307\u5b9a\u65b9\u5411\u76f8\u5bf9\u4e8e$e_{i1}$\u7684\u5e26\u7b26\u53f7\u65cb\u8f6c\u89d2\u5ea6, $X_{ij}$\u4e3a\u7ecf\u5efa\u7acbLevi-Civita Connection\u540e\u5207\u7a7a\u95f4$X_i$\u4e0e\u5207\u7a7a\u95f4$X_j$($p \\in X_i \\cap X_j$) \u5bf9\u5e94\u5750\u6807\u8f74\u7684\u65cb\u8f6c\u89d2\u5ea6, $k_{ij} \\in N$\u4e3aPeriod Jump. \u6613\u77e5, \u4f7f\u7528Period Jump\u53ef\u4ee5\u4f7f\u5f97\u5efa\u7acb\u7684\u6a21\u578b\u6e05\u6670\u6613\u61c2, \u4f46\u4e5f\u5f15\u5165\u4e86\u6574\u6570\u89c4\u5212\u95ee\u9898.<\/p>\n<p>\u4e3a\u4e86\u89c4\u907f\u6574\u6570\u89c4\u5212\u95ee\u9898, \u4e5f\u6709\u5b66\u8005\u4f7f\u7528\u4e09\u89d2\u51fd\u6570\u7684\u5f62\u5f0f\u8868\u793a\u65b9\u5411, \u5373$v=(cos\\phi, sin\\phi)^T = e^{i\\phi}$, \u5982\u6b64\u4e00\u6765\u4fbf\u53ef\u89c4\u5212Period Jump\u7684\u4f7f\u7528, \u4f46\u4e5f\u540c\u6837\u5f15\u5165\u4e86\u975e\u7ebf\u6027\u4f18\u5316\u95ee\u9898, \u56e0\u6b64\u8fd9\u79cd\u8868\u793a\u65b9\u6cd5\u4e5f\u5e76\u4e0d\u5e38\u7528. \u76ee\u524d\u66f4\u88ab\u8ba4\u53ef\u7684\u8868\u793a\u65b9\u6cd5\u662f\u590d\u6570\u591a\u9879\u5f0f.<\/p>\n<p>\u5bf9\u4e8e$N$-\u5411\u91cf\u96c6$\\{ u_1, \\cdots, u_N \\}, u_i \\in C$, \u53ef\u5f97\u5176\u5bf9\u5e94\u7684\u590d\u6570\u591a\u9879\u5f0f$$p(z) = (z &#8211; u_1)\\cdots(z &#8211; u_N) = {\\textstyle  \\sum_i^N } c_iz^i,$$\u5219\u5176\u7cfb\u6570\u96c6$\\{ c_i \\}$\u662f\u4e00\u4e2a2\u7ef4\u5411\u91cf\u7684\u987a\u5e8f\u65e0\u5173\u7684\u8868\u793a. \u4f7f\u7528\u590d\u6570\u591a\u9879\u5f0f\u8868\u793a\u79bb\u6563$N$-RoSy\u573a\u7684\u4e00\u4e2a\u6700\u5927\u7684\u4f18\u70b9\u4fbf\u662f\u7528\u5e42\u8fd0\u7b97\u89c4\u907f\u4e86\u6574\u6570\u89c4\u5212\u95ee\u9898: \u76f8\u90bb\u7684$u_i, i \\in [1,\\cdots,N]$\u7684\u76f8\u5bf9\u4e8e\u7279\u5b9a\u5750\u6807\u8f74\u7684\u65cb\u8f6c\u89d2\u4e4b\u95f4\u603b\u662f\u76f8\u5dee$\\frac{2\\pi}{N}$, \u5219\u5bf9\u4e8e$\\forall i \\in [1,\\cdots,N]$, \u5c06$u_i$\u65cb\u8f6c$\\frac{2\\pi}{N}$\u82e5\u5e72\u6b21\u4ee5\u540e\u603b\u80fd\u5f97\u5230\u4e00\u4e2a\u7279\u5b9a\u7684$u_k, k \\in [1,\\cdots,N]$, \u4e0d\u59a8\u7528$u_1$\u8868\u793a\u5176\u5b83$u_i, i \\ne 1$, \u5219$p(z) = z^N + \\cdots + (-1)^Nu_1^N$, \u663e\u7136\u89c4\u907f\u4e86\u6574\u6570\u89c4\u5212\u95ee\u9898. \u8fd9\u6837\u4e00\u6765, \u6bd4\u8f83\u4e24\u4e2a\u5207\u7a7a\u95f4\u4e0a\u7684\u79bb\u6563$N$-RoSy\u573a, \u4ec5\u9700\u6bd4\u8f83\u5bf9\u5e94\u7684\u590d\u6570\u591a\u9879\u5f0f\u7cfb\u6570\u96c6$\\{ c_i \\}$\u5373\u53ef.<\/p>\n<h3>P20: Directional Field\u4e2d\u7684Objectives and Constraints<\/h3>\n<h4>20.1 Objectives<\/h4>\n<p>\u5728\u4e0d\u540c\u7684\u5e94\u7528\u9886\u57df\u4e2d, \u901a\u5e38\u4f1a\u4f7f\u7528\u4e0d\u540c\u7684\u80fd\u91cf\u51fd\u6570\u7528\u4e8e\u4f18\u5316\u65b9\u5411\u573a, \u6240\u671f\u671b\u5f97\u5230\u7684\u65b9\u5411\u573a\u7684\u6027\u8d28\u4e5f\u4f1a\u6709\u6240\u4e0d\u540c, \u5982\u5149\u6ed1\u6027, \u5e73\u884c\u6027, \u6b63\u4ea4\u6027\u4e0e\u65cb\u5ea6\u6781\u5c0f\u6027\u7b49. \u4ee5\u5e73\u884c\u6027\u4e3a\u4f8b, \u5176\u80fd\u91cf\u51fd\u6570\u901a\u5e38\u8bbe\u7f6e\u4e3a\u5982\u4e0b\u5f62\u5f0f:$$E_{fair-N} = \\frac{N}{2} \\sum_e w_e(\\delta_e)^2.$$\u5f53\u4f7f\u7528\u7684\u65b9\u5411\u573a\u4e3aCross Field\u65f6, \u4e0a\u8ff0\u80fd\u91cf\u51fd\u6570\u5373\u53ef\u5199\u4e3a$$E_{fair-4} = \\frac{4}{2} \\sum_e w_e(\\phi_j &#8211; (\\phi_i + X_{ij} + \\frac{2\\pi}{N}k_{ij}))^2,$$\u5176\u4e2d\u5404\u7b26\u53f7\u542b\u4e49\u8be6\u89c1\u4e0a\u8282, \u6b64\u5904\u4e0d\u518d\u8d58\u8ff0.<\/p>\n<p>\u7531\u4e8e$k_{ij}$\u4e3a\u6574\u6570, \u4e0a\u8ff0\u6700\u4f18\u5316\u95ee\u9898\u7684\u6c42\u89e3\u96be\u5ea6\u662f\u6bd4\u8f83\u5927\u7684. \u4e00\u79cd\u5e38\u7528\u7684\u8d2a\u5fc3\u7b97\u6cd5\u4e3a:<br \/>\n1. \u5c06$k_{ij}$\u89c6\u4e3a\u5b9e\u6570, \u518d\u6781\u5c0f\u5316$E_{fair-4}$.<br \/>\n2. \u5bf9\u4e0a\u8ff0\u6b65\u9aa4\u6c42\u5f97\u7684$k_{ij}$\u8fdb\u884c\u53d6\u6574(\u5982\u56db\u820d\u4e94\u5165).<br \/>\n3. \u91cd\u590d\u4e0a\u8ff0\u4e24\u6b65.<br \/>\n\u5f53\u7136\u4e5f\u53ef\u4ee5\u4f7f\u7528\u4e0a\u8282\u4ecb\u7ecd\u7684\u590d\u6570\u591a\u9879\u5f0f\u8868\u793a, \u6765\u89c4\u907f\u6574\u6570$k_{ij}$\u5e26\u6765\u7684\u6574\u6570\u89c4\u5212\u95ee\u9898. \u4f46\u9700\u8981\u6ce8\u610f\u7684\u662f, \u82e5\u4f7f\u7528\u590d\u6570\u591a\u9879\u5f0f\u8868\u793a\u4e0a\u8ff0\u6700\u4f18\u5316\u95ee\u9898, \u4e14\u4e0d\u52a0\u7ea6\u675f, \u6c42\u5f97\u7684\u5404\u4e2a\u9762\u4e0a\u7684\u65b9\u5411\u573a\u4e2d\u5bb9\u6613\u51fa\u73b0\u9000\u5316\u7684\u60c5\u51b5(\u65b9\u5411\u5168\u4e3a0), \u56e0\u6b64\u5728\u6c42\u89e3\u4e0a\u8ff0\u6700\u4f18\u5316\u95ee\u9898\u65f6, \u9700\u8981\u786e\u5b9a\u4e24\u4e2a\u9762\u4e0a\u7684\u65b9\u5411\u573a, \u4ee5\u6b64\u4f5c\u4e3a\u7ea6\u675f.<\/p>\n<h4>20.2 Constraints<\/h4>\n<p>\u6c42\u89e3\u65b9\u5411\u573a\u7684\u8fc7\u7a0b\u4e2d\u5e38\u89c1\u7684\u7ea6\u675f\u4e3b\u8981\u6709\u4e09\u79cd.<br \/>\n$\\cdot$ <strong>\u5bf9\u9f50\u7ea6\u675f.<\/strong> \u5373\u6c42\u5f97\u7684\u65b9\u5411\u573a\u4e2d\u7684\u65b9\u5411\u9700\u8981\u4e0e\u9884\u5b9a\u4e49\u7684\u65b9\u5411\u5bf9\u9f50, \u9884\u5b9a\u4e49\u7684\u65b9\u5411\u53ef\u4ee5\u4ece\u4e3b\u66f2\u7387, \u8fb9\u754c, \u7279\u5f81\u7ebf\u6216\u8005\u7528\u6237\u81ea\u5b9a\u4e49\u7684\u66f2\u7ebf\u4e2d\u5f97\u5230.<br \/>\n$\\cdot$ <strong>\u5bf9\u79f0\u7ea6\u675f.<\/strong> \u82e5\u7f51\u683c\u8868\u9762\u5177\u6709\u53cc\u8fb9\u5bf9\u79f0\u6027, \u5219\u6c42\u5f97\u7684\u65b9\u5411\u573a\u4e5f\u5e94\u9075\u5faa\u76f8\u540c\u7684\u5bf9\u79f0\u6027.<br \/>\n$\\cdot$ <strong>\u66f2\u9762\u6620\u5c04\u7ea6\u675f.<\/strong> \u5bf9\u4e24\u4e2a\u5177\u6709\u5bf9\u5e94\u5173\u7cfb\u7684\u7f51\u683c, \u5176\u65b9\u5411\u573a\u4e5f\u5e94\u5177\u6709\u5bf9\u5e94\u5173\u7cfb.<\/p>\n<h4>20.3 Integrable field<\/h4>\n<p>\u4e0d\u59a8\u5c06\u4e00\u4e2a\u7f51\u683c\u8868\u9762\u4e0a\u7684\u8fde\u7eed\u65b9\u5411\u573a\u89c6\u4e3a\u7f51\u683c\u8868\u9762\u4e0a\u7684\u4e00\u4e2a\u8fde\u7eed\u591a\u503c\u51fd\u6570, \u8be5\u591a\u503c\u51fd\u6570\u7684\u503c\u57df\u7ef4\u5ea6\u4e3a$n$, \u5c06\u8be5\u591a\u503c\u51fd\u6570&#8221;\u62c6\u5206&#8221;\u4e3a$n$\u4e2a\u5b9e\u503c\u51fd\u6570, \u82e5\u8fd9$n$\u4e2a\u5b9e\u503c\u51fd\u6570\u5747\u5728\u7f51\u683c\u8868\u9762\u4e0a\u53ef\u79ef, \u5219\u79f0\u8be5\u8fde\u7eed\u65b9\u5411\u573a\u4e3a\u4e00\u4e2a\u53ef\u79ef\u573a. \u4e00\u4e2a\u5e38\u89c1\u7684\u53ef\u79ef\u573a\u4e3a\u53c2\u6570\u5316\u8fc7\u7a0b\u4e2d\u4f7f\u7528\u7684\u65b9\u5411\u573a\u7684\u68af\u5ea6\u573a, \u8be5\u65b9\u5411\u573a\u5bf9\u5e94\u7684\u4e24\u4e2a\u6807\u91cf\u51fd\u6570\u5747\u5728\u6bcf\u4e2a\u7f51\u683c\u9876\u70b9\u4e0a\u662fWell-Defined\u7684. \u53ef\u79ef\u573a\u4e5f\u63d0\u4f9b\u4e86\u53e6\u5916\u4e00\u4e2a\u53c2\u6570\u5316\u7684\u601d\u8def, \u5373\u5c06\u4f18\u5316\u5f97\u5230\u7684\u68af\u5ea6\u573a\u8fdb\u884c\u79ef\u5206, \u5373\u53ef\u5f97\u5230\u53c2\u6570\u5316\u7ed3\u679c.<\/p>\n<p>\u53ef\u79ef\u7684\u4e00\u4e2a\u5145\u8981\u6761\u4ef6\u662f\u65cb\u5ea6\u4e3a0(\u65e0\u65cb, \u8be5\u5145\u8981\u6761\u4ef6\u5f85\u6c42\u8bc1). \u5bf9\u4e8e\u4efb\u610f\u6807\u91cf\u51fd\u6570$h:M \\to R$, \u6709$$\\left \\langle \\nabla h_f,e \\right \\rangle = \\left \\langle \\nabla h_g,e \\right \\rangle,$$\u5176\u4e2d, $f,g$\u4e3a\u4e24\u4e2a\u76f8\u90bb\u7684\u4e09\u89d2\u5f62, \u5176\u516c\u5171\u8fb9\u4e3a$e$. \u5219\u5bf9\u4e8e\u4efb\u610f1-Vector Field $\\alpha$, $\\alpha$\u65e0\u65cb\u7684\u5145\u8981\u6761\u4ef6\u4e3a$\\left \\langle \\nabla \\alpha_f,e \\right \\rangle = \\left \\langle \\nabla \\alpha_g,e \\right \\rangle.$<\/p>\n<p>$\\cdot$ Cross Field\u7684\u65e0\u65cb\u5316<\/p>\n<p>\u8bba\u6587Computing Inversion-Free Mappings By Simplex Assembly\u4e2d\u4f7f\u7528\u4e86\u8fd9\u6837\u4e00\u4e2a\u80fd\u91cf\u51fd\u6570$$E = E_C + \\lambda E_{Field},\\\\E_{Field} = \\sum_e (\\left \\langle \\alpha_f,e \\right \\rangle &#8211; \\left \\langle \\alpha_g,e \\right \\rangle)^2 + (\\left \\langle \\beta_f,e \\right \\rangle &#8211; \\left \\langle \\beta_g,e \\right \\rangle)^2,$$\u5176\u4e2d, $E_C$\u662f\u4e00\u4e2a\u4e0e\u626d\u66f2\u7a0b\u5ea6\u76f8\u5173\u7684\u80fd\u91cf\u51fd\u6570. \u7b97\u6cd5\u8fdb\u884c\u7684\u8fc7\u7a0b\u4e2d, \u4f1a\u9010\u6b65\u589e\u52a0$\\lambda$, \u4f7f\u5f97\u5728\u6700\u7ec8\u7684\u4f18\u5316\u7ed3\u679c\u4e2d$E_{Field}$\u8d8b\u8fd1\u4e8e0. \u7136\u800c, \u7b97\u6cd5\u7ed3\u679c\u5e76\u4e0d\u80fd\u4fdd\u8bc1\u7f51\u683c\u4e0a\u6bcf\u4e2a\u70b9\u4e0a\u7684\u4e24\u4e2a\u65b9\u5411\u662f\u6b63\u4ea4\u7684, \u6211\u4eec\u53ef\u4ee5\u5c06\u4e24\u4e2a\u65b9\u5411\u5206\u522b\u5f80\u53cd\u65b9\u5411\u5ef6\u4f38, \u8fd9\u6837\u4fbf\u5f97\u5230\u4e86\u4e00\u4e2aFrame Field, \u5982\u4e0b\u56fe\u6240\u793a. \u8fd9\u6837\u4e00\u6765, \u6211\u4eec\u4fbf\u5c06Cross Field\u65e0\u65cb\u5316\u7684\u95ee\u9898\u8f6c\u5316\u4e3aFrame Field\u65e0\u65cb\u5316\u7684\u95ee\u9898.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Integrable-field.png\" alt=\"\" width=\"375\" height=\"404\" class=\"aligncenter size-full wp-image-1349\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Integrable-field.png 750w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Integrable-field-279x300.png 279w\" sizes=\"(max-width: 375px) 100vw, 375px\" \/><\/p>\n<p>\u8bba\u6587Frame Fields: Anisotropic and NonOrthogonal Cross Fields\u63d0\u4f9b\u4e86\u4e00\u79cdFrame Field\u65e0\u65cb\u5316\u7684\u7b97\u6cd5. \u4f5c\u8005\u4ece\u5217\u5411\u91cf\u7ec4\u7684\u89d2\u5ea6\u51fa\u53d1, Cross Field(4-RoSy Field) \u4e0a\u6bcf\u4e2a\u70b9\u7684\u65b9\u5411\u96c6\u53ef\u4ee5\u5199\u4e3a$X = \\left \\langle u, u^\\bot, -u, -u^\\bot \\right \\rangle$, \u800cFrame Field($2^2$Vector Field) \u4e0a\u6bcf\u4e2a\u70b9\u7684\u65b9\u5411\u96c6\u5219\u53ef\u4ee5\u5199\u4e3a$F = \\left \\langle v, w, -v, -w \\right \\rangle$. \u4e0d\u59a8\u5c06$F$\u89c6\u4e3a\u4e00\u4e2a\u77e9\u9635, \u5219\u53ef\u4ee5\u5bf9$F$\u4f7f\u7528\u6781\u5206\u89e3\u5f97\u5230$F = WX$, \u5176\u4e2d$W$\u662f\u4e00\u4e2a\u5bf9\u79f0\u6b63\u5b9a\u77e9\u9635(Symmetric Positive Definite Matrix, \u7b80\u79f0SPD Matrix). \u6781\u5206\u89e3\u53ef\u4ee5\u91c7\u7528SVD\u5f97\u5230, \u5373$F = U \\sum V^T = $$ U \\sum U^T UV^T$, \u4ee4$W = U \\sum U^T, X = UV^T$,\u5373\u53ef\u5f97\u5230$F$\u7684\u6781\u5206\u89e3. \u4f5c\u8005\u8ba4\u4e3a, \u82e5$X, W$\u5bf9\u4e8e\u7f51\u683c\u8868\u9762\u4e0a\u7684\u70b9\u5747\u4e3a\u8fde\u7eed\u51fd\u6570\u751a\u81f3\u5149\u6ed1\u51fd\u6570, \u5219\u8be5Frame Field\u4e5f\u662f\u4e00\u4e2a\u8fde\u7eed\u5411\u91cf\u573a\u751a\u81f3\u5149\u6ed1\u5411\u91cf\u573a.\u56e0\u6b64, \u5206\u522b\u4f18\u5316$X, W$\u5373\u53ef\u5f97\u5230\u65e0\u65cb\u7684Frame Field.<br \/>\n$\\quad \\cdot$ <strong>$X:$<\/strong> \u91c7\u7528\u4e4b\u524d\u7684\u80fd\u91cf\u51fd\u6570\u8fdb\u884c\u4f18\u5316, \u5373$$E_{fair-4} = \\frac{4}{2} \\sum_e w_e(\\phi_j &#8211; (\\phi_i + X_{ij} + \\frac{2\\pi}{N}k_{ij}))^2.$$<br \/>\n$\\quad \\cdot$ <strong>$W:$<\/strong> \u91c7\u7528\u62c9\u666e\u62c9\u65af\u5149\u987a\u7b97\u5b50, \u7531\u4e8e\u62c9\u666e\u62c9\u65af\u5149\u987a\u7b97\u5b50\u662f\u4e00\u4e2a\u51f8\u7ec4\u5408\u7684\u5f62\u5f0f, \u6545\u80fd\u4fdd\u8bc1\u5149\u987a\u540e\u7684$W$\u4ecd\u65e7\u4e3a\u4e00\u4e2aSPD\u77e9\u9635.<\/p>\n<p>$\\cdot$ $2^2$\u65b9\u5411\u573a\u7684\u65e0\u65cb\u5316<\/p>\n<p>\u8bba\u6587General Planar Quadrilateral Mesh Design Using Conjugate Direction Field\u63d0\u4f9b\u4e86\u4e00\u79cd$2^2$\u65b9\u5411\u573a\u65e0\u65cb\u5316\u7684\u7b97\u6cd5. \u4f5c\u8005\u4f9d\u65e7\u4ece\u5217\u5411\u91cf\u7ec4\u7684\u89d2\u5ea6\u51fa\u53d1, $2^2$\u65b9\u5411\u573a\u4e0a\u6bcf\u4e2a\u70b9\u7684\u65b9\u5411\u96c6\u53ef\u4ee5\u5199\u4e3a$F = \\left \\langle v, w, -v, -w \\right \\rangle$, \u5176\u4e2d$\\left \\| v \\right \\| = \\left \\| w \\right \\|$. \u7b49\u4ef7\u7684\u5199\u6cd5\u8fd8\u6709: $F = \\left \\langle w, -v, -w, -v \\right \\rangle$, $F = \\left \\langle -v, -w, v, w \\right \\rangle$, $F = \\left \\langle -w, v, w, -v \\right \\rangle$. \u5b83\u4eec\u4e4b\u95f4\u76f8\u5dee\u5982\u4e0b\u5e26\u7b26\u53f7\u7684\u7f6e\u6362\u77e9\u9635:$$\\begin{pmatrix}1 &#038; 0\\\\0 &#038; 1\\end{pmatrix},\\begin{pmatrix}0 &#038; 1\\\\-1 &#038; 0\\end{pmatrix},\\begin{pmatrix}-1 &#038; 0\\\\0 &#038; -1\\end{pmatrix},\\begin{pmatrix}0 &#038; -1\\\\1 &#038; 0\\end{pmatrix}.$$\u6545\u5728\u6bd4\u8f83\u76f8\u90bb\u9762\u7684\u65b9\u5411\u573a\u65f6, \u4f7f\u7528\u7684\u5ea6\u91cf\u5e94\u4e3a:$$[v_f | w_f] = [v_g | w_g]P_{fg},$$\u5176\u4e2d, $f,g$\u4e3a\u76f8\u90bb\u7684\u4e24\u4e2a\u9762, \u5176\u516c\u5171\u8fb9\u4e3a$e$, $P_{fg}$\u662f\u4e0a\u8ff0\u56db\u4e2a\u7f6e\u6362\u77e9\u9635\u6240\u6784\u6210\u7684\u96c6\u5408\u4e2d\u7684\u5143\u7d20. \u5b9e\u9645\u4e0a, \u6b64\u5904\u5f15\u5165\u7f6e\u6362\u77e9\u9635\u7684\u521d\u8877\u4e0e\u79bb\u6563$N$-RoSy\u573a\u4e2d\u5f15\u5165\u6574\u6570\u53d8\u91cf$k_{ij}$\u7684\u521d\u8877\u662f\u4e00\u81f4\u7684, \u5747\u662f\u4e3a\u4e86\u89c4\u907f\u4eba\u4e3a\u9009\u62e9\u987a\u5e8f\u7684\u5f71\u54cd, \u53ea\u4e0d\u8fc7\u6b64\u5904\u8ba8\u8bba\u7684\u5bf9\u8c61\u4e3a$2^2$\u65b9\u5411\u573a, \u6bcf\u4e2a\u70b9\u4e0a\u7684\u5404\u65b9\u5411\u95f4\u7684\u5939\u89d2\u5e76\u4e0d\u662f\u56fa\u5b9a\u768490\u5ea6, \u56e0\u6b64\u6b64\u5904\u9700\u8981\u4f7f\u7528\u7f6e\u6362\u77e9\u9635\u7684\u8bed\u8a00\u8fdb\u884c\u63cf\u8ff0. \u8bba\u6587\u7684\u7b97\u6cd5\u601d\u60f3\u4e5f\u53ef\u4ee5\u63a8\u5e7f\u81f33\u7ef4\u60c5\u5f62.<\/p>\n<h3>P21: Remeshing<\/h3>\n<p>\u4ece\u8fd9\u4e00\u8282\u5f00\u59cb\u4ecb\u7ecd\u7684\u5185\u5bb9\u5f88\u591a\u90fd\u4e0e\u81ea\u5df1\u7855\u58eb\u9636\u6bb5\u7814\u7a76\u7684\u5185\u5bb9\u6709\u5173, \u6240\u4ee5\u8fd8\u662f\u633a\u6709\u4eb2\u5207\u611f\u7684. \u91cd\u65b0\u7f51\u683c\u5316\u662f\u4e00\u79cd\u63d0\u5347\u7f51\u683c\u8d28\u91cf\u7684\u5173\u952e\u6280\u672f, \u5176\u76ee\u6807\u6709\u4e24\u4e2a:<br \/>\n$\\cdot$ \u8f93\u5165\u7f51\u683c\u4e0e\u8f93\u51fa\u7f51\u683c\u5e94\u5728\u67d0\u4e9b\u6307\u6807(\u5982\u4f4d\u7f6e, \u6cd5\u5411, \u66f2\u7387\u7b49\u4e00\u4e9b\u9ad8\u9636\u5fae\u5206\u91cf) \u4e0a\u5c3d\u53ef\u80fd\u76f8\u4f3c.<br \/>\n$\\cdot$ \u63d0\u5347\u8f93\u5165\u7f51\u683c\u7684\u8d28\u91cf, \u4e0d\u540c\u7684\u5e94\u7528\u5bf9\u4e8e\u8f93\u5165\u7f51\u683c\u4e00\u822c\u4f1a\u6709\u4e0d\u540c\u7684\u8981\u6c42.<br \/>\n\u7b97\u6cd5\u8f93\u5165\u4e00\u822c\u662f\u4e09\u89d2\u7f51\u683c, \u800c\u7528\u4e8e\u8861\u91cf\u7f51\u683c\u8d28\u91cf\u7684\u56e0\u7d20\u4e5f\u6709\u5f88\u591a, \u5982\u91c7\u6837\u5bc6\u5ea6, \u5947\u5f02\u70b9\u6570\u91cf(\u4e09\u89d2\u7f51\u683c\u4e2d\u4e00\u822c\u8ba4\u4e3a\u5ea6\u4e0d\u4e3a6\u7684\u70b9\u4e3a\u5947\u5f02\u70b9, \u4f46\u5947\u5f02\u70b9\u5bf9\u4e8e\u6e32\u67d3\u7684\u5f71\u54cd\u7a0b\u5ea6\u4e00\u822c\u8f83\u5c0f), \u9876\u70b9\u6570\u91cf, \u7f51\u683c\u671d\u5411(\u5404\u5411\u540c\u6027\u4e0e\u5404\u5411\u5f02\u6027), \u5bf9\u9f50\u8d28\u91cf(\u5982\u7f51\u683c\u5143\u7d20\u4e0e\u7279\u5f81\u7ebf\u7684\u5bf9\u9f50\u7a0b\u5ea6), \u7f51\u683c\u5143\u7d20\u7684\u5f62\u72b6\u4e0e\u62d3\u6251\u6027\u8d28\u7b49.<\/p>\n<h4>21.1 Incremental Remeshing<\/h4>\n<p>\u5728\u91cd\u65b0\u7f51\u683c\u5316\u9886\u57df, \u4e00\u79cd\u7ecf\u5178\u7b97\u6cd5\u662fIncremental Remeshing. \u5b83\u4e3b\u8981\u5305\u542b\u56db\u79cd\u64cd\u4f5c, \u5982\u4e0b\u56fe\u6240\u793a.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Remeshing.png\" alt=\"\" width=\"1313\" height=\"539\" class=\"aligncenter size-full wp-image-1353\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Remeshing.png 1313w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Remeshing-300x123.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Remeshing-768x315.png 768w\" sizes=\"(max-width: 1313px) 100vw, 1313px\" \/><\/p>\n<p>\u7b97\u6cd5\u4f2a\u4ee3\u7801\u5982\u4e0b\u6240\u793a:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Remeshing-Pseudo-Code.png\" alt=\"\" width=\"1599\" height=\"705\" class=\"aligncenter size-full wp-image-1354\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Remeshing-Pseudo-Code.png 1599w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Remeshing-Pseudo-Code-300x132.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Remeshing-Pseudo-Code-768x339.png 768w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Remeshing-Pseudo-Code-1536x677.png 1536w\" sizes=\"(max-width: 1599px) 100vw, 1599px\" \/><\/p>\n<p>\u63a5\u4e0b\u6765\u89e3\u91ca\u7b97\u6cd5\u5404\u6b65\u9aa4.<br \/>\n$\\cdot$ \u7b97\u6cd5\u4e2d\u4f7f\u7528\u4e86<strong>\u4e24\u4e2a\u7ecf\u9a8c\u53c2\u6570$\\frac{4}{5},\\frac{4}{3}$<\/strong>.<br \/>\n$\\cdot$ <strong>Split long edges(high_e).<\/strong> \u904d\u5386\u5f53\u524d\u7f51\u683c\u4e2d\u7684\u6240\u6709\u8fb9, \u904d\u5386\u8fc7\u7a0b\u4e2d\u82e5\u53d1\u73b0\u67d0\u6761\u8fb9\u7684\u957f\u5ea6\u5927\u4e8e\u7ed9\u5b9a\u7684\u9608\u503chigh_e, \u5219\u5c06\u8fd9\u6761\u8fb9\u4ece\u4e2d\u70b9&#8221;\u5288\u5f00&#8221;, \u4f7f\u5f97\u4e24\u4e2a\u76f8\u90bb\u7684\u4e09\u89d2\u5f62\u88ab\u5e73\u5206.<br \/>\n$\\cdot$ <strong>Collapse short edges(low_e, high_e).<\/strong> \u584c\u9677\u6240\u6709\u957f\u5ea6\u5c0f\u4e8e\u7ed9\u5b9a\u9608\u503clow_e\u7684\u8fb9. \u4f46\u8fd9\u79cd\u5c40\u90e8\u64cd\u4f5c\u5e26\u6765\u7684\u95ee\u9898\u662f, \u968f\u7740\u77ed\u8fb9\u7684\u584c\u9677, \u53ef\u80fd\u5f15\u5165\u957f\u5ea6\u5927\u4e8e\u7ed9\u5b9a\u9608\u503chigh_e\u7684\u957f\u8fb9. \u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u7684\u65b9\u6cd5\u662f\u5728\u6bcf\u6b21\u584c\u9677\u4e4b\u524d\u6d4b\u8bd5\u6b64\u6b21\u584c\u9677\u64cd\u4f5c\u662f\u5426\u4f1a\u5f15\u5165\u4e0d\u5408\u6cd5\u7684\u957f\u8fb9, \u82e5\u4f1a\u5f15\u5165, \u5219\u4e0d\u6267\u884c\u672c\u6b21\u584c\u9677\u64cd\u4f5c.<br \/>\n$\\cdot$ <strong>Equalize valences.<\/strong> \u901a\u8fc7\u7ffb\u8f6c\u8fb9\u4f7f\u5f97\u9876\u70b9\u7684\u5ea6\u76f8\u7b49(\u4e09\u89d2\u7f51\u683c\u4e2d\u9876\u70b9\u7684\u76ee\u6807\u5ea6\u901a\u5e38\u8bbe\u7f6e\u4e3a6), \u5224\u65ad\u662f\u5426\u80fd\u8fdb\u884c\u7ffb\u8f6c\u7684\u51c6\u5219\u901a\u5e38\u53ef\u4ee5\u8bbe\u7f6e\u4e3a\u5982\u4e0b\u5f62\u5f0f:$$\\sum_{i} |degree(v_i) &#8211; 6|,$$\u5176\u4e2d, $i$\u4e3a\u53d7\u5230\u672c\u6b21\u7ffb\u8f6c\u8fb9\u5f71\u54cd\u7684\u9876\u70b9\u7684\u4e0b\u6807, $degree(v_i)$\u4e3a\u9876\u70b9$v_i$\u7684\u5ea6. \u82e5\u672c\u6b21\u7ffb\u8f6c\u8fb9\u540e, \u8be5\u503c\u51cf\u5c11, \u5219\u8ba4\u4e3a\u53ef\u6267\u884c\u672c\u6b21\u7ffb\u8f6c\u8fb9\u7684\u64cd\u4f5c.<br \/>\n$\\cdot$ <strong>The tangential relaxation.<\/strong> \u5bf9\u7f51\u683c\u8fdb\u884c\u5149\u987a, \u5149\u987a\u901a\u5e38\u4f7f\u7528\u62c9\u666e\u62c9\u65af\u7b97\u5b50,$$q = \\frac{1}{N_p} \\sum_{p_j \\in \\Omega(p)} p_j.$$\u82e5\u5149\u987a\u8fc7\u7a0b\u4e2d\u6709\u9876\u70b9$p$\u504f\u79bb\u7f51\u683c\u8868\u9762, \u5219\u9700\u8981\u5c06\u504f\u79bb\u7684\u9876\u70b9$p$\u91cd\u65b0\u6295\u5f71\u81f3\u7f51\u683c\u8868\u9762\u4e0a\u70b9$q$\u7684\u5207\u5e73\u9762\u4e0a,$$p&#8217; = q + nn^T(p-q).$$<\/p>\n<p>\u5f53\u5bf9\u7b97\u6cd5\u7ed3\u679c\u6709\u4fdd\u7279\u5f81\u7684\u8981\u6c42\u65f6, \u7b97\u6cd5\u6267\u884c\u8fc7\u7a0b\u4e2d\u8981\u6ce8\u610f\u4ee5\u4e0b\u51e0\u70b9.<br \/>\n$\\cdot$ \u7279\u5f81\u7ebf\u4e0e\u7279\u5f81\u70b9\u5747\u5df2\u5728\u8f93\u5165\u6a21\u578b\u4e2d\u4f5c\u51fa\u6807\u8bb0.<br \/>\n$\\cdot$ \u6240\u6709\u5c40\u90e8\u64cd\u4f5c\u5e94\u4fdd\u6301\u89d2\u70b9(\u8d85\u8fc72\u6761\u7279\u5f81\u8fb9\u8fde\u63a5\u6216\u8005\u53ea\u8fde\u63a5\u4e00\u6761\u7279\u5f81\u8fb9\u7684\u70b9) \u4e0d\u52a8.<br \/>\n$\\cdot$ \u7279\u5f81\u70b9\u5e94\u6cbf\u7740\u7279\u5f81\u7ebf\u584c\u9677.<br \/>\n$\\cdot$ \u5206\u5272\u4e00\u6761\u7279\u5f81\u8fb9\u4f1a\u5f15\u5165\u4e24\u6761\u65b0\u7684\u7279\u5f81\u8fb9\u4e0e\u4e00\u4e2a\u65b0\u7684\u7279\u5f81\u70b9.<br \/>\n$\\cdot$ \u7279\u5f81\u8fb9\u4e0d\u5e94\u88ab\u7ffb\u8f6c.<\/p>\n<h4>21.2 Parameterization-Based Method<\/h4>\n<p>\u9664\u4e86Incremental Remeshing\u4ee5\u5916, \u8fd8\u53ef\u5229\u7528\u53c2\u6570\u5316\u5c06\u4e09\u7ef4\u7a7a\u95f4\u4e0a\u7684\u91cd\u65b0\u7f51\u683c\u5316\u95ee\u9898\u8f6c\u5316\u4e3a\u4e8c\u7ef4\u5e73\u9762\u4e0a\u7684\u91cd\u65b0\u7f51\u683c\u5316\u95ee\u9898. \u76f8\u6bd4\u8f83\u4e09\u7ef4\u7a7a\u95f4, \u6211\u4eec\u66f4\u5bb9\u6613\u8c03\u6574\u4e8c\u7ef4\u5e73\u9762\u4e0a\u7684\u91c7\u6837\u70b9\u7684\u4f4d\u7f6e. \u4f46\u8fd9\u79cd\u65b9\u5f0f\u4e5f\u4f1a\u5e26\u6765\u51e0\u4e2a\u95ee\u9898.<br \/>\n$\\cdot$ \u53c2\u6570\u5316\u7ed3\u679c\u901a\u5e38\u5e26\u6709\u626d\u66f2.<br \/>\n$\\cdot$ \u5f53\u4e00\u4e2a\u7f51\u683c\u5207\u5272(\u4f7f\u5f97\u5207\u5272\u4ea7\u751f\u7684\u5757\u4e0e\u5706\u76d8\u540c\u80da) \u540e\u5176\u53c2\u6570\u5316\u7ed3\u679c\u5bb9\u6613\u4ea7\u751f\u4e0d\u8fde\u7eed\u70b9.<br \/>\n$\\cdot$ \u5f53\u5904\u7406\u7684\u7f51\u683c\u7684\u9690\u85cf\u66f2\u9762\u4e3a\u95ed\u66f2\u9762\u65f6, \u901a\u5e38\u9700\u8981\u5bf9\u7f51\u683c\u8fdb\u884c\u5207\u5272. \u56e0\u6b64, \u5272\u7f1d\u7684\u8d28\u91cf\u5341\u5206\u91cd\u8981. \u5e38\u7528\u7684\u751f\u6210\u5272\u7f1d\u7684\u7b97\u6cd5\u4e0a\u6587\u5df2\u4ecb\u7ecd, \u5982D-Charts\u7b97\u6cd5. \u4f46\u5728\u5206\u522b\u5bf9\u5404\u5757\u8fdb\u884c\u91cd\u65b0\u7f51\u683c\u5316\u4ee5\u540e, \u8fb9\u754c\u53ef\u80fd\u51fa\u73b0\u62fc\u63a5\u4e0d\u4e0a\u7684\u95ee\u9898, \u5e38\u7528\u7684\u89e3\u51b3\u65b9\u6848\u662f\u4e0d\u5bf9\u4e0a\u4e00\u5757\u7684\u8fb9\u754c\u8fdb\u884c\u5904\u7406, \u5c06\u5176\u8fb9\u754c\u4e0e\u4e0b\u4e00\u5757\u4e00\u5e76\u91cd\u65b0\u7f51\u683c\u5316.<br \/>\n\u5c3d\u7ba1\u6709\u4e0a\u8ff0\u7f3a\u70b9, \u4f46\u57fa\u4e8e\u53c2\u6570\u5316\u7684\u7b97\u6cd5\u80fd\u591f\u907f\u514dIncremental Remeshing\u5728\u91cd\u6295\u5f71\u6b65\u9aa4\u51fa\u73b0\u5f02\u5e38\u7684\u95ee\u9898, \u56e0\u6b64\u8fd8\u662f\u88ab\u8bb8\u591a\u5b66\u8005\u6240\u8ba4\u53ef.<\/p>\n<h4>21.3 Approximation<\/h4>\n<p>\u91cd\u65b0\u7f51\u683c\u5316\u5e0c\u671b\u8f93\u5165\u7f51\u683c\u4e0e\u8f93\u51fa\u7f51\u683c\u5e94\u5728\u67d0\u4e9b\u6307\u6807(\u5982\u4f4d\u7f6e, \u6cd5\u5411, \u66f2\u7387\u7b49\u9ad8\u9636\u5fae\u5206\u91cf) \u4e0a\u5c3d\u53ef\u80fd\u76f8\u4f3c, \u800c\u901a\u5e38\u7528\u4e8e\u8861\u91cf\u4e24\u4e2a\u7f51\u683c\u7684\u9876\u70b9\u4f4d\u7f6e\u7684\u5dee\u5f02\u7684\u5ea6\u91cf\u4fbf\u662fHausdorff\u8ddd\u79bb. \u5728\u62d3\u6734\u5b66\u4e0a, Hausdorff\u8ddd\u79bb\u7528\u4e8e\u8861\u91cf\u4e24\u4e2a\u5ea6\u91cf\u7a7a\u95f4\u7684\u5b50\u96c6\u5f7c\u6b64\u4e4b\u95f4\u7684\u8ddd\u79bb.<\/p>\n<p><strong>Hausdorff\u8ddd\u79bb<\/strong> \u4ee4$X, Y$\u662f\u5ea6\u91cf\u7a7a\u95f4$(M,d)$\u7684\u4e24\u4e2a\u975e\u7a7a\u5b50\u96c6. \u6211\u4eec\u5b9a\u4e49Hausdorff\u8ddd\u79bb$d_H(X, Y)$\u4e3a$$d_H(X, Y) = max\\{ \\sup_{x \\in X} \\inf_{y \\in Y} d(x, y), \\sup_{y \\in Y} \\inf_{x \\in X} d(x, y) \\}.$$\u4e00\u822c\u6765\u8bf4, $\\sup_{x \\in X} \\inf_{y \\in Y} d(x, y) \\ne \\sup_{y \\in Y} \\inf_{x \\in X} d(x, y),$ \u5982\u4e0b\u56fe\u6240\u793a.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Hausdorff-Distance.png\" alt=\"\" width=\"608\" height=\"613\" class=\"aligncenter size-full wp-image-1357\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Hausdorff-Distance.png 1216w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Hausdorff-Distance-298x300.png 298w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Hausdorff-Distance-150x150.png 150w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Hausdorff-Distance-768x774.png 768w\" sizes=\"(max-width: 608px) 100vw, 608px\" \/> <\/p>\n<p>\u5f53\u628aHausdorff\u8ddd\u79bb\u63a8\u5e7f\u81f3\u4e09\u89d2\u7f51\u683c\u4e0a\u4ee5\u540e, \u6b64\u65f6\u4e09\u89d2\u7f51\u683c$M_1, M_2$\u4e4b\u95f4\u7684Hausdorff\u8ddd\u79bb\u5b9a\u4e49\u4e3a:$$d_H(M_1, M_2) = \\max \\{ d_h(M_1, M_2), d_h(M_2, M_1) \\},$$\u5176\u4e2d$d_h(S, T) = \\max_{p \\in S} \\min_{q \\in T} d(p, q) := \\max_{p \\in S} d(p, T).$<\/p>\n<p>\u5b9e\u9645\u4e0a, \u8ba1\u7b97\u4e24\u4e2a\u4e09\u89d2\u7f51\u683c$M_1, M_2$\u4e4b\u95f4\u7684Hausdorff\u8ddd\u79bb\u7684\u8ba1\u7b97\u91cf\u662f\u6bd4\u8f83\u5927\u7684, \u56e0\u6b64\u901a\u5e38\u9700\u8981\u8fdb\u884c\u8fd1\u4f3c. \u5bf9$M_1, M_2$\u5206\u522b\u8fdb\u884c\u91c7\u6837\u5f97\u5230\u4e24\u4e2a\u70b9\u96c6$S_1 \\subset M_1, S_2 \\subset M_2$, \u5219$d_h(M_1, M_2)$\u53ef\u88ab\u8fd1\u4f3c\u4e3a$$d_h(M_1, M_2) \\approx \\max_{a \\in S_1} d(a, M_2)\\\\\\Longrightarrow d_H(M_1, M_2) \\approx \\max \\{ \\max_{a \\in S_1} d(a, M_2), \\max_{b \\in S_2} d(b, M_1) \\}.$$\u4e0a\u8ff0\u8ba1\u7b97\u65b9\u5f0f\u5bf9\u4e8e$d_H(M_1, M_2)$\u7684\u903c\u8fd1\u7a0b\u5ea6\u662f\u9ad8\u4e8e\u76f4\u63a5\u8ba1\u7b97$d_H(S_1, S_2)$\u7684.<\/p>\n<h4>21.4 Error-Bounded Method<\/h4>\n<p>\u8fd9\u662f\u57282007\u5e74\u4fbf\u5df2\u7ecf\u63d0\u51fa\u7684\u4e00\u79cd\u7b97\u6cd5, \u5176\u4e3b\u8981\u7684\u7b97\u6cd5\u601d\u60f3\u662f\u82e5\u5f53\u524d\u7684\u5c40\u90e8\u64cd\u4f5c\u4f1a\u4f7f\u5f97\u5f53\u524d\u7f51\u683c\u4e0e\u8f93\u5165\u7f51\u683c\u4e4b\u95f4\u7684Hausdorff\u8ddd\u79bb\u5927\u4e8e\u7ed9\u5b9a\u7684\u9608\u503c, \u5219\u4e0d\u6267\u884c\u5f53\u524d\u7684\u5c40\u90e8\u64cd\u4f5c, \u4ece\u800c\u4f7f\u5f97\u5f53\u524d\u7f51\u683c\u59cb\u7ec8\u5904\u4e8e\u4e00\u4e2aError-Bounded\u7684\u53ef\u884c\u96c6\u91cc. \u8bf4\u5b9e\u8bdd, \u6211\u4e00\u76f4\u4ee5\u4e3aError-Bounded Method\u662f\u4ece\u7406\u8bba\u4e0a\u8bc1\u660e\u6709\u754c, \u975e\u5e38\u671f\u5f85\u770b\u5230\u76f8\u5173\u8bc1\u660e. \u4e8b\u5b9e\u8bc1\u660e, \u662f\u6211\u60f3\u592a\u591a\u4e86\u2026\u2026<\/p>\n<p>\u8fd9\u79cd\u7b97\u6cd5\u5b58\u5728\u4e00\u4e2a\u5173\u952e\u7684\u95ee\u9898\u4fbf\u662f, \u6bcf\u8fdb\u884c\u4e00\u6b21\u5c40\u90e8\u64cd\u4f5c\u524d\u90fd\u8981\u8ba1\u7b97Hausdorff\u8ddd\u79bb\u7684\u4ee3\u4ef7\u592a\u9ad8\u4e86, \u56e0\u6b64\u6709\u5b66\u8005\u63d0\u51fa, \u4e0d\u9700\u8981\u6bcf\u8fdb\u884c\u4e00\u6b21\u5c40\u90e8\u64cd\u4f5c\u524d\u90fd\u8ba1\u7b97Hausdorff\u8ddd\u79bb, \u53ef\u4ee5\u5728\u56fa\u5b9a\u6b21\u6570\u7684\u5c40\u90e8\u64cd\u4f5c\u4ee5\u540e, \u68c0\u67e5\u5f53\u524d\u7f51\u683c\u4e0e\u8f93\u5165\u7f51\u683c\u4e4b\u95f4\u7684Hausdorff\u8ddd\u79bb\u662f\u5426\u5927\u4e8e\u7ed9\u5b9a\u7684\u9608\u503c. \u82e5\u662f\u5219\u5f80\u5bfc\u81f4Hausdorff\u8ddd\u79bb\u8f83\u5927\u7684\u533a\u57df\u8fdb\u884c\u63d2\u5165\u70b9\u7684\u64cd\u4f5c, \u5b9e\u9a8c\u8bc1\u660e, \u5f53\u63d2\u5165\u7684\u70b9\u4f7f\u5f97\u5f53\u524d\u533a\u57df\u7684\u70b9\u7684\u5206\u5e03\u662f\u5747\u5300\u5206\u5e03\u65f6, \u76f8\u5e94\u7684Hausdorff\u8ddd\u79bb\u5f80\u5f80\u662f\u5728\u7ed9\u5b9a\u7684\u9608\u503c\u4e4b\u5185\u7684.<\/p>\n<h4>21.5 Angles<\/h4>\n<p>\u9488\u5bf9\u89d2\u5ea6\u8fdb\u884c\u91cd\u65b0\u7f51\u683c\u5316\u7684\u4ee3\u8868\u8bba\u6587\u662fIsotropic Surface Remeshing without Large and Small Angles.\u6b64\u5904\u7684\u5c0f\u89d2\u5ea6\u6216\u8005\u5927\u89d2\u5ea6\u662f\u6307\u5728\u7ed9\u5b9a\u7684\u533a\u95f4$[\\beta_{\\min}, \\beta_{\\max}]$\u4e4b\u5916\u7684\u89d2\u5ea6. \u8bba\u6587\u7b97\u6cd5\u7684\u6838\u5fc3\u601d\u60f3\u662f:<br \/>\n$\\cdot$ <strong>\u53bb\u9664\u5927\u89d2\u5ea6:<\/strong> Edge Splitting.<br \/>\n$\\cdot$ <strong>\u63d0\u5347\u5c0f\u89d2\u5ea6:<\/strong> Edge Collapsing.<br \/>\n\u5982\u4e0b\u56fe\u6240\u793a, 1) Split; 2) Flip.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Large-Angle-Removal.png\" alt=\"\" width=\"842\" height=\"656\" class=\"aligncenter size-full wp-image-1358\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Large-Angle-Removal.png 842w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Large-Angle-Removal-300x234.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Large-Angle-Removal-768x598.png 768w\" sizes=\"(max-width: 842px) 100vw, 842px\" \/><\/p>\n<h3>P22: Delaunay Triangulations<\/h3>\n<p>\u8fd9\u8282\u8bfe\u4ecb\u7ecd\u7684\u5185\u5bb9\u8fd8\u662f\u5f88\u6709\u610f\u601d\u7684, \u4e3b\u8981\u4fa7\u91cd\u4e8eDelaunay\u4e09\u89d2\u5256\u5206\u4e2d\u4e00\u4e9b\u6027\u8d28\u7684\u8bc1\u660e. \u81ea\u5df1\u867d\u7136\u4e4b\u524d\u7528\u8fc7, \u4f46\u5e76\u6ca1\u6709\u6df1\u5165\u5730\u4e86\u89e3\u8fc7\u76f8\u5173\u6027\u8d28\u7684\u8bc1\u660e~<\/p>\n<h4>22.1 Convex Hull<\/h4>\n<p>$\\cdot$ <strong>\u51f8\u96c6<\/strong>. \u5bf9\u4e8e\u96c6\u5408$P \\in R^d$\u5185\u7684\u4efb\u610f\u4e24\u70b9$p,q$, \u82e5\u4e4b\u95f4\u7684\u8fde\u7ebf$\\overline{pq} \\in P$, \u5219\u79f0\u96c6\u5408$P$\u4e3a\u4e00\u4e2a\u51f8\u96c6. \u4e5f\u53ef\u4ee5\u5229\u7528\u8fde\u901a\u6027\u4f5c\u4e00\u4e2a\u7b49\u4ef7\u7684\u5b9a\u4e49: \u5bf9\u4e8e\u4efb\u610f\u76f4\u7ebf$l \\in R^d$\u4e0e\u96c6\u5408$P \\in R^d$, \u82e5$l \\cap P$\u5747\u4e3a\u4e00\u4e2a\u8fde\u901a\u96c6, \u5219\u79f0\u96c6\u5408$P$\u4e3a\u4e00\u4e2a\u51f8\u96c6. \u5bf9\u4e8e\u4efb\u610f\u51f8\u96c6\u7684\u96c6\u5408\u65cf$\\{ P_i \\}$, $\\cap_i P_i$\u5747\u4e3a\u51f8\u96c6.<\/p>\n<p>$\\cdot$ <strong>\u51f8\u5305<\/strong>. \u6709\u9650\u70b9\u96c6$P \\in R^d$\u7684\u51f8\u5305\u6784\u6210\u4e00\u4e2a\u51f8\u591a\u9762\u4f53, \u8bb0\u4e3a$conv(P)$. \u82e5$p \\in P$\u4e14$p \\notin conv(P \\backslash \\{ p \\})$, \u5219\u79f0$p$\u4e3a$conv(P)$\u7684\u4e00\u4e2a\u9876\u70b9(\u6216Extremal Point). \u6c42\u89e3\u51f8\u5305\u7684\u7b97\u6cd5\u4e3b\u8981\u6709\u4e24\u79cd.<br \/>\n$\\quad \\cdot$ <strong>Carath\u00e9odory\u2019s Theorem.<\/strong> \u904d\u5386$P$\u4e2d\u6bcf\u4e2a\u70b9$p$, \u5224\u65ad\u662f\u5426\u5b58\u5728$q,r,s \\in P \\backslash \\{ p \\}$, \u4f7f\u5f97$p$\u5728$q,r,s$\u6784\u6210\u7684\u4e09\u89d2\u5f62\u5185\u90e8. \u82e5\u4e0d\u5b58\u5728\u7b26\u5408\u6761\u4ef6\u7684\u4e09\u4e2a\u70b9, \u5219\u5f53\u524d\u70b9$p$\u662f$P$\u7684\u51f8\u5305\u7684\u4e00\u4e2a\u9876\u70b9. \u8be5\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a$O(n^4)$.<br \/>\n$\\quad \\cdot$ <strong>Carath\u00e9odory\u2019s Theorem.<\/strong> \u904d\u5386$P$\u4e2d\u6bcf\u4e2a\u70b9$p$, \u5224\u65ad\u662f\u5426\u5b58\u5728$q,r,s \\in P \\backslash \\{ p \\}$, \u4f7f\u5f97$p$\u5728$q,r,s$\u6784\u6210\u7684\u4e09\u89d2\u5f62\u5185\u90e8. \u82e5\u4e0d\u5b58\u5728\u7b26\u5408\u6761\u4ef6\u7684\u4e09\u4e2a\u70b9, \u5219\u5f53\u524d\u70b9$p$\u662f$P$\u7684\u51f8\u5305\u7684\u4e00\u4e2a\u9876\u70b9. \u8be5\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a$O(n^4)$.<br \/>\n$\\quad \\cdot$ <strong>The Separation Theorem.<\/strong> \u904d\u5386$P^2$\u4e2d\u7684\u70b9\u5bf9$(p,q)$, \u5224\u65ad$P \\backslash \\{ p, q\\}$\u4e2d\u7684\u6240\u6709\u70b9\u662f\u5426\u90fd\u5728$p, q$\u4e4b\u95f4\u7684\u8fde\u7ebf$\\overline{pq}$\u7684\u4e00\u4fa7, \u82e5\u662f\u5219\u8bf4\u660e$\\overline{pq}$\u662f$P$\u7684\u51f8\u5305\u8fb9\u754c\u7684\u4e00\u90e8\u5206. \u8be5\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a$O(n^3)$.<\/p>\n<h4>22.2 Triangulation<\/h4>\n<p>\u4e09\u89d2\u5256\u5206\u662f\u628a\u6307\u7531\u4e00\u4e2a\u591a\u8fb9\u5f62\u5256\u5206\u5f97\u5230\u7684\u4e09\u89d2\u5f62\u96c6\u5408, \u5176\u5e94\u7528\u662f\u5341\u5206\u5e7f\u6cdb\u7684, \u5982\u9762\u79ef\u8ba1\u7b97, \u63d2\u503c\u7b49. \u5728\u4e00\u4e2a\u6709\u9650\u70b9\u96c6$P \\subset R^2$\u4e0a\u7684\u4e09\u89d2\u5256\u5206\u662f\u4e00\u4e2a\u4e09\u89d2\u5f62\u96c6$\\mathcal{T}$, \u5e76\u6ee1\u8db3\u5982\u4e0b\u7ea6\u675f:<br \/>\n$\\cdot$ $conv(P) = \\cup_{T \\in \\mathcal{T}} T$.<br \/>\n$\\cdot$ $P = \\cup_{T \\in \\mathcal{T}} V(T)$.<br \/>\n$\\cdot$ \u5bf9\u4e8e\u4efb\u610f\u96c6\u5408\u5bf9$T, U \\in \\mathcal{T}$, $T \\cap U$\u8981\u4e48\u4ec5\u542b\u516c\u5171\u70b9, \u8981\u4e48\u4ec5\u542b\u516c\u5171\u8fb9, \u8981\u4e48\u662f\u7a7a\u96c6.<\/p>\n<h4>22.3 Delaunay Triangulation<\/h4>\n<p><strong>\u4e8c\u7ef4Delaunay\u4e09\u89d2\u5256\u5206<\/strong> \u7ed9\u5b9a\u5e73\u9762\u4e0a\u7684\u79bb\u6563\u70b9\u96c6$P$, \u82e5\u5b58\u5728\u4e00\u4e2a\u4e09\u89d2\u5256\u5206$DT(P)$, \u4f7f\u5f97$DT(P)$\u5185\u7684\u4efb\u610f\u4e00\u4e2a\u4e09\u89d2\u5f62\u7684\u5916\u63a5\u5706\u5185\u90e8\u90fd\u4e0d\u542b$P$\u4e2d\u7684\u5143\u7d20(\u7a7a\u5706\u7279\u6027, \u4e5f\u53ef\u4ee5\u5229\u7528\u5185\u63a5\u56db\u8fb9\u5f62\u7684\u5bf9\u89d2\u4e92\u8865\u7684\u6027\u8d28\u8f85\u52a9\u5224\u65ad\u662f\u5426\u6ee1\u8db3\u7a7a\u5706\u7279\u6027), \u5219\u79f0\u4e09\u89d2\u5256\u5206$DT(P)$\u4e3a\u4e00\u4e2a\u4e8c\u7ef4Delaunay\u4e09\u89d2\u5256\u5206. \u4ee5\u4e0b\u5747\u53ea\u8ba8\u8bba\u4e8c\u7ef4\u60c5\u5f62, \u6545\u5c06\u4e8c\u7ef4Delaunay\u4e09\u89d2\u5256\u5206\u7b80\u8bb0\u4e3aDelaunay\u4e09\u89d2\u5256\u5206. Delaunay\u4e09\u89d2\u5256\u5206\u7684\u5b58\u5728\u6027\u4e0e\u552f\u4e00\u6027\u5747\u662f\u65e0\u6cd5\u4fdd\u8bc1\u7684.<\/p>\n<p>The Lawson Flip Algorithm\u662f\u4e00\u79cd\u751f\u6210Delaunay\u4e09\u89d2\u5256\u5206\u7684\u7ecf\u5178\u7b97\u6cd5. \u5176\u7b97\u6cd5\u6b65\u9aa4\u4e3a:<br \/>\n1) \u8ba1\u7b97\u79bb\u6563\u70b9\u96c6$P$\u7684\u4e00\u4e2a\u4e09\u89d2\u5256\u5206.<br \/>\n2) \u904d\u5386\u4e09\u89d2\u5256\u5206\u4e2d\u7684\u6bcf\u4e00\u4e2a\u56db\u8fb9\u5f62, \u82e5\u5f53\u524d\u56db\u8fb9\u5f62\u5bf9\u5e94\u7684\u5b50\u4e09\u89d2\u5256\u5206\u4e0d\u662f\u4e00\u4e2aDelaunay\u4e09\u89d2\u5256\u5206, \u5219\u5bf9\u56db\u8fb9\u5f62\u5185\u7684\u8fb9\u6267\u884cFlip\u64cd\u4f5c.<\/p>\n<p>\u8be5\u7b97\u6cd5\u7684\u7406\u8bba\u4fdd\u8bc1\u662f\u5982\u4e0b\u5b9a\u7406:<br \/>\n\u8bbe$P \\subseteq R^2$\u662f$n$\u4e2a\u70b9\u7684\u96c6\u5408, $\\mathcal{T}$\u662f$P$\u7684\u4e00\u4e2a\u4e09\u89d2\u5256\u5206. \u5219Lawson Flip\u7b97\u6cd5\u6700\u591a\u6267\u884c$\\binom{n}{2} = O(n^2)$\u6b21Flip\u64cd\u4f5c, \u4e14\u6700\u7ec8\u5f97\u5230\u7684\u4e09\u89d2\u5256\u5206$D$\u662f$P$\u7684\u4e00\u4e2aDelaunay\u4e09\u89d2\u5256\u5206.<br \/>\n\u4ee5\u4e0b\u4ec5\u8fdb\u884c\u76f4\u89c2\u610f\u4e49\u4e0a\u7684\u8bc1\u660e, \u5206\u4e3a\u4e24\u6b65\u8fdb\u884c.<br \/>\n1) \u7b97\u6cd5\u5fc5\u5b9a\u80fd\u591f\u505c\u6b62.<br \/>\n2) \u7b97\u6cd5\u6700\u7ec8\u5f97\u5230\u7684\u4e09\u89d2\u5256\u5206\u662f\u4e00\u4e2aDelaunay\u4e09\u89d2\u5256\u5206.<\/p>\n<p>\u8bc1\u660e\u524d\u9700\u8981\u5148\u5f15\u5165The Lifting Map\u7684\u6982\u5ff5: \u7ed9\u5b9a\u70b9$p = (x, y) \\in R^2$, \u5176\u63d0\u5347$l(p)$\u4e3a\u70b9$l(p) = (x, y, x^2 + y^2) \\in R^3$. \u4ece\u51e0\u4f55\u4e0a\u6765\u770b, $l$\u5c06\u70b9\u7ad6\u76f4\u63d0\u5347\u5230\u4e00\u4e2a\u5355\u4f4d\u629b\u7269\u9762\u4e0a, \u5982\u4e0b\u56fe\u6240\u793a.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/The-Lifting-Map.png\" alt=\"\" width=\"1211\" height=\"693\" class=\"aligncenter size-full wp-image-1361\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/The-Lifting-Map.png 1211w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/The-Lifting-Map-300x172.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/The-Lifting-Map-768x439.png 768w\" sizes=\"(max-width: 1211px) 100vw, 1211px\" \/><\/p>\n<p>\u5173\u4e8eLifting Map\u7684\u4e00\u4e2a\u91cd\u8981\u5f15\u7406\u4e3a: \u8bbe$C$\u662f\u5e73\u9762\u4e0a\u7684\u4e00\u4e2a\u5706, \u7ecf\u63d0\u5347\u540e$l(C) = \\{ l(p) | p \\in C \\}$\u4f4d\u4e8e\u4e00\u4e2a\u552f\u4e00\u7684\u5e73\u9762$h(C) \\subset R^3$\u4e0a. \u6b64\u5916, \u4efb\u4e00\u70b9$p \\in R^2$\u5728\u5706$C$\u5185(\u5916) \u5f53\u4e14\u4ec5\u5f53\u70b9$p$\u7ecf\u63d0\u5347\u540e\u5f97\u5230\u7684\u70b9$l(p)$\u5728\u5e73\u9762$h(C)$\u4e0b(\u4e0a), \u5982\u4e0b\u56fe\u6240\u793a.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Important-Property-of-the-Lifting-Map.png\" alt=\"\" width=\"1213\" height=\"830\" class=\"aligncenter size-full wp-image-1362\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Important-Property-of-the-Lifting-Map.png 1213w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Important-Property-of-the-Lifting-Map-300x205.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Important-Property-of-the-Lifting-Map-768x526.png 768w\" sizes=\"(max-width: 1213px) 100vw, 1213px\" \/><\/p>\n<p>\u7b80\u5355\u8bc1\u660e\u4e00\u4e0b\u8fd9\u4e2a\u5f15\u7406: \u4e0d\u59a8\u8bbe\u5e73\u9762\u4e0a\u7684\u5706$C$\u5bf9\u5e94\u7684\u65b9\u7a0b\u4e3a$$(x &#8211; x_C)^2 + (y &#8211; y_C)^2 = r_C^2,$$\u5176\u4e2d$(x_C, y_C)$\u4e3a\u5706$C$\u7684\u5706\u5fc3, $r_C$\u4e3a\u5706$C$\u7684\u534a\u5f84. \u5bf9\u4e8e\u5706\u5468\u4e0a\u7684\u70b9$(x, y)$, \u7531\u4e8e\u70b9$(x, y)$\u7ecf\u63d0\u5347\u540e\u4f4d\u4e8e\u629b\u7269\u9762\u4e0a, \u6ee1\u8db3\u5173\u7cfb\u5f0f$z = x^2 + y^2$, \u4ee3\u5165\u5706$C$\u5bf9\u5e94\u7684\u65b9\u7a0b\u53ef\u5f97$$z = 2x_Cx + 2y_Cy + (r^2 &#8211; x_C^2 &#8211; y_C^2),$$\u663e\u7136\u8fd9\u662f\u4e00\u4e2a\u5e73\u9762\u65b9\u7a0b, \u4e14\u7531\u4e8e\u5706$C$\u7684\u5706\u5fc3$(x_C, y_C)$\u4e0e\u534a\u5f84$r_C$\u5747\u662f\u56fa\u5b9a\u7684, \u6545\u8be5\u5e73\u9762\u65b9\u7a0b\u4e5f\u662f\u552f\u4e00\u7684. \u7c7b\u4f3c\u53ef\u63a8\u5f97\u5f15\u7406\u5269\u4f59\u90e8\u5206.<\/p>\n<p>$\\cdot$ <strong>Termination.<\/strong> \u4ece\u51e0\u4f55\u4e0a\u770b, Lawson Flip\u7b97\u6cd5\u53ef\u4ee5\u89e3\u91ca\u4e3a\u5c06\u4e00\u4e2a\u56db\u9762\u4f53\u4e2d\u6700\u4e0a\u9762\u7684\u4e24\u4e2a\u4e09\u89d2\u5f62\u66ff\u6362\u4e3a\u6700\u4e0b\u9762\u7684\u4e24\u4e2a\u4e09\u89d2\u5f62\u7684\u64cd\u4f5c, \u53ef\u7ed3\u5408\u4e0a\u8ff0\u5f15\u7406\u4e0e\u4e0b\u56fe\u7406\u89e3.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Lawson_Flip_1.png\" alt=\"\" width=\"1774\" height=\"667\" class=\"aligncenter size-full wp-image-1364\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Lawson_Flip_1.png 1774w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Lawson_Flip_1-300x113.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Lawson_Flip_1-768x289.png 768w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Lawson_Flip_1-1536x578.png 1536w\" sizes=\"(max-width: 1774px) 100vw, 1774px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Lawson_Flip_2.png\" alt=\"\" width=\"1073\" height=\"769\" class=\"aligncenter size-full wp-image-1365\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Lawson_Flip_2.png 1073w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Lawson_Flip_2-300x215.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Lawson_Flip_2-768x550.png 768w\" sizes=\"(max-width: 1073px) 100vw, 1073px\" \/><\/p>\n<p>\u4ece\u56db\u9762\u4f53\u4f53\u79ef\u7684\u89d2\u5ea6\u6765\u770b, \u6bcf\u4e00\u6b21\u8fdb\u884cLawson Flip\u7b97\u6cd5\u90fd\u51cf\u5c11\u4e86\u76f8\u5e94\u7684\u56db\u9762\u4f53\u4f53\u79ef(\u5176\u5b9e\u8fd9\u91cc\u6211\u6ca1\u6709\u5f88\u7406\u89e3\u56e7), \u7531\u4e8e\u56db\u9762\u4f53\u7684\u4f53\u79ef\u603b\u662f\u6709\u4e0b\u754c\u7684(0\u662f\u5176\u4e0b\u754c), \u800c\u6bcf\u6b21\u8fdb\u884cLawson Flip\u7b97\u6cd5\u5f97\u5230\u7684\u56db\u9762\u4f53\u7684\u4f53\u79ef\u6784\u6210\u7684\u5e8f\u5217\u662f\u4e00\u4e2a\u5355\u8c03\u9012\u51cf\u5e8f\u5217, \u6545\u7531\u5355\u8c03\u6709\u754c\u5b9a\u7406\u53ef\u77e5\u8be5\u7b97\u6cd5\u662f\u53ef\u6536\u655b\u7684. \u53e6\u5916\u4e00\u65b9\u9762, \u4e00\u65e6\u67d0\u6761\u8fb9\u88ab\u7ffb\u8f6c, \u5219\u8be5\u8fb9\u6240\u5728\u7684\u5e73\u9762\u4f1a\u4e25\u683c\u5904\u4e8e\u629b\u7269\u9762\u4e4b\u4e0a, \u4e14\u4e0d\u4f1a\u518d\u88ab\u7ffb\u8f6c(\u5176\u5b9e\u8fd9\u91cc\u6211\u4e5f\u6ca1\u6709\u5f88\u7406\u89e3\u56e7). \u53c8$n$\u4e2a\u70b9\u6700\u591a\u4ea7\u751f$\\binom{n}{2}$\u6761\u8fb9, \u6545Lawson Flip\u7b97\u6cd5\u6267\u884c\u7684\u6b21\u6570\u603b\u662f\u6709\u4e0a\u754c\u7684.<\/p>\n<p>$\\cdot$ <strong>Correctness.<\/strong> \u9996\u5148\u5b9a\u4e49\u5c40\u90e8Delaunay(Locally Delaunay) \u5256\u5206: \u8bbe\u7531Lawson Flip\u7b97\u6cd5\u5f97\u5230\u4e09\u89d2\u5256\u5206$D$, $\\triangle, \\triangle&#8217;$\u662f$D$\u4e2d\u7684\u4e24\u4e2a\u76f8\u90bb\u4e09\u89d2\u5f62. \u82e5$\\triangle$\u7684\u5916\u63a5\u5706\u5185\u90e8\u4e0d\u542b$\\triangle&#8217;$\u7684\u4efb\u4e00\u9876\u70b9, \u4e14\u53cd\u8fc7\u6765\u4e5f\u6210\u7acb, \u5219\u79f0$\\triangle, \\triangle&#8217;$\u6784\u6210\u4e00\u4e2a\u5c40\u90e8Delaynay\u5256\u5206. \u63a5\u4e0b\u6765\u4ece\u76f4\u89c2\u610f\u4e49\u4e0a\u7b80\u5355\u8bc1\u660e\u4e00\u4e0b\u7531Lawson Flip\u7b97\u6cd5\u5f97\u5230\u7684\u5c40\u90e8Delaynay\u5256\u5206\u53ef\u4ee5\u5f97\u5230\u5168\u5c40Delaynay\u5256\u5206\u7684\u4e8b\u5b9e.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Locally-Delaunay.png\" alt=\"\" width=\"1535\" height=\"789\" class=\"aligncenter size-full wp-image-1366\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Locally-Delaunay.png 1535w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Locally-Delaunay-300x154.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Locally-Delaunay-768x395.png 768w\" sizes=\"(max-width: 1535px) 100vw, 1535px\" \/><\/p>\n<p>\u8bc1: \u91c7\u7528\u53cd\u8bc1\u6cd5, \u82e5\u5c40\u90e8Delaunay\u4e09\u89d2\u5256\u5206$D$\u5e76\u975e\u5168\u5c40Delaynay\u5256\u5206, \u5219\u8bbe$\\tau$\u662f\u5c40\u90e8Delaunay\u4e09\u89d2\u5256\u5206$D$\u4e2d\u7684\u4e00\u4e2a\u4e09\u89d2\u5f62, $w_n \\in P$\u662f\u843d\u5728$\\tau$\u7684\u5916\u63a5\u5706\u5916\u90e8\u7684\u4e00\u4e2a\u70b9, $\\tau_n$\u662f\u5c40\u90e8Delaunay\u4e09\u89d2\u5256\u5206$D$\u4e2d\u4ee5$w_n$\u4e3a\u9876\u70b9\u7684\u4e00\u4e2a\u4e09\u89d2\u5f62, \u5219\u53ef\u4ee5\u5c06$v$\u4e0e$\\tau$\u4e2d\u4efb\u4e00\u70b9\u76f8\u8fde\u5f97\u5230\u7ebf\u6bb5$l$, \u6cbf\u7740\u7ebf\u6bb5$l$\u53ef\u5f97\u5230\u4e00\u5217\u5c40\u90e8Delaunay\u4e09\u89d2\u5256\u5206$D$\u4e2d\u6309\u987a\u5e8f\u76f8\u90bb\u7684\u4e09\u89d2\u5f62$\\tau, \\tau_1, \\cdots, \\tau_n$.<\/p>\n<p>\u7531\u4e8e\u4e09\u89d2\u5f62$\\tau, \\tau_1$\u76f8\u90bb, \u7531\u5c40\u90e8Delaunay\u4e09\u89d2\u5256\u5206\u5b9a\u4e49\u53ef\u77e5, $\\tau_1$\u4e2d\u4e0e\u516c\u5171\u8fb9\u76f8\u5bf9\u7684\u9876\u70b9$w_1$\u5fc5\u5b9a\u843d\u5728$\\tau$\u7684\u5916\u63a5\u5706\u5916\u90e8. \u518d\u770b\u76f8\u90bb\u7684\u4e24\u4e2a\u4e09\u89d2\u5f62$\\tau_1, \\tau_2$, \u7531\u5c40\u90e8Delaunay\u4e09\u89d2\u5256\u5206\u5b9a\u4e49\u53ef\u77e5, $\\tau_2$\u4e2d\u4e0e\u516c\u5171\u8fb9\u76f8\u5bf9\u7684\u9876\u70b9$w_2$\u5fc5\u5b9a\u843d\u5728$\\tau_1$\u7684\u5916\u63a5\u5706\u5916\u90e8, \u4ece\u800c\u843d\u5728$\\tau$\u7684\u5916\u63a5\u5706\u5916\u90e8, \u5982\u4e0a\u56fe(b)\u4e2d\u6240\u793a\u2026\u2026 \u7c7b\u4f3c\u53ef\u63a8\u5f97, $\\tau_n$\u4e2d\u7684\u9876\u70b9$w_n$\u4e5f\u5fc5\u843d\u5728$\\tau$\u7684\u5916\u63a5\u5706\u5916\u90e8, \u800c\u8fd9\u4e0e\u5047\u8bbe\u77db\u76fe, \u6545\u547d\u9898\u5f97\u8bc1.<\/p>\n<h4>22.4 Maximize the Minimum Angle<\/h4>\n<p>\u82e5\u79bb\u6563\u70b9\u96c6$P$\u7684Delaunay\u4e09\u89d2\u5256\u5206\u5b58\u5728, \u5219\u5176\u6700\u5c0f\u89d2\u662f\u79bb\u6563\u70b9\u96c6$P$\u7684\u6240\u6709\u4e09\u89d2\u5316\u7684\u6700\u5c0f\u89d2\u7684\u6700\u5927\u503c. \u63a5\u4e0b\u6765\u7b80\u5355\u8bc1\u660eDelaunay\u4e09\u89d2\u5256\u5206\u80fd\u591f\u6700\u5927\u5316\u6700\u5c0f\u89d2\u7684\u7279\u6027.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Maximize-the-Minimum-Angle.png\" alt=\"\" width=\"1430\" height=\"708\" class=\"aligncenter size-full wp-image-1368\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Maximize-the-Minimum-Angle.png 1430w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Maximize-the-Minimum-Angle-300x149.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Maximize-the-Minimum-Angle-768x380.png 768w\" sizes=\"(max-width: 1430px) 100vw, 1430px\" \/><\/p>\n<p>\u8bc1: \u4ec5\u5173\u6ce8\u4e0a\u56fe(b)\u5373\u53ef,<br \/>\n$\\cdot$ Flip\u524d\u4e24\u4e2a\u4e09\u89d2\u5f62\u7684\u516d\u4e2a\u5185\u89d2\u5206\u522b\u4e3a$\\alpha_1 + \\alpha_2, \\alpha_3, \\alpha_4, \\underline{\\alpha_1}, \\underline{\\alpha_2}, \\overline{\\alpha_3} + \\overline{\\alpha_4}$.<br \/>\n$\\cdot$ Flip\u540e\u4e24\u4e2a\u4e09\u89d2\u5f62\u7684\u516d\u4e2a\u5185\u89d2\u5206\u522b\u4e3a$\\alpha_1, \\alpha_2, \\overline{\\alpha_3}, \\overline{\\alpha_4}, \\underline{\\alpha_1} + \\alpha_4, \\underline{\\alpha_2} + \\alpha_3.$<br \/>\n\u7531\u5706\u5468\u89d2\u5b9a\u7406\u6613\u63a8\u5f97$$\\alpha_1 > \\underline{\\alpha_1}, \\alpha_2 > \\underline{\\alpha_2}, \\overline{\\alpha_3} > \\alpha_3, \\overline{\\alpha_4} > \\alpha_4,\\\\\\underline{\\alpha_1} + \\alpha_4 > \\alpha_4, \\underline{\\alpha_2} + \\alpha_3 > \\alpha_3,$$\u4ece\u800c\u547d\u9898\u5f97\u8bc1.<\/p>\n<h3>P23: Optimal Delaunay Triangulation\u4e0eVoronoi Diagram<\/h3>\n<p>\u672c\u8282\u662f\u8be5\u7cfb\u5217\u8bfe\u7a0b\u7684\u6700\u540e\u4e00\u8282, \u770b\u7740Voronoi Diagram\u4e0eCVT\u518d\u6b21\u51fa\u73b0\u5728\u773c\u524d, \u771f\u7684\u633a\u6709\u4eb2\u5207\u611f\u7684~<\/p>\n<h4>23.1 Optimal Delaunay Triangulation<\/h4>\n<p>\u6709\u65f6\u5019\u82e5\u4ec5\u662f\u5bf9\u79bb\u6563\u70b9\u96c6\u4f5cDelaunay\u4e09\u89d2\u5256\u5206, \u662f\u65e0\u6cd5\u5f97\u5230\u9ad8\u8d28\u91cf\u7684\u4e09\u89d2\u5256\u5206\u7684, \u5982\u5b58\u5728\u6700\u5c0f\u89d2\u4f9d\u65e7\u8f83\u5c0f\u7684\u95ee\u9898. \u4e3a\u4e86\u5c3d\u53ef\u80fd\u5730\u5b9e\u73b0\u6700\u5c0f\u89d2\u6700\u5927\u5316\u7684\u76ee\u6807, \u8fd8\u5e94\u9002\u5f53\u8c03\u6574\u70b9\u7684\u4f4d\u7f6e, \u4e00\u822c\u4ece\u66f2\u9762\u903c\u8fd1\u7684\u89d2\u5ea6\u51fa\u53d1\u6765\u4f18\u5316\u4e0b\u8ff0\u80fd\u91cf\u51fd\u6570,$$E = \\sum_{T \\in \\mathcal{T}} \\int\\limits_{T} | \\hat{u}(x) &#8211; u(x) | dx,$$\u5176\u4e2d, \u5404\u7b26\u53f7\u8bf4\u660e\u5982\u4e0b:<br \/>\n$\\cdot$ $u(x): z = x^2 + y^2.$<br \/>\n$\\cdot$ $\\hat{u}(x):$ $u$\u7684\u5206\u7247\u7ebf\u6027\u63d2\u503c.<br \/>\n$\\cdot$ $\\mathcal{T}:$ \u4e00\u4e2a\u4e09\u89d2\u5256\u5206.<br \/>\n\u4ece\u76f4\u89c2\u610f\u4e49\u4e0a\u7406\u89e3, \u66f4\u9ad8\u8d28\u91cf\u7684\u4e09\u89d2\u5256\u5206\u5bf9\u5e94\u7684\u56db\u9762\u4f53\u4f53\u79ef\u4e4b\u548c\u4e5f\u5f80\u5f80\u66f4\u5c0f. $u(x), \\hat{u}(x)$\u4e5f\u5206\u522b\u5bf9\u5e94\u4e0b\u56fe\u4e2d\u7684\u629b\u7269\u9762\u4e0e\u4e09\u89d2\u9762.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Optimal-Delaunay-Triangulation.png\" alt=\"\" width=\"589\" height=\"378\" class=\"aligncenter size-full wp-image-1372\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Optimal-Delaunay-Triangulation.png 589w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/Optimal-Delaunay-Triangulation-300x193.png 300w\" sizes=\"(max-width: 589px) 100vw, 589px\" \/><\/p>\n<p>\u5bb9\u6613\u6ce8\u610f\u5230, \u80fd\u91cf\u51fd\u6570$E$\u542b\u6709\u4e24\u7ec4\u672a\u77e5\u53d8\u91cf, \u5206\u522b\u662f\u9876\u70b9\u4f4d\u7f6e\u96c6\u4e0e\u4e09\u89d2\u5256\u5206.\u9488\u5bf9\u8fd9\u79cd\u542b\u4e24\u7ec4\u672a\u77e5\u53d8\u91cf\u7684\u80fd\u91cf\u51fd\u6570, \u53ef\u91c7\u7528\u4ea4\u66ff\u8fed\u4ee3\u7684\u65b9\u5f0f.<br \/>\n$\\cdot$ \u66f4\u65b0\u4e09\u89d2\u5256\u5206. \u904d\u5386\u6240\u6709\u8fb9, \u5bf9\u4e0d\u6ee1\u8db3\u7a7a\u5706\u7279\u6027\u7684\u8fb9\u6267\u884cFlip\u64cd\u4f5c.<br \/>\n$\\cdot$ \u66f4\u65b0\u9876\u70b9\u4f4d\u7f6e.<br \/>\n\u4e3b\u8981\u5173\u6ce8\u4e00\u4e0b\u9876\u70b9\u4f4d\u7f6e\u7684\u66f4\u65b0. \u5047\u8bbe\u6b64\u65f6Delaunay\u4e09\u89d2\u5256\u5206\u5df2\u88ab\u56fa\u5b9a, \u5219$$E = \\sum_{T \\in \\mathcal{T}} \\int\\limits_{T} | \\hat{u}(x) &#8211; u(x) | dx = \\sum_{T \\in \\mathcal{T}} \\int\\limits_{T} \\hat{u}(x) dx + C\\\\=\\sum_{T \\in \\mathcal{T}}\\frac{|T|}{3}(u(p_i) + u(p_j) + u(p_k)) + C,$$\u5176\u4e2d, \u4e0a\u8ff0\u63a8\u5bfc\u4e2d\u7b2c\u4e8c\u4e2a\u7b49\u5f0f\u662f\u6839\u636eDelaunay\u4e09\u89d2\u5256\u5206\u7684\u6027\u8d28\u5f97\u5230\u7684, \u6b64\u65f6$\\hat{u}(x)$\u5728\u5404\u4e2a\u4e09\u89d2\u5f62$T$\u4e0a\u603b\u662f\u5927\u4e8e$u(x)$\u7684, \u6545\u53ef\u53bb\u9664\u7edd\u5bf9\u503c\u7b26\u53f7; \u7b2c\u4e09\u4e2a\u7b49\u5f0f\u5219\u662f\u7531\u4e09\u68f1\u67f1\u7684\u4f53\u79ef\u516c\u5f0f\u5f97\u5230. \u63a5\u4e0b\u6765\u4ee4\u5176\u68af\u5ea6\u4e3a0, \u5f97$$\\nabla E_{p_i} = \\sum_{T \\in \\Omega(i)} \\frac{\\nabla|T|}{3}(u(p_i) + u(p_j) + u(p_k)) + \\frac{|\\Omega|}{3}\\nabla u(p_i) = 0\\\\ \\because \\sum_{T \\in \\Omega(i)} \\frac{\\nabla|T|}{3}u(p_i) = \\frac{u(p_i)}{3} \\sum_{T \\in \\Omega(i)} \\nabla|T| \\\\= \\frac{u(p_i)}{3} \\nabla|\\Omega| = \\frac{u(p_i)}{3} \\cdot 0 = 0\\\\ \\therefore \\nabla u(p_i) = -\\frac{1}{|\\Omega|} \\sum_{T \\in \\Omega(i)} \\frac{\\nabla|T|}{3}(u(p_j) + u(p_k)).$$\u63a5\u4e0b\u6765\u4fbf\u53ef\u5229\u7528Gauss\u2013Seidel\u8fed\u4ee3, \u9010\u6b65\u6839\u636e\u6bcf\u4e00\u4e2a$u(p_i)$\u7684\u68af\u5ea6\u66f4\u65b0\u6bcf\u4e00\u4e2a\u70b9$p_i$\u7684\u4f4d\u7f6e(\u7531\u4e8e\u53d1\u73b0\u8001\u5e08\u5728\u63a8\u5bfc\u65f6\u51fa\u73b0\u9519\u8bef, \u6545\u6b64\u5904\u4e5f\u4e0d\u518d\u7ee7\u7eed\u63a8\u5bfc, \u540e\u9762\u82e5\u6709\u9700\u8981\u518d\u8865\u5145). \u6b64\u5916, \u6b64\u5904$u(x)$\u4e5f\u5e76\u4e0d\u5c40\u9650\u4e8e\u524d\u9762\u63d0\u5230\u7684Lifting Map.<\/p>\n<h4>23.2 \u4e8c\u7ef4Voronoi Diagram<\/h4>\n<p>$\\cdot$ <strong>\u90ae\u5c40\u95ee\u9898.<\/strong> \u4e8c\u7ef4Voronoi Diagram(\u4ee5\u4e0b\u5747\u53ea\u8ba8\u8bba\u4e8c\u7ef4\u60c5\u5f62, \u6545\u5c06\u4e8c\u7ef4Voronoi Diagram\u7b80\u8bb0\u4e3aVoronoi Diagram) \u8d77\u6e90\u4e8e\u90ae\u5c40\u95ee\u9898: \u5047\u8bbe\u4e00\u4e2a\u57ce\u5e02\u6709$n$\u4e2a\u90ae\u5c40$p_1, \\cdots, p_n$, \u6709\u4eba\u5904\u4e8e\u8be5\u57ce\u5e02\u7684\u70b9$q$\u5904, \u60f3\u77e5\u9053\u54ea\u4e2a\u90ae\u5c40\u79bb\u4ed6\u6700\u8fd1? \u663e\u7136, \u4e00\u4e2a\u6700\u7b80\u5355\u7684\u65b9\u6cd5\u4fbf\u662f\u904d\u5386\u6240\u6709\u90ae\u5c40, \u8ba1\u7b97\u6700\u77ed\u8ddd\u79bb. \u4f46\u4e00\u4e2a\u66f4\u5f7b\u5e95\u7684\u89e3\u51b3\u65b9\u6848\u5e94\u8be5\u662f\u5efa\u7acb\u4e00\u4e2a\u6570\u636e\u7ed3\u6784\u6765\u5e94\u5bf9\u5404\u79cd\u5404\u6837\u7684\u67e5\u8be2\u4e0e\u90ae\u5c40\u6570\u91cf\u589e\u52a0\u5e26\u6765\u7684\u904d\u5386\u6d88\u8017. \u4e8e\u662f, \u53ef\u4ee5\u5c06\u8be5\u5e73\u9762\u5256\u5206\u4e3a\u82e5\u5e72\u4e2a\u533a\u57df, \u6bcf\u4e2a\u533a\u57df\u5185\u90fd\u6709\u4e14\u53ea\u6709\u4e00\u4e2a\u79cd\u5b50\u70b9(\u5bf9\u5e94\u4e8e\u4e00\u4e2a\u90ae\u5c40\u7684\u4f4d\u7f6e\u70b9), \u4f7f\u5f97\u6bcf\u4e2a\u533a\u57df\u5185\u7684\u6240\u6709\u70b9\u8ddd\u79bb\u5f53\u524d\u533a\u57df\u5185\u7684\u79cd\u5b50\u70b9\u7684\u8ddd\u79bb\u76f8\u6bd4\u8f83\u8ddd\u79bb\u5176\u5b83\u79cd\u5b50\u70b9\u7684\u8ddd\u79bb\u662f\u6700\u8fd1\u7684. \u63a5\u4e0b\u6765\u4fbf\u53ef\u4ee5\u7ed9\u51faVoronoi Cell\u7684\u6570\u5b66\u5b9a\u4e49.<\/p>\n<p>$\\cdot$ <strong>Voronoi Cell<\/strong> \u7ed9\u5b9a$R^2$\u4e0a\u7684\u70b9\u96c6$P = \\{ p_1, \\cdots, p_n \\}$, $p_i \\in P$\u6240\u5c5e\u7684Voronoi Cell $VP(i)$\u5b9a\u4e49\u4e3a$$VP(i) := \\{ q \\in R^2 | \\| q &#8211; q_i \\| \\le \\| q &#8211; p \\|, \\forall p \\in P \\},$$\u540c\u65f6\u6bcf\u4e00\u4e2aVoronoi Cell $VP(i)$\u9700\u8981\u6ee1\u8db3\u4e0b\u8ff0\u7ea6\u675f.<br \/>\n$\\quad \\cdot$ $VP(i) = \\cap_{j \\ne i} H(p_i, p_j)$, \u5176\u4e2d$H(p_i, p_j)$\u4e3a$p_i, p_j$\u4e4b\u95f4\u7684Bisector.<br \/>\n$\\quad \\cdot$ $VP(i)$\u975e\u7a7a\u4e14\u4e3a\u51f8\u96c6.<br \/>\n$\\quad \\cdot$ \u5e73\u9762\u4e0a\u6bcf\u4e00\u70b9\u90fd\u53ea\u5c5e\u4e8e\u4e00\u4e2aVoronoi Cell, \u6545\u6240\u6709\u7684Voronoi Cell\u6784\u6210\u5e73\u9762\u7684\u5256\u5206.<br \/>\n\u63a5\u4e0b\u6765\u4ecb\u7ecdVoronoi Diagram\u7684\u76f8\u5173\u5f15\u7406, \u8bb0$VV(P)$\u4e3aVoronoi Diagram\u7684\u9876\u70b9\u96c6, $VE(P)$\u4e3aVoronoi Diagram\u6240\u6709\u8fb9\u6784\u6210\u7684\u96c6\u5408, $VR(P)$\u4e3aVoronoi Diagram\u6240\u6709\u9762\u6784\u6210\u7684\u96c6\u5408.<\/p>\n<p>$\\cdot$ <strong>\u5f15\u74061<\/strong> \u5bf9\u4e8e$\\forall v \\in VV(P)$, \u4e0b\u5217\u547d\u9898\u6210\u7acb.<br \/>\n$\\quad \\cdot$ $v$\u4e3a$VE(P)$\u4e2d\u81f3\u5c11\u4e09\u6761\u8fb9\u7684\u4ea4\u96c6\u4e2d\u7684\u5143\u7d20.<br \/>\n$\\quad \\cdot$ $v$\u4e3a$VR(P)$\u4e2d\u81f3\u5c11\u4e09\u4e2a\u9762\u7684\u4ea4\u96c6\u4e2d\u7684\u5143\u7d20.<\/p>\n<p>\u8bc1: \u7531\u4e8e\u6240\u6709\u7684Voronoi Cell\u5747\u4e3a\u51f8\u96c6, \u6545\u6bcf\u4e00\u4e2a\u5185\u89d2\u5747\u5c0f\u4e8e$\\pi$. \u663e\u7136, \u82e5$v$\u4e3a$VE(P)$\u4e2d\u4e0d\u591a\u4e8e\u4e24\u6761\u8fb9\u7684\u4ea4\u96c6\u4e2d\u7684\u5143\u7d20, \u5219$v$\u5468\u56f4\u7684\u5185\u89d2\u548c\u5c0f\u4e8e$2\\pi$, \u4ece\u800c\u6240\u6709\u7684Voronoi Cell\u65e0\u6cd5\u6784\u6210\u5e73\u9762\u7684\u5256\u5206, \u77db\u76fe. \u6545\u547d\u9898\u5f97\u8bc1.<\/p>\n<p>$\\cdot$ <strong>\u5f15\u74062<\/strong> \u5bf9\u4e8e$\\forall v \\in VV(P)$, \u4e0b\u5217\u547d\u9898\u6210\u7acb.<br \/>\n$\\quad \\cdot$ $v$\u4e3a\u67d0\u4e2a\u5706$C$\u7684\u5706\u5fc3, \u5176\u4e2d, \u5706$C$\u81f3\u5c11\u8fc7$P$\u4e2d\u4e09\u4e2a\u70b9.<br \/>\n$\\quad \\cdot$ $C(v)^{\\circ} \\cap P = \\emptyset$, \u5176\u4e2d, $C(v)^{\\circ}$\u4e3a$C(v)$\u7684\u5185\u70b9\u96c6.<\/p>\n<p>\u8bc1: \u53cd\u8bc1\u6cd5, \u5047\u8bbe\u5b58\u5728\u70b9$p_l \\in C(v)^{\\circ}$, \u5219\u9876\u70b9$v$\u8ddd\u79bb$p_l$\u6700\u8fd1(\u76f8\u6bd4\u8f83$p_1, \\cdots, p_k$), \u8fd9\u4e0e\u9876\u70b9$v$\u5904\u4e8e$VP(1),VP(2), \\cdots$\u6216\u8005$VP(k)$\u5185\u7684\u4e8b\u5b9e\u77db\u76fe, \u6545\u547d\u9898\u5f97\u8bc1.<\/p>\n<h4>23.3 Duality: Delaunay triangulation<\/h4>\n<p>\u5bf9\u4e8e\u7ed9\u5b9a\u7684\u56fe$G$, \u5f97\u5230\u56fe$G$\u7684\u5bf9\u5076\u56fe$G&#8217;$\u7684\u89c4\u5219\u5982\u4e0b:<br \/>\n$\\cdot$ \u5728\u56fe$G$\u7684\u6bcf\u4e00\u4e2a\u9762$f_i$\u5185\u53d6\u4e00\u4e2a\u70b9$v_i&#8217;$\u4f5c\u4e3a\u5bf9\u5076\u56fe$G&#8217;$\u7684\u4e00\u4e2a\u9876\u70b9.<br \/>\n$\\cdot$ \u5bf9\u4e8e\u56fe$G$\u7684\u4e00\u6761\u8fb9$e_i$, \u82e5$e_i$\u4e3a\u56fe$G$\u4e2d\u4e24\u4e2a\u9762\u7684\u516c\u5171\u8fb9, \u5219\u8fde\u63a5\u8fd9\u4e24\u4e2a\u9762\u7684\u9876\u70b9, \u4e14\u5176\u8fde\u7ebf\u9700\u8981\u7a7f\u8fc7$e_i$; \u82e5$e_i$\u4e3a\u56fe$G$\u4e2d\u67d0\u4e2a\u9762\u7684\u5272\u8fb9, \u5219\u4ee5\u8be5\u9762\u9876\u70b9\u4f5c\u73af, \u4e14\u8ba9\u5b83\u4e0e$e_i$\u76f8\u4ea4.<\/p>\n<p><strong>\u5b9a\u7406<\/strong> \u8bbe\u70b9\u96c6$P \\subset R^2$\u542b\u6709\u7684\u70b9\u7684\u6570\u91cf\u5927\u4e8e3, \u4e14\u70b9\u96c6$P$\u5185\u4efb\u610f\u4e09\u70b9\u4e0d\u5171\u7ebf, \u4efb\u610f\u56db\u70b9\u4e0d\u5171\u5706, \u5219\u70b9\u96c6$P$\u7684Voronoi Diagram $VD(P)$\u7684\u5e73\u9762\u5bf9\u5076\u56fe\u662f\u552f\u4e00\u7684, \u4e14\u6070\u4e3a\u70b9\u96c6$P$\u7684Delaunay\u4e09\u89d2\u5256\u5206.<\/p>\n<p>\u8bc1: (\u5fc5\u8981\u6027) \u6839\u636e\u51f8\u5305, \u4e09\u89d2\u5256\u5206\u4e0e\u7a7a\u5706\u7279\u6027\u7684\u5b9a\u4e49\u5373\u53ef\u5f97\u8bc1.<br \/>\n(\u5145\u5206\u6027) \u6839\u636e\u5916\u63a5\u5706\u5706\u5fc3\u4e0e\u7a7a\u5706\u7279\u6027\u7684\u5b9a\u4e49\u5373\u53ef\u5f97\u8bc1.<\/p>\n<h4>23.4 CVT<\/h4>\n<p>CVT\u662f\u4e00\u79cd\u7279\u6b8a\u7684Voronoi Diagram, \u5176\u6bcf\u4e00\u4e2aVoronoi Cell $V_i$\u7684\u79cd\u5b50\u70b9$p_i$\u90fd\u6070\u4e3a\u5176\u8d28\u5fc3, \u5176\u4e2d, Voronoi Cell $V_i$\u7684\u8d28\u5fc3\u5b9a\u4e49\u4e3a$$c_i = \\frac{\\int_{V_i} \\| x &#8211; p_i \\|^2 dx}{\\int_{V_i}dx}.$$\u901a\u5e38\u53ef\u901a\u8fc7\u4f18\u5316\u4e0b\u8ff0\u80fd\u91cf\u51fd\u6570\u5f97\u5230CVT:$$E(p_1, \\cdots, p_n, V_1, \\cdots, V_n) = \\sum^n_{i = 1} \\int_{V_i} \\| x &#8211; p_i \\|^2 dx.$$\u5bf9\u4e8e\u4e0a\u8ff0\u542b\u6709\u4e24\u7ec4\u672a\u77e5\u53d8\u91cf\u7684\u6700\u4f18\u5316\u95ee\u9898\u800c\u8a00, \u53ef\u5229\u7528Lloyd\u8fed\u4ee3\u7b97\u6cd5\u8fdb\u884c\u6c42\u89e3, \u7b97\u6cd5\u6b65\u9aa4\u5982\u4e0b\u6240\u793a.<br \/>\n$\\cdot$ \u6839\u636e\u79cd\u5b50\u70b9$p_i$\u6784\u9020\u76f8\u5e94\u7684Voroni Diagram.<br \/>\n$\\cdot$ \u8ba1\u7b97Voroni Cell $V_i$\u7684\u8d28\u5fc3$c_i$, \u5e76\u79fb\u52a8\u79cd\u5b50\u70b9$p_i$\u81f3\u76f8\u5e94\u7684\u8d28\u5fc3\u5904.<br \/>\n$\\cdot$ \u91cd\u590d\u4e0a\u8ff0\u4e24\u6b65\u76f4\u81f3\u7b97\u6cd5\u6536\u655b.<\/p>\n<h4>23.5 Variational Shape Approximation(VSA)<\/h4>\n<p>\u4e4b\u524d\u5df2\u7ecf\u5b66\u8fc7VSA, \u5982\u4eca\u5b66\u5b8c\u4e86CVT, \u6211\u4eec\u53ef\u4ee5\u91cd\u65b0\u4eceCVT\u7684\u89d2\u5ea6\u51fa\u53d1\u89e3\u91caVSA. \u56de\u987e\u4e00\u4e0b, VSA\u7684\u76ee\u6807\u662f\u7528\u4e00\u4e2a\u4ee3\u7406\u96c6$P = \\{ P_1, \\cdots, P_k \\}$\u903c\u8fd1\u8f93\u5165\u7f51\u683c$M$, \u5373$$M = R_1 \\cup \\cdots \\cup R_k \\approx P_1 \\cup \\cdots \\cup P_k$$ \u5176\u4e2d, $R = \\{ R_1, \\cdots, R_k \\}$\u662f\u5bf9\u8f93\u5165\u7f51\u683c$M$\u7684\u4e00\u4e2a\u5256\u5206, \u4ee3\u7406$P_i$\u662f\u6307\u7a7a\u95f4\u4e2d\u7684\u4e00\u4e2a\u5e73\u9762$(x_i, n_i)$. \u800cVSA\u6240\u7814\u7a76\u7684\u6700\u4f18\u5316\u95ee\u9898\u4e3a: \u7ed9\u5b9a$k \\in N$, \u4e09\u89d2\u7f51\u683c$M$\u4e0e\u8bef\u5dee\u5ea6\u91cf$E$($L^2$\u6216$L^{2,1}$), \u5bfb\u627e\u4e00\u4e2a\u5256\u5206$R = \\{ R_1, \\cdots, R_k \\}$\u4e0e\u4e00\u4e2a\u4ee3\u7406\u96c6$P = \\{ P_1, \\cdots, P_k \\}$\u4f7f\u5f97\u4e0b\u8ff0\u5173\u4e8e\u626d\u66f2\u7a0b\u5ea6\u7684\u80fd\u91cf\u51fd\u6570\u6700\u5c0f,$$E(R, P) = \\sum^k_{i=1}E(R_i, P_i),$$\u5176\u4e2d, $R_i$\u4e0e$P_i$\u4e4b\u95f4\u7684\u8bef\u5dee\u5ea6\u91cf\u6709\u4e24\u79cd\u5b9a\u4e49\u65b9\u5f0f, \u5206\u522b\u4e3a<br \/>\n$\\cdot$ $L^2$\u8bef\u5dee:$$L^2(R_i, P_i) = \\int_{x \\in R_i}(n^T_ix &#8211; n^T_ix_i)^2dx.$$$\\cdot$ $L^{2,1}$\u8bef\u5dee:$$L^{2,1}(R_i, P_i) = \\int_{x \\in R_i}\\left \\| n(x) &#8211; n_i \\right \\|^2 dx.$$\u53ef\u4f7f\u7528Lloyd\u7b97\u6cd5\u6c42\u89e3\u4e0a\u8ff0\u6700\u4f18\u5316\u95ee\u9898, \u7b97\u6cd5\u6b65\u9aa4\u5982\u4e0b\u6240\u793a.<br \/>\n$\\cdot$ <strong>\u521d\u59cb\u5316.<\/strong> \u4efb\u9009$k$\u4e2a\u4e09\u89d2\u5f62\u6784\u6210\u7684\u96c6\u5408\u4f5c\u4e3a$R$, \u8fd9$k$\u4e2a\u4e09\u89d2\u5f62\u6240\u5728\u7684\u5e73\u9762\u6784\u6210\u7684\u96c6\u5408\u4f5c\u4e3a$P$.<br \/>\n$\\cdot$ <strong>\u51e0\u4f55\u5212\u5206\u9636\u6bb5.<\/strong> \u5bfb\u627e\u5bf9$P$\u62df\u5408\u6548\u679c\u6700\u597d\u7684\u5256\u5206$R$.<br \/>\n$\\cdot$ <strong>\u4ee3\u7406\u62df\u5408\u9636\u6bb5.<\/strong> \u56fa\u5b9a\u5256\u5206$R$, \u540c\u65f6\u8c03\u6574\u4ee3\u7406\u96c6. \u4e0e\u4e0a\u4e00\u8282\u4ecb\u7ecd\u7684Lloyd\u7b97\u6cd5\u6b65\u9aa4\u6709\u6240\u4e0d\u540c\u7684\u662f, \u6b64\u5904\u9700\u8981\u8ba1\u7b97\u7684&#8221;\u8d28\u5fc3&#8221;\u662f$n_i$.<br \/>\n\u7b97\u6cd5\u4f2a\u4ee3\u7801\u5982\u4e0b\u56fe\u6240\u793a.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/VSA-Perudo-Code.png\" alt=\"\" width=\"1176\" height=\"837\" class=\"aligncenter size-full wp-image-1373\" srcset=\"https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/VSA-Perudo-Code.png 1176w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/VSA-Perudo-Code-300x214.png 300w, https:\/\/www.caiqinyi.cn\/wp-content\/uploads\/2021\/10\/VSA-Perudo-Code-768x547.png 768w\" sizes=\"(max-width: 1176px) 100vw, 1176px\" \/><\/p>\n<p>\u81f3\u6b64, \u6570\u5b57\u51e0\u4f55\u5904\u7406\u8bfe\u7a0b\u7b14\u8bb0\u5b8c\u7ed3\u6492\u82b1. *\u2605,\u00b0*:.\u2606(\uffe3\u25bd\uffe3)\/$:*.\u00b0\u2605* \u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u672c\u6587\u4e3b\u8981\u7528\u4e8e\u8bb0\u5f55\u5b66\u4e60\u5085\u5b5d\u660e\u8001\u5e08\u7684\u6570\u5b57\u51e0\u4f55\u5904\u7406\u8bfe\u7a0b\u65f6\u5bf9\u81ea\u5df1\u6709\u6240\u542f\u53d1\u7684\u7b14\u8bb0~ \u89c6\u9891\u94fe\u63a5: \u6570\u5b57\u51e0\u4f55\u5904\u7406-\u4e2d\u56fd\u79d1\u5b66\u6280 &hellip; <a href=\"https:\/\/www.caiqinyi.cn\/index.php\/2021\/10\/03\/digital_geometry_processing_course_notes\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">\u6570\u5b57\u51e0\u4f55\u5904\u7406\u8bfe\u7a0b\u7b14\u8bb0(\u5df2\u5b8c\u7ed3)<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"_links":{"self":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/1163"}],"collection":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/comments?post=1163"}],"version-history":[{"count":107,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/1163\/revisions"}],"predecessor-version":[{"id":1191,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/1163\/revisions\/1191"}],"wp:attachment":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/media?parent=1163"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/categories?post=1163"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/tags?post=1163"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}