Программная реализация алгоритма Кируса-бека

Кусочно–аналитическая граничная модель твердого тела может быть представлена в виде четырехуровневой иерархической графической структуры. Тело Т представляется множеством органичивающих его граней Т = {a₁, a₂, …, a_n}; каждая грань задается циклом ограничивающих его ребер и а = <l₁, l₂, ... , l_m> и нормалью n, направленной из тела; каждое ребро – двойкой точек начала и конца l_i = <А, В> и каждая точка – тройкой координат в трехмерном пространстве А = (X,Y,Z).

Для реализации аналитических операций над гранями, ограничивающими тело для каждой плоской грани задается четверка коэффициентов A, B, C, D, однозначно определяющих уравнение плоскости – носителя.

Приведенная модель может быть реализована в  виде графа. В вершинах первых четырех  уровней (I – IV) размещаются ссылки на элементы нижних уровней (I уровень – тело, II уровень – отсеки граней, III уровень – ребра, IV уровень –вершины), на уровне V записываются значения координат вершин циклов граней, на уровне II для каждой грани хранится ссылка на координаты.

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

Запись  координат вершин – 24 слова, запись данных о коэффициентах уравнений носителей граней – 24 слова, число ссылок первого уровня – 6, второго, третьего и четвертого– по 24, итого ссылок– 78.

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

Алгебрологическая граничная модель.

Наряду  с кусочно–аналитическими моделями в системах моделирования твердых тел используют алгебрологические модели или модели полупространств. Их применяют для описания объектов сложной структуры, ограниченных отсеками поверхностей, имеющих аналитическое представление. Алгебрологические граничные модели АЛМ строятся с помощью теории множеств, булевой алгебры и R–функций. Алгебрологическая модель объекта – совокупность уравнений ориентированных поверхностей, теоретико–множественная формула Т и параметры системы координат объекта S:

  М={{ST}, M_pⁱ }, I = 1, 2, ..., n.

В качестве булевых функций используется конъюнкция, дизъюнкция и отрицание. Переменные булевых функций принимаюn значения 1 и 0, соответствующих понятиям "истинно" и "ложно". В качестве ограничивающих тело граней G_i принимаются двусторонние поверхности Pi, заданные уравнениями Pi=f(X,Y,Z).

Они разделяют пространство на положительные D_i и отрицательные D_i области, определяемые неравенствами:

  f_i(x, y, z) ³ 0; f_i(x,y,z) < 0.

Внутренние  точки объекта типа "твердое  тело" принадлежат области с  неотрицательными значениями выражения. Из областей Di и Di с помощью теоретико–множественных операций можно образовать геометрические объекты. Это выполняется с помощью процедуры задания для некоторого количества n областей D_i булевой функции:

F(D₁, D₂, ... , D_n). (1)

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

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

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

Системы моделирования твердого тела используют развитую технику интерактивного взаимодействия при формировании и редактировании моделей геометрии. Наряду с наиболее распространенной в таких системах техникой синтеза из БЭФ и их комбинацией (комплексов) применяют кинематический метод, или метод перемещения контура по образующей.

При этом, как правило, формируется кусочно–аналитическая модель или граничное представление объекта. Линейное перемещение прямой порождает плоскость, линейное перемещение окружности – цилиндрическую поверхность, вращение окружности – тороидальную или сферическую поверхность в зависимости от расположения оси вращения.

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

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

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

Моделирование скульптурных поверхностей.

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

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

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

Задачи  интерполяции связаны с поиском гладких кривых (сплайнов) или поверхностей, проходящих через множество заданных точек.

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

Существуют  два основных способа представления  кривых: с помощью функций переменных x, y и z и функций некоторого параметра t. В первом случае, чтобы определить точки (x,y,z) на кривой, приходится иметь дело с функциями вида

x = x, y = f(x), z = g(x).

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

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

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

Параметрической кубической кривой является кривая, в которой x, y и z – многочлены третьего порядка (т.е. кубические) относительно некоторого параметра t. Так как мы рассматриваем конечные отрезки кривой, то без потери общности можем ограничить диапазон изменения параметра и считать 0 £ t £ 1. Следовательно,

x(t) = a_xt³ + b_xt² +c_xt + d_x,

y(t) = a_yt³ + b_yt² +c_yt + d_y, 0 £ t £ 1

z(t) = a_zt³ + b_zt² +c_zt + d_z.

Производные функции x(t), y(t) и z(t) по параметру t имеют  один и тот же вид. Например,

  = 3a_xt² + 2b_xt + c_x.

Использование кубических кривых обусловлено тем, что для сегментов кривой не существует представления более низкого  порядка, которое обеспечивало бы в точке соединения кривых друг с другом непрерывность положения и наклона сегментов и в то же время гарантировало бы, что концевые точки сегмента кривой проходят через заданные точки. В точке соединения сегменты кривой и их касательные векторы равны. При этом, в общем случае Сⁱ –непрерывность означает, что непрерывны функция и ее первые i производные.

Для интерполяции кривых используют различные методы, среди которых наибольшее распространение получили методы интерполяции локальными эрмитовыми сплайнами нечетных степеней, интерполяции кривых параметрическими кубическими сплайнами, интерполяции кривых с помощью В–сплайнов, аппроксимации кривых методом Безье.

 

1.2 Описание алгоритма Кируса – Бека

 

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

Алгоритмы отсечения бывают дву- или трехмерными  и применяются как к регулярным, так и к нерегулярным областям и объемам. Эти алгоритмы можно  реализовать аппаратно или программно. Алгоритмы отсечения, реализованные  программно, зачастую оказываются недостаточно быстродействующими для приложений ориентированных на процессы, протекающие  в реальном времени. Поэтому как  трех- так и двyмepныe алгоритмы  отсечения реализуются аппаратными  или микропрограммными средствами. В подобных реализациях обычно ограничиваются дву- или трехмерными отсекателями типовых форм. Однако с появлением сверхбольших интегральных схем (СБИС) открываются возможности для более общих реализаций, позволяющих работать в реальном времени как с регулярными, так и с нерегулярными областями и телами.

Для создания надежного алгоритма отсечения  нужно иметь хороший метод  определения местоположения относительно окна (внутри, на границе или вне  его) точки, принадлежащей отрезку. Для этой цели в алгоритме Кируса — Бека используется вектор нормали.

Возьмем выпуклую отсекающую область R. Хотя R не обязана быть двумерной, в данном случае, предполагается, что она двумерна. R может быть любым плоским выпуклым многоугольником. Она не должна быть вогнутым многоугольником. Внутренняя нормаль n в произвольной точке а, лежащей на границе R, удовлетворяет условию: n(b — а) ³ 0, где b — любая другая точка на границе R. Чтобы убедиться в этом, вспомним, что скалярное произведение двух векторов V₁ и V₂ равно: V₁V₂*|V₁||V₂|cosq, где q — это меньший из двух углов, образованных V₁ и V₂. Заметим, что если q = p/2, то cosq  = 0 и V₁V₂ = 0, т. е. когда скалярное произведение пары векторов равно нулю, то они перпендикулярны. На рис. 1 показана выпуклая область R т. е. отсекающее окно. Там же показаны внешняя (наружная) n_H и внутренняя n_B нормали к границе окна, исходящие из точки а, лежащей на этой границе. Кроме того, на рис. 1 показаны еще несколько векторов, проведенных из точки а в другие точки на границе окна. Угол между n_B и любым из таких векторов всегда принадлежит интервалу -p/2 £ q £ p/2. При таких значениях угла косинус его всегда положителен. Следовательно, положительно и скалярное произведение этих векторов, как было установлено выше. А вот угол между внешней нормалью и любым из подобных векторов равен p - q, a cos(p - q) = —cosq при этом отрицателен.

 

1. Внутренняя и внешняя  нормали

Возьмем параметрическое представление  отрезка Р₁Р₂.

 

P(t) = Р₁ + (P₂ - P₁)t, 0 £ t £ 1.

 

Если f — граничная точка выпуклой области R, a n — внутренняя нормаль к одной из ограничивающих эту область плоскостей, то для любой конкретной величины t, т. е. для любой точки отрезка Р₁P₂ из условия n[P(t) - f] < 0 следует, что вектор P(t) - f направлен вовне области R. Из условия n[P(t) - f] = 0 следует, что P(t) - f принадлежит плоскости, которая проходит через f и перпендикулярна нормали. Из условия n[P(t) - f] > 0 следует, что вектор P(t) - f направлен   внутрь R, как показано на рис. 2. Из всех этих условий взятых вместе следует, что бесконечная прямая пересекает замкнутую выпуклую область, которая в двумерном случае сводится к замкнутому выпуклому многоугольнику ровно в двух точках. Далее, пусть эти две точки не принадлежат одной граничной плоскости или ребру. Тогда уравнение n[Р( t) - f] = 0 имеет только одно решение. Если точка f лежит на той граничной плоскости или на том ребре, для которых n является внутренней нормалью, то точка на отрезке Р(t), которая удовлетворяет последнему уравнению, будет точкой пересечения этого отрезка с указанной граничной плоскостью.