CN121925683A - 解码方法、编码方法及解码装置 - Google Patents

Abstract

解码方法对多个三维点进行解码，使用第1三角形集合三角形的2个三角形集合顶点，计算将2个三角形集合顶点连结的边上的第1点的位置（S301），使第1点的位置在第1方向上偏移（S302），并使用具有偏移后的位置的第1点生成第2三角形集合三角形（S303），第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点，节点是包括多个三维点的八叉树结构内的单位。

Description

解码方法、编码方法及解码装置

技术领域

本公开涉及解码方法、编码方法、解码装置及编码装置。

背景技术

在用于汽车或者机器人自主动作的计算机视觉、地图信息、监视、基础设施查点或者影像分发等广泛的领域中，有效利用三维数据的装置或者服务预计在今后得到普及。通过测距仪等距离传感器、立体相机或者多个单目相机的组合等各种方法来取得三维数据。

作为三维数据的表现方法之一，有通过三维空间内的点群来表现三维构造的形状的被称为点云的表现方法。在点云中，存放有点群的位置和颜色。点云虽然预想会成为三维数据的表现方法的主流，但点群的数据量非常大。因此，在三维数据的积蓄或者传送中，与二维的动态图像（作为一例有通过MPEG进行了标准化的MPEG-4 AVC或者HEVC等）同样，需要通过编码对数据量进行压缩。

另外，关于点云的压缩，通过进行与点云关联的处理的公开库（点云库（PointCloud Library））等提供了部分的支持。

另外，已知使用三维的地图数据对位于车辆周边的设施进行检索并显示的技术（例如参照专利文献1）。

在先技术文献

专利文献

专利文献1：国际公布第2014/020663号

发明内容

发明所要解决的课题

在这样的三维数据的编码及解码中，期望能够提高被复原的三维数据的精度。

本公开的目的在于，提供能够提高被复原的三维数据的精度的解码方法、编码方法、解码装置或者编码装置。

用于解决课题的手段

本公开的一个方式所涉及的解码方法对多个三维点进行解码，使用第1三角形集合三角形的2个三角形集合顶点，计算将所述2个三角形集合顶点连结的边上的第1点的位置，使所述第1点的所述位置在第1方向上偏移，使用具有偏移后的所述位置的所述第1点生成第2三角形集合三角形，所述第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点，所述节点是包括所述多个三维点的八叉树结构内的单位。

本公开的一个方式所涉及的编码方法对多个三维点进行编码，使用第1三角形集合三角形的2个三角形集合顶点，计算将所述2个三角形集合顶点连结的边上的第1点的位置，使所述第1点的所述位置在第1方向上偏移，使用具有偏移后的所述位置的所述第1点生成第2三角形集合三角形，所述第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点，所述节点是包括所述多个三维点的八叉树结构内的单位。

发明效果

本公开能够提供能够提高被复原的三维数据的精度的解码方法、编码方法、解码装置或者编码装置。

附图说明

图1是表示实施方式所涉及的原始点群的例子的图。

图2是表示实施方式所涉及的剪枝八叉树的例子的图。

图3是表示实施方式所涉及的对叶节点进行二维显示的例子的图。

图4是用于说明实施方式所涉及的质心顶点的生成方法的图。

图5是用于说明实施方式所涉及的质心顶点的生成方法的图。

图6是表示实施方式所涉及的顶点信息的例子的图。

图7是表示实施方式所涉及的三角形集合面的例子的图。

图8是用于说明实施方式所涉及的点群的复原处理的图。

图9是表示实施方式所涉及的点群的例子的图。

图10是表示实施方式所涉及的质心顶点的生成例的图。

图11是实施方式所涉及的三角形（三角形集合面）的生成例的图。

图12是表示实施方式所涉及的面顶点的生成例的图。

图13是表示实施方式所涉及的各种顶点和三角形的例子的图。

图14是表示实施方式所涉及的插值顶点的例子的图。

图15是表示实施方式所涉及的插值顶点的例子的图。

图16是实施方式所涉及的解码处理的流程图。

图17是实施方式所涉及的三角形及点的生成处理的流程图。

图18是实施方式所涉及的编码处理的流程图。

图19是表示实施方式所涉及的GDUH及GDU的句法例的图。

图20是表示实施方式所涉及的GDUH及GDU的句法例的图。

图21是表示实施方式所涉及的各种顶点和三角形的例子的图。

图22是表示实施方式所涉及的进行了调整处理的情况下的各种顶点和三角形的例子的图。

图23是实施方式所涉及的解码处理的流程图。

图24是实施方式所涉及的解码装置的框图。

图25是实施方式所涉及的编码处理的流程图。

图26是实施方式所涉及的编码装置的框图。

具体实施方式

本公开的一个方式所涉及的解码方法对多个三维点进行解码，使用第1三角形集合三角形的2个三角形集合顶点，计算将所述2个三角形集合顶点连结的边上的第1点的位置，使所述第1点的所述位置在第1方向上偏移，使用具有偏移后的所述位置的所述第1点生成第2三角形集合三角形，所述第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点，所述节点是包括所述多个三维点的八叉树结构内的单位。

由此，该解码方法除了三角形集合顶点之外，还在第1三角形集合三角形的边上生成第1点，并使用第1点生成第2三角形集合三角形。由此，能够提高被复原的三维数据的精度。进而，该解码方法通过使第1点的位置偏移，存在能够进一步提高三维数据的精度的可能性。在此，精度是表示以何种程度复原了原始点群的形状的指标，其越高则表示越好地复原了原始点群。也就是说，如该解码方法那样，通过使用被追加的第1点生成第2三角形集合三角形，能够实现更精细的表现，因此精度提高。

例如，所述第1方向也可以是所述第1点的所述位置从所述节点的多个边缘顶点的重心偏离的方向。由此，该解码方法能够高精度地复原向从多个边缘顶点的重心偏离的方向凸的原始点群的形状。

例如，所述第1方向也可以是从所述节点的多个边缘顶点的重心朝向所述节点的质心顶点的方向。由此，该解码方法能够提高质心顶点的周边的复原精度。

例如，所述第1方向也可以是所述第1点的所述位置从所述节点的多个边缘顶点的重心偏离的方向，而且是沿着所述第1三角形集合三角形的法线的方向。由此，该解码方法能够复原更接近于原三维数据的形状的三维数据。

例如，在所述多个边缘顶点的所述重心与所述节点的质心顶点之间的距离越大时，在所述第1点的所述位置的偏移中应用的偏移量也可以越大。由此，该解码方法能够复原更接近于原三维数据的形状的三维数据。

例如，在所述第1点的所述位置的偏移中应用的偏移量也可以通过用所述多个边缘顶点的所述重心与所述节点的质心顶点之间的距离乘以系数来计算，所述系数也可以大于0且小于1/8。在系数过大的情况下，容易发生校正后的位置位于节点的外侧的错误。相对于此，通过使用小于1/8的值作为系数，能够抑制这样的错误的发生。

例如也可以是，在所述节点的尺寸比阈值大的情况下，进行所述第1点的所述位置的计算、所述第1点的所述位置的偏移及所述第2三角形集合三角形的生成，在所述节点的所述尺寸比所述阈值小的情况下，不进行所述第1点的所述位置的计算、所述第1点的所述位置的偏移及所述第2三角形集合三角形的生成。在节点的尺寸大的情况下，被复原的三维数据的精度降低的可能性高。在这样的情况下，通过进行第1点的位置的计算、第1点的位置的偏移及第2三角形集合三角形的生成，能够有效地提高三维数据的精度。

例如，所述第1点也可以是所述边的中点。由此，该解码方法通过在边的中点的位置上生成第1点，能够有效地提高三维数据的精度。

例如，所述2个三角形集合顶点也可以包括被生成在除了所述节点的边之外的所述节点的面上的面顶点。由此，该解码方法能够提高通过使用面顶点而复原的三维数据的精度。

例如也可以是，所述第1三角形集合三角形的3个三角形集合顶点各自是边缘顶点、质心顶点、以及除了所述节点的边之外的所述节点的面所提供的面顶点中的某一个，在所述2个三角形集合顶点的组不是所述面顶点与所述质心顶点的组的情况下，所述第1点的所述位置被偏移，在所述2个三角形集合顶点的组是所述面顶点与所述质心顶点的组的情况下，所述第1点的所述位置不被偏移。

在2个三角形集合顶点的组是面顶点和质心顶点的情况下，通过使第1点的位置偏移而复原的三维数据的形状有可能偏离原三维数据的形状。由此，通过在这样的情况下不进行偏移，能够提高被复原的三维数据的精度。

本公开的一个方式所涉及的编码方法对多个三维点进行编码，使用第1三角形集合三角形的2个三角形集合顶点，计算将所述2个三角形集合顶点连结的边上的第1点的位置，使所述第1点的所述位置在第1方向上偏移，使用具有偏移后的所述位置的所述第1点生成第2三角形集合三角形，所述第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点，所述节点是包括所述多个三维点的八叉树结构内的单位。

由此，该编码方法除了三角形集合顶点之外，还在第1三角形集合三角形的边上生成第1点，并使用第1点生成第2三角形集合三角形。由此，能够提高被复原的三维数据的精度。进而，该编码方法通过使第1点的位置偏移，存在能够进一步提高三维数据的精度的可能性。

另外，本公开的一个方式所涉及的解码装置对多个三维点进行解码，具备处理器和存储器，所述处理器使用所述存储器，使用第1三角形集合三角形的2个三角形集合顶点，计算将所述2个三角形集合顶点连结的边上的第1点的位置，使所述第1点的所述位置在第1方向上偏移，使用具有偏移后的所述位置的所述第1点生成第2三角形集合三角形，所述第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点，所述节点是包括所述多个三维点的八叉树结构内的单位。

另外，本公开的一个方式所涉及的编码装置对多个三维点进行编码，具备处理器和存储器，所述处理器使用所述存储器，使用第1三角形集合三角形的2个三角形集合顶点，计算将所述2个三角形集合顶点连结的边上的第1点的位置，使所述第1点的所述位置在第1方向上偏移，使用具有偏移后的所述位置的所述第1点生成第2三角形集合三角形，所述第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点，所述节点是包括所述多个三维点的八叉树结构内的单位。

此外，这些概括或者具体的方式也可以由系统、方法、集成电路、计算机程序或者计算机可读取的CD-ROM等记录介质实现，还可以通过系统、方法、集成电路、计算机程序及记录介质的任意组合来实现。

以下，关于实施方式，参照附图具体进行说明。此外，以下说明的实施方式均表示本公开的一个具体例。以下的实施方式所示的数值、形状、材料、构成要素、构成要素的配置位置及连接方式、步骤、步骤的顺序等是一例，并非意在限定本公开。此外，关于以下实施方式中的构成要素之中独立权利要求中未记载的构成要素，作为任意的构成要素而被说明。

（实施方式）

以下说明本实施方式所涉及的编码装置（三维数据编码装置）及解码装置（三维数据解码装置）。编码装置对三维数据进行编码，从而生成比特流。解码装置对该比特流进行解码，从而生成三维数据。

三维数据例如是三维点群数据（也被称为点群数据）。点群是多个三维点的集合，表示对象物（对象、object）的三维形状。点群数据包括多个三维点的位置信息及属性信息。该位置信息表示各三维点的三维位置。此外，位置信息有时也被称为几何（geometry）信息。例如，位置信息由正交坐标系或者极坐标系表现。

属性信息例如表示颜色信息、反射率、透射率、红外信息、法线矢量或者时刻信息等。1个三维点有时具有单一的属性信息，有时具有多个种类的属性信息。

此外，以下主要说明位置信息的编码及解码，但编码装置也可以进行属性信息的编码及解码。

[三角形集合方式]

本实施方式所涉及的编码装置使用三角形集合（TriSoup：Triangle-Soup、三角面片集）方式对位置信息进行编码。

三角形集合方式是对点群数据的位置信息进行编码的方式之一，是不可逆压缩方式。在三角形集合方式中，将处理对象的原始点群置换为三角形的集合，并在该平面上对点群进行近似。具体而言，将原始点群置换为节点内的顶点信息，并将顶点彼此连结来生成三角形群。另外，用于生成三角形的顶点信息被存放至比特流，并向解码装置发送。

首先，说明使用三角形集合方式的编码处理。图1是表示原始点群的例子的图。如图1所示，对象物的点群102被包含在对象空间101中，且包括多个点103。

首先，编码装置对原始点群进行八叉树（Octree）分割直到规定的深度（depth）为止。在八叉树分割中，对象空间被分割为8个节点（子空间），生成表示在各节点中是否包含点群的8比特的信息（占用码）。另外，包含点群的节点进一步被分割为8个节点，生成表示在该8个节点各自中是否包含点群的8比特的信息。反复进行该处理直到预定的层级为止。

在此，在通常的八叉树编码中，例如反复进行分割，直到节点所包含的点群的数量成为1个或者阈值以下为止。另一方面，在三角形集合方式中，进行八叉树分割直到途中的层级为止，而针对该层级以下的层级不进行八叉树分割。将这样的直到途中的层级为止的八叉树，称为剪枝八叉树。

图2是表示剪枝八叉树的例子的图。如图2所示，点群102被分割为剪枝八叉树的多个叶节点104（最下层的节点）。

接下来，编码装置针对剪枝八叉树的各个叶节点104进行以下的处理。此外，以下将叶节点也简称为节点。编码装置作为与节点的边缘（edge）接近的点群的代表点而在边缘上生成顶点。将该顶点称为边缘顶点。例如，针对多个边缘（例如平行的4边）中的各个边缘生成边缘顶点。

图3是对叶节点104进行二维显示的例子，例如是表示从图1所示的z方向观察的xy平面的图。如图3所示，基于叶节点104内的多个点111之中的边缘的接近点，在边缘上生成边缘顶点112。

此外，在图3中，叶节点104的外周的虚线是边缘。另外，在该例中，在与边缘的距离为1以内的点（图3中的范围113所包含的点）的位置的加权平均的位置上，生成边缘顶点112。此外，距离的单位例如是点群的分辨率，但不限于此。另外，该距离（阈值）在该例中为1，但也可以为1以外，也可以是可变的。

接下来，编码装置基于在包含多个边缘顶点的平面的法线方向上存在的点群，在节点的内部也生成顶点。将该顶点称为质心（centroid）顶点。

图4及图5是用于说明质心顶点的生成方法的图。首先，编码装置从边缘顶点群之中例如选择4点作为代表点。在图4所示的例中，选择边缘顶点v1～v4。接下来，编码装置计算经过4点的近似平面121。接下来，编码装置计算近似平面121的法线n、以及4点的平均坐标M。接下来，编码装置在与从平均坐标M在法线n的方向上延伸的射线接近的1个以上的点（例如图5所示的范围122所包含的点）的加权平均坐标处，生成质心顶点C。

接下来，编码装置对作为边缘顶点和质心顶点的信息的顶点信息进行熵编码，并将编码后的顶点信息存放至比特流所包括的几何数据单元（Geometry Data Unit：以下记作GDU）。此外，GDU不仅包括顶点信息，还包括表示剪枝八叉树的信息。

图6是表示顶点信息的例子的图。通过上述的处理，如图6所示，点群102被转换为顶点信息123。

接下来，说明上述生成的比特流的解码处理。首先，解码装置从比特流对GDU进行解码，得到顶点信息。接下来，解码装置将顶点彼此连结，生成作为三角形群的三角形集合面（TriSoup-Surface）。

图7是表示三角形集合面的例子的图。在图7所示的例中，基于顶点信息，生成4个边缘顶点v1～v4、以及质心顶点C。另外，生成以质心顶点C和2个边缘顶点为顶点的三角形131（三角形集合面）。例如，分别选择相邻的2个边缘上的2个边缘顶点的组，并生成以选择的组和质心顶点为顶点的三角形131。

图8是用于说明点群的复原处理的图。通过按每个叶节点进行上述的处理，如图8所示，生成由多个三角形131表现对象物的三维模型。

接下来，解码装置在三角形131的表面上以一定间隔生成点132，从而对点群133的位置信息进行复原。

[点群面的山脊线的表现的例子]

在三角形集合方式中，存在无法复原跨相邻节点的山脊线（脊线）的形状的情况。相对于此，编码装置在与相邻的节点抵接的面上生成面顶点，在根据质心顶点、面顶点及边缘顶点生成的三角形的面上也复原点群。

例如，在叶节点的内侧分布有点群分布（点群面）的折曲部分的情况下，点群面的角与边缘不相交，在角的位置上无法生成顶点，因此存在将顶点连结而成的面模型无法再现原始点群的形状的情况。

图9是表示点群跨节点1及节点2分布且形成有山脊线的情况下的点群的例子的图。如图9所示，基于边缘附近的点群分布，生成边缘顶点112。

图10是表示该情况下的质心顶点的生成例的图。如图10所示，在边缘顶点群的近似平面的法线方向上生成质心顶点151。

图11是表示该情况下的三角形131（三角形集合面）的生成例的图。如图11所示，将多个顶点（多个边缘顶点及质心顶点）连接从而生成三角形131。此时，如图11所示，无法再现节点边界附近的点群。

这是因为，质心顶点虽然能够对原始点群面进行采样，但在当前的方式中，无法在相邻的2个节点的2个质心顶点之间生成顶点。例如在山脊线沿着x、y、z的某一个轴方向在节点内持续分布的情况下，由于山脊线不跨边缘，不生成与山脊线对应的顶点。由此，发生该问题。

在本实施方式中，编码装置对点群面的山脊线进行预测，在判定为2个相邻节点具有相同的山脊线的情况下，向解码装置传送用于将2个相邻节点的2个质心顶点用线段连接的信息。该信息例如是按节点间的每个面赋予的1比特的信息。

解码装置使用该信息将质心顶点连接，在得到的线段与节点间的共享面的交点处生成新顶点（面顶点）。解码装置使用该新顶点，在生成三角形131时能够再现山脊线。

另外，面顶点的坐标位置不被量化，因此不存在由于量化引起位置偏差的问题。

图12是表示面顶点的生成例的图。如图12所示，解码装置通过生成面顶点161，并使用面顶点161生成三角形131，能够再现山脊线。

通过上述的方法，能够再现节点边界附近的点群面，因此能够得到更接近于原始点群的解码点群。此外，在上述说明中点群面仅被用于说明与山脊线相关的课题，不需要在实际上求出山脊线。

[插值顶点处理]

在三角形集合方式中，在节点内，除了质心顶点之外，还依次选择2个三角形集合顶点（边缘顶点或者面顶点），通过这3点依次生成三角形（也称为三角形集合三角形或者三角形集合面）。另外，通过在各个三角形的表面上生成多个点来复原点群。

但是，存在低比特率时（即节点的尺寸大的情况下）复原点群的品质降低的课题。特别是在原始点群为曲面形状的情况下，如果使节点的尺寸增大，则节点内的各个三角形的面积变大，因此无法表现原始点群的曲面，角部分明的点群被复原。

此外，以下主要说明解码装置中的点群重构，但在编码装置中也可以进行同样的处理。

图13是表示各种顶点和三角形的例子的图。该图是从侧面观察三角形的图。三角形集合顶点V0及V1是在节点边界（节点边缘或者节点面）上形成的边缘顶点或者面顶点。通过质心顶点C、三角形集合顶点V0和另一个三角形集合顶点（未图示）生成三角形，通过质心顶点C、三角形集合顶点V1和另一个三角形集合顶点（未图示）生成三角形。

在本实施方式中，解码装置在点群重构的阶段中，使用插值顶点对各三角形进行细分。图14是表示被生成的插值顶点的例子的图。例如，解码装置在各三角形的边的中点处生成插值顶点。在图14所示的例中，解码装置在质心顶点C与三角形集合顶点V0的中点处生成插值顶点N0，在质心顶点C与三角形集合顶点V1的中点处生成插值顶点N1。

接下来，解码装置对插值顶点N0及N1的位置进行调整（移动）。例如，解码装置使插值顶点N0及N1的位置（坐标）向从边缘顶点群的重心G朝向质心顶点C的方向（矢量Cvec的方向）移动（偏移）。由此，解码装置能够提高复原点群的精度，能够生成接近于原始点群的曲面形状的主观性优异的复原点群。

解码装置基于几何数据单元头（GDUH：Geometry Data Unit Header）中存放的插值顶点有效标记，决定是否进行该插值顶点的生成处理及插值顶点的调整处理（以下将包括插值顶点的生成处理和插值顶点的调整处理在内的处理也称为插值顶点处理）。GDUH是GDU的头信息，GDU是存放点群的位置信息（几何信息）的数据单位。例如，GDU包括多个节点的信息。

另外，解码装置将插值顶点的移动量（调整量）例如设定为与从边缘顶点群的重心G到质心顶点C的距离（矢量Cvec的长度）成比例的值。

另外，编码装置在原始点群为平面点群的情况下，将插值顶点有效标记设定为关闭（不进行插值顶点处理）。由此，解码装置能够维持将平面之处复原为平面的处理。

另外，解码装置即使在插值顶点有效标记为开启的情况下，如果矢量Cvec的长度为0，则也不进行该插值顶点的位置调整。在矢量Cvec的长度为0的情况下，节点内部的原始点群的形状平坦的可能性高。由此，解码装置能够提高复原点群的精度。

此外，插值方法也可以不使用中点插值而使用其他方法。例如，插值顶点N0也可以被生成在将质心顶点C与三角形集合顶点V0连结的边上的任意的位置。例如，插值顶点N0也可以被生成在插值顶点N0与质心顶点C的距离和插值顶点N0与三角形集合顶点V0的距离所成的比例成为预定比例的位置上。

另外，也可以多次反复进行该插值顶点处理。即也可以是，第1三角形通过插值顶点处理被细分为多个第2三角形，多个第2三角形中的至少一个通过插值顶点处理被细分为多个第3三角形。

如上，通过进行插值顶点处理，能够提高复原点群的精度。另外，虽然通过使节点的尺寸变小能够提高复原点群的精度，但通过进行插值顶点处理，与使节点的尺寸变小的情况相比，能够抑制比特流所包括的数据量的增加。另外，插值顶点有效标记被追加地存放于比特流，但例如在插值顶点有效标记以GDU单位存放的情况下，仅通过对每个GDU追加1比特的标记，就能够复原非常精细的点群形状。也就是说，通过使用插值顶点处理，能够抑制比特流的数据量的增加并且提高复原点群的精度。

[插值顶点的调整处理]

以下，说明与顶点的类别相应的插值顶点的调整（移动）处理。图15是表示插值顶点的例子的图。该图例如对应于从上向下对图13及图14所示的节点进行俯视的图。也就是说，在图15中，质心顶点C向近前侧突起，边缘顶点群的重心G隐藏至图的内侧。另外，在节点的上侧也存在边缘顶点及面顶点，但省略其记载。另外，插值顶点N0～N2的位置被向近前方向校正（移动）。

在图15所示的例中，针对以质心顶点C、边缘顶点E0和面顶点F为顶点的第1三角形C-E0-F，在边C-E0上生成插值顶点N0，在边E0-F上生成插值顶点N1，在边F-C上生成插值顶点N2。

通过使用该插值顶点N0、N1及N2对第1三角形C-E0-F进行分割（SubDivide、再分割），新生成4个第2三角形。也就是说，生成第2三角形C-N0-N2、第2三角形N0-E0-N1、第2三角形N2-N1-F和第2三角形N0-N1-N2。

在此，插值顶点N0、N1及N2根据矢量Cvec的方向和长度被调整位置。由此，由4个第2三角形表现的形状与由第1三角形C-E0-F表现的形状相比成为更圆润的形状。

以下，说明插值顶点N0、N1、N2各自的调整处理。在本实施方式中，根据表示插值顶点是否位于节点边界（生成插值顶点的边是否与节点边界一致）的第1条件切换处理。另外，根据表示生成插值顶点的边的两端的2个顶点的组是否为质心顶点与面顶点的组的第2条件切换处理。

首先，说明针对插值顶点N0的调整处理。在此，插值顶点N0属于既不符合上述的第1条件也不符合第2条件的情形。在该情况下，进行上述的插值顶点的调整处理。

在此，插值顶点N0的移动量（调整量）根据矢量Cvec的长度决定。例如，插值顶点N0的移动量是用矢量Cvec的长度（边缘顶点群的重心G与质心顶点C的距离）乘以插值系数α而得到的值。在此，插值系数α也可以是预定的值。或者，插值系数α也可以在编码装置中被决定，并将表示插值系数α的信息存放于比特流。在该情况下，解码装置基于比特流所包括的该信息决定插值系数α。例如，编码装置按每个处理单位（例如GDU或者切片等），计算使得复原点群的形状最接近于原始点群的形状的插值系数α。

此外，插值系数α也可以为0＜α＜1。另外，例如也可以为0＜α＜1/8，也可以为0＜α＜1/4。此外，上述插值系数α的范围也可以根据节点的尺寸切换。例如也可以是，在节点为第1尺寸的情况下应用0＜α＜1/8，在节点为比第1尺寸大的第2尺寸的情况下应用0＜α＜1/4。也就是说，在节点的尺寸大的情况下，也可以使用更大的范围。换言之，在节点的尺寸大的情况下，插值系数α的范围的上限也可以更大。

此外，在插值系数α被预先决定的情况下，该插值系数α被预先决定为该范围内的值。由此也可以是，在节点为第1尺寸的情况下插值系数α被设定为第1值，在节点为比第1尺寸大的第2尺寸的情况下插值系数α被设定为比第1值大的第2值。另外，在编码装置设定插值系数α的情况下，该插值系数α也可以被设定为该范围内的值。

接下来，说明针对插值顶点N1的调整处理。在此，插值顶点N1属于符合上述的第1条件的情形。也就是说，插值顶点N1存在于对象节点与相邻节点的边界面。

在该情况下，解码装置在相邻的节点间使插值顶点的位置一致。在相邻的节点间插值顶点的位置不一致的情况下，由三角形群构成的复原面产生间隙，其原样成为复原点群的间隙。由此，复原点群的精度降低。另一方面，通过在相邻的节点间使插值顶点的位置一致，能够生成在节点间连续的复原面。

首先，解码装置判定插值顶点是否位于节点边界。此外，边缘顶点与面顶点之间的插值顶点存在于节点边界。由此，解码装置也可以判定插值顶点是否为边缘顶点与面顶点之间的顶点。

在插值顶点位于节点边界的情况下，解码装置在共享该插值顶点的节点间，使用共通的值作为插值顶点的移动量。例如，共通的值也可以通过使用对象节点的Cvec与相邻节点的Cvec的平均值来计算。或者，共通的值也可以通过使用对象节点的Cvec和相邻节点的Cvec中的某一方来计算。例如，共通的值也可以通过使用对象节点和相邻节点之中的解码顺序（或者编码顺序）在先的节点的Cvec来计算。

或者，解码装置也可以不调整位于节点边界的插值顶点的位置。或者，编码装置也可以决定是否调整位于节点边界的插值顶点的位置，并将表示是否调整位于节点边界的插值顶点的位置的标记存放至比特流。在该情况下，解码装置依照该标记，决定是否调整位于节点边界的插值顶点的位置。

接下来，说明针对插值顶点N2的调整处理。在此，插值顶点N2属于符合上述的第2条件的情形。也就是说，生成插值顶点N2的边的两端的2个顶点的组是质心顶点C与面顶点F的组。

在此，面顶点表现了由2个节点的2个质心顶点表现的原始点群的山脊线。由此，针对作为质心顶点C与面顶点F的中点的插值顶点N2，在不进行位置调整的情况下，存在能够更好地再现原始点群的形状的可能性。由此，解码装置针对插值顶点N2不进行位置调整。

此外，上述的处理被应用于第1三角形C-F-E0以外的第1三角形（图15所示的第1三角形C-F-E1、以及其他第1三角形（未图示））。由此，生成非常精细的三角形群（复原面）。

另外，解码装置在这多个第2三角形上，使用光线追踪（RayTracing）生成多个点，从而复原点群。

[处理流程]

图16是解码装置所进行的解码处理的流程图。首先，解码装置从比特流中，对表示剪枝八叉树的八叉树信息进行算术解码（熵解码），使用该八叉树信息生成剪枝八叉树，并生成多个叶节点（叶节点群）（S101）。

接下来，解码装置从比特流中，对表示边缘顶点及质心顶点的位置的顶点信息进行算术解码（S102）。

接下来，解码装置对表示是否将面的两侧的节点的质心顶点连接来生成面顶点的面顶点信息进行算术解码（S103）。接下来，解码装置基于面顶点信息，生成面顶点（S104）。

接下来，解码装置使用各顶点生成三角形，并在三角形上生成多个点，从而复原点群（S105）。

图17是三角形及点的生成处理（S105）的流程图。解码装置针对剪枝八叉树的多个叶节点中的各个叶节点进行以下的步骤S111～S117的处理（循环处理）。首先，解码装置对节点内的多个边缘顶点及面顶点以逆时针进行定序（S111）。接下来，解码装置将节点内的顶点群（多个边缘顶点、质心顶点及面顶点）连结来生成三角形（S112）。

接下来，解码装置判定是否进行插值顶点处理（S113）。例如，解码装置从比特流中将插值顶点有效标记取得（解码），并根据取得的插值顶点有效标记，判定是否进行插值顶点处理。

解码装置在进行插值顶点处理的情况下（S113：是），在各三角形的各边上生成插值顶点（S114）。接下来，解码装置对各插值顶点的位置进行调整（S115）。由此，生成将原三角形细分而成的4个三角形。

接下来，解码装置在三角形（细分而成的4个三角形）的表面上生成多个点（S116）。接下来，解码装置用坐标值使节点内的复原点群唯一化并追加至解码点群（S117）。在此，唯一化是将坐标值重复的点排除。如上，针对对象节点的循环处理结束。

另一方面，解码装置在不进行插值顶点处理的情况下（S113：否），跳过步骤S114及S115，在三角形的表面上生成多个点（S116）。接下来，解码装置用坐标值使节点内的复原点群唯一化并追加至解码点群（S117）。

图18是编码装置所进行的编码处理的流程图。首先，编码装置对点群进行八叉树分割从而生成剪枝八叉树，并生成剪枝八叉树的多个叶节点（叶节点群）。另外，编码装置对表示剪枝八叉树的八叉树信息进行算术编码（熵编码），并将编码后的八叉树信息存放至比特流（S201）。

接下来，编码装置针对多个节点（叶节点）中的各个节点，根据该节点内的点群的分布生成边缘顶点和质心顶点，对表示各自的位置信息的顶点信息进行算术编码（熵编码），并将编码后的顶点信息存放至比特流（S202）。

接下来，编码装置在将对象节点的质心顶点与相邻节点的质心顶点连接的线段与该面交叉的位置上生成面顶点（S203）。

接下来，编码装置对面顶点信息进行编码，并将编码后的面顶点信息存放至比特流（S204）。

接下来，编码装置使用各顶点生成三角形，并在三角形上生成多个点，从而复原点群（S205）。此外，步骤S205的详细内容与解码装置中的步骤S105同样。此外，编码装置决定在步骤S113中是否进行插值顶点处理，并将表示决定的结果的插值顶点有效标记存放至比特流。另外，在编码装置中复原后的点群被用于后续的编码处理（例如预测处理等）。

[句法]

说明为了本实施方式的插值顶点处理而从编码装置向解码装置传送的信息的句法。图19是表示GDUH（geometry＿data＿unit＿header）及GDU（geometry＿data＿unit＿data）的句法例的图。

如图19所示，GDUH除了包括现有的头信息之外，还包括C顶点有效标记和插值顶点有效标记。C顶点有效标记表示生成质心顶点的功能是否有效（是否生成质心顶点）。解码装置在生成质心顶点的功能有效的情况下，生成质心顶点，除了边缘顶点之外还使用质心顶点生成三角形。另一方面，解码装置在生成质心顶点的功能并非有效的情况下，不生成质心顶点，而仅使用边缘顶点生成三角形。

插值顶点有效标记是表示是否进行上述的插值顶点处理（插值顶点的生成及调整）的1比特的信息。例如，该插值顶点有效标记在生成质心顶点的功能有效的情况（C顶点有效标记为开启（例如1）的情况）下，被包含于GDUH，在生成质心顶点的功能并非有效的情况（C顶点有效标记为关闭（例如0）的情况）下，不被包含于GDUH（不被包含于比特流）。

GDU包括八叉树信息以及geometry＿trisoup＿data。八叉树信息是表示剪枝八叉树的构成的信息，而且是表示剪枝八叉树所包括的多个叶节点的位置的信息。

geometry＿trisoup＿data包括与三角形的生成相关的信息。例如，geometry＿trisoup＿data包括与边缘顶点及质心顶点相关的顶点信息、以及与面顶点相关的面顶点信息等。

图20是表示GDUH及GDU的其他句法例的图。在图20中，GDUH除了包括图19所示的信息之外还包括插值系数。插值系数被用于计算在插值顶点的位置的调整中使用的移动量。例如，插值系数是与矢量Cvec的长度相乘的系数。

例如，该插值系数在生成质心顶点的功能有效的情况下被包含于GDUH，在生成质心顶点的功能并非有效的情况下不被包含于GDUH（不被包含于比特流）。

此外，在此表示了插值顶点有效标记和插值系数在C顶点有效标记开启的情况下被包含于GDUH的例子，但插值顶点有效标记和插值系数中的至少一方也可以无论C顶点有效标记的值如何都被包含于GDUH。

另外，插值顶点有效标记和插值系数中的至少一方也可以被包含于比特流所包括的GDUH以外的控制信息。例如，插值顶点有效标记和插值系数中的至少一方也可以被包含于序列单位的控制信息（头）。此外，序列是包括多个帧的单位。序列单位的控制信息例如是SPS（序列参数集（Sequence Parameter Set））或者GPS（几何参数集（Geometry ParameterSet））等。SPS是对多个帧共通的控制信息（参数集）。GPS是与位置信息的编码相关的元数据（参数集），是对多个帧共通的元数据。

[变形例]

上述说明了对插值顶点的位置进行调整的例子，但也可以除了插值顶点之外，还对质心顶点、边缘顶点及面顶点中的至少一个的位置进行调整。由此，能够提高复原点群的精度。

图21是表示各种顶点和三角形的例子的图。图21所示的例子相对于图13所示的例子，质心顶点C的位置不同。

具体而言，在三角形集合方式中，需要以较少的顶点的种类和数量表现与原始点群的形状近似的形状。由此，例如，如图21所示，存在将质心顶点C的位置配置在原始点群的分布的稍外侧的情况。

例如，编码装置针对矢量Cvec的长度，进行优先执行小数部分的进位的整数化处理。例如，在小数部分为0.3以上的情况下执行进位。在该情况下，质心顶点C的突出量（相对于原位置的移动量）处于-0.3～＋0.7的范围。

另一方面，在使用本实施方式中说明的插值顶点处理的情况下，顶点的数量增加，因此无需进行这样的质心顶点的位置的调整的处理。由此，解码装置在应用插值顶点处理的情况下，对质心顶点C的位置进行再调整。图22是表示在进行了该调整处理的情况下的各种顶点和三角形的例子的图。

例如，解码装置进行调整以使矢量Cvec变短，以使顶点群更正确地表现原始点群的形状。例如，解码装置通过用矢量Cvec的长度乘以预定的系数来计算调整量。例如，该系数也可以是1/4或者1/8等。解码装置通过从矢量Cvec的长度减去计算出的调整量来对矢量Cvec进行调整。也就是说，质心顶点C的位置向矢量Cvec的方向的逆向移动该调整量。

另外，在上述的插值顶点处理中，使用像这样调整后的矢量Cvec，计算插值顶点的移动量。

另外，解码装置也可以根据矢量Cvec的长度切换是否进行上述的插值顶点处理。例如，解码装置判定矢量Cvec的长度是否比第1阈值大。解码装置在矢量Cvec的长度比第1阈值大的情况下，判定为点群形状的隆起大，使用插值顶点处理。另一方面，解码装置在矢量Cvec的长度为第1阈值以下的情况下，判定为点群形状的隆起小，不使用插值顶点处理。

例如，第1阈值也可以是预定的固定值。或者，编码装置也可以决定第1阈值的值，并将表示第1阈值的值的信息存放至GDUH等的元数据。在该情况下，解码装置基于该信息决定第1阈值的值。

另外，解码装置也可以根据节点的尺寸切换是否进行插值顶点处理。例如，解码装置判定对象节点的尺寸是否比第2阈值大。解码装置在对象节点的尺寸比第2阈值大的情况下，针对对象节点应用插值顶点处理。另一方面，解码装置在对象节点的尺寸为第2阈值以下的情况下，针对对象节点不应用插值顶点处理。

例如，第2阈值也可以是预定的固定值。或者，编码装置也可以决定第2阈值的值，并将表示第2阈值的值的信息存放至GDUH等的元数据。在该情况下，解码装置基于该信息决定第2阈值的值。

此外，解码装置也可以无论矢量Cvec的长度如何都应用插值顶点处理，也可以无论节点的尺寸的大小如何都应用插值顶点处理。

另外，在上述说明中表示了在原三角形的1个边上生成1个插值顶点的例子，但也可以在1个边上生成2个以上的插值顶点。此外，也可以在原三角形的全部边各自上都生成2个以上的插值顶点，也可以在原三角形的一部分边上生成2个以上的插值顶点，而在剩余的边上生成1个插值顶点。

在该情况下也可以通过与上述同样的方法进行插值顶点的调整处理。也就是说，某边上的全部插值顶点向矢量Cvec的方向移动。由此，能够使复原点群的形状接近于原始点群，因此能够提高复原点群的精度。

另外，在上述说明中，使插值顶点移动的方向是从边缘顶点群的重心G朝向质心顶点C的方向（矢量Cvec方向），但也可以此外的方向。例如，使插值顶点移动的方向也可以是与原三角形交叉的方向。例如，使插值顶点移动的方向也可以是插值顶点的位置从边缘顶点群的重心G偏离的方向。例如，使插值顶点移动的方向也可以是三角形的法线的方向。具体而言，使插值顶点移动的方向也可以是沿着三角形的法线而且插值顶点的位置从边缘顶点群的重心G偏离的方向。或者，使插值顶点移动的方向也可以是节点的外侧方向、或者插值顶点的位置从节点的中心偏离的方向。

另外，插值顶点的调整的方法、在调整中使用的矢量、调整方向（移动方向）及调整量（移动量）、插值系数中的至少一个既可以在处理单位所包括的全部插值顶点中共通地使用，也可以按每个插值顶点不同。在此，处理单位既可以是节点，也可以是包括多个节点的单位（例如GDU或者切片等）。

[汇总]

如上，实施方式所涉及的解码装置（三维数据解码装置）进行图23所示的处理。解码装置对多个三维点进行解码。解码装置使用第1三角形集合三角形的2个三角形集合顶点，计算将2个三角形集合顶点（例如质心顶点、边缘顶点或者面顶点）连结的边上的第1点（例如插值顶点）的位置（S301），并使第1点的位置在第1方向上偏移（S302），使用具有偏移后的位置的第1点生成第2三角形集合三角形（S303）。第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点。节点是包括多个三维点的八叉树结构内的单位。

由此，解码装置除了三角形集合顶点之外，还在第1三角形集合三角形的边上生成第1点，并使用第1点生成第2三角形集合三角形。由此，能够提高被复原的三维数据的精度。进而，解码装置通过使第1点的位置偏移，存在能够进一步提高三维数据的精度的可能性。在此，精度是表示以何种程度复原了原始点群的形状的指标，其越高则表示越好地复原了原始点群。也就是说，如该解码方法那样，通过使用被追加的第1点生成第2三角形集合三角形，能够实现更精细的表现，因此精度提高。

例如，第1方向是第1点的位置从节点的多个边缘顶点的重心（例如重心G）偏离的方向。由此，解码装置能够高精度地复原向从多个边缘顶点的重心偏离的方向凸的原始点群的形状。

例如，第1方向是从节点的多个边缘顶点的重心朝向节点的质心顶点的方向（例如矢量Cvec的方向）。由此，解码装置能够提高质心顶点的周边的复原精度。

例如，第1方向是第1点的位置从节点的多个边缘顶点的重心偏离的方向，而且是沿着第1三角形集合三角形的法线的方向。由此，解码装置能够复原更接近于原三维数据的形状的三维数据。

例如，在多个边缘顶点的重心与节点的质心顶点之间的距离越大时，在第1点的位置的偏移中应用的偏移量越大。由此，解码装置能够复原更接近于原三维数据的形状的三维数据。

例如，在第1点的位置的偏移中应用的偏移量通过用多个边缘顶点的重心与节点的质心顶点之间的距离乘以系数（例如插值系数）来计算，系数大于0且小于1/8。在系数过大的情况下，容易发生校正后的位置位于节点的外侧的错误。相对于此，通过使用小于1/8的值作为系数，能够抑制这样的错误的发生。

例如，在节点的尺寸比阈值大的情况下，进行第1点的位置的计算、第1点的位置的偏移及第2三角形集合三角形的生成，在节点的尺寸比阈值小的情况下，不进行第1点的位置的计算、第1点的位置的偏移及第2三角形集合三角形的生成。在节点的尺寸大的情况下，被复原的三维数据的精度降低的可能性高。在这样的情况下，通过进行第1点的位置的计算、第1点的位置的偏移及第2三角形集合三角形的生成，能够有效地提高三维数据的精度。

例如，第1点是边的中点。由此，解码装置通过在边的中点的位置上生成第1点，能够有效地提高三维数据的精度。

例如，2个三角形集合顶点包括被生成在除了节点的边之外的节点的面上的面顶点。由此，解码装置能够提高通过使用面顶点而复原的三维数据的精度。

例如，第1三角形集合三角形的3个三角形集合顶点各自是边缘顶点、质心顶点、以及除了节点的边之外的节点的面所提供的面顶点中的某一个，在2个三角形集合顶点的组不是面顶点与质心顶点的组的情况下，第1点的位置被偏移，在2个三角形集合顶点的组是面顶点与质心顶点的组的情况下，第1点的位置不被偏移。

在2个三角形集合顶点的组是面顶点和质心顶点的情况下，通过使第1点的位置偏移而复原的三维数据的形状有可能偏离原三维数据的形状。由此，通过在这样的情况下不进行偏移，能够提高被复原的三维数据的精度。

图24是解码装置10的框图。例如，解码装置10具备处理器11和存储器12，处理器11使用存储器12进行上述处理。

另外，实施方式所涉及的编码装置（三维数据编码装置）进行图25所示的处理。编码装置对多个三维点进行编码。编码装置使用第1三角形集合三角形的2个三角形集合顶点，计算将2个三角形集合顶点（例如质心顶点、边缘顶点或者面顶点）连结的边上的第1点（例如插值顶点）的位置（S311），使第1点的位置在第1方向上偏移（S312），并使用具有偏移后的位置的第1点生成第2三角形集合三角形（S313）。第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点。节点是包括多个三维点的八叉树结构内的单位。

由此，编码装置除了三角形集合顶点之外，还在第1三角形集合三角形的边上生成第1点，并使用第1点生成第2三角形集合三角形。由此，能够提高被复原的三维数据的精度。进而，编码装置通过使第1点的位置偏移，存在能够进一步提高三维数据的精度的可能性。

图26是编码装置20的框图。例如，编码装置20具备处理器21和存储器22，处理器21使用存储器22进行上述处理。此外，编码装置也可以对上述的解码装置进行同样的处理。

以上说明了本公开的实施方式及变形例所涉及的编码装置（三维数据编码装置）及解码装置（三维数据解码装置）等，但本公开不限定于该实施方式。

另外，上述实施方式所涉及的编码装置及解码装置等所包括的各处理部在典型上通过作为集成电路的LSI实现。其既可以个别地作为单芯片，也可以以包含一部分或者全部的方式作为单芯片。

另外，形成集成电路不限于LSI，也可以由专用电路或者通用处理器实现。也可以利用在制造LSI后能够编程的FPGA（Field Programmable Gate Array：现场可编程逻辑门阵列）、或者可重构LSI内部的电路单元的连接及设定的可重构处理器。

另外，在上述各实施方式中，各构成要素也可以由专用的硬件构成，或者通过执行适于各构成要素的软件程序来实现。各构成要素也可以通过CPU或处理器等程序执行部读出并执行在硬盘或半导体存储器等记录介质中记录的软件程序来实现。

另外，本公开也可以作为由编码装置（三维数据编码装置）及解码装置（三维数据解码装置）等执行的编码方法（三维数据编码方法）或者解码方法（三维数据解码方法）等实现。

另外，本公开也可以作为使计算机、处理器或者装置执行上述编码方法或者解码方法的程序实现。另外，本公开也可以作为通过上述编码方法生成的比特流实现。另外，本公开也可以作为记录有该程序或者该比特流的记录介质实现。例如，本公开也可以作为记录有该程序或者该比特流的非易失性的计算机可读取的记录介质实现。

另外，框图中的功能模块的分割是一例，也可以将多个功能模块作为一个功能模块实现，或者将一个功能模块分割为多个，或者将一部分功能转移至其他功能模块。另外，也可以将具有相似的功能的多个功能模块的功能，由单一的硬件或者软件并列或者分时地处理。

另外，流程图中的各步骤执行的顺序是为了具体说明本公开而例示的顺序，也可以是上述以外的顺序。另外，上述步骤的一部分也可以与其他步骤同时（并行）地执行。

以上基于实施方式说明了一个或者多个方式所涉及的编码装置及解码装置等，本公开不限定于该实施方式。只要不脱离本公开的主旨，对本实施方式施加了本领域技术人员所想到的各种变形而得到的方式、将不同实施方式中的构成要素组合而构筑的方式，也可以都包含在一个或者多个方式的范围内。

工业实用性

本公开能够适用于编码装置及解码装置。

附图标记说明：

10 解码装置

11、21 处理器

12、22 存储器

20 编码装置

101 对象空间

102、133 点群

103、111、132 点

104 叶节点

112 边缘顶点

113、122 范围

121 近似平面

123 顶点信息

131 三角形

151 质心顶点

161 面顶点

Claims (12)

1.一种解码方法，对多个三维点进行解码，

使用第1三角形集合三角形的2个三角形集合顶点，计算将所述2个三角形集合顶点连结的边上的第1点的位置，

使所述第1点的所述位置在第1方向上偏移，

使用具有偏移后的所述位置的所述第1点生成第2三角形集合三角形，

所述第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点，

所述节点是包括所述多个三维点的八叉树结构内的单位。

2.如权利要求1所述的解码方法，

所述第1方向是所述第1点的所述位置从所述节点的多个边缘顶点的重心偏离的方向。

3.如权利要求1所述的解码方法，

所述第1方向是从所述节点的多个边缘顶点的重心朝向所述节点的质心顶点的方向。

4.如权利要求2所述的解码方法，

所述第1方向是所述第1点的所述位置从所述节点的多个边缘顶点的重心偏离的方向，而且是沿着所述第1三角形集合三角形的法线的方向。

5.如权利要求3所述的解码方法，

在所述多个边缘顶点的所述重心与所述节点的质心顶点之间的距离越大时，在所述第1点的所述位置的偏移中应用的偏移量越大。

6.如权利要求3所述的解码方法，

在所述第1点的所述位置的偏移中应用的偏移量通过用所述多个边缘顶点的所述重心与所述节点的质心顶点之间的距离乘以系数来计算，

所述系数大于0且小于1/8。

7.如权利要求1所述的解码方法，

在所述节点的尺寸比阈值大的情况下，进行所述第1点的所述位置的计算、所述第1点的所述位置的偏移及所述第2三角形集合三角形的生成，

在所述节点的所述尺寸比所述阈值小的情况下，不进行所述第1点的所述位置的计算、所述第1点的所述位置的偏移及所述第2三角形集合三角形的生成。

8.如权利要求1所述的解码方法，

所述第1点是所述边的中点。

9.如权利要求1所述的解码方法，

所述2个三角形集合顶点包括被生成在除了所述节点的边之外的所述节点的面上的面顶点。

10.如权利要求1所述的解码方法，

所述第1三角形集合三角形的3个三角形集合顶点各自是边缘顶点、质心顶点、以及除了所述节点的边之外的所述节点的面所提供的面顶点中的某一个，

在所述2个三角形集合顶点的组不是所述面顶点与所述质心顶点的组的情况下，所述第1点的所述位置被偏移，

在所述2个三角形集合顶点的组是所述面顶点与所述质心顶点的组的情况下，所述第1点的所述位置不被偏移。

11.一种编码方法，对多个三维点进行编码，

使用第1三角形集合三角形的2个三角形集合顶点，计算将所述2个三角形集合顶点连结的边上的第1点的位置，

使所述第1点的所述位置在第1方向上偏移，

使用具有偏移后的所述位置的所述第1点生成第2三角形集合三角形，

所述第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点，

所述节点是包括所述多个三维点的八叉树结构内的单位。

12.一种解码装置，对多个三维点进行解码，具备：

处理器；以及

存储器，

所述处理器使用所述存储器，

使用第1三角形集合三角形的2个三角形集合顶点，计算将所述2个三角形集合顶点连结的边上的第1点的位置，

使所述第1点的所述位置在第1方向上偏移，

使用具有偏移后的所述位置的所述第1点生成第2三角形集合三角形，

所述第1三角形集合三角形被用于依照三角形集合方式，在节点内生成多个三维点，

所述节点是包括所述多个三维点的八叉树结构内的单位。