þþHOS T E D B Y可在www.sciencedirect.com网站上查阅计算设计与工程学报2（2015）55www.elsevier.com/locate/jcdeECE检测Masatomo Inui，Nobuyuki Umezun，Yuuki Kitamura日本茨城县日立市中成泽4-12-1茨城大学智能系统工程系接收日期：2014年9月27日;接收日期：2014年10月21日;接受日期：2014年10月23日2014年12月6日在线发布摘要为了满足欧洲经济委员会（ECE）的安全法规，汽车零件的表面区域必须具有足够的圆度，如果它们可能接触半径为50.0 mm（外部零件）或半径为82.5 mm（内部零件）的球体。在本文中，一种新的基于偏移的方法来自动检测可能的球接触形状的零件。给出一个精确逼近零件形状的多面体模型作为输入，并将模型的偏移形状作为所有表面三角形的扩展形状的布尔联合来获得。我们采用了三维模型的三重dexel表示，使稳定和精确的布尔联合计算。为了加速这些布尔运算中的深度元素运算，提出了一种新的并行处理方法，该方法采用伪列表结构和轴对齐包围盒然后，从偏移形状中提取零件表面的可能的球体接触形状，作为一组点或一组多边形。&2015 年 CAD/CAM 工 程 师 协 会 。 由 Elsevier 制 作 和 主 持 。 这 是 一 个 在 CC BY-NC-ND 许 可 证 下 的 开 放 获 取 文 章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。关键词：ECE安全检测;汽车零部件设计;碰撞检测;偏移; GPU1. 介绍安全性是汽车零部件设计中的一个重要问题。欧洲经济委员会（ECE）对零件形状定义了几项安全法规，以便在发生车祸时不会伤害行人，驾驶员或乘客[1]。例如，ECE-17定义了汽车座椅结构部件的形状条件，而ECE-21和ECE-25分别规定了汽车内部和头枕角落的圆度条件。ECE-26与ECE-21相关，控制外部零件的表面圆度。其他国家也有类似的规定，如日本、美国和中国[2]。图1示出了ECE-21和ECE-25的概念。可与半径为82.5mm的假想球体接触的车内部件和头枕的角必须具有大于R3.2的圆度。这个半径相当于婴儿头部的平均ECE-17对座椅施加了类似的形状约束。因此，座椅设计者经常在座椅下放置粗电线n通讯作者。联系电话：传真：81 294 38 526281294385229电子邮件地址：umezu@mx.ibaraki.ac.jp（N. Umezu）。同行评审由CAD/CAM工程师协会负责底座（见图2），使头部不能直接接触尖角。ECE-26规定，半径为50.0 mm的球体可能接触的任何外表面部分必须具有大于R2.5的圆度。由于外部和内部部件强烈影响汽车的外观和舒适性，因此它们通常最初是根据其功能和美学进行设计的。目前，ECE关于零件形状的法规仅在最终设计阶段由专家进行检查检测中最重要的任务是检测半径为50.0 mm（对于外部零件）或半径为82.5 mm（对于内部零件）的球体可以接触的表面区域。为了手动检查每个零件的接触情况，需要制作许多这项工作是乏味的，耗时的，并且容易出现人为错误。因此，非常需要一种允许设计者自己检查规则的快速自动检查方法各种商业系统使得能够可视化球体接触部件形状（例如，CAVA[3]）。然而，这种系统的可视化质量不足以精确理解球体如何接触零件。根据我们的研究，一些日本公司已经开发了自动化检查任务的内部系统http://dx.doi.org/10.1016/j.jcde.2014.11.0062288-4300/2015 CAD/CAM工程师协会。&由Elsevier制作和主持。这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。56M. Inui等人/Journal of Computational Design and Engineering 2（2015）55Fig. 1. 安全法规ECE-21和ECE-25的几何描述。图二. 安全法规ECE-17的几何描述。例如，在虚拟铣削方法中，在汽车零件上执行固定轴铣削模拟，使用特定半径的球端刀具来区分球体接触形状。假设接触球沿着刀具轴（在三轴铣削的情况下为z为了提高检测质量，必须沿多个轴进行铣削仿真，这导致相当长的计算时间。为辅助零件设计，提出了一种自动检测汽车零件球面接触形状的新方法。输入数据由精确近似零件形状的多面体模型组成。考虑零件的曲面偏移球体的半径。当球体的中心点位于离面上时，球体可以接触零件表面。 图 3，S表示零件表面，S0表示其偏移。所提出的方法计算的偏移形状的部分作为布尔联盟的扩展形状的所有表面三角形的模型。采用三深度表示的3D模型[4-使用两种方法提取和可视化可能接触球体的部分上的那些点。第一个采样偏移表面上的许多点（例如，图3中的点p0）并计算它们的法向量。零件上的球体接触点是通过将采样点沿偏移曲面的法线方向向零件曲面投影回来获得的。图3中的点p对应于球体与中心点p0的接触点。然后可以通过对这些接触点着色来可视化接触区域。图3.第三章。偏置曲面上的点与球体接触点之间的关系第二种方法将S 0向内偏移（收缩）回初始曲面以导出曲面S“。这是通过在零件曲面上滑动球体而形成的曲面。零件表面S和收缩表面S“之间的相交对应于零件的球体接触形状。我们的方法推导出的相交表面作为一组小多边形。本文的组织结构如下。在下一节中，简要回顾了ECE法规和补偿计算的一些相关研究我们的球接触形状检测算法的新贡献在第节中解释3 .第三章。第4节和第5节详细介绍了基于dexel的并行偏移算法，包括dexel数据更新机制的伪列表结构和AABB线程管理方法。在第6节中，我们描述了基于偏移曲面的球接触形状的可视化方法。在第7中讨论了一些复杂的汽车零件CAD模型的实验提取和可视化结果，我们在第8中总结了我们的结论。2. 相关研究2.1. ECE检查虽然ECE检测是汽车制造商的一个重要课题，但很少研究自动化检测任务的技术。许多制造商仍然使用人工检查方法。丰田汽车公司在2005年提交了一些关于ECE-17，-21和-25自动检测的专利[8]。丰田的方法使用CAD模型的偏移表面来提取可能的球体接触表面。复杂3D形状的偏移计算通常是困难和不稳定的，丰田的专利没有描述他们计算方法的技术细节一些汽车公司使用CAVA软件[3]，其技术细节尚未公布。Yamazaki等人提出了一种ECE法规检查系统，该系统基于检测CAD模型与放置在模型表面上的半径为82.5 mm的球体之间的相交[9]。为了提高计算速度，提出了一种并行相交检测算法，并结合几何数据分级管理。然而，该方法不能应用于具有尖锐边缘的部件，M. Inui等人/Journal of Computational Design and Engineering 2（2015）5557角，因为没有给出在这种表面上放置球体的适当方法。当前作者提出了一种改进的虚拟铣削方法，用于快速检测球体接触形状[10]，并使用图形处理单元（GPU）的深度缓冲机制加速反向偏移方法，用于铣削模拟[11]。由于该系统是基于三轴铣削仿真技术，没有克服虚拟铣削依赖于球体逼近方向的关键局限性。2.2. 偏移计算我们的ECE检测方法使用零件模型的偏移曲面。偏移是几何造型中最基本的操作之一。Rossignac和Requicha[12]在早期的工作中全面研究了抵消的数学问题。曲线和曲面的偏移操作是众所周知的[13然而，当我们考虑3D模型时，偏移的复杂性显著增加，因为偏移必须处理模型中的各个表面以及通过修剪和重新连接偏移表面到闭合模型中的拓扑重建。用于偏移3D模型的早期技术[12，16，17]通常在计算上是昂贵的，并且模型重建可能是不稳定的。为了克服这些困难，基于3D模型的离散表示的新偏移计算方法已经变得流行。已知的表示方案利用点、体素、深度元素[18]、射线[19]和分层深度图像（LDI）[20]，以及各种改进，例如，已经报道了三重dexels[4由于离散的三维模型没有表面元素，拓扑重建步骤，这是最关键的过程，在传统的偏移，是不必要的。偏移后，通过对离散模型应用一些表面提取技术（如marching cubes[21]或双轮廓[22]），导出偏移形状的多面体模型Chen等人提出了一种基于点的偏移方法[23，24]，其中点在输入多面体模型的表面上密集采样偏移曲面上的候选点是通过简单地移动多边形上的点或将顶点和边上的点替换为球体和圆柱体上的点来生成的。在移除位于偏移模型内部的点Liu和Wang提出了另一种基于点集的偏移方法[25]。他们的方法假设物体表面上的每个采样点都有一个唯一的法向量。在具有尖锐边缘和顶点的汽车零件中，很难满足这个条件，因为这些元素上的点有多个法向量。偏移3D对象可以被识别为对象与偏移半径的球体之间的Minkowski和。Lien提出了一种基于点的Minkowski求和运算[26]，将两个物体的表面转换为两组点，然后求和。位于Minkowski sum对象内部的点通过应用一系列“过滤器”来确定偏移表面。基于点的偏移中最昂贵的过程是这个过滤步骤，并且对于具有大偏移半径的情况，例如典型的ECE检查，成本可能变得巨大。考虑一个盒子状空间中的3D对象。距离场是空间网格结构，其中从点到物体最近表面的距离在每个网格点处许多研究人员提出了基于距离场的偏移方法[27对于某个偏移半径r，模型的偏移曲面穿过连接距离大于r的网格点与距离小于r的另一点的边。在检测到这样的边缘之后，行进立方体方法（或类似方法）可以确定多边形偏移表面。在[31]中使用了类似的想法，其中开发了几种滤波方法来降低距离场的计算成本。Li和McMains讨论了使用剔除技术的体素化Minkowski和 计 算 [32 ， 33] 。 他 们 的 方 法 首 先 生 成 两 个 对 象 的Minkowski和形状的可能表面元素然后根据表面元素选择对应于Minkowski和形状的体素。不幸的是，使用这种基于空间网格的偏移方法进行ECE检查将消耗大量的存储器来记录距离场或体素模型。Wang和Manocha提出的偏移方法使用LDI来记录偏移计算的对象形状和时间结果[34，35]。Zhao等人开发了一种紧凑型LDI（CLDI）方法，该方法提供了改进的数据存储技术，以减少所需的内存量[36]。 这些工作还利用GPU的并行处理能力来加速计算。由于三深度表示在几何上等同于LDI和CLDI，因此[34 - 36]中提出的偏移方法与我们的工作相似。主要区别将在下一节中解释。3. 拟议方法我们的碰撞检测方法需要一个精确的镶嵌的汽车零件的CAD模型的输入大多数商业CAD系统提供将模型数据输出为一组三角形多边形的功能，例如STL格式。模型的偏移形状作为模型的所有表面三角形的扩展形状的布尔并集而与基于点的偏移相比，该技术不需要任何滤波操作。布尔运算使用3D模型的三重深度表示与基于空间网格的方法相比，这种表示方法需要更少的内存来生成相同精度的偏移形状。我 们 的 偏 移 方 法 与 Wang 和 Manocha[ 34 ， 35] 以 及Zhao[36]提出的形状表示技术相似，并且还使用GPU的并行处理能力来加速计算。与这些先前的研究相比，本文提出的方法具有以下新特征：我们的方法将偏移形状计算为零件的所有三角形的扩展形状因为●58M. Inui等人/Journal of Computational Design and Engineering 2（2015）55¼~~三角形的边和顶点构成合成的偏移表面，这是检测碰撞的鲁棒方法。[34，35]中给出的算法使用放置在零件表面上分布的点处的球体来计算偏移形状。这种方法容易忽略尖锐边缘和顶点周围的碰撞，这是ECE检查中最关键的条件。我们引入了一个新的伪列表方法来支持并行构造的深度元素模型。这使得处理比以前的方法更有效[34，36]，后者使用具有多个冗余操作的数据存储机制。我们的伪列表技术还使深度元素模型能够在模型更新过程中部分更新，这在以前的方法中是一个有问题的操作。除了传统的基于点的可视化技术[9，10]之外，所提出的方法将球体接触形状计算为一组小多边形。这不仅对于可视化目的是期望的，而且对于以标准多边形数据格式将碰撞检测结果传输到其他CAD系统也是期望的。4. 预处理操作为了准备适合所提出的方法的数据，输入模型的表面多边形根据它们的接近程度被分成小组。这种分类是根据AABB的层次结构进行的[37]。考虑形成模型表面的n个三角形多边形。通过测量多边形在x、y和z方向上的坐标范围来定义紧密包含多边形的AABB。定义一个根AABB，它包含给定模型的所有三角形多边形。我们将AABB中所有多边形的中心点投影到与其最长轴平行的直线上，并根据投影点在直线上的顺序对多边形进行排序。然后，两个AABB分别由第一个n/2个排序的多边形和剩余的n/2个多边形形成他们被认为是原AABB的两个孩子。多边形的排序和分组操作以及迭代定义子AABB的过程，得到二叉AABB树。当树的所有叶AABB仅包含nmax个或更少的多边形时，树构造过程终止，其中nmax是每个叶AABB所允许的多边形的最大数量。在我们的实现中，我们根据数值实验设置nmax8。每个叶AABB保留其中的多边形的数量和多边形的几何数据（顶点的3D模型的三深度表示用于偏移计算并表示偏移形状。在最初的深度元素建模[18]中，对象形状由一系列z轴对齐的垂直段表示，这些垂直段是为x-y在深度元素模型中，近水平表面由深度元素段的端点精确表示，而垂直或近垂直表面具有由x-y三深度模型被提出来克服这种表示精度的不均匀性。在三重深度元素表示中，对象形状不仅由z轴对齐的深度元素模型定义，而且还由基于y-z平面中的网格的x轴对齐的深度元素模型和基于z-x平面中的网格的y在这种表示中，垂直或接近垂直的表面的几何信息由水平x轴或y轴对齐的深度元素的端点精确表示[45. 并行偏移计算为了实现并行偏移软件，我们使用计算统一设备架构（CUDA）[38]。目前的GPU被设计为在芯片上具有数千个小型流处理器（SP）。通过使用CUDA，程序员可以将GPU用作通用并行处理器，其中每个SP执行计算单元（或线程）。通过使用GPU获得的加速主要是由于功能的迭代执行被其等效线程的并行执行所取代。在CUDA下，程序- mers可以指定执行多达65535 65535 512个并发线程。为了正确管理如此大量的线程，CUDA提供了网格和块见图4。 深度模型和三重深度模型的定义。●●M. Inui等人/Journal of Computational Design and Engineering 2（2015）5559结构.每个块都是一个1D、2D或3D线程阵列，每个网格都是一个1D或2D块阵列在PC中，CPU和GPU是独立的单元，拥有自己的内存系统。用于GPU处理的数据通常在被传输到图形存储器之前在主CPU存储器中准备。在我们的并行偏移计算中，基本数据是每个叶子AABB内三角形多边形的顶点坐标。在执行用于偏移计算的线程之前，这些被传输到GPU。在线程完成其执行之后，表示零件的偏移形状的三深度模型被记录在图形存储器中。然后，模型数据从图形存储器传输到主CPU存储器，并在可视化过程中使用5.1. 单个AABB在下面的部分中，我们解释了z轴对齐深度元素的偏移计算。在实际处理中，对于x轴和y轴对齐的深度元素重复相同的操作。在处理开始之前，在x-y平面中的规则正方形网格上准备零z轴对准的深度元素模型（偏移深度元素模型，ODM）定义网格，使其保持偏移模型到x-y网格的分辨率根据偏移计算的精度要求和可用的存储器大小来确定。ODM在以下计算中更新，并最终形成深度元素表示中零件的偏移形状模型。AABB树的每个叶子AABB是偏移计算的基本处理单元。单个叶子AABB在其邻域中最多保持nmax个多边形。它们以半径r扩展（其中r对于外部部件为50.0 mm，对于内部部件为82.5 mm）。多边形的展开形状等效于放置在多边形上的球体、圆柱体和厚板的布尔并集形状，如下所示：半径为r的球体放置在多边形的所有顶点上。半径为r的圆柱体沿着多边形的每条边e放置，圆柱体的中心轴与e重合。将每个面的面积和厚度为2r的板放置在每个多边形面f上，板的中心平面与f重合。根据多边形的扩展，保持多边形的AABB也被扩大r，以适当地将扩展的多边形包围在内。这个操作是通过简单地移动六个矩形的AABB在其向外的方向，如图所示。五、放大的AABB到x-y平面的投影限制了对于投影中的每个网格点，我们计算从该点开始的垂直线与展开的图五、用于保存扩展多边形的AABB的包围图六、两个放大的AABB与扩展多边形的投影多边形，并生成扩展的多边形的时间深度元素模型（见图7（a））。然后计算时间深度元素模型和ODM的深度元素布尔联合，结果给出新的ODM（图7（b））。在该过程中，针对投影内的所有网格点计算扩展三角形中的一系列深度元素和ODM中同一网格点上的另一系列深度元素的布尔并集。网格点上深度元素的布尔联合计算独立于其他网格点上的深度元素因此，深度方向布尔联合计算可以被并行化。一个CUDA线程被分配给每个网格点。该线程计算网格点上然后执行上述深度布尔联合计算。通过调用扩展AABB投影中所有网格点的线程，我们获得了叶AABB中三角形的偏移深度模型的对所有叶AABB执行此操作，零件模型的偏移计算完成。在当前实现中，以下值存储在ODM的每个深度元素中：top_v，bottom_v：深度元素的顶端和底端的z对于x轴或y轴对齐的深度元素，则存储端点的x值或ytop_ID、bottom_ID：构成深度元素的顶端和底端的展开三角形的组成元素（球体、圆柱体或平板）的标识号。该信息在从扩展三角形到深度元素段的转换过程中获得。然后，将标识号传输到ODM的深度元素，下面的深度布尔联合操作。●●●60M. Inui等人/Journal of Computational Design and Engineering 2（2015）55-图7.第一次会议。时间深度元素模型的计算过程（a）以及时间深度元素模型和ODM的布尔联合计算（b）。5.2. 并联式深度存储机构由于CUDA线程可以同时执行多个网格点的深度元素布尔联合操作，因此我们需要一种适合于深度元素模型并行更新的数据存储机制。先前的工作[34，36]已经使用计数函数和独占扫描函数[38]实现了这样的机制。5.2.1. 计数扫描法考虑将生成的深度元素模型存储在全局数组dexel[ ]中。计数功能和基于扫描的方法以两遍的方式存储数据。在第一遍中，对每个网格点计算布尔联合运算产生的模型中深度元素的数量。计数结果存储在全局数组count[ ]中，其中count[i]记录网格点gpi的深度元素的数量。一个新的数组start[ ]通过对count[ ]应用独占扫描操作来准备和填充。在该操作中，从count[0]到count[i然后重复两个深度元素模型的布尔联合计算，以将结果深度元素存储在深度元素[ ]中，其中将gpi的结果深度元素从深度元素[start[i]]存储到深度元素[start[i]count[i] 1]。上述机制有两个缺点。首先，在两次执行相同的深度方面的布尔操作中存在一定程度的冗余。其次，很难处理dexel模型的部分修改。由于ODM的深度元素数据被打包在1D数组dexel[ ]中，因此添加新的深度元素以修改部分深度元素模型需要更新存储在dexel[ ]中的所有数据。5.2.2. 伪列表法为了克服这些问题，我们已经开发了一种新的伪列表数据存储机制的并行更新的dexel模型。链表结构适合于记录每个网格点的一系列深度元素。如图4（a）所示，指向序列中第一个dexel元素的指针被分配给每个网格点。每个dexel元素都有一个指向系列中下一个元素的指针;最后一个dexel有一个空指针。虽然在CUDA中有几种实现列表结构的方法，但没有一种方法被公布或充分研究。由于CUDA不允许在处理期间动态分配设备内存，因此大多数已知方法都预先分配足够的内存作为数组。它们不是使用指针，而是使用每个数组元素的索引号来引用列表中的特定元素。本文提出的伪列表结构遵循这一策略，在并行深度元素模型构造中实现了深度元素的列表式处理。在全局数组dexel[ ]中生成并准备足够数量的空数据dexel元素。指向dexel[ ]中第一个可用元素的全局索引计数器idx也被准备并初始化为0。伪列表结构使用以下1D整数数组：start[i]：start[i]对应于从网格点gpi到关联深度元素列表中的第一个元素的指针。start[ ]的大小与xend[i]：end[i]表示从gpi到dexel列表中最后一个元素的另一个指针。这个数组与start[]拥有相同数量的元素。next[ ]：next[ ]的每个元素表示指向同一列表中下一个dexel的指针。分配给next[ ]的内存必须足够允许在模型构建过程中生成的所有深度元素记录它们的下一个元素。在开始模型构造之前，start[]中的所有元素end[]和next[]初始化为考虑将新的深度元素添加到从网格点gpi开始的深度元素列表的末尾。从数组dexel[idx]中获得具有空数据的dexel然后通过原子增量函数更新索引号idx[39]。(In在并行处理环境中，保证全局值a的递增操作不保证按顺序改变其值M. Inui等人/Journal of Computational Design and Engineering 2（2015）5561图8.第八条。更新深度元素列表以插入三个新深度元素。因为多个线程可以同时更新a的值。通过使用原子增量函数，可以避免这种冲突，并且idx可以用作增量计数器。然后使用原子交换函数将end[i]的值替换为idx。这个函数返回end[i]的旧值。如果返回值old_idx为在这种情况下，start[i]的值也被更新为idx。否则，old_idx表示gp i的dexel列表中最后一个dexel元素的索引号。idx因此被设置为next [old_idx]，以记录dexel [old_idx]的下一个dexel元素是dexel [idx]。图8示出了start[i]、end[i]和next[]的更新过程，以将深度元素[1]、深度元素[5]和深度元素[9]插入到网格点gpi的空深度元素列表。采用伪列表允许简单地将新的深度元素插入到深度元素列表中。与基于计数和扫描的方法相比，我们的技术在单遍操作中实现了深度元素模型的并行因为修改网格点的深度元素列表不会影响其他网格点的深度元素列表，所以我们可以部分更新深度元素模型。也就是说，将深度元素插入伪列表的操作不必顺序执行，并且多个线程可以并行地执行对同一伪列表的插入操作。由于原子增量函数和原子交换函数自动控制实际插入的执行顺序，因此我们可以在施工过程然而，伪列表方法不容易允许从列表中消除深度元素。在我们当前的实现中，通过简单地将深度元素标记为无效来实现深度元素消除。随着dexel操作的继续，会生成更多无效的dexel，这些dexel最终可能会构成dexel[ ]中所有预定义的dexel元素。为了防止这个问题，我们的抵消程序准备了一种垃圾收集机制。在某些处理间隔，图形存储器中的深度元素模型数据被传送到主CPU存储器。对无效深度元素的指针引用由CPU中的主机程序适当地消除，并且仅具有有效深度元素的新深度元素模型被写回到图形存储器以用于在GPU上继续处理见图9。AABB在x-y5.3. 多个AABB为了进一步利用GPU的并行处理能力，在第10节中给出的用于单个叶AABB的偏移计算被简化。5.1扩展到多个AABB的并行偏移计算。在这种情况下，我们需要一种机制来避免深度布尔运算中的冲突。 图第9（a）段说明了这种情况。考虑同时调用AABB0和AABB1中多边形的偏移计算。因为AABB0和AABB1的扩展框在它们到x-y为了避免我们的平行偏移框架中的这种冲突，必须选择多个AABB，以便其扩展形状的投影不相交。扩展AABB的这种选择如下实现。我们将零件模型投影到x-y如果x坐标范围大于y坐标范围，则所有叶AABB根据其中心点的x坐标排序。否则，AABB按y坐标排序。在图9（a）中，白色小圆圈代表AABB的中心点。在下面的解释中，我们假设排序结果是按照x坐标进行的.全局变量Rmax被初始化为一个小值。然后以升序访问排序的叶AABB对于每个访问的AABB，检查扩展框[xmin，xmax]的x坐标范围。如果xmin大于Rmax，则62M. Inui等人/Journal of Computational Design and Engineering 2（2015）55选择该展开的叶AABB，并将Rmax的值更新为xmax。重复该选择过程，直到已经访问了所有排序的叶AABB，并且 已经 获 得 了一 组 在其 投 影 中没 有 相互 交 叉 的扩 展AABB。以类似的方式实现根据y并行偏移操作是用选定的AABB执行的。重复相同的AABB选择和偏移操作，直到所有AABB都用于偏移计算。考虑图9所示的叶AABB放置。AABB根据其中心点的x坐标进行排序和索引。在第一选择过程中，获得四个AABB ： AABB0 、 AABB2 、 AABB4 和 AABB7 （ 参 见 图 9（a））。然后重复相同的选择过程，得到AABB1、AABB3、AABB6和AABB8（参见图9（b））。在我们的实现中，使用上述算法选择多个AABB的偏移操作通常比使用单个AABB的偏移减少10 - 15%的计算时间所提出的方法选择的AABB的集合不是最优的。在第一选择过程中，AABB3（或AABB5）、AABB8和AABB9也可以被选择，因为它们彼此不相交或与AABB0、AABB2、AABB4和AABB7不相交（参见图9（a））。尽管我们测试了几种用于选择更多AABB而没有相互交叉的方法，但它们通常会增加选择的计算时间并降低偏移操作的整体性能6. 球体接触形状球体接触形状使用偏移零件模型的三重深度表示来可视化。开发了两种可视化，一种是用零件表面上的点显示球接触形状，另一种是将形状显示为一组小多边形。6.1. 点可视化在z轴对齐的深度元素模型中，可以使用深度元素的端点的z值及其在x-y平面中的对应网格点的（x，y可以以类似的方式获得覆盖x轴和y轴对齐的深度元素模型中的偏移表面的点。在这些点处，构成偏移形状的组件球体、圆柱体或厚片可以通过深度元素端点处记录的ID编号来区分。这些ID允许精确计算偏移曲面端点处的法向量。如果偏移上的深度元素端点p是中心在c处的球体的一部分，则从c到p的矢量对应于p处的法向矢量n（参见图10（a））。圆柱体和平板上的点的法向量可以用类似的方法计算（见图10（b）和（c））。p处的负法向量将点投影回零件表面为p见图10。 法向量计算方法。见图11。 Dexel的缩小形状。和82.5mm用于内部部件）。对于表示偏移形状的三深度模型中的所有深度端点重复该投影，并且最终获得球体接触形状作为覆盖零件表面的一组点6.2. 多边形可视化我们已经开发了第二种技术来可视化球体接触形状。在此方法中，偏移形状再次沿其负方向偏移，或此收缩曲面表示由球体滑过零件曲面所给出的曲面。因此，收缩表面和给定零件模型的原始表面的相交对应于零件上的球体接触形状。使用Wang和Manocha[34]提出的方法实现收缩操作。我们将收缩半径的球体放置在偏移模型中的所有深度端点处。从给定的偏移模型中减去这些球体的深度元素，得到一个新的收缩形状的深度元素模型（见图11中的S“）。上一节中描述的伪列表机制用于记录M. Inui等人/Journal of Computational Design and Engineering 2（2015）5563¼¼þþ每个网格点。在我们当前的实现中，收缩操作使用半径比原始偏移小0.1 mm的球体。这是正确处理具有开放曲面的模型所必需的。由于这样的模型没有厚度，偏移和收缩操作将产生空深度元素，并且球体接触形状的提取将是困难的。在收缩操作之后，剩余的三深度模型被转换为等效的多面体模型。在这种转换中可以使用行进立方体或双重轮廓算法（详见[36]）。在当前的实现中，小多边形被放置在收缩深度元素模型的顶部和底部，以给出一组包裹模型表面的小多边形。零件模型的原始曲面与收缩模型的曲面的交点通过选择收缩模型的曲面多边形来确定，收缩模型的曲面多边形到原始曲面的距离足够小（在当前实现中小于ε0.15 mm;该值必须大于d）。结果，球接触形状被获得为一组小多边形。7. 实验结果采用Visual C++、CUDA 6.0和OpenGL实现了球接触面形状可视化系统，并进行使用Intel Core i7处理器（3.4 GHz），12 GB内存和nVidiaGeForce GTX-650 Ti GPU。 表1列出了计算偏移模型所需的时间，triple-dexel表示。我们将该系统应用于六个多面体模型的汽车零部件。一个模型由汽车零部件制造商提供，另外五个模型是从CAD演示模型和汽车公司档案中选择的[40]。为了评价系统在相同条件下的性能，所有部件的偏移半径均设定为82.5 mm。表1还列出了表示零件形状的多边形的数量，以及x-y多个AABB的偏移操作的计算时间图图12示出了六个示例部件。它们在三深度表示中的偏移形状在图13中给出。在此图中，偏移形状的阴影图像是通过在偏移表面上的点处使用法向量信息绘制深度元素的每个端点来生成的这些法向量是使用第6.1节中解释的方法计算的。图14和15示出了这些部件的可能的球体接触形状的检测结果。 图图14示出了在零件表面上具有着色点的结果形状，图15使用小多边形可视化结果。这些是通过对偏移曲面应用收缩操作提取的。图16示出了这两者之间的差异。表1偏移所需的计算时间号样品多边形x-y平面网格分辨率z-x平面网格分辨率y-z平面网格分辨率所需时间A 597，455 895~ 1827 1827~ 709 895~ 709 774. 53B 369，408 1794~ 774 774~ 913 1794~ 913 594.58C 569，352 1168~ 1400 1400~ 658 1168~ 658 305.21D 1，488，731 672~ 1559 1559~ 642 672 ~ 642E 2，097，122 1432~ 736 736~ 431 1423~ 431 573.82F 2，097，122 1473~ 711 711~ 512 1473~ 512 566.48见图12。 样品零件。64M. Inui等人/Journal of Computational Design and Engineering 2（2015）55图13岁三深度表示中样例零件的偏移形状图十四岁试样接触球体形状的检测结果生成的形状通过零件表面上的彩色点可视化图十五岁试样接触球体形状的检测结果生成的形状用小多边形可视化M. Inui等人/Journal of Computational Design and Engineering 2（2015）5565图16. （a）基于点的可视化和（b）基于点的可视化之间的差异。方法.结果是相似的，但多边形的可视化（图16（b））在球体接触形状上产生了更精细的细节。8. 结论在本文中，我们提出了一种新的方法，以协助ECE的安全检查的内部和外部的汽车零部件。该方法从零件的偏置曲面中提取可能的球面接触形状.多面体零件模型的偏移形状被计算为模型的所有表面三角形的扩展形状的布尔并集。采用三维模型的三深度表示，以实现稳定和精确的布尔计算。提出了一种新的基于伪链表结构和AABB的并行偏移算法，在GPU上利用并行利用偏移形状，提取了零件表面上可能的球面接触形状.我们研究了一种新的可视化方法，其中偏移表面本身收缩，以获得由球体在零件表面上滑动产生的表面零件表面和收缩表面之间的相交对应于球体接触形状。我们的系统仍处于试验阶段。我们正准备在实际汽车设计过程中对该系统进行实地测试，并将根据设计师的意见和要求在未来工作中进行进一步改进利益冲突作者与本文内容没有直接相关的利益冲突。引用[1] 碰撞测试工程师的门户网站[Internet]。与碰撞测试相关的欧洲法规[引用于2014年9月27日]。可从以下网址获得：www.crash-network.com/Regulations/ECE_Regulations/ece_regulations.html[2] 日本汽车标准国际化中心（JASIC）[互联网]. [2014年9月27日]。可查阅：www.jasic.org/e/index_e.htm。[3] EDS Technologies [Internet].[2014 年 9 月 27 日 ] 。 可 查 阅 ： http ：//www.edstechnologies.com/publish.html。[4] Michelucci D. Benouamer MO通过三重射线表示弥合CSG和BREP之间的差距。在：ACM Symposium on Solid Modeling and Applications;1997; p.68比79[5] [10]杨文，李文，李文，李文.在线雕刻和多深度体的可视化见：第八届ACM实体建模和应用研讨会论文集; 2003年;第258-261页。[6] 任毅，朱伟，李延生. 产品原型设计中三维立体模型到多面体表面模型的特征保持与转换。计算机辅助设计与应用2008; 5（6）932-41。[7] Zhang W，Leu MC.基于三坐标表示的数控加工仿真。在：柔性自动化国际研讨会论文集; 2008; ISFA2008U_100。[8] 日 本 丰 田 汽 车 公 司 . [2014 年 9 月 27 日 ] 。 见 http ： //www.j-tokkyo.com/2006/G06F/JP2006-277304.shtml [日文]。[9] Yamazaki S，Baba T，Umezu N.，犬尾湾汽车内部部件的快速安全验 证IEEE International Conference on Mechatronics and Automation（ICMA）; 2011; p.1957-1962年。[10] Inui M，Umezu N.汽车零部件头部碰撞形状的快速检测。Journal ofAdvanced Mechanical Design，Systems，and Manufac-turing 2013; 7（5）818-26.[11] Inui M，Ohta A.使用GPU加速模具制造。 IEEE计算机图形学与应用2007; 27（1）82-8。[12] RossignacJR，Requicha AAG.实体建模中的偏移操作计算机辅助几何设计1986; 3：129-48.[13] 前川湖偏移曲线和曲面概述。计算机辅助设计1999; 31：165-73.[14] 范湾偏移曲线和曲面：简要综述。计算机辅助设计1992; 24（4）223-9.[15] 霍夫曼几何与实体建模：导论。Burling-ton（MA）：MorganKaufmann; 1989.[16] Satoh T，Chiyokura H.使用曲面数据对集合进行布尔运算。在：ACM Symposium on Solid Modeling Foundations and CAD/CAMApplications; 1991; Austin，Texas; p.119比127[17] 福赛斯·M炮击和抵消机构。在：第三届实体建模和应用研讨会论文集; 1995年;盐湖城，犹他州;第101页。3 7 3 -381.66M. Inui等人/Journal of Computational Design and Engineering 2（2015）55[18] 万胡克湾实时着色铣削显示。计算机图形学（ACM S
