Пересечение двух тел в пространстве

Привет всем!
У меня есть небольшое увлечение - иногда делаю карты к сетевым 3д бегалкам, конкретнее - quake3 и alien arena. Использую редактор карт GTKRadiant 1.5.0.
При создании своей последней карты к АА я столкнулся с проблеммой ее компиляции.

Вкратце суть мэппинга - рисуем пространственные элементы (стены, пол и потолок), т.е. окружение, где потом будем бегать в игре. Эти пространственные элементы (браши) могут быть пирамидами, призмами и сложными пространственными многогранниками.

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

И вот я решил сделать программу, которая бы находила эти пересечения. Результатом работы в редакторе GTKRadiant (еще до компиляции) является файл *.map. Это текстовый файл исходных данных. Не буду описывать его структуру. Скажу только, что на данном этапе создания проги, она считывает указанный файл *.map и формирует массив координат узлов каждого браша.

А дальше - тупик. Нужен какой то алгоритм, по которому можно определить пересекаются ли 2 произвольных браша или нет.

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

Мозгов на решение у меня видимо не хватает . Подключайтесь пожалуйста!

0

Многогранники выпуклые?

0

да, браши могут иметь только выпуклые углы

0

Пересечение двух многогранников эквивалентно выполнению хотя бы одного из условий:
1. Вершина одного многогранника находится внутри другого
2. Ребро одного многогранника пересекает грань другого


Первое проверяется по аналогии с плоским случаем (там пользуемся ориентированными площадями) - с помощью ориентированных объемов.

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

Это решение жутко громоздкое, думаю, существует более простое. Буду рад увидеть его.
(Если вдруг рискнете реализовать это - могу более подробно описать любой момент)

1

Смотри что есть у меня может поможет!!Вот сама тема с заданием https://www.cyberforum.ru/orde... 38869.html и кидаю прогу как мне это реализовали, может поможет что то.....
P.S. ______________________________________
Не забываем про поднятие репутации!!

Вложения

main1.rar (1.5 Кб, 42 просмотров)

1

Спасибо за помощь! Надо подумать над этим.

При тестировании своей проги выявил баг. Структура файла *.map такова:

...
...
...

// entity 0
{
"classname" "worldspawn"
"sky" "martian"
// brush 1
{
( 448 -608 448 ) ( 448 -768 448 ) ( 0 -608 448 ) arena5/bricks4_1 0 0 0 1 1
...
...
...

Три группы скобок - это координаты трех точек, образующих одну плоскость (грань) браша, таким образом приведенная строка файла описывает одну плоскость браша N1. В призме будет 6 граней и, соответственно, 6 строк в файле.
Используя данные одной строки файла можно составить уравнение плоскости, образованной тремя точками.

Координаты узлов каждого браша получал решением системы из трех уравнений плоскостей (узлы браша - это ни что иное, как точка пересечения трех плоскостей, граней браша).

Если браш - это куб или призма, получим в итоге 6 уравнений плоскостей и 8 точек - узлов.

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

Поиск таких "мнимых" узлов еще не решен в программе. Думаю искать их по признаку - на прямой, проходящей через 2 узла браша, не может быть третьего узла, т.е. не должно быть так, что 3 узла лежат на одной прямой.

Решу эту задачу, потом займусь самым сложным - проверкой пересечения брашей.

Миниатюры

 

0