Овременный период (с 1979 г.)

ачальный (1963-1970 гг.)

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

ериод ученичества (1971-1978 гг.)

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

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

— разрабатывать методы сглаживания поверхностей;

— моделировать эффекты освещения;

— генерировать структуры и рельефы;

— подавлять алиайзинг (ступеньки) в изображении.

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

— определяется базовое математическое обеспечение, не связанное с аппаратурой;

— проводится нормирование графических средств;

— стандартизуются графические средства.

овременный период (с 1979 г.)

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

Можно выделить основные моменты в этом периоде, касающиеся развития компьютерной графики:

— разработка так называемых параллельных архитектур на основе БИС (больших интегральных схем) и СБИС (сверхбольших интегральных схем); это означает, что компьютер получает возможность проводить различные вычисления, связанные с построением и преобразованием изображений «параллельно» на нескольких процессорах;

— разработка методов подавления алиайзинга на основе использования элементов с жесткой логикой или средств микропрограммирования (т.е. аппаратными средствами);

— моделирование отражения света от объектов;

— использование видеотехники: микширование, врезка изображений, запись на видеокассеты и диски и т.д.

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

— преобразование цветовых пространств;

— классификация и сравнение алгоритмов удаления невидимых линий, алгоритмов синтеза изображений;

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

5. Основное назначение системы Автокад

Основное назначение системы Автокад:

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

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

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

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

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

Если просто попробовать сделать даже простейший чертеж с помощью системы Автокад – или любой другой аналогичной – то затраты на получение изображения, особенно на первых порах, могут оказаться больше, чем с помощью карандаша и бумаги. По экспертным оценкам, по сравнению с ручным способом затраты времени при построении нового чертежа изменяются от сокращения на 20 % до увеличения вдвое. Некоторый выигрыш получается при больших объемах надписей, штриховок, простановок условных обозначений, вычерчивании рамок и «штампов» — особенно если эти элементы созданы заранее.

6. Что означает аббревиатура AutoCAD?

На английском языке сам термин AutoCAD (по-русски мы пишем и произносим как Автокад) представляет собой аббревиатуру (сокращение) от группы слов, последние из которых Computer Aided Design (CAD) с некоторой приблизительностью можно перевести как «создание с помощью компьютера». Таким образом, соответствующий пакет программ ориентирован исключительно на использование его в персональных компьютерах (ПК).

7. Основные преимущества Автокада перед другими графическими системами

Основные преимущества Автокада перед другими графическими системами:

1. Очень широкий набор команд. Так, уже в 10-й версии Автокада насчитывалось более 420 команд, в более поздних версиях это число значительно больше.

2. Хорошее сочетание простых и сложных функций; так, не нужно переходить в специальные меню при пользовании такими разными по сложности командами, как «отрезок» и «масштаб» и т.п.

3. Интуитивное понимание назначения команд. В русскоязычных версиях Автокада команды не допускают различного толкования, и смысл команды «отрезок» не спутать с командой «сотри» и т.д. В версиях, начиная с 12-й, команды выведены на экран в виде так называемых кнопок, где смысл команды ясен из ее условного изображения на кнопке (пиктограммы). Название команды дублируется при обращении к соответствующей кнопке с изображением команды в виде словесной формулировки.

4. Широкий выбор периферийных устройств и их модификаций. Это означает, что Автокад позволяет использовать аппаратные возможности разных компьютеров (как это принято называть «разных конфигураций») в полном объеме.

5. Наличие различных языковых — русской и английской — версий.

6. Возможность изменять набор (меню) команд, т.е. составлять свое «персональное» меню как из стандартных команд, наиболее часто используемых пользователем, так и дополняя это меню своими командами.

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

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

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

8. Определения систем координат: мировая, пользовательская, нормированная, однородная, аппаратная

Мировая система координат (МСК) — так называемая встроенная внутренняя система координат. Это обычная декартова система координат, горизонтальная ось Х, вертикальная — У. Начало системы координат фиксировано в левом нижнем углу рабочего поля. При необходимости построения трехмерных изображений ось Z вводится по правилу правой руки. Эту систему координат пользователь изменить не может – ни положения начала отсчета, ни направления осей. Единственное, что можно сделать в этой системе координат – изменить единицы измерения, что приводит к изменению размеров рабочего поля.

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

Нормированная система координат(НСК) – это заданные независимо от конкретного устройства координаты, меняющиеся в диапазоне от 0 до 1.

Если координаты (х, у) любого устройства – монитора, принтера и т.д. – могут меняться в пределах 0 ? x ? хmax , 0 ? y ? ymax, то нормированные координаты вводятся с помощью следующих соотношений:

x := x/xmax, y := y/ymax.

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

Координаты устройства, или аппаратная система координат (АСК) – это координатная система конкретной установки (экрана, графопостроителя, принтера и т.д.).

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

9. Идеи Автокада: слои, привязка, системы координат, рисунки-прототипы

Слои

Одно из наиболее интересных изобретений компьютерной графики, используемое также и в Автокаде — так называемые слои. Их можно рассматривать как прозрачные листы (кальки) с изображениями отдельных частей рисунка. Каждый слой может нести свою информацию, при этом из итогового рисунка можно удалять отдельные слои. Так, в одном слое изображаются осевые линии, во втором – основные, на третьем – штриховка, на четвертом – размеры, и т.д. При этом границы чертежа, рисунка, единицы измерения, системы координат для всех слоев остаются едиными. При работе в Автокаде слой определяется своим именем, и в каждом слое можно использовать свои типы линий, цвет изображения. На экране можно наблюдать все, что нарисовано в разных слоях, или часть слоев отключить (“заморозить”), и в этом случае то, что на этих слоях нарисовано, на экран не выводится.

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

Средства привязки

1. Можно включить так называемую сетку на экране, и перемещение курсора будет идти только по узлам сетки. Расстояние между узлами сетки устанавливается пользователем, причем можно делать разные шаги сетки по горизонтали и по вертикали.

2. При построении сложных рисунков можно использовать средства привязки типа ПЕРЕСЕЧЕНИЕ, НОРМАЛЬ, ЦЕНТР и т.д. Если сделать простейший чертеж с помощью мыши – например, изображение треугольника – и просмотреть его затем в увеличенном масштабе, то в большинстве случаев соединение в конечной точке построения треугольника будет неточным. Отрезки либо пересекутся, либо окажутся несоединенными. Это связано с точностью позиционирования курсора на экране с помощью мыши – а она ограничена даже чисто технически. Использование средств привязки устраняет этот недостаток.

истемы координат.

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

Рисунки-прототипы

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

Если не заказывать никакого прототипа, Автокад все равно предоставляет некоторый стандартный вариант с именем acad.dwg. Следует заметить, что все рисунки, создаваемые в Автокаде, хранятся в виде файлов с расширением .dwg (от английского слова drawing — рисунок).

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

10. Определение примитива. Примеры примитивов в Автокаде

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

Примеры примитивов:

— точка (маркер);

— линия (ломаная);

— дуга;

— штриховка;

— текст

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

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

Особый примитив — ПОЛИЛИНИЯ (в ранних версиях был только примитив ПОЛОСА). Это связанная последовательность отрезков и дуг, и рассматривается она Автокадом как единый элемент (примитив) рисунка.

11. Что такое ядро графической системы? Для чего оно создано?

Ядром графической системы (ЯГС) называется первый международный стандарт в области машинной графики.

Этот стандарт определяет:

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

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

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

Самое важное преимущество, получаемое за счет наличия ЯГС:

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

12. Расшифруйте требования к графической системе: согласованность, устойчивость, приборная независимость

1. Согласованность: обязательные требования стандарта не должны противоречить друг другу.

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

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

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

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

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

13. Расшифруйте требования к графической системе: совместимость, ортогональность, прозрачность

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

Применительно к графическим системам это означает, например, что большинство требований государственных стандартов (ГОСТ, ГОСТ-Р) или единой системы конструкторской документации (ЕСКД) при выполнении чертежей должны выполняться если не автоматически, то при минимальных усилиях пользователя – система должна быть «настроена» на их выполнение. На примере системы Автокад очень показательны в этом отношении способы простановки размеров на любом чертеже или на любой схеме – их практически невозможно поставить неправильно, сама система делает это правильно в соответствии со сделанными нами установками.

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

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

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

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

14. Расшифруйте требования к графической системе: неизбыточность, компактность, приборная широта

1. Неизбыточность: на данном функциональном уровне не нужны возможности, которые не используются.

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

2. Компактность: результат должен достигаться минимальным числом функций и их параметров.

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

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

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

15. Расшифруйте требования к графической системе: комфортабельность, полнота, эффективность

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

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

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

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

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

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

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

16. Расшифруйте требования к графической системе: надежность, эффективность, прозрачность

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

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

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

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

17. Обязательный набор примитивов в соответствии с требованиями ЯГС. Атрибуты примитивов. Зависимые и независимые, постоянные и временные атрибуты

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

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

ЯГС как стандарт определяет обязательный набор примитивов:

1. Ломаная. В Автокаде буквально такой команды нет. Но, если внимательно проследить, как работает команда «Отрезок», то это по существу и есть команда построения ломаной как серии последовательно соединенных отрезков.

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

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

4. Полигональная область – пустой, закрашенный или заштрихованный многоугольник. Например, в Автокаде этот примитив представляет собой обычный замкнутый многоугольник, число сторон которого – от 3 до 1024 – задается пользователем.

5. Матрица ячеек — обобщение матрицы пикселей растрового устройства. Это матрица ячеек, каждая из которых может иметь свой цвет или яркость. Сама такая матрица может рассматриваться как растр, но это уже не технический, а математический растр. Использование такого «растра» можно часто увидеть на телевидении – когда на месте обычного изображения лица человека, узнавание которого нежелательно, помещается своего рода маска. Она и представляет собой матрицу ячеек, каждая из которых включает в себя определенное точек технического растра, обычно при этом атрибуты этой ячейки (цвет, яркость) имеют средние значения по соответствующему ансамблю элементов технического растра.

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

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

22. Определения сглаживания и интерполяции, их отличия

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

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

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

Рассмотрим задачи геометрического моделирования при проектировании кривых и поверхностей.

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

1) построение кривой, проходящей через эти точки (интерполяция);

2) построение кривой, проходящей вблизи этих точек (сглаживание).

В качестве примера на рис.16 для одного и того же набора точек приведены две кривые: верхняя кривая – интерполирующая, нижняя – сглаживающая.

При решении той и другой задачи сразу возникают минимум две проблемы:

— в каком классе кривых искать нужную кривую;

— как искать эту кривую.

Остановимся на первой проблеме.

Рис. 16. Примеры интерполирующей (верхней) и сглаживающей (нижней) кривых для одного и того же набора точек

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

Пусть на плоскости задан набор точек (х, у ), i = 0, 1, …, m, причем

х0x1x2

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

23. Определение полинома Лагранжа. Достоинства и недостатки

Известен полином, носящий имя Лагранжа. Он определяется соотношением

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

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

Это не что иное, как уравнение прямой, проходящей через заданные точки (х0, у0), (х1, у1). Для случая трех точек получится квадратная парабола, для четырех точек – кубическая парабола, и т. д. Если число заданных точек, пронумерованных от 0 до m, составляет m + 1, то степень соответствующего полинома Лагранжа на единицу меньше и равна m.

Достоинства полинома Лагранжа:

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

2) полином однозначно определяется, т.е. при заданном наборе значений хi и уi его выражение всегда получается одним и тем же;

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

Недостатки полинома Лагранжа:

1) с ростом числа точек растет и степень полинома (m -1 при m точках), и растет степень уклонения кривой от аппроксимируемой зависимости;

2) изменение или добавление хотя бы одной точки приводит к изменению всего полинома.

24. Определение кубического сплайна. Условия для определения его коэффициентов

Термин «сплайн» произошел от английского слова spline — так называлась гибкая полоска стали, с помощью которой проводятся гладкие кривые через заданные точки. Этот способ построения кривых использовался при строительстве лодок и корпусов кораблей с гладкими обводами.

Определение:

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

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

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

3. На всем протяжении [x0, xm ] у функции S(x) есть непрерывная вторая (по меньшей мере) производная.

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

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

S(xi – 0) = S(xi + 0), i = 1, 2, …, m – 1 )

— это дает m – 1 условие. Обратим внимание, что в крайних точках эти условия нельзя сформулировать. Для первой производной тоже m — 1 условий, и для второй. Если учесть еще первое требование – m + 1 условие — то всего получается 4m — 2 условия. Два недостающих условия получаются, если задать, например, значения первых производных в граничных точках при i = 0 и i = m (это своего рода граничные условия)

S/(x0) = l0; S/(xm) = lm;

и тогда задача решается однозначно. Последние два условия по существу означают, что с их помощью мы можем задать направления «входа» в соответствующую кривую при х = х0 и выхода из нее при х = хm.

26. Растровое представление объекта – определение. Непосредственные и косвенные соседи на растре. Алгоритм Брезенхема построения растровой развертки отрезка

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

Растровое представление объекта – представление геометрической фигуры в виде множества элементов растра на целочисленной плоскости.

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

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

Знание проблем растровой генерации полезно в следующих случаях:

— при наличии (или задании) зависимости атрибутов пиксела от каких-либо условий, например, от положения пикселя на границе или внутри многоугольника;

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

Растровая развертка отрезка — это процесс последовательной инициализации множества пикселей экрана, изображающего отрезок. Можно отметить, что растровое изображение отрезка довольно очевидно для трех случаев – когда он ориентирован строго горизонтально, вертикально или под углом 45о к этим направлениям. Тогда на квадратной сетке элементов растра никаких проблем с выбором элементов, которые следует «инициализировать» (т.е. заставить изменить цвет и/или яркость, чтобы получить изображение на общем фоне экрана), не возникает. В общем случае, при рисовании отрезка произвольной ориентации, дело обстоит сложнее.

Если даже ограничить класс растровых представлений простыми растровыми кривыми, то уже возможны два типа представлений — 8- и 4-связные (или слабо- и сильносвязные).

Рассмотрим так называемое «простое» решение задачи.

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

Можно предложить следующий алгоритм последовательной генерации точек.

Если М1(х1, у1), М2(х2, у2) — границы отрезка, то его уравнение:

y2 — y1

y = y1 + k*(x — x1), x1? x ? x2, k = ,

x2 — x1

причем далее принимаем 0 ? k1. То, что это уравнение прямой, очевидно. При этом соответствующая прямая проходит через заданные точки: при х = х1 будет у = у1, а при х = х2 получим у = у2.

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

Dx := 1; Dy := abs((y2 — y1)/(x2 — x1));

X := x1; y := y1; L := x2 — x1;

for i := 0 to L — 1 do begin

PutPixel(x, Round(y));

X := x + Dx; y := y + Dy; end.

Работа этого алгоритма происходит следующим образом: начинаем с начальной точки (x1, y1), «рисуем» ее, инициализируя соответствующий пиксель. Затем получаем очередную точку на отрезке и инициализируем пиксель, ближайший к ней.

Условие k1 необходимо, чтобы при построении растровой развертки не пропустить ни одной точки: по координате х шагаем с шагом Dx = 1, по y с меньшим шагом, округляя значения y до целых значений. Если k1, то в этом алгоритме нужно поменять местами переменные x и y.

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

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

х := x1; y := y1; n := x2 — x1; m:= y2 — y1; d := m/n; e := 0;

for i := 1 to n do begin {шаг по x и вычисление отклонения}

x := x + 1; e := e + d;

{если отклонение по оси ординат от текущего значения у больше 1/2, то нужно увеличить у на 1 и скорректировать величину е от нового значения у}

if e0.5 then begin y := y + 1; e := e — 1; end;

PutPixel(x,y);

end;

В этом случае получается 8-связное представление отрезка, т.к. переход к следующей точке осуществляется на одну из соседних 8 клеток.

Более общие алгоритмы такого рода (в частности, без ограничения k1 ) для 8- и 4-связных разверток называются алгоритмами Брезенхема.

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

Многоугольник – фигура, ограниченная на плоскости простой (несамопересекающейся) ломаной замкнутой линией.

Ломаная задается своими вершинами Аi (хi ,уi ), i = 1, 2, …, n.

Соседние точки с номерами i и i + 1 — смежные вершины.

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

Теорема Жордана:

Простая замкнутая плоская ломаная разбивает плоскость на две связные компоненты: 1) ограниченную область, или внутренность многоугольника; 2) неограниченную внешнюю часть.

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

Алгоритм должен отличать внутренние и внешние точки.

Рис. 22

Обозначим ребра многоугольника Еi :[Ai , Ai+1 ], i = 1, 2, …, n (при этом вершина с номером n + 1 совпадает с вершиной номер 1).

Пусть Рi(х, у) — некоторая точка плоскости, не принадлежащая ломаной (границе многоугольника), см. рис. 22. Нужно определить, находится ли она внутри многоугольника.

Из точки Рi ведем горизонтальную полупрямую влево (т.е. точка Рi -правый конец полупрямой). При достаточно большом удалении конечной (условно конечной, так как полупрямая теоретически бесконечна) точки этой полупрямой Q от точки Рi варианты:

— нет пересечений полупрямой с границей многоугольника, тогда Рi — внешняя точка;

— есть четное число пересечений полупрямой с границами многоугольника; тогда Рi – внешняя для этого многоугольника точка;

— есть нечетное число пересечений; Рi — внутренняя точка.

Пересечение называется существенным, если PiQ пересекает ломаную, а не касается одной из вершин.

Правила:

1) пересечения отрезка с горизонтальными ребрами игнорируются;

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

4.5 Алгоритм определения точки пересечения произвольного

луча с геометрическими объектами

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

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

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

Статьи к прочтению:

Провал во времени (1979)

Похожие статьи: