综合了形状和物理性能的实体数据的存储方法专利名称：综合了形状和物理性能的实体数据的存储方法技术领域：本发明涉及三角形与线段的交点的计算方法及其程序。相关技术的说明用小的存储容量可以存储综合了形状和物理性能的实体数据，因而，将物体的形状、构造、物理信息、履历作一元化管理，可以将有关从设计开始至加工、组装、试验、评价等一连串的工序的数据用相同的数据进行管理，作为能够将CAD和模拟一元化的实体数据的存储方法，公开在专利文献1中。专利文献1特开2002-230054 号公报如图1所示，专利文献1的综合了形状和物理性能的实体数据的存储方法由外部数据输入步骤(A)、八叉树(octree)分割步骤(B)、以及单元数据存储步骤(C)构成， 在外部数据输入步骤(A)中，将由用外部数据取得步骤Sl取得的目标物的边界数据构成的外部数据12输入至存有本发明的方法的计算机等中，在八叉树分割步骤(B)中，用八叉树分割将外部数据12分割成边界平面成正交的长方体的单元，在单元数据存储步骤(C)中， 在每个单元上存储各种物理性能值。上述的专利文献1的发明中，用八叉树分割将由目标物的形状数据构成的外部数据分割成边界平面成正交的长方体的单元，每个单元上存储各种物理性能值。被分割的各单元由位于目标物内侧的内部单元和包含边界面的边界单元构成。另外，作为属性，内部单元具有1种物理性能值，边界单元具有目标物的内侧与外侧的2种物理性能值。以下，将用本方法产生的数据称为V-CAD数据，将使用这个数据的设计或模拟称为体积CAD或V-CAD。在图1中，14是V-CAD数据。图2是表示根据专利文献1由外部数据作成V-CAD数据的步骤的图。如该图所示，对于S-CAD数据和三角形缀片数据，在步骤1中定义体素(voxel)空间，在步骤2中进行几何形状与各单元的棱线的交点计算(单元切断点的取得)，在步骤3中，由每个单元的切断点信息作成单元内面的外周环，在步骤4中，一边参照原来的几何形状一边将外周环内作三角形分割，在步骤5中，通过设定单元的媒质值作成V-CAD数据。在上述的专利文献1的方法中，在图1的八叉树分割步骤(B)以及图2的步骤 2中，重复求出定义外部数据即几何形状的三角形与各单元的棱线即线段的交点的计算，产生庞大次数的计算。作为这样的三角形与线段的交点计算方法，一直以来，知道有非专利文献1 非专利文献3。非专利文献1Moller 的方法(Journal of graphicstools, 2 (1) :21-281997)。非专利文献2Badouel 的方法(Graphic Gems, Academic PressP21_28 1990)。非专利文献3Computational Geometry in C:Joseph 0 Rourke/CambridgeUniversity Press P239)关于三角形与线段的交点计算，存在有各式各样的方法，其多数是计算无限平面与无限直线的交点，是判断其交点是否包含在作为平面内的闭区域的三角形内的方法。那样的方法计算成本高，如所推断的那样，今后在V-CAD系统中需要有对重复进行许多次计算进行改善的策略。在非专利文献1的Moller的方法中，通过利用数学式2的式(1)的矢量计算式可以用比较低的成本计算。数学式2UP1P2P3PLin 三角形的顶点、线段的始点VDir:线段的方向矢量t:在线段中的参数U，V:在三角形内的参数但是，在这个方法中，在对于同样的三角形求与不同的多个线段的交点时也需要改变全部的计算式来计算，所以，在所谓同样的三角形的条件下不发生交点计算的优点， 存在着所谓谋求高速化困难的问题。在非专利文献2的Badouel的方法中，如图3所示，利用平面的基准点Ppin和法线矢量Vta、直线的基准点Pun按以下方法求出。作为数学式3的式0)，由于直线的基准点与平面的距离可以用dst = VNrm Vpnt (Vta为单位矢量)求得，所以，交点的座标可以用Plnt = PLin+VLin dst/(Vun VnJ 计算。接着，将三角形的各顶点以及平面和直线的交点投影在座标平面(xy平面、yz平面、ZX平面)的任一平面上，在该平面上，计算构成数学式3的式(3)的、。、的计算方法，如图4所示，当投影在xy平面上的情况下，作为P1 0q，Z1)、 P2 (x2，y2, Z2), P3 (x3, y3，z3)、PInt (, y，)，也可以作成省略各顶点的Z座标后的一次变换式 (数学式3的式4)的逆变换。数学式3权利要求1.一种综合了形状和物理性能的实体数据的存储方法，包括通过八叉树分割将由对象物的形状数据构成的外部数据分割成边界平面成正交的长方体的单元，计算所述外部数据即定义几何形状的以3点Ptl，P1, P2作为3顶点的三角形与所述各单元的棱线即连接A，B的线段的交点的步骤，该步骤包括座标系设定部件设定将Ptl作为原点、将PtlP1作为第一轴(U轴)的单位长度、将PtlP2作为第二轴(V轴)的单位长度、将PciP1XPtlP2的单位矢量作为第三轴(N轴)的座标系R的座标系设定步骤(A)；矩阵计算部件将通常的座标系中的点的座标变换成座标系R的座标值的变换矩阵M的变换矩阵计算步骤(B)；线段端座标计算部件计算线段两端A，B的u，, 座标值的线段端座标计算步骤(C)；交叉判断部件根据两端，B的u，, 座标值判断有无与三角形的交叉，不交叉时，结束与所述线段相关的计算并进入输出步骤的交叉判断步骤(D)；交点座标计算部件在所述交叉判断步骤(D)中为交叉的情况下，计算该交点的u，座标值的交点座标计算步骤(E)；交点判断部件从所述交点的u，座标值判断有无三角形内的交点的交点判断步骤(F)；输出部件将反映所述交点是否在所述三角形内的这一信息和所述交点座标的信息中的至少一方的信息的数据发送给输出装置的输出步骤。2.如权利要求1所述的综合了形状和物理性能的实体数据的存储方法，其特征在于 在所述变换矩阵计算步骤(B)中，变换矩阵M是Affine变换矩阵。3.如权利要求1所述的综合了形状和物理性能的实体数据的存储方法，其特征在于 在线段端座标计算步骤(C)中，用式(8)求出u，座标值，Puvn = MPxyz(8)4.如权利要求1所述的综合了形状和物理性能的实体数据的存储方法，其特征在于 在交叉判断步骤中，若一个点的座标等于或超过线段的长度，则判断为无交点， 以及/或者若2点的座标同号，则判断为无交点，若为异号，则判断为有交点。5.如权利要求1所述的综合了形状和物理性能的实体数据的存储方法，其特征在于 在交叉判断步骤中，在以下情况下，(1)2点的u座标均为0以下或1以上，0)2点的 座标均为O以下，或(3)2点的u座标+座标均为1以上时，判断为交点在三角形外。6.如权利要求1所述的综合了形状和物理性能的实体数据的存储方法，其特征在于 在交点座标计算步骤(E)中，将用两端，的座标的值内分的点作为交点，计算其u，v座标值。7.如权利要求1所述的综合了形状和物理性能的实体数据的存储方法，其特征在于 在交点判断步骤(F)中，交点的u，v座标值满足于数学式1的式(13)时，判断为在三角形内部，数学式1 O u 1 (Vecl方向的范围) O1 (Vec2方向的范围)(13) 0u+v1 (P1P2的线的内侧(P0侧)8. 一种综合了形状和物理性能的实体数据的存储方法，包括 通过八叉树分割将由对象物的形状数据构成的外部数据分割成边界平面成正交的长方体的单元，计算所述外部数据即定义几何形状的以3点Ptl，P1, P2作为3顶点的三角形与各单元的棱线即连接A，B的线段的交点的交点计算装置， 该交点计算装置包括设定将Ptl作为原点、将PtlP1作为第一轴(U轴)的单位长度、将PtlP2作为第二轴(V轴) 的单位长度、将PclP1XPtlP2W单位矢量作为第三轴(N轴)的座标系R的座标系设定部件 (A)；计算将通常的座标系中的点的座标变换成座标系R的座标值的变换矩阵M的变换矩阵计算部件；计算线段两端A，B的u，, 座标值的线段端座标计算部件(C)； 根据两端，B的u，座标值判断有无与三角形的交叉，不交叉时，结束与所述线段相关的计算的交叉判断部件(D)；在所述交叉判断部件(D)中为交叉的情况下，计算该交点的u，座标值的交点座标计算部件(E)；从交点的u，座标值判断有无三角形内的交点的交点判断部件(F)； 将反映所述交点是否在所述三角形内的这一信息和所述交点座标的信息中的至少一方信息的数据发送给输出装置的输出部件。全文摘要本发明提供一种综合了形状和物理性能的实体数据的存储方法。其中，在计算将P0，P1，P2作为3顶点的三角形与连接A，B的线段的交点的方法中包括，设定将P0作为原点、将P0P1作为第一轴(U轴)的单位长度、将P0P2作为第二轴(V轴)的单位长度、将P0P1P0P2的单位矢量作为第三轴(N轴)的座标系R，计算将通常的座标系中的点的座标变换成座标系R的座标值的变换矩阵M，计算线段两端A，B的u，v，n座标值。另外，根据两端A，B的u，v，n座标值判断有无与三角形的交叉，在交叉的情况下，计算其交点的u，v座标值，从交点的u，v座标值判断有无三角形内的交点。