Узнайте, существует ли какой-либо конкретный треугольник в трехмерном пространстве из данной точки с произвольным числом других треугольников, потенциально на пути

Question

Я хотел бы написать функцию, которая возвращает «Истина», если треугольник (заданный его вершинами и нормальным) в трехмерном пространстве, видна из заданной точки в трехмерном пространстве (заданная ее х, у и z co'rds), учитывая, что другие треугольники в пространстве могут действовать как «блокирующие», которые останавливают вас видеть указанный треугольник от точки.

Под «видеть» и «видимые» я имею в виду, что можно подключить любой точки треугольника до точки наблюдения с прямым линии, которая не пересекают никаких блокирующих треугольников.

hopefully this shows what I mean

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

Мои два подхода наивы;

1) проецировать линию от точки наблюдения через каждую вершину потенциального «блокирующего» треугольника до некоторого очень большого радиуса (для моего приложения никакие треугольники не будут находиться на расстоянии более 1000 единиц от точки наблюдения, скажем так, я бы выберите 1001 единиц). Тогда у меня была бы область за трафиком с краями, описанными проецируемыми линиями, в которых объект не может быть замечен. Я сделаю это для всех блокировщиков, затем найду объединение всех этих областей и проверит, находится ли мой треугольник под одной из (потенциально многих) областей.

или

2) Опять стреляют линии для всех блокирующих вершин треугольника, найти точку, в которой эти линии пересекают плоскость, в которой треугольник испытуемого находится, чтобы получить проецируемый треугольник каждого блокатора в плоскости. Смешайте любые перекрывающиеся проецируемые треугольники в один многоугольник. Затем проверьте, что тестируемый треугольник не полностью находится внутри любого из проецируемых треугольников или объединенных полигонов.

Проблема с методом 1) заключается в том, что его трудно найти, если форма полностью закрыта трехмерным томом и еще сложнее объединить пересекающиеся трехмерные тома в один большой объем 3D.

Проблема с методом 2) бывают случаи, когда проецируемые линии через блокирующие вершины треугольника никогда не попадут в плоскость представляющего интерес треугольника. Нельзя просто игнорировать эти случаи, они все еще могут заглушить интересующий треугольник, они просто проливают бесконечную длинную тень на самолет.

Я опираюсь на метод 2, но, как я уже сказал, эти методы кажутся немного наивными, если кто-то может предложить более элегантное решение, это было бы очень интересно для меня! Описание или псевдокод является идеальным, в конце концов я надеюсь реализовать это в matlab или C++, но на данный момент позволяет держать вещи вообще!

Answer 1

Я бы тоже пошел с вашим вторым подходом, но с некоторыми изменениями.

Прежде всего, предположим, что вы проецируете свои треугольники на какой-то самолет. Здесь у вас есть несколько самолетов на выбор, но я не уверен, какой из них будет лучше для вас:

Вы можете проецировать все треугольники на свою испытательную плоскость треугольника. Таким образом, вы можете легко получить информацию, если треугольник окклюдера находится впереди или позади тестируемого. Недостатком является то, что, когда вы смотрите на угол скоса на свой испытанный треугольник, числовые ошибки растут и могут нарушить ваше решение.

Следующая опция, и я должен начать с нее, чтобы выбрать один из 6 выровненных по оси плоскостей. Представьте их как стены небесного ящика. В зависимости от относительного положения наблюдателя и треугольника вы можете выбрать один вдоль оси с большими расстояниями. Кроме того, выбор плоскости с выравниванием по оси может немного упростить вашу математику.

Следующая опция может быть использована плоскость, перпендикулярная линии между наблюдателем и центром треугольника. Этот параметр может свести к минимуму ошибки, если у вас есть треугольники, расположенные под крайним углом, но вам нужно будет проверить его самостоятельно.

Когда вы проецируете проецируемый треугольник, вы можете вычислить для него ограничивающий прямоугольник - это ваша область интереса, и вам не нужно ничего знать за пределами нее. Вы можете вычислить 4 плоскости, которые проходят через границы наблюдателя и прямоугольника, например, типичный вид усечения.

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

А вот самая важная часть:

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

Если вы решите все это, пожалуйста, имейте в виду, что ваши окклюдеры могут находиться за проверенным треугольником, поэтому вам нужно учитывать это. Самое простое решение - закрепить их с проверенной плоскостью треугольника и оставить только то, что перед ним.