CN119422173A 三角形生成装置、三角形生成方法、以及三角形生成程序 （株式会社电装）

2024.12.20PCT/JP2023/0233602023.06.23WO2023/249113JA2023.12.28部针对由顶点坐标组定义的基本三角形分别判定是否是具有与正三角形的一致度相对较大的添加部生成包含分割后的三角形的顶点坐标的顶点坐标组中包含的各顶点的坐标定义的基本为比基本三角形小的多个细分割三角形的顶点2获取部(S1)，构成为针对一个或者多个基本三角形，获取包含三角形分割部(S2)，构成为将由上述顶点坐标组中包含的各顶点的对象判定部(S120)，构成为针对由上述顶点坐标组定义的上述基本三角预先整形执行部(S150)，构成为将判定为不是上述对象三角形的上述基本添加部(S155)，构成为生成包含分割后的上述三角形的顶点坐针对由通过上述添加部生成的上述新的顶点坐标组中包含的各顶点的坐标定义的基上述对象判定部针对上述基本三角形分别判定内角的最大值是上述内角的最大值为上述允许角度以上的情况下判断为上述基本三角形不是上述对象三在由上述对象判定部判定为上述基本三角形不是上述对象三整形执行部通过将在上述基本三角形中具有最大值的内角平分的平分线来将上述基本三上述主分割点是包含上述第一边的两端点，并处于将上述第一边3上述副分割点是包含上述支线的两端点，并将上述支线以上述上述支线对是在上述支线中相邻的任意的两上述三角形分割部针对由通过上述添加部生成的上述新的顶点坐标组中包含的各顶割为比上述基本三角形小的多个上述细分割三在上述基本三角形中，上述第一边是具有最大角度的内角的大小仅次于上述最大角度的角度的内角的对边，上述第三边是具有最小角度的内角的对上述组合信息在指定属于一个上述细分割三角形的上述副分割点主分割点识别设定部(S330)，构成为对上述主分割点分别设定识副分割点识别设定部(S545)，构成为对上通过上述主分割点识别编号和上述副分割点识别编号确定上述副分割上述组合信息基于上述主分割点识别编号和上述副分割识别编号指定属于上述细分上述执行部按每个上述主分割点并行地计算上述细分割三9.一种三角形生成方法，是构成为针对一个或者多针对由上述顶点坐标组定义的上述基本三角形分别判定是否是具有与正三角形的一将判定为不是上述对象三角形的上述基本三角形分割为多个三针对由上述新的顶点坐标组中包含的各顶点的坐标定义的基10.一种三角形生成程序，是使计算机作为三角形生成装置发挥功能的三角形生成程构成为针对一个或者多个基本三角形，获取包含各顶点4构成为将由上述顶点坐标组中包含的各顶点的坐标定义的上述基本三角形的每一个针对由上述顶点坐标组定义的上述基本三角形分别判定是否是具有与正三角形的一构成为将判定为不是上述对象三角形的上述基本三角构成为生成包含分割后的上述三角形的顶点坐标的新的上述顶点坐标组的添加步骤针对由通过上述添加步骤生成的上述新的顶点坐标组中包含的各顶点的坐标定义的5[0002]本国际申请主张基于2022年6月24日向日本专利厅申请的日本专利申请第2022-基于分割后的三角形来更详细地平滑表现三维[0011]对象判定部构成为针对由顶点坐标组定义的基本三角形分别判定是否是具有与象三角形的基本三角形分割为多个三角形，以便成为与正三角形的一致度相对较大的形[0012]三角形分割部针对由通过添加部生成的新的顶点坐标组中包含的各顶点的坐标6的顶点坐标组中包含的各顶点的坐标定义的基本三角形通过预先整形执行部的执行而具[0014]本公开的另一方式是构成为针对一个或者多个基本三角形获取包含各顶点的坐[0015]这样构成的作为本公开的另一方式的三角形生成方法是由作为本公开的一方式7[0042]图26是表示在图20～图23中的由primid＝0指定的基本三角形中，分割针对由majdividx＝3指定的第一主线上点设定的支线对所夹的区域的细分割三角形的说明[0053]操作输入部12输出用于确定用户经由未图示的键盘以及鼠标进行的输入操作的[0055]数据输入输出部14在与通过有线或者无线连接的外部设备之间进行数据的输入[0058]模拟程序25是用于在虚拟空间上再现道路的三维形状以及道路周边的三维形状8[0063]通过三角形生成处理输出包含比基本三角形小的三角形的顶点坐标的新的顶点在多边形顶点坐标数据中包含针对多个基本角形包含执行计算三角形的顶点坐标的计算，并将计算出的顶点坐标输出(即，存储)至9小的形状的的三角形整形为具有与正三角形的一致度相对较大的形状的多个三角形的处v2))中储存的顶点坐标为三角形的顶点的基本三角形。[0077]运算装置20在S110－S130中，从由idx中储存的值指定的基本三角形中确定不是[0079]接着在S115中，运算装置20针对由idx中储存的值指定的基本三角形，变更数组vertices[]中的顶点坐标的储存顺序，使得对边的长度呈降序。即，将数组的要素组的各要素。即，设为数组的要素vertices[3k]中储存的顶点坐标是V3k，数组的要素vertices[3k+1]中储存的顶点坐标是[0083]接着在S120中，运算装置20判定由idx中储存的值指定的基本三角形是否是上述[0085]运算装置20使用余弦定理亦即c的对边是作为三个顶点坐标中的开头的数组的要素vertices[3idx]中储存的顶点坐标所[0086]数组flag[idx]表示与由idx中储存的值指定的基本三角形相关的标志的值。这为L以上的情况下使处理移至S135。另一方面，运算装置20在判定为低于L的情况下移至[0093]在S145中，运算装置20判定由idx中储存的值指定的基本三角形是对象三角形和[0094]在S150中，运算装置20通过表示最大值的内角的平分线将由idx中储存的值指定的基本三角形分割为两个，使得分割后的三角形成为与正三角形的一致度相对较大的形[0095]如上述那样，在由idx中储存的值指定的基本三角形中，数组的要素vertices点M[0099]另一方面，运算装置20将分割出的三角形中的数组的要素vertices[idx]中储存L－1加上数组的要素scan[idx]中储存的值后的值储存于变量aidx。aidx＝(L－1)+scan[idx]。然后，将aidx设为作为idx而指定的基本三角形的顶点，将数组的要素vertices[3idx]中储存的顶点坐标(即，v3k+1)、数组的要素vertices[3idx+2]中储存的顶点坐标3k)、点M的坐标分别储存为数组的要素vertices[3aidx]、vertices[3aidx+1]、v3k0点M5为顶点坐标的三角形。在变量aidx中储存9(即，表示L－1的值)加上作为数组的要素的概要进行说明。图12～图14所示的三角形表示由上述的数组vertices[]中包含的顶点组vertices[]中包含的顶点坐标定义的基本三角形分别具有与正三角形的一致度相对较[0119]所谓第一主线例如是如图12所示的第一主线l0那样，在基本三角形中最长的边，是在基本三角形中具有最大角度的内角IA的对边。在由idx中储存的值指定的基本三角形中储存的顶点坐标所示的顶点连接的边相当[0120]所谓第二主线例如是如图12所示的第二主线l1那样，在基本三角形中第二长的指定的基本三角形中，将数组的要素vertices[3idx]中储存的顶点坐标所示的顶点、与vertices[3idx+2]中储存的顶点坐标所示的顶点连接的边相当于第[0121]所谓第三主线例如是如图12所示的第二主线l1那样，在基本三角形中最短的边，的顶点坐标所示的顶点连接的边相当于第三[0128]第一主线上点是处于将第一主线l0以主分割数等分的位置的多个[0130]支线是经过第一主线上点从第一主线l0到达第二主线l1，并沿着第三主线l2的线[0131]在图13的例子中，基本三角形具有针对四个第一主线上点分别设定的四个支线0～ml30[0139]在图13的例子中，关于作为第一主线上点的右顶点AR，针ml3[0140]此外，在基本三角形中从离基点AB较远的第一主线上点起按顺支线对的本实施方式中，针对作为第一主线上点的基点AB设定的支线不被设定为基准支[0142]例如，关于上述的作为第一主线上点的右顶点AR，将由针ml3与相邻的支线ml2构成的支线对所夹的区域相互不重复地分割的三角形是细分割三角的基准支线ml3与相邻支线ml2所夹的基本三角形的区域的细分割三角形的数量计算如图13所示，分割针对右顶点AR设定的基准支线ml3与相邻支线ml2所夹的区域的细分割三第一个的细分割三角形是指区域内识别编号＝0的细分割三角形。即，将第一个设为作为ml3上的支线上点且从第一主线起观察第一个的支线上点。将第二个设为作为ml2上的支线上点且从第一主线起观察第一个的支线上点。将第三个设为作为ml3上的支线上点且从第线上点的组合方式。从第一主线起观察第二个细分割三角形是指区域内识别编号＝1的细为作为ml2上的支线上点且从第一主线起观察第三个细分割三角形是指区域内识别编号＝2的细分割三角形。即，将第一个设为作为ml3上的支线上点且从第一主线起观察第二个支线上点。将第二个设为作为ml2上的支线上点且从第一主线起观察第二个支线上点。将第三个设为作为ml3上的支线上点且从第一主作为ml2上的支线上点且从第一主线起观察第二个支线上点。将第二个设为作为ml3上的支线上点且从第一主线起观察第三个支线上点。将第三个设为作为ml2上的支线上点且从第理后的数组vertices[]中储存的顶点坐标定义的基本三角形的数量储存于基本三角形数[0167]运算装置20基于(2)式计算第一主线上点数，并将计算出的值储存于数组maj以分割长度d0后的值，并设为将计算出的值取整为计算出的值以上的最接近的整数后的主线上点的间隔是相当于分割长度d0的长度。相当于分割长度d0的长度也可以不是严格与的0为基本ID的基本三角形，表示第一主线上点数的值被储存为数组的要素majvert[0174]在接下来的S260中，运算装置20判定idx中储存的值是否为基本三角形数P以[0176]在S270中，运算装置20例如也可以使idx在0≦idx≦P－1的范围内以1为单位变化，来计算数组的要素majvertnum[idx]的总数，并将计算出的总数储存于csummajvertnum[idx]。数组的要素majvertnum[idx]的总数是指数组的要素majvertnum[0]～majvertnum[idx]的总[0177]在idx储存有P－1时的数组的要素csummajvertnum[P－1]相当于全部P个数P＝3的例子进行说明。当设为如上述那样主线上处理的循环次数等于基本三角形数P中vertnum[P－1](例如，P＝3)而储存的值亦即10被计算为全部的基本三角形中的第一主[0185]输出数组是数组primlookupidx[idx]、数组majdividx[idx]、数组[0188]数组primlookupidx[idx]是在支线上处理的执行中为了参照上述的三角形参数数组而使用的所谓检查表。换句话说，数组primlookupidx[idx]是用于将由idx(即，idxm)指定的一个第一主线上点、与包含该第一主线上点的基本三角形的基本ID[0189]数组majdividx储存的值指定的第一主线上点，储存与该第一主线上点对应的第二主线上点的位置矢量。第二主线上点是处于将第二主线以与分割第一主线的分割比相同的分割比等分的位置的的整数。数组的要素minvertnum[]表示为正整数。数组的要素pointonmaj[0195]首先，在S300中，运算装置20为了生成数组primlookupidx[idx]而执行[0198]在接下来的S402中，运算装置20将数组的要素majvertnum[idx]储存于变量repnum。另外，运算装置20将数组的要素csummajvertnum[idx]与数组的要素majvertnum[idx]的差储存于变量ofsi[0199]接着在S403中，运算装置20判定repnum中储存的值是否比0大。运算装置20在[0203]接着在S407中，运算装置20判定变量m中储存的值是否为repnum中储存的值以算装置20至此结束本primlookupidx数[0211]首先在S330中，运算装置20针对由idx中储存的值指定的第一主线上点计算主分割点识别编号。主分割点识别编号在是包含由idx指定的第一主线上点的基本三角形内对AB朝向右顶点AB增加的编号。运算装置20将计算出的主分割点识别编号储存于数组maj__[0214]maj_div_idx[idx]＝idx_csum_maj_vert_num[lookup_idx]+maj_vert_num[0215](3)式所示的lookupidx相当于用于指定应当参照的三角形参数数组的索引[0216]接着在S340中，运算装置20针对由idx中储存的值指定的第一主线上点计算位置第一主线上点对应的第二主线上点计算位置矢量，并储存于数组pointonmajline1[0217]通过将第一主线以majdividx[idx]/majvertnum[idx]的比率划分来计上点是基点AB的情况下，第一主线上点的坐标和与该坐标对应的第二主线上点的坐标一[0222]接着，运算装置20基于(6)式、(7)式，计算作为最长的边的第一主线的边矢量地，运算装置20基于(9)式，以基点AB为基准计算第二主线上点的坐标，并储存于数组[0228]point_on_maj_line0[idx]＝org+((float)maj_div_idx/(float)(maj_vert_[0230]point_on_maj_line1[idx]＝org+((float)maj_div_idx/(float)(maj_vert_针对该点设定的支线上的支线上点数。运算装置20将计算出的支线上点数储存于数组minvertnum[idx]。基于数组的要素pointonmajline0[idx]、以及数组的要素[0235]min_vert_num[idx]＝ceil((point_on_maj_line1[idx]_point_on_maj_line0线上点中的数组的要素maj＿dev＿idx[idx]为0的第一主线上点相当于基点AB。针对基点将计算出的数量储存于数组primnumperedg将成对的两个支线中的针对maj＿div＿idx较大的第一主线上点设定的支线设为基准支形的顶点的数量是基准支线上点和相邻支线上点的合计值。当留意在idx中储存0的情况[0251]在S390中，运算装置20例如也可以使idx在0≦idx≦Q－1的范围内以1为单位变数组的要素primnumperedge[0]～primn[0252]在idx储存有Q－1时的数组的要素csumprimnumperedge[Q－1]相当于分割针对全部Q个第一主线上点设定的支线对所夹的区域的细分割三角形的总数R(以下，也即，针对第一主线上点分别储存参照三角形参数数组时的索引(即，基本AB为0按顺序对第一主线上点分别设定主分割点识[0256]另外，通过S340的重复，从而如图29所示，作为数组的要素pointonmaj[0260]在图20～图22的例子中，作为数组的要素csumma亦即17相当于分割针对9个(即，Q＝9)第一主线上点设定的支线对所夹的区域的细分割三细分割处理中使用的idx以下也记载为id[0266]数组majlinelookupidx[idx]是在细分割处理的执行中为了参照上述的主线参数数组而使用的检查表。换句话说，数组majlinelookupidx[idx]是用于将由[0267]数组tessvert[idx]针对由idx(即，idxsub)中储存的值指定的细分割三角中的累积和Q而使用累积和R，代替数组majvertnum[]而使用primnumperedge存的值指定的细分割三角形是包含该细分割三角形的分割支线对所夹的区域的细分割三置20将计算出的区域内识别编号储存于数组tessprim[0280]tess_prim_idx＝idx_csum_prim_num_per_edge[lookup_idx]+prim_num_per_识别编号指定属于确定出的细分割三角形的支线上点的组合方式的信息。在本实施方式第一主线上点的主分割点编号的majdividx[idx]为基准时，如0→-1→0那样以主分设定支线对的第一主线上点的主分割点编号的majdividx[idx]为基准时，如－1→0→-1那样以主分割点识别编号的位移量表示支线上点的组合方式。对支线上点的组合方式而言，针对区域内识别编号＝1的细分割三角形，如－1→0→0(例分割识别编号＝2)那样，以副分割点识别编号相对于基准副分割识别编号的位移量来表[0303]接着在S540中，运算装置20针对属于由idx中储存的值指定的细分割三角形的支[0307]point_1＝po置20将计算出的副分割识别编号储存于变量mindividx。(18)式中的floor((tess[0311]div_ratio＝min_div_idx/min_vert_num[lookup_idx+maj_div_offset[idy]]…[0312]内分比表示属于由idx中储存的值指定的细分割三角形的支线上点中的由idy中[0313]接着在S550中，运算装置20将基于(20)式计算出的坐标储存于数组tessvert[0322]当如上述那样设为循环次数是累积和R时，通过S515的重复，储存数组的要素说明。如图22所示，由idx＝9指定的细分割三角形包含于由primid＝1指定的基本三角设定包含由idx＝9指定的细分割三角形的支线对的第一主线上点的主分割点识别编号[0325]在S520中，针对由idx＝9指定的细分割三角形，区域内识别编号(即，tessprimid[9])基于(13)式而被计算第二主线上点的坐标被确定为属于细分割三角[0331]运算装置20针对由idx＝0～R－1指定的细分割三角形执行相同的处理。作为结区域分割得比基本三角形小的多个细分割三角形算装置20在内角的最大值为允许角度以上的情况下，判定为基本三角形不是对象三角形为60°≦最大内角＜90°,能够使分割后的三角形接近与正三角形的一致度相对较大的形将支线对所夹的基本三角形的区域的相互不重复地分割的一[0344](1f)运算装置20在基本三角形中，将具有最大角度的内0)。[0345]这样的运算装置20能够使细分割三角形中的三个边中的沿着设定第二主线上点支线上的支线上点(即，基准支线上点)、和与该基准支线上点相邻的支线上的支线上点准支线上点后接着指定相邻支线上点、以及在指定相邻支线上点后接着指定基准支线上[0348]运算装置20通过在支线对中使两个支线交替移动并指定割长度d0的两个边是指在分割支线对所夹的区域的细分割三角形中，与第一主线平行的基于主分割点识别编号和副分割点识别编号来指定属于分割支线对所夹的基本三角形的位移量和副分割点识别编号的位移量来指定属于细分割三角形的表示为相对于针对第一主线上点设定的支线上的支线上点所具有的主分割点识别编号的S140～S165是每个idx的重复处理，因此GPU22也可以在S140～S165中，按每个idx设置线由idx＝0指定的数组的要素input[0]与由idx＝1指定的数组的要素input[1]的和。然后，在数组input[S－1]中储存数组的要素input[0]～数组的要素input[S[0391]在S680中，使stride递增。即，GPU22将stride中储存的值加上1后的值储存于的累积和并行处理，从而在数组的要素flag[L－1]中储存数组的要素flag[idx]的总和[0397]另外，例如，也可以在S390中，将上述的数组input[]置换为数组primnumperedge[]。通过执行上述的累积和并行处理，从而在数组的要素majvertnum[Q-将组合信息作为表格存储于存储器，并基于存储于存储器的组合信息来生成细分割三角形的顶点且是第一主线与第二主线的交点的右顶点AR起朝向基点AB按顺序设定主分割点识算机通过构成被编程为执行由计算机程序具体化的一个至多个功能的处理器以及存储器执行一个至多个功能的处理器以及存储器与由一个以上的硬件逻辑电路构成的处理器的[0410](4h)也可以通过多个构成要素实现上述实施方式的一个构成要素所具有的多个其他的上述实施方式的结构附加或者置换上述实施方式的结构[0411](4i)除了上述的运算装置20以外，也可以以将该运算装置20设为构成要素的装[0421]针对由通过上述添加部生成的上述新的顶点坐标组中包含的各顶点的坐标定义[0424]上述对象判定部针对上述基本三角形分别判定内角的最在上述内角的最大值低于上述允许角度的情况下判断为上述基本三角形是上述对象三角预先整形执行部通过将在上述基本三角形中具有最大值的内角平分的平分线来将上述基[0438]上述三角形分割部针对由通过上述添加部生成的上述新的顶点坐标组中包含的各顶点的坐标定义的基本三角形的每一个，通过上述主分割数设定部设定上述主分割数，域分割为比上述基本三角形小的多个上述细分割三角形的[0449]通过上述主分割点识别编号和上述副分割点识别编号确定上述副分割点的每一[0450]上述组合信息基于上述主分割点识别编号和上述副分割识别编号指定属于上