计算机图形学之关于光线与三角形的相交求解

首先,三角形的三个顶点定义了一个平面。每个平面都有一个法线,可以看作垂直于平面表面的直线。考虑到我们知道三角形顶点(A,B和C)的坐标,我们可以计算向量AB和AC(它们只是从A到B和A到C的线)。为此,我们只需从A中减去B和从A中减去C。

要计算平面的法线(逻辑上,由于三角形位于平面中,它与三角形的法线相同),我们只需计算AB和AC的叉积。这两个矢量位于同一平面,因为它们连接三角形的顶点。由该叉积产生的矢量(表示为N)救是三角形的法线(图1)。

图1

数学表达如下:
A = v1 - v0 = (1-(-1), (-1)-(-1), 0) = (2, 0, 0)
B = v2 - v0 = (0-(-1), 1-(-1), 0) = (1, 2, 0)
C = A × B
N_x = A.y * B.z - A.z * B.y = 0
N_y = A.z * B.x - A.x * B.z = 0
N_z = A.x * B.y - A.y * B.x = 2 * 2 - 0 * 1 = 4
N = (0, 0, 4)
(注意:在向量里,符号“×”指叉积,符号“⋅”指点积)

如果对C进行归一化,我们得到向量(0,0,1),它与正z轴平行。

这里还有一点需要注意的是,如果交换A与B向量叉乘的顺序,会得到一个与C方向想法的向量:
N = B × A
N_x = B.y * A.z - B.z * A.y = 0
N_y = B.z * A.x - B.x * A.z = 0
N_z = B.x * A.y - B.y * A.x = 0 * 1 - 2 * 2 = -4
N = (0, 0, -4)
这里涉及到三角形顶点申明顺序和方向(绕组)

设光线与平面的相交点为p,则p减掉三角形任意一个顶点所生成的向量位于平面内;又因为两个垂直的向量的点积为0。所以有:
(p - v1) ⋅ N = 0;(公式1)
p点也可以用光线来表示:
p = O + tR;(公式2)
其中O为光线原点,R为光线的方向(已归一化)。
将公式2带入公式1,得到:
((O + tR) - v1) ⋅ C = 0;
由于O, R, v1, C已知,可求得t,将t带入公式二,即可求得焦点p;
t = ((v1 - O) ⋅ N) / (R ⋅ N)(公式3)

此时有两个需要注意的点
1,当三角形位于光线的背后的时候,此时 t < 0;
2,当三角形与光线平行时,此时公式3无解;如果注意一下公式3,会发现此时(R ⋅ N) = 0;那么此时公式3会除以0;所以要提前测试一下;

求得交点之后,还需要进行内外测试。目前所求的交点为光线与平面的交点,所以还不知道交点是否在三角形内;所以需要进行内外测试已检测交点是否在三角形内;

图2

如图2所示,有一个与x轴对齐的矢量A。让我们假设这个向量实际上与三角形的一个边对齐(由两个顶点V0V1定义的边)。现在,第二条边B由三角形的顶点V0和V2定义。让我们计算这两个向量的叉积。结果是一个向量,它指向与z轴和三角形法线相同的方向。
A=(1,0,0)
B=(1,1,0)
C.x = A.y * B.z − A.z * B.y =0
C.y = A.z * B.x − A.x * B.z =0
C.z = A.x * B.y − A.y * B.x = 1 ∗ 1 − 0 ∗ 1 = 1
C=(0,0,1)

现在,假设顶点V2不是坐标(1,1,0),而是坐标(1,-1,0)。换句话说,我们已经反映了它关于x轴的位置。如果我们现在计算交叉积 A x B',我们得到结果C'=(0, 0,-1)
A=(1,0,0)
B=(1,−1,0)
C.x = A.y * B.z − A.z * B.y =0
C.y = A.z * B.x − A.x * B.z=0
C.z = A.x * B.y − A.y * B.x=1∗−1−0∗1=−1
C=(0,0,−1)

我们知道光线与三角形相交的点在同一平面上。从上面的测试中得知,如果位于三角形平面中的交点P位于矢量A的左侧,那么三角形的法线和向量C是正的(C是A和B之间的叉积的结果。在这种情况下,A =(V1-V0)和B =(P-V0))。但是,如果P位于A的右侧,则该点积为负。在图2中可以看到,当它位于A的左侧时,P点位于三角形内部。为了测试点p是否在三角形内,需要重复左/右测试对于三角形的每个边缘。如果对于每个三角形边缘,发现点P位于矢量C的左侧(其中C分别定义为三角形的每个边缘的V1-V0,V2-V1和V0-V2),那么我们知道确保P在三角形内。如果任何三角形边缘的测试失败,则P位于三角形边界之外。该过程如图3所示。

图3

代码如下:

bool rayTriangleIntersect(
      const Vec3 \& orig, const Vec3& dir,
      const Vec3& v0, const Vec3& v1, const Vec3& v2,
      float t)
{
      Vec3 v1v0 = v1 - v0;
      Vec3 v2v0 = v2 - v0;
      Vec3 N =  v1v0.crossProduct(v2v0);  // 求三角形法向量

      //求交点P
      float NdotRayDirection = N.dotProduct(dir); 
      if(fabs(NdotRayDirection) < kEpsilon) return false; //如果三角形法向量与光线的点积接近于0,可以认为光线与三角形平行,此时没有交点,返回false

      t = (N.dotProduct(v0) + N.dotProduct(orig)) / NdotRayDirection; //计算t值
      if(t < 0) return false; //如果t小于0,那么三角形在光线背后,返回false

      Vec3 P = orig + t * dir; //计算交点p

      Vec3 C;
      //内外测试
      Vec3 vp0 = P - v0;
      Vec3 edge0 = v1 - v0;
      C= edge0.crossProduct(vp0);
      if(C < 0) return false;  //在三角形外边,返回false

      Vec3 vp1 = P - v1;
      Vec3 edge1 = v2 - v1;
      C= edge1.crossProduct(vp1);
      if(C < 0) return false;  //在三角形外边,返回false

      Vec3 vp2 = P - v2;
      Vec3 edge2 = v0 - v2;
      C= edge2.crossProduct(vp2);
      if(C < 0) return false;   //在三角形外边,返回false
  
      return true; //三角形与光线有交点,返回true
}

引用文章:https://www.scratchapixel.com/lessons/3d-basic-rendering/ray-tracing-rendering-a-triangle/ray-triangle-intersection-geometric-solution

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,732评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,496评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,264评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,807评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,806评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,675评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,029评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,683评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 41,704评论 1 299
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,666评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,773评论 1 332
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,413评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,016评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,978评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,204评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,083评论 2 350
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,503评论 2 343