Код 3d-пересечения не работает должным образом

Question

Я создал этот кусок кода, чтобы получить пересечение двух трехмерных линейных сегментов.

К сожалению, результат этого кода является неточным, точка пересечения не всегда находится на обеих линиях.

Я смущен и не уверен, что я делаю неправильно.

Вот мой код:

--dir = direction 
--p1,p2 = represents the line 
function GetIntersection(dirStart, dirEnd, p1, p2) 
    local s1_x, s1_y, s2_x, s2_y = dirEnd.x - dirStart.x, dirEnd.z - dirStart.z, p2.x - p1.x, p2.z - p1.z 
    local div = (-s2_x * s1_y) + (s1_x * s2_y) 

    if div == 0 then return nil end 
    local s = (-s1_y * (dirStart.x - p1.x) + s1_x * (dirStart.z - p1.z))/div 
    local t = (s2_x * (dirStart.z - p1.z) - s2_y * (dirStart.x - p1.x))/div 

    if (s >= 0 and s <= 1 and t >= 0 and t <= 1) and (Vector(dirStart.x + (t * s1_x), 0, dirStart.z + (t * s1_y)) or nil) then 
     local v = Vector(dirStart.x + (t * s1_x),0,dirStart.z + (t * s1_y)) 
     return v 
    end 
end 

Answer 1

Это пример Delphi код, чтобы найти расстояние между двумя косыми линиями в 3D. Для ваших целей необходимо проверить этот результат, если достаточно малое значение (пересечение действительно существует), проверить, что параметры s и t находятся в диапазоне 0..1, затем вычислить точку с использованием параметра s

Математика этого подхода описанный в «кратчайшей линии ... раздел Paul Bourke page

VecDiff если вектор разница функция Dot ID скалярная функция продукта

function LineLineDistance(const L0, L1: TLine3D; var s, t: Double): Double; 
var 
    u: TPoint3D; 
    a, b, c, d, e, det, invdet:Double; 
begin 
    u := VecDiff(L1.Base, L0.Base); 
    a := Dot(L0.Direction, L0.Direction); 
    b := Dot(L0.Direction, L1.Direction); 
    c := Dot(L1.Direction, L1.Direction); 
    d := Dot(L0.Direction, u); 
    e := Dot(L1.Direction, u); 
    det := a * c - b * b; 
    if det < eps then 
    Result := -1 
    else begin 
    invdet := 1/det; 
    s := invdet * (b * e - c * d); 
    t := invdet * (a * e - b * d); 

    Result := Distance(PointAtParam(L0, s), PointAtParam(L1, t)); 
    end; 
end; 

Answer 2

насколько я могу сказать, что ваш код хорошо. Я реализовал это в javascript по адресу https://jsfiddle.net/SalixAlba/kkrc9kcf/

и, похоже, работает для всех случаев, о которых я могу думать. Единственные изменения, которые я сделал, это изменить все, чтобы работать в javascript, а не в lua. Окончательное условие было прокомментировано

function GetIntersection(dirStart, dirEnd, p1, p2) { 
    var s1_x = dirEnd.x - dirStart.x; 
    var s1_y = dirEnd.z - dirStart.z; 
    var s2_x = p2.x - p1.x; 
    var s2_y = p2.z - p1.z; 
    var div = (-s2_x * s1_y) + (s1_x * s2_y); 

    if (div == 0) 
    return new Vector(0,0); 

    var s = (-s1_y * (dirStart.x - p1.x) + s1_x * (dirStart.z - p1.z))/div; 
    var t = (s2_x * (dirStart.z - p1.z) - s2_y * (dirStart.x - p1.x))/div; 

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1) { 
     //and (Vector(dirStart.x + (t * s1_x), 0, dirStart.z + (t * s1_y)) or nil) then 
     var v = new Vector(
     dirStart.x + (t * s1_x), 
     dirStart.z + (t * s1_y)); 
     return v; 
    } 
    return new Vector(0,0); 
} 

Математически это имеет смысл. Если A, B и C, D - ваши две линии. Пусть s1 = B-A, s2 = C-D. Точка линии AB задается A + t s1, а точка на линии CD задается C + s s2. Для пересечения мы требуем

А + Т s1 = С + s s2

или

(АС) + T s1 = s s2

Вы два формула S, T можно найти с помощью принимая декартово произведение 2D с каждым из векторов s1 и s2

(АС)^s1 + T s1^s1 = s s2^s1 (АС)^с2 + T s1^s2 = s s2^с2

rec Alling s1^s1 = s2^s2 = 0 и s2^s1 = - s1^s2 мы получим

(AC)^s1 = s s2^s1 (AC)^s2 + т s1^s2 = 0

, который можно решить, чтобы получить s и t. Это соответствует вашим уравнениям.