Форум программистов, компьютерный форум, киберфорум
Наши страницы
Геометрия
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Bretbas
Каждому свое
520 / 206 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
1

Алгоритм определения пересечения луча куба

14.05.2017, 19:36. Просмотров 940. Ответов 20
Метки нет (Все метки)

Доброго времени суток, Господа.
Возникла проблема, не могу понять как реализовать алгоритм, который позволяет определить, пересекает ли луч куб, или нет.
Алгоритм, который определял, пересекает ли луч сферу я сделал, а вот с кубом, что-то не могу

Поможете?
Имеются такие данные:
Луч: его начало и направление
Куб: Имеются все точки куба, и локальная матрица его расположения в мире.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2017, 19:36
Ответы с готовыми решениями:

Точка пересечения луча и поверхности сферы
Подскажите самый простой способ. Точка пересечения луча и поверхности сферы. ...

Найти точку пересечения луча и плоскости
Здравствуйте, помогите пожалуйста решить задачу. Предположим, что нам дан...

Как определить координаты пересечения луча и отрезка?
Начало луча находится в точке A(x1, y1). Луч направлен под углом \alpha. Начало...

Пересечение луча и отрезка
Помогите, пожалуйста, хотя бы формулой. Дано: точки A, B, C, D, лежащие на...

Пересечение луча и цилиндра
Добрый день! Есть формула Точки цилиндра лежат не дальше чем r от оси...

20
eropegov
372 / 363 / 74
Регистрация: 30.01.2017
Сообщений: 1,015
14.05.2017, 21:28 2
Цитата Сообщение от Bretbas Посмотреть сообщение
Имеются все точки куба
Всех точек куба бесконечно много. Все вершины, наверное?
Цитата Сообщение от Bretbas Посмотреть сообщение
локальная матрица его расположения в мире
Что это такое? И зачем она вам, если уже есть "все точки"?
0
wlmn
23 / 23 / 3
Регистрация: 05.02.2017
Сообщений: 200
15.05.2017, 04:25 3
почему бы не найти точки пересечения с плоскостями граней Ax+By+Cz+D=0
и не подставить их в неравенства для других плоскостей (плоскость делит пространство на 2 части: A1x+B1y+C1z+D1>0 и <0)
Т.о. внутренность куба определяется 6 неравенствами.

Если хотя бы 1 из 6 найденных точек удовлетворяет всем неравенствам вида Ax+By+Cz+D<=0 (или >=0), то луч пересекает куб. Если нет такой точки, то не пересекает.
0
Excalibur921
756 / 430 / 69
Регистрация: 12.10.2013
Сообщений: 2,883
15.05.2017, 11:18 4
Цитата Сообщение от Bretbas Посмотреть сообщение
пересекает ли луч куб,
Это очень древняя задачка. Фактически затертая даже не до дыр в любой книге наподобие “основы машинной графики” с оптимизированной математикой до предела… там и стоит искать ответы для рендера отполированные временем.

Как велик:
1) Анализ кандидата на пересечение. Описанная сфера вокруг куба. Проверять наверно квадрат расстояния от центра масс куба до луча.

2)Уточнение.
Может при взгляде из камеры на куб это принадлежность точки многоугольнику будет быстрей уравнений.
0
Bretbas
Каждому свое
520 / 206 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
15.05.2017, 12:53  [ТС] 5
eropegov,
Всех точек куба бесконечно много. Все вершины, наверное?
Да, вершины. Извините

Что это такое? И зачем она вам, если уже есть "все точки"?
Это матрица трансформаций. Определяет положение и вращение объекта в пространстве. Начальное положение объекта в точке (0,0,0) и вращение (0,0,0). Умножив каждую вершину на матрицу объекта, мы получим его положение и вращение в пространстве, где он сейчас находится.
Используются матрицы для более эффективной работы с объектами, так как матрицы можно перемножать. Есть матрица положения, и матрица вращения. Мы перемножаем эти две матрицы, и получаем матрицу, которая содержит в себе две эти операции одновременно(положение, вращение). Затем, перемножаем каждую вершину объекта с этой матрицей, и вершина приобретает координаты, как будто ее переместили и повернули.
Если бы не было матриц, нам бы пришлось вначале перемещать все вершины объекта, а потом вращать все вершины объекта, а это намного дольше, чем просто умножить на матрицу трансформаций
Матрицы в основном используются в компьютерной графике.

wlmn,
почему бы не найти точки пересечения с плоскостями граней Ax+By+Cz+D=0
Вы имеете ввиду, рассматривать куб как 6 плоскостей, и составить неравенство? А что нужно подставлять из луча?
0
wlmn
23 / 23 / 3
Регистрация: 05.02.2017
Сообщений: 200
15.05.2017, 12:59 6
Bretbas, ну луч как можно описать?
как прямую (x-x0)/a = (y-y0)/b = (z-z0)/c
с тремя неравенствами x>x0, y>y0, z>z0 (ну или некоторые (или все) <)
Выражаете y,z через x, подставляете в уравнение плоскости, находите точку пересечения плоскости и прямой. Смотрите, удовлетворяет ли точка неравенствам.
1
Байт
Эксперт C
18964 / 12175 / 2544
Регистрация: 24.12.2010
Сообщений: 24,831
15.05.2017, 13:12 7
Цитата Сообщение от wlmn Посмотреть сообщение
ну луч как можно описать?
Имхо, компактнее луч описывается векторным уравнение
X = A + t*v, t>=0
где X (произвольная точка луча), А(начало луча) - радиус векторы, v - направляющий вектор луча, t(параметр) - действительное число (>=0)
Кстати, и грань куба ABCD можно описать подобным соотношением
X = A + AB*u + AC*v, 0 <= u,v <=1
Приравнивая и расписывая покоординатно получаем 3 уравнения относительно t, u, v. Остается проверить, что решение удовлетворяет неравенствам.
1
wlmn
23 / 23 / 3
Регистрация: 05.02.2017
Сообщений: 200
15.05.2017, 13:22 8
Байт, ну можно и так.
0
Байт
Эксперт C
18964 / 12175 / 2544
Регистрация: 24.12.2010
Сообщений: 24,831
15.05.2017, 13:25 9
Цитата Сообщение от wlmn Посмотреть сообщение
ну можно и так.
В самом деле все эквивалентно. Просто, имхо, предложенный подход позволяет написать программу с меньшим количеством разветвлений.
0
Bretbas
Каждому свое
520 / 206 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
16.05.2017, 08:21  [ТС] 10
wlmn, Байт, Ребят, я на самом деле не очень понял, что Вы мне рассказали. Скорее всего это от пробелов моих знаний в линейной алгебре.
Я делаю так:
1. Беру одну сторону куба ABCD.
2. Ищу два перпендикулярных вектора AB=E1 и AC=E2
3. Ищу векторное произведение E1xE2 и получаю вектор N, который перпендикулярен векторам E1 и E2.
4. Нормализую вектор N(n1, n2, n3) и соответственно получаю нормаль к плоскости ABCD
5. Расписываю параметрическое уравнение плоскости Ax +By + Cz + D = 0, где A = n1, B = n2, C = n3; Соответственно получаем уравнение вида n1x + n2y + n3z + D = 0
6. Подставляем любую точку нашей плоскости в формулу, и соответственно находим D.
Например подставим точку B(Bx, By, Bz) из нашей стороны куба: D = -n1*Bx - n2*By - n3*Bz
7. Теперь рассмотрим луч: P = P0 + t*U, где P0 - начало луча, U - его направление, t - параметр
8. Разложим наш луч x = P0x + t*Ux; y = P0y + t*Uy; z = P0z + t*Uz
9. Поставим в наше уравнение плоскости: n1(P0x + t*Ux) + n2(P0y + t*Uy) + n3(P0z + t*Uz) + D = 0
10. Найдем параметр t = -((P0 * N) + D) / (U * N)

Что дальше то? Проверить параметр на t>=0? Но мы рассматриваем же плоскость а не грань в данном случае, и нужно как-то еще ограничения искать относительно нашей стороны ABCD.
0
Symon
Эксперт по математике/физике
2071 / 1921 / 561
Регистрация: 29.09.2012
Сообщений: 3,960
Записей в блоге: 13
16.05.2017, 09:38 11
Цитата Сообщение от Bretbas Посмотреть сообщение
пересекает ли луч куб, или нет.
Дано множество М (шар, куб ...) и точка S вне этого множества. Определить, пересекает ли данный луч, исходящий точки S, множества М.
1. Берем некоторую плоскость (например, одну из координатных, или плоскость, перпендикулярную лучу, проходящему через центр фигуры...)
2. Находим центральную проекцию фигуры М из точки S - тень фигуры.
3. Луч, исходящий из точки S пересекает фигуру тогда и только тогда, если он пересекает тень фигуры.
4. Чтобы построить тень выпуклого многогранника достаточно спроектировать вершины и построить их выпуклую оболочку.
2
Байт
Эксперт C
18964 / 12175 / 2544
Регистрация: 24.12.2010
Сообщений: 24,831
16.05.2017, 11:42 12
Bretbas, в моем посте 7 вы, видио, не обратили внимания на НЕРАВЕНСТВА.
Теперь о вашем решении. Пп 1, 2 - совершенно правильные. Дальше вы делаете совершенно не нужные вещи. Какие-то нормализации, векторные произведения... Штуки это хорошие, но здесь не нужные.
А надо такю
Записываете уравнение грани ABCD: X = A +E1*u + E2*v (0 <=u <=1, 0<=v <= 1) Если бы не эти неравенства, мы получили бы уравнение всей плоскости. А с ними - именно квадрат (или даже прямоугольник, если длины векторов Е1, Е2 не равны)
Теперь Луч: P = P0 + t*U (t >=0)
Теперь ищем точку пересечения P = X
Я надеюсь, понятно, что это 3 уравнения (по 1 на каждую координату)?
И неизвестных у них 3 - u, v, t
Вот и решаем эту систему любым подходящим методом - Гаусса, Крамера...
Нашли эти u, v, t,
Осталось только проверить неравенства
0 <= u <= 1
0 <= v <= 1
t >= 0
Если они все выполняются - пересечение есть. Хоть одно не выполняется - нету.
Если какая-то место этих рассуждений окажется непонятной - спрашивайте

Добавлено через 8 минут
Может быть вам будет интересно, что предложенная техника записи уравнений граней подходит и для параллелограммов. Для треугольных граней формула чуток другая
X = A + u*E1 + v*E2, 0 <= u+ v <= 1

Добавлено через 22 минуты
Цитата Сообщение от Symon Посмотреть сообщение
Берем некоторую плоскость...
Да, ваш метод вычислительно проще. А главное, он универсальнее.
1
Bretbas
Каждому свое
520 / 206 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
17.05.2017, 09:15  [ТС] 13
Байт,

Итак, вот что у меня получилось:
P0x + t * Ux = Ax + u * E1x + v * E2x;
P0y + t * Uy = Ay + u * E1y + v * E2y;
P0z + t * Uz = Az + u * E1z + v * E2z;

где
P(P0x, P0y, P0z) - Начало луча;
U(Ux, Uy, Uz) - Направление луча;
A(Ax, Ay, Az) - Одна из точек нашей грани куба
E1 = AB; E2 = AC - Вектора нашей грани

Теперь приводим вот к такому виду:
t * Ux - u * E1x - v * E2x = Ax - P0x;
t * Uy - u * E1y - v * E2y = Ay - P0y;
t * Uz - u * E1z - v * E2z = Az - P0z;

Я так понимаю, что нужно как-то составить матрицу, чтобы решить это уравнение относительно t, u, и v?
Припоминаю, мы такое делали на первом курсе линейной алгебры...

Добавлено через 11 часов 30 минут
Вот мое решение. Пока не проверял:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
bool isIntersectQuad(   const XMVECTOR& A, 
                const XMVECTOR& B, 
                const XMVECTOR& C, 
                const XMVECTOR& D, 
                const XMVECTOR& originRay, 
                const XMVECTOR& dirRay 
                )
{
    const XMVECTOR E1   =   A - B;
    const XMVECTOR E2   =   A - C;
    const XMVECTOR M    =   A - originRay;
 
    const float h1  = M.x; const float h2 = M.y; const float h3 = M.z;
    const float a1  = dirRay.x; const float a2 = dirRay.y; const float a3 = dirRay.z;
    const float b1  = E1.x; const float b2 = E1.y; const float b3 = E1.z;
    const float c1  = E2.x; const float c2 = E2.y; const float c3 = E2.z;
 
    float det = a1*b2*c3 - a1*b3*c2 + b1*c2*a3 - b1*c3*a2 + c1*a2*b3 - c1*a3*b2;
    float detx = h1*b2*c3 - h1*b3*c2 + b1*c2*h3 - b1*c3*h2 + c1*h2*b3 - c1*h3*b2;
    float dety = a1*h2*c3 - a1*h3*c2 + h1*c2*a3 - h1*c3*a2 + c1*a2*h3 - c1*a3*h2;
    float detz = a1*b2*h3 - a1*b3*h2 + b1*h2*a3 - b1*h3*a2 + h1*a2*b3 - h1*a3*b2;
 
    float t = detx / det;
    float u = dety / det;
    float v = detz / det;
 
    if( ( u >= 0 ) && ( u <= 1 ) && ( v >= 0 ) && ( v <= 1 ) && ( t >= 0 ) )
        return true;
 
    return false;
}
0
Байт
Эксперт C
18964 / 12175 / 2544
Регистрация: 24.12.2010
Сообщений: 24,831
17.05.2017, 12:43 14
Bretbas, ход решения верен.
0
Bretbas
Каждому свое
520 / 206 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
17.05.2017, 20:10  [ТС] 15
Байт,
ход решения верен.
ход то верный, только что-то он неважно работает.
Вот результат:


Вот так отправляю грани на проверку куба:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const auto& verticesMesh =mesh.vertices;
bool isIntersect = false;
for( auto i = 0; i < mesh.numVertices; i += 4 )
{
    const auto vertex1 = verticesMesh[i];
    const auto vertex2 = verticesMesh[i + 1];
    const auto vertex3 = verticesMesh[i + 2];
    const auto vertex4 = verticesMesh[i + 3];
 
    XMVECTOR A      =   XMVectorSet( vertex1.pos.x, vertex1.pos.y, vertex1.pos.z, 1.0f );
    XMVECTOR B      =   XMVectorSet( vertex2.pos.x, vertex2.pos.y, vertex2.pos.z, 1.0f );
    XMVECTOR C      =   XMVectorSet( vertex3.pos.x, vertex3.pos.y, vertex3.pos.z, 1.0f );
    XMVECTOR D      =   XMVectorSet( vertex4.pos.x, vertex4.pos.y, vertex4.pos.z, 1.0f );
 
    //A = XMVector3TransformCoord( A, globalMatrix );
    //B = XMVector3TransformCoord( B, globalMatrix );
    //C = XMVector3TransformCoord( C, globalMatrix );
    //D = XMVector3TransformCoord( D, globalMatrix );
 
    if( isIntersectQuad( A, B, C, D, rayOrigin, rayDir ) )
    {
        isIntersect = true;
        componentMaterial -> setMaterial( _selectedMaterial );
        break;
    }
}
Кстати такая же проблема, когда начинаю проверять не квадраты, а треугольники вот такой функцией:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
bool isIntersectTriangle(   const XMVECTOR& v0, 
                    const XMVECTOR& v1, 
                    const XMVECTOR& v2, 
                    const XMVECTOR& originRay, 
                    const XMVECTOR& dirRay 
                )
{
    const XMVECTOR E1   =   v1 - v0;
    const XMVECTOR E2   =   v2 - v0;
    const XMVECTOR M    =   originRay - v0; 
 
    const float h1  = M.x; const float h2 = M.y; const float h3 = M.z;
    const float a1  = dirRay.x; const float a2 = dirRay.y; const float a3 = dirRay.z;
    const float b1  = E1.x; const float b2 = E1.y; const float b3 = E1.z;
    const float c1  = E2.x; const float c2 = E2.y; const float c3 = E2.z;
 
    float det = a1*b2*c3 - a1*b3*c2 + b1*c2*a3 - b1*c3*a2 + c1*a2*b3 - c1*a3*b2;
    float detx = h1*b2*c3 - h1*b3*c2 + b1*c2*h3 - b1*c3*h2 + c1*h2*b3 - c1*h3*b2;
    float dety = a1*h2*c3 - a1*h3*c2 + h1*c2*a3 - h1*c3*a2 + c1*a2*h3 - c1*a3*h2;
    float detz = a1*b2*h3 - a1*b3*h2 + b1*h2*a3 - b1*h3*a2 + h1*a2*b3 - h1*a3*b2;
 
    float t = -detx / det;
    float u = dety / det;
    float v = detz / det;
    
    if( ( u >= 0 ) && ( u <= 1 ) && ( v >= 0 ) && ( v <= 1 ) && ( t >= 0 ) )
        return true;
 
    return false;
}
Не пойму, в чем может проблема...уже 3 дня мудохаюсь с этим
0
Байт
Эксперт C
18964 / 12175 / 2544
Регистрация: 24.12.2010
Сообщений: 24,831
17.05.2017, 20:17 16
Лучший ответ Сообщение было отмечено Bretbas как решение

Решение

Цитата Сообщение от Bretbas Посмотреть сообщение
только что-то он неважно работает.
Пройтись отладчиком не пробывал?
0
Excalibur921
756 / 430 / 69
Регистрация: 12.10.2013
Сообщений: 2,883
17.05.2017, 20:52 17
Цитата Сообщение от Bretbas Посмотреть сообщение
уже 3 дня мудохаюсь с этим
Набрать в гугле "Intersection ray cube" ?
0
Bretbas
Каждому свое
520 / 206 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
19.05.2017, 21:46  [ТС] 18
Короче сделал легче:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
bool isIntersectionCube( const XMVECTOR& originRay, const XMVECTOR& dirRay, const float sizeOfSide )
{
    float d = sizeOfSide / 2;
    float x, z, y;
 
    // Верхняя сторона
    x = originRay.x + dirRay.x * ( d - originRay.y ) / dirRay.y;
    z = originRay.z + dirRay.z * ( d - originRay.y ) / dirRay.y;
    if( ( x < d ) && ( x > -d ) && ( z < d ) && ( z > -d ) )
        return true;
 
    // Нижняя сторона
    x = originRay.x + dirRay.x * ( -d - originRay.y ) / dirRay.y;
    z = originRay.z + dirRay.z * ( -d - originRay.y ) / dirRay.y;
    if( ( x < d ) && ( x > -d ) && ( z < d ) && ( z > -d ) )
        return true;
 
    // Правая боковая сторона
    z = originRay.z + dirRay.z * ( d - originRay.x ) / dirRay.x;
    y = originRay.y + dirRay.y * ( d - originRay.x ) / dirRay.x;
    if( ( z < d ) && ( z > -d ) && ( y < d ) && ( y > -d ) )
        return true;
 
    // Левая боковая сторона
    z = originRay.z + dirRay.z * ( -d - originRay.x ) / dirRay.x;
    y = originRay.y + dirRay.y * ( -d - originRay.x ) / dirRay.x;
    if( ( z < d ) && ( z > -d ) && ( y < d ) && ( y > -d ) )
        return true;
 
    // Задняя сторона
    x = originRay.x + dirRay.x * ( d - originRay.z ) / dirRay.z;
    y = originRay.y + dirRay.y * ( d - originRay.z ) / dirRay.z;
    if( ( x < d ) && ( x > -d ) && ( y < d ) && ( y > -d ) )
        return true;
 
    // Передняя сторона
    x = originRay.x + dirRay.x * ( -d - originRay.z ) / dirRay.z;
    y = originRay.y + dirRay.y * ( -d - originRay.z ) / dirRay.z;
    if( ( x < d ) && ( x > -d ) && ( y < d ) && ( y > -d ) )
        return true;
 
    return false;
}
Луч должен быть в локальном пространстве объекта
0
Nacuott
1404 / 697 / 105
Регистрация: 24.02.2013
Сообщений: 1,745
Записей в блоге: 12
21.05.2017, 11:15 19
Проще всего сделать так. См.картинку.
Зрячим должно быть ясно - если луч попадает в шестигранник abcdef, то луч пересекает куб, в противном случае-нет.
1
Миниатюры
Алгоритм определения пересечения луча куба  
Nacuott
1404 / 697 / 105
Регистрация: 24.02.2013
Сообщений: 1,745
Записей в блоге: 12
23.05.2017, 19:07 20
Выше, в посту, описка-вместо шестигранник - шестиугольник abcdef.
1
23.05.2017, 19:07
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2017, 19:07

Отражение луча от точки
Найти отражение луча от точки при известной нормали к этой точке. Луч задается...

Получить направление отраженного луча
Есть луч и отрезок. Луч падает на отрезок. Нам известна точка начала луча,...

Найти пересечение луча и отрезка
Здравствуйте. Я не силён в математике, поэтому прошу помощи. Нужно найти...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru