«В.М. Гасов, А.М. Цыганенко ТРЕХМЕРНАЯ ГРАФИКА В МЕДИАИНДУСТРИИ Учебник Допущено УМО по образованию в области полиграфии и книжного дела для студентов высших учебных заведений, обучающихся по специальностям: 230102.65 – ...»

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

Рис. 3.10. Перспективная проекция отрезка Одним из свойств центральной проекции являются так называемые точки схода. Дело в том, что ребра куба, не параллельные проекционной плоскости в перспективной проекции, будут пересекаться (сходиться) в определенной точке пространства (рис. 3.11).

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

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

На рис. 3.12 приведена двухточечная центральная проекция куба.

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

Для иллюстрации процесса получения формул центральной перспективной проекции расположим оси системы координат, проекционную (экранную) плоскость и центр проекции как показано на рис. 3.13.

Рис. 3.13. Расположение проекционной плоскости Положим, нам необходимо имитировать на экране монитора или матричной панели изображение реальных объектов, находящихся в пространстве за этим экраном. Изображенная на рис. 3.13 система координат – левосторонняя. В приведенном примере плоскость экрана монитора совпадает с проекционной плоскостью.

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

При этом ребра (отрезки прямых) реального объекта после перспективного преобразования переходят в отрезки прямых на проекционной плоскости.

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

В соответствии с рис. 3.13 точка А проецируется на экран как А1. Расстояние от наблюдателя до проекционной плоскости равно с. Можно определить координаты точки А1 на экране (или проекционной плоскости). Обозначим их xэ и yэ. Из подобия треугольников AyAzN и yэON находим, что где с – это расстояние от центра проекции до экрана;

N = (0, 0, – c) – координаты наблюдателя.

Если наблюдателя разместить в точке начала координат, а проекционную плоскость удалить на расстояние с, то соотношения для xэ и yэ примут следующий вид:

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

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

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

Известно, что вектор (x, y, z) в однородных координатах записывается в виде (tx, ty, tz, t), где t = 0. Число t называется масштабным множителем. Для того чтобы из вектора, записанного в однородных координатах, получить вектор в обычных координатах необходимо разделить первые три координаты на масштабный множитель: (tx/t, ty/t, tz/t, t/t)(x, y, z, l).

Фактически здесь осуществляется переход от n-мерного пространства к (n + 1)-мерному. Обратное преобразование называется проекцией однородных координат.

Отметим некоторые свойства однородных координат. Некоторые точки, неопределенные в n-мерном пространстве, становятся вполне определенными при переходе к однородным координатам. Например, однородный вектор (0, 0, 1, 0) в трехмерном пространстве соответствует бесконечно удаленной точке z =.

Поскольку в однородных координатах эту точку можно представить в виде (0, 0, 1, e), при e0, то в трехмерном пространстве это соответствует точке (0, 0, 1/e).

Будем считать, что проецирование производится на плоскость XOY, а наблюдатель смотрит на проекцию вдоль оси OZ.

Предположим, что центр проектирования лежит на оси Z в точке С с координатами (0, 0, –с), а плоскость проецирования совпадает с координатной плоскостью XOY и экраном (рис. 3.13).

Возьмем в пространстве произвольную точку А(x, у, z), проведем через нее и точку С прямую и запишем ее параметрические уравнения:

Найдем координаты точки пересечения этой прямой с плоскостью XOY. Из того, что Z* = 0, получаем:

и, соответственно:

Тот же самый результат можно получить, если использовать матрицу:

В самом деле, Матрица соответствующего перспективного преобразования (без проецирования) имеет следующий вид:

Каждая прямая (проектор) однозначно определяется точкой своего пересечения с плоскостью XOY и описывается уравнениями Переходя к однородным координатам и используя матрицу [Q], получаем Если принять, что t стремится к бесконечности, то точка (x, y, z, 1) преобразуется в точку с координатами (0, 0, 1, 0). Для этого достаточно разделить все аргументы на t:

и перейти к пределу.

В результате бесконечно удаленный центр (0, 0, 1, 0) пучка параллельных оси Z прямых переходит в точку (0, 0, –c, 1) оси Z. Полученная точка, как указывалось выше, называется точкой схода.

Точка С (рис. 3.13) называется фокусом, а расстояние от точки расположения наблюдателя до проекционной плоскости (с) – фокусным расстоянием. Это расстояние существенно влияет на получаемое в итоге проецирования изображение. Так, на рис. 3. показаны каркасные изображения одного и того объекта, полученные при разном фокусном расстоянии.

Рис. 3.14. Примеры изображения объекта, построенного при большом (а) Укажем некоторые особенности проекций и рационального выбора их параметров. Очевидно, что в центральных проекциях более удаленные объекты изображаются в относительно меньших масштабах. Это явление иногда называется перспективным сокращением. Интенсивность перспективных сокращений зависит, при неизменном положении картинной плоскости, от заданной величины фокусного расстояния. При его уменьшении и одновременном приближении точки зрения к объекту эта интенсивность возрастает (рис. 3.14). Одновременно возрастают и углы, под которыми части объекта видны при правильном (расчетном) рассматривании проекции. Возрастает и общий угол зрения – угол между лучами, проведенными в крайние точки изображения (объекта). При больших фокусных расстояниях и небольших углах зрения проекция становится похожей на аксонометрическую. При малых расстояниях и больших углах перспектива становится «резкой», появляются замечаемые глазом искажения. Углы между линиями объекта искажаются, размеры по глубине как бы утрируются. Учитывая это, точку зрения стремятся выбирать так, чтобы общий угол зрения не превышал 40–60°.

Впрочем, в значительной степени, подобные искажения кажущиеся. Дело в том, что классическая схема построения проекции предполагает не только правильное нанесение изображения, а и правильное (расчетное) его рассматривание. С учетом принятых масштабов мы должны рассматривать изображение из точки, соответствующей центру проецирования. При этом, если фокусное расстояние было небольшим, мы соответственно должны приблизить глаз к картине. Углы зрения, под которыми будут видны отдельные части объекта, восстановятся. Но, естественно, боковые части картины будем рассматривать под углом (глаз можно поворачивать, но нельзя двигать головой). Кажущиеся перспективные искажения на проекции будут компенсированы, если части изображения будут рассматриваться в определенных ракурсах. Обычная ошибка — когда изображения, построенные для больших углов зрения (так называемые широкоугольные), мы пытаемся рассматривать в мелком масштабе с гораздо более далекого расстояния.

Главная точка схода изображения, как правило, размещается в средней части изображения, поскольку изображение рассматривают, располагая глаза где-то против ее средней части (в соответствии с эргономическими рекомендациями). Даже, если мы смотрим на изображение сбоку от экрана, глаз «исправляет» изображение. В отдельных случаях, например, при росписи стен и сводов в архитектурных сооружениях или декораций в театре, от этого правила сознательно отступают. Существует даже понятие «театральная перспектива».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В качестве примера на рис. 3.15 приведено перспективное изображение объекта, получившее название линейная проекция или линейная перспектива.

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

На рис. 3.16 показано перспективное изображение комнаты.

На нём представлена точка yI, которая является точкой схода для всех прямых, перпендикулярных картинной плоскости, и линия горизонта h. Точки схода других параллельных прямых, лежащих в предметной плоскости, располагаются на линии горизонта h (например, DI).

Рис. 3.16. Перспективное (упрощенное) изображение комнаты В приведенном примере выполнено построение перспективного изображения по способу центральной аксонометрии.

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

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

Процесс проецирования для цилиндрической центральной проекции выполняется с помощью следующих соотношений:

где F – фокусное расстояние.

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

Что касается проекций на сферические поверхности – здесь трудность заключается в том, что сфера на плоскость не развертывается. Поэтому приходится перепроецировать изображение со сферической поверхности на плоскость и вычерчивать плоскую «перепроекцию».

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

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

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

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

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

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

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

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

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

Наибольшее распространение получили трехмерные отсекатели в форме:

· прямоугольного параллелепипеда или полого бруска, используемого при параллельном или аксонометрическом проецировании (рис. 3.18);

· усеченной пирамиды, являющейся пирамидой видимости (используется при центральном или перспективном проецировании) (рис. 3.19).

Рис. 3.18. Трехмерный отсекатель в форме параллелепипеда В общем случае отрезок, соединяющий центр проекции с центром усеченной пирамиды, может и не совпадать с осью Z правой системы координат. Поэтому приведенный на рис. 3.19 пример можно рассматривать как частный случай.

Если разместить центр проекции по оси Z в бесконечности, то мы получим вместо усеченной пирамиды параллелограмм и параллельную проекцию.

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

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

Причем объекты вне пределов этих отсекателей являются невидимыми для наблюдателя и не проецируются на экран.

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

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

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

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

При построении алгоритмов решения задач отсечения широко используются следующие подходы. Первый подход характеризуется тем, что, задача трехмерного отсечения преобразуется в двухмерную. Это позволяет использовать известный математический аппарат двухмерной графики, методы и алгоритмы отсечения в двухмерном пространстве. Например, при трехмерном отсечении отрезка АВ (рис. 3.19) можно трансформировать задачу в двухмерную задачу отсечения примитивов, путем использования методов проецирования на координатные плоскости XOY, XOZ, YOZ.

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

Рассмотрим это на простейшем примере. Положим, что задана центральная перспективная проекция с центром проекции в начале координат, как показано на рис. 3.20.

Задачу преобразования центральной перспективы к виду параллельной проекции обычно решают в два этапа.

Вначале приводят видимый объем к нормированному виду.

При этом значение zmax= 1, а границы по осям x и y принимаются лежащими в диапазоне [–1, 1], как показано на рис. 3.21.

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

где и, соответственно, Нормированный видимый объем позволяет с большей легкостью решать задачу отсечения по границе, поскольку, в этом случае может применяться модифицированный вариант алгоритма Коэна–Сазарленда (или какой-либо другой), в котором вместо 4-битовых используются 6-битовые коды для описания нахождения точки вне или внутри соответствующей области пространства. При этом значением 0 обозначается видимый конец отрезка, 1 – невидимый. При таком подходе уравнения боковых граней видимого объема упрощаются. Например, для правой отсекающей плоскости уравнение запишется z = x, а для левой боковой z = –x и т. д. Тогда для некоторой точки (x, y, z) условие установления единичного значения бита будет выглядеть следующим образом:

1-й бит: если конец ребра левее границы видимого объема;

2-й бит: если конец ребра правее объема;

3-й бит: если конец ребра ниже объема;

4-й бит: если конец ребра выше объема;

5-й бит: если конец ребра ближе объема;

6-й бит: если конец ребра дальше объема.

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

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

Это достигается с помощью матрицы После применения матрицы M p нормированный видимый объем становится прямоугольным параллелепипедом, что позволяет перейти от центральной перспективной проекции к параллельной проекции. Легко проверить, что как показано на рис. 3. и рис. 3.22, а также, например, Трехмерные отсекатели могут иметь и другую форму. В общем случае, отсекатель может представлять собой произвольный выпуклый объем, в виде нестандартного тела с шестью, семью и более гранями. Для этих отсекателей разработаны свои алгоритмы отсечения. Например, для трехмерных отсекателей с семью гранями применяется алгоритм Каруса–Бека.

МЕТОДЫ ФОРМИРОВАНИЯ

ГЕОМЕТРИИ

ТРЕХМЕРНЫХ МОДЕЛЕЙ

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

Это традиционный подход, который применялся еще в XVIII–XIX веках при строительстве морских кораблей. В этом случае вместо представления трехмерной поверхности корпуса корабля проектировались его «обводы», представляющие собой поперечные и продольные сечения корпуса. Причем, первоначально по каждому сечению задавалось определенное число опорных точек, которые затем объединялись плавной кривой. Построение таких кривых осуществлялось с помощью специальных инструментов (типа лекал).

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

Для построения таких функций используется интерполяция – построение непрерывных кривых (или поверхностей) по конечным наборам параметров (значений координат).

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

В этом случае требуется восстановить образующую по некоторому набору точек с заданными координатами – интерполировать её.

Сегодня известен широкий набор методов интерполяции – полиномиальная аппроксимация, линейная или квадратичная полиномиальная аппроксимация.

В инженерной деятельности часто возникает необходимость описать в виде функциональной зависимости связь между величинами, заданными таблично или в виде набора точек с координатами (xi, yi), i = 0, 1, 2,...n, где n – общее количество точек. Как правило, эти табличные данные получены экспериментально и имеют погрешности. При аппроксимации желательно получить относительно простую функциональную зависимость (например, полином), которая позволила бы «сгладить» экспериментальные погрешности, получить промежуточные и экстраполяционные значения функций, изначально не содержащиеся в исходной табличной информации.

Рис. 4.1. Графическая интерпретация аппроксимации Эта функциональная (аналитическая) зависимость должна с достаточной точностью соответствовать исходной табличной зависимости. Критерием точности или достаточно «хорошего»

приближения могут служить несколько условий.

Обозначим через fi значение, вычисленное из функциональной зависимости для x = xi и сопоставляемое с yi.

Одно из условий согласования можно записать как т. е. сумма отклонений табличных и функциональных значений для одинаковых x = xi должна быть минимальной (метод средних).

Отклонения могут иметь разные знаки, поэтому достаточная точность в ряде случаев не достигается.

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

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

В качестве функциональной зависимости рассмотрим многочлен Формула (1) примет вид Условия минимума S можно записать, приравнивая к нулю частные производные S по независимым переменным С0,С1,...СМ:

Тогда из (3) можно получить систему нормальных уравнений Для определения коэффициентов Сi и, следовательно, искомой зависимости (2) необходимо вычислить суммы и решить систему уравнений (4). Матрица системы (4) называется матрицей Грама и является симметричной и положительно определенной.

Эти полезные свойства используются при ее решении.

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

Построение с использованием отношений. Построение с использованием отношений заключается в том, что задаются:

• элемент, подлежащий построению;

• список отношений и элементы, к которым относятся отношения.

При этом могут использоваться два способа реализации построения (по отношениям): общий и частный.

При общем способе реализации процесс построения по заданным отношениям можно представить в виде двухшаговой процедуры:

• на основе заданных типов отношений, элементов и параметров строится система алгебраических уравнений;

• решается построенная система уравнений.

Очевидное достоинство такого способа проявляется в простоте расширения системы. Для введения нового отношения достаточно добавлять соответствующие уравнения.

Основные проблемы такого способа заключаются в следующем:

• построенная система уравнений может иметь несколько решений, поэтому необходимо выбрать наиболее адекватное, для чего используется интерактивный режим взаимодействия человека с программой;

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

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

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

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

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

Построение с использованием преобразований. Построение нового объекта с использованием преобразований заключается в следующем:

• задается преобразуемый объект;

• задается преобразование (это может быть обычное аффинное преобразование, определяемое матрицей, или некоторое деформирующее преобразование, например, изгиб);

• выполнение преобразования; (аффинное преобразование выполняется с помощью умножения матриц).

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

• методами интерполяции по точкам;

• вычислением конических сечений;

• расчетом пересечения поверхностей;

• выполнением преобразования некоторой базовой кривой;

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

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

Параметрическое представление кривых выбирается по целому ряду причин, одна из которых связана с тем, что геометрические элементы объектов могут иметь вертикальные касательные. При этом аппроксимация кривой y = f(x) аналитическими функциями была бы невозможной. Кроме того, кривые линии контура объекта могут быть неплоскими. К тому же, параметрическое представление обеспечивает независимость представления от выбора системы координат и отвечает структуре процесса визуализации на экранах устройств отображения информации (позиционирование осуществляется с помощью функции времени x(t) и y(t)).

Существует много методов описания параметрических кубических кривых. К наиболее применяемым относятся:

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

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

Основные способы построения поверхностей:

• интерполяция по точкам;

• перемещение образующей кривой по заданной траектории (кинематический метод);

• деформацией исходной базовой поверхности;

• построением поверхности, эквидистантной к исходной;

• использование кинематического принципа;

• применение операций добавления или удаления сегментов в структуре изображения;

• применение теоретико-множественных (булевских) операций.

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

Наибольшее распространение получили: форма Безье, форма В-сплайнов, форма Эрмита и некоторые другие.

4.3. Аппроксимация обводов и контуров Для геометрического ядра современных CAD/CAM/CAE-систем характерна интеграция методов твердотельного моделирования трехмерных объектов и традиционных методов математического моделирования сложных криволинейных поверхностей.

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

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

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

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

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

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

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

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

Обеспечение качества аппроксимации. Сконструированные криволинейные обводы должны «вести себя» предсказуемо для достаточно больших массивов точек:

• осцилляции не должны превышать заданных значений;

• особые точки должны легко определяться;

• используемые при описании обводов функции должны допускать операцию многократного дифференцирования.

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

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

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

Перечисленным требованиям в большей степени удовлетворяют параметрические полиномиальные функции и рациональные параметрические функции. Обобщение методов Безье и B-сплайнов в начале 70-х годов позволило получить одно из мощнейших и универсальных средств геометрического моделирования криволинейных обводов – NURBS-технологию.

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

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

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

3. Задача сглаживания функции. Требуется недостаточно гладкую функцию (например, не дифференцируемую или дифференцируемую небольшое число раз) приближенно представить более гладкой функцией. Эта задача близка к задачам 1 и 2. Задачи сглаживания возникают, когда необходимо, чтобы искомая кривая или поверхность описывались функцией, обеспечивающей, например, необходимую степень дифференцирования.

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

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

В общем случае в задачах геометрического моделирования сложных объектов проектируемые кривые не могут быть записаны в виде уравнения y = (x) с использованием обычных однозначных функций. Кривые инженерных объектов могут иметь вертикальные касательные, что тесно связано с многозначностью функций. Поэтому в автоматизированном проектировании ведущую роль играет параметрическое представление участков кривых.

Параметризация осуществляется заданием декартовых координат точки кривой как функций некоторого параметра:

Для задания кривых используют параметрическое уравнение в векторной форме:

где r = {x, y, z} – радиус-вектор точки на кривой;

e1, e2, e3 – орты координатных осей;

u – параметр точки на кривой.

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

Параметрический метод задания кривых имеет следующие преимущества:

• более простое вычисление координат точек;

• упрощение расчетов при преобразованиях кривых;

• упрощение расчетов, связанных с подготовкой информации для станков с числовым программным управлением.

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

В этой форме представления произвольный полином n-й степени может быть легко вычислен по схеме Горнера, которая реализуется с помощью n умножений и n сложений, т. е. всего за 2n арифметических действий. Схема Горнера удобна для реализации на компьютере благодаря цикличности вычислений и необходимости сохранять кроме коэффициентов полинома и значений аргумента только одной промежуточной величины. Полином p(u) единственным образом разлагается в произведение из n линейных множителей:

При решении прикладных задач в основном применяют полиномы с коэффициентами ai, являющимися вещественными числами. Решения p(u) вещественного полинома обладают следующими свойствами:

• решения могут повторяться (например, если a1 = a2);

• решения могут быть как вещественными, так и комплексными;

• комплексные корни имеют сопряженные пары.

Как правило, из множества полиномов выбирают полиномы нечетных степеней. Это объясняется следующим. Если полином p(u) имеет нечетную степень, то он должен иметь, по крайней мере, один вещественный корень. Это вытекает непосредственно из приведенных выше свойств, т. к. общее число решений нечетного полинома – нечетное число, а комплексных корней (если они существуют) – четное число. Далее мы также будем рассматривать только вещественные полиномы.

Итак, рассмотрим вектор-функцию в виде векторного полинома степени n:

где ai, i = 0,1,… n – произвольные постоянные векторы;

[a, b] – интервал изменения параметра u кривой a.

Пусть в n + 1 точках кривой a последовательно заданы значения радиус-вектора: Pi, i = 0,1,…, n. Назначим каждому значению радиус-вектора Pi значение параметра ui [a, b] согласно сетке D:

Найдём значения произвольных постоянных векторов в выражении (6) из условий интерполирования кривой a полиномом (6):

Подставляя (6) в условия (8), получим систему n + 1 векторных линейных алгебраических уравнений для нахождения постоянных векторов в выражении (6):

Эту систему уравнений можно записать в компактной матричной форме:

Система векторных линейных алгебраических уравнений (9) эквивалентна трём системам скалярных алгебраических уравнений относительно проекций радиус-вектора P(u) на базисные векторы ej j = 1, 2, 3 соответственно:

где x i = x (ui) – заданные значения проекций радиус-вектора в точках i = 0,1,.. n;

a ji – проекция постоянного вектора ai на ось 0xj системы координат 0x10x20x3.

При этом все системы уравнений (10) будут иметь одинаковые матрицы коэффициентов:

В связи с этой особенностью при интерполировании кривой a параметрическим полиномом достаточно решить одну систему линейных алгебраических уравнений (6) с тремя правыми частями. При этом каждая правая часть системы будет соответствовать j-й проекции постоянных радиус-вектор аi на оси координат 0x10x20x3.

Матрица (11) является матрицей Вандермонда, и её определитель отличен от нуля в силу выбора узлов сетки D согласно (7).

Следовательно, система уравнений (10) имеет единственное решение.

На практике для интерполирования значений функции в точках иногда применяют полиномы, предложенные Лагранжем:

где Lin(u) – базисные полиномы интерполяции Лагранжа.

В этом случае для построения полинома (12) не нужно решать систему линейных алгебраических уравнений вида (9), полином явно выражается через исходные величины: Pi, ui.

Если в точках заданы не только значения радиус-вектора Pi, но и производные Pi’, то единственным полиномом наименьшей степени, имеющим именно эти значения функции и ее производных во всех точках, является интерполяционный полином Эрмита:

p (u) / Pi [1 - 2L 'i (ui) (u - ui)] L 2 (u) + / P i' (u - ui) L 2 (u), (13) Так как полином Li(u) имеет степень n, то полином Эрмита будет иметь степень (2n + 1). Для конструирования обводов чаще применяют кусочные полиномы Эрмита, определяющие участки между каждой парой точек. Тогда в случае n = 3 полином интерполирует заданные узловые точки и заданные в них касательные векторы, а в случае n = 5 – также векторы вторых производных.

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

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

Задачу интерполирования некоторого набора данных параметрическими полиномами можно представить с помощью так называемого приближения Вандермонда. Уравнение (5) запишем в следующем виде:

Для определения коэффициентов полинома (14) надо решить три линейных системы уравнений.

Запишем обобщенную матрицу Вандермонда:

где Фin(u) представляет собой базис пространства всех полиномов степени не выше n.

Определитель обобщенной матрицы Вандермонда также отличен от нуля, следовательно, система уравнений для определения коэффициентов полинома (14) имеет единственное решение. Доказано, что для геометрического моделирования гладких кривых и обводов в качестве Фin(u) удобно использовать полиномы Бернштейна.

Одной из актуальных в этом случае является задача преобразования различных полиномиальных базисов в базис Бернштейна.

параметрическими полиномами Итак, другой распространенной формой представления полиномов является представление в форме Бернштейна. Кроме аспектов, связанных с вычислительной устойчивостью алгоритмов с участием полиномов в форме Бернштейна, этот вид представления полиномов имеет несомненные преимущества чисто с геометрической точки зрения. Рассмотрим «геометрические»

свойства полиномов Бернштейна более подробно.

Произвольный полином степени n в форме Бернштейна определяется уравнением где n – коэффициенты Бернштейна;

B n (u) – скалярные функции Бернштейна.

Коэффициенты f i могут быть скалярными значениями некоторой функции (u), вычисленными на некотором отрезке 0 u для равноотстоящих точек.

Тогда полином p(u) аппроксимирует функцию (u) при достаточно больших n.

Если заменить скалярные коэффициенты n произвольными векторами ri, то в этом случае полином p(u) аппроксимирует ломаную, вершинами которой является заданный набор векторов ri, и определяет на заданном отрезке 0 u 1 дугу кривой Безье n-го порядка. Изменяя положение векторов, можно управлять формой дуги кривой.

Скалярные функции Bi (u) определяются уравнениями и образуют так называемый базис Бернштейна для множества всех полиномов степени не выше n на отрезке [0, 1]. Например, для случая n = 7 изображены функции базиса Бернштейна (рис. 4.2).

В ряде случаев вместо единичного отрезка [0, 1] изменения параметра целесообразно использовать отрезок [tk, tk+1]. Тогда значения локального параметра u на этом общем отрезке tk u tk+ можно вычислить по формуле На отрезке [tk, tk+1] базисные функции Бернштейна определяются уравнениями Отметим следующие основные свойства полиномов Бернштейна.

Сумма полиномов, определенных на заданном отрезке, равна единице:

Это свойство обеспечивает инвариантность полиномов при аффинных преобразованиях. Следовательно, аффинно-инвариантны и кривые Безье, определяемые этим набором полиномов. Заметим, что этим свойством обладают также полиномы в форме Лагранжа (12) и Эрмита (13), но не обладают стандартные полиномы (5).

Все полиномы не отрицательны на заданном отрезке:

Указано, что значения полинома p(u) находятся в интервале Это означает, что кривая, определяемая полиномом p(u), леn жит внутри выпуклой оболочки коэффициентов i. Часто это свойство называют «свойством выпуклости оболочки». Заметим, что на плоскости выпуклая оболочка представляет собой область, ограниченную выпуклой ломаной, а в пространстве – выпуклым многогранником.

Возможно рекурсивное вычисление полиномов степени n, если известны полиномы степени (n – 1):

Это свойство используется для вычисления Bi (u) с помощью повторяющейся линейной интерполяции.

Если B i – полиномы Бернштейна степени n, то полиномы B i степени (n + 1) вычисляются с помощью выражения Это свойство используется при аппроксимации кривой Безье n-го порядка другой кривой порядка (n + 1).

Доказано, что полиномы Бернштейна лучше приспособлены для вычисления простых корней, чем степенные полиномы, как на единичном отрезке [0, 1], так и на отрезке [tk, tk+1]. Полиномы в форме Бернштейна обладают большей вычислительной устойчивостью, чем степенные полиномы. Это связано с тем, что при вычислении степенных полиномов по схеме Горнера может происходить значительная потеря точности за счет вычитания близких больших по модулю округленных чисел. При этом потеря точности увеличивается с возрастанием n из-за ограниченного числа цифровых разрядов компьютера. Избежать потери точности в этом случае удается, применяя для вычисления полинома рекурентные формулы. Одним из методов измерения вычислительной устойчивости алгоритмов заключается в сравнении оценок погрешностей значения полинома в различных формах представления в окрестности произвольной точки. В работе выполнено исследование вычислительных аспектов алгоритмов полиномиальной аппроксимации, и доказано, что полиномы в форме Бернштейна имеют меньшую оценку погрешности, чем степенные полиномы в стандартной форме. Однако при выполнении преобразования из одной формы представления полинома в другую указанное свойство может теряться из-за появления вычислительной неустойчивости.

Полиномы Бернштейна B i имеют максимум при значении паn раметра u = n Это свойство используется при локальном контроле формы обвода. Перемещение управляющей точки ri кривой Безье в большей мере затрагивает участок кривой в окрестности точки со значением параметра i.

Полиномы Бернштейна могут быть вычислены по схеме Горнера с помощью следующих формул:

Геометрические свойства производных полиномов Бернштейна. Вычисление первой производной.

Возьмем производную полинома Бернштейна n-го порядка:

Таким образом, окончательно получаем формулу для вычисления первой производной полиномов Бернштейна:

Тогда для кривой Безье формула первой производной имеет вид:

Так как Bi (u) 0 для j {0,..., n}, то Окончательно получаем формулу для вычисления первой производной кривой Безье:

Форму записи последней формулы можно упростить, если использовать оператор разности :

Тогда формула первой производной принимает вид:

С геометрической точки зрения, производной кривой Безье является другая кривая Безье h(u), векторы управляющих точек которой определяются вычислением разностей векторов управляющих точек исходной кривой. Кривая первой «производной» h(u) иногда называется первым годографом кривой Безье. Векторы характеристической ломаной годографа определяются следующим образом:

Начальный вектор a выбирается произвольно, в ряде случаев удобно выбрать a = 0.

4.7. Методы полиномиальной аппроксимации Вышерассмотренные методы достаточно просто обобщаются на случай аппроксимации двухмерных обводов. Для конструирования криволинейных поверхностей с помощью стандартных параметрических полиномов, полиномов Бернштейна и NURBS в современных системах геометрического моделирования применяют три основных метода:

• тензорного произведения (tensor product surfaces);

• каркасный (lofting surfaces);

• булевой суммы (transfinite method).

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

По заданному массиву P = {Pij, i = 0, 1,..., n, j = 0, 1,..., n} рациональная поверхность определяется уравнением:

где Bi (u), Bj (v) – полиномы Бернштейна;

wij – весовые коэффициенты (wij > 0).

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

Параметрические уравнения, определяющие рациональную поверхность Безье, часто записывают в матричной форме:

где M [wij] = S W M = [mij], mij =(–1)j–1 – матрица коэффициентов.

Основные свойства рациональных поверхностей Безье:

• поверхность полностью определяется набором вершин характеристической сетки Pij;

• поверхность лежит в выпуклой оболочке точек Pij;

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

• граничными кривыми порции поверхности являются рациональные кривые, управляемые набором точек и соответствующих весов;

• рациональная поверхность Безье аффинно- и проективно-инвариантна;

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

С помощью этого метода поверхность определяется семейством кривых. Уравнение поверхности записывается в виде:

или Метод булевой суммы (поверхности Кунса) В случае конструирования поверхности методом Кунса необходимо задать два семейства граничных кривых (в u- и v-направлениях). Уравнение поверхности Кунса имеет вид:

Граничные кривые представляют собой рациональные кривые Безье, управляющие точки которых получены с помощью методов интерполяции исходных точек поверхности, внутренние точки порции поверхности вычисляются с помощью билинейной интерполяции в двух направлениях. Обобщением поверхностей Кунса являются поверхности, интерполирующие всю заданную криволинейную сетку 0 u M, 0 v N (поверхности Гордона).

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

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

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

Сплайны изначально и до сих пор используются при проектировании технических объектов в системах автоматизированного проектирования (САПР). Позднее были оценены их возможности в использовании для программных пакетов двух- и трехмерной графики.

Сплайн – от англ. spline – полоска стали, с помощью которой проводятся плавные кривые через заданные точки. Такие полоски стали применялись в машиностроении для построения плавных обводов контуров различных тел, в частности, корпусов кораблей, кузовов автомобилей, фюзеляжей самолетов. Форма тела задавалась при помощи набора сечений – плазов.

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

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

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

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

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

Эти сплайны применяются для решения двух следующих задач:

• по заданному массиву опорных точек на плоскости (или в пространстве) необходимо построить кривую либо проходящую через все эти точки – задача интерполяции;

• либо проходящую вблизи этих точек – задача сглаживания.

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

Пусть на плоскости задан набор точек (xi,yi), i = 0, 1,..., m, таких что x0 < x1 0, т. е. угол между векторами острый, то грань является лицевой. Если (l, n) < 0, т. е. угол между векторами тупой, то грань является нелицевой.

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

где [P]T = [a b c d] представляет собой плоскость. Поэтому любое выпуклое твердое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей, т. е.

где каждый столбец содержит коэффициенты одной плоскости.

Напомним, что любая точка пространства представима в однородных координатах вектором [S] = [х у z 1]. Более того, если точка [S] лежит на плоскости, то [S]•[P]T = 0. Если же [S] не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают отрицательное скалярное произведение, т. е. нормали направлены наружу.

Рассмотрим единичный куб с центром в начале координат (рис. 6.1).

Шесть плоскостей, описывающих данный куб, таковы:

Более подробно уравнение правой плоскости можно записать как Полная матрица тела:

Скалярное произведение вектора на матрицу объема равно Здесь результаты для второго, четвертого и шестого уравнения плоскостей (столбцов) положительны и, следовательно, составлены некорректно. Умножая эти уравнения (столбцы) на –1, получаем корректную матрицу тела для куба:

Разумеется, это не всегда возможно. Существует несколько полезных методов для более общего случая. Хотя уравнение плоскости (1) содержит четыре неизвестных коэффициента, его можно нормировать так, чтобы d = 1. Следовательно, трех неколлинеарных точек достаточно для определения этих граней.

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

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

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

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

Общее понятие алгоритма удаления невидимых линий Алгоритм удаления невидимых линий:

где O — множество объектов в трехмерном пространстве;

S — множество видимых отрезков на экране;

I — множество промежуточных представлений;

— множество функций перехода, = {PM, IS, CT, DT, VT};

— функция стратегии;

РМ — функция, строящая перспективное изображение, т.е.

переводящая координаты точек из трехмерного пространства в двухмерное;

IS — функция, вычисляющая точку пересечения двух отрезков (в двух- и трехмерном пространстве);

CT — функция, выполняющая в двухмерном пространстве «тест принадлежности». Эта функция определяет, лежит ли точка на поверхности и принимает соответственно значение «истина»

или «ложь»;

DT — функция, выполняющая «тест глубины». Эта функция определяет, какая из двух точек расположена на большей глубине (дальше от точки наблюдения);

VT — функция, выполняющая «тест видимости». Эта функция принимает значение «истина», если поверхность потенциально видна, и «ложь», если поверхность полностью невидима;

s — определяет порядок, в котором должны применяться функции из для получения результата.

Функции перехода имеют достаточно простое геометрическое толкование элементов. Так, для пересечения двух прямых имеем:

Если A1/A2 = B1/B2 = C1/C2, то прямые совпадают.

Если A1 B1, то прямые параллельны.

В остальных случаях прямые пересекаются.

Отрезки пересекаются, если max[min(x1, x2), min(x1', x2')] x1 min[max(x1, x2), max(x1', x2')];

max[min(y1, y2), min(y1', y2')] y1 min[max(y1, y2), max(y1', y2')], где (x1, y1), (x2, y2) — концы отрезка на первой прямой;

(x1', y1'), (x2', y2') — концы отрезка на второй прямой;

(xi, yi) — точка пересечения прямых.

Тест CT применяется к объектам, находящимся в картинной плоскости, и определяет, лежит ли точка P внутри многоугольника. Если количество вершин многоугольника и угол между точкой и вершиной (i ai) и ai = 2, то точка лежит внутри многоугольника. Если ai = 0, то точка лежит вне многоугольника. Существует три теста глубины DT:DT1, DT2, DT3. Тест DT1 сопоставляет два графических элемента (точку и грань) и определяет, заслоняет ли грань точку. DT2, в отличие от DT1, оперирует не только в объектном пространстве, но и в картинной плоскости. Сравнивает либо две грани, либо точку и грань. Тест DT3 применяется в алгоритмах сканирующей прямой, в которых видимость проверяется вдоль сканирующей прямой. Видимость определяется простым сравнением z-координат сегментов на пробном интервале, т. е. на отрезке сканирующей прямой, внутри которого никакие два ребра проекций не пересекаются со сканирующей прямой.

Тест видимости VT определяет, является ли грань тела передней и тем самым потенциально видимой или эта грань задняя и невидимая.

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

Операция «поиск» используется для идентификации элемента в наборе записей. Например, может быть поставлена задача: найти в наборе многоугольников такой, у которого самые отдаленные вершины расположены наиболее близко к точке наблюдения.

Операция «выборка» — это особый вид поиска. Требуется найти в наборе записей те, которые обладают данным свойством. В рассматриваемых ниже алгоритмах также используются тесты PM, IS, CT, DT, VT.

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

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

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

6.3. Алгоритм плавающего горизонта Алгоритм плавающего горизонта чаще всего используется для удаления невидимых линий трехмерного представления функций, описывающих поверхность в виде F(x, y, z) = 0.

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

Предложено много алгоритмов, использующих этот подход.

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

На рис. 6.2 приведен пример, где указанные параллельные плоскости определяются постоянными значениями z. Функция F(x, y, z) = 0 сводится к последовательности кривых, лежащих в каждой из этих параллельных плоскостей, например, к последовательности y = f(x, z) или x = g(y, z), где z постоянно на каждой из заданных параллельных плоскостей.

Рис. 6.2. Секущие плоскости с постоянной координатой Итак, поверхность теперь складывается из последовательности кривых, лежащих в каждой из этих плоскостей, как показано на рис. 6.3. Здесь предполагается, что полученные кривые являются однозначными функциями независимых переменных.

Рис. 6.3. Кривые в секущих плоскостях с постоянной координатой Если спроецировать полученные кривые на плоскость z = 0, как показано на рис. 6.3, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности. Алгоритм сначала упорядочивает плоскости z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, то есть для каждого значения координаты x в пространстве изображения определяется соответствующее значение y. Алгоритм удаления невидимой линии заключается в следующем: если на текущей плоскости при некотором заданном значении x соответствующее значение y на кривой больше значения y для всех предыдущих кривых при этом значении x, то текущая кривая видима в этой точке; в противном случае она невидима.

Невидимые участки показаны пунктиром на рис. 6.4. Реализация данного алгоритма достаточно проста. Для хранения максимальных значений y при каждом значении x используется массив, длина которого равна числу различимых точек (разрешению) по оси x в пространстве изображения. Значения, хранящиеся в этом массиве, представляют собой текущие значения «горизонта». Поэтому по мере рисования каждой очередной кривой этот горизонт «всплывает». Фактически этот алгоритм удаления невидимых линий работает каждый раз с одной линией.

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

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

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

Рис. 6.5. Обработка нижней стороны поверхности В изложенном алгоритме предполагается, что значение функции, то есть y, известно для каждого значения x в пространстве изображения. Однако, если для каждого значения x нельзя указать (вычислить) соответствующее ему значение y, то невозможно поддерживать массивы верхнего и нижнего плавающих горизонтов. В таком случае используется линейная интерполяция значений y между известными значениями для того, чтобы заполнить массивы верхнего и нижнего плавающих горизонтов, как показано на рис. 6.6.

Y значения x в пространстве изображения линейное интерполирование Рис. 6.6. Линейная интерполяция между заданными точками Если видимость кривой меняется, то метод с такой простой интерполяцией не даст корректного результата. Этот эффект проиллюстрирован на рис. 6.7a. Предполагая, что операция по заполнению массивов проводится после проверки видимости, получаем, что при переходе текущей кривой от видимого к невидимому состоянию (сегмент AB на рис. 6.7a), точка (xn+k, yn+k) объявляется невидимой. Тогда участок кривой между точками (xn, yn) и (xn+k, yn+k) не изображается и операция по заполнению массивов не проводится. Образуется зазор между текущей и предыдущей кривыми. Если на участке текущей кривой происходит переход от невидимого состояния к видимому (сегмент CD на рис. 6.7a), то точка (xm+k, ym+k) объявляется видимой, а участок кривой между точками (xm, ym) и (xm+k, ym+k) изображается и операция по заполнению массивов проводится. Поэтому изображается и невидимый кусок сегмента CD. Кроме того, массивы плавающих горизонтов не будут содержать точных значений y.

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

текущая линия текущая линия Существует несколько методов получения точек пересечения кривых. На растровых дисплеях значение координаты x можно увеличивать на 1, начиная с xn или xm (рис. 6.7a). Значение y, соответствующее текущему значению координаты x в пространстве изображения, получается путем добавления к значению y, соответствующему предыдущему значению координаты x, вертикального приращения y вдоль заданной кривой. Затем определяется видимость новой точки с координатами (x + 1, y + y).

Если эта точка видима, то активируется связанный с ней пиксел.

Если невидима, то пиксел не активируется, а x увеличивается на 1. Этот процесс продолжается до тех пор, пока не встретится xn+k или xm+k. Пересечения для растровых дисплеев определяются изложенным методом с достаточной точностью. Близкий и даже более элегантный метод определения пересечений основан на двоичном поиске.

Точное значение точки пересечения двух прямолинейных отрезков, которые интерполируют текущую и предшествующую кривые, между точками (xn, yn) и (xn+k, yn+k) (рис. 6.7) задается формулами а индексы c и p соответствуют текущей (current) и предшествующей (previous) кривым. Полученный результат показан на рис. 6.7б.

Теперь алгоритм излагается более формально.

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

Если на участке от предыдущего (xn) до текущего (xn+k) значения x видимость кривой изменяется, то вычисляется точка пересечения (xi).

Если на участке от xn до xn+k сегмент кривой полностью видим, то он изображается целиком; если он стал невидимым, то изображается фрагмент от xn до xi, если же он стал видимым, то изображается фрагмент от xi до xn+k. Заполнить массивы верхнего и нижнего плавающих горизонтов.

Изложенный алгоритм приводит к некоторым дефектам, когда кривая, лежащая в одной из более удаленных от точки наблюдения плоскостей, появляется слева или справа из-под множества кривых, лежащих в плоскостях, которые ближе к указанной точке наблюдения. Этот эффект продемонстрирован на рис. 6.7, где уже обработанные плоскости n – 1 и n расположены ближе к точке наблюдения. На рисунке показано, что получается при обработке плоскости n + 1. После обработки кривых n – 1 и n верхний горизонт для значений x = 0 и 1 равен начальному значению y, для значений x от 2 до 17 он равен ординатам кривой n; а для значений 18, 19, 20 — ординатам кривой n – 1. Нижний горизонт для значений x = 0 и 1 равен начальному значению y, для значений x = 2, 3, 4 — ординатам кривой n; а для значений x от 5 до 20 — ординатам кривой n – 1. При обработке текущей кривой n + 1 алгоритм объявляет ее видимой при x = 4. Это показано сплошной линией на рис. 6.8. Аналогичный эффект возникает и справа при x = 18. Такой эффект приводит к появлению зазубренных боковых ребер. Проблема с зазубренностью боковых ребер решается включением в массивы верхнего и нижнего горизонтов ординат, соответствующих штриховым линиям на рис. 6.8. Это можно выполнить эффективно, создав ложные боковые ребра. Приведем алгоритм, реализующий эту идею для обеих ребер.

Обработка левого бокового ребра: если Pn является первой точкой на первой кривой, то запомним Pn в качестве Pn–1 и закончим заполнение. В противном случае создадим ребро, соединяющее Pn–1 и Pn. Занесем в массивы верхнего и нижнего горизонтов ординаты этого ребра и запомним Pn в качестве Pn–1.

Обработка правого бокового ребра: если Pn является последней точкой на первой кривой, то запомним Pn в качестве Pn–1 и закончим заполнение. В противном случае создадим ребро, соединяющее Pn и Pn–1. Занесем в массивы верхнего и нижнего горизонтов ординаты этого ребра и запомним Pn в качестве Pn–1.

Теперь полный алгоритм выглядит следующим образом.

Для каждой плоскости z = const.

Обработать левое боковое ребро.

Для каждой точки, лежащей на кривой из текущей плоскоcти:

• если при некотором заданном значении x соответствующее значение y на кривой больше максимума или меньше минимума по y для всех предыдущих кривых при этом x, то кривая видима (в этой точке). В противном случае она невидима;

• если на сегменте от предыдущего xn до текущего xn+k значения x видимость кривой изменяется, то вычисляется пересечение (xi);

• если на участке от xn до xn+k сегмент кривой полностью видим, то он изображается целиком; если он стал невидимым, то изображается его кусок от xn до xi; если же он стал видимым, то изображается его кусок от xi до xn+k.

Заполнить массивы верхнего и нижнего плавающих горизонтов.

Обработать правое боковое ребро.

Если функция содержит очень острые участки (пики), то приведенный алгоритм может дать некорректные результаты. Этот эффект показан на рис. 6.9.

Здесь самая нижняя линия (z = 1) содержит пик. При x = 8 следующая линия (z = 2) объявляется видимой. При x = 12 эта линия (z = 2) объявляется невидимой, определяется точка пересечения и линия (z = 2) изображается от x = 8 до этой точки. На участке от x = 12 до x = 16 эта линия (z = 2) вновь становится видимой, определяется новая точка пересечения и кривая изображается от этого пересечения до x = 16. Следующая линия (z = 3) при x = 8 видима;

однако она объявляется видимой и при x = 12. Следовательно, эта линия изображается на участке от x = 8 до x = 12, несмотря на то что она заслонена пиком. Этот эффект вызван вычислением значений функции и оценкой ее видимости на участках, меньших, чем разрешающая способность экрана, то есть тем, что функция задана слишком малым количеством точек. Если встречаются узкие участки, то функцию следует вычислять в большем числе точек. Если в примере на рис. 6.9 функцию вычислять в точках с абсциссами 0, 2, 4,..., 18, 20, вместо точек 0, 4,..., 16, 20, то линия z = 3 будет изображена правильно.

На рис. 6.10 показан типичный результат работы алгоритма плавающего горизонта.

Рис. 6.10. Функция y = (1/5)sin(x)cos(z) – (3/2)cos(7/4)e(–), 6.4. Алгоритм трассировки лучей Оценки эффективности всех алгоритмов удаления невидимых поверхностей, изложенных ранее, зависят от определенных характеристик когерентности той сцены, для которой ведется поиск ее видимых участков. В отличие от них, трассировка лучей является методом грубой силы. Главная идея, лежащая в основе этого метода, заключается в том, что наблюдатель видит любой объект посредством испускаемого неким источником света, который падает на этот объект и затем каким-то путем доходит до наблюдателя. Свет может достичь наблюдателя, отразившись от поверхности, преломившись или пройдя через нее. Если проследить за лучами света, выпущенными источником, то можно убедиться, что весьма немногие из них дойдут до наблюдателя. Следовательно, этот процесс был бы вычислительно неэффективен. В следствии этого было предложено отслеживать (трассировать) лучи в обратном направлении, т. е. от наблюдателя к объекту, как показано на рис. 6.11. В первом алгоритме трассировка прекращалась, как только луч пересекал поверхность видимого непрозрачного объекта; т. е. луч использовался только для обработки скрытых или видимых поверхностей. С течением времени был реализован алгоритм трассировки лучей с использованием общих моделей освещения. Эти алгоритмы учитывают эффекты отражения одного объекта от поверхности другого, преломления, прозрачности и затенения. Производится также устранение ступенчатости. Рассмотрим применение метода трассировки лучей для определения видимых или скрытых поверхностей.

Рис. 6.11 служит иллюстрацией алгоритма трассировки лучей.

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

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

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

Если точка зрения находится не в бесконечности, алгоритм трассировки лучей лишь незначительно усложняется. Здесь предполагается, что наблюдатель по-прежнему находится на положительной полуоси z. Картинная плоскость, т. е. растр, перпендикулярна оси z, как показано на рис. 6.11. Задача состоит в том, чтобы построить одноточечную центральную проекцию на картинную плоскость.

Рис. 6.12. Сферическая и прямоугольная оболочки Наиболее важным элементом алгоритма определения видимых поверхностей путем трассировки лучей является процедура определения пересечений. В состав сцены можно включать любой объект, для которого можно создать процедуру построения пересечений. Объекты сцены могут состоять из набора плоских многоугольников, многогранников или 6–11 тел, ограниченных или определяемых квадратичными или биполиномиальными параметрическими поверхностями. Поскольку 75– 95% времени, затрачиваемого алгоритмом трассировки лучей, уходит на определение пересечений, то эффективность процедуры поиска пересечений оказывает значительное влияние на производительность всего алгоритма. Вычислительная стоимость определения пересечений произвольной пространственной прямой (луча) с одним выделенным объектом может оказаться высокой. Чтобы избавиться от ненужного поиска пересечений, производится проверка пересечения луча с объемной оболочкой рассматриваемого объекта. И если луч не пересекает оболочки, то не нужно больше искать пересечений этого объекта с лучом. В качестве оболочки можно использовать прямоугольный параллелепипед или сферу. Хотя, как показано, на рис. 6.12, использование сферы в качестве оболочки может оказаться неэффективным, факт пересечения трехмерного луча со сферой определяется очень просто. В частности, если расстояние от центра сферической оболочки до луча превосходит радиус этой сферы, луч не пересекает оболочки. Следовательно, он не может пересекаться и с объектом.

Рис. 6.13. Трассировка луча с учётом перспективы Поэтому тест со сферической оболочкой сводится к определению расстояния от точки до трехмерной прямой, т. е. луча. Будем использовать параметрическое представление прямой, проходящей через точки P1(x1, y1, z1) и P2(x2, y2, z2) т. е.:

с компонентами Тогда минимальное расстояние d от этой прямой до точки P0(x0, y0, z0) равно:

а параметр t, определяющий ближайшую точку Р(t), равен:

Если d2 > R2, где R – радиус сферической оболочки, то луч не может пересечься с объектом.

Выполнение габаритного теста с прямоугольной оболочкой в трехмерном пространстве требует большого объема вычислений.

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

Одной простой процедурой можно свести тест с прямоугольной оболочкой к сравнению знаков, упрощая тем самым вычисление пересечений с объектом, а также сравнения по глубине среди точек пересечения. В этой процедуре используются переносы и повороты вокруг координатных осей для того, чтобы добиться совпадения луча с осью z. Аналогичным преобразованиям подвергается и прямоугольная оболочка объекта. Луч пересекает оболочку, если в новой перенесенной и повернутой системе координат знаки xmin и xmax, а также ymin и ymax противоположны, как показано на рис. 6.14.

пересекающий непересекающий Рис. 6.14. Пересечение прямоугольной области Рассмотрим упрощение вычислений точек пересечения луча и поверхности второго порядка общего вида. В произвольной декартовой системе координат поверхности второго порядка являются геометрическим местом точек, координаты которых удовлетворяют уравнению После применения преобразования, которое является комбинацией переноса и поворота и используется для совмещения луча с осью z, пересечение этого луча с поверхностью, если оно имеет место, возникает при x = y = 0. Поэтому в общем случае точки пересечения являются решениями уравнения, т. е.

где штрих сверху обозначает коэффициенты общего уравнения поверхности второго порядка после преобразования. Если c3l 2 - 4a3l dl < 0, то решения выражаются комплексными числами и луч не пересекает поверхности. Если бесконечная поверхность второго порядка (например, конус или цилиндр) ограничена плоскостями, то эти плоскости также следует преобразовать и проверить на пересечения. Если найдено пересечение с бесконечной ограничивающей плоскостью, то необходимо, кроме того, произвести проверку на попадание внутрь. Однако в преобразованной системе координат эту проверку можно произвести на двухмерной проекции фигуры, образованной пересечением ограничивающей плоскости и квадратичной поверхности. Для получения точки пересечения в исходной системе координат необходимо применить обратное преобразование.

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

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

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

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

Этот метод основан на понятиях, заимствованных из алгебраической геометрии. Решения получающихся при этом алгебраических уравнений высших степеней находятся численно. Метод, подобный этому, можно реализовать в преобразованной системе координат. Напомним, что биполиномиальная параметрическая поверхность определяется уравнением с компонентами в преобразованной системе координат выполнено условие x = y = 0.

Значит, Совместное решение этой пары уравнений дает значения u и w для точек пересечения. Подстановка этих значений в уравнение z = h (u, w) дает компоненту z для точек пересечения. Неудача попытки найти действительное решение означает, что луч не пересекает поверхность. Степень системы уравнений для u, w равна произведению степеней биполиномиальных поверхностей. Бикубическая поверхность, например, имеет шестую степень. Следовательно, в общем случае потребуются численные методы решения. Там, где это допустимо, для начального приближения u и w можно использовать пересечения луча с выпуклой оболочкой. Для получения пересечений в исходной системе координат, как и ранее, следует использовать обратное преобразование.

Если трассируемый луч пересекает объекты сцены в нескольких точках, то необходимо определить видимое пересечение.

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

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

Создать список объектов, содержащий по меньшей мере следующую информацию:

• Полное описание объекта: тип, поверхность, характеристики и т. п.

• Описание сферической оболочки: центр и радиус.

• Флаг прямоугольной оболочки. Если этот флаг поднят, то будет выполнен габаритный тест с прямоугольной оболочкой, если же он опущен, то тест выполняться не будет. Заметим, что габаритный тест необходим не для всех объектов, например для сферы он не нужен.

• Описание прямоугольной оболочки: xmin, xmax, ymin, ymax, zmin, zmax.

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

Запомнить это комбинированное преобразование.

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

Если список пересечений пуст, то изобразить данный пиксел с фоновым значением интенсивности.