Пересечение прямой и сферы - PullRequest
Новая
       25

Пересечение прямой и сферы

7 голосов
/ 04 мая 2011

Я пытаюсь найти точку пересечения между сферой и линией, но, честно говоря, я понятия не имею, как это сделать. Может ли кто-нибудь помочь мне в этом?

Ответы [ 9 ]

14 голосов
/ 04 мая 2011

Выразите строку как функцию t: 

{ x(t) = x0*(1-t) + t*x1
{ y(t) = y0*(1-t) + t*y1
{ z(t) = z0*(1-t) + t*z1

Когда t = 0, это будет в одной конечной точке (x0,y0,z0). Когда t = 1, это будет в другой конечной точке (x1,y1,z1).

Напишите формулу для расстояния до центра сферы (в квадрате) в t (где (xc,yc,zc) - центр сферы): 

f(t) = (x(t) - xc)^2 + (y(t) - yc)^2 + (z(t) - zc)^2

Решите для t, когда f(t) равно R^2 (R - радиус сферы): 

(x(t) - xc)^2 + (y(t) - yc)^2 + (z(t) - zc)^2 = R^2

A = (x0-xc)^2 + (y0-yc)^2 + (z0-zc)^2 - R^2
B = (x1-xc)^2 + (y1-yc)^2 + (z1-zc)^2 - A - C - R^2
C = (x0-x1)^2 + (y0-y1)^2 + (z0-z1)^2

Решить A + B*t + C*t^2 = 0 для t. Это нормальное квадратное уравнение .

Вы можете получить до двух решений. Любое решение, где t лежит между 0 и 1. Действительны.

Если вы получили правильное решение для t, включите его в первые уравнения, чтобы получить точку пересечения.

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

Редактировать: Я исправил формулу для B. Я перепутал знаки. Спасибо, М. Кац, за упоминание, что это не сработало.

7 голосов
/ 06 июля 2013

Я считаю, что в решении Маркуса Жардеро есть неточность.Не уверен, в чем проблема, но я почти уверен, что точно перевел это в код, и когда я попытался найти пересечение отрезка прямой, который, как известно, пересекается в сферу, я получил отрицательный дискриминант (без решений).

Я нашел это: http://www.codeproject.com/Articles/19799/Simple-Ray-Tracing-in-C-Part-II-Triangles-Intersec,, который дает похожий, но немного другой вывод.

Я превратил это в следующий код C #, и он работает для меня: 

    public static Point3D[] FindLineSphereIntersections( Point3D linePoint0, Point3D linePoint1, Point3D circleCenter, double circleRadius )
    {
        // http://www.codeproject.com/Articles/19799/Simple-Ray-Tracing-in-C-Part-II-Triangles-Intersec

        double cx = circleCenter.X;
        double cy = circleCenter.Y;
        double cz = circleCenter.Z;

        double px = linePoint0.X;
        double py = linePoint0.Y;
        double pz = linePoint0.Z;

        double vx = linePoint1.X - px;
        double vy = linePoint1.Y - py;
        double vz = linePoint1.Z - pz;

        double A = vx * vx + vy * vy + vz * vz;
        double B = 2.0 * (px * vx + py * vy + pz * vz - vx * cx - vy * cy - vz * cz);
        double C = px * px - 2 * px * cx + cx * cx + py * py - 2 * py * cy + cy * cy +
                   pz * pz - 2 * pz * cz + cz * cz - circleRadius * circleRadius;

        // discriminant
        double D = B * B - 4 * A * C;

        if ( D < 0 )
        {
            return new Point3D[ 0 ];
        }

        double t1 = ( -B - Math.Sqrt ( D ) ) / ( 2.0 * A );

        Point3D solution1 = new Point3D( linePoint0.X * ( 1 - t1 ) + t1 * linePoint1.X,
                                         linePoint0.Y * ( 1 - t1 ) + t1 * linePoint1.Y,
                                         linePoint0.Z * ( 1 - t1 ) + t1 * linePoint1.Z );
        if ( D == 0 )
        {
            return new Point3D[] { solution1 };
        }

        double t2 = ( -B + Math.Sqrt( D ) ) / ( 2.0 * A );
        Point3D solution2 = new Point3D( linePoint0.X * ( 1 - t2 ) + t2 * linePoint1.X,
                                         linePoint0.Y * ( 1 - t2 ) + t2 * linePoint1.Y,
                                         linePoint0.Z * ( 1 - t2 ) + t2 * linePoint1.Z );

        // prefer a solution that's on the line segment itself

        if ( Math.Abs( t1 - 0.5 ) < Math.Abs( t2 - 0.5 ) )
        {
            return new Point3D[] { solution1, solution2 };
        }

        return new Point3D[] { solution2, solution1 };
    }
4 голосов
/ 10 июля 2015

Не хватает репутации, чтобы комментировать ответ М. Каца, но его ответ предполагает, что линия может идти бесконечно в каждом направлении. Если вам нужны только точки пересечения СЕГМЕНТА линии, вам нужно, чтобы t1 и t2 были меньше единицы (на основе определения параметризованного уравнения). Пожалуйста, смотрите мой ответ в C # ниже: 

        public static Point3D[] FindLineSphereIntersections(Point3D linePoint0, Point3D linePoint1, Point3D circleCenter, double circleRadius)
    {

        double cx = circleCenter.X;
        double cy = circleCenter.Y;
        double cz = circleCenter.Z;

        double px = linePoint0.X;
        double py = linePoint0.Y;
        double pz = linePoint0.Z;

        double vx = linePoint1.X - px;
        double vy = linePoint1.Y - py;
        double vz = linePoint1.Z - pz;

        double A = vx * vx + vy * vy + vz * vz;
        double B = 2.0 * (px * vx + py * vy + pz * vz - vx * cx - vy * cy - vz * cz);
        double C = px * px - 2 * px * cx + cx * cx + py * py - 2 * py * cy + cy * cy +
                   pz * pz - 2 * pz * cz + cz * cz - circleRadius * circleRadius;

        // discriminant
        double D = B * B - 4 * A * C;

        double t1 = (-B - Math.Sqrt(D)) / (2.0 * A);

        Point3D solution1 = new Point3D(linePoint0.X * (1 - t1) + t1 * linePoint1.X,
                                         linePoint0.Y * (1 - t1) + t1 * linePoint1.Y,
                                         linePoint0.Z * (1 - t1) + t1 * linePoint1.Z);

        double t2 = (-B + Math.Sqrt(D)) / (2.0 * A);
        Point3D solution2 = new Point3D(linePoint0.X * (1 - t2) + t2 * linePoint1.X,
                                         linePoint0.Y * (1 - t2) + t2 * linePoint1.Y,
                                         linePoint0.Z * (1 - t2) + t2 * linePoint1.Z);

        if (D < 0 || t1 > 1 || t2 >1)
        {
            return new Point3D[0];
        }
        else if (D == 0)
        {
            return new [] { solution1 };
        }
        else
        {
            return new [] { solution1, solution2 };
        }
    }
2 голосов
/ 05 мая 2011

Вы можете использовать Wolfram Alpha, чтобы решить ее в системе координат, где сфера центрирована.

В этой системе уравнения:

Сфера: 

     x^2 + y^2 + z^2 = r^2

Прямая линия: 

    x = x0 + Cos[x1] t
    y = y0 + Cos[y1] t
    z = z0 + Cos[z1] t

Затем мы просим Вольфрама Альфу решить для t : (Попробуйте!)

и после этого вы можете снова перейти на исходную систему координат (простой перевод)

2 голосов
/ 04 мая 2011

Посмотрите на "пересечение сферы лучей" - один и тот же тест используется все время при трассировке лучей, и есть множество примеров в сети, и даже довольно много здесь на стеке потока.

1 голос
/ 04 мая 2011

Найдите решение двух уравнений в (x, y, z), описывающих линию и сферу.

Может быть 0, 1 или 2 решения.

  • 0 означает, что они не пересекаются
  • 1 означает, что линия является касательной к сфере
  • 2 означает, что линия проходит через сферу.
0 голосов
/ 01 августа 2016

У меня нет репутации, чтобы комментировать решение Ашавского, но проверка в конце потребовала немного доработки. 

if (D < 0)
    return new Point3D[0];
else if ((t1 > 1 || t1 < 0) && (t2 > 1 || t2 < 0))
    return new Point3D[0];
else if (!(t1 > 1 || t1 < 0) && (t2 > 1 || t2 < 0))
    return new [] { solution1 };
else if ((t1 > 1 || t1 < 0) && !(t2 > 1 || t2 < 0))
    return new [] { solution2 };
else if (D == 0)
    return new [] { solution1 };
else
    return new [] { solution1, solution2 };
0 голосов
/ 01 февраля 2015

Или вы можете просто найти формулу обоих:
линия: (x-x0)/a=(y-y0)/b=(z-z0)/c, которые представляют собой симметричные уравнения отрезка линии между точками, которые вы можете найти.
сфера: (x-xc)^2+(y-yc)^2+(z-zc)^2 = R^2.

Используйте симметричное уравнение, чтобы найти взаимосвязь между x и y и x и z.

Затем включите y и z в терминах x в уравнение сферы.
Затем найдите x, а затем вы можете найти y и z.

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

0 голосов
/ 20 октября 2014

Вот более краткая формулировка с использованием внутренних продуктов, менее 100 LOC и без внешних ссылок. Также был задан вопрос о линии, а не об отрезке.

Предположим, что сфера центрирована в C с радиусом r. Строка описывается P+l*D, где D*D=1. P и C - это точки, D - это вектор, l - это число.

Устанавливаем PC = P-C, pd = PC*D и s = pd*pd - PC*PC + r*r. Если s < 0 нет решений, если s == 0 есть только один, в противном случае их два. Для решений мы устанавливаем l = -pd +- sqrt(s), затем подключаемся к P+l*D.

...