【优秀硕士博士论文】基于弹簧-质点模型的收缩膜模拟

硕士学位论文题目基于弹簧质点模型的收缩膜模拟专业计算机科学与技术研究方向数字图像处理与计算机图形学授予学位日期2014年6月30日基于弹簧质点模型的收缩膜模拟计算机科学与技术专业虚拟包装作为计算机辅助设计的重要应用之一，它是建立在计算机仿真技术、三维建模和计算机图形学等基础之上的综合应用。通过对数字化包装模型的计算机仿真试验进行包装产品的评估，可以降低产品设计成本，并提高其设计质量，从而提高企业生产效益。本文以收缩膜为研究对象，详细分析了现实工业软包装中收缩膜材料的物理结构和收缩性能。在充分研究柔性物体物理模型的基础上，建立了基于弹簧质点模型的收缩膜物理模型。通过对收缩膜的模拟，解决了现实工业收缩膜包装生产中，因收缩膜形变产生的图片或文字失真问题。本文工作的主要内容包括1）提取影响收缩膜形变的主要物理特性，建立基于弹簧质点模型的收缩膜物理模型，将收缩膜离散化为一张规则的质点网格。通过对质点进行受力分析，建立起力学模型，并采用显式欧拉数值积分法对质点进行运动方程求解，实现收缩膜的动态模拟。2）为了提高整个系统的普适性和健壮性，本文测试了不同的物体模型。通过大量的试验总结出了系统参数的自适应计算方法，用于计算系统弹簧长度、胡克系数和阻尼系数等参数。3）为了解决收缩膜在收缩过程中和被包裹物的碰撞检测问题，本文采用了基于AABB层次树的碰撞检测算法，并给出了其详细的构造过程和计算方法。同时，引入了OPENMP并行计算技术，提高了碰撞检测算法的计算效率。4）为了解决收缩膜收缩后导致的图片或文字的失真现象，本文提出纹理预失真方法。该方法根据收缩膜初始态和稳定态质点的位置信息，在纹理贴图之前对图片的纹理坐标进行预先变化，以此来解决失真问题。本文针对不同的质点规模、弹簧拉伸率、纹理预失真和效率等方面进行了详尽的实验，并给出了各种实验条件下的效果图和效率对比。实验结果表明，针对不同的模型，都取得了较为真实的收缩效果，证明了本文算法的普适性和健壮性；在不同的实验条件下，实验效果与预期接近，说明了本文模拟的真实性；从系统效率测试数据可知，在取得良好效果的前提下，系统能够较为流畅的完成模拟，体现了本文算法的实时性。通过纹理预失真处理，解决了图片或文字失真的问题，达到了本文模拟的目的。关键词弹簧质点模型，收缩膜，碰撞检测，纹理预失真，OPENMPSHRINKFILMSIMULATIONBASEDONSPRINGMASSMODELMAJORCOMPUTERSCIENCEANDTECHNOLOGYVIRTUALPACKINGISONEOFTHEIMPORTANTAPPLICATIONSOFCOMPUTERAIDEDDESIGN,WHICHISTHECOMPREHENSIVEAPPLICATIONBASEDONCOMPUTERSIMULATIONTECHNOLOGY,COMPUTERMODELINGANDCOMPUTERGRAPHICSTHROUGHDIGITALPACKAGINGSIMULATING,EVALUATINGPACKAGINGPRODUCTSCANREDUCETHEDESIGNCOST,IMPROVETHEQUALITYOFDESIGN,SOASTOIMPROVEPRODUCTIONEFFICIENCYREGARDINGSHRINKFILMASTHERESEARCHOBJECT,THETHESISANALYZESTHEPHYSICALSTRUCTUREANDPERFORMANCEOFINDUSTRIALSHRINKFILMINDETAILONTHEBASISOFFULLYSTUDYINGFLEXIBLEPHYSICALMODEL,THETHESISESTABLISHESTHESHRINKFILMMODELTHATBASEDONSPRINGMASSMODEL,ANDSOLVESTHEDISTORTIONOFIMAGESORCHARACTERSININDUSTRIALBYTHESIMULATIONTHEMAINCONTENTOFTHEARTICLEINCLUDESFIRST,THETHESISSUMMARIZESTHEMAINPHYSICALPROPERTIESTHATAFFECTSHRINKFILMDEFORMATION,ESTABLISHESTHESHRINKFILMMODELANDSEPARATESSHRINKFILMINTOAUNIFORMGRIDOFPARTICLESBYTHESTRESSANALYSISOFPARTICLE,THEMECHANICSMODELISBUILTANDTHETHESISSELECTSTHEEXPLICITEULERNUMERICALINTEGRATIONMETHODTOIMPLEMENTTHEDYNAMICSIMULATIONOFSHRINKFILMSECOND,INORDERTOIMPROVETHEUNIVERSALITYANDROBUSTNESSOFTHESIMULATIONSYSTEM,THEARTICLETESTSDIFFERENTMODELSTHROUGHLOTSOFEXPERIMENTS,SUMMARIZINGTHEADAPTIVEPARAMETERCALCULATIONTHATUSEDTOCALCULATESYSTEMPARAMETERS,SUCHASSPRINGLENGTH,HOOKCOEFFICIENT,DAMPINGCOEFFICIENTTHIRD,THETHESISAPPLIESTHECOLLISIONDETECTIONALGORITHMBASEDONAABBHIERARCHYTREE,ANDGIVESTHEDETAILEDCONSTRUCTIONANDCALCULATIONPROCESSATTHESAMETIME,THETHESISINTRODUCESTHEOPENMPPARALLELCOMPUTINGTECHNOLOGYTOIMPROVETHEEFFICIENCYOFCOLLISIONDETECTIONALGORITHMFOURTH,THETHESISUSESTHETEXTUREPREDISTORTIONMETHODTOSOLVETHEDISTORTIONOFIMAGESORCHARACTERSACCORDINGTOTHEINITIALANDSTABLESTATEOFPARTICLESPOSITION,THEMETHODREVERSELYADJUSTSTEXTURECOORDINATESBEFORETEXTUREMAPPINGTHETHESISCONDUCTSDETAILEDEXPERIMENTSONPARTICLESIZE,SPRINGSTRETCHINGRATE,TEXTUREPREDISTORTIONANDEFFICIENCY,ANDGIVESTHEEFFECTANDEFFICIENCYINVARIOUSEXPERIMENTALCONDITIONSTHEEXPERIMENTALRESULTSSHOWTHATGOODCONTRACTIONEFFECTSAREOBTAINEDINDIFFERENTMODELS,ANDPROVETHEUNIVERSALITYANDROBUSTNESSINDIFFERENTEXPERIMENTCONDITIONS,EXPERIMENTALRESULTSARECLOSETOTHEEXPECTED,WHICHPRESENTTHEAUTHENTICITYOFTHESIMULATIONFROMEFFICIENCYTEST,THESYSTEMCANFINISHSIMULATIONSMOOTHLYINREALTIMETEXTUREPREDISTORTIONSETTLESTHEDISTORTIONOFIMAGESORCHARACTERS,ANDACHIEVESTHEGOALOFTHESIMULATIONKEYWORDSSPRINGMASSMODEL,SHRINKFILM,COLLISIONDETECTION,TEXTUREPREDISTORTION,OPENMP目录目录I1绪论111课题研究背景112课题研究意义313收缩膜模拟的主要难点414本文主要工作415本文组织结构516本章小结62相关工作综述721收缩膜模型7211几何模型7212物理模型7213混合方法8214几种常见建模方法比较922碰撞检测算法9221碰撞检测算法分类9222常见碰撞检测算法1023数值积分方法概述1324OPENMP并行技术15241OPENMP概述15242OPENMP执行模式1625本章小结173收缩膜的物理建模1831收缩膜建模1832力学模型20321内力分析20322外力分析2533数值积分方法2534本章小结264收缩膜的碰撞检测及响应2741基于AABB层次树的碰撞检测算法27411构建AABB二叉树28412收缩膜与模型的碰撞检测2942碰撞响应3343OPENMP使用3344本章小结375收缩膜系统实现细节3851系统设计38511系统算法数据结构和UML图38512系统算法流程设计4052系统实现细节42521模型构造42522收缩膜初始套筒构造43523收缩过程模拟49524纹理预失真5053本章小结536实验结果及其分析5461实验环境5462实验结果与分析54621不同投影轴55622不同的质点规模58623不同的弹簧拉伸率59624纹理预失真处理效果60625算法加速效率分析63626本文算法不足分析6563本章小结667总结与展望6771总结6772展望68参考文献70作者在读期间的科研成果74声明75致谢76图11收缩膜应用2图12收缩膜上文字或图像的产品说明3图21常见包围盒平面图11图22两种并行方式系统结构图15图23FORKJOIN并行执行模型17图31收缩膜物理模型结构图19图32三种弹簧类型19图41碰撞穿透效果图27图42AABB层次树构造过程示意图29图43AABB层次树的遍历过程30图44线段与平行平面相交测试示意图5531图51系统UML图（1）38图52系统UML图（2）39图53本文算法流程图41图54复合模型效果图42图55二维凸包计算过程46图56凸包优化效果图47图57收缩膜质点网格效果图48图58收缩膜套筒效果图49图59纹理失真效果图50图510标签图案示意图5751图511纹理预失真前示意图5751图512纹理预失真后示意图5752图61沿X轴效果图55图62沿Y轴效果图56图63沿Z轴效果图57图64质点规模效率测试58图65BOTTLE模型不同拉伸率效果图59图66BALL模型不同拉伸率效果60图67纹理预失真前后对比图62图68使用OPENMP前后效率对比图64图69收缩膜被穿透效果图65图610弹簧穿透模型示意图651绪论11课题研究背景虚拟包装是建立在计算机仿真技术、三维建模和计算机图形学等技术基础之上的综合应用。其基本思想是采用包装产品的数字化模型代替实物样品，并通过对数字化包装模型的计算机三维仿真试验进行包装产品的评估1。虚拟包装能够以较短的开发周期和较低的设计成本获得较高的产品设计质量，从而提高企业的生产效益。其相关应用能够使包装业的产品生产、设计具有快速的市场应变能力，进而大大提升了其市场竞争力。作为一种常见的包装材料，收缩膜在现实生活中被大量使用。它不仅能紧束包装物，防散性好，而且贴体透明，能体现商品的形象。因此，收缩膜被广泛应用于电子电器、药品、食品和工艺礼品等各种产品的外包装，如图11所示。收缩膜在常温下稳定，当加热到玻璃化温度时则会产生收缩现象，并且收缩膜材料具有合适的纵横收缩率。例如，当作为收缩膜套筒使用时，如果纵向过度收缩，则收缩膜不能完全包裹物体；而如果横向收缩不够，则会产生褶皱。收缩膜通常是由无定型塑料材料加工而成，常见的材料有聚偏氯乙烯（PVDC）、聚苯乙烯（PS）、聚氯乙烯（PVC）等。PS收缩膜韧性低，使用较少，而PVC收缩膜不便于回收再利用，并在燃烧时会产生大量有毒气体，不利于环保。聚酯（PET）收缩膜是一种新型的收缩膜包装材料，它无毒、无气味、并且便于回收，是公认的环保型收缩膜材料。此外，它的物理机械性能、技术指标、应用范围和使用方法等都比较接近于PVC收缩膜，又因其价格低廉，所以它是PVC收缩膜的理想取代品。且PET收缩膜的纵向收缩率小于百分之三，而其横向收缩率能够达到百分之七十，是当前收缩性能最好的收缩膜材料。聚酯收缩膜采用急骤冷却无定形的工艺方法吹塑成型，这种生产工艺方法根据高聚物材料定向原理设计1。在软包装设计中，通过对收缩膜添加图片或文字信息可以达到广告宣传和美观的目的，如图12所示。但是，在通常情况下，将规则的纹理图片贴到扭曲的收缩膜上时，图片或文字将发生失真，如图12中标记部分。在传统的工业软包装中，通过不停的试探图片或文字失真的程度来改变印刷图案，以解决这个问题。为了得到正确的预失真图案，往往需要通过多次试探，浪费了大量的人力和物力资源。图11收缩膜应用12课题研究意义1）理论意义本文研究分析了收缩膜的物理特性，建立了基于弹簧质点模型的收缩膜物理模型。通过对现实工业中收缩膜收缩过程的分析，定义了该模型的力学模型，并设计了系统模型参数的自适应算法，以适应各种不同的被包裹物，增强了整个系统的鲁棒性，本文工作为后续的收缩膜研究和模拟奠定了理论基础。2）现实意义通过虚拟模拟的方法，在软包装开发设计的过程中能够及早的发现问题，及时给予反馈，从而能够选择出最佳的收缩效果。并针对现实工业软包装中收缩膜上的图片或文字失真问题，本文提出了纹理预失真方法。该方法根据收缩膜初始态和收缩后稳定态的质点位置信息，对图片的纹理坐标按一定规则进行变换，使之预先发生失真，而经过收缩膜收缩后，正好恢复到未失真状态。通图12收缩膜上文字或图像的产品说明过数字化处理的方法替代了人为的反复试探，节约了人力和物力资源，降低了产品设计中可能产生的经济损失。13收缩膜模拟的主要难点目前，针对收缩膜虚拟仿真技术的研究相对空白，由于收缩膜本身材料的多样性、结构的复杂性和物理特性的多变性，给使用计算机仿真和虚拟现实技术精确高效的模拟收缩膜收缩过程带来很多困难。具体来说，在收缩膜的模拟中存在如下难点1）收缩膜的物理建模由于收缩膜的制作方法和物理材料各异，导致其物理结构和收缩属性也会千差万别，这给收缩膜的物理建模带来了很大困难。因此，如何构造一个能够精确表征收缩膜特性的物理模型是本文模拟的难点之一。2）收缩模拟过程的鲁棒性本文希望可以构建一个通用系统，能对不同模型进行收缩膜模拟。因此，如何根据不同的模型自适应计算出不同的模拟参数，提高算法的普适性和健壮性是本文的难点之一。3）收缩膜收缩过程中的碰撞检测和响应问题本文将收缩膜离散化为一张由大量排列规则的质点构成的网格，在收缩膜的收缩模拟过程中，为了避免质点穿透模型，必须进行大量费时的碰撞检测以及碰撞响应计算。如何提供精确且高效的碰撞检测及响应算法是本文需要解决的难点之一。4）纹理图案失真处理为了解决传统工业软包装中收缩膜上图案失真的问题，本文尝试采用计算机仿真技术对包装产品进行数字化评估。但是，该采用什么样的处理方法矫正图案的失真是本文要解决的难点之一。14本文主要工作本文主要工作如下1）通过对收缩膜物理属性的大量分析和研究，提取影响收缩膜形变的主要物理特性，建立了基于弹簧质点模型的收缩膜物理模型，为本文的收缩膜模拟奠定了坚实的理论基础。2）为了使本文模拟系统具有普适性和健壮性，设计了包括弹簧长度、胡克系数和阻尼系数等系统参数的自适应计算方法。3）通过对计算机仿真中常用的碰撞检测算法做了研究和对比，总结出了适合本文收缩膜模拟的基于AABB层次树的碰撞检测算法和质点碰撞即静止的响应处理方法。同时，为了提高本文算法的计算效率，引入了OPENMP并行计算技术。4）附加到收缩膜上用于说明或美观的图片或文字可能会因为收缩膜的收缩而发生失真现象，本文采用纹理预失真方法，设计了纹理坐标变换规则，并通过对图片纹理坐标的变化，解决了失真的问题。15本文组织结构第一章简要介绍了本文的研究背景和意义，详细介绍了收缩膜模拟的主要难点和本文的主要工作。第二章介绍了几种用于柔性物体模拟的建模方法及其发展历程，并对它们的物理性能和适用情况做了对比。对几种常用的碰撞检测算法进行了详细的介绍，并分析了几种典型的数值积分求解方法。为提高本文算法计算速度，引入了OPENMP并行计算技术。第三章建立了基于弹簧质点模型的收缩膜物理模型，对该模型中不同弹簧的收缩率，以及各质点所受内力和外力进行了具体的分析和计算。并选取了适合本文收缩膜模拟的显式欧拉数值法，建立了各质点的运动求解方程。第四章根据收缩膜模拟的特性选择了基于AABB层次树的碰撞检测算法，定义了质点碰撞即静止的碰撞响应方法，并详细介绍了AABB二叉树的构建和收缩膜与模型的碰撞检测过程。最后，介绍了OPENMP在本文算法中的使用，并对REDUCTION、SCHEDULE等子句的用法和功能进行了详细说明。第五章对本文算法所使用到的各种数据结构做了描述，并给出了系统UML图和算法设计流程图。给出了本文算法的各部分的具体实现，并且为提高算法的鲁棒性，对部分算法进行了约束和改进。第六章设计了几种不同参数下收缩膜模拟的实验效果，对结果进行了详细的分析，并给出了使用OPENMP并行技术前后的计算效率测试和对比。另外，对本文算法的不足点进行了简要的说明和分析。第七章对本文研究工作进行总结，简述在实现过程中遇到的问题及相应的解决方法。详细阐述了本文算法的不足，并对后续的研究工作提出展望。16本章小结本章首先介绍了本文研究的背景和意义。其次，详细介绍了本文模拟实现过程中的诸多难点，并根据本文的几个难点，详细给出了本文的主要工作内容。最后，对本文的组织结构做了详细说明。2相关工作综述21收缩膜模型鉴于布料与收缩膜的相似性，本文借鉴布料模拟方法来对收缩膜进行建模，并加入收缩膜特有的物理特性。在外力作用下布料会产生不规则变形，并且由不同材料，不同制作方法制得的布料具有各种不同的特征参数，234中对此有详细描述。由于布料本身特性的复杂性，尚不存在一个统一的物理表达模型。目前，用于布料建模的方法大致可以分为三类几何方法、物理方法和混合方法5。211几何模型在布料模拟的初期，由于计算机硬件环境的限制和物理方法计算量非常大等原因，因此广泛采用基于几何特性的建模方法来表示布料的内部特性和外部形态，并使用数学方法来简化和模拟复杂布料的运动行为。长期以来，许多研究者做了大量的工作，从不同的角度探究了布料模拟方法。1986年WEIL等6最早提出了一种基于几何特征的布料建模方法，该方法采用余弦函数以及其几何变换来模拟悬垂的布料。HINDS等78提出基于等距面的几何方法，NG等9采用纯几何方法来模拟特殊情景下布料的形变。另外，HADAP等10采用几何方法与纹理技术相结合的方式模拟布料上的褶皱。以上基于纯几何方法建模的模拟技术，大多数采用的是悬链线、B样条插值等方法，这些方法不需要求解繁杂的微分方程，因此其计算量小，效率较高。但是，纯几何方法模型并没有考虑布料的物理属性，而且还需要用户进行一定程度的交互干预，因此该方法模拟效果欠佳，而且适用性较差。212物理模型鉴于纯几何方法模型不能反映布料的物理特性，TERZOPOULOS等411将运动力学上的某些模型应用到了布料仿真。在基于物理方法的模型中，为了更加形象的表征布料的内部结构，通常把布料离散化为一张规则的质点网格，通过加入质点的质量、速度、加速度和合力等物理属性，将布料各个部分的运动看作质点在合力作用下运动的结果。根据物理运动规律，建立并求解微分方程来模拟布料的各种运动行为。基于物理方法的模型主要包括以下几类弹性形变模型（ELASTICITYBASEDMODEL）1214，弹簧质点模型（SPRINGMASSMODEL）1519和粒子模型（PARTICLEMODEL）2024。TERZOPOULOS4最早提出基于物理的弹性模型，该模型是布料模拟技术上的里程碑。它从连续力学的角度研究物体的形变，并认为柔性物体的运动遵循牛顿经典力学定律和弹性力学原理，将运动求解归结为以时间为函数的微分方程求解，通过求解微分方程得到物体上各质点的空间位置、速度和加速度等物理属性。后来的研究者大都承用该运动力学思想，把工作的重点集中在弹性模型上，并提出了很多布料模拟技术，这些技术最终都可以归结为弹簧质点模型。PROVOT16首次提出了弹簧质点模型，该模型将布料离散成构成网格的质点，质点间由无质量的理想弹簧连接。CHOIKJ等18在PROVOT的基础上做了少许的修改和补充，提出了相似的物理模型。弹簧质点模型的构造复杂度较低，即使模拟较为复杂的布料运动形态，也能够获得比较真实的效果，并且该模型计算量小、速度快，本文模拟系统中使用的正是这种物理模型。BREEN等20在探究了不同布料力学特性的基础上，提出了粒子系统方法。该方法将布料表示为质点的集合，使用相邻粒子间的几何关系来表达布料的外部形态，并通过粒子间的相互作用力表示布料的行为。然后对该模型系统建立运动方程，采用数值积分法对其求解实现布料的实时模拟25。相对于几何方法，基于物理方法的布料模拟可以获得更加逼真的效果，但是由于使用了大量的数学、物理定律和微分方程，因此基于物理的方法计算量较大，模拟速度较慢。不过，由于该方法能够直观的表征布料的物理特征属性，因而在布料的模拟中，它是一种行之有效的方法。213混合方法鉴于几何方法和物理方法各自的优缺点，一些混合方法被提出。RUDOMIN26最早提出了几何物理混合方法，该方法通过建立一个基于几何模型的布料的凸包来构建布料的初始形态，然后再运用物理方法表达其行为。为了形象表示布料的褶皱，KUNII27提出了基于几何物理混合方法的奇异性理论。混合方法的基本思想是先构建布料的几何模型来表达其初始形态，而后根据其物理特性进行行为表达。采用混合方法进行布料模拟，其真实感与基于物理的方法相差甚远，因此该方法没有被继续研究下去。214几种常见建模方法比较以上几节分别对几何方法、物理方法和混合方法做了详细的介绍和分析，研究者从模拟的真实性、效率等方面出发，采用不同的理论和方法对布料模拟进行了大量研究。由于对布料模拟的侧重点不同，所以这些方法有各自的优缺点。它们的比较如表21所示。表21常见建模方法比较类型几何方法物理方法混合方法优点计算量较小，模拟效率较高。真实感较强，能很好的表达出布料的真实属性。在真实感和效率方面得到了折衷。缺点真实感较差，不能真实的表达出布料的真实属性。计算量稍大，模型求解方法稍复杂，模拟速度稍慢。算法复杂度较高，计算量庞大，且适用性较差。22碰撞检测算法在计算机仿真、虚拟现实、游戏和机器人路径规划等领域中，碰撞检测是一个至关重要的问题。在计算机三维仿真和大型3D游戏中，为了能反映出真实的现象，系统必须能够及时检测到碰撞，并做出合理的响应。随着虚拟场景和几何模型日益复杂，以及人们对场景的真实性和实时交互性的要求也逐渐增高，碰撞检测和响应往往成为系统效率的瓶颈之一。221碰撞检测算法分类根据考虑的角度不同，碰撞检测算法从总体上可以分为基于时间的和基于空间的两大类28。其中，基于时间的碰撞检测算法又可分为连续的和离散的两类29。连续的碰撞检测算法是在连续的时间间隔内进行碰撞检测，虽其正确性得到了保证，但是计算量较大，不能满足实时性；而离散的碰撞检测算法是在每个离散的时间点上都进行检测，这样可能就会漏掉本该发生碰撞的情形，但其检测速度较快。基于空间的碰撞检测算法分为基于图像空间的和基于物体空间的两类29，而基于物体空间的碰撞检测算法又可分为基于空间结构的和基于模型的两类。其中，基于空间结构的碰撞检测算法可进一步分为层次包围盒法30和空间切分法3132两小类。空间切分法的基本思想是将整个场景空间切分为等体积的单元格，仅对相邻单元格或占据同一单元格的几何对象进行相交测试，比较经典的方法有八叉树3334、KD树35和BSP树3637，层次包围盒法的基本思想将在下节详细介绍。空间切分法和层次包围盒法都使用了层次结构模型，其目标是通过尽可能的减少需要进行相交测试几何对象的数目，来提高碰撞检测算法的效率。空间切分法由于灵活性差、存储量大，一般适用于稀疏场景中分布比较均匀的几何对象间的碰撞检测。222常见碰撞检测算法基于层次包围盒的碰撞检测算法是目前计算机仿真和大型3D游戏等中广泛采用的碰撞检测技术3839，它利用几何结构简单而体积略大的包围盒对复杂几何对象进行近似表达。在进行碰撞检测时，首先进行包围盒间初步的相交测试，只有包围盒相交时，才对其包裹的对象做进一步相交测试。在初步的包围盒间相交测试时，为了避免不必要的测试，引入了二叉树结构，可以快速剔除不可能发生碰撞的对象，能够快速逼近对象的几何模型，提高了计算效率40。比较经典的层次包围盒算法有沿坐标轴的包围盒AABBAXISALIGNEDBOUNDINGBOX4143，方向包围盒OBBORIENTEDBOUNDINGBOX44、包围球SPHERE4547和KDOPSDISCRETEORIENTATIONPOLYTOPE32等，如图22给出了几种常见包围盒平面图。1）AABB包围盒AABB是沿坐标轴的包围盒，它的各边平行于各坐标轴并且是能够包裹几何对象的最小长方体。在构造AABB包围盒时，根据几何对象的位置和形态取得到其在X，Y，Z方向上的最小值和最大值，作为包围盒最低和最高的顶点，便可确定AABB包围盒。由于构造一个几何对象的AABB包围盒只需6N次比较（N为几何对象的顶点数目），因而AABB包围盒的构造难度较低，并存储量较小。AABB包围盒与基本几何元素间的相交测试复杂度较低，即使是两个AABB间的求交测试，也最多需要6次比较。但是，AABB包围盒的紧密型稍差，特别对于倾斜放置的细长形几何对象，该包围盒将留下很大的空隙，会造成大量冗余的相交测试，AABB包围盒的构造将在第四章中详细介绍。2）OBB包围盒OBB是有向包围盒，它是能够包裹几何对象，且在任意方向上最小的长方体。构造OBB包围盒的过程相对复杂，关键在于如何确定包围盒的最佳方向，以及在最佳方向上确保包围盒的体积最小。假定几何对象的基本几何元素为三角形，并设第I个三角形的顶点分别表示为，则可计算出该几何对象的均值和协方差矩阵130（N为三角形数目），130,1,3，均为三维矢量。由于协方差矩阵的三个特征向量两两垂直，规一化后可作为基底，可以用来确定OBB包围AABB包围盒OBB包围盒SPHERE包围球KDOPS包围盒图21常见包围盒平面图盒的最佳方向。计算几何对象的所有顶点在基底上的投影，根据三个轴向上最小和最大投影的差值可以确定OBB包围盒的大小，由此可知OBB包围盒的构造复杂度较大。存储一个OBB包围盒需要15个浮点数，其中9个浮点数表示最佳方向的三个基底向量和6个浮点数表示范围，其存储量比仅需6个浮点数的AABB包围盒稍大。由于OBB间的相交测试基于分离轴理论，因此其相交测试算法的复杂度较大，效率较低。但是，因为OBB包围盒的方向根据几何对象的位置形态确定，所以其能够紧密的包裹几何对象，紧密型较好。3）包围球包围球是能够包裹几何对象的最小球体。假定几何对象的质点坐标最小值为，最大值为，则可以通过最小和最大，值确定包围球的球心，计算方法为，半径012,012,012，则包围球可定义为1222212。从以上计算方法可知包围球,|0202028UPDATEDAMPERFACTORCURSPRINGLEN,TARGETLEN,SEARCHSTEP9CURSPRINGLENCOMPUTESPRINGLENWITHDAMPERDAMPERFACTOR,TIMEWITHOUTDAMPER10IFTARGETLENBETWEENLASTSPRINGLENANDCURSPRINGLEN11SEARCHSTEPSEARCHSTEP/212LASTSPRINGLENCURSPRINGLEN13RETURNDAMPERFACTOR表31中，第3行在没有阻尼力作用下，根据系统信息计算收缩膜到达弹簧自然长度状态时（初始化弹簧为拉伸状态）所经过的时间TIMEWITHOUTDAMPER。第4行根据收缩膜的收缩率以及系统初始化弹簧长度，计算得到系统趋于稳定状态时弹簧长度TARGETLEN。第5行根据系统初始化的阻尼系数DAMPERFACTOR和TIMEWITHOUTDAMPER，计算得到当前阻尼系数下的弹簧长度CURSPRINGLEN。第7行进入循环体开始调整DAMPERFACTOR，当CURSPRINGLEN大于TARGETLEN时，DAMPERFACTOR减少一个搜索步长SEARCHSTEP，反之则反。第10行表示当弹簧长度变化较大时（亦即阻尼系数改变较大），SEARCHSTEP将减半。当CURSPRINGLEN无限趋近于TARGETLEN时循环体结束，当前DAMPERFACTOR即为系统的阻尼系数。322外力分析上文已经介绍，收缩膜的收缩原理是采用热吹塑成型的，利用的是收缩膜材料遇热收缩的特性，并加以吹力使得收缩膜紧贴模型。为了形象的模拟收缩膜收缩效果，这里自定义一个外力来模拟工业上的热吹风力，其定义如公式312所示。312_0,1式中，表示收缩膜所受的热吹风力，为质点所受弹力的_平均值；表示外力系数，其越大收缩膜收缩越快，最终贴的越紧，反之则反。因此，综上可以得到质点I所受到的合力如公式313所示31333数值积分方法由于显式积分方法在每一个时间步的计算速度都优于隐式积分方法，尤其当系统中质点规模较小时，显式积分方法相比隐式积分方法具有更好的效率。另外，在系统小时间步长的情况下，显式欧拉法单步计算的速度较其他方法更快，不但保证系统计算的高效性，而且也获得了系统模拟稳定性和精确性，因此本文采用了显式欧拉数值积分法进行运动方程求解。根据质点I在T时刻的所受合力计算出在一个时间步长后的速度，然后再根据质点I在T时刻的位置和已经得到的速度便可以计算出质点I在时刻后的位置，表示为公式314和315。314315式中，表示质点I在T时刻的速度，表示质点I在T时刻的位置，表示质点在I在T时刻所受的合力，M表示质点I的质量，是系统时间步长。显式欧拉法实际是利用质点I在T时刻的加速度与在T时刻的速度来近似表示质点I在时间段内的平均加速度和平均速度，这是影响模拟精确性的主要因素，因此可以将时间步长设置在一个很小的阈值内，以提高系统模拟的计算精确度。同时，通过调整时间步长和弹簧弹性系数等方法可以避免或解决显式欧拉法导致的模拟系统不稳定问题。从本文的实验结果分析得到，采用该方法进行收缩膜模拟可以达到高效、精确，以及较为真实的模拟效果，本文第六章中给出了针对不同模型的收缩膜效果，此处不再累述。34本章小结在本章中，首先，分析了基于弹簧质点模型的特点，将其与收缩膜联系起来，建立了基于弹簧质点模型的收缩膜物理模型，并对模型中的三种弹簧的作用分别作了详细的说明。其次，将收缩膜离散化为规则的质点网格，对质点进行内外力分析和计算，并给出了弹簧胡可系数和阻尼系数的自适应计算方法。最后，通过采用显式欧拉法对质点的运动方程进行求解，以达到高效、精确、真实的模拟效果。4收缩膜的碰撞检测及响应本文碰撞检测和响应的任务是确定收缩膜和模型之间是否会发生碰撞，并在碰撞发生时，改变质点运动方式，以防止其穿透模型，如果不能及时检测到碰撞发生并做出正确响应，就会出现收缩膜穿透模型的不真实现象，如图41所示。41基于AABB层次树的碰撞检测算法基于以下几个因素，本文选取AABB包围盒作为收缩膜碰撞检测的基本加速结构一是仅仅需要几何对象的位置信息在X，Y，Z方向上的最小和最大值即可构造AABB包围盒，其构造难度低，并且信息存储量少；二是AABB图41碰撞穿透效果图包围盒间的相交测试复杂度低，即使是两个AABB包围盒间的相交测试也最多仅需要6次比较；三是本文被收缩膜包裹的几何对象是静态物体，包围盒一旦建立不需要更新。为了进一步减少质点和被包裹模型的几何相交测试，本文进一步采用基于AABB包围盒的层次包围盒技术，为被包裹模型建立一棵层次二叉树，有效地提高碰撞检测速度。411构建AABB二叉树针对被包裹的几何模型，本文采用自顶向下的方法为其构造AABB层次二叉树，该方法的基本思想是以递归的方式将父节点中的几何对象划分为两个子集，并为之构建AABB包围盒，然后加入到左右孩子结点中，构造过程示意图如42所示，算法的实现过程步骤如下（1）获取几何对象模型的三角形集合，计算该集合的AABB包围盒，并创建二叉树根结点。（2）确定分割轴采用最长轴方法，选取AABB包围盒在X，Y，Z轴上具有最大间距的轴，该方法仅需要两次比较便可确定分割轴。（3）确定分割平面选择与分割轴正交的平面位置，可以采用平均值法或中值法确定分割点54。平均值法是选取AABB包围盒中所有三角形顶点在分割轴上投影的平均值，而中值法是选取分割轴的中间值。平均值法能够使得子节点的包围盒较小，但同时也破坏了二叉树的平衡性；而中值法可以得到两个大小基本相等的子节点包围盒，从而能够构造一棵平衡的二叉树，该方法计算简单，并降低了二叉树高度，因此本文采用中值法确定分割平面。（4）左右子集划分根据分割平面，将三角形集合划分为左右两个子集。在划分过程中，对于集合中的每一个三角形，找到其在分割轴上的最小和最大值，并计算两最值与分割平面间的距离。如果最大值与分割平面的距离大于最小值与分割平面的距离，则将该三角形划分到右子集中，否则划分到左子集中。当划分完三角形集合，如果所有的三角形都被划分到同一个子集中，则平均划分所有的三角形到左右子集中。（5）分别计算左右子集的AABB包围盒，并创建新结点作为父结点的左右孩子结点。（6）重复（2）（3）（4）（5）过程至终止条件。其中，递归构建层次树的终止条件通常有三种情况一是遍历过程达到某一指定的深度，二是集合中的三角形数量小于某给定的值，三是子包围盒中包含的三角形数量接近于其父包围盒。本文采用的终止条件是第二种，设定集合中的三角形数量小于10。412收缩膜与模型的碰撞检测在本文收缩膜物理模型中，收缩膜与模型之间的碰撞实际上是质点与模型之间的碰撞检测问题，本文将这个问题通过如下方式转换为线段与模型的相交测试问题。设质点在时刻的位置为，在下一个时间步长后的位置通过计算得到，由于时间步长较小，因此质点在一个时间步长内的运动轨迹可以近似为一条线段，此时已经将质点与模型的碰撞检测问题转换为判断线段是否和模型相交的问题。由于针对模型构建了基于AABB包围盒的层次结构，因此收缩膜与模型之间的碰撞检测最终转化成遍历AABB层次树，并进行线段与AABB包围盒和三角形之间的相交测试。1）遍历AABB层次树划分前第一次划分第二次划分图42AABB层次树构造过程示意图通过遍历AABB层次树，快速剔除不可能与线段相交的图元，大大提高了碰撞检测的效率。遍历AABB层次树主要借助一个栈结构，其过程如图43所示。在整个遍历过程中，主要涉及到线段和AABB包围盒以及线段和三角形求求交测试两个问题，下面分别由两个小节来叙述这两个问题。2）线段与AABB相交测试55开始层次树根节点入栈栈是否为空取栈顶节点，出栈计算交点结束YN该节点是否为叶节点Y线段与三角形是否相交Y线段与AABB是否相交N左、右孩子节点入栈YNN图43AABB层次树的遍历过程两个平行平面可以构成一个平行平面空间（SLAB），因此AABB包围盒可视为三个相互垂直的SLAB的交集。当且仅当线段的起点或终点位于AABB包围盒内部，或者线段与构成AABB包围盒的三个SLAB相交测试结果存在交集时，则说明线段与AABB包围盒相交，因此线段与AABB包围盒相交测试的关键是计算线段与三个SLAB的相交区间，及相交区间是否存在交集。为了计算所有的相交区间，需要记录线段进入每个SLAB的最大值，以及离开每个SLAB的最小值。如果入口的最大值大于出口的最小值，说明相交区间没有交集，则线段与AABB包围盒不相交，反之则反。对于由水平（XSLAB）和竖直（YSLAB）方向的SLAB构成的二维盒体，线段与其相交测试情况如图44所示。图44中，线段进入平行平面入口点为1和3，其中3为最大入口值，11出口点为2和4，其中2为最小的出口值。最大入口值大于最小出口值，线段与XSLAB、YSLAB之间的相交结果不存在交集，则该线段不与盒体相交。11线段进入平行平面入口点为5和6，其中6为最大入口值，出口点为7和228，其中7为最小出口值。最大入口值小于最小出口值，线段与XSLAB、Y22SLAB之间的相交结果存在交集，则该线段与盒体相交。P1P2Q1Q2INSIDEYSLAB图44线段与平行平面相交测试示意图55INSIDEXSLABINSIDEXSLABINSIDEYSLAB1234568777假定公式41表示线段，其中、分别为线段的起点和终点，则将其代入平行平面方程中即可求出T，如公式42所示。将T值代入到线段的参数化方程41中便可求得交点。41,0,142/式42中，为原点到平面的距离，为平面的法向量。3）线段与三角形相交测试55设三角形ABC上的点的定义如公式43所示43,式中，为该点的质心坐标，且。点P位于三角形ABC内,1部的必要条件是仅当该点的质心坐标满足，并由，0,11三角形上的点可以表示为如公式44所示44,若，则可得点P位于三角形内部。0,0且1假定两端点M、N构成的线段定义为如公式41所示。通过假定可以求出，然后根据这些变量的范围来确定三角形与线段是,否相交。45,464748根据公式45、46、47和48，并由克莱姆法则可求得，如公式49,所示491,1,2,1,2,2,1,式中，。12由于，则公式49可以变形为如公式410DET,|所示4101121221若，且，则三角形与线段相交，并可以通过010,01T求出交点。42碰撞响应碰撞响应是影响收缩膜模拟效果的重要因素之一，如果碰撞响应处理不当，不仅会耗费大量的计算资源，更会严重影响模拟效果的真实性。通过对现实工业软包装中不同种类收缩膜收缩过程的观察和分析发现，收缩膜在热吹风的作用下逐渐逼近被包裹物，当收缩膜局部到达被包裹物后，该部分将紧紧依附在被包裹物表面，收缩膜几乎不会发生滑动或者被反弹的现象。因此，本文采取的是碰撞即静止的方法来近似模拟收缩膜与被包裹物碰撞后的效果，即弹簧质点在运动一个时间步长后，如果检测到质点在内运动形成的线段与模型相交，则可根据41节中的方法求得线段与该AABB内三角形面片的交点，此时将该弹簧质点的位置信息置为已求得交点的位置信息，并将其标记为已经发生碰撞状态，而后续的模拟不再对该质点进行运动方程求解。该方法能够很好的表现出收缩膜与被包裹物碰撞后的形态，体现了收缩膜模拟的真实性。同时，随着收缩膜向被包裹物逐渐逼近，越来越多的质点与其发生碰撞，而发生碰撞后的质点将被抽离出来并加以标记，不再占用系统模拟的计算资源。在某种程度上，该方法在保证模拟效果的同时，也提高了模拟系统的计算效率。43OPENMP使用在碰撞检测中，虽然建立了AABB层次树，剔除了大量不可能相交的对象，减少了线段和三角形求交的数目，但是由于质点规模较大，效率仍然不能达到实时性。随着计算机硬件的飞速发展，现在CPU已经进入了多核并行计算时代，因此本文尝试利用多核CPU来并行加速碰撞检测算法。如第二章所述，OPENMP的配置和使用都较为方便，只需在需要并行计算的源程序前添加PRAGMAOMP制导语句指明使用意图，编译器则可以自动将该段程序并行化处理。下文将结合本文部分算法，对其所用的几种制导语句和条件子句进行详细的介绍和分析。表41更新弹簧质点1FUNCTIONUPDATEPARTICLES2IFDEF_OPENMP3PRAGMAOMPPARALLELFORSCHEDULEDYNAMIC4ENDIF5FOREACHIIN0,|ROWNUM|1DO6FOREACHKIN0,|COLNUM|1DO7IFISCOLLIDEDWITHRIGIDOBJECTCONTINUE8INTEGRATE9COLLSIONQUERY10IFISCOLLIDEDWITHRIGIDOBJECTRESPONDCOLLISION11ELSESETPOSITIONNEWPOSITION表42计算弹簧质点系统物理属性1FUNCTIONCOMPUTESYSTEMPHYSICALATTRIBUTES2IFDEF_OPENMP3PRAGMAOMPPARALLELFORREDUCTIONAVGSPRINGLEN,NUM_THREADGETTHREADSNUMSPRINGSNUM,SCHEDULEDYNAMIC4ENDIF5FOREACHIIN0,|SPRINGSNUM|1DO6COMPUTERESTLENGTH7COMPUTEHOOKERCOFFYANGM