科技行者

行者学院 转型私董会 科技行者专题报道 网红大战科技行者

知识库

知识库 安全导航

至顶网软件频道基础软件空间直线段和三角形相交算法

空间直线段和三角形相交算法

  • 扫一扫
    分享文章到微信

  • 扫一扫
    关注官方公众号
    至顶头条

维空间当中,直线和三角形的相交算法是计算机三维图形学当中,碰撞检测和选择操作的最基本的算法 DirectX SDK当中PICK例子,提供了原始代码,对于这段代码有不同的理解这里是用仿射坐标系分解的方式解释它。

作者:[顾问团]寻开心 来源:CSDN 2008年3月24日

关键字: 三角形 直线段 空间 游戏 Linux

  • 评论
  • 分享微博
  • 分享邮件

三维空间当中,直线和三角形的相交算法是计算机三维图形学当中,碰撞检测和选择操作的最基本的算法
DirectX SDK当中PICK例子,提供了原始代码,对于这段代码有不同的理解
这里是用仿射坐标系分解的方式解释它

基本知识
      空间平面方程, N*P+D=0; 或者N*P=D,
               这里*是向量的点乘,N是平面的法向量,P是平面上的任意一点
              而D表示的是原点到平面的距离,或者平面到原点的距离,注意这个距离是矢量
      点到空间平面的距离
              对于N*P=D的情形,D就是从原点到平面的距离
              N*P0-D就是点到平面的距离了
   
要解决线段和空间三角形相交的问题,分两步解决
第一步
        计算线段和空间三角形所在的平面的交点
        计算线段的两个端点到平面的距离,如果符号相同,表示位于同测,必然不相交
        根据距离可以差值得到0距离时候的点,这个点就是交点了
第二步,交点是否在空间三角形的内部
       这个时候,可以用仿射坐标系分解的方法来计算
首先介绍什么是仿射坐标系
      我们比较熟悉的是笛卡儿的正交坐标系,两个坐标轴是相互垂直的
      而仿射坐标系当中,两个坐标轴是不垂直的,只要不是平行的就可以组成仿射坐标系
     显然,笛卡儿的正交坐标系是仿射坐标系的一个特例了
     无论是正交还是仿射坐标系,都有下列事实存在:
            假定两个坐标轴的向量是X和Y
           空间任何的一个点P都可以表示成为 P = O + x*X + y*Y
           O是原点,x和y就是在这个坐标系下的坐标了
           空间任何一个点,按照这个坐标系来说,x和y的数值都是唯一的
           对于空间上的一个点,过它做平行坐标轴的平行线,和坐标轴相交,这个交点到原点的距离就是系数
           对于正交坐标系来说,平行线和坐标轴围成的是一个矩形
           对于仿射坐标系来手,平行线和坐标轴未成的是一个平行四边形
 如果我们把三角形的一个顶点看作是仿射坐标系的原点,而从这个顶点发出去的两个边作为仿射坐标系的两个坐标轴的单位向量,那么平面内的任何一个点在这个仿射坐标系下的坐标数值就可以区分出来点和这个三角形之间的关系了。假定坐标是u和v,那么 u>0,v>0表示,点在第一象限
          u+v<=1 表示点在三角形的内部
  如果  0<= u <= 1 并且   0<=v <=1则表示点在有两条边组成的平行四边形的内部
根据找个原理,我们就可以判定,点是否在三角形或者平行四边形的内部了

具体计算方式
      三角形的三个顶点分别是P1,P2,P3, 同平面的点Po
     两个边向量就是 U = P2-P1  V=P3-P1     
    此坐标系内的点Po' = Po - P1
解这个方程就可以获得到仿射坐标系下的坐标了:
       Po' = u*U + v*V
因为点是三维的,只要u和v两个位置数, 所以取出三维坐标当中的两个坐标分量计算就可以了。
其实我们只要找平面法向量三个坐标分量当中,绝对值小的那两个坐标分量来计算就可以了
实际上这就是解一个二元一次的方程组而已
具体的算法无需给出

    • 评论
    • 分享微博
    • 分享邮件
    邮件订阅

    如果您非常迫切的想了解IT领域最新产品与技术信息,那么订阅至顶网技术邮件将是您的最佳途径之一。

    重磅专题
    往期文章
    最新文章