qweqweqe123123

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

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

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

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

где Р(u,v) и Q(s,t) — параметрические уравнения пересекающихся поверхностей. Уравнение (7.50) распадается на три скалярных уравнения с четырьмя неизвестными: и, v, s и t. Решение этой системы требует присвоения произвольного значения одному из параметров. При этом получаются значения параметров, соответвующие точке на кривой пересечения. Изменение выбранного произвольного значения дает все остальные точки кривой пересечения. Недостаток этого метода в том, что его сходимость зависит от начальных приближений неизвестных в уравнении (7.50) [49]. Более того, он не всегда позволяет найти все кривые пересечения. Другими словами, при больших интервалах изменения произвольно за- даваемого параметра некоторые кривые могут быть потеряны полностью, а некоторые — частично.

Методы из второй категории основаны на теории последовательного деления [37]. каждая поверхность последовательно делится на множество частей до тех пор, пока каждая из них не будет представлять собой нечто близкое к плоскому четырехугольнику. Затем четырехугольники одной поверхности проверяются на пе- ресечение с четырехугольниками другой поверхности. В результате получаются пары пересекающихся четырехугольников, а точки прямых, по которым они непересекаются, дают хорошее начальное приближение для уравнения (7.50). Однако может оказаться непросто проверять нары четырехугольников в правильной последовательности так, чтобы точки пересечения образовывали кривые. Для прреодоления этой проблемы был предложен альтернативный подход [124, 90). В методе Пенга из всех четырехугольников пересекающихся поверхностей выбирается лишь одна пересекающаяся пара, которая дает первый сегмент кривой пересечения. Один из концов этого сегмента берется в качестве начальной точки т, которой производится поиск следующей точки пересечения. Другими словами, ищется новая пара четырехугольников, которая даст соседний сегмент кривой пересечения, одним из концов которого будет начальная точка поиска. Пересечение новой пары четырехугольников даст две точки, одна из которых берется в качестве нового конца кривой, от которого начинается поиск следующей пары четырехугольников. Пенг хранил четырехугольники в квадрантном дереве(quadtree), предложенном Саметом [135] для повышения эффективности поиска соседней пары. Процедура поиска продолжается до тех пор, пока не будет достигнута одна из границ поверхности, после чего поиск начинается с другого конца первого сегмента. Точные координаты точек пересечения получаются решением уравнения (7.50) с использованием концов сегментов в качестве начального приближения. Эта процедура повторяется со всеми начальными сегментами до тех пор, пока не будут найдены все кривые. В приложении К мы расскажем, каким образом следует искать все сегменты кривых пересечения.

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

 


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

Смотрите также