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

 

 

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

 

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ  ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

(ГОУВПО «ВГТУ»)

Естественно-гуманитарный

(факультет)

Кафедра  САПРИС_________________________________________________

 

 

КУРСОВАЯ  РАБОТА

 

по дисциплине Компьютерная геометрия и графика______________________

__________________________________________________________________

Тема  Отсечение отрезков алгоритмом Кируса-Бека                                          _

__________________________________________________________________

Расчетно-пояснительная записка

 

Разработал студент                      ___________________Д.С.  Чабанов_______

                                                            Подпись, дата         Инициалы, фамилия

Руководитель                                 ___________________В.Н.  Кострова______

                                                            Подпись, дата         Инициалы, фамилия

 

 

 

 

 

 

 

Защищена ___________________ Оценка __________________________ ____

                              дата

 

 

 

 

 

Воронеж 2011 

 

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

 

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ  ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

(ГОУВПО «ВГТУ»)

 

 

Кафедра_САПРИС_________________________________________________

 

ЗАДАНИЕ

на курсовую работу

 

по дисциплине Компьютерная геометрия и графика _____________________

__________________________________________________________________

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

_______________________________________________________________

Студент группы С-081      Чабанов Денис Сергеевич_____________________

                                                    Фамилия, имя, отчество

Номер варианта 5)_________________________________________________

Технические условия _процессор Intel Pentium 4, 1024 Mb ОЗУ, 80 Gb HDD,

_ОС Windows XP___________________________________________________

__________________________________________________________________

Содержание и объем  работы (графические работы, расчеты  и прочее)

общий объём работы – 45 листов , 12 рисунков , 2 таблицы ,  1 приложение._

Сроки выполнения этапов _ разработка алгоритма с 09.04.2010 по 20.04.2010 , разработка программы с 21.04.2010 по 05.05.2010, оформление пояснительной записки с 06.05.2010 по 14.05.2010                      __________

Срок защиты курсовой работы           ________________________________

 

Руководитель                             ________________________________________

                                                    Подпись, дата                Инициалы, фамилия

Задание принял студент           ________________________________________

                                                    Подпись, дата               Инициалы, фамилия  

Содержание

 

Введение           4

1 Теоретическая  часть         5

   1.1 Геометрическое моделирование в САПР     5

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

2 Практическая часть         23

   2.1 Постановка задачи        23

   2.2 Назначение          23

   2.3 Системные требования        23

   2.4 Структура программы        24

   2.5 Инструкция пользователю       25

   2.6 Контрольный пример        27

Заключение          28

Список литературы         29

Приложение. Листинг  программы       30

 

 

 

 

 

  Введение

 

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

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

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

 

 

Теоретическая часть

 

1.1 Геометрическое моделирование в САПР

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

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

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

Для реализации систем геометрического  моделирования важным являются три взаимосвязанных метода: 1) моделирования и представления геометрических моделей; 2) формирования и описания геометрических моделей; 3) отображение моделей на графических устройствах. Рассмотрим наиболее употребительные методы моделирования, формирования и отображения геометрических моделей.

Классификация методов геометрического моделирования.

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

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

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

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

1) омываемые средой (внешние обводы  самолетов, судов, автомобилей,  лопастей турбин и т.д.);

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

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

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

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

Метод каркасной или проволочной модели проектирования.

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

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

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

Модели  объемных тел.

Наибольшее  распространение в САПР, ориентированных  на проектирование машиностроительных объектов, получили системы моделирования твердого тела. В этих системах используется два типа геометрических моделей:

1) конструктивной геометрии (МКГ)  или структурная; 

2) поверхности или граничная. 

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

Модель  конструкторской геометрии трехмерного  объекта МКГ. Эта модель представляет собой бинарный древовидный граф G = (U, V), где U – множество вершин – базовых элементов формы, из которых конструируется объект; V – множество ребер, которые обозначают теоретико–множественные операции, выполняемые над соответствующими базовыми элементами формы. Каждый БЭФ в модели задан множеством атрибутов:

A = <X, Y, Z, a_x, a_y, a_z, S_x, S_y, ... S_n>,

где X, Y, Z – координаты точки привязки локальной системы координат БЭФ к системе координат синтезируемого объекта; a_x, a_y, a_z – углы поворота БЭФ относительно соответствующих осей координат; S_x, S_y, ... S_n – метрические параметры объекта.

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

Недостатком модели конструкторской геометрии  МКГ является отсутствие явных границ отсеков граней в случае, когда имеет место взаимопроникновение БЭФ при выполнении теоретико–множественных операций.

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

Кусочно–аналитическая граничная модель.

Для получения кусочно–аналитической граничной модели необходимо модель конструкторской геометрии МКГ преобразовать в геометрическом процессоре системы. Существует несколько алгоритмов преобразований модели.