Метод поиска линии пересечения двух поверхностей

[anpoit00]

Здравствуйте!
Вот стоит проблема нахождения линии пересечения двух поверхностей.
Поверхности заданы последовательным набором треугольников.
Сначала попробовал решить проблему аналитически: находил точку пересечения каждого ребра с противоположной поверхностью. Однако в этом случае происчодит неточний расчёт т.к. цоцедние точки пересечения соединяются прямой а долгни кривой. В тоже время я могу описать поверчность параметрически (Nurns) т.к. у меня есть вершины треуголников. Как я понимаю результатом пересечения двух пар. поверхностей должна являться тоже пар. кривая которую можно перевески в декартовие координаты.



Вопрос 1: Знает ли кто такой метод?

спасибо

http://www.gamedev.ru/files/images/?id=60229

[anpoit00]

http://www.gamedev.ru/files/images/?id=60235

[uni]

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

Для поверхностей, у которых известны их уравнения F(x)=0, можно построить численно линию пересечения на основе знания одной стартовой начальной точки на линии пересечения и векторов нормалей к поверхностям (они берутся из уравнений). Векторное перемножение этих нормалей даст направление движения вдоль линии пересечения поверхностей, а начальная точка позволит вычислить её численно путём решения диффура, построенного на основе полученного вектора производных (касательного вектора линии пересечения).

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

[maksevrodim]

Вряд ли я такую задачу осилю...
-------------
кнр

[kolas]

Для начала нужно построить пространственное дерево (например можно R-tree), чтобы алгоритм не был полиномиальным. Затем найти все отрезки для пересеченных треугольников, тоже сложить их в дерево, и найти связанные отрезки. В итоге алгоритм будет O(N log N).