Только оптимизированная сфера-линия?

Question

Есть ли оптимизированное уравнение для вычисления пересечения сферы и линии, я знаю о ближайшем решении точки, но мне было интересно, есть ли другой. Существует также квадратичное уравнение, но оно требует большого количества вычислений, и я не уверен в всех ранних выходах, которые возможны с ним. Я знаю двух по (я думаю) ...

Vec3 d = lineEnd - lineStart; // the ray 
Vec3 f = lineStart - sphereCenter; // center -> lineStart 


float c = dot(f, f) - radius * radius; 

if(c <= 0) 
{ 
    // first out 
    // sphere is touching the vertex 
    // hit ! 
} 

float b = dot(f, d); 

if(b >= 0) 
{ 
    // second out 
    // line ray and center -> start, are going same direction 
    // if the start point didn't intersect above 
    // then there's no way for the segment or other point to 
    // miss 
} 

float a = dot(d, d); 

// ... any other optimizations 

if(b*b - a*c < 0) 
{ 
    // miss 
} 

Answer 1

Я не думаю, что вы действительно можете стать намного лучше. Вы могли бы устранить некоторые простые случаи. Если говорят, что начальная и конечная точки линии имеют координаты x меньше, чем центр сферы минус радиус и единицы выше центра сферы и единицы ниже, то это будет невозможно. Вы могли бы рассмотреть куб, окружающий сферу. Если линия не пересекает поле, она не может пересекать сферу. Это может быть проще рассчитать.

Квадратичный алгоритм не так уж плох. Продукт Dot состоит из трех умножений и трех дополнений. Я думаю, что все это можно сделать в двенадцати умножениях (исключая умножение на 2 и 4). Есть шанс, что вы можете устранить некоторые из них. Обратите внимание, что вам не нужно вычислять квадратный корень, который является действительно дорогим битом, просто проверьте знак дискриминанта, как в вашем коде.

Answer 2

посмотреть здесь ray and ellipsoid intersection accuracy improvement

• просто установить r[3], как (1/R*R,1/R*R,1/R*R)
• или обновление уравнений сингулярного радиуса (можно умножить целое уравнение 1/(R * R) позже)
• в текущем состоянии его нужно 3 х Тройная точка, в 1 х SQRT, 2 х DIV и некоторые незначительные операции, такие как +, -, *