Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения

Подождите немного. Документ загружается.

ПРЕОБРАЗОВАНИЯ НА ПЛОСКОСТИ И В ПРОСТРАНСТВЕ

if ( d != 1.0)

{

for ( int j = 0; j < 4; j++ )

{

Out.x [i][j] /= d;

x [i][j] /= d;

}

for ( int j = 0; j < 4; j++ )

{

if ( j != i )

{

if ( x [j][i] != 0.0)

{

doublemulby = x[j][i];

for ( int k = 0; k < 4; k++ )

{

x [j][k] = mulby * x [i][k];

Out.x [j][k] = mulby * Out.x [i][k];

}

*this = Out;

}

void Matrix :: Transpose ()

{

doublet;

for ( int i = 0; i < 4; i++ )

for ( int j = i; j < 4; j++ )

if ( i != j )

{

t = x [i][j];

x [i][j] = x [j][i];

x [j][i] = t;

}

Matrix& Matrix :: operator += ( const Matrix& A )

{

for ( int i = 0; i < 4; i++ )

for ( int j = 0; j < 4; j++ )

x [i][j] += A.x [i][j];

return *this;

}

Matrix& Matrix :: operator = ( const Matrix& A )

{

for ( int i = 0; i < 4; i++ )

for ( int j = 0; j < 4; j++ )

x [i][j] = A.x [i][j];

return *this;

}

Matrix& Matrix :: operator *= ( double v )

{

for ( int i = 0; i < 4; i++ )

ПРЕОБРАЗОВАНИЯ НА ПЛОСКОСТИ И В ПРОСТРАНСТВЕ

for ( int j = 0; j < 4; j++ )

x [i][j] *= v;

return *this;

}

Matrix& Matrix :: operator *= ( const Matrix& A )

{

Matrixres = *this;

for ( int i = 0; i < 4; i++ )

for ( int j = 0; j < 4; j++ )

{

double sum = 0;

for ( int k = 0; k < 4; k++ )

sum += res.x [i][k] * A.x [k][j];

x [i][j] = sum;

}

return *this;

}

Matrix operator + ( const Matrix& A, const Matrix& B )

{

Matrixres;

for ( int i = 0; i < 4; i++ )

for ( int j = 0; j < 4; j++ )

res.x [i][j] = A.x [i][j] + B.x [i][j];

return res;

}

Matrix operator  ( const Matrix& A, const Matrix& B )

{

Matrixres;

for ( int i = 0; i < 4; i++ )

for ( int j = 0; j < 4; j++ )

res.x [i][j] = A.x [i][j]  B.x [i][j];

return res;

}

Matrix operator * ( const Matrix& A, const Matrix& B )

{

Matrixres;

for ( int i = 0; i < 4; i++ )

for ( int j = 0; j < 4; j++ )

{

double sum = 0;

for ( int k = 0; k < 4; k++ )

sum += A.x [i][k] * B.x [k][j];

res.x [i][j] = sum;

}

return res;

}

Matrix operator * ( const Matrix& A, double v )

{

ПРЕОБРАЗОВАНИЯ НА ПЛОСКОСТИ И В ПРОСТРАНСТВЕ

Matrixres;

for ( int i = 0; i < 4; i++ )

for ( int j = 0; j < 4; j++ )

res.x [i][j] = A.x [i][j] * v;

return res;

}

Vector operator * ( const Matrix& M, const Vector& v )

{

Vectorres;

res.x = v.x * M.x [0][0] + v.y * M.x [1][0] + v.z * M.x [2][0] + M.x [3][0];

res.y = v.x * M.x [0][1] + v.y * M.x [1][1] + v.z * M.x [2][1] + M.x [3][1];

res.z = v.x * M.x [0][2] + v.y * M.x [1][2] + v.z * M.x [2][2] + M.x [3][2];

doubledenom = v.x * M.x [0][3] + v.y * M.x [1][3] + v.z * M.x [2][3] + M.x [3][3];

if ( denom != 1.0 )

res /= denom;

return res;

}

//////////////////////// Derived classes /////////////////////////////

Matrix Translate ( const Vector& Loc )

{

Matrixres ( 1 );

res.x [3][0] = Loc.x;

res.x [3][1] = Loc.y;

res.x [3][2] = Loc.z;

return res;

}

Matrix Scale ( const Vector& v )

{

Matrixres ( 1 );

res.x [0][0] = v.x;

res.x [1][1] = v.y;

res.x [2][2] = v.z;

return res;

}

Matrix RotateX ( double Angle )

{

Matrixres ( 1 );

double Cosine = cos ( Angle );

double Sine = sin ( Angle );

res.x [1][1] = Cosine;

res.x [2][1] = Sine;

res.x [1][2] = Sine;

res.x [2][2] = Cosine;

return res;

}

Matrix RotateY ( double Angle )

{

Matrixres ( 1 );

ПРЕОБРАЗОВАНИЯ НА ПЛОСКОСТИ И В ПРОСТРАНСТВЕ

double Cosine = cos ( Angle );

double Sine = sin ( Angle );

res.x [0][0] = Cosine;

res.x [2][0] = Sine;

res.x [0][2] = Sine;

res.x [2][2] = Cosine;

return res;

}

Matrix RotateZ ( double Angle )

{

Matrixres ( 1 );

double Cosine = cos ( Angle );

double Sine = sin ( Angle );

res.x [0][0] = Cosine;

res.x [1][0] = Sine;

res.x [0][1] = Sine;

res.x [1][1] = Cosine;

return res;

}

Matrix Rotation ( const Vector& axis, double angle )

{

Matrixres ( 1 );

double Cosine = cos ( angle );

double Sine = sin ( angle );

res.x [0][0] = axis.x * axis.x + ( 1  axis.x * axis.x ) * Cosine;

res.x [0][1] = axis.x * axis.y * ( 1  Cosine ) + axis.z * Sine;

res.x [0][2] = axis.x * axis.z * ( 1  Cosine )  axis.y * Sine;

res.x [0][3] = 0;

res.x [1][0] = axis.x * axis.y * ( 1  Cosine )  axis.z * Sine;

res.x [1][1] = axis.y * axis.y + ( 1  axis.y * axis.y ) * Cosine;

res.x [1][2] = axis.y * axis.z * ( 1  Cosine ) + axis.x * Sine;

res.x [1][3] = 0;

res.x [2][0] = axis.x * axis.z * ( 1  Cosine ) + axis.y * Sine;

res.x [2][1] = axis.y * axis.z * ( 1  Cosine )  axis.x * Sine;

res.x [2][2] = axis.z * axis.z + ( 1  axis.z * axis.z ) * Cosine;

res.x [2][3] = 0;

res.x [3][0] = 0;

res.x [3][1] = 0;

res.x [3][2] = 0;

res.x [3][3] = 1;

return res;

}

Matrix MirrorX ()

{

Matrixres ( 1 );

res.x [0][0] = 1;

return res;

}

Matrix MirrorY ()

{

Matrixres ( 1 );

ПРЕОБРАЗОВАНИЯ НА ПЛОСКОСТИ И В ПРОСТРАНСТВЕ

res.x [1][1] = 1;

return res;

}

Matrix MirrorZ ()

{

Matrixres ( 1 );

res.x [2][2] = 1;

return res;

}

РАСТРОВЫЕ АЛГОРИТМЫ

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

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

решетки) пикселов (растра), то, естественно, возникает необходимость в растровых алгоритмах.

Хотя большинство графических библиотек содержат внутри себя достаточное количество

простейших растровых алгоритмов, таких, как:

• переведение идеального объекта (отрезка, окружности и др.) в их растровые образы;

• обработка растровых изображений,

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

Достаточно важным понятием для растровой сетки является связность  возможность

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

При этом возникает вопрос, когда пикселы (x

)и (x

) можно считать соседними.

Вводится два понятия связности:

2121

≤−+− yyxx ,

8связность, когда пикселы считаются соседними, если их x и yкоординаты отличаются

не более чем на единицу, то есть

4связность, когда пикселы считаются соседними, если либо их xкоординаты, либо y

координаты отличаются на единицу, то есть

≤− xx , 1

≤− yy .

Понятие 4связности является более сильным, чем 8связность: любые

два 4связных пиксела являются и 8связными, но не наоборот (рис. 1).

В качестве линии на растровой сетке выступает набор пикселов P

,..., P

, где любые два пиксела P

i+1

являются соседними.

Замечание

Так как понятие линии базируется на понятии связности, то естественным образом

возникает понятие 4? и 8?связных линий. Поэтому когда мы говорим о растровом представлении,

например, отрезка, то следует ясно понимать, о каком именно представлении идет речь. При этом

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

различные способы построения.

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

Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки

)и (x

). Для простоты будем считать, что 0 =< y

 y

=< x

x

. Тогда отрезок

описывается следующим уравнением:

[]

211

,),( xxxxx

yy ∈−

−

или

y = kx + b .

Простейший алгоритм растрового представления отрезка имеет

вид:

! // File Line1.cpp

void Line ( int x1, int y1, int x2, int y2, int color )

{

double k = ((double)(y2yl))/(x2xl):

double b = y1  k*x1;

for ( int x = x1; x <= x2; x++ )

putpixel ( x, round ( k*x + b ), color );

}

РАСТРОВЫЕ АЛГОРИТМЫ

Используя рекуррентное соотношение для вычисления у, можно упростить функцию,

однако это не устраняет основного недостатка алгоритма  использования вещественных

вычислений для работы на целочисленной решетке.

В 1965 году Брезенхеймом был предложен простой целочисленный алгоритм для

растрового построения отрезка, первоначально предназначенный для использования в

графопостроителях.

При построении растрового изображения отрезка всегда выбирается ближайший по

вертикали пиксел.

При этом из двух точек А и В (рис. 2) выбирается та, которая ближе к исходной прямой

(в данном случае выбирается точка А, так как a < b). Для этого вводится число d, равное (x



)(b а).

В случае d > 0 значение у от предыдущей точки увеличивается на 1, a d на 2(∆y∆x). В

противном случае значение у не изменяется, а значение d заменяется на 2∆y.

Реализация приведенного алгоритма представлена ниже.

! // File Line2.cpp

// simplest Bresenhames alg. 0 <= y2  y1 <= x2  x1

void Line2 ( int x1, int y1, int x2, int y2, int color )

{

int dx = x2  x1;

int dy = y2  y1;

int d = ( dy << 1 )  dx;

int d1 = dy << 1;

int d2 = ( dy  dx ) << 1;

putpixel ( x1, y1, color );

for ( int x = x1 + 1, y = y1; x <= x2; x++ )

{

if ( d > 0 )

{

d += d2;

y += 1;

}

else

d += d1;

putpixel ( x, y, color );

}

Из предложенного примера несложно написать функцию для построения 4связной

развертки отрезка.

! // File Line3.cpp

void Line4 ( int x1, int y1, int x2, int y2, int color )

{

int dx = x2  x1;

int dy = y2  y1;

int d = 0;

int d1 = dy << 1;

int d2 = ( dx << 1 );

putpixel ( x1, y1, color );

for ( int x = x1 , y = y1; i = 1; i <= dx + dy; i++ )

{

if ( d > 0 )

{

d += d2;

y += 1;

}

РАСТРОВЫЕ АЛГОРИТМЫ

else

{

d += d1;

x += 1;

}

putpixel ( x, y, color );

}

Общий случай произвольного отрезка легко сводится к рассмотренному выше, следует

только иметь в виду, что при выполнении неравенства xy ∆≥∆ необходимо поменять местами x

и y.

! // File Line4.cpp

#include <conio.h>

#include <graphics.h>

#include <process.h>

#include <stdio.h>

#include <stdlib.h>

// Bresenhames alg.

void Line ( int x1, int y1, int x2, int y2, int color )

{

int dx = abs ( x2  x1 );

int dy = abs ( y2  y1 );

int sx = x2 >= x1 ? 1 : 1;

int sy = y2 >= y1 ? 1 : 1;

if ( dy <= dx )

{

int d = ( dy << 1 )  dx;

int d1 = dy << 1;

int d2 = ( dy  dx ) << 1;

putpixel ( x1, y1, color );

for ( int x = x1 + sx, y = y1, i = 1; i <= dx; i++, x += sx )

{

if ( d > 0 )

{

d += d2;

y += sy;

}

else

d += d1;

putpixel ( x, y, color );

}

else

{

int d = ( dx << 1 )  dy;

int d1 = dx << 1;

int d2 = ( dx  dy ) << 1;

putpixel ( x1, y1, color );

for ( int x = x1, y = y1 + sy, i = 1; i <= dy; i++, y += sy )

{

if ( d > 0 )

{

d += d2;

x += sx;

}

else

d += d1;

РАСТРОВЫЕ АЛГОРИТМЫ

putpixel ( x, y, color );

}

main ()

{

int driver = DETECT;

int mode;

int res;

initgraph ( &driver, &mode, "" );

if ( ( res = graphresult () ) != grOk )

{

printf("\nGraphics error: %s\n", grapherrormsg ( res) );

exit ( 1 );

}

int x1 = 501,

y1 = 100 ,

x2 = 150,

y2 = 301;

Line ( x1, y1, x2, y2, WHITE );

getch ();

closegraph ();

}

Отсечение отрезка. Алгоритм Сазерленда'Кохена

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

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

области, как правило, выступает прямоугольник.

Ниже рассматривается достаточно простой и эффективный алгоритм

отсечения отрезков по границе произвольного прямоугольника. Он заключается в

разбиении всей плоскости на 9 областей прямыми, образующими прямоугольник.

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

расположены одинаково. Определив, в какие области попали концы

рассматриваемого отрезка, легко понять, где именно необходимо отсечение. Для

этого каждой области сообщается 4битовый код, где установленный бит 0

означает, что точка лежит левее прямоугольника, бит 1 означает, что точка лежит

выше прямоугольника, бит 2 означает, что точка лежит правее прямоугольника, бит

3 означает, что точка лежит ниже прямоугольника.

Приведенная ниже программа реализует алгоритм СазерлендаКохена отсечения

отрезка по прямоугольной области.

! // File clip.cpp

#include <conio.h>

#include <graphics.h>

#include <process.h>

#include <stdio.h>

#include <stdlib.h>

void Swap ( int& a, int& b )

{

int c;

c = a;

a = b;

b = c;

РАСТРОВЫЕ АЛГОРИТМЫ

}

int OutCode ( int x, int y, int X1, int Y1, int X2, int Y2 )

{

int code = 0;

if ( x < X1 )

code |= 0x01;

if ( y < Y1 )

code |= 0x02;

if ( x > X2 )

code |= 0x04;

if ( y > Y2 )

code |= 0x08;

return code;

}

void ClipLine ( int x1, int y1, int x2, int y2,

int X1, int Y1, int X2, int Y2 )

{

int code1 = OutCode ( x1, y1, X1, Y1, X2, Y2 );

int code2 = OutCode ( x2, y2, X1, Y1, X2, Y2 );

int inside = ( code1 | code2 ) == 0;

int outside = ( code1 & code2 ) != 0;

while ( !outside && !inside )

{

if ( code1 == 0 )

{

Swap ( x1, x2 );

Swap ( y1, y2 );

Swap ( code1, code2 );

}

if ( code1 & 0x01 ) // clip left

{

y1 += (long)(y2y1)*(X1x1)/(x2x1);

x1 = X1;

}

else

if ( code1 & 0x02 ) // clip above

{

x1 += (long)(x2x1)*(Y1y1)/(y2y1);

y1 = Y1;

}

else

if ( code1 & 0x04 ) // clip right

{

y1 += (long)(y2y1)*(X2x1)/(x2x1);

x1 = X2;

}

else

if ( code1 & 0x08 ) // clip below

{

x1 += (long)(x2x1)*(Y2y1)/(y2y1);

y1 = Y2;

}

code1 = OutCode ( x1, y1, X1, Y1, X2, Y2 );

code2 = OutCode ( x2, y2, X1, Y1, X2, Y2 );

inside = ( code1 | code2 ) == 0;

outside = ( code1 & code2 ) != 0;