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

Вид материалаДокументы

Содержание


Механизмы двухмерной графики
Подобный материал:
1   2   3   4   5   6   7   8   9   ...   37
^ МЕХАНИЗМЫ ДВУХМЕРНОЙ ГРАФИКИ

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

В данной главе мы познакомимся с тем, что называется двухмерная проекция и изучим следующие темы:
  • Картезианская, или двухмерная проекция;
  • Точки, линии и области;
  • Трансляция;
  • Масштабирование;
  • Повороты;
  • Разрезание;

Использование матриц. Двухмерная проекция

Двухмерную проекцию (2-D), иначе называемую картезианской, можно сравнить с листом бумаги в клеточку.

Каждая точка в двухмерной проекции однозначно описывается двумя координатами. Обычно эти координаты обозначаются буквами х и у, где х определяет точку на горизонтальной оси X, а у задает точку на вертикальной оси Y. Например, если нам захочется нарисовать точки (1,1) и (-3,4), то мы сделаем так, как это показано на рисунке 4.1.

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


Точки, линии и области

Все мы видели игры типа Asteroids, Spectre и Major Havoc. Многие из них имеют общие черты первых видеоигр — все они выполнены линиями и все они, как правило, плоские. Кстати, в предыдущих главах мы еще ничего не делали для рисования проекции кроме отображения точки.

Точки

Мы уже дали определение точке. Она представляет собой позицию на плоскости, которую можно описать парой координат X и Y. Давайте напишем маленькую программу на Си, рисующую точки на экране. Листинг 4.1 показывает такую программу.

Листинг 4.1. Программа, рисующая точки (POINTY.C).

#include

#include

void main(void)

{

int х, у, index, color;

// перевести компьютер в графический режим

_setvideomode(_VRES16COLOR); // режим 640х480, 16 цветов

// нарисовать 10000 точек на экране, расположенных случайным образом

for(index = 0; index<10000; index++)

{

// получить случайные координаты и цвет

х = rand()%640;

у = rand()%480;

color = rand()%16;

_setcolor(color); // установить цвет для рисования точки

_setpixel(х,у); // нарисовать точку

} // конец цикла for

// ждать нажатия клавиши

while(!kbhit()){}

// восстановить текстовый режим

_setvideоmоde(_DEFAULTMODE) ;

} // конец функции main


Теперь разберемся, что делает эта программа:

Компьютер переводится в режим VGA с помощью вызова функции Си _setvideomode ( VRES16COLOR). Это функция из графической библиотеки Microsoft. После этого программа входит в главный цикл. В структуре

FOR каждый раз случайным образом генерируются три числа: одно для цвета и два других для координат (х,у) позиции точки, которую мы хотим нарисовать:
  • Затем мы используем библиотечную функцию _setpixel(х,у), чтобы нарисовать точку на экране. Программа делает это 10000 раз, а потом останавливается;
  • Затем программа ждет нажатия любой клавиши, после чего происходит выход в DOS.

Если вы запустите программу несколько раз, то сможете заметить, что точки все время оказываются в одних и тех же местах. Как это получается? Дело в том, что мы пользуемся функцией rand (), которая не является в полном смысле генератором случайных чисел. Она возвращает так называемые псевдослучай­ные числа. Чтобы избежать этого, вам надо всякий раз при запуске устанавли­вать генератор случайных чисел с разными начальными значениями. Вставьте в начало программы функцию srand(int) — и все будет в порядке,

Линии

Линия, как вы знаете, — это кратчайший отрезок между двумя точками. Например, между точками (1,1) и (5,5) на плоскости линия будет выглядеть так (рис. 4.2):

Давайте изменим программу из Листинга 4.1 так, чтобы она рисовала линии вместо точек. Чтобы сделать это, нужно кое-что изменить. Вместо двух случай­ных чисел х и у теперь их будет четыре: (х1,у1) и (х2,у2). Потом программа нарисует между ними линию, используя вызов библиотечной функции. Листинг будет выглядеть так:


Листинг 4.2. Программа, рисующая линии (LINER.С).

#include

#include

void main(void)

{

int xl,yl,x2,у2,color,index;

// перевести компьютер в графический режим

_setvideomode(_VRES16COLOR); // режим 640х480, 16 цветов

// нарисуем 1000 случайных линий на экране

for (index = 0; index<1000; index++)

{

// получим случайные координаты концов линий и цвет

x1 = rand()%640; // Х-координата начальной точки

y1 = rand()%480; // Y-координата начальной точки

х2 = rand()%640; // Х-координата конечной точки

у2 = rand()%480; // У-координата конечной точки

color = rand()%16;

_setcolor(color); // установить цвет

_moveto(х1,у1); // переместиться к началу линии

_lineto(х2,у2); // нарисовать линию

} // конец цикла for // ждать нажатия любой клавиши

while(!kbhit()){}

// перевести компьютер в текстовый режим

_setvideomode(_DEFAULTMODE);

} // конец функции main


Многоугольники

Линии весьма просты, и если вы приложите немного усилий, то сможете из программы 4.2 сделать простой Screen Saver. Но видеоигры кроме линий содержат еще множество интересных графических объектов, например, многоугольников.

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

Все многоугольники являются закрытыми геометрическими объектами. Многоугольники бывают двух типов. Оба типа представлены на рисунке 4.4.

Существует математический алгоритм, позволяющий определить, к какому типу относится данный многоугольник, но он довольно сложен и сейчас нам не нужен. Давайте лучше напишем программу, рисующую многоугольники (Листинг 4.3).





Листинг 4.3. Программа, рисующая многоугольники (POLYDRAW.C).

#include

#include

void main(void)

{

// перевести компьютер в графический режим

_setvideomode( VRES16COLOR); // режим 640х480, 16 цветов

// нарисовать простой многоугольник

_setcolor(1); // пусть он будет синего цвета

_moveto(100,100); // первая вершина

_lineto(120,120); // вторая вершина

_lineto(150,200); // третья вершина

_lineto(SO,190); // четвертая вершина

_lineto(90,60); // пятая вершина

_lineto (100,100); // назад для замыкания контура

// теперь отмечаем каждую вершину белым цветом

_setcolor(15); // белый цвет

_setpixel(100,100); // вершина 1

_setpixel(120,120); // еершина 2

_setpixel(150,200); // вершина 3

_setpixel(80,190); // вершина 4

_setpixel(80,60); // вершина 5

// ожидание нажатия любой клавиши

while(!kbhit()){}

// перевести компьютер в текстовый режим

_setvideomode(_DEFAULTMODE);

} // конец функции main

Объекты

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

Листинг 4.4. Структуры данных для задания вершин объектов.

typedef struct vertex_typ

{

float x,y;

} vertex, *vertex_ptr;

// структура объекта

typedef struct object_typ

{

int num_vertices; // количество вершин в объекте

int color; // цвет объекта

float хо,уо; // позиция объекта

float x_velocity; // используем позже для

float y_velocity; // перемещения объекта

float scale; // коэффициент масштабирования

float angle; // угол поворота

vertex vertices[16]; // массив для определения 16 вершин

} object, *object_ptr;

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

Позиционирование объекта

Теперь поговорим о строчке, которая определяет позицию объекта в структуре из Листинге 4.4. Координаты (хо,уо) описывают начальную позицию объекта на плоскости.

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

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




деле все оказывается несколько проще. Давайте договоримся, что у нас на компьютере мировые и экранные системы координат совпадают. Это значит, что:
  • Точка (0,0) находится в левом верхнем углу экрана;
  • При движении вправо увеличивается значение Х-координаты;
  • При перемещении вниз увеличивается Y-координата.

Благодаря этим допущениям мы получаем экранные координаты, похожие на координаты 1-го квадранта (положительные значения осей Х и Y), но при этом надо всегда помнить, что ось Y у нас перевернута относительно экрана.

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

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

Трансляция объектов

Трансляцией объекта будем называть его перемещение, при котором не меняется ни угол поворота, ни размер объекта. Давайте воспользуемся нашей структурой данных для определения конкретного объекта, с которым будем эксперименти­ровать и в дальнейшем. К примеру, пусть это будет астероид. На рисунке 4.7 показан его внешний вид. Листинг 4.5 содержит фрагмент, описывающий наш астероид.


Листинг 4.5. Описание астероида.

Object asteroid;

// определим поля

asteroid.num_vertices = 6; //шести вершин будет достаточно

asteroid.color = 1; //цвет астероида - синий

asteroid.х0 = 320; // поместить астероид в центр экрана

asteroid.у0 = 240;

//теперь задаем координаты вершин как смещения относительно точки х0, у0

asteroid.vertices[0].х = 4.0;

asteroid.vertices[0].у = 3.5;

asteroid.vertices[1].х = 8.5;

asteroid.vertices[1].у = -3.0;

asteroid.vertices[2].x = 6;

asteroid.vertices[2].у = -5;

asteroid.vertices[3],x = 2;

asteroid.vertices[3].у = -3;

asteroid.vertices[4].х = -4;

asteroid.vertices[4].у = -6;

asteroid.vertices[5].х = -3.5;

asteroid.vertices[5].у = 5.5;

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

Теперь давайте чуть-чуть подумаем. Мы можем нарисовать вершины объекта относительно его положения на экране, которое описывается как (хо,уо). Если же мы хотим передвинуть объект, то можно сделать так:


x0=x0+dx

y0=y0+dy


где dx и dy — это количество пикселей, на которое мы хотим переместить объект по оси Х или Y.

Это все, что можно сказать о трансляции объектов. Теперь поговорим о масштабировании.

Масштабирование объектов

Масштабирование означает изменение размера объекта. Посмотрим для примера на рисунок 4.8. Астероид на нем в два раза больше, чем на рисунке 4.7. Это во многом объясняет принципы масштабирования. Все, что нам надо сделать, это умножить координаты каждой из вершин объекта на коэффициент масштабирования. Фрагмент кода в Листинге 4.6 показывает, как это делается для структуры объекта, определенной нами ранее.


Листинг 4.6. Масштабирование астероида.

void Scale_Object(object_ptr object,float scale)

{

int index;

// для всех вершин масштабируем х- и у-компоненты

for (index = 0; indexnum vertices; index++)

{

object->vertices [index].х *= scale;

object->vertlces[index].y *= scale;

} // конец цикла for

} // конец функции


Функция из Листинга 4.6 работает путем масштабирования координат каждой из вершин объекта. Если нам придет в голову увеличить наш объект «астероид»- в два раза, то нам потребуется написать следующее:


Scale_Object((object_ptr)&asteroid,2, 0};


С этим, вроде, все. Теперь мы уже готовы приступить к вращению объекта.

Вращение объектов

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

Если экран — это плоскость X-Y, то ось Z — это перпендикуляр к осям Х и Y. Таким образом, если мы описываем наши объекты относительно двухмерного мира, то у нас появляется возможность вращать их относительно оси Z,

Следующие формулы позволяют вращать произвольную точку (X,Y) отно­сительно оси Z:


new_x = x*cos(angle) - y*sin(angle) new_у = y*cos(angle) + y*sin(angle)


где angle — это угол, на который вы хотите повернуть точку. Кроме этого вам стоит помнить еще пару вещей:
  • Положительные углы имеют эффект вращения по часовой стрелке;
  • Отрицательные углы имеют эффект вращения против часовой стрелки.


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

Deg_To_Rad(deg) {pi*deg/180;}

Rad_To_Deg(rad) {180*rad/pi;}

Другими словами, это значит, что в круге 360 градусов или 2хPi радиан. Теперь нам нужно написать функцию для вращения объекта. Давайте просто используем формулы, не задумываясь о том, как и почему они работают. Функция в Листинге 4.7 делает именно то, что мы хотим.

Листинг 4.7. Вращение объекта.

void Rotate_0bject(object__ptr object, float angle)

{

int index;

float x_new, y_new,cs, sn;

// сначала вычислим синус и косинус угла

сs = cos(angle) ;

sn = sin(angle);

// поворачиваем каждую вершину на угол angle

for (index=0; indexnum_vertices; index++)

{

x_new = object->vertices [index].x*cs-object->vertices[index].y*sn;

y_new = object->vertices [index].y*cs+object->vertices[index].x*sn;

// изменяем исходные координаты.на расчетные

object->vertices[index].x = x_new;

object->vertices[index].y = у_new;

} // конец цикла for

} // конец функции

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

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

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

Шаг 1. - Инициировать поле астероидов;

Шаг 2. - Стереть поле астероидов;

Шаг 3. - Трансформировать поле астероидов;

Шаг 4. - Нарисовать поле астероидов;

Шаг 5. - Перейти к Шагу 2, пока пользователь не нажмет на кнопку.

Чтобы сделать это проще, я добавил три новых поля к нашей структуре: одно для угла поворота и два - для скорости (целиком программа представлена в Листинге 4.8).

Листинг 4.8. Программа, которая рисует поле астероидов (FIELD.С).

// ВКЛЮЧАЕМЫЕ ФАЙЛЫ ////////////////////////////////////

#include

#include

#include

// ОПРЕДЕЛЕНИЯ /////////////////////////////////////////

#define NUM_ASTEROIDS 10

#define ERASE 0

#define draw 1

// СТРУКТУРЫ ДАННЫХ ////////////////////////////////////

//определяем структуру "вершина"

typedef struct vertex_typ

{

float x,y; // координаты точки на плоскости

} vertex, *vertex__ptr;

// структура объекта

typedef struct object_typ

{

int num_vertices; // количество вершин объекта

int color; // цвет объекта

float xo,yo; // позиция объекта

float x_velocity; // скорость перемещения по осям Х

float y_velocity; // и y

float scale; // коэффициент масштабирования

float angle; // угол поворота

vertex vertices[16]; // 16 вершин

}object, *object_ptr;

// Глобальные переменные //////////////////////////////

object asteroids[NUM_ASTEROIDS];

// Функции ////////////////////////////////////////////

void Delay(int t)

{

// функция формирует некоторую временную задержку

float x = 1;

while(t—>0)

x=cos(x);

} // конец функции /////////////////////////////////////

void Scale_Object(object_ptr object,float scale)

{

int index;

// для всех вершин масштабируем координаты х и у

for (index = 0; indexnum_vertices; index++)

{

object->vertices[index].x *= scale;

object->vertices[index].y *= scale;

}// end for index

// конец функции ///////////////////////////////////////////

void Rotate_Object(object_ptr object, float angle)

{

int index;

float x_new, y_new,cs,sn;

// заранее вычислить синус и косинус

cs = cos(angle);

sn = sin(angle);

// поворачиваем каждую вершину на угол angle

for (index=0; indexnum_vertices; index++)

{

x new = object->vertices[index].x * cs - object->vertices[index].y * sn;

у new = object->vertices[index].y * cs + object->vertices[index].x * sn;

object->vertices[index].x = x_new;

object->vertices[index].y = y_new;

} // конец цикла for

} // конец функции //////////////////////////////////////////////////

void Create_Field(void)

{

int index;

// формируем поле астероидов

for (index=0; index
{

// заполнить все поля

asteroids[index].num_vertices = 6;

asteroids[index].color = 1 + rand() % 14; // всегда видимый

asteroids[index].xo = 41 + rand() % 599;

asteroids[index].yo = 41 + rand() % 439;

asteroids[index].x_velocity = -10 + rand() % 20;

asteroids[index].y_velocity = -10 + randO % 20;

asteroids[index].scale = (float)(rand() % 30) / 10;

asteroids[index].angle = (float) (-50+(float)(rand()%100))/100;

asteroids[index].vertices [0].x =4.0;

asteroids[index].vertices[0].у = 3.5;

asteroids[index].vertices[l].x=8.5;

asteroids[index].vertices[1].y = -3.0;

asteroids[index].vertices[2].x = 6;

asteroids[index].vertices[2].у = -5;

asteroids[index].vertices[3].x = 2;

asteroids[index].vertices[3].у =—3;

asteroids[index].vertices[4].x = -4;

asteroids[index].vertices[4].у = -6;

asteroids[index].vertices[5].x = -3.5;

asteroids[index].vertices[5].у =5.5;

// теперь масштабируем каждый астероид до нужного размера

Scale_Object((object_ptr)&asteroids [index],

asteroids[index].scale) ;

} // конец цикла for

} // конец функции ///////////////////////////////////////////////////////

void Draw_Asteroids(int erase)

{

int index,vertex;

float xo,yo;

for (index=0; index
{

// рисуем астероид

if (erase==ERASE)

_setcolor(0);

else

_setcolor(asteroids[index].color);

// получить позицию объекта

xo = asteroids[index].xo;

yo = asteroids[index].yo;

// перемещаемся к первой вершине

_moveto((int)(xo+asteroids[index].vertices[0].x),

(int)(yo+asteroids[index],vertices[0].y));

for (vertex=1; vertex
{

_lineto((int)(xo+asteroids[index].vertlces[vertex].x),(int) (yo+asteroids[index].vertices [vertex].y));

} // конец цикла for по вершинам

// замыкаем контур

_lineto((int)(xo+asteroids[index].vertices[0].x), (int)(yo+asteroids[index].vertices[0].y));

} // конец цикла for по астероидам

} // конец функции ///////////////////////////////////////////////////////////////////////////////////////////

void Translate_Asteroids()

{

int index;

for (index=0; index
// перемещаем текущий астероид

asteroids[index].xo += asteroids[index].x_velocity;

asteroids[index].yo += asteroids[index].y_velocity;

if (asteroids[index].xo > 600 || asteroids[index].xo < 40)

{

asteroids[index].x_velocity = -asteroids[index].x_velocity;

asteroids[index].xo += asteroids[index].x_velocity;

}

if (asteroids[index].yo > 440 || asteroids[index].yo < 40)

{

asteroids [index].y_velocity = -asteroids[index] .y_velocity;

asteroids[index].yo += asteroids[index].y_velocity;

}

} // конец цикла for } // конец функции

///////////////////////////////////////////////////////

void Rotate_Asteroids(void)

{

int index;

for (index=0; index
{

// вращаем текущий астероид

Rotate_0bject ((object_ptr) &asteroids [index],

asteroids[index].angle);

} // конец цикла for

} // конец функции

///////////////////////////////////////////////////////

void main(void) {

_setvideomode(_VRES16COLOR); // 640х480, 16 цветов

// инициализируем поле астероидов

Create_Field{) ;

while(!kbhit())

{ // очищаем поле

Draw_Asteroids(ERASE) ;

// изменяем поле

Rotate_Asteroids();

Translate_Asteroids();

// рисуем поле

Draw_Asteroids(DRAW) ;

// небольшая задержка

Delay(500);

} // конец цикла while

// устанавливаем текстовый режим

_setvideomode( DEFAULTMODE);

} // конец функции main


Набрав, откомпилировав и запустив программу из Листинга 4.8, вы увидите на экране поле астероидов вместе со множеством разноцветных камней, отскакивающих от границ экрана (определение факта столкновения будет подробнее излагаться далее в этой главе, а также в главе одиннадцатой, «Алгоритмы, структуры данных и методология видеоигр»)

Теперь нам надо еще кое-что обсудить:
  • Первое, на что вы обратили внимание, это то, что образы слегка мелькают. Это связано с тем, что программа формирует изображение в тот же момент, когда происходит перерисовка экрана.
  • Экран — это множество линий, которые рисуются на мониторе слева направо и сверху вниз вашей видеокартой. Проблема заключается в том, что мы не можем изменять видеобуфер, пока на экране что-то рисуется. В пятой главе, «Секреты VGA-карт», мы обсудим рисование всего экрана целиком в отдельный буфер с последующим перемещением его в видеопамять;
  • Другая проблема, связанная с мерцанием, заключается в том, что мы используем графическую бибилотеку Microsoft С, которая не очень быстро работает. Вы должны понимать, что Microsoft не оптимизировал ее для высокой производительности и скорости работы;
  • Программа использует числа с плавающей запятой, которые впоследствии будут заменены числами с фиксированной запятой;
  • Вся программа совершенно неэффективна с точки зрения написания видеоигр. Все, что она делает, выполнено в классической, «книжной» манере. У разработчиков видеоигр есть правило номер 1: «Всегда есть способ сделать то, что кажется невозможным». Если б это было не так, то половина видеоигр вообще никогда не была бы написана, поскольку ПК не в состоянии обеспечить нужной производительности.

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

Отсечения

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

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

ситуации.

Отсечения могут производится на двух; «уровнях»:
  • Уровень образа;
  • Уровень объекта.

Отсечение области образов основывается на проверке каждой точки, кото рая может быть нарисована на экране в отсекаемой области. Например, если мы имеем квадратную область, которая соприкасается с границами экрана в режиме 13п (320х200), то мы не будем рисовать точки, выходящие за границу. Точки, которые находятся внутри области и ограничены координатами 0-319 по оси Х и 0-199 по оси Y, будут нарисованы, остальные - нет.

Поскольку все объекты, которые могут появляться на экране компьютера состоят из точек, то этот метод наиболее прост в реализации. Какие геометри­ческие фигуры рисуются, в этом случае не имеет значения. Будь то линии, треугольники, битовые карты и еще что-нибудь - все они используют вызов функции рисования точки. Если функция, рисующая точку, определяет, что точка выходит за границы области, то данная точка не ставится.

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

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

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

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

Матрицы

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

Матрица — это множество чисел, сгруппированных в колонки и столбцы. Здесь изображены две матрицы: Матрица А и Матрица В.



Матрица А — это матрица 2х3 (то есть у нее две строки и три столбца), тогда как матрица В — это матрица 3х3. Мы можем получить доступ к элементу матрицы А, используя запись А[m,n], где m - это строка, а n - столбец. Элемент в левом верхнем углу матрицы А будет обозначаться А[0,0] и он равен, единице.

Произведение операций над матрицами

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

Для примера, рассмотрим сложение двух матриц размерностью 2х3 - матрицы А и матрицы С:



При сложении матриц А и С нужно складывать каждый из элементов m,n. Суммы элементов займут в результирующей матрице сответствующие места:



Мы также можем умножить матрицу на скаляр k. Например, чтобы умножить матрицу А на 3, мы должны умножить на 3 каждый ее элемент:



Теперь поговорим об умножении двух матриц. Эта операция немного отличается от умножения на скалярную величину. Вы должны запомнить несколько правил:
  • Количество столбцов в первой матрице (n) должно быть равно количеству строк во второй (также n). Это значит, что если размерность первой матрицы (mxn), то размерность второй матрицы должна быть (nхr). Два остальных измерения m и r могут быть любыми;
  • Произведение матриц не коммутативно, то есть А х В не равно В х А.

Умножение матрицы mxn на матрицу nхr может быть описано алгоритмически следующим образом:
    1. Для каждой строки первой матрицы:
      • Умножить строку на столбец другой матрицы поэлементно.
      • Сложить полученный результат;
    1. Поместить результат в позицию [i,j] результирующей матрицы, где i - это строка первой матрицы, a j - столбец второй матрицы.

Для простоты посмотрим на рисунок 4.9:



Мы можем это сделать намного проще, написав программу на Си. Давайте определим матрицу 3х3 и напишем функцию, умножающую матрицы. В Листинге 4.9 показана соответствующая программа.