关键词: 几何计算, 三角形相交, 降维, 几何奇异, 计算坐标系

Abstract: This paper focuses on geometric singularity and algorithm speed. In our algorithm,
a 3D problem is reduced to planes and is further divided to a linear problem. In order to simplify
the representation of geometric problem, a computational coordinate system is constructed. Thus,
the geometric singularity of two triangles is reduced to planar problems between a line and a
triangle, which limits the singularity to co-points and co-lines. Consequently, the complex
spatial geometric singularity can be represented by planar drawings simply and visually and the
robustness of our algorithm can be certificated theoretically. This paper gives the whole algorithm
and detailed schemes. Experiment tests show that the priority in simplifying geometric relations,
geometric singularity and calculations is sufficient to make up for the cost of transformation. The
speed is 1 million pairs of triangles per second on a notebook computer.

Key words: geometric computing, triangles intersection, dimension reduction, geometric
singularity, computational coordinates