四维网格模型：连续刚体运动与3D物体的时空变化

计算设计与工程杂志，卷。号12（2014）96~102www.jcde.org四维网格模型从一个连续刚体运动Ikuru Otomo*，Masahiko Onosato和Fumiki Tanaka北海道大学研究生院情报科学技术学研究科，日本北海道札幌市北区西9，北14（2013年9月12日接收;2013年10月26日修订;2013年11月1日接受摘要在设计和制造领域中，存在管理三维（3D）对象的动态状态的许多问题为了解决这些问题，人们提出了四维网格模型及其建模系统4D网格模型是由四面体单元包围的4D物体模型，可以连续地表示3D物体的时空变化4D网格模型有助于将3D模型的动态问题作为几何问题来解决。然而，基于时间序列三维体素数据的方法的4D网格模型的构建受到限制这种方法占用内存，需要大量的计算时间。在本研究中，我们提出了一种新的方法来建立4D网格模型，该模型是由具有连续刚体运动的3D网格模型衍生而来的该方法是通过对三维网格模型进行四维扫掠和四面体化来实现的这里，刚体运动是螺旋运动，其是平移和旋转运动的组合关键词：四维网格模型;三维网格模型;第四维;刚体运动1. 介绍在设计和制造领域中，存在表示三维（3D）对象的时间变化的各种应用。它们是通过准备3D对象的时间序列数据，对初始状态进行移动操作然而，这些方法不足以连续且高精度地表示3D对象的形状、位置和取向的时空变化因此，已经提出了四维（4D）四维模型使三维物体的动态状态能够表示为时空扩展的高阶空间中的静态几何实体，如图1（d）所示例如，它有助于解决包括变形和运动的3D对象之间的碰撞避免问题另一个例子是使用4D网格模型表示五轴加工中工件变换的连续过程[6]。然而，4D网格模型的构建是用基于时间序列3D体素数据的方法来实现的，该方法占用内存并且需要较长的计算时间。*通讯作者。联系电话：+81-11-706-6438，传真：+81-11-706-6438电子邮件地址：otomo@dse.ssi.ist.hokudai.ac.jp© 2014 CAD/CAM工程师协会Techno-Press doi：10.7315/JCDE. 2014. 010本研究的目的是提出另一种方法来构建一个4D网格模型，使用一个3D网格模型与刚体运动。与现有方法相比，该方法能够通过减少顶点、四面体的数量和创建时间来本文首先介绍了4D网格模型及其建模系统的相关工作和概述。然后，详细说明了所提出的构建4D网格模型的方法。最后，与本文提出了一种基于时间序列体素数据的方法2. 相关研究和我们以前的工作通常，通过准备3D对象的时间序列数据来实现(a)（b）（c）（d）图1.表示3D对象的时间变化的几种方法（空间被减少到1D）：（a）时间序列数据，（b）时间变化的初始状态和操作，（c）插值，(d)4D模型。I. Otomo等人/Journal of Computational Design and Engineering，Vol.号12（2014）96~10297对初始状态进行移动操作，或者通过在不同状态之间进行插值准备3D对象的时间序列数据的示例3D视频是一种使用多个摄像机从多个视角记录实时变化的3D对象的媒体。利用体求交法重建物体通过对初始状态进行运动操作，实现了多种物理仿真和机床状态在每个单位时间内按顺序更新。在物理模拟中，3D对象的行为由作为时间变化因素的给定最近，物理模拟可以很容易地实现到计算机中使用物理引擎，如PhysX [13]和Havok [4]。与机床模拟一样，机床的运动由操作命令（如G代码[5]）驱动在不同状态之间插值的一个例子是3D多边形模型的变形[7]。变形技术是将源对象通过中间对象逐渐变形该方法通过建立源对象和目标对象网格之间的对应关系，计算源对象和目标对象之间的插值点来实现。如上所述，当前表示3D对象的时间变化的方法是通过准备一组静态来实现它们只具有沿时间轴的离散信息，不能高精度地描述时间的连续变化。此外，由于沿时间轴的信息是离散的，所以在若干对象之间的因此，我们提出了4D网格建模及其建模系统。在我们以前的工作[6，11，12]中，从时间序列3D体素数据构建4D网格模型体素是一种简单的表示三维物体形状的方法然而，处理高分辨率体素模型消耗大量的内存。3. 四维几何建模综述3.1 四维网格模型在这项研究中，第四维（4D）是一个四维欧几里得空间，包括三维空间和一维时间。图2显示了4维拓扑的四个拓扑元素：顶点，边，面和细胞。细胞是4D空间中的3D子空间，最简单的细胞是四面体。五角体是由五个四面体单元包围的4D单纯形。此外，4D立方体被称为超立方体，由16个顶点，32条边，24个面和8个单元组成4D网格模型被定义为由四面体单元限定的4D对象如图3所示，通过提取4D网格模型的横截面来获得3D模型。图2. 4D拓扑的四个元素和基本4D形状。图3.4D网格模型表示。3.2 4D网格建模系统图4描述了当前4D网格建模系统的流程需要时间序列3D体素数据来构建4D网格模型（图4A），并且为了从3D体素模型编织到4D网格模型，使用4D4D MarchingCubes算法是Marching Cubes算法[8]到4D的扩展，并且它基于更高维的等值面算法[3]。有各种应用程序来管理4D网格模型（D、E、F和G）。可以将4D网格模型投影到3D中，并将其可视化为3D包络模型（D）。3D包络模型通过将球旋转算法[2]应用于投影到3D空间的4D网格模型的顶点来构造此外，通过超平面切割从4D网格模型中提取横截面也是可能的（E）。通过将Marching Tetrahedra算法[10]应用于4D网格模型的每个四面体单元来实现利用4D物体间的碰撞检测方法（F），还提出了一种通过形状变形来避免运动物体间碰撞的碰撞解决方法（G）。4D碰撞检测方法是在3D中使用AABB树的碰撞检测方法的扩展[17]。如上所述，4D网格模型的构造98I. Otomo等人/Journal of Computational Design and Engineering，Vol.号12（2014）96~102图4. 4D网格建模系统的流程。目前是用基于时间序列三维体素数据的方法来实现的。我们提出了另一种方法，用于从具有刚体运动的3D网格模型构造4. 由刚体运动4.1 三维网格模型扫掠形状的四面体化在这项研究中，从一个三维网格模型和平移和旋转运动的参数，扫描形状的三维网格模型沿时空轴上获得。这种获得的4D扫描形状被四面体化以将其表示为4D网格模型。在这里，我们不考虑通过时间向后移动换句话说，平移运动矢量中的每个时间轴元素必须为正。所提出的方法主要包括以下四个步骤：步骤1. 在初始状态下对三维网格模型内部进行四面体化;步骤2.对三维网格模型依次进行运动，并对4D扫掠形状进行四面体化;步骤3. 在最终状态下对三维网格模型内部进行四面体化;步骤4.通过合并步骤1、步骤2和步骤3中生成的四面体构建4D网格模型步骤1和步骤3是表示也使用一组四面体的4D网格模型的垂直于t轴的两端的必要过程因此，需要对3D网格模型的内部进行四面体化在这方面，有必要添加新的顶点，因为已知一些多面体根本没有四面体化[1，14]。此外，不应在边界形状上添加额外的顶点，并且还应保留边界形状故受约束者图5.扫描形状的三角形网格沿时空轴。图6.三棱柱的四面体化使用Delaunay四面体化方法[15]它将边界形状视为约束条件并执行四面体化。在执行3D网格模型的四面体化时，必须确认在3D网格模型中没有网格的缺失或干扰否则，I. Otomo等人/Journal of Computational Design and Engineering，Vol.号12（2014）96~10299我3D网格模型的内部/外部判定可能失败，并且四面体化可能不能正确完成。在我们的软件程序中，3D网格模型的四面体化方法由TetGen [16]实现t0和t = t0 + t t）（图7）。因此，旋转角必须以这样的方式划分，使得t = t0 + t/2处的失真变得小于给定阈值。如图8所示，在3D空间中，考虑四-关于步骤2，三角形网格由四个顶点Pi=[xP，y，zP]T（i= 1，2，我Pii沿着时空轴是一个三棱柱（图5）。为了将每个三棱柱四面体化，添加了四个新顶点：一个顶点位于三棱柱的质心，三个顶点在每个质心的正方形面（图6）。3，4），其体积为VP，四面体绕通过任意点的任意轴旋转θ。我们假设PY是旋转后的四个点，Pi和PY之间的中心是Q。此外，我我由三角形面和三棱柱的形心生成两个四面体，由每个正方形面生成四个四面体，其中最后，一个三棱柱被分成14个四面体。在本研究中，由于运动前后的顶点之间的对应关系必须是明显的，所以我们只覆盖刚体运动。因此，今后应在变形方面开展更多的工作4.2 以体积变化为指标在将所提出的方法应用于旋转运动时，由顶点Qi组成的四面体被定义为VQ。如果将VQ/VP定义为体积比RV，则为定义为Eq.（1），其曲线图如图9所示1+cosθRV=2（1）以来|cos θ| 0 ≤ R V≤ 1成立。由于3D网格模型的内部可以由一组四面体来表示，因此Eq.（1）也适用于3D网格模型如果用户给出了可接受的体积变化下限RVmin（其中0≤RVmin 1），则旋转θ步长（其中0°θ步长 ≤ 180°）的步长由等式2给出。（二）、通过连接旋转之前和之后的对应顶点（在时间t =1时）来产生“扭曲的”三棱柱。θ阶跃= cos-1（ 2RV最小值-1）（2）图7.扭曲的三棱柱。图8.旋转引起的四面体体积变化图10显示了RVmin和θstep之间的关系。例如，如果RVmin= 0.998，则θstep= 5.1。通过将旋转角θ除以θ步长，3D网格模型符合可接受范围。5. 构建4D网格模型5.1 与基于时间序列3D体素数据的方法的比较通过准备时间序列三维体素数据和三维网格模型，构建了两个4D网格模型时间序列3D体素数据的空间分区的数目是128×128×128，并且时间步的数目是64。在时间序列3D体素数据中，长度为20体素的立方体对于每个时间步长向+z在3D网格模型中，准备一个长度为20的立方体立方体由14个顶点和24个三角形网格表示每次向z轴方向移动+1.0表1.构建的4D网格模型的数据。一种基于时序三维体素数据的方法基于三维网格模型的方法数量的顶点197,8284,750四面体数目1,185,28021,552施工时间[秒]4.630.06* 操 作 系 统 ： Windows XP ， CPU ： AMD Opteron2224SE 3.2GHz，RAM：64GB100I. Otomo等人/Journal of Computational Design and Engineering，Vol.号12（2014）96~102图9.体积比RV与旋转角θ之间的关系。图10.可接受下限之间的关系体积变化的极限RVmin和旋转θ步的步长。在虚拟场中，t= 0 ~ 64期间，间隔1.0在图11中，示出了从垂直于t轴的切片超平面提取的3D网格模型它表示3D模型在指定时间的状态。由于基于时间序列3D体素数据的方法是使用4D MarchingCubes算法实现的，因此它不能表示如图11（a）所示的尖锐边缘和拐角。另一方面，如图11（b）所示，基于3D网格模型的方法不会出现表1显示了顶点数、四面体数和构建每个4D网格模型的处理时间结果表明，该方法可以更快地构造出顶点数和四面体数都较少的4D网格模型。5.2 从具有旋转在准备松鼠的3D网格模型（图12）作为输入时，构建4D网格模型。给定的运动是一个螺旋运动，在虚拟场中，在t= 0 ~ 100的时间内，绕x轴旋转360 °，同时向x轴方向平移+20.0 °的可接受的体积变化RVmin的下限为0.9976，结果，运动被分成65步（5.538每个旋转角度）。4D网格模型构建的处理时间如图13所示。4D网格模型具有3，909，554个顶点和18，266，982个四面体。在图14和图15中，示出了根据本发明的实施例的3D网格模型。（一）（b）第（1）款图11.垂直于t轴（t= 32）的4D网格模型的横截面提取结果：（a）基于时间序列3D体素数据的方法，（b）基于3D网格模型的方法。示出了从垂直于x、y、z或t轴的切片超平面提取的图像从这些图中，我们可以验证具有运动的3D对象被表示为4D模型。6. 结论在这项研究中，提出了一种新的方法，直接从一个三维网格模型与刚体运动的4D网格模型。本报告的主要贡献如下： 直接构造4D网格模型的方法详细解释了从具有刚体运动的3D网格模型中提取的方法。提出了一种从三维网格模型中反映刚体运动和时间变化的三角形网格生成四维扫掠形状的此时，三角形网格的扫掠形状被分成14个四面体。此外，为了使所构建的4D网格模型具有封闭的形状，我们提出了一种将3D网格模型内部四面体化并将生成的四面体添加到4D网格模型中的方法。I. Otomo等人/Journal of Computational Design and Engineering，Vol.号12（2014）96~102101图12.松鼠的3D网格模型图13.处理时间。(a)（b）（c）图14.垂直于t轴的4D网格模型的横截面提取结果：（a）t= 1.0，（b）t= 20.0，（c）t= 100.0。(a)（b）（c）图15.垂直于x、y或z轴的4D网格模型的横截面提取结果：（a）x= 3.0，（b）y= 3.3，（c）z= 3.5。102I. Otomo等人/Journal of Computational Design and Engineering，Vol.号12（2014）96~102 通过分析旋转前后三维网格模型顶点连接时的体积变化，提出了一种确定旋转角度步长的方法，使三维网格模型的体积变化在可接受的范围内。 结果表明，所提出的方法，使显着-与基于时间序列三维体素数据的方法相比，所构建的4D网格模型的计算时间和数据量都有很大的减少这一事实是通过一个例子来说明的。本研究的剩余问题是评估所建立的4D网格模型的四面体网格的质量，并将所提出的方法应用于变形。还考虑了使用GPU加速所提出的方法致谢部分工作得到了JSPS KAKENHI资助号24656106的支持引用[1]巴吉米尔湾关于不可分解的多面体。美国数学月刊1948;55（7）：411-413。[2][14] 杨 晓 ， 李 晓 . 曲 面 重 建 的 球 旋 转 算 法 。 IEEETransactions on Visualization and Computer Graphics. 1999;5（4）：349-359.[3]吴伟，王伟，王伟.更高维度的等值面。在：第11届IEEE可视化年会论文集; 2000年10月8-13日;犹他州盐湖城;第267-273页。[4]Havok [Internet]. 都 柏 林 （ 爱 尔 兰 ） ： TelekinesysResearch Ltd.; c1999-2013 [2013年11月25日引用]。可从以下网址获得：http://havok.com/[5]国际标准化组织ISO 6983-1：数控机床。程序格式和地址字的定义。第1部分：定位、直线运动和轮廓控制用数据格式。日内瓦（瑞士）：本组织; 1982年。[6][10]张文龙，张文龙，张文龙.用时空模型表示五轴加工中工件变换的连续过程。收录于：亚洲设计与数字工程会议论文集; 2012年12月6日至8日;日本二世古;附带：1个USB记忆棒。[7]Lee AWF，Dobkin D，Sweldens W，Schröder P.多分辨率网格变形。第26届计算机图形学和交互技术年会论文集; 1999年8月8日至13日;洛杉矶，加利福尼亚州; p. 343-350[8]Lorensen WE，Cline HE。Marching Cubes：一种高分辨率的3D表面构建算法。计算机图形学. 1987; 21（4）：163-169.[9]Moezzi S，Tai LC，Gerard P. 3D数字视频。IEEE Multimedia. 1997; 4（1）：18-26.[10] Müller H，Wehle M.使用自适应四面体化的隐式曲面可视化。In：Scientific Visualization Conference; 1997 Jun 9-13; Dagstuhl，Germany; p. 243-250[11] 王文，王文.用于时空对象表示的四维网格建模。In：Proceedings of Asian Conference on Design and DigitalEngineering; 2010 Aug 25-28; Jeju，Korea; p. 579-589.[12] 张文龙，李晓梅，李晓梅.从一系列三维体素模型编织出四维网 格模型。收 录于：Proceedings of 10 th AnnualInternational CAD Conference and Exhibition; 2013 Jun 17-20; Bergamo，Italy;附带：1个USB记忆棒。[13] PhysX [Internet]. Santa Clara（CA）：Nvidia Corporation;c2013 [cited 2013 Nov 25]. 可 从 以 下 网 址 获 得 ：https://developer.nvidia.com/technologies/physx[14] 申 哈 特 湖 Über die Zerlegung von Dreieckspolyedern inTetraeder [关于三角多面体到四面体的细分]。数学年鉴德语. 1928; 98（1）：309-312。[15] 小休丘克约束德洛内四面体化和可证明的良好边界恢复 。 In ： Proceedings of the 11th International MeshingRoundtable; 2002 Sep 15-18; Ithaca，NY; p. 193-204.[16] 是的TetGen：一个高质量的四面体网格生成器和一个3DDelaunay三角剖分器[互联网]。柏林（德国）：Weier-strass应用分析和随机研究所，数值数学和科学计算研究组; [引用于2013年11月25日]。可从以下网址获得：http://tetgen.org[17] 范登卑尔根湾使用AABB树的复杂可变形模型的高效碰撞检测。图形工具杂志。1997; 2（4）：1-13.