CN117115393B 一种基于gpu的nurbs曲面并行求交方法、设备及存储介质 （浙江大学）

本发明公开了一种基于GPU的NURBS曲面并环与奇点的定位使用GPU进行加速，在曲面采样采样点求解切向量和法向量；借助GPU对两个参数曲面分别进行自底向上构建BVH满四叉树，之后将GPU内存中的曲面BVH拷贝到CPU内存进行判交，进一步基于GPU构建曲面对应高斯球面的本发明方法在保证NURBS曲面求交结果稳定可靠的同时充分利用GPU并行计算能力加速求交，是2在曲面采样中，基于GPU对NURBS曲面进行采样赋值并对所有采借助GPU对两个参数曲面分别进行自底向上构建BVH满四叉树，之后将GPU内存中的曲绕数时，取参数曲面s上每一个需要计算卷绕数的小面片的四边的顺时针方向为积分路径于每条边上非端点处各点的值，均采用在这条边上的两个端点上的值以t为自变量的线性应一个采样点，负责计算给定度数时该采样点与每一个控制点分别关联后相应的B样条基35.根据权利要求1所述的基于GPU的NURBS曲面并盒的构建，并确定应当将求得的包围盒写入BVH数组中的哪一个位置，在计算完叶子节点6.根据权利要求1所述的基于GPU的NURBS曲面并行求交设备实现如权利要求1_6中任一所述的NURBS曲面行时实现如权利要求1_6中任一所述的NURBS曲面并4阶段对产品的高精度要求，而有理多项式参数化的几何建模形式又是CAD中最常用的精确分参数的、特殊形式的NURBS曲线/曲面，因此针对NURBS的算法研究往往可以平滑迁移到[0004]根据Sederberg等人的总结，曲面求交算法的研究通常基于细分法和跟踪法两种值法往往作为细分法和跟踪法的优化策略出现，被用作整个求交流程的辅助而非主干算牛顿迭代法在跟踪法前期进行起始点的定位，并使用细分应对牛顿迭代收敛不佳的情况，多分枝情况下分支相交时的交点(这点对鲁棒性的提升尤为重要)、引入了方向包围盒(OrientedBoundingBox，OBB)等[6]。Krishnan等人将NURBS曲面解构成Bezier面片的组5没有充分利用NURBS曲面的性质做针对性的优化，尽管Bezier曲面的赋值和跟踪计算量更较理想的速度在多种复杂的相交情形下保证算法的鲁棒性[11]。但这是一项针对一般曲面[0006]也有一些工作专门针对曲面求交中的跟踪这一子步骤提出了针对性的优化，例史永丰等人通过改进微分方程提高跟踪的鲁棒性，避免交线分支遗漏和跟踪跳线等问及相切的奇异情况缺少考虑[5]。Cheng等人首次提出了一种基于向量场法的同时检测环和曲面求交算法需要将输入的NURBS曲面划分成一个细密的网格，求值、构建层次包围体裁剪等。Guthe等人针对NURBS和T样条曲面提出了一种基于纹理的GPU上的曲面裁剪算法，[0010][1]PatrikalakisN，MaekawaT，KoK，etal.SurfacetoSurface6[0011][2]PieglL.OnNURBS：aSurvey[J].IEEEComputerGraphicsand[0012][3]SederbergTW，ChristiansenHN，KatzS.Improvedtestforclosed[0013][4]KrishnanS，ManochaD.Anefficientsurface[0014][5]SederbergTW，MeyersRJ.LoopdetectioninsurfacepatchNURBSmodelingoperationsontheGPU[J].IEEEtransactionsonvisualization[0017][8]PatrikalakisNM.Surface_to_surfaceintersections[J].IEEEComputer[0020][11]ParkY，SonSH，KimMS，etal.Surface–Surface_IntersectionComputationUsingaBoundingVolumeHierarchywithOsculatingToroidal[0023][14]史永丰，程婷[0024][15]ChengKP.UsingPlaneVectorFieldstoObtainAllthe[0025][16]KriezisGA，PatrikalakisNM，WolterFE.Topologicalanddifferential_equationmethodsforsurfaceintersections[J].Computer_Aided[0026][17]MaY，LeeYS.Detectionofloopsandsingularitiesofsurface71023.curvesandsurfacesontheGPU[C]//Proceedingsofthe2007ACMsymposiumonarbitrarydegreeNUR[0030][21]SchollmeyerA，B.DirecttrimmingofNURBSsurfacesonthe[0031][22]KrishnamurthyA，McMainsS，HannielI.GPU_acceleratedHausdorffdistancecomputationbetweendynamicdeformableNURBSsurfaces[J].Computer_[0032][23]HannielI，KrishnamurthyA，McMainsS.ComputingtheHausdorffdistancebetweenNURBSsurfacesusingnumericaliterationontheGPU[J]GPU却在过去的十多年里才正式成为一种通用计算设备，因此本发明调研阶段很少能找到[0034]针对现有技术的不足，本发明提出了一种基于GPU的NURBS曲面高鲁棒性求交方法，旨在保证NURBS曲面求交结果稳定可靠的同时充分利用现代GPU并行计算能力加速求[0037]3)本发明基于对NURBS定义和参数曲面BVH稳定结构的利用，加速了NURBS曲面在[0039]基于上述贡献1)_贡献4)，本发明给出了一个完整的基于GPU的NURBS曲面求交方8[0043]借助GPU对两个参数曲面分别进行自底向上构建BVH满四叉树，之后将GPU内存中于GPU上的向量场法计算向量场和卷绕数以判断是否存在关键点，进一步寻找高度可能存要组成一个父节点的每四个子节点，让处理这四个子节点的四个线程中的三个进入闲置，在子节点且体积更大的节点的四个子节点与另一个节点9的顺时针方向为积分路径γ,使用近似手段来简化和加速卷绕数计算，并对近似计算的结关于t的一般数值积分，采用中心差分近似的方式求得构成被积函数的部分变量在所述小所述设备实现上述任一种NURBS曲面并被处理器执行时实现上述任一种NURBS曲面[0066]图3为NURBS曲面的BVH(5层)根据参数域进行层次划分的示意图(a)，以及各层包[0068]图5为将计算卷绕数的环路积分根据沿着u或v的四条路径转化为关于t的分段数[0069]图6为使用递归细分进一步区分小环与切点的具体流程；图7为分辨率为32、64、[0083]其中ui是B样条节点向量(表示为vecknot)中的第i个元素，[0084]参数曲面的参数维度是2，每一组参数域内的两个参数u和v可以确定曲面上一点要计算NURBS曲线基函数的子程序被实现，赋值算法就可以在计算曲面坐标时从两个参数这样的采样形式使得后续高复用率的加速方式成为[0091]其中z是一个(p+1)×(n+p)大小的矩阵，该矩阵中的任一元素z(i,j)表示当得到的矩阵Z也完全不同。得到Z后，每个线程从果异步的写入m×m×3大小的数组E中，其每个元素E(i,j)表示在一个采样点的三维坐标。[0098]其中X表示NURBS对应的非有理B样条采样点的空间坐标，而w是(4)式中作为分母[0101]其中所有变量都是在赋值过程中已经求过的量，只不过N"的值被仅存储在N的[0104]采用如上算法做NURBS曲面的赋值和求解法向量，必须将参数曲面沿两个参数方[0106]层次包围体(BVH)是一种在光线追踪、曲面求交等领域被广泛应用的树状加速结位两个相交物体相交的位置。对于任何类型的BVH而言，父节点总是完全包围若干个子节[0107]任何时候，一个物体与BVH的父节点相交是该物体与该父节点的任意子节点相交的一个必要不充分条件，而对父节点进行判交总是比对其所有子节点计算判交代价更小，[0108]轴向包围盒(AABB)是一种在各类图形学任务上十分常用的包围盒，包围盒的长、[0109]在本发明的曲面求交算法中，层次包围体(BVH)采用轴向包围盒(AABB)作为包围两个曲面是否可能相交以及在哪些小面片上[0110]由于算法将曲面的BVH组织成了上述的四叉树形式，分辨率r被规定为2的整数指个顶点的包围盒被用于来近似小面片的包围盒，这些顶点的空间坐标已经在采样赋值求[0114]当构建完两个曲面的BVH，判交算法自顶向下递归地对两个BVH的节点进行判pairpair[0123]根据算法1和(11)式，用数组存放BVH，修改和读取树节点的时间复杂度为O(log它节点，取4个子节点所用的4个线程中的1个来进行该节点的计算，其余三个节点不起作[0131]由于BVH的判交采用递归实现，并且递归的路径不能提前预测，所以判交无法用区域内有平行的法向量，这一结论在一些工作中被用来判定环的存在。事实上，当两个[0144]关键点的检测可以使用基于卷绕数(rotationnumber)的算法完成。将D(u,v)参数域上的任意一条环路的顺时针路线表示为γ,为方便表示，记则卷绕数R(γ)可以表示为：v)空间距离最近的点F(u,v)。由于曲面BVH构建与判交算法已经计算出与u和v所在盒子有χψ[0153]在本发明的算法中，取曲面s上每一个需要计算卷绕数的小面片的四边的顺时针t为自变量的线性插值。基于此，每一段关于t的数值积分的被积函数都是关于t的一次函[0164]由于向量场的参数域及参数域划分和曲面s完全相同，算法分配用以计算卷绕数的GPU线程数等于s中疑似有小环或切点的盒子(曲面BVH和高斯球面BVH排除后剩余的盒一个程序段中，对于每个小面片的四个顶点，GPU线程需要计算顶点位置的F(u,v)和VO(U,0.第二个程序段负责计算每个小方片的卷绕数，并将卷绕数是否为0的信息写在一块GPU全局内存中与该小方片对应的位置上。[0166]本发明工作的重点在对跟踪前期的BVH构建、拓扑判定算法进行优化和用GPU加拟合，由于本发明使用的添加正则项的最小二求交全流程的具体方法。下面简单介绍本发明的工作中最后用以求解交线和切点的CPU方较小的跟踪算法找到足够多的小环上的交点。如果直到细分的精度小于了算法给定的误定会与两个曲面的边界都产生至少一个交点，通过二者BVH判交筛选出的小盒子对可以指出一个交线分支具体与哪些曲面边界相交。曲面边界相当于将NURBS曲面的参数u或者v替关注正则相交和切向相交两类情形，它将交线分别视作两个NURBS参数曲面上各自的一条参数曲线，从而将交线在跟踪点的切向量与两个曲面在该点处的切向量和法向量相关联，集的、足以拟合出交线的一个点序列。算法的最后用B样条曲线的形式来拟合出每一条交真实值之差的平方和，通过寻找使得损失函数导数为0的那一组控制点坐标来拟合目标函散点数量相等，节点向量设置为clamped类型(即首个节点和末尾节点都有pc+1的重复度，信息对应的指向GPU内存的指针变量，为这些变量分配所需的GPU内存(使用cudaMalloc)，根据自己x方向上的线程编号找到对应的采样点在u方向上的位置，同时根据自己y方向上每个元素表示一个节点。CPU程序在根据上述线程层次创建的核函数中将GPU内存中的BVH包围盒的构建，核函数通过调用算法1描述的计算相对下标的方法确定应当将求得的包围否则总是让存在子节点且体积更大的节点的四个子节点与另一个[0182]小环与奇点的定位模块，高斯球面的BVH的构建与判交与NURBS曲面BVH的构建与映射保留的盒子对信息拷贝到GPU内存中，连同曲面采样信息一同传递给核函数。每一个GPU线程与一个盒子对相对应，该线程首先计算第一个曲面上四个对应小采样点的有向距[0184]本发明通过4组对比实验验证前文所提出的基于GPU的NURBS曲面求交方法在赋[0188](3)OpenNURBS。OpenNURBS是一款由RobertMcNeel&Associate