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

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

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

В западной литературе, полученной большей частью из интернета, я нашел описания двух самых популярных методов по проецированию трехмерных сцен. Это BSP-Tree и Portal Clipping методы. Каждый из них имеет ряд преимуществ перед другим. И, так как мне больше понравился метод Portal Clipping, который имел большое сходство с уже разработанным лично мною методом построения, то я выбрал именно его.

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

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

Ну и популярные трехмерные компьютерные игры, наводнившие рынок...

PORTAL CLIPPING, ТРЕХМЕРНАЯ ГРАФИКА, ТЕКСТУРИРОВАНИЕ, INTEL 80x86, PASCAL 7.0

(1) Объект исследования – технология построения трехмерных изображений.
(2) Метод исследования – вычислительный эксперимент.
(3) Цель работы – реализация практического алгоритма, основанного на технологии Portal Clipping.
(4) В результате была написана программа, представляющая собой работающую модель трехмерного двигателя.
(5) Программа может быть использована в качестве основы для других программ, работающих с трехмерной графикой.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ
1.ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДА PORTAL CLIPPING
1.1.ВОЗНИКНОВЕНИЕ МЕТОДА PORTAL CLIPPING
1.2.ОСНОВЫ ТРЕХМЕРНОЙ ГРАФИКИ В МЕТОДЕ PORTAL CLIPPING
1.3.ПРЕИМУЩЕСТВА И ОТЛИЧИТЕЛЬНЫЕ ЧЕРТЫ МЕТОДА
1.4.НЕДОСТАТКИ МЕТОДА И БОРЬБА С НИМИ
2.РЕАЛИЗАЦИЯ МЕТОДА
2.1.ЭТАПЫ АЛГОРИТМА
2.2.ОПРЕДЕЛЕНИЕ СТОЛКНОВЕНИЙ СО СТЕНКАМИ СЕКТОРА.
2.3.ПРОХОЖДЕНИЕ СКВОЗЬ ПОРТАЛЫ.
2.4.ГРАФИЧЕСКОЕ ОТОБРАЖЕНИЕ ВИРТУАЛЬНОГО МИРА НА ЭКРАН.
2.5.ТЕКСТУРИРОВАНИЕ
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ 1. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ.
ПРИЛОЖЕНИЕ 2. РУКОВОДСТВО ПРОГРАММИСТА.
ПРИЛОЖЕНИЕ 3. РИСУНКИ.

ВВЕДЕНИЕ
Трехмерная компьютерная графика и моделирование занимают в наше время одну из развивающихся сфер науки. С появлением графических средств стало возможным моделировать различного рода научно-технические явления, такие как физические процессы, проводить сложные математические расчеты, и, наконец, создавать трехмерные изображения объектов.
В настоящее время существует множество прикладных программ, предназначенных для работы с компьютерной графикой. Все они ориентированы на серьезную деятельность программиста, дают возможность выполнять проектно-расчетные работы, затрагивающие определенное направление в разработках, такие как архитектуростроение, геоинформационные системы и многое другое. Их предназначение состоит в представлении наглядности визуально-отображаемой информации перед разработчиком, чтобы в последствии иметь как можно более полную картину о том, что должно получиться на финальном этапе реально разрабатываемого проекта.
Так, допустим, архитектор может не строя здания смоделировать его модель на компьютере и проанализировать характеристики результата. Физик имеет возможность задать в соответствующем программном пакете параметры для некоторой физической системы и получить ответ на интересующие его вопросы, без проведения экспериментов в реальном мире.
Опустившись на более детальный уровень реализации прикладных программных пакетов, можно обнаружить разнообразные подходы к развитию и построению трехмерной компьютерной графики. В их основе лежат специально придуманные алгоритмы, достигающие необходимой производительности и качества моделирования. В конечном итоге, все они направлены на следующие аспекты: быстрота геометрических и графических расчетов, удобный пользовательский интерфейс и возможность конструирования любых объектов виртуального компьютерного мира.
В последнее время, в западной литературе наиболее распространены несколько подходов к компьютерному моделированию. Эти алгоритмы были специальным образом придуманы, описаны и реализованы в виде программных продуктов. Можно отметить некоторые из них, получившие общее признание. Это BSP-Tree метод, Portal Clipping.
Цель, для которой написана эта работа, объяснить и показать один из возможных путей создания пользователем собственных виртуальных миров, причем концепция, описанная здесь, в первую очередь направлена на обеспечение высокой скорости произведения трехмерных расчетов, без ощутимых потерь качества моделируемых данных. В качестве финального результата работы будет предоставлена программа, написанная на языке программирования Pascal 7.0 под DOS [1], позволяющая пользователю совершать трехмерные прогулки по виртуальным мирам.

1.Теоретические основы метода Portal Clipping
1.1.Возникновение метода Portal Clipping
Самый простой метод компьютерного графического моделирования состоит в полном переборе всех имеющихся на виртуальной сцене графических примитивов, сортировки их по удаленности от камеры наблюдения и уже после этого прорисовку на экран компьютера. Метод чрезмерно прост, но не экономичен. На один и тот же кусочек экранного пространства приходится рисовать по несколько примитивов или их частей. Это ведет к увеличению компьютерного времени, снижая производительность.
Чтобы уменьшить количество производимых расчетных операций, разумно будет изначально отсортировать все стационарные объекты виртуального мира, отбирая их по какому-то критерию.
Абстрактно можно размышлять так. Представим себе здание с множеством комнат и дверей, разделяющих их. Когда наблюдатель находится в одной из них, то очевидно он не может видеть целиком все здание, а только все стены той комнаты, где он стоит и стены в соседних комнатах за дверными проемами. Поэтому, проецируя здание на экран компьютера, у нас отпадает необходимость вести трехмерные расчеты для всех стенок. Будут браться только те из них, которые окажутся видимыми для наблюдателя.
Это и есть идея метода построения трехмерных виртуальных миров, называемого Portal Clipping.

1.2.Основы трехмерной графики в методе Portal Clipping
Для начала введем несколько правил построения виртуального трехмерного мира.
1. Примитивом или простейшей частью, так называемым кирпичиком виртуального трехмерного мира, будем считать выпуклый многоугольник с произвольным количеством вершин. Назовем его условно полигоном.
2. Множество полигонов составляют сектор, соприкасаясь друг с другом сторонами. Сектор также должен быть трехмерно выпуклым.
3. Отдельные полигоны сектора обозначим «порталами». Многоугольники этого типа будут служить в качестве перехода из одного сектора в другой. (В тот момент, когда камера наблюдателя перемещается сквозь них).
Таким образом, всю карту при построении можно разбить на сектора – те же самые комнаты - соединенные между собой портальными переходами. Для камеры наблюдателя необходимо будет приписываться тот номер сектора, которому она принадлежит в данный момент. При пересечении камерой какого-либо портала, номер сектора будет меняться на тот, в который данный портал ведет.
При таких условиях отпадает необходимость каждый раз, создавая очередной кадр на экране компьютера, рисовать абсолютно все полигоны карты. Достаточно будет начать вырисовывание с того сектора, где в данный момент находится камера наблюдателя и закончить процесс, если не найдется больше ни одного сектора, который был бы виден на экране сквозь портальные переходы уже нарисованных секторов. Очевидно, что в некоторых случаях (например, когда виртуальный мир очень велик) алгоритму не требуется каждый раз отображать на экран все сектора. Заранее будут отсекаться те из них, которые являются невидимыми для наблюдателя, соответственно уменьшая число производимых вычислений.

1.3.Преимущества и отличительные черты метода
Сейчас, когда были изложены основы построения трехмерной графики на экран компьютера, можно поговорить о преимуществах метода.
Во-первых, какова бы не была трехмерная сцена, в любом случае трудоемкость построения ее на экран не будет превышать количества пикселей экрана. Ведь по существу, каждый последующий сектор в глубину трехмерной сцены будет рисоваться только в пределах портала, вернее сказать имиджа полигона-портала, который в этот сектор ведет. Экран разбивается на кусочки, каждый из которых не налагается на другие, отсюда и заключаем гарантированную трудоемкость.
Во-вторых, помимо простоты и быстроты, метод обладает рядом специальных свойств, не присущие другим методам. Так, например, возможна реализация различных спецэффектов. Перечислим их и дадим краткое описание:
1.Создание зеркальных стен.
В данном типе стен будут отражаться окружающие ее стены и предметы трехмерного мира. Достигается это следующим образом: зеркальная стена является обычным порталом, ведущим в тот же самый сектор, которому он принадлежит. Останется только реализовать зеркальное отображение координат камеры. Отметим, что данным свойствам обладает только метод Portal Clipping.
2.Создание телепортаторов.
Телепортатор – это место на карте, попадая в которое камера переносится в другое место карты. В методе Portal Clipping простейшим телепортатором служит все тот же портал, пересекая который будет необходимо только присвоить положению камеры новые координаты.
3. Создание абстрактных пространств в виртуальном мире.
Приведем простой пример: пересекая портал, камера переходит в следующий сектор. Однако портал нового сектора, который соответствует возвращению камеры в исходный сектор, вовсе не обязательно должен туда вести. Попятясь камерой назад, мы можем уже не попасть в предыдущий сектор, а в любое другое место карты, связанное с пересечением обратного портала. Таким образом можно как угодно комбинировать переходы между секторами, нарушая традиционные представления о реальном мире.
В-третьих, метод не нуждается в выделении памяти под «Z-buffer», как это требуется в некоторых других методах (BSP-Tree) [2]. Это снижает число производимых вычислений и дает выигрыш в трудоемкости по памяти.

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

2.Реализация метода
2.1.Этапы алгоритма
Предположим, что был создан некоторый виртуальный мир, удовлетворяющий всем условиям технологии Portal Clipping. Опишем алгоритм по которому будут выполняться расчеты проецирования на экран компьютера и осуществляться перемещения камеры наблюдателя. Алгоритм представляет собой несколько этапов :
1.Управление камерой: повороты, движения (Рисунок 1).
2.Детектирование столкновений камеры (другое название коллизий) со стенками сектора при перемещениях в пределах данного (Рисунок 2).
3.Детектирование пересечений с порталами данного сектора, с последующим изменением номера принадлежности камеры сектору, в который камера может перейти.
4.Графическое проецирование видимых частей трехмерного виртуального мира на экран.
Рассмотрим этапы алгоритма на более детальном уровне.
Операции над камерой наблюдателя.
Пусть векторная система положения камеры в трехмерном пространстве задается в виде матрицы:

Матрица М задается углами U1, U2, U3 и имеет вид:

Тогда повороты будут осуществляться путем умножения матрицы поворота M на матрицу V:

Где

причем, положение U1=U2=U3=90 соответствует нейтральной операции (т.е. поворота не будет вообще).
Перемещение камеры в пространстве выражается по формулам:

Где (Xc,Yc,Zc) - координаты камеры, а CameraStep – величина перемещения. (v1,v2,v3) – нормализованный вектор, называемый вектором направления. Чтобы сделать шаг вперед, нужно принять вектор (v1,v2,v3) равный вектору из матрицы системы положения камеры (v21,v22,v23).
2.2.Определение столкновений со стенками сектора.
Расчеты данного типа производятся с целью избежать возможности выхода камеры наблюдения за пределы ограниченного стенами пространства – исключить эффект прохождения сквозь стены.
Так как у нас имеется номер конкретного сектора, в котором в данный момент находится наблюдатель, то нет смысла определять возможные столкновения камеры со стенками всей карты целиком. Достаточно проверить коллизии со стенками этого одного сектора. Пользуясь тем, что любой сектор представлен выпуклым пространственным многоугольником, можно существенно облегчить процесс детектирования коллизий. Это достигается перебором всех стен сектора и определения расстояний до них по вектору направления движения камеры. Любой полигон задается на карте начальной точкой его отсчета (X0,Y0,Z0) и системой из трех векторов: два направляющих вектора плоскости (a1,b1,g1), (a2,b2,g2) и вектором нормали к ней (a3,b3,g3). Определенные ранее переменные (Xc,Yc,Zc), вектор (v1,v2,v3) тоже понадобиться использовать в расчетах коллизий.
Итак, расстояние до плоскости стены-многоугольника высчитывается следующим способом:

L - это и есть искомое расстояние до стены (Рисунок 2). Если знаменатель последней дроби обращается в ноль, то это означает, что вектор направления движения камеры параллелен плоскости стены. Естественно, что в этом случае никакой коллизии быть не может. А величина L также еще должна быть положительно определенной.
Рассчитывая L для каждой стенки сектора, в итоге следует взять самое минимальное из них. Поэтому в качестве переменной перемещения камеры CameraStep необходимо взять ее равной минимальному L, чтобы таким образом избежать выхода камеры за стенки сектора.

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

2.4.Графическое отображение виртуального мира на экран.
Пожалуй, данный раздел является самым основным аспектом, для которого и был придуман метод Portal Clipping. Анализируя принципиальные отличия от других методов, данный метод не требует выделения памяти компьютера под Z-buffer. Все полигоны рисуются не поверх друг друга, как при использовании Z-buffer, а каждый на специально отведенном для него на экране участке – имидже полигона. Имидж полигона – есть проекция трехмерного многоугольника на двухмерный экран компьютера. При проецировании возможны случаи, когда имидж полигона-стены может отсекаться имиджем полигона-портала, что позволяет не тратить времени на рисование скрытой за портальным переходом части стены. Таким образом общая трудоемкость вывода графики стремится к величине, зависящей только от количества точек на экране.
Перейдем теперь к рассмотрению вопроса о проецировании имиджей полигонов на экран. Обыкновенная точка , заданная координатами (X,Y,Z), будет проецироваться на визуальную плоскость камеры наблюдения по формулам:

где V, как уже было отмечено, матрица-система положения камеры, (a,b,c) и (dx,dy,dz) – представляют собой вектора (причем в выражении они транспонированы), (X0,Y0) – середина экрана (для режима VGA 320x200x256 это будет (160,100) ), а (K1,K2) – полученные двумерные координаты точки на экране. Именно таким образом осуществляется перспективное проецирование трехмерного пространства на двухмерную плоскость экрана камеры.
Следует также заметить, что переменная b, участвующая в расчете, по сути своей представляет расстояние по перпендикуляру от данной точки в трехмерном пространстве до визуальной плоскости камеры. Расстояние может быть и отрицательным, в этом случае точка будет являться невидимой, то есть расположенной за камерой наблюдения.
Полигон – это множество точек в трехмерном пространстве, лежащих в одной плоскости. Проецируя поочередно каждую из них и соединяя линиями, получаем на экране имидж полигона. Необходимо также заметить одну серьезную деталь: если несколько точек проецируемого полигона лежат за визуальной плоскостью камеры, то их необходимо отсекать. Вместо них вычисляются точки пересечения полигона с визуальной плоскостью камеры и соединяются линией. Это называется отсечением полигонов или «Poligon clipping».
Важен еще один момент. При проецировании имиджей полигонов на экран возможны ситуации, когда сам имидж будет лежать полностью или частично за пределами экрана. Здесь необходимо обрезать выходящие части.
Теперь, когда мы получили имидж полигона на экране, остается его затекстурировать, иначе говоря натянуть на него какую-нибудь картинку. Сейчас мы займемся рассмотрением подробного описания текстурирования.

2.5.Текстурирование
Текстура, как уже упоминалось, представляет собой какой-то рисунок, накладываемый на имидж полигона в соответствии с перспективной коррекцией. Каким же образом это достигается? Нам необходимо будет по заданной позиции на экране получить цвет из рисунка текстуры, соответствующий этой позиции.
Фактически, необходимо решить систему из трех уравнений и трех неизвестных, где левая часть уравнения описывает трассировку лучей исходящих из камеры, а правая часть задает уравнение плоскости, которой принадлежит полигон. На вход системе будет задаваться позиция на экране (двухмерные координаты к1 и к2) а решение системы - переменные (t1,t2) – будут являться позицией на текстуре, в которой записан цвет. Итак, уравнение имеет вид:

Здесь (Xc,Yc,Zc) – точка положение камеры в пространстве, (Xo,Yo,Zo) – точка начала отсчета полигона в трехмерном пространстве, (a1,b1,g1) и (a2,b2,g2) – задающие плоскость полигона вектора. Переменные М1,М2.М3 – представляют собой «управляемый» с помощью изменяющихся величин к1 и к2 вектор направления расхождения лучей (трассировки лучей) из камеры:

где Vij – элементы матрицы V - системы положения камеры в пространстве, R – коэффициент перспективной коррекции (для режима VGA 320x200x256 рекомендуется брать равным 200), (k1,k2) – координаты позиции текстурируемого пиксела на экране (для режима VGA 320x200x256, к1[-159;159], к2[-99;99]).
Таким образом, задавая координаты пикселей (к1,к2) на экране, меняющиеся в заданных пределах, мы будем получать соответствующие им координаты пикселя на текстуре (t1,t2). Иначе говоря, в позицию на экране по координатам (к1,к2) будем ставить пиксель цвета, расположенный в текстуре по координатам (t1,t2).
Перейдем к вопросу о решении заданной системы уравнений. При заданных координатах к1 и к2 нам нужно с минимальной по времени затратой получить величины t1 и t2, чтобы потом по этим координатам взять номер цвета из текстуры и поставить его в позицию на экране.
Решив уравнения, можно получить следующие формулы для нахождения величин t1 и t2. Причем здесь решение разбивается на три различных случая:

Случай 1. w1 <> 0

Случай 2. w2 <> 0

Случай 3. w3 <> 0

Как видно, формулы получились громоздкими. Вычисление каждого из случаев требует больших временных затрат, поэтому оперировать ими в таком виде нельзя, иначе для получения хотя бы одного экранного кадра будет требоваться более секунды, что само по себе является недопустимым для нормальной работы. (Если конечно вы не используете машину типа «Cray» ).
Заметим, что для изменяющимися величинами в формулах являются только две переменные к1 и к2, которые содержаться как в числителе, так и в знаменателе дробей. К2 – это номер строки на экране, а к1 – номер столбца.
Поэтому поступим так: организуем перебор всех строк, то есть переменной к2 и будем вести текстурирование вдоль зафиксированной строки экрана с номером к2 по позициям столбцов к1, от –159 до +159. Отдельно в начале цикла по переменной к2 вычислим числители L1, L2 и знаменатель L3 (общий для всех дробей конкретного случая) каждой из дробей, считая к1=-159. Далее вычислим приращения числителей и знаменателя дробей при увеличении переменной к1 на единицу. Обозначим их I1, I2, I3. Тогда нужные t1 и t2 найдутся в виде (Рассматривается 1 случай):

For к1=-99 to 99 do
{
M1:=v11*(-159)-v21*R+v31*k2;
M2:=v12*(-159)-v22*R+v32*k2;
M3:=v13*(-159)-v23*R+v33*k2;

L1 = (dx*b2-dy*a2) / w1 + (M1*b2-M2*a2)*t / w1;
L2 = (dy*a1-dx*b1) / w1 + (M2*a1-M1*b1)*t / w1;
I1 = (dx*b2-dy*a2) / w1 + (v11*b2-v12*a2)*t / w1;
I2 = (dy*a1-dx*b1) / w1 + (v12*a1-v11*b1)*t / w1;
For к1=-159 to 159 do
{
t1 = L1 / L3;
t2 = L2 / L3;
Screen[k1,k2] = Texture[t1,t2];
L1 = L1 + I1;
L2 = L2 + I2;
L3 = L3 + I3;}

Это означает, что для текстурирования линии пикселей на экране нам уже не потребуется вычислять всю формулу для каждого, а обойтись двумя простыми делениями и тремя сложениями.
Рассмотренный алгоритм действует для текстурирования всего экрана. Однако совсем не обязательно, что конкретный имидж полигона будет занимать собой все экранное пространство, он может быть и значительно меньше. Тогда можно завести два массива Lbd[200] и Rbd[200], в которых будут хранится крайние левые и правые соответственно границы имиджа полигона для k2–го номера строки. Текстурирование будет вестись по к2 от самой верхней точки имиджа (или от -99, если она выходит за верхнюю границу экрана) до самой нижней (или до 99, если выходит за нижнюю границу экрана). Цикл по переменной к1 будет от Lbd[к2] до Rbd[к2]. Но этот процесс возможен только в том случае, если полигон представляет собой выпуклый многоугольник.

Заключение
В заключении хотелось бы отметить применение методики построения трехмерных виртуальных миров по технологии Portal Clipping. Сфера внедрения её разнообразна, начинается от компьютерных игр и простирается до разработки архитектурных сооружений. Возможный аспект – планирование строительства домов. При помощи этой технологии можно будет проводить исследования по архитектурным особенностям сооружений жилых домов и перспектив их строительства.
Также данную технологию можно применять в дизайнерских целях. Пользователь способен будет моделировать обстановку комнат, подбирая оптимальные и изящные комбинации из набора виртуальной мебели. То есть, на экране компьютера можно будет заранее посмотреть и проанализировать расположение фурнитуры, для последующего ее установления уже непосредственно в доме клиента.
К сожалению приложенный к работе пакет программ не свидетельствует в явном виде о полных возможностях описываемой технологии, что связанно, прежде всего с нехваткой компьютерного времени, отведенного под работу и трудностями реализационного типа.
Дополнительной информацию по изложенному материалу можно найти в [3]
Список использованных источников
1. Прайс Д. Программирование на языке Паскаль: Практическое руководство. Пер. с англ. – М.:Мир, 1987. – 232 с., ил.
2. BSP Trees. http://symbolcraft.com/pjl/graphics/bsp/
3. Cells and Portals. http://www.netmagic.net/~achalfin/Graphics/portal.htm
Приложение 1. Руководство пользователя.
Состав пакета программы.
3dca.exe – программа, реализующая перемещения камеры по трехмерному виртуальному миру по технологии Portal Clipping.
Map.3dm – файл ресурсов для трехмерного двигателя. Содержит текстуры и трехмерную карту.
Запуск производится из командной строки путем набора следующей строки: 3dca.exe map map.3dm
Управление.
W – двигаться вперед, S - двигаться назад, A и D – сделать шаг влево или вправо, Q и E – поднять/опустить голову, «стрелка влево» и «стрелка вправо» -повернуться налево или направо, 7 и 9 (на дополнительной клавиатуре) – наклонить голову в бок налево или направо, - и + (на дополнительной клавиатуре) двигаться вверх или вниз соответственно.
Недокументированные возможности.
L – включить освещение, T – включить/выключить информацию о количестве кадров в секунду, I – текстурирование с использованием интерполяции, - и + - поменять размер окна экрана, O/P – просветить/затемнить световую гамму экрана, Y и U – увеличить/уменьшить коэффициент перспективы, R – включение спецэффекта.

Приложение 2. Руководство программиста.
Написана на языке программирования Pascal 7.0 под DOS.
Все измерение проводились на компьютере Intel Pentium 100Mhz, 32Mb.
Графический режим – 320х200х256,
Число кадров в секунду – 20 и более,
Интерполяционное текстурирование (группами по 16 пикселов),
Список файлов:
3dca.pas – исходный текст программы на языке Паскаль.
map.3dm – файл ресурсов, содержащий необходимую информацию и подаваемый на вход откомпилированному файлу 3dca.pas

Приложение 3. Рисунки.

Рисунок 1. Положение камеры наблюдения в трехмерном пространстве.

Рисунок 2. Нахождение расстояния от камеры наблюдения до плоскости полигона (многоугольника).