Программирование математических объектов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ

КАФЕДРА КИТ

Курсовая работа

2008

СОДЕРЖАНИЕ

ВСТУПЛЕНИЕ

1. Математические объекты

1.1 Группы

1.2 Графы

2. Справка по работе с программой

2.1 Назначение программного продукта

2.2 Обучение работе с программным продуктом

2.3 Ограничения применения 10

3. Нереализованные возможности

4. Основная форма

5. Методы создания программы

5.1 Матричные преобразования

5.2 Создание одноцветного треугольника

6. Программа

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ВСТУПЛЕНИЕ

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

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

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

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

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

1. Математические объекты

1.1 Группы

Группа - оперативное множество, в котором действует процедура умножения и которое подчинено следующим условиям:

замкнутости: для каждой пары g1g2=g3, причем g3 должен принадлежать группе G: g1g2 G; g1g2 = g3 G;

наличия тождественного элемента e: среди множества элементов группы G справедливы равенство eg = g; ge = g; e,g G;

наличие обратных элементов: для всякого g из G должен отыскаться единственный ему обратный элемент g, принадлежащий G, при умножении на который получился тождественный элемент e. e = qq; e,g,g G;

ассоциативности: для любых трёх элементов g1, g2, g3 из G справедливо равенство: g1(g2g3) = (g1g2)g3. Условия ассоциативности выполняется для квадратных матриц.

Линейное преобразование A вектора x в вектор c осуществляется с помощью квадратной матрицы y = Ax.

Если есть прямое преобразование, то должно быть и обратное, при условии, что A имеет A. y = Ax;

x = Tx ;y = Tx ; Следовательно Ty = ATx; Умножим с лева на T , получим y = TATx;

Отсюда следует формула прямого преобразования подобия.

Формулу обратного преобразования подобия можно получить, умножив на T с права:

Если Ax = x; то ненулевой вектор x является собственным вектором. Для нахождения собственных векторов используют формулу

где E - единичная матрица.

Корни многочлена P() = det(A - E) = 0 подставляют в формулу (*) и получают собственные векторы x.

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

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

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

Вот как эта матрица будет выглядеть:

1.2 Графы

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

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

G (V,E) = V; E, n(V) > 0, E V V,

где для неориентированного графа E = E-¹ (бинарное отношение E симметрично).

Минимальный граф состоит из одной вершины.

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

Пусть v₁ и v₂ - вершины, e₁ = (v₁ , v₂ ) - соединяющее их ребро.

Тогда вершина v₁ и ребро e₁ инцидентны, вершина v₂ и ребро e₁ также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

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

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

1 Отношение инцидентности задано матрицей смежности:

- столбцы и строки матрицы - вершины графа;

- для смежных вершин элемент матрицы равен1, для остальных - 0;

- для неориентированного графа эта матрица всегда симметрична;

число рёбер равно числу единиц выше или ниже главной диагонали матрицы ( включая элементы на диагонали).

2 Отношение инцидентности задано матрицей инцидентности:

- столбцы матрицы соответствуют вершинам графа, а строки - рёбрам;

- если ребро e_i инцидентно вершине v_j, то элемент матрицы _ij=1, в противном случае - _ij = 0.

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

Для ориентированного графа при заполнении матрицы:

_ij = -1,если v_j - начало ребра;

_ij =1,если v_j -конец ребра;

_ij = (где - любое число, кроме -1,1,0),если ребро - петля в вершине v_j_;

в остальных случаях _ij = 0.

3 Граф задан списком ребер.


e_i	v_i, v_j
1	a, b
2	b, d
…

Примечание. Здесь e_i -ребро, v_i_, v_j - пара вершин, соединяемых этим ребром.

Граф связан, если любая пара его вершин связана ребром.

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

Граф H называют частью графа G, если множество вершин графа H принадлежит множеству вершин графа G и множество рёбер графа H принадлежит множеству рёбер графа G, т.е.:

V(H) V(G); E(H) E(G).

Часть графа H называется суграфом, если она содержит все вершины графа G.

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

Подграф G(U) графа G на множестве вершин U ( U V ) - это часть графа, которой принадлежат все ребра с обоими концами из U.

Звёздный граф для вершины v (v G) состоит из всех рёбер с началом и концом в вершине v. Множество вершин звёздного графа состоит из вершины v и других смежных с ней вершин.

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

Вершина v_о, инцидентная ребру e₁ и не инцидентная ребру e₂, называется началом маршрута в графе G.

Вершина v_n, инцидентная ребру e_n и не инцидентная ребру e_n_-1, называется концом маршрута.

Число ребер маршрута называется его длиной.

Если вершины v_о и v_n совпадают, то маршрут называется циклическим (или просто циклом).

Отрезок конечного или бесконечного маршрута сам является маршрутом.

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

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

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

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

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

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

2. Справка по работе с программой

2.1 Назначение программного продукта

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

2.2 Обучение работе с программным продуктом

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

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

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

Рисунок 1

Рисунок 2

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

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

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

В программном продукте действительны такие функциональные клавиши:

Esc - выход из программы в операционную систему;

F1 - справка о программном продукте;

F9 - режим просмотра ;

X - вращение объекта вокруг оси X;

Y - вращение объекта вокруг оси Y;

Z - вращение объекта вокруг оси Z;

В программном продукте есть такие пункты меню "Файл", "Вид", "Помощь".

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

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

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

Опция "Выход" предназначена для выхода из программы в операционную систему.

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

Так же пункт меню "Помощь" содержит опцию "О программе", в которой можно узнать краткую информацию о программном продукте и его разработчике.

2.3 Ограничения применения

В программе желательно использовать 16 битный режим, причём разрешение графического режима, выраженное в пикселях, не имеет значения. Допускаются только 8 битные, 16 битные и 32 битные графические режимы. Во всех остальных режимах, например, 2 битных, 4 битных, 24 битных программа работать не будет.

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

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

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

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

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

3. Нереализованные возможности

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

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

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

Текстуры бывают: аффинные, точные (перспективно - корректные), параболические. Текстуры можно накладывать на все трёхмерные объекты.

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

4. Основная форма

Основная форма содержит такие компоненты как:

Main Menu - Предназначен для добавления к главной программе главного меню. Является компонентом Standart. Компонент Main Menu не визуальный компонент. Редактор меню вызывается после выбора опции Items. В редакторе можно создавать пункты меню проименовывая их с помощь свойства Caption. Переходя от одной компоненте к другой можно с помощью того же свойства Caption отредактировать пункты меню. Чтобы вставить линию разделитель нужно в свойстве Caption первой позицией указать символ "-" (дефис). После окончания создания пунктов меню редактор меню надо закрыть.

BitBtn - Этот компонент предназначен для создания кнопки с картинкой. В системе имеется набор готовых шаблонов.

После размещения объекта на форме изображение, помещаемое на кнопку, задаётся в свойстве Glyph (Значок). При этом вызывается редактор, с помощью которого выбирается нужная картинка (в формате BMP). Каждая такая картинка может состоять из 4 частей, равных по ширине. Первая часть - изображение кнопки в обычном состоянии, вторая - изображение "отключённой" кнопки, третья - изображение кнопки после щелчка мыши, изображение на нажатой кнопке. Число составных частей задаётся в свойстве NumGlyph (от 1 до 4). Расстояние от картинки до границ кнопки (в пикселях) можно указать в свойстве Margin. В свойстве Kind задаётся реакция кнопки на щелчок.

Button - Компонент предназначен для создания кнопок на форме и обработки события нажатия кнопки. Расположен на панели Standart. Имя кнопки указывается в поле Name, а выводимый текст на кнопке в свойстве Caption.

Combo Box - Компонент Поле со списком. Представляет собой вариант списка, с присоединённым дополнительным полем, в котором отображается выбранный элемент списка. Это же поле может использоваться для ввода новых элементов или для быстрого поиска элементов по начальным символам. Если на экране отображается только присоединённое поле ("раскрывающийся список"), то для раскрытия списка можно использовать клавиатурную комбинацию Alt+Вниз.

Open Dialog - Компонент предназначен для выбора файла с целью последующего открытия; Свойства класса TOpenDialog приведены в табл. 1

Таблица 1 - Свойства класса TOpenDialog


Свойство	Назначение
DefaultExt	Расширение имени, используемое по умолчанию. Добавляется в конец выбраного пользователем имени файла, если расширение не указано явно.
FileName	Выбранное пользователем имя файла вместе с полным путём поиска
Files	Список выбранных имён файлов. В свойстве Options должен быть включён флажок ofAllowMultiSelect
Filter	Набор масок, в соответствии с которыми отбираются имена файлов для отображения в диалоговом окне. Каждая маска состоит из двух частей: названия и шаблона, - разделённых символом \|. Одному названию могут соответствовать несколько шаблонов. Маски отделяются друг от друга символом \|
FilterIndex	Номер текущей маски. Нумерация начинается с 1
HistoryList	Список ранее выбранных файлов (тип Strings)
InitialDir	Текущий каталог, содержимое которого отображается при первом открытии диалогового окна
Options	Набор флажков, определяющих окна выбора файлов.
Title	Заголовок диалогового окна

Save Dialog - Этот компонент практически ничем не отличается от компонента Open Dialog за исключением нескольких настроек, специфичных для процесса сохранения файла.

Label - Компонент находится на панэле Standart. Предназначен для вывода текста на форме с помощью свойства Text.

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

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

TDXDraw - Этот компонент находится на вкладке DelphiX. Он предназначен для вывода двухмерной и трёхмерной графики, используя Direct Draw и Direct X. Разрешение выводимой графики задаётся в свойстве Display. Вид курсора задаётся в свойстве Cursor. Метод DXDraw.Surface.Fill(Color) - заполняет видеостраницу цветом Color. С помощью свойства DXDraw.Surface.pixels[x, y]:=Color - ставится точка на виртуальной видеостранице. С помощью метода DXDraw.Flip - невидимая видеостраница делается видимой. Схема обрисовки изображения на двух видеостраницах: видимой и не видимой делает возможной создать анимацию без мерцания изображения.

5. Методы создания программы

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

Рисунок 3

Здесь буквами x, y, z обозначены положительные направления осей Ox, Oy и Oz соответственно. Также предполагается, что камера неподвижна и находится в точке с координатами (0,0,-dist), ось зрения камеры направлена по оси Oz, а именно в точку (0,0,0) (т.е. camera target = (0,0,0)), ось Ox с точки зрения камеры направлена слева направо, ось Oy - снизу вверх, ось Oz - вглубь экрана. Размер экрана - xSize на ySize пикселей.

Здесь и далее используются обозначения:


sx, sy	координаты проекции точки на экране
x, y, z	3D координаты точки,
Dist	расстояние от камеры (она находится в точке (0,0,-dist)) до начала координат,

Для созданя трёхмерных объектов необходимы примитивы. Такими примитивами являются элементарные трёхмерные объекты - треугольные грани. У каждой треугольной грани есть три вершины - три точки, имеющие трёхмерные координаты. Чтобы спроецировать их на плоскость, т. е. из трёхмерных координат x,y,z получить двухмерные sx, sy надо пользоваться формулой:

sx = xSize/2+x*dist/(z+dist); sy = ySize/2-y*dist/(z+dist);

5.1 Матричные преобразования

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

Введем несколько терминов. n-мерный вектор, он же вектор размерности n, он же вектор размера n: упорядоченный набор n действительных чисел. Матрица размера m на n (будет обозначаться как m*n, mxn): таблица размера m на n, в каждой клетке которой - действительное число.

Вот пример матрицы 3x3:

[ 15 y*z 0.6 ]

[ 7 -3 91 ]

[ sin(x) 0.123 exp(t) ]

Вектор будем записывать в столбик и рассматривать его как матрицу размера n*1.

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

[ 1 ] [ 4 ]

[ 2 ] * [ 5 ] = 1*4 + 2*5 + 3*6 = 32

[ 3 ] [ 6 ]

Операция векторного произведения: определена для (n-1) вектора одинакового размера n. Результат - вектор, причем, перпендикулярный всем множителям.

Замечание: результат меняется от перестановки мест множителей!

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

[ Ax ] [ Bx ] | i j k | [ Ay*Bz-Az*By ]

AxB = [ Ay ] x [ By ] = | Ax Ay Az | = [ Az*Bx-Ax*Bz ]

[ Az ] [ Bz ] | Bx By Bz | [ Ax*By-Ay*Bx ]

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

[ 1 x 500 ] [ 8 a 3 ] [ 9 a+x 503 ]

[ 2 y 600 ] + [ 9 b 2 ] = [ 11 b+y 602 ]

[ 3 z 700 ] [ 10 c 1 ] [ 13 c+z 701 ]

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

Операция умножения двух матриц: определена для двух матриц таких размеров a*b и c*d, что b = c. Например, если b = c, но a d, то при перестановке множителей операция будет вообще не определена. Результатом умножения матрицы A размером a*b на матрицу B размером b*d будет матрица C размером a*d, в которой элемент, стоящий в строке i и столбце j, равен произведению строки i матрицы A на столбец j матрицы B. Произведение строки на столбец определяется как сумма произведений соответствующих элементов строки и столбца. Например, умножение строки на столбец (они должны быть равной длины, поэтому и такие ограничения на размеры матриц):

[ 4 ]

[ 1 2 3 ] * [ 5 ] = 1*4 + 2*5 + 3*6 = 32

[ 6 ]

А чтобы перемножить две матрицы, надо эту операцию проделать для каждого элемента. Вот пример:

[ 1 2 3 ] [ 0 3 ] [ 1*0+2*1+3*2 1*3+2*4+3*5 ]

[ 4 5 6 ] * [ 1 4 ] = [ 4*0+5*1+6*2 4*3+5*4+6*5 ] = ...

[ 7 8 9 ] [ 2 5 ] [ 7*0+8*1+9*2 7*3+8*4+9*5 ]

Умножение и сложение матриц обладают почти тем же набором свойств, что и обычные числа, хотя некоторые привычные свойства не выполняются (например, A*B B*A); на самом деле требуется знать, что произведение вида A*B*C*D*... не зависит от того, как расставить скобки. Или, что

A*(B*C) = (A*B)*C.

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

Перенос точки (точки будут также рассматриваться как вектора с началом в начале координат и концом в собственно точке) с координатами (x,y,z) на вектор (dx,dy,dz) делается простым сложением всех координат. То есть результат - это (x+dx,y+dy,z+dz). Подобно сложению вектора-точки с вектором-переносом.

Рассмотрим для примера поворот точки (x,y,z) относительно оси z. В этом случае z не меняется, а (x,y) меняются так же, как и при 2D повороте относительно начала координат.

Покажем координаты точки A - результата поворота A(x,y) на угол alpha (рис. 4).

Рисунок 4

Пусть r = sqrt(x*x+y*y). Пусть угол AOx равен phi, тогда из рисунка видно, что cos(phi) = x/r, sin(phi) = y/r. Угол AOA равен по условию alpha. Отсюда

x = r*cos(alpha+phi) = r*(cos(alpha)*cos(phi)-sin(alpha)*sin(phi)) =

= (r*cos(phi))*cos(alpha)-(r*sin(phi))*sin(alpha) =

= x*cos(alpha)-y*sin(alpha)

y = r*sin(alpha+phi) = r*(cos(alpha)*sin(phi)+sin(alpha)*cos(phi)) =

= (r*cos(phi))*sin(alpha)+(r*sin(phi))*cos(alpha) =

= x*sin(alpha)+y*cos(alpha)

Для трехмерного случая, таким образом

x = x*cos(alpha)-y*sin(alpha)

y = x*sin(alpha)+y*cos(alpha)

z = z

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

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

[ x ] = [ cos(alpha) -sin(alpha) 0 ] [ x ]

[ y ] = [ sin(alpha) cos(alpha) 0 ] [ y ]

[ z ] = [ 0 0 1 ] [ z ]

То есть поворот на угол alpha задается одной и той же матрицей, и с помощью этой матрицы (умножая ее на вектор-точку) можно получить координаты повернутой точки. С одной стороны умножение матрицы на вектор требует больше операций, чем расчет x и y по формулам.

Нос другой удобство матриц для заключается как раз в свойстве

A*(B*C) = (A*B)*C. Пусть делается несколько поворотов подряд, например, пять (столько, сколько надо для поворота относительно произвольной оси), и пусть они задаются матрицами A, B, C, D, E (A - матрица самого первого поворота, E - последнего). Тогда для вектора p мы получаем

p = E*(D*(C*(B*(A*p)))) = E*D*C*B*A*p = (E*D*C*B*A)*p = (E*(D*(C*(B*A))))*p = T*p,

где T = (E*(D*(C*(B*A)))) матрица преобразования, являющегося комбинацией пяти поворотов. Посчитав один раз эту матрицу, можно в дальнейшем применить довольно сложное преобразование из пяти поворотов к любому вектору с помощью всего одного умножения матрицы на вектор.

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

На самом деле, эти преобразования тоже легко записываются в виде матриц. Только вместо матриц 3x3 и 3-мерных векторов используются так называемые однородные 4-мерные координаты и матрицы 4x4. При этом вместо векторов вида

[ x ]

[ y ]

[ z ]

используются вектора вида

[ x ]

[ y ]

[ z ]

[ 1 ]

а вместо произвольных матриц 3x3 используются матрицы 4x4 такого вида:

[ a b c d ]

[ e f g h ]

[ i j k l ]

[ 0 0 0 1 ]

Видно, что если d = h = l = 0, то в результате применения всех операций получается то же самое, что и для матриц 3x3.

Матрица параллельного переноса теперь определяется как

[ 1 0 0 dx ]

[ 0 1 0 dy ]

[ 0 0 1 dz ]

[ 0 0 0 1 ]

Матрицу масштабирования можно определить и для матриц 3x3, и для матриц 4x4:

[ kx 0 0 ] [ kx 0 0 0 ]

[ 0 ky 0 ] или [ 0 ky 0 0 ]

[ 0 0 kz ] [ 0 0 kz 0 ]

[ 0 0 0 1 ]

где kx, ky, kz - коэффициенты масштабирования по соответствующим осям.

Таким образом, получаем следующее. Любое нужное нам преобразование пространства можно задать матрицей 4x4 определенной структуры, разной для разных преобразований. Результат последовательного выполнений нескольких преобразований совпадает с результатом одного преобразования T, которое также задается матрицей 4x4, вычисляемой как произведение матриц всех этих преобразований. Важен порядок умножения, так как A*B B*A. Результат применения преобразования T к вектору [ x y z ] считается как результат умножения матрицы T на вектор [ x y z 1 ].

Докажем на примере, что A*B B*A. Пусть A - матрица переноса, B - поворота. Если сначала перенести объект, а потом повернем относительно центра координат (это будет B*A), то результат не будет соответствовать результату, при котором сначала объект поворачивают, а затем переносят (A*B).

5.2 Создание одноцветного треугольника

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

Нужно отсортировать вершины так, чтобы вершина A была верхней, C - нижней, тогда min_y = A.y, max_y = C.y, и надо обойти все линии от min_y до max_y. Рассмотрим какую-то линию sy, A.y <= sy <= C.y. Если sy < B.y, то она пересекает стороны AB и AC; если sy >= B.y - то стороны BC и AC. Известны координаты всех вершин, поэтому можно написать уравнения сторон и найти пересечение нужной стороны с прямой y = sy. Получим два конца отрезка. Так как не известно, какой из них левый, а какой правый, нужно сравним их координаты по x и обменяем значения, если нужно. Рисуя этот отрезок, повторяя процедуру для каждой строки - получаем треугольник.

Рассматривая более подробно пересечения прямой

y = sy (текущей строки) и стороны треугольника, например AB, Получим уравнение прямой AB в форме x = k*y+b:

x = A.x+(y-A.y)*(B.x-A.x)/(B.y-A.y)

Теперь надо подставить известное для текущей прямой значение y = sy:

x = A.x+(sy-A.y)*(B.x-A.x)/(B.y-A.y)

Для других сторон пересечение ищется совершенно точно так же. Например:

// ...

// здесь сортируем вершины (A,B,C)

// ...

for sy = A.y to C.y begin

x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y);

if (sy < B.y)Then

x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y);

else

x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y);

if (x1 > x2) Then

begin

tmp = x1; x1 = x2; x2 = tmp;

end;

drawHorizontalLine(sy, x1, x2);

end;

Необходимо защититься от случая, когда B.y = C.y - в этом (и только этом, потому как если C.y = A.y, то треугольник пустой и рисовать его не нужно, или можно рисовать горизонтальную линию; а если B.y = A.y, то sy >= A.y и до деления на B.y - A.y не дойдет) случае произойдет попытка деления на ноль.

// ...

// здесь сортируем вершины (A,B,C)

// ...

for sy = A.y to C.y begin

x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y);

if (sy < B.y)

x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y);

else begin

if (C.y == B.y)

x2 = B.x;

else

x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y);

end;

if (x1 > x2)Then

begin

tmp = x1; x1 = x2; x2 = tmp;

drawHorizontalLine(sy, x1, x2);

end;

// ...

Здесь drawHorizontalLine(sy, x1, x2) - горизонтальная линия. Её создание не представляет сложности и код будетвыглядеть так.

//...

For i:=x1 to x2 do

PutPixel(i,sy,Color);

//...

6. Программа

unit graph3;

interface

uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

DXClass, DXDraws, StdCtrls,graph, Menus,graph3D,figures, Buttons;

const Mode:Word=0;

type TLab = class(TForm)

Vid: TDXDraw;

Timer: TDXTimer;

Enter: TButton;

Menu: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

N7: TMenuItem;

N8: TMenuItem;

N9: TMenuItem;

OpenDialog: TOpenDialog;

SaveDialog: TSaveDialog;

N10: TMenuItem;

Space: TButton;

Box1: TComboBox;

Label1: TLabel;

OK: TButton;

Cancel: TButton;

Label6: TLabel;

BCube: TBitBtn;

BSide: TBitBtn;

Box6: TComboBox;

Label7: TLabel;

procedure FormCreate(Sender: TObject);

procedure TimerTimer(Sender: TObject; LagCount: Integer);

procedure VidMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure EnterClick(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure N4Click(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure N9Click(Sender: TObject);

procedure N10Click(Sender: TObject);

procedure SpaceClick(Sender: TObject);

procedure FormKeyDown(Sender: TObject; var Key: Word;

Shift: TShiftState);

procedure FormKeyUp(Sender: TObject; var Key: Word;

Shift: TShiftState);

procedure CancelClick(Sender: TObject);

procedure OKClick(Sender: TObject);

procedure N8Click(Sender: TObject);

procedure BCubeClick(Sender: TObject);

pr ocedure BSideClick(Sender: TObject);

procedure N6Click(Sender: TObject);

private

public

end;

var Lab: TLab;

implementation

{$R *.DFM}

const ScreenX:Word=640;

ScreenY:Word=480;

x1:integer=0;

y1:integer=0;

White=$FFFFFF;

View:Boolean=False;

Figure:Word=1;

Accept:Boolean=True;

sv:Word=0;

var c:char;S,SS,TMP:PPl;t:PTexture;

CS,CO,CC,CSc,CL:Word;Rot:TRot;

x0,y0,x2,y2:integer;r:Single;

Blue,Red,Yelow,M,N,SC:Word;

Keys:array[1..255]of Boolean;

Input:array[1..12]of procedure (x,y:integer;var E:Boolean);

Bol:Boolean;Option:array[1..5] of String;

o:array[1..MaxSide]of TPoint;

w:array[1..2]of TPoint;tmp_o:TPoint;

cx,cy:Word;oc:TPoint;ClicCub:array[0..MaxSide]of Boolean;

procedure LoadObject(Name:String;var Obj:PObj);

var f1:file of TPoint; a:TSides;

f2:file of Word;

S,Tmp:TPoint;i,j:word;Name2:String;

B:Boolean;

begin

For i:=1 to Length (Name)-4 do begin

Name2:=Name2+Name[i];

end;

Name:=Name2;

Assign(f2,Name+.res);

Reset(f2);

Read(f2,Obj^.Count);

close(f2);

Assign(f1,Name+.dat);

Reset(f1);

Read(f1,Obj^.o);

For i:=1 to Obj^.Count do

New(Obj^.Side[i],Create(Obj^.o.x,Obj^.o.y,Obj^.o.z,0,0,0,a));

For i:=1 to Obj^.Count do begin

inc(CS);

if(i mod 2<>0)Then

T:=ColorText(RGB(100+Random(155),100+Random(155),100+Random(155)),GMT)

else T:=T;

Obj^.Side[i]^.Texture:=T;

Obj^.Side[i]^.Mode:=Mode;

Obj^.Side[i]^.Alpha:=0;

Read(f1,S);

For j:=1 to 3 do

begin

Read(f1,S);

Obj^.Side[i]^.S[j]:=S;

SS^[i,j]:=S;

end;

close(f1);

end;

procedure SaveObject(Name:String;var Obj:PObj);

var f1:file of TPoint;

f2:file of Word;B:Boolean;

S:TPoint;i,j:word;Name2:String;

begin

B:=False;

For i:=1 to Length(Name) do

if(Name[i]=.)Then B:=True;

if(B=True)Then begin

For i:=1 to Length(Name)-4 do begin

Name2:=Name2+Name[i];

end;

Name:=Name2;

end;

Assign(f2,Name+.res);

Rewrite(f2);

Reset(f2);

Write(f2,Obj^.Count);

close(f2);

Assign(f1,Name+.dat);

Rewrite(f1);

Reset(f1);

Write(f1,Obj^.o);

For i:=1 to Obj^.Count do begin

Obj^.Side[i]^.o:=tmp_o;

S:=Obj^.Side[i]^.o;

Write(f1,S);

For j:=1 to 3 do

begin

S:=Obj^.Side[i]^.S[j];

Write(f1,S);

end;

close(f1);

end;

procedure CreateTMP(var Obj:PObj);

var i,j,k:Word;

begin

Obj^.o.x:=0;Obj^.o.y:=0;Obj^.o.z:=100;

For i:=1 to Obj^.Count do

begin

tmp_o:=Obj^.Side[i]^.o;

Obj^.Side[i]^.o:=o[i];

For j:=1 to 3 do

Obj^.Side[i]^.S[j]:=S^[i,j];

end;

procedure ShowSide;

var i,j,k,cx,cy:Word;tmp:TPoint;

begin

Lab.Vid.Surface.Fill(0);

myForm(GetMaxX,GetMaxY);

For i:=1 to CS do begin

Line(Trunc(SS^[i,1].x),Trunc(SS^[i,1].y),Trunc(SS^[i,2].x),Trunc(SS^[i,2].y),White);

Line(Trunc(SS^[i,2].x),Trunc(SS^[i,2].y),Trunc(SS^[i,3].x),Trunc(SS^[i,3].y),White);

Line(Trunc(SS^[i,3].x),Trunc(SS^[i,3].y),Trunc(SS^[i,1].x),Trunc(SS^[i,1].y),White);

Line(Trunc(SS^[i,1].x),Trunc(SS^[i,1].z),Trunc(SS^[i,2].x),Trunc(SS^[i,2].z),White);

Line(Trunc(SS^[i,2].x),Trunc(SS^[i,2].z),Trunc(SS^[i,3].x),Trunc(SS^[i,3].z),White);

Line(Trunc(SS^[i,3].x),Trunc(SS^[i,3].z),Trunc(SS^[i,1].x),Trunc(SS^[i,1].z),White);

Line(Trunc(SS^[i,1].z*r),Trunc(SS^[i,1].y),Trunc(SS^[i,2].z*r),Trunc(SS^[i,2].y),White);

Line(Trunc(SS^[i,2].z*r),Trunc(SS^[i,2].y),Trunc(SS^[i,3].z*r),Trunc(SS^[i,3].y),White);

Line(Trunc(SS^[i,3].z*r),Trunc(SS^[i,3].y),Trunc(SS^[i,1].z*r),Trunc(SS^[i,1].y),White);

if(ClicCub[i]=True)Then begin

Line(Trunc(SS^[i,1].z),Trunc(SS^[i,1].y),Trunc(SS^[i,2].z),Trunc(SS^[i,1].y),White);

Line(Trunc(SS^[i,2].z),Trunc(SS^[i,1].y),Trunc(SS^[i,1].z),Trunc(SS^[i,3].y),White);

end;

S[CS]:=SS[CS];

cx:=GMX div 2;

cy:=GMY div 2+1;

For i:=1 to 3 do

begin

S^[CS,i].x:=S^[CS,i].x-cx+dF;

S^[CS,i].y:=cy-S^[CS,i].y-dF;

S^[CS,i].z:=S^[CS,i].z-cx-dF;

end;

procedure CreateSide(var Obj:PObj);

var cx,cy,i,j,k:Word;

begin

r:=1;

For i:=1 to Obj^.Count do

S[i]:=Obj^.Side[i]^.S;

TMP:=S;

Lab.Vid.Surface.Fill(0);

myForm(GetMaxX,GetMaxY);

cx:=GMX div 2;

cy:=GMY div 2+1;

For j:=1 to CS do

For i:=1 to 3 do

begin

TMP^[j,i].x:=TMP^[j,i].x-cx+dF;

TMP^[j,i].y:=cy-TMP^[j,i].y-dF;

TMP^[j,i].z:=TMP^[j,i].z-cx-dF;

end;

For i:=1 to CS do begin

Line(Trunc(TMP^[i,1].x),Trunc(TMP^[i,1].y),Trunc(TMP^[i,2].x),Trunc(TMP^[i,2].y),White);

Line(Trunc(TMP^[i,2].x),Trunc(TMP^[i,2].y),Trunc(TMP^[i,3].x),Trunc(TMP^[i,3].y),White);

Line(Trunc(TMP^[i,3].x),Trunc(TMP^[i,3].y),Trunc(TMP^[i,1].x),Trunc(TMP^[i,1].y),White);

Line(Trunc(TMP^[i,1].x),Trunc(TMP^[i,1].z),Trunc(TMP^[i,2].x),Trunc(TMP^[i,2].z),White);

Line(Trunc(TMP^[i,2].x),Trunc(TMP^[i,2].z),Trunc(TMP^[i,3].x),Trunc(TMP^[i,3].z),White);

Line(Trunc(TMP^[i,3].x),Trunc(TMP^[i,3].z),Trunc(TMP^[i,1].x),Trunc(TMP^[i,1].z),White);

Line(Trunc(TMP^[i,1].z*r),Trunc(TMP^[i,1].y),Trunc(TMP^[i,2].z*r),Trunc(TMP^[i,2].y),White);

Line(Trunc(TMP^[i,2].z*r),Trunc(TMP^[i,2].y),Trunc(TMP^[i,3].z*r),Trunc(TMP^[i,3].y),White);

Line(Trunc(TMP^[i,3].z*r),Trunc(TMP^[i,3].y),Trunc(TMP^[i,1].z*r),Trunc(TMP^[i,1].y),White);

end;

Flip(Lab.Vid);

end;

procedure LoadSide(var Obj:PObj);

var i,j,k:Word;TMP:PPL;

begin

r:=1;

For i:=1 to Obj^.Count do

S[i]:=Obj^.Side[i]^.S;

SS^:=S^;

Lab.Vid.Surface.Fill(0);

myForm(GetMaxX,GetMaxY);

For j:=1 to CS do

For i:=1 to 3 do

begin

SS^[j,i].x:=SS^[j,i].x+cx-dF;

SS^[j,i].y:=cy-SS^[j,i].y-dF;

SS^[j,i].z:=SS^[j,i].z+cx+dF;