Поместив луч выбора и объекты в одну систему координат, мы готовы проверить какие объекты пересекает луч. Поскольку объекты представлены сетками с треугольными ячейками, один из возможных способов заключается в следующем. Для каждого объекта мы перебираем элементы его списка граней и проверяем не пересекает ли луч какой-нибудь из этих треугольников. Если да, значит луч попал в тот объект, которому принадлежит треугольник.
Однако, выполнение проверки пересечения с лучом для каждого треугольника сцены требует много времени на вычисления. Более быстрый, хотя и менее точный метод — представить каждый объект с помощью ограничивающей сферы. Тогда мы выполняем проверку пересечения луча и ограничивающей сферы и тот объект, чью ограничивающую сферу пересекает луч, считается выбранным.
Луч выбора может пересекать несколько объектов. В этом случае выбранным считается самый близкий к камере объект, потому что дальние объекты закрываются им.
Зная центральную точку c и радиус r сферы, мы можем проверить находится ли точка p на поверхности сферы с помощью следующей простой формулы:
где p — это точка на сфере, если условие выполняется (рис. 15.3).
Рис. 15.3. Длина вектора p – c, обозначаемая как |p – c|, равна радиусу сферы, если точка p лежит на поверхности сферы. Обратите внимание, что на иллюстрации для простоты изображен круг, но идея работает и в трех измерениях
Чтобы определить, пересекает ли луч p (t) = p 0 + t u сферу и, если да, то где, мы подставляем формулу луча в уравнение сферы и ищем значение параметра t, удовлетворяющее уравнению сферы, что позволит нам найти точки пересечения.
Подставляем формулу луча в уравнение сферы:
и получаем квадратное уравнение:
где A = u Ч u , B = 2( u Ч ( p 0 – c )) и C = ( p 0 – c ) Ч ( p 0 – c ) – r 2 . Если вектор u нормализован, то A = 1.
Предполагая, что вектор u нормализован, получаем решения для t0 и t1:
На рис. 15.4 показаны возможные результаты для t0 и t1 и объяснено, что эти результаты означают с точки зрения геометрии.
Рис. 15.4. a) Луч проходит мимо сферы; и t0 и t1 мнимые числа б) Луч находится за сферой; и t0 и t1 отрицательные числа. в) Луч начинается внутри сферы; одно из решений положительное, а другое — отрицательное. Положительное решение соответствует единственной точке пересечения. г) Луч пересекает сферу; и t0 и t1 положительные числа. д) Луч касается сферы в единственной точке; в этом случае оба решения положительны и t0 = t1.
Приведенный ниже метод возвращает true, если переданный в первом параметре луч пересекает переданную во втором параметре сферу. Если луч проходит мимо сферы, метод возвращает false:
Конечно, мы уже показывали объявление структуры BoundingSphere, но для удобства приведем его здесь еще раз:
Доброго времени суток, Господа. Ребят, помогите решить проблему с Picking’ом. Уже 3 дня мудохаюсь, не могу сделать. Вот такой результат я имею:
Вот так передаю вершины на проверку пересечения луча:
А вот моя функция, которая проверяет пересечение грани куба в лучом:
Перевод луча в пространство куба — это правильно. Дальше можно проще.
Точка пересечения луча с верхней плоскостью (не с квадом):
R — это половина длины ребра куба. p1.y, естественно, = R, нам эта величина не требуется. Проверяем:
Верхнюю сторону ищем только если Pos.y > R, нижнюю — если Pos.y 11:41, 18 мая 2017
Изобретать велосипед не запрещено, но может попробовать обычный способ: В DirectXMath есть функция Intersects https://msdn.microsoft.com/en-us/library/windows/desktop/hh855922(v=vs.85).aspx которая не только определяет попадание луча в треугольник но и возвращает расстояние до него. С ее помощью можно организовать выбор объекта любой формы.
В DirectXMath есть функция Intersects
Я использую xnamath, и ради такой элементарщины, впринципе, переписывать движок на DirectXMath не очень охото
Что такое Pos здесь и Dir? Начало и направление луча? И почему p1.y = R?
bretbas > Что такое Pos здесь и Dir? Начало и направление луча? Да. Приведённые в пространство куба. bretbas > почему p1.y = R? Потому, что это в пространстве с нулём в центре куба и осями вдоль его граней. Верхняя грань находится на высоте R, p1.y будет равно R вне зависимости от места пересечения.
Mikle, понял. Спасибо, попробую
Сделал, все работает. Еще раз благодарен Mikle
Вот код. Луч должен обязательно быть в локальном пространстве объекта
Найти точку пересечения луча, выходящего из куба с гранью этого куба.
Известны координаты точек A и C (координаты — локальные для куба), известен размер куба.
Надо определить грань, которую пересекает луч и найти трёхмерную точку на этой грани (точка B).
Ищу наиболее быстрый и элегантный способ. Помогите, может кто знает.
P.S. Нашел пока только алгоритм для проверки пересечения луча с отдельным треугольником, но он работает криво и даже если его подправить — берёт слишком много инструкций: http://ideone.com/gYEcni
jabberx тест на пересечение луча с плоскостью, для 6 граней, затем взять ближайшую точку (sqrt можно не брать достаточно dist^2)
Dufrenite очень интересно, а что она возвращает? мне нужна трёхмерная точка
thevlad пока так и сделал, 3 грани заранее отбрасываю, но хотелось бы чего побыстрее
jabberx > а что она возвращает? мне нужна трёхмерная точка Окай.
float3 point1 = origin + ray * tNear; float3 point2 = origin + ray * tFar;
Но тут куб как я понял ААББ, а старт луча не обязательно в кубе. Но ведь луч можно трансформировать в локальное пространство куба и тогда будет все, как тебе нужно.
Вопрос по HLSL (я его не использую). Что делают функции: float3 min(float3, float3) float3 max(float3, float3) Что в них сравнивается? Длина? Или там выбираются большие/меньшие компоненты и собирается новый вектор?
jabberx > Или там выбираются большие/меньшие компоненты и собирается новый вектор?
Тест моего изначального грубого варианта, где считались пересечения с отдельными плоскостями: http://ideone.com/e4MMng Тест более изящного варианта, предложенного товарищами Dufrenite и fzr125: http://ideone.com/hL0UT5 (работает в
1.25 раз быстрее), Я его модифицировал, поскольку там два результата (point1, point2) — добавил проверку, позволяющую определять нужный результат (функция is_vecs_facing или см последнюю строчку здесь), но не уверен, что это лучший вариант. Думаю, по-нормальному это всё выглядело бы как-то так:
Алгоритм пересечения для базового куба Процесс пересечения луча с кубом по своей сути является алгоритмом Сайруса-Бека, описанным в разделе «Алгоритм Сайруса-Бека» главы 4, где прямая линия отсекается границами выпуклого окна в двумерном пространстве. Данный алгоритм был также использован для отсечения прямой линии отображаемым объемом камеры в главе 8. Основная идея заключается в том, что каждая плоскость куба определяет «внутреннее» и «внешнее» полупространства и что точка на луче лежит внутри этого куба тогда и только тогда, когда она лежит «внутри» каждого полупространства куба. Тогда пересечение луча с кубом сводится к определению интервала времени, в течение которого луч лежит внутри всех плоскостей куба.
Обозначим куб буквой Р. Протестируем луч поочередно с каждой плоскостью куба Р, вычисляя моменты времени, в которые луч или входит во внутреннее полупространство данной плоскости, или выходит из него. Мы будем отслеживать этот «возможный интервал» («candidate interval* — CI) — такой интервал времени, в который, на основе выполненных до данного момента тестов, луч может находиться внутри данного объекта. Этот интервал ограничен значениями времени tm и tout то есть CI = [rin, toiJ. По мере проверки каждой плоскости куба Р мы «усекаем» этот интервал, либо увеличивая rin, либо уменьшая tout. Если для какой-нибудь точки CI становится пустым, то луч должен пройти мимо данного объекта, определяя «досрочный выход». Если после проверки всех плоскостей куба Р мы обнаружим, что оставшийся интервал CI не пуст, то луч входит в объект в момент ta и выходит из него в момент tmt.
Рис. 14.12. Луч протыкает базовый куб (а); двумерный случай (6)
Для иллюстрации этого процесса на рис. 14.12, а показан пример, в котором луч входит в базовый куб при £ = 3,6 и выходит из него при г = 4,1. Тогда при завершении тестирования остается интервал С1 = [3,6, 4,1]. На рис. 14.12, б для простоты показан двумерный вариант того же процесса; здесь мы хотим найти пересечение луча с квадратом. С нашей «всевидящей» обзорной точки мы видим, что луч вначале соударяется с верхней плоскостью квадрата при г = 1,6 и входит во внутреннее полупростран-
Доброго времени суток, Господа. Возникла проблема, не могу понять как реализовать алгоритм, который позволяет определить, пересекает ли луч куб, или нет. Алгоритм, который определял, пересекает ли луч сферу я сделал, а вот с кубом, что-то не могу
Поможете? Имеются такие данные: Луч: его начало и направление Куб: Имеются все точки куба, и локальная матрица его расположения в мире.
Найти точку пересечения луча и плоскости Здравствуйте, помогите пожалуйста решить задачу. Предположим, что нам дан луч и плоскость в.
Точка пересечения луча и поверхности сферы Подскажите самый простой способ. Точка пересечения луча и поверхности сферы. Двумя точками в.
Как определить координаты пересечения луча и отрезка? Начало луча находится в точке A(x1, y1). Луч направлен под углом \alpha. Начало отрезка находится в.
Точка пересечения луча (прямой) с треугольником. Как найти точку пересечения луча (прямой) с треугольником в пространстве? Добавлено через 4 часа.
Проверка пересечения луча с анимационной моделью Если с не анимационными моделями проверять пересечение луча с треугольниками меша проблем не.
Найти элементы пересечения луча в матрице Всем доброго дня! Помогите пожалуйста найти элементы матрицы которые пересекает луч в виде матрицы.
Найти точки пересечения луча и окружности Given a sphere of radius sphereRadius, center point is sphereCenter and a ray with origin rayStart.
Нахождение координат пересечения луча с вертикальной плоскостью Здравствуйте, уважаемые форумчане! Работаю над выбором объекта в сцене с помощью центра экрана.
Доброго времени суток, Господа. Возникла проблема, не могу понять как реализовать алгоритм, который позволяет определить, пересекает ли луч куб, или нет. Алгоритм, который определял, пересекает ли луч сферу я сделал, а вот с кубом, что-то не могу
Поможете? Имеются такие данные: Луч: его начало и направление Куб: Имеются все точки куба, и локальная матрица его расположения в мире.
Найти точку пересечения луча и плоскости Здравствуйте, помогите пожалуйста решить задачу. Предположим, что нам дан луч и плоскость в.
Точка пересечения луча и поверхности сферы Подскажите самый простой способ. Точка пересечения луча и поверхности сферы. Двумя точками в.
Как определить координаты пересечения луча и отрезка? Начало луча находится в точке A(x1, y1). Луч направлен под углом \alpha. Начало отрезка находится в.
Точка пересечения луча (прямой) с треугольником. Как найти точку пересечения луча (прямой) с треугольником в пространстве? Добавлено через 4 часа.
Это очень древняя задачка. Фактически затертая даже не до дыр в любой книге наподобие “основы машинной графики” с оптимизированной математикой до предела… там и стоит искать ответы для рендера отполированные временем.
Как велик: 1) Анализ кандидата на пересечение. Описанная сфера вокруг куба. Проверять наверно квадрат расстояния от центра масс куба до луча.
2)Уточнение. Может при взгляде из камеры на куб это принадлежность точки многоугольнику будет быстрей уравнений.
Это матрица трансформаций. Определяет положение и вращение объекта в пространстве. Начальное положение объекта в точке (0,0,0) и вращение (0,0,0). Умножив каждую вершину на матрицу объекта, мы получим его положение и вращение в пространстве, где он сейчас находится. Используются матрицы для более эффективной работы с объектами, так как матрицы можно перемножать. Есть матрица положения, и матрица вращения. Мы перемножаем эти две матрицы, и получаем матрицу, которая содержит в себе две эти операции одновременно(положение, вращение). Затем, перемножаем каждую вершину объекта с этой матрицей, и вершина приобретает координаты, как будто ее переместили и повернули. Если бы не было матриц, нам бы пришлось вначале перемещать все вершины объекта, а потом вращать все вершины объекта, а это намного дольше, чем просто умножить на матрицу трансформаций Матрицы в основном используются в компьютерной графике.
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.
Bretbas, в моем посте 7 вы, видио, не обратили внимания на НЕРАВЕНСТВА. Теперь о вашем решении. Пп 1, 2 — совершенно правильные. Дальше вы делаете совершенно не нужные вещи. Какие-то нормализации, векторные произведения. Штуки это хорошие, но здесь не нужные. А надо такю Записываете уравнение грани ABCD: X = A +E1*u + E2*v (0 =0) Теперь ищем точку пересечения P = X Я надеюсь, понятно, что это 3 уравнения (по 1 на каждую координату)? И неизвестных у них 3 — u, v, t Вот и решаем эту систему любым подходящим методом — Гаусса, Крамера. Нашли эти u, v, t, Осталось только проверить неравенства 0 = 0 Если они все выполняются — пересечение есть. Хоть одно не выполняется — нету. Если какая-то место этих рассуждений окажется непонятной — спрашивайте
Добавлено через 8 минут Может быть вам будет интересно, что предложенная техника записи уравнений граней подходит и для параллелограммов. Для треугольных граней формула чуток другая X = A + u*E1 + v*E2, 0 Добавлено через 22 минуты
Как определить координаты пересечения луча и отрезка?