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

Интерактивная компьютерная графика предполагает воспроизведение изображений в режиме диалога пользователя с ЭВМ в реальном масштабе времени. программа автоматизированный проектирование

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

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

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

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

Функции, выполняемые КГ, задаются её программным обеспечением. Возможности, которые КГ представляет пользователю, определяются в основном программами. Нулевой уровень представляет драйверы -программы управления вводом - выводом, первый уровень - программы формирования файлов в форматах команд графических устройств, второй уровень - базовый пакет вычерчивания графических примитивов (линий, текста и т.д.). Третий уровень включает программы, реализующие геометрические построения, аффинные преобразования и т.п.

Четвёртый уровень включает программы организаций графического диалога. Программное обеспечение базового графического пакета должно быть независимым от аппаратуры и от средств диалога. С помощью базовой графической системы обеспечивается интерфейс между геометрической моделью и устройствами ввода - вывода, графический диалог. В зависимости от размерности геометрической модели (2D или 3D) компьютерная графика подразделяется на двухмерную (плоскую) и трёхмерную (объёмную).

После краткого рассмотрения вопросов компьютерной графики следует затронуть ещё один интересный вопрос - историю развития компьютерной графики.

1.2 Этапы развития средств компьютерной графики

Как самостоятельное научное и прикладное направление КГ возникла 40 лет назад как следствие широкого применения ЭВМ. Основные идеи её применения восходят к работе И. Сазерленда из лаборатории им. Линкольна в Массачусетском технологическом институте. Затем последовали работы Т.Е. Джонсона, Л.Дж. Робертса. В 1963 году Сазерлендом была разработана двухкоординатная графическая система, которая была расширена Джонсоном до трехкоординатной системы. Исторический интерес представляет сегодня программа исследования, выполнявшаяся с 1959 года фирмой General Motors. Разработанная при этом система получила название DAC-1. Аппаратура системы была изготовлена фирмой IBM в 1963 году. Дисплей этой системы стал прототипом современных дисплеев. Затем появляется система SAGE, в которой широко используется дисплей, управляемый ЭВМ. Световое перо явилось развитием идеи световой пушки, применяемой для идентификации цели в системе SAGE.

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

Практически первой интерактивной графической системой следует считать систему SKETCHPAD. В этой системе на экране ЭЛТ, управляемой ЭВМ, изображались различные геометрические фигуры. С помощью светового пера можно было не только рисовать на экране фигуры, но и осуществлять некоторые преобразования их. В силу высокой стоимости технических средств КГ получила распространение в авиастроении, кораблестроении и других областях, где её применение экономически оправдано.

Один из исторических путей развития КГ связан с получением чертежей на выходе ЭВМ. В 50-х годах широкое распространение получили аналоговые координатные самописцы. В 1958 году была разработана в США программно- управляемая чертёжная установка. В начале 60-х годов были разработаны системы изготовления различных чертежей с помощью устройств, называемых графопостроителями. Самая первая система КГ, состоящая из 16-битовой ЭВМ, устройства ввода графической информации и чертёжного автомата, появилась в 1971 году в США.

В 70-х годах с появлением микропроцессоров фирмы "Интел" появляются автоматизированные рабочие места (АРМ) со встроенными ЭВМ. Во второй половине 70-х годов проводятся работы по стандартизации графического программного обеспечения. Результатом явилось создание системы базовой графики GKS. Появились цветные растровые дисплеи.

В начале 80-х уровень компьютерной графики стал высоким, а её применение - экономически выгодным. Получили распространение дисплеи с запоминанием, дисплеи с выводом изображения в виде растра. В 1981году появляются компьютеры IBM PC. Если раньше существовали по отдельности алфавитно-цифровые и графические дисплеи, то теперь на экране дисплея IBM PC можно было представить текст и графическую информацию. Устройство типа "мышь" позволило значительно упростить работу в режиме диалога. В эти же годы были созданы трёхмерные графические системы для решения конструкторских и технологических задач.

С самого начала развития КГ последовательно решалась проблема синтеза изображения с помощью ЭВМ. В начальном периоде (1963-1970 гг.) были разработаны алгоритмы удаления невидимых линий, сформулированы основные понятия и разработаны алгоритмы создания рисунков на цифровом графопостроителе, введены понятия освещения и затемнения. В период 1971-1978 гг. разрабатываются многочисленные методы интерполяции и аппроксимации сложных поверхностей, программы для графики размерностей 2D и 3D. С 1979 года и по настоящее время основная тенденция развития КГ заключается в разработке программного и технического обеспечений. В нашей стране первая диалоговая графическая система была внедрена в 1969 году. В 1975 году была внедрена первая система автоматизированного выпуска проектно-графической документации. В начале 80-х годов разрабатываются пакеты программ: ГРАФОР, ГРАФИКА, ФАП-КФ, АЛГРАФ для реализации 2D-графики и отдельных задач 3D-графики. Разрабатываются автоматизированные рабочие места (АРМ) АРМ2-01, АРМ2-04, АРМ2-05, АРС-С на базе СМ 1420, в которых была предусмотрена связь с ЕС ЭВМ. В то же время была создана первая отечественная трёхмерная система СИМАК. В настоящее время в России направления работ в области КГ сводятся к математическому и программному обеспечению КГ.

1.3 Возможности современной компьютерной графики

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

Самыми первыми программами 3D-моделирования были программы автоматизированного проектирования. К новейшим средствам в этом направлении следует отнести SolidWorks, разработанную американской компанией SolidWorks Corporation, которая преследовала цель создания массовой, недорогой системы для каждого конструктора. В этой системе реализовано твёрдотельное геометрическое моделирование. Созданные детали могут объединяться в сборку с заданием ограничения взаимного расположения любых деталей друг относительно друга (соосность, фиксация, совпадение точек и т.д.). Связка SolidWorks и КОМПАС - ГРАФИК5 обеспечивает мощное конструирование и эффективный выпуск чертёжной документации. К программным продуктам этого же направления относится пакет Autodesk Mechanical Desktop (AMD), объединяющий в себе средства конструирования деталей, узлов и моделирование поверхностей. Данный продукт ориентирован на моделирование параметрических твёрдотельных сборок деталей, узлов и агрегатов, автоматизированный выпуск конструкторской документации.

К другому направлению КГ, где широкое распространение получило 3D-моделирование, относится разработка современных компьютерных игр. К числу программных продуктов, пригодных для построения трёхмерных компьютерных игр, относятся Direct 3D и OpenGL. Пользуясь этими программами, можно построить сцену практически любой сложности, с поверхностями любой формы, с источниками света, прозрачными объектами, с любыми текстурами и без них. Количество изображений, получаемых с помощью Direct 3D и OpenGL, нельзя, конечно, сравнить с тем, что можно получить от 3D Studio MAX.

При испытании программы 3D Studio MAX пользователи проделали огромную работу, применяя эту программу в различных областях: от создания статической рекламы и динамических заставок для телеканалов до моделирования катастроф и трёхмерной анимации. Данная система используется для создания современных фильмов со спецэффектами. Достаточно посадить одного человека, чтобы создать спецэффекты, создающие полное ощущение реальности. Широкому применению визуальных эффектов никто не удивляется. Эффекты в блокбастерах (боевиках) и романтических сказках, играх и мультимедийных презентациях, в кино и на телевидении, трёхмерные и мультипликационные, объединяет только одно: они созданы с помощью компьютеров.

В последние годы сформировалось новое направление КГ-представление "виртуальных" объектов. С 19 по 23 мая 1997 года в Центре международной торговли проходил ежегодный Российский фестиваль компьютерной графики и анимации. На выставке была представлена новинка - телевизионная виртуальная студия. С помощью такой студии можно делать оригинальные передачи без огромных павильонов и дорогостоящих декораций. С сентября 1997 года компания "Б.С. Графика" оформляет московский канал "ТВ Центр" и выпускает там две телепередачи: "Интернет КАФЕ" и "Виртуальный мир". Применение трёхмерной анимации и виртуальных технологий в кинематографе, оформлении телевизионных передач, шоу-бизнесе стало обязательным, однако существуют и другие примеры применения новейших технологий. 6 - 8 мая 1998 года в Осло проходил Первый международный симпозиум по визуализации. На данной конференции были продемонстрированы различные технические средства для представления виртуальных объектов. Особый интерес вызвали проекты по созданию виртуальных городов. С помощью уникальной системы и методологии компьютерного моделирования построены виртуальные модели реального времени городских районов. Эти модели, с точностью до надписей на стенах и занавесок в окнах, конструируются путём сочетания фотографий, полученных с помощью аэрофотосъёмки, со стереометрическими "представлениями" улиц для реалистического трёхмерного моделирования с использованием пакета MultiGen II Pro.

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

Одним из наиболее перспективных направлений применения КГ является автоматизация конструкторской и дизайнерской деятельности. Так, компания IBM разработала систему Catia, с помощью которой на разработку автомобиля Neon, выпущенного в конце 1994 года, американская корпорация Chrysler Motors затратила всего 31 месяц, опередив японские компании, долгое время державшие планку на отметке 36 месяцев. Той же системой были созданы прототипы автомобилей Volvo-960, Jeep Cherokee, SAAB-900, ВАЗ-2110 и самолёта Boeing 777. В последнем случае экономия составила 15 процентов от всей суммы средств - примерно 8 млн. долларов.

Можно выделить программы КГ, используемые в шоу-бизнесе для создания рекламных роликов. Ведущую роль в этом направлении играет компания GlassworKS. Одной из последних разработок этой компании является Softmage - программа на базе 3D-Studio, но более приспособленная для создания видеоклипов.

В последнее время появились программы КГ-генераторы ландшафтов. Наиболее простыми являются Bryce 2, затем Bryce 3D. С помощью этих программ можно создавать вполне реалистичные пейзажи, управлять временами суток, погодными условиями и т.д. Основным преимуществом данного продукта является простое управление, понятное из общения с интерфейсом. Предусмотрены возможности анимации, взгляда с разных точек на проекцию. Более широкими возможностями обладают пакеты Animatek's Word Builder 2.0 и Word Construction Set 3.0. Animatek's Word Builder создаёт реалистические пейзажи, а отличная интеграция с 3D Studio MAX позволяет полностью реализовать плод воображения. Второй пакет опять же интегрирует ландшафты, но в такой степени, что кроме него уже не требуются другие пакеты 3D-моделирования, хотя используется поддержка 3D Studio MAX.

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

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

Большинство программ 3D-моделирования (3D Studio MAX и другие) не предназначены для инженерных работ. Для этих задач компания Autodesk создала AutoCAD. Данный продукт занимает лидирующую позицию в мировом списке программ такого класса. Неудивительно, ведь он способен выполнять практически все операции, связанные с инженерными системами. Работа этой системы обслуживается тысячами узлов всемирной сети Internet. Система предназначена для профессионалов в области САПР (систем автоматизированного проектирования). Известная компания по производству CAD-программ Bentley Systems представила программу Micro Station (система интерактивного графического проектирования IGDS), которая занимает второе место после системы AutoCAD. Основные назначения Micro Station: выполнение высокопрофессиональных работ в машиностроении, транспорте, электронике, геодезии и картографии, архитектуре и управлении.

Следует отметить, что за последние 7-8 лет с появлением новейших операционных систем Windows 95, Windows NT 4.0, Windows 98 стали реальностью многие задачи компьютерной графики, решение которых в среде DOS в принципе не представлялось возможным. Компьютерная графика постепенно становится обычным и привычным инструментом конструктора, дизайнера, специалиста по рекламе, бизнесмена и преподавателя.

1.4 Место КГ в автоматизированных системах

Как показал многолетний зарубежный опыт, одним из главных факторов развития экономики является широкое применение средств автоматизации и вычислительной техники. Были разработаны и внедрены различные автоматизированные системы: САПР - системы автоматизированного проектирования; АСНИ - автоматизированные системы научных исследований; АСТПП - автоматизированные системы технологической подготовки производства; АСПУР - автоматизированные системы поддержки управленческих решений; АИС - административно-информационные системы.

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

Для совершенствования управления организациями в США, Западной Европе, Японии разработаны и внедрены АИС. Пользователями АИС выступают административно-управленческие работники. В основе АИС лежит модель предприятия (фирмы), в которую включены подсистемы финансирования, управления запасами, сбыта, связи между ними.

АИС реализует:

а) функции управления на трёх уровнях (стратегическом, административном, оперативном);

б) справочно-информационные функции;

в) бухгалтерский учёт;

г) управление запасами:

Компьютерная графика в АИС является обслуживающей подсистемой.

Основные функции КГ в АИС:

выполнение графиков, схем, структур, диаграмм, планов;

выполнение документации;

редактирование документации;

изготовление эскизов и чертежей.

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

в сборе и обработке информации;

в анализе информации;

в адаптации (выявление неравновесных состояний и устранение их);

в синтезе (формирование моделей объектов).

КГ используется в АСПУР в представлении исходных данных, в организации диалога, выводе результатов: распечатки, таблицы, графики, схемы, структуры.

Кроме АИС и АСПУР к автоматизированным системам, где широко применяется КГ, относятся САПР и АСТПП.

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

2. Геометрическое моделирование объектов

2.1 Геометрические модели объектов двухмерной графики

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

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

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

а) модель не должна противоречить реальному объекту (правильность модели);

б) возможность моделирования объекта целиком (мощность модели);

в) возможность вычисления ряда геометрических параметров;

г) минимальное количество информации для представления модели (компактность);

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

Геометрические модели бывают двухмерные и трёхмерные. Двухмерные модели позволяют формировать и изменять чертежи, а трёхмерная модель -создать виртуальное представление объекта в трёх измерениях.

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

2.1.1 Базовые объекты

Точка задаётся двумя координатами: x,y.

В изображениях, выводимых на экран дисплея, очень часто фигурируют отрезки прямых. Для вывода отрезков на экран используются различные устройства, называемые генераторами векторов. В различных генераторах используют различные формы уравнений прямой линии. Обозначим концы отрезка прямой как (x1,y1) и (x2,y2). Кроме того, введём обозначения

X=X2 - X1,

Y=Y2-Y1. (1)

Уравнение прямой может быть записано в различных формах:

1. Параметрическая форма

X = (1 - t) X1 - tX2,

Y = (1 - t) Y1 - tY2. (2)

Параметр t изменяется в диапазоне 0 t 1.

2. Экспоненциальная параметрическая форма

(3)

где 0 t .

3. Дифференциальная форма

(4)

4. Интегральная форма

(5)

параметр t изменяется в диапазоне 0 t Т.

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

Уравнение эллипса с центром в начале координат и полуосями a и b может быть записано

(6)

Уравнение эллипса с центром в точке (xс,yс) имеет вид

(7)

2.1.2 Конструирование кривых

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

Основные принципы конструирования кривых:

а) кривая должна быть кусочно-составной;

б) возможность управления формой кривой;

в) увеличение числа сегментов кривой не должно нарушать гладкость кривой;

г) использование минимального количества параметров для математических моделей, описывающих кривые;

д) возможность преобразования изображения;

е) возможность описания кривых с касательными, параллельными осями координат;

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

В описании кривых в КГ возможны два подхода:

а) задание кривой уравнением;

б) описание приближенными методами: интерполяции и аппроксимации.

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

2.1.3 Интерполирование полиномами

Пусть (x1,y1), (x2,y2), ..., (xn,yn) - последовательность точек, заданных на плоскости, причём xi xj при ij. Формулу интерполяционного полинома (n-1) степени можно представить в виде

. (8)

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

Пример 1. Заданы пять точек: (0, 0), (1, 3), (2, 0), (3, 0), (4, 0).

Соответствующий интерполяционный полином может быть записан

Этот полином имеет три экстремума вблизи точек (0,67; 3,46), (2,46; -0,47), (3,5; 0,66) (рис. 1).

Уравнение (8) представляет интерполяционную формулу Лагранжа. Для решения задач КГ более подходит параметрическая формула

. (9)

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

(10)

где h - шаг интерполяции; yi = yi+1 - yi (i=0, 1, 2,…) - конечная разность.

Например,

y0 =y1 - y0,

y1 =y2 - y1,

y2 =y3 - y2

и т.д.

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

Пример 2. Построить интерполяционный полином Ньютона для точек (0;5,2); (1,8), (2;10,4), (3;12,4), (4,14), (5;15,2). Определим шаг интерполяции h=1.

Составим таблицу разностей.

Из табл. 1 видно, что y0=5,2 , y1=2,8 , 2y = 0,4.

Подставив указанные значения в (10), получим

или

Таблица 1

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

, (11)

где - полином Лагранжа.

Рис. 1. Интерполяционный полином

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

Рис. 2. Исходные данные для конструирования кривой Фергюсона

2.1.4 Сглаживание

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

В 1963 году Фергюсон впервые ввёл кубическую параметризацию для определения кривых (рис. 2)

r = r(t) = a0+ a1t + a2t2 +a3t3. (12)

Для определения a0, a1, a2, a3 задают обычно значения r и dr/dt на обоих концах сегмента. Обозначая dr/dt через , получаем

а0 = r(0);

a0 + a1 + a2 + a3 = r(1);

a1 = ; (13)

a1 + 2a2 + 3a3 =,

отсюда

а0 = r(0);

a1 = ;

a2 =3 r(1) - r(0)-2-; (14)

a3 =2 r(0) - r(1) ++.

Подстановкой (14) в (12) можно выразить r через r(0), r(1), и

r = r(t) =r(0)(1-3t2 +2t3) +r(1)(3t2 - 2t3)+ (t- 2t2 +t3) + (-t2+t3).

В 1970 году Безье обобщил результаты Фергюсона и предложил записывать параметрическое уравнение кривой в следующем виде

(15)

где r0, r1,…,rn - радиус-векторы (n+1) - вершин характеристической ломаной.

Полиномиальная кривая (15) проходит через точки Р0 и Рn, направления касательных в которых совпадают с направлениями векторов Р0Р1 и Рn-1Рn.

Уравнения кривых Безье второго и третьего порядков могут быть записаны соответственно

r = r(t) = (1-t)2 r0 + 2t(1-t)r1 + t2r2,

r = r(t) = (1-t)3 r0 + 3t(1-t2)r1 + 3t2(1-t)r2 +t3r3.

Пример 3. Построить сегмент кривой Безье, представленной характерными точками Р0(1,2), Р1(3,4), Р2(5,1).

Уравнение кривой в параметрическом виде будет записано

х(t) =(1-t)2+ 6t(1-t) + 5t2,

y(t) = 2(1-t)2+ 8t(1-t) + t2.

Вид этой кривой показан на рис.3.

Кубическая кривая Безье проходит через точки r0 и r1, имеет касательную в точке r0, идущую от r0 к r1, и касательную в точке r3, идущую от r2 к r3. Прямые Р0Р1, Р1Р2, Р2Р3 образуют характеристическую ломаную заданной кривой. Для построения кривой необходимо задать точки Р0 и Р3, затем на касательных к кривой в этих точках необходимо задать точки Р1 и Р2. Варьируя отрезками Р0Р1 и Р2Р3, можно изменять форму кривой (рис.4).

Рис. 3. Пример построения кривой Безье второго порядка

а) б)

Рис. 4. Примеры кривых Безье, построенных по 4 точкам

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

2.1.5 Сплайны

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

Интерполяционным кубическим сплайном называется функция S(x), обладающая следующими свойствами:

S(xi) = yi , i=0, 1, 2,…,m;

на каждом из отрезков [xi , xi+1], i=0, 1,…,m-1 функция

(16)

на всём интервале [х0,хm] функция S(x) имеет непрерывную вторую производную.

На каждом из отрезков [xi , xi+1] сплайн (16) определяется четырьмя коэффициентами, поэтому для полного построения на интервале [х0, хm] необходимо 4m параметров.

Для выполнения третьего условия достаточно потребовать непрерывности сплайна во всех внутренних точках xi, i = 0, 1, 2,…, m-1 (что даёт m - 1 условий связи на коэффициенты), а также его первой (m - 1 условий) и второй (еще m-1 условий) производных в этих точках. Вместе с условием (1) получаем

m - 1+ m - 1+ m - 1+ m + 1= 4m - 2

равенств. Недостающие два условия для определения коэффициентов можно получить, задав, например, значения первых производных на концах интервала [х0, хm]:

S'(x0) = L0 , S'(xm) = Lm.

2.2 Основы графического представления информации

2.2.1 Преобразование координат пространства в координаты экрана дисплея. Системы координат

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

Записывая уравнения диагоналей окон

, (17)

легко получить уравнения, связывающие координаты

Хэ = А1Хп + В1;, Yэ = А2Yп + В2, (18)

в которых коэффициенты А1, В1, А2, В2 легко вычислить, подставив в (17) координаты Хэн , Yэн , Хэв , Yэв , Xпн , Yпн , Хвп , Yвп.

Рис. 5. Окно пользователя и окно экрана

В КГ в зависимости от класса решаемых задач применяют такие координатные системы: аффинная, декартовая, полярная, система однородных координат и другие.

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

Локальная система координат - трёхмерная или двухмерная система координат, в которой производится моделирование объекта.

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

Мировая система координат - трёхмерная или двухмерная прямоугольная декартовая система координат, используемая для описания изображения и являющаяся входной системой координат КГ.

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

Рис. 6. Приборная система координат

2.2.2 Геометрические преобразования

Очень распространенной задачей КГ является определение местоположения пиксела, соответствующего точке с координатами (x, y) после поворота её относительно точки (x0, y0) на угол . Пусть r - длина вектора, соединяющего точку (x, y) с точкой (x0, y03) (рис. 7). Поскольку её значение при повороте не изменяется, справедливы следующие уравнения:

X - x0 = r cos( + ), (19)

Y - y0 = r sin( + ).

Рис. 7. Поворот точки (х, у) на угол относительно точки (хо, уо)

Разложив косинус и синус суммы двух углов в уравнении (19) и выполнив подстановку

х-x0 = rcos, y-y0 = rsin,

получим уравнение, определяющее значение (X,Y) новых координат:

X = x0 + (х - x0)cos - (y - y0)sin;

Y = y0 + (х - x0)sin + (y - y0)cos.

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

.

Изменение масштаба производится умножением значений координат на масштабный множитель. Матрицу изменения масштаба можно записать, зная масштабные множители Sx и Sy:

.

Отражение (относительно оси абсцисс) (рис. 8):

x1= x;

y1= - y.

Матрица отражения может быть записана

.

Рис. 8. Отражение точки относительно оси абсцисс

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

X =x + x;

Y =y + y.

Рис. 9. Перенос точки

Для того, чтобы записать матрицу переноса, необходимо ввести однородные координаты. В КГ однородные координаты вводят следующим образом: точке М(x, y) ставится в соответствие точка (x, y, 1) в пространстве (рис. 10).

Рис. 10. Ввод однородных координат

Матрица переноса может быть записана

.

Координаты точки M1(x1,y1) могут быть подсчитаны

.

Соответственно могут быть рассчитаны координаты точки M1 при повороте и масштабировании:

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

Вопросы и упражнения:

Что называется геометрической моделью объекта?

Какие требования предъявляются к геометрическому моделированию?

Назовите основные принципы конструирования кривых.

Какой недостаток у интерполирования полиномами?

Когда при интерполировании рекомендуется применять интерполяционный полином Ньютона?

В каких случаях рекомендуется применять интерполяционный полином Эрмита?

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

Постройте сегмент кривой Безье, представленной характерными точками P0(1,2), P1(3,4), P2(5,5), P3(8,1).

Как выполняется интерполяция кубическими сплайнами?

Какие системы координат используются в компьютерной графике?

Какие геометрические преобразования на плоскости используются в компьютерной графике?

3. Геометрическое моделирование объектов объёмной графики

3.1 Геометрические модели объектов трехмерной КГ

К геометрическим объектам КГ относятся:

а) точка, отрезок, прямая, плоскость;

б) кривые линии (плоские и пространственные);

в) многогранники;

г) поверхности: линейчатые и криволинейные;

д) элементарные геометрические тела (объёмные примитивы): параллелепипед, конус, цилиндр и т.д.;

е) составные геометрические объекты, полученные из объёмных примитивов с использованием операций геометрического синтеза: соединение, пересечение, разность, дополнение;

ж) объёмные фигуры произвольной формы.

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

3.1.1 Аналитические модели геометрических объектов трёхмерной КГ

В КГ принято, что ось Z направлена перпендикулярно плоскости экрана, а оси x и y лежат в плоскости экрана.

При описании геометрических объектов возможны два подхода:

точное аналитическое описание объектов;

описание объектов приближенными методами: интерполяции и аппроксимации.

Формы задания прямой в пространстве. В аналитической геометрии прямая, проходящая через точку в заданном направлении, определяется уравнением (рис. 11,а).

r = r1+ta,

где r1 - радиус - вектор заданной точки на прямой; a - единичный вектор, задающий направление; t - параметр.

Пример 4. Прямая, проходящая через точку (1, 2, 3) и в направлении (1/, -1/, 1/), определяется соотношением

Координаты точек этой прямой определяются

x = 1+, y = 2 - , z = 3+,

где =t/.

Если прямая проходит через две точки Р1 Р2, то для произвольной точки пространства Р (рис.11,б) запишем уравнение

Отсюда r = r1+t(r2 - r1),

и в конечном итоге r = (1- t)r1+tr2. (20)

а) б)

Рис. 11. Различные способы задания прямой

Пример 5. Прямая, проходящая через точки (1, 2, 3) и (5, 6, 7), определяется соотношениями

X = (1- t) + 5t =1 + 4t;

Y = 2(1- t) + 6t =2 + 4t;

Z = 3(1- t) + 7t =3 + 4t

Формы задания плоскости. Уравнение вида

Ax + By + Cz + 0 = 0,

где A, B, C не равны нулю одновременно, определяет плоскость.

Плоскость, проходящая через точки A, B, C, заданные радиусами-векторами a, b, c, (рис.12) определяется уравнением

r = a+ u(b-a) + х(c-a),

где u, х - параметры.

Рис. 12. Плоскость, проходящая через три точки

Формы задания кривых. В объемной КГ применяются плоские и пространственные кривые. Плоские кривые рассматриваются как граничные кривые отсека поверхности. Формы задания плоских кривых рассмотрены в 2.1.3 и 2.1.4. Пространственную кривую в трёхмерном пространстве можно получить как линию пересечения двух поверхностей или как траекторию движущейся точки. В КГ предпочтительней второй вариант.

Параметрическое задание пространственной кривой имеет вид

x =x(u);

y =y(u);

z =z(u);

a u b,

где функции x(u), y(u), z(u) - непрерывные на отрезке [a,b].

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

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

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

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

Рис. 13. Представление многогранника

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

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

Простейшим средством интерполирования в трехмерном случае является треугольник, заданный тремя точками: Р1, Р2, Р3. Поверхность треугольника, вершины которого находятся в указанных точках, определяется уравнением

, (21)

где u+1.

Из уравнения (21) следует, что T(1,0) = P1; T(0,1)=P2; T(0,0) = P3.

Кроме того, T(u,0) - прямая, соединяющая точки: P1и P2, T(0, ) - прямая, соединяющая точки P2 и P3; T(u,1-u) - прямая, соединяющая точки P1 и P2 (рис.14). Следовательно, уравнение (19) определяет плоскость, проходящую через точки P1, P2 ,P3.

Рис. 14. Пример отсека поверхности, заданного тремя точками

Такой способ интерполяции поверхности треугольниками получил название триангуляции.

Пример 6. Рассмотрим точки P1(1,0,0), P2(0,1,0) и P3(0,0,1). Координаты x, y, z каждой точки плоскости определяются следующими выражениями:

x (u, ) = u,

y (u, ) = ,

z (u, ) = 1-u- или

x + y + z = 1.

Более сложным является случай интерполяции, когда отсек поверхности задаётся четырьмя точками: P1, P2 ,P3, P4 (рис.15).

Рис.15. Пример четырех точек, определяющих поверхность

Поверхность Т(u, ) определяется уравнением

T(u, ) = P1(1-u)(1-)+ P2(1-u) +P3u(1-) + P4u. (22)

Если четыре точки компланарны, то Т(u, ) представляет плоский четырёх угольник, в противном случае - поверхность второго порядка.

Пример 7. Рассмотрим точки P1(0,0,0), P2(0,1,0), P3(1,0,0), P4(1,1,1). Координаты каждой точки интерполяционной поверхности определяются уравнениями, получаемыми подстановкой координат в (22)

x (u, ) = u, y (u, ) = , z (u, ) = u, или

z = xy.

Если в уравнении прямой (20) заменить векторы r1 и r2 на P(0, ) и P(1, ) - уравнения пространственных кривых, то получим уравнение линейчатой поверхности. Такая поверхность образуется прямой, скользящей по двум кривым, называемым направляющими. Уравнение линейчатой поверхности (рис.16) определяется

T(u, ) = (1-u)P(0,)+ uP(1,). (23)

Рис. 16. Линейчатая поверхность

Как обобщение интерполяции поверхности по четырем точкам можно рассматривать интерполяцию поверхности по методу С. Инаба, в котором заданы четыре точки и значения частных производных и в этих точках (рис.17).

Рис. 17. Задание поверхности по способу С. Инаба

Уравнение отсека поверхности (см. рис.17) в декартовых координатах может быть записано

; (24)

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

В 1960 году Кунсом был разработан метод интерполяции поверхности по четырем граничным кривым (рис.18).

Рис. 18. Порция поверхности по Кунсу

Рассматривая кривые P(0,) и P(1,) как направляющие, можем записать в соответствии с (23) уравнение линейчатой поверхности:

T1(u,) = (1-u)P(0, )+uP(1, ). (25)

Линейная интерполяция в -направлении даёт линейчатую поверхность

T2(u,) = (1-)P(u,0)+ P(u,1). (26)

Их сумма Т1+Т2 задаёт порцию поверхности, каждая из границ которой является суммой граничной кривой и отрезка, соединяющего концевые точки этой кривой. Это легко проверить: если подставить =0, то граница определяется не P(u,0), а выражением

T(u,0) + [(1-u)P(0, )+ uP(1,0)].

Следовательно, для получения поверхности интерполяции необходимо из суммы поверхностей Т1 и Т2 вычесть уравнение четырёх прямых, соединяющих концевые точки, аналогичных (22):

T(u,) = (1-u)P(0, )+uP(1, ) +(1-)P(u,0)+ P(u,1) -

- P(0,0)(1-u)(1-) -P(0,1)(1-u) - P(1,0)u (1-) - P(1,1)u. (27)

Последовательные подстановки u=0, u=1, =0, =1 подтверждают, что порция поверхности (27) имеет четыре заданные кривые своими границами.

Вспомогательные функции u; (1-u); ; (-1) называют функциями смещения, т.к. они соединяют воедино четыре отдельные граничные кривые. Можно обобщить формулу (27), если использовать вместо u(1-u), v(1-v) функции слияния (рис. 19).

Рис. 19. Графики функций смещения

Часто в КГ в качестве исходных данных для конструирования поверхности выступают не граничные кривые, а точки-ориентиры. Обобщая формы записи кривой Фергюсона (13) и кривой Безье (15) для n=3 получим соответственно уравнения поверхностей, допуская зависимость a0, a1, a2, a3 от второго параметра :

; (28)

, (29)

где - вершины характеристического многоугольника (рис.20).

Рис. 20. Характеристический многогранник поверхности Безье

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

Кроме поверхностей, полученных способами интерполяции и с помощью характеристических многогранников, в КГ широко используются объекты, представляющие собой поверхности вращения. Поверхность вращения получается вращением плоской кривой, которую называют образующей, вокруг некоторой прямой, называемой осью вращения. Каждая точка образующей при своём вращении вокруг оси описывает окружность. Коническая поверхность получается вращение прямой l вокруг оси i. При этом образующая и ось имеют точку пересечения (рис.21, а). Цилиндрическая поверхность получается в случае, если образующая l параллельна оси i (рис.21, б).

а) б)

Рис. 21. Примеры поверхностей вращения

Если за ось вращения принять ось у, образующую обозначить f(u), то уравнение поверхности может быть записано (рис.22)

r(u,) = f(u)(cose1 + sine2) + ua0, (30)

где e1, e2 - единичные векторы, идущие вдоль осей z и х; a0 - единичный вектор в направлении оси вращения.

Если образующая задана уравнением

F(u)= tg u,

то из уравнения (30) при a0=1 получаем уравнение конической поверхности вращения (см. рис.21, а) в параметрическом виде:

r(u,) = u[a0 + tg (cose1 + sine2)].

Рис. 22. Поверхность вращения общего вида

Представление объёмных примитивов. В КГ под объёмными примитивами (элементарными геометрическими телами) понимают тела: конус, цилиндр, сфера, параллелепипед, тор, пирамида, призма. Для того чтобы записать уравнение объёмного примитива, необходимо в уравнении поверхности вместо равенства перейти к неравенству. Например, уравнение

x2 + y2 +z2 = R2

есть уравнение сферы, а неравенство

x2 + y2 +z2 R2

задаёт объёмный примитив, также именуемый сферой.

Синтез составных геометрических объектов (СГО) из объёмных примитивов выполняется с использованием геометрических операций, аналогичных операциям над множествами. Цель геометрического синтеза -получение описания сложного объекта. К операциям геометрического синтеза относятся: объединение, пересечение, разность, дополнение. На рис.23 показаны примеры операций геометрического синтеза.

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

Метод контактного соединения используется для синтеза объектов из элементарных ГО, соединение которых осуществляется по плоским контурам. Примером контактного соединения будет объединение объектов, изображенное на рис.23, б.

Метод соединения с проникновением предполагает следующую последовательность шагов:

а) определение объёмных примитивов V1 и V2;

б) определение пар потенциально пересекающихся поверхностей;

в) аналитическое определение кривой пересечения для любой пары пересекающихся поверхностей и удаление тех сегментов кривой, которые не лежат внутри пересекающихся поверхностей;

г) сегментация поверхностей в соответствии с полученной линией пересечения;

д) удаление сегментов поверхностей.

Рис. 23. Операции геометрического синтеза

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

Задание толщиной: S = F1(C, P, D, L). Опорный контур С перемещается в плоскости Р (по умолчанию это плоскость z = 0); второй контур определяется переносом контура С по направлению вектора D на расстояние L.

Задание вращением: S = F2(C, A). С помощью контура С (разомкнутого или замкнутого) образуется сплошное тело вращением вокруг оси А.

Задание списком контуров: S = F3(LC, LP, LR, LS), где LP(i) - плоскость, в которой лежит LC(i) - контур, LR(i) - первый из соединяемых объектов, LS(i) - направление обхода контура.

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

3.2 Графическое представление информации в трёхмерной КГ

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

3.2.1 Ортогональные проекции

Проекции обеспечивают получение двухмерных изображений трёхмерных объектов. Наиболее распространённой является ортогональная проекция. При ортогональном проектировании изображение некоторой точки А трёхмерного объекта определяется как точка пересечения перпендикуляра, проведённого из этой точки на плоскость проекции, с плоскостью проекции (рис.24). Если последняя представляет собой плоскость XOY, то величина Z просто приравнивается к нулю (или какой-нибудь постоянной).