Пересечение поверхностей

[Igors]

Здравствуйте

Есть полигоны (только треугольники), нужно разбить их в местах где они пересекают друг друга. Задача очень близка к boolean, но в данном случае цель - улучшение качества карты освещенности. Сам инструмент collision detection у меня есть. Я могу определять что ребро и/или полигон пересекает другой полигон, могу найти точки пересечения. Проблема в том что делать когда пересечения найдены и как вообще организовать данные. Например, один большой полигон (такой как пол или потолок) может пересекаться с очень многими другими. Что мне делать с найденными отрезками пересечений? Как собрать их в новые полигоны?

Идеи, предложения?

Заранее спасибо

[spectre71]

1) Какого типа пересечения, например в 2-х или в 3-х измерениях
2) Соответсвенно по какому принципу разбивка и сборка новых(очень желательна картинка)
3) Какова цель(не вдаваясь в предметную область)
4) Какие ограничения

[Igors]

1) Какого типа пересечения, например в 2-х или в 3-х измерениях
2) Соответсвенно по какому принципу разбивка и сборка новых(очень желательна картинка)
3) Какова цель(не вдаваясь в предметную область)
4) Какие ограничения

1) в 3-х измерениях
2) Никаких принципов пока нет - это и есть цель/тема обсуждения. Пока я умею находить точки/отрезки пересечений.
3) Цель - та же геометрия но с новыми вершинами (вертексами) в местах пересечений. Для этого надо построить новые треугольники.
4) Гарантируется что все исходные полигоны корректны (планарны). Все в памяти (примерно до 12 Gb) свапа на диск нет.

Edit: хотел "прикрепить картинку" а она что-то "не прикрепляется"   Наверное что-то не так делаю

[spectre71]

1) Все-таки исходные полигоны или треугольники.
2) Результатирующие - только треугольники?

Админы! Похоже в данном разделе вложения файлов не делаются .  Это как-то фигово!
Как вариант, можно разместить какртинку на сайте, например здесь http://www.radikal.ru/ и дать ссылку.

[Igors]

1) Все-таки исходные полигоны или треугольники.
2) Результатирующие - только треугольники?

Админы! Похоже в данном разделе вложения файлов не делаются .  Это как-то фигово!
Как вариант, можно разместить какртинку на сайте, например здесь http://www.radikal.ru/ и дать ссылку.

Понял, разместил, даю ссылку
http://i022.radikal.ru/0908/b0/b948c7d4e4f7.png

Для простоты полагаем что все состоит из треугольников имеющих представительную площадь. Например на картинке каждый квадрат состоит из 2 треугольников. Результат должен быть в том же формате - корректная геометрия. 

[spectre71]

1) Имем тругольник (твое допущение)
2) Имеем 2 точки на нем соединенные отрезком
Случаи:
0) Вырожденные случаи(обе точки за пределами или на одном ребре) - разбиения нет
Исключая вырожденные:
1) точки совпадают - разбиение простое, от точки к вершинам
2) одна из точек совпадает с вершиной - разбиение простое, от внутренней точки к вершинам
3) обе точки на разных ребрах - имеем треугольник и четырехугольник. Задача разбить четырехугольник.
4) одна на ребре одна внутри - можно свести к случаю 3 (продолжением отрезка до ребра)
5) обе внутри - можно свести к случаю 3 (продолжением отрезка до ребер)
Остается задача разбить четырехугольник, что можно сделать несколькими способами.

Если есть особые критерии(?) к получаемым при разбивке треугольникам, то разбивка в каждом из 5 случаев может усложниться.

[Igors]

1) Имем тругольник (твое допущение)
2) Имеем 2 точки на нем соединенные отрезком

Это только очень частный случай. А представьте себе какая-то ваза стоит на полу и немного "вдавлена" в пол. Тут мы имеем сотни отрезков пересечения. Очевидно что пытаться классифицировать все случаи бесполезно, нужна более общая "engine". Какая?

[spectre71]

1) Имем тругольник (твое допущение)
2) Имеем 2 точки на нем соединенные отрезком

Это только очень частный случай. А представьте себе какая-то ваза стоит на полу и немного "вдавлена" в пол. Тут мы имеем сотни отрезков пересечения. Очевидно что пытаться классифицировать все случаи бесполезно, нужна более общая "engine". Какая?

Ты наверное имеешь ввиду что треугольник может иметь несколько пересечений? Это я проглядел, здесь посложнее.
Но тебе все равно нужно сводить к разбивке отдельных треугольников(по отрезкам пересечений на нем), иначе никак.
Задача сводиться к нахождению всех отрезков для треугольника(насколько я понял ты ее решил).
И собственно разбиению по ним.
Правильно я понял?

[Igors]

1) Имем тругольник (твое допущение)
2) Имеем 2 точки на нем соединенные отрезком

Это только очень частный случай. А представьте себе какая-то ваза стоит на полу и немного "вдавлена" в пол. Тут мы имеем сотни отрезков пересечения. Очевидно что пытаться классифицировать все случаи бесполезно, нужна более общая "engine". Какая?

Ты наверное имеешь ввиду что треугольник может иметь несколько пересечений? Это я проглядел, здесь посложнее.
Но тебе все равно нужно сводить к разбивке отдельных треугольников(по отрезкам пересечений на нем), иначе никак.
Задача сводиться к нахождению всех отрезков для треугольника(насколько я понял ты ее решил).
И собственно разбиению по ним.
Правильно я понял?

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

[spectre71]

Ты наверное имеешь ввиду что треугольник может иметь несколько пересечений? Это я проглядел, здесь посложнее.
Но тебе все равно нужно сводить к разбивке отдельных треугольников(по отрезкам пересечений на нем), иначе никак.
Задача сводиться к нахождению всех отрезков для треугольника(насколько я понял ты ее решил).
И собственно разбиению по ним.
Правильно я понял?

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

Извини, но в данной предметной области я слябо шарю. Так что, не могу однозначно интерпретировать твой ответ. Начни сначала, постарайся абстрагироваться и описать задачу доступно(вне предметной области), это и тебе поможет в решении задачи.

[Igors]

Извини, но в данной предметной области я слябо шарю. Так что, не могу однозначно интерпретировать твой ответ. Начни сначала, постарайся абстрагироваться и описать задачу доступно(вне предметной области), это и тебе поможет в решении задачи.

Просто есть "информация о пересечениях" - известно что на поверхности некоторых треугольников есть отрезки - там где его пересекли другие треугольники. Задача на основании этой информации создать новые треугольники - корректную поверхность без дырок и перехлестов.

Пришлось читать теорию, пока вижу есть такой алгоритм Деланэ (Delaunay), но он не все делает что мне надо. Учу дальше...