如何做光線和三角形邊相交？

我正面臨與三角形邊緣相交的光線問題。實際上，我試圖用鼠標選取/相交於三角形，頂點，網格物體的邊緣。所以我從鼠標的當前位置製作了光線，然後將它與三角形/多邊形，頂點，邊緣等網格元素相交以使用它。基本上，3D建模的東西。用三角形相交很簡單而有趣。頂點部分很棘手。如何做光線和三角形邊相交？

但現在，我不知道如何與三角形邊相交/挑選。我的意思是我如何對待他們與鼠標相交時？首先，我認爲他們可以像3D線一樣對待。但最終未能做到雷和線相交。在互聯網上搜索，但沒有找到任何有用的信息。儘管我發現一些開源項目正在使用OpenGL內置的拾取功能來挑選/相交Edge。但就我而言，我無法使用它。 :(

我目前的邊緣採摘代碼結構如下所示：

void pickEdge(Ray ray, Scene scene) 
{ 
    for each object in scene 
    { 
     mesh = getMesh(object) 
     for each triangle in mesh 
     { 
      for each edge in triangle 
      { 
       v1 = getV1(edge) 
       v2 = getV2(edge) 

       // Do intersect with 'ray' and 'v1', 'v2'. But how? 
      } 
     } 
    } 
}

所以我堅持在這裏，真的需要一些幫助任何想法，算法或小的幫助是極大的讚賞

。

來源

2016-08-05 Forhad Reza

確定您的拾取點是否在邊緣的可接受「半徑」內 - 使用與線公式的距離。然後對邊緣進行正交投影，以便在必要時在邊緣產生「點」。 –

@Brett Hale你說'使用距離線公式'。其實我被困在這一點上。實際上我還沒有能夠實現Ray-Line相交。如果您將其作爲答案發布並提供更多詳細信息，則會更有幫助。感謝您的寶貴意見:) –

啊...其實我仍然卡住:(需要幫助...請。 –

請在這個頁面的最後給看看的算法和更普遍的所有的人，這個網站提供：http://geomalgorithms.com/a05-_intersect-1.html

來源

2016-08-08 06:47:23 abenci

哇！這些算法真的非常有用。我必須看看我能否明智地使用它們來解決我的問題......謝謝。 –

在可以上下煮在3D空間中找到三角形和光線之間的交叉你的情況的問題去fi在二維空間（平面）中找到三角形內的點位置（INSIDE，OUTSIDE，ON BOUNDARY）。你所要做的就是在屏幕平面上投影三角形，在邊緣找到交點並在邊緣執行反投影。點的位置是鼠標的位置。唯一的問題是處理退化的情況，如將三角形映射到線段中。但我認爲這不會成爲問題，因爲這種情況很容易應付。

來源

2016-08-15 07:41:40 LmTinyToon

第一種方法是將邊緣（和光線）正交投影到垂直於光線的平面上，然後計算投影光線到投影邊緣的距離。即，首先確定與你的光線正交的兩個正交矢量rdir1, rdir2。

然後你計算你的射線（它的基點）到這個平面的投影，它將簡單地產生一個2d點rp。

於是，你設想的邊緣到面，通過簡單地將點積： pv1 = new Vector2(DotProduct(v1, rdir1), DotProduct(v1, rdir2)) pv2 = new Vector2(DotProduct(v2, rdir1), DotProduct(v2, rdir2))

現在你可以計算的點rp從這個2D線pv1, pv2的距離。如果邊緣的方向取自視圖矩陣的「前向」方向，則與之垂直的兩個向量將是視圖矩陣的左側和右側向量。

做上面的配方會產生類似於將邊緣投影到屏幕上的東西。因此，也可以將邊緣投影到屏幕上並使用這些座標。

來源

2016-09-02 15:22:00 VlltStiller

嗯...我認爲我的問題可以通過簡單的3D（xyz）數學來解決。但現在，事情似乎並不那麼容易。事實上，我很少理解正交投影，把東西投射到......飛機......東西......等等。確實，在這些情況下，瞭解數學是最重要的。而我，我，我自己;總是停留在這一點上：（...你理解我了嗎？無論如何，感謝這個更好的答案，讓我看看我能否解決我的問題哦，我現在沒有太多時間，但是謝謝！ –

Hello Mohammad，不要被長時間的回覆嚇倒，它確實非常簡單，確實有不同的方法（通過使用交叉產品），但答案已經太長了，如果你在乎，我會添加其他路線。 – VlltStiller

當然，事實上，我很樂意從你那裏得到更多的信息。關於 –

首先，兩個幾何對象A和B之間的距離是多少？它是A和B上任意兩點之間的最小距離，即。 dist(A,B) = min { EuclideanLength(x - y) | x in A, y in B}。（如果它存在並且是唯一的，它在你的情況下就是這樣）。

這裏你已經知道了EuclideanLength((x,y,z)) = sqrt(x^2 + y^2 + z^2)。由於sqrt嚴格增加，所以最大限度地減少SquareEuclideanLength((x,y,z)) = x^2 + y^2 + z^2，這大大簡化了問題。

在你的問題中，對象是一條線段A := {v1 + t*(v2-v1) | 0 <= t <= 1}和一條線B := {p + s*d | s is any real number}。（別擔心，你問一個光線，一條線是你真正想要的東西。）

現在，計算距離歸結爲尋找合適的t和s，從而SquareEuclideanLength(v1 + t*(v2-v1) - p - s*d)是最小的，然後計算EuclideanLength(v1 + t*(v2-v1) - p - s*d)得到真正的距離。

要解決這個問題，我們需要一些解析幾何。因爲d不爲零，所以我們可以將每個矢量v寫爲與d正交的部分和d：的倍數的部分的和。對於這樣的「正交分解」，它始終保持爲SquareEuclideanLength(v) = SquareEuclideanLength(Ov) + SquareEuclideanLength(Mv)。

由於

d = Md在上述

SquareEuclideanLength(v1 + t*(v2-v1) - p - s*d) = SquareEuclideanLength(Ov1 + t*(Ov2-Ov1) - Op) + SquareEuclideanLength(Mv1 + t*(Mv2-Mv1) - Mp - s*d)

左加數不依賴於s並且按照自己的選擇t你可以找到一個s使得右加數爲0！（請記住，Mv1，Mv2 ...是d數倍。）

因此找到你只需要找到這樣的地圖O，如上M，找到極小t最小。

假設d是標準化的，這實際上是由Ov := CrossProduct(v, d)和Mv := DotProduct(v, d)*d給出，只是相信我，這也適用，如果d不歸。

所以尋找遠處的食譜是現在：找到0 <= t <= 1，最大限度地減少

SquareEuclideanLength(Cross(v1 - p, d) + t*Cross(v2 - v1, d)) = SquareEuclideanLength(Cross(v1 - p, d)) + 2*t*Dot(Cross(v1 - p, d), Cross(v2 - v1, d)) + t^2 SquareEuclideanLength(Cross(v2 - v1, d))。

你就已經知道從點線距離計算這個公式（這就是它是什麼），它是由相對於分化爲t和等於0

解決，使這個方程的極小是 t = -Dot(Cross(v1 - p, d), Cross(v2 - v1, d))/SquareEuclideanLength(Cross(v2 - v1, d))

使用此t，您可以計算v1 + t*(v2 - v1)，線段A上距離線B最近的點，並且可以將其插入到點線距離算法中以查找追求的距離。

我希望這可以幫助你！

來源

2016-09-06 13:18:37 VlltStiller

非常感謝所有這些信息！最好的問候:) –

如何做光線和三角形邊相交？

回答

相關問題