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

2024.12.23PCT/JP2023/0233542023.06.23WO2023/249111JA2023.12.28点为包含第一边的两端点且位于将第一边以主分割数等分的位置的多个(M+1)点，支线为穿过主分割点从第一边到第二边且沿着第三边的线分割数等分的多个(N+1)点，支线对为在支线中2获取部(S1)，构成为针对一个或者多个基本三角形获取包含三角形分割部(S2)，构成为将由上述顶点坐标组所包含的各顶点的支线对所夹着的上述基本三角形的区域以属于上述支线对的两个支线上的副分割点为顶上述主分割点为包含上述第一边的两端点且位于将上述第一边以上述主分割数等分上述支线为穿过上述主分割点从上述第一边到第二边且上述副分割点为包含上述支线的两端点且将上述支线以上述副分割数等分的多个(N+在上述基本三角形中，上述第一边为具有最大角度的内角的在指定属于一个上述细分割三角形的上述副分割点时，上述组主分割点识别设定部(S330)，构成为针对上述主分割点的每副分割点识别设定部(S545)，构成为通过上述主分割点识别编号和上述副分割点识别编号确定上述副分割上述组合信息基于上述主分割点识别编号和上述副分割识别编号来指定属于上述细上述执行部按照每个上述主分割点并行地计算上述细分割三3对象判定部(S120)，构成为针对由上述顶点坐标组定义的上述基本三角形的每一个，预整形执行部(S150)，构成为将判定为不是上述对象三角形的上述追加部(S155)，构成为生成包含分割后的上述三角形的顶点坐上述三角形分割部针对由上述预整形部生成的上述新的顶点坐标组所包含的各顶点上述对象判定部针对上述基本三角形的每一个，判定内角的最大值是否小于容许角在由上述对象判定部判定为上述基本三角形不是上述对象三角形执行部通过在上述基本三角形中将具有最大值的内角二等分的二等分线将上述基本三9.一种三角形生成方法，是构成为针对一个或者多针对在上述第一边上设定的多个主分割点的每个主分割点，设定针对上述主分割点的每一个，按照所设定的每个支线对，将基本三角形的区域以属于上述支线对的两个支线上的副分割点为顶点相互不重复地分割上述主分割点为包含上述第一边的两端点且位于将上述第一边以上述主分割数等分上述支线为穿过上述主分割点从上述第一边到第二边且上述副分割点为包含上述支线的两端点且将上述支线以上述副分割数等分的多个(N+4获取步骤(S1)，构成为针对一个或者多个基本三角形获取包含述支线对所夹着的上述基本三角形的区域以属于上述支线对的两个支线上的副分割点为上述主分割点为包含上述第一边的两端点且位于将上述第一边以上述主分割数等分上述支线为穿过上述主分割点从上述第一边到第二边且上述副分割点为包含上述支线的两端点且将上述支线以上述副分割数等分的多个(N+5[0002]本国际申请主张基于在2022年6月24日在日本专利局申请的日本专利申请第[0004]例如，在下述专利文献1中公开了与将三角形二等分为规定尺寸以下的细分相关[0007]在专利文献1所记载的方法中，反复执行从三角形的某个顶点朝向其对边引出分[0011]主分割数设定部构成为设定将第一边基于预先决定的分割长度等分为多个时的主分割数。副分割数设定部构成为针对在第一边上设定的多个主分割点的每个主分割点，6端点且位于将第一边以主分割数等分的位置的多个(M+1)点。支线为穿过主分割点从第一[0013]作为这样构成的本公开的一个技术方案的三角形生成装置通过基于分割长度来三角形中的3个边中的、沿着设定主分割点的第一边的边以及沿着设定副分割点的支线的[0015]作为这样构成的本公开的另一个技术方案的三角形生成方法为由作为本公开的[0016]本公开的又一技术方案是由作为本公开的一个技术方案的三角形生成装置执行7div_idx＝3指定的第一主线上点设定的支线对所夹着的区域进行分割的细分割三角形的[0045]图29是用于对在图20～图23中的由prim_id＝0～2指定的各基本三角形中的各参[0055]数据输入输出部14在与利用有线或者无线连接的外部设备之间进行数据的输入种功能是通过由运算装置20执行储存于非迁移实体记录介质的程序而实现的。在该例中，8的三角多边形(以下，也称为基本三角形)分别分割为比基本三角形小的多个三角形的程[0063]通过三角形生成处理而输出包含比基本三角形小的三角形的顶点坐标的新的顶[0065]使用图2的流程图对由运算装置20执行的三角形生成处理的顺序进行说明。例如在多边形顶点坐标数据中包含关于多个基本9形状的三角形整形为具有与正三角形的一致度相对大的形状的多个三角在本实施方式中，将具有相对接近正三角形的形状的基本三角形作为对象来执行多级分v43k+1vertices[3idx+1]、vertices[3idx+2]表示由idx指定的一个基本三角形的顶点坐标。0v2))中储存的顶点[0080]接着，在S115中，运算装置20针对由idx中储存的值指定的基本三角形，将数组vertices[]中的顶点坐标的储存顺序变更为对边的长度呈降序。即，将数组的元素[0082]首先，运算装置20基于各顶点坐标来计算顶点坐标v3k所表示的度、顶点坐标v3k+1所表示的顶点的对边b的长度、顶点坐标v3k+2所表示的顶点的对边c的长[0086]运算装置20使用余弦定理即c2＝a2+b2_2abcosθ,将θ计算为表示内角的最大值的对边是指三个顶点坐标中的开头即数组的元素vertices[3idx]中储存的顶点坐标所表示[0087]数组flag[idx]表示与由idx中储存的值指定的基本三角形相关的标志的值。此素flag[]的累积和。此处所说的数组的元素flag[]的累积和是指数组的元素flag[0]~[0092]在S140_S165中，运算装置20将在S120中判定为非对象三角形的基本三角形分割[0094]在S145中，运算装置20判定由idx中储存的值指定的基本三角形是对象三角形以置20判定为非对象三角形，并将处理转移到S150。另一方面，在储存为数组的元素flag[0095]在S150中，运算装置20通过表示最大值的内角的二等分线将由idx中储存的值指[0096]如上述那样，在由idx中储存的值指定的基本三角形中，数组的元素vertices顶点坐标(即，在图8中为v3k+1)、数组的元素vertices[3idx+1]中储存的顶点坐标(即，v3k+2的顶点坐标(即，在图8中为v3k+1)、数组的元素vertices[idx+2]中储存的顶点坐标(即，L_1加上数组的元素scan[idx]中储存的值而得的值储存于变量aidx。aidx＝(L_1)+scan点M的坐标分别储存为数组的元素vertices[3aidx]、vertices[3aidx+1]、vertices[3aidx+[0102]此外，运算装置20也可以使储存分割后的三角形的顶点坐标的数组与上述相0[0115]在S175中，运算装置20再次在基本三角形内将顶点重新排列为对边的长度呈降[0117]基于图11所示的流程图、以及图12～图14对运算装置20在S12中执行的多级分割的概况进行说明。图12～图14所示的三角形表示由上述的数组vertices[]所包含的顶点vertices[]所包含的顶点坐标定义的基本三角形分别具有与正三角形的一致度相对大的且是在基本三角形中具有最大角度的内角IA的对边。在由idx中储存的值指定的基本三角2]中储存的顶点坐标所表示的顶点的边相当于第一[0121]第二主线例如像图12所示的第二主线l1那样，是指在基本三角形中第二长的边，并且是在基本三角形中具有次于最大角度大的角度的内角的对边。在由idx中储存的值指定的基本三角形中，连接数组的元素vertices[3idx]中储存的顶点坐标所表示的顶点和vertices[3idx+2]中储存的顶点坐标所表示的顶点的边相且是在基本三角形中具有最小角度的内角的对边。在由idx中储存的值指定的基本三角形中储存的顶点坐标所表示的顶点的边相当于第三[0129]第一主线上点是位于将第一主线l0以主分割数等分的位置的多个[0131]支线为穿过第一主线上点且从第一主线l0到第二主线l1且沿着第三主线l2的线ml0～ml3按照针对上述的第一主线上点分别设定的每个支线对，计算细分割三角形的顶点的坐标。组合信息是指指定属于各细分割三角形的支线上点的组合所夹着的基本三角形的区域以属于支线对的两个支线上的支线上点为顶点相互不重复地准支线上的支线上点和邻接支线上的支线上点为顶点相互不重复地分割的一个以上的三[0140]在图13的例子中，对于作为第一主线上点的右顶点AR，针[0141]此外，在基本三角形中从远离基点AB的第一主线上点起依与邻接的支线ml2构成的支线对所夹着的区域相互不重复地分割的三角形为细分割三角基准支线ml3与邻接支线ml2所夹着的基本三角形的区域进行分割的细分割三角形的数量被[0146]上述的组合信息指定属于各细分割三角形的支线上点的组合方式。详细情况后的支线上点并且是在从第一主线观察时第一个支线上点。将第二个设为ml2上的支线上点并且是在从第一主线观察时第一个支线上点。将第三个设为ml3上的支线上点并且是在从支线上点的组合方式。从第一主线观察时第二个细分割三角形是指区域内识别编号＝1的个设为ml2上的支线上点并且是在从第一主线观察时第二上的支线上点并且是在从第一主线观察时第二个支线上点。将第二个设为ml2上的支线上点并且是在从第一主线观察时第二个支线上点。将第三个设为ml3上的支线上点并且是在为ml2上的支线上点并且是在从第一主线观察时第二个支线上点。将第二个设为ml3上的支线上点并且是在从第一主线观察时第三个支线上点。将第三个设为ml2上的支线上点并且分割。[0157]基于图15所示的流程图对在多级分割的S21中执行的主线上处理进行说明。在本[0160]数组prim_id[idx]为对于由数组vertices[]中储存的顶点坐标定义的基本三角处理后的数组vertices[]中储存的顶点坐标定义的基本三角形的数量储存于基本三角形R。[0168]运算装置20基于(2)式来计算第一主线上点数，并将计算出的值储存于数组maj_值，将使四舍五入后的值加上1而得的值计算为第一主线上点数。由于使用四舍五入后的0设为基本ID的基本三角形，将表示第一主线上点数的值储存为数组的元素maj_vert_num[0174]在接下来的S260中，运算装置20判定idx中储存的值是否是基本三角形数P以[0175]另一方面，在idx中储存的值小于基本三角形数P的情况下，运算装置20转移到来计算数组的元素maj_vert_num[idx]的总数，并将计算出的总数储存于csum_maj_vert_[0177]在idx中储存P_1时的数组的元素csum_maj_vert_num[P_1]相当于P个所有基本三数P＝3的例子进行说明。若如上述那样主线上处理的循环次数与储存于基本三角形数P的[0181]另外，通过执行S270，如图29所示，作为数组的元素csum_maj_vert_n[0184]基于图16所示的流程图对在多级分割的S22中执行的支线上处理进行说明。在本maj_line0[idx]、数组point_on_maj_line1[idx]、数组min_vert_num[idx]、数组prim_[0188]数组prim_lookup_idx[idx]为在支线上处理的执行中为了参照上述的三角形参m)指定的一个第一主线上点与包含该第一主线上点的基本三角形的基本ID(即，idx_p)建[0190]数组point_on_maj_line0[idx]对于由idx(即，idx_m)中储存的值指定的第一主上点是位于以与分割第一主线的分割比相同的分割比等分第[0195]首先，在S300中，运算装置20执行prim_lookup_idx数组生成处理，以生成数组[0198]在接下来的S402中，运算装置20将数组的元素maj_vert_num[idx]储存于变量rep_num。另外，运算装置20将数组的元素csum_maj_vert_num[idx]与数组的元素maj_vert_num[idx]的差储存于变则运算装置20以上结束本prim_lookup_i分割点识别编号。主分割点识别编号为在包含由idx指定的第一主线上点的基本三角形内从基点AB朝向右顶点AB增加的编号。运算装置20将计算出的主分割点识别编号储存于数组[0214]maj_div_idx[idx]＝idx_csum_maj_vert_num]lookup_idx+maj_vert_num[0215](3)式所示的lookup_idx相当于用于指定应参照的三角形参数数组的索引(即，[0217]第一主线上点的坐标是通过以maj_div_idx[idx]/maj_vert_num[idx]的比率对第一主线进行划分而计算的。第二主线上点的坐标同样是通过以maj_div_idx[idx]/maj_算装置20基于(9)式，以基点AB为基准来计算第二主线上点的坐标，并储存于数组point_[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_vert_num[idx]。基于数组的元素point_on_maj_line0[idx]、以及数组的元素point_on_的式(10)来计算数组的元素min_vert_num[i[0234]min_vert_num[idx]＝ceil((point_on_maj_line1[idx]_point_on_maj_line0作为数组的元素min_vert_num[针对该点设定的每个支线对，计算对支线对所夹着的区域进行分割的细分割三角形的数[0249]另一方面，在判定为idx中储存的值小于累积和Q的情况下，运算装置20转移到计算数组的元素prim_num_per_edge[idx]的总数，并将计算出的总数储存于数组csum_prim_num_per_edge[idx]。数组的元素prim_num_per_edge[idx]的总数是指数组的元素prim_num_per_edge[0]～prim_num_per_edge[0251]在idx中储存Q_1时的数组的元素csum_prim_num_per_edge[Q_1]相当于对针对Q个所有第一主线上点设定的支线对所夹着的区域进行分割的细分割三角形的总数R(以下，组的元素prim_lookup_idx[0]～p于对针对9个(即，Q＝9)第一主线上点设定的支线对所夹着的区域进行分割的细分割三角[0260]此外，以下，也将数组prim_lookup_idx[idx]、数组maj_div_idx[idx]、数组[0262]基于图18所示的流程图对在多级分割的S23中执行的细分割处理进行说明。在本下在细分割处理中使用的idx也记载为idx_idx_sub)指定的一个细分割三角形与识别对包含该细分割三角形的支线对进行设定的第别表示一个细分割三角形中的三个顶点坐标。此外，也可以与上述的数组vertices[]同存的值指定的细分割三角形是在对由包含该细分割三角形的支线对所夹着的区域进行分运算装置20将计算出的区域内识别编号储存于数组tess_prim_i[0279]tess_prim_idx＝idx_csum_prim_num_per_edge[lookup_idx]+prim_num_per_点的主分割点编号即maj_div_idx[idx]为基准，则支线上点的组合方式像_1→0→_1那样[0297]0,[0303]运算装置20基于(16)式，将两端点中的一个即第一主线上点的位置矢量(即，坐算装置20将计算出的副分割识别编号储存于变量min_div_idx。(18)式中的floor((tess_[0310]div_ratio＝min_div_idx/min_vert_num[lookup_idx+maj_div_offsee[idy]]…储存的值指定的支线上点对包含该点的支线进行[0321]若如上述那样循环次数为累积和R，则通过反复S515，从而储存数组的元素maj_中储存的值指定的细分割三角关设定包含由idx＝9指定的细分割三角形的支线对的第一主线上点的主分割点识别编号一主线上点的坐标确定为属于细分割三角形即第一主线上点设定的支线)的两端点。在S545中基于(18)式将副分割识别编号计算为1，标)储存于数组tess_vert[idy]得到包含合计R个细分割三角形的顶点坐标的数组tess_vert[id第一主线上设定的多个第一主线上点，分别设定对所设定的支线进行等分时的副分割数。[0337](1b)运算装置20在基本三角形中，将具有最大角度的内0)。割长度d0相当的两个边是指在分割支线对所夹着的区域的细分割三角形中与第一主线平相互不重复地分割支线对所夹着的基本三角割点识别编号和副分割点识别编号来指定属于对支线对所夹着的基本三角形的区域进行位移量和副分割点识别编号的位移量来指定属于细分割三角形的表示为相对于针对第一主线上点设定的支线上的支线上点所具有的主分割点识别编号的[0350](3)如上述那样运算装置20也可以生成组合信息。由于不需要将表示组合信息的多边形顶点坐标数据(即，数组vertices[])定义的基本三角形分别判定是否是对象三角形的基本三角形)分割为多个三角形，以成为与正三角形的一致度相对大的形状。在S155针对由在S11中生成的新的数组vertices[]所包含的各顶点的坐标定义的基本三角形中步分割基本三角形的区域的多个细分割三角形的顶点的坐[0352]这样的运算装置20能够对被整形为与正三角形的一致度相对大的预整形后的基算装置20在内角的最大值为容许角度以上的情况下，判定为基本三角形不是对象三角形。[0379]若累积和并行处理结束，则在数组input[idx]中储存数组input[idx]的累积存由idx＝0指定的数组的元素input[0]与由idx＝1指定的数组的元素input[1]的和。而[0385]在S640中，将数组的元素input[idx]与数组的元素input[idx_stride]的和储存[]。通过执行上述的累积和并行处理，而在[0407](4g)本公开所记载的运算装置20及其方法也可以通过构成被编程为执行由计算机程序具体化的一个至多个功能的处理器和存储器而被提供的专用计算机来实现。或者，本公开所记载的运算装置20及其方法也可以通过由一个以上的专用硬件逻辑电路构成处通过被编程为执行一个至多个功能的处理器和存储器与由一个以上的硬件逻辑电路构成[0408](4h)也可以通过多个构成元素实现上述实施方式的一个构成元素所具有的多个上述实施方式的结构附加或者置换上述实施方式的结构的[0409](4i)除了上述的运算装置20之外，还能够以将该运算装置20作为构成元素的装上述支线对所夹着的上述基本三角形的区域以属于上述支线对的两个支线上的副分割点[0419]上述主分割点为包含上述第一边的两端点且位于将上述第一边以上述主分割数[0421]上述副分割点为包含上述支线的两端点且将上述支线以上述副分割数等分的多具有次于上述最大角度大的角度的内角的对边，上述第三边为具有最小角度的内角的对[0433]通过上述主分割点识别编号和上述副分割点识别编号确定上述副分割点的每一[0434]上述组合信息基于上述主分割点识别编号和上述副分割识别编号来指定属于上[0445]上述三角形分割部针对由上述预整形部生成的上述新的顶点坐标组所包含的各预整形执行部通过在上述基本三角形中将具有最大值的内角二等分的二等分线将上述基上述基本三角形的区域以属于上述支线对的两个支线上的副分割点为