三维曲线法向量估计算法及其在曲面模型生成中的应用

þþHOS T E D B Y可在www.sciencedirect.com网站上查阅计算设计与工程学报2（2015）67www.elsevier.com/locate/jcde由边界曲线估计曲面法线的一种算法Jisoon Parka，n，Taewon Kimb，Seung-Yeob Baekc，Kunwoo Leeba3D Systems Korea，Inc. 创新中心，525，Seolleung-ro，Gangnam-gu，Seoul，Republic of Koreab首尔国立大学机械和航空航天工程学院，1，Gwanak-ro，Gwanak-gu，Seoul，Republic of Koreac首尔国立大学先进机械和设计研究所，1，Gwanak-ro，Gwanak-gu，Seoul，Republic of Korea接收日期：2014年8月11日;接收日期：2014年11月13日;接受日期：2014年11月27日2014年12月6日在线发布摘要近年来，随着基于草图接口的几何造型方法的不断完善，由三维曲线生成曲面模型然而，曲面的三维曲线网络仍然是一个模糊的问题，由于缺乏几何信息。本文提出了一种新的算法来估计三维曲线的法向量，这与用户的意图密切相关利用3D曲线的RMF（旋转最小化框架）定义弯曲能量，并将此最小能量框架估计为符合设计意图的框架。所提出的算法证明了各种曲线网络的曲面模型创建。本文提出的三维曲线几何信息估计算法，可用于草图造型过程中新信息的提取。同时，通过曲线网络与曲面生成算法的融合，有望形成一种新的三维建模框架。&2015 年 CAD/CAM 工 程 师 协 会 。 由 Elsevier 制 作 和 主 持 。 这 是 一 个 在 CC BY-NC-ND 许 可 证 下 的 开 放 获 取 文 章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。关键词：计算机辅助设计;曲线网络;曲面造型;曲面法线估计1. 介绍尽管经过数十年的研究和开发，三维（3D）建模仍然是一个重大挑战。计算机辅助设计（CAD），尽管其巨大的进步，从初始阶段的布尔运算基本图表的各种几何运算，仍然需要一个漫长的培训期和高度的技术专长。近年来，出现了用于从设计师的二维（2D）草图构建3D曲线网络的新颖建模技术，以降低使用专业3D建模工具的障碍[1这种建模方法被广泛用于设计初始阶段的概念设计，因为它们有助于直观地表达设计师的想法，并为额外的创造性元素提供空间。n通讯作者。联系电话：82 2 3218 0596;传真：82 2 6262 9999。电子邮件地址：Jisoon. 3DSystems.com（J. Park）。同行评审由CAD/CAM工程师协会负责尽管基于草图的建模工具具有优势，但仅凭3D曲线网络无法提供足够的视觉反馈。3D曲线网络只给我们设计师绘制的特征线，而不是完整的渲染模型。从严格意义上说，它们不是模型，只是一组线条。它们没有任何表面信息，因此很难想象模型的详细形状。因此，从绘制的曲线网络构造曲面模型是必不可少的。除了提供更精确的视觉反馈外，构建的表面模型还可用于各种应用领域，如分析，模拟和3D打印。然而，构建仅具有曲线上的位置信息和拓扑关系的模型具有不确定性的固有问题，其为许多分析方法而不是最优解决方案提供了空间。这个基本问题在CAD领域已经被长期处理，并被称为放样或蒙皮。这是由于生成的模型缺乏几何信息而产生的问题。为了解决这一问题，需要定义一种能够精确反映附加约束条件或设计意图的优化模型。http://dx.doi.org/10.1016/j.jcde.2014.11.0072288-4300/2015 CAD/CAM工程师协会。&由Elsevier制作和主持。这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。68J. Park等人/Journal of Computational Design and Engineering 2（2015）67解决这些问题的困难在于：（i）是否可以从曲线的位置信息和拓扑关系中获得额外的几何信息（可能性问题），以及（ii）以某种方式获得的几何信息是否正确地反映了设计意图（验证问题）。在此背景下，本研究旨在通过确定三维曲线网络的几何特征来实现曲面造型的自动实现。为了确定这样的几何特征，使用旋转最小化框架（RMF）来确定目标曲线上的点的新框架。RMF是一种定义在曲线上的移动正交标架，它不绕曲线的瞬时切线旋转。由于其最小的扭曲，RMF被广泛应用于计算机图形学，运动设计和CAD中的扫描曲面建模。虽然它比Frenet标架计算困难，但它没有曲面造型中不可接受的不连续性。RMF具有这些特点，适合于曲线几何信息的估计。使用这个新定义的框架，我们根据草图教程和以前的认知相关研究确定了与设计意图相匹配的曲线的法向量。本文提出的方法与现有文献中提出的方法不同之处在于，通过建立反映设计意图的优化方程和确定法向量，允许在缺乏几何信息的情况下进行曲线造型。在以往的研究中，大多数曲面模型的生成方法都是基于已知几何信息的曲面片生成算法。本文提出了一种由边界曲线估计曲面法向量的新方法。它不仅对从曲线网络构造三维模型有较好的效果，而且对未知参数的估计也有重要意义几何信息本文的其余部分组织如下：第2节介绍了相关领域现有论文所采用的解决问题的方法。第3节描述了所提出的曲面造型的整个过程。第4节详细描述了用于确定几何特征的算法以及基于这些特征的建模过程。第5节提供了各种曲线网络的建模结果的概述。最后，第六部分是结论、局限性和未来的研究方向。2. 文献综述自从十多年前引入使用基于草图的界面的建模方法以来，它一直是激烈研究的对象Teddy，Igarashi等人开发的系统[4]通过向轮廓所包围的表面添加嵌入式外观，将2D轮廓转换为3D表面，从而从简单的草图中实现直观的建模。Nealen等人开发的Fiber-mesh[5]增加了功能特性，允许自由转换和修正基于Teddy的表面。Rivers等人[6]提出了一种通过整合多因子2D轮廓数据进行3D建模的新算法。与这一研究流并行的是，有相当多的研究集中在3D曲线网络的构建方法上。由Bae等人提出的ILoveSketch[1]是一个用于构建3D曲线网络的系统，允许在基于手势的界面上直接绘制草图。关于JustDrawIt！Grimm和Joshi[2]通过分析新绘制的2D草图并定义其与现有草图的关系，提出了一种2D到3D的转换方法。Schmidt等人[3]通过分析草图绘制过程并将2D草图重建为3D草图来实现数学模型。Schaefer等人的论文[7]代表了基于如此构建的3D曲线网络进行曲面建模的研究。本文提出了一种改进的方法，以满足C1连续性的模型，生成矩形片从相邻的曲线内构建的曲线网络和分割他们使用Catmull-Clark细分方法。虽然该方法在曲线网络精确描述模型的前提下取得了令人满意的结果，但在处理复杂曲线草图时存在模型纠缠的局限性。Abbasinejad等人。[8]通过使用拉普拉斯方法而不是优化方法通过线性化来定义问题。在这种方法中，任何给定的圆被渲染成三角形网格，然后通过连接每个曲线片的轮廓上的网格来构建模型，并通过使用线性插值来生成类似于肥皂片的模型。虽然它具有快速线性代数计算的优点，但由于不充分利用几何数据Bessmeltsev等人[9]对基于设计的建模方法进行了研究，其中模型是从矩形网格中生成的，该矩形网格是用从表面上的曲线迭代提取后最好地反映设计的曲线对构建的。该方法的优点在于，由于其使用考虑设计的优化方法，因此所得到的模型的质量优异，但缺点在于，需要大量时间来从目标曲线提取所有曲线对。迄今为止已知的最新方法是Abbasinejad等人提出的补丁分解方法[10]第10段。该方法通过将曲面片分解为准平面曲面片来解决复杂曲面片的生成问题这种新方法的主要限制是不光滑的连续性，因为补丁是通过分解产生的。虽然这些研究也将曲线网络转换为3D表面模型，但结果与我们为设计者提供视觉反馈的目的不同。它应该计算足够快，以显示响应设计师草图的结果模型，并提供精确的视觉反馈。Schaefer等[7]用于复杂曲线网络时，没有得到一致的结果Bessmeltsev等人[9]花费太多时间，因此无法实时显示结果。阿巴西-内贾德等[8，10]可能会生成真实的表面模型-J. Park等人/Journal of Computational Design and Engineering 2（2015）6769Fig. 1.五种方法来创建单个复杂贴片边界的曲面近似：（a）Schaefer等人的放样曲线网络。[7]，（b）Bessmeltsev等人的设计驱动四边形。[9]，（c）Abbasinejad等人的线性拉普拉斯平滑。[8]，（d）Abbasinejad等人的最小直纹曲面。[10]，以及（e）我们的方法，该方法估计符合设计意图的曲面法线时间，但有弱点，不能提供足够的视觉反馈。我们的研究弥补了这些缺陷，估计新的几何信息，反映设计意图和构建表面模型的基础上。图1示出了使用现有方法之一和本文中提出的用于对闭合草图进行建模的方法所获得的结果。3. 曲面造型图 2展示了本文所提出的曲面造型的全过程。曲面造型过程分为两个子过程：法向量的确定（如图2（d）所示）和初始网格的生成（如图2（d）所示）。 2（b）和（c），对于对应于图2所示输入的目标曲线。 2（a）. 这些数据用于获得网格的每个顶点的目标法向量，如图所示。 2（e），导致图中所示的结果。 2（f）.获得法向量的子过程涉及新帧的基于RMF的定义。RMF由初始向量和与曲线相切的向量确定，从而改变初始向量并迭代地寻找使RMF定义的计算成本最小化的帧的值。然后从定义的坐标系中确定曲线的法向量选择能够反映设计意图的框架的成本在第4.1和第4.2节中定义，包括设置曲线的新框架和确定曲线的法向量的过程曲面建模的第二个子过程涉及到生成代表整体形状的三角形网格（网格生成）和提高其质量（网格光顺）。在第4.3节中解释了应用CAD领域中使用的孔填充算法的初始网格生成。网格光顺是建模过程的最后一步，其中所有网格顶点的目标法向量是从曲线的法向量获得的，然后，它们被应用于初始网格。第4.4包含对这一过程的方法论解释。4. 算法4.1. 曲面弯曲能根据Mamassian和Landy[11]进行的草图感知研究的结果，在简单的草图中，曲率较小的曲线更容易被感知。Rose等人[12]对可展曲面的研究提出了类似的假设并进行了实验验证。Shao等人[13]和Zhuang等人的研究也支持这一理论。[14]第10段。为了量化曲率，我们将曲面弯曲能定义如下：如果在构成曲面片的曲线的急剧弯曲部分附近，曲线的法向量的变化很小，则曲率被认为是小的。在图3（a）和（b）中标记的法向矢量中，图3中的相邻法向矢量。与图3（a）相比，图3（b）具有较小的变化和较小的曲率。这可以通过以下等式表示：∑arccos<$nv1;nv2<$V Vc曲线g的交点曲面弯曲能的最小化相当于表面积的最小化。换句话说，曲面弯曲能的定义假定了一个最小曲面，并与曲面建模直接相关。4.2. 曲线法向量的确定构成面片的曲线的法向矢量应该具有连续性;即，不应该有太大的变化。可使用RMF[13]满足此要求。RMF是用初始向量和与曲线相切的向量计算的;在这项研究中，我们 使 用 了 Wang 等 人 提 出 的 加 倍 反 射 方 法 。 [15]计 算RMF。从曲线的位置信息可以得到与曲线相切的矢量。因此，为了获得最小化曲面弯曲能量的RMF，70J. Park等人/Journal of Computational Design and Engineering 2（2015）67i;jJ我我图二.我们的表面模型创建过程（a）输入3D边界曲线，（b）初始三角形网格，（c）网格细化，（d）使用RMF和弯曲能量估计输入曲线的法向量，（e）根据（d）的结果计算目标表面法线，以及（f）用目标法线进行网格光顺探索在搜索的解决方案，产生最小值的总和的三角形表面积的网格。图2（b）示出了由此构成的初始网格。为了应用4.2节中获得的法向量，通过向网格添加顶点来提高网格质量，如图2（c）所示。4.4. 网格光顺算法在获得曲线的所有法向量后，网格内顶点的法向量将使用调和场进行插值调和函数f的f应满足拉普拉斯方程。2019-02 - 25使用离散拉普拉斯算子，我们可以这样写：图三. 表面弯曲能的定义。之间的角度差相邻点的法向量指示表面弯曲的量。在这种情况下，（a）比（b）弯曲得更多∑ω。F.v-fv0;vAV如第4.1节所述，应执行迭代计算，从而改变RMF的初始向量。新帧的一个轴被设置为垂直于在起始点处与曲线相切的那些轴的向量。在通过逐渐改变初始向量进行迭代计算之后，具有曲面弯曲能量的最低值的RMF被确定为曲线的法线向量我们需要求解非线性方程，以获得最小化方程的解。（一）.但利用RMF可将该方程关于曲线的初始法向量进行简化。4.3. 初始网格生成为了在3D曲面上绘制的闭合曲线上生成平滑的网格而不扭曲，考虑整体曲线形状至关重要。许多基于CAD的孔填充算法服务于此目的。在Barequet和Sharir的研究中，所有构成闭曲线的顶点都是ωi;j<$cotαi;j<$cotβi;j顶点vig <$3 <$的Ni <$f vj1-环顶点图4列出了等式符号。设f是曲线上顶点的法向量，则网格顶点的法向量可以通过线性方程获得。为了实现到一个模型的转换，满足用户的预期目的，我们适用于网格的所有顶点的法向量，从而使用山田等人建议的离散弹簧模型[17]第10段。5. 结果如图5所示的结果所示，所提出的算法使得能够将在缺乏几何信息的条件下生成的初始网格转换为近似用户预期目的的自然外观模型。我们使用的测试数据从viANi我J. Park等人/Journal of Computational Design and Engineering 2（2015）6771我爱素描[1]和JustDrawIt！[2]作为输入信息的曲线网络。我们处理了从曲线网络（边界曲线）构建曲面模型，并手动从曲线网络中提取每个面片。Abbasinejad等人[8];Zhuang等人[14]处理了从曲线网络中提取斑块周期的方法。通过这些研究，我们可以自动化补丁查找过程。使用本文提出的算法，我们成功地生成补丁的各种类型的曲线，无论是一个平面曲线清楚地显示用户的意图或曲线具有高度复杂的结构。这一结果可以得到，因为见图4。 拉普拉斯方程的符号。该算法估计反映设计意图的几何特征。与现有方法的结果比较如图1所示。图中所示的模型是使用ILoveSketch [1]绘制的“roadster”。Abbasinejad 等 人 [8]和 Schaefer 等 人 [7]（ 图 1 （ a ） 和（c））的结果似乎是最小曲面，但很难说它们反映了设计意图。Bessmeltsev等人的方法。[9]可以获得如图1（c）所示的高质量表面模型，因为他们在算法中考虑了设计意图，但计算时间仍然是一个问题。Abbasi-nejad等的结果。[10]（Fig. 1（d））看起来比前三个结果更接近其设计意图。其分解过程简化了问题，但在面片连接处出现不光滑连续。我们的方法（图1（e））显示了视觉上优于其他方法的结果，证明了估计的几何信息在构建表面模型中起着重要作用。通过在包括补片的整个曲线上的网格生成以及根据用户的意图定制的法向量的确定，可以获得优异的结果6. 结论在本文中，我们提出了一种算法，可以自动生成一个模型定制用户的意图从草图为基础的三维曲线。为了获得曲面造型所需的几何信息，我们建立了一个方程，该方程描述了通过使用基于RMF的最小扭曲条件和凹偏好条件来获得曲线我们还获得了图五、结果表明，该算法适用于各种曲线网络的输入.第一列是来自ILoveSketch[1]和JustDrawIt[2]的输入曲线。第二列和第三列分别显示了不带和带目标法向光顺的合成网格72J. Park等人/Journal of Computational Design and Engineering 2（2015）67通过执行迭代计算来匹配用户意图的曲线的法向量，并通过相应地变换网格来实现曲面模型。该算法在缺乏几何信息的情况下，将草图意图以方程的形式呈现出来，从而通过法向量的最优解获得新的几何信息通过将相邻块的法线向量数据与针对每个块获得的边界曲线的法线向量相加，可以获得更接近用户意图的网格该方法结合曲线网络技术，为三维建模提供了一种新的利益冲突作者声明不存在竞争性的经济利益。确认这项研究得到了韩国政府资助的韩国国家研究基金会赠款的支持（教育部（赠款#2013-065185）和科学，信息通信 技 术 和 未 来 规 划 部 （ 赠 款 #2013 R1 A6 A3A04058094））。引用[1] 放大图片作者：Bae S，Balakrishnan R，Singh K. ILoveSketch：尽可能自然的草图系统，用于创建3D曲线模型。在：第21届年度ACM用户界面软件和技术研讨会论文集; 2008年10月19日至22日;第21页。151-160。[2] Grimm C，Joshi P Just DrawIt：一个3D草图系统。In：Proceedingsof International Symposium on Sketch-Based Interfaces and Modeling;Jun4121-130[3] Schmidt R，Khan A，Singh K，Kurtenbach G. 3D支架的分析图。In：Proceedings of ACM SIGGRAPH Asia 2009; Dec 16-19 ，2009;Yokohama，Japan; Article 149.[4] 吴晓波，李晓波，李晓波.泰迪：一个三维自由设计的草图界面。在：SIGGRAPH的会议记录。Aug 8-13，1999; Los Angeles，CA; p.409-416[5] [10]杨文，杨文，杨文.纤维网：用3d曲线设计自由曲面。ACMTransactions on Graphics2007; 26（3）.（第四十一条）。[6] Rivers A，Durand F，Igarashi T. 3D建模与剪影。ACMTransactionson Graphics 2010; 29（4）1-8.[7] 放大图片作者：J.使用细分曲面放样曲线网络 。在：2004 年Eurographics/ACM SIGGRAPH几何处理研讨会论文集。 Jul 8-10，2004; Nice，France; p. 103-114[8] 放大图片作者：Abbasinejad F，Joshi P.来自无组织空间曲线的曲面片。在：第二十八届年度研讨会的计算几何会议记录。 君17-20,二〇一二年; 查珀尔希尔， NC; p. 417-418[9] 张文辉，张文辉，张文辉.设计驱动的封闭3D曲线的四边形化。ACM Transactions on Graphics（TOG）号316; Nov 28-Dec 1，2012;文章编号178.[10] [10]杨文，李文，李文.用于3D草绘的曲面片。在：基于草图的界面和建模国际研讨会论文集。Jul 19-20，2013; Anaheim，CA; p. 53比60[11] MamassianP，Landy MS. 观察者对线条图3D解释的偏差。视觉研究1998; 38（18）2817-32.[12] Rose K，Sheffer A，Wither J，Cani MP，Thibert B任意草图边界的可展曲面。第五届欧洲图形学研讨会几何处理论文集. Jul 4-6，2007;Barcelona，Spain;p. 16 3 -172。[13] 杨伟杰，张晓刚，张晓刚. CrossShade：使用横截面曲线为概念草图着色。ACM Transactions on Graphics2012; 31（4）.（文章编号）45）。[14] Zhuang Y，Zou M，Carr N，Ju T.一个通用的和有效的方法来寻找循环在3D曲线网络。ACM Transactions on Graphics2013; 32（6）.（文章编号）180）。[15] 王伟，朱特勒B ，郑东，刘勇. 旋转最小标架的计算。ACMTransactions on Graphics2008;27（1）. （文章编号）2）的情况。[16] Barquet G，Sharir M. 填充多面体边界的空隙。计算机辅助几何设计1995; 12（2）207-29.[17] 张文，张文.一种生成光顺曲线和曲面的离散弹簧模型. 第七届太平洋计算机图形与应用会议论文集。Oct 5-7，1999; Seoul，Korea; p.270比279