Я давно хотел создать трехмерный движок с нуля как задачу кодирования с конечной целью - реализовать его на фантастической консоли.
Лучший (то есть самый простой?) Способ, который я нашел, был raytracing / raycasting. Я не нашел много, ища в Интернете алгоритмы лучевой передачи, только находя проблемы точки в многоугольнике (которые только говорят мне, пересекает ли луч многоугольник или нет, не совсем мой интерес, так как у меня не было бы информации о первом пересечении и при этом у меня не было бы точек пересечения).
Единственное решение, которое я мог придумать, - это грубое принуждение луча, перемещая его с небольшими интервалами, и каждый раз проверять, занята ли эта точка чем-то или нет (для этого потребовалось бы заполнить фигуры и не дать мне иметь 2D-фигуры). так как они никогда не будут отображены, хотя ни одна из них не является проблемой). Тем не менее, это выглядит слишком сложно с точки зрения производительности.
Насколько я знаю, большинство из этих проблем решаются с помощью линейной алгебры, но я не настолько компетентен, чтобы самостоятельно строить решение. Есть ли у этой проблемы практическое решение?
РЕДАКТИРОВАТЬ: Я только что нашел алгебраическое решение в 2D, которое может быть расширено в 3D. Идея такова:
- Для каждого ребра проверьте, находится ли одна из двух вершин в поле зрения (т. Е. Если O - начало каждого луча, а P - вершина, вы должны сначала проверить, что точка находится внутри дальней точки прицел, а затем, меньше ли угол с вектором вперед, чем угол зрения). Если хотя бы одна из двух вершин находится внутри поля зрения, добавьте их в массив E.
- Если у нас есть массив R лучей для стрельбы и массив массивов I информации о точках попадания, мы можем выполнить цикл для каждого луча в R и для каждого ребра в E, а затем сохранить f (луч, ребро) в I где f - это функция, которая дает нам информацию о том, столкнулись ли луч и край и где они произошли.
- f использует базовую линейную алгебру: и луч, и ребро для всех целей являются двумя сегментами. Два сегмента - это просто части двух линий. Скажем, если ребро имеет вершины A и B (AB - вектор, который идет от A до B), и если дальняя точка называется P (OP - вектор, который идет от O к P). Мы можем создать две строки, r и s, определенные A + ηAB и O + λOP. После того, как мы проверим, являются ли r и s параллельными (проверьте, равно ли абсолютное значение точечного произведения AB и OP норме AB, умноженной на норму OP), тривиально получить значения для η и λ.
- Теперь, если η <0 ИЛИ η> 1, имеем, что два сегмента не сталкиваются.
- После того, как мы сделали это для каждого луча и каждого ребра, мы сравниваем каждый элемент в каждом массиве i в I, чтобы увидеть, какой из них имеет наименьшее λ. Самая низкая λ несет первое столкновение и, следовательно, данные для отображения на экране.
Все здесь - линейная алгебра, хотя я боюсь, что она все еще может быть тяжелой в вычислительном отношении, поскольку многое происходит, и она все еще только 2D.