Один метод побудови полігональних зображень
Василь Терешков
Побудова тривимірних зображень
об'єктів за допомогою комп'ютера - тема, яка здавна привертала особливу увагу
програмістів та розробників апаратних засобів. З появою ефективних
графічних бібліотек (Direct3D, OpenGL і т.п.) і спеціалізованих відеокарт
інтерес до математичних основ машинної графіки знизився, оскільки у
програмістів зникла необхідність самостійно створювати алгоритми
побудови зображень. У цьому одна зі сторін сумної тенденції перетворення
програмування з мистецтва в ремесло.
Все ж чимало є й тих, хто захоче не тільки
отримати результат, а й дізнатися, що лежить між інтерфейсом графічної
бібліотеки і готової картинкою на екрані. Для них і призначена ця стаття, в
якої ми постараємося викласти суть одного методу побудови тривимірних
зображень, можливо, не найефективнішого.
Термінологія
Перш пояснимо деякі математичні поняття,
якими будемо користуватися й надалі.
Світова система координат - у нашому випадку
просторова прямокутна система координат (СК), дві осі якої (X та Y)
спрямовані на всі боки екрану монітора, а третя - від спостерігача.
Екранна система координат - СК у площині екрана, її
осі збігаються з осями X та Y світової СК.
Система координат моделі - СК, щодо якої в
файлі задані координати всіх вершин моделі, зображення якої будується.
Вектор - спрямований відрізок, його становище будемо
задавати або координатами початку і кінця, або їх дивовижними речами (власне
координатами вектора). Довжина (модуль) вектора розраховується як квадратний
корінь з суми квадратів його координат - це наслідок теореми Піфагора.
Скалярний добуток векторів - число p, визначається наступним чином: 
або 
, де | A | і
| B | - довжини векторів A і B, x, y, z - їх координати, t - кут між ними.
Колінеарні вектори - два або більше вектора, що лежать на одній прямій або
паралельні прямі. Компланарність вектори - три або більше вектора, які при
відкладення з однієї точки виявляються що лежать в одній площині. Якщо вектори
A, B, C компланарність, то вектор C можна розкласти по векторах A і B, тобто
C = aA + bB, де a і b - деякі коефіцієнти. Нормаль до вектору - вектор
одиничної довжини, перпендикулярний даному. На площині координати нормалі до
вектору P (x; y) визначаються за формулами:
Визначник - алгебраїчне вираз, записане в
особливій формі. Ми будемо використовувати визначники 3-го порядку:
Існує мнемонічне правило обчислення
визначників 3-го порядку - так зване правило Саррюса, з яким можна
ознайомитися в спеціальній літературі.
Використані дані та їх подання
Можливо, ви звернули увагу на слово
«Полігональних» у заголовку статті. Пояснимо його сенс. «Полігон» в перекладі на
російську мову означає «багатокутник», а «полігональних» - «складений з
багатокутників ». У застосуванні до машинної графіку це означає, що для
побудови зображення довільного тіла спочатку створюється його модель --
складний багатогранник, всі грані якого являють собою багатокутники, як
правило, найпростіші, - трикутники.
У файлі з інформацією про модель повинні бути яких-небудь
чином задані координати всіх вершин (їх кількість може сягати кількох
тисяч) і порядок їх з'єднання. Якщо передбачається накладення текстур, то
кожній вершині повинні бути приписані ще два числа - текстурні координати u,
v. Їх значення в наступному. Текстура являє собою плоске растрове
зображення, яке повинно бути накладено на просторову модель без
розривів. Це передбачає нерівномірне деформацію текстури - її стиск і
розтяг. Але одночасно потрібно, щоб текстура не «сповзла», тобто під
всіх щитах моделі виявилися строго певні точки растру. Ці точки і
задаються координатами u, v в системі координат, пов'язаної з текстурою. Доброю
механічної аналогією може послужити шматок гуми, натягує на каркас і
прикріплюється шпильками у вершинах каркаса.
З технічної точки зору зберігати всі ці дані
Кращий час у двійковому файлі, що містить три масиви:
// Інформація про вершини
struct TVertex
(
float x;// координати в СК моделі
float y;
float z;
)
Vertices [NUM_VERTICES];
// Інформація про гранях
struct Ttriangle
(
int i1;// номери вершин, що становлять межу, в масиві Vertices
int i2;
int i3;
float u1;// текстурні координати вершин
float v1;
float u2;
float v2;
float u3;
float v3;
)
Triangles [NUM_TRIANGLES];
// Текстура (256 кольорів)
unsigned
char Texture [TEXTURE_SIZE];
Окремо потрібно вказати ракурс, під яким буде
видно модель. Найбільш зручним для користувача було б завдання осі обертання в
вигляді вектора і кута повороту навколо неї. Однак значно простіше реалізувати
послідовні повороти за трьома кутами: навколо осі X, навколо осі Y ', до якої
перейшла вісь Y при першому повороті, навколо осі Z'', до якої перейшла вісь Z 'при
другому повороті.
Алгоритм побудови зображення
Зображення моделі будується по окремих гранях, а
зображення межі - по окремих точках, для кожної з яких визначається
колір. При цьому, по-перше, зафарбовані повинні бути всі крапки внутрішній області
зображення, по-друге, колір точки повинен розраховуватися лише один раз, що
накладає деякі обмеження на вибір алгоритму.
Першим етапом побудови зображення трикутної грані
буде визначення координат її вершин у світовій СК і, зокрема, їх положення
на екрані, для чого потрібно повернути СК моделі на заздалегідь задані кути (див.
вище). Найбільш витончено такий поворот здійснюється множенням радіуса-вектора
вершини на матрицю повороту. Ми опишемо його в термінах звичайної координатної
геометрії із застосуванням формул повороту «плоскої» (!) СК. Нехай x, y, z --
початкові, а x ', y', z '- кінцеві координати вершини, ТАУ - кут повороту,
тоді ці формули набувають вигляду:
навколо осі X:
навколо осі Y:
навколо осі Z:
Слід пам'ятати, що наше завдання вимагає здійснювати
всі три повороти послідовно і при кожному новому повороті використовувати в
як початкових координат ті, що отримані при попередньому.
Перейдемо до другого, не менш важливого етапу. Після
того, як контур межі на екрані визначений, потрібно знайти всі точки (пікселі),
що лежать всередині нього, іншими словами, вирішити класичну задачу про належність
точки внутрішній області трикутника. Один з варіантів її вирішення (знайдений
автором статті) такий. Уявімо контур межі складеним з векторів, а не
відрізків (див. малюнок 1). До кожного з них проведемо нормаль. Знаки координат
вектора нормалі виберемо так, щоб він був спрямований у бік протилежної
вершини. Тоді всередині трикутника будуть знаходитися ті і тільки ті точки, для
яких всі три скалярних твори вектора, проведеного з якої-небудь
вершини в цю точку, і нормалі, проведеної з тієї самої вершини, є позитивними.
Наприклад, на наведеному малюнку точка P лежить всередині
трикутника, оскільки виконуються співвідношення (тут і далі великими
латинськими літерами будемо позначати точки і вектори, а малими - координати):
Для кожної такої таким чином точки потрібно
визначити її видимість. Для цього використовуємо широко поширений метод
z-буфера. Буфер являє собою масив виду
float
ZBuffer [SCREEN_WIDTH] [SCREEN_HEIGHT];
Кожній точці на екрані (пікселю) відповідає один
елемент масиву, а його значення трактується як «глибина» цієї точки, іншими
словами, її координата z у світовій СК. Перед висновком точки її «глибина»
порівнюється з поточним значенням у масиві і, якщо виявляється менше його,
записується на його місце і крапка виводиться на екран. Таким чином, видимої
серед усіх точок з однаковими координатами x і y виявляється та, у якої
координата z мінімальна.
Уважний читач помітить, що попередньому етапі
задачу про взаємне розташування точки і трикутника ми вирішували в площині
екрану і ні для однієї з перевіряються точок координата z взагалі невідома. Зате
відомі координати z вершин трикутної грані, а крім того, той очевидний
факт, що будь-яка з точок (нехай це буде все та ж точка P на малюнку вгорі)
лежить в площині грані. Отже, вектори A, C, XP (можна вибрати й
інші трійки) компланарність і
Ця система з невідомими a, b, Zxp легко вирішується
методом підстановки. Склавши Zx і Zxp, ми отримаємо координату z точки P.
Тепер, якщо ми переконалися, що точка знаходиться всередині
трикутника і вона не перекреслені іншими точками, можна приступити до останнього
етапу - визначення її кольору виходячи з текстурних координат вершин грані, то
Тобто, по суті, відшукання текстурних координат цієї точки. При накладанні на
грань текстура деформується - розтягується або стискується - але так, що при
цієї деформації прямі лінії залишаються прямими. Таке перетворення площини
називається афінному і задається рівняннями виду
x '=
ax + by + c;
y '=
dx + ey + f.
Наведені рівняння справедливі для координат будь-якої
точки, в тому числі і для вершин, а отже, якщо ми, наприклад, хочемо знайти
координату u точки P, то повинні спочатку визначити a, b, c, вирішивши систему
рівнянь
Для вирішення таких систем часто застосовують так
зване правило Крамера. Нехай F11 - визначник, отриманий виписуванням
коефіцієнтів перед невідомими в правій частині так, як вони розташовані в
системі, а F12 - визначник, отриманий з F11 заміною i-го стовпця на
стовпець вільних членів (ліва частина системи). Тоді i-і невідоме
розраховується за формулою
Так знаходяться числа a, b, c і, аналогічно, d, e, f,
які потім застосовуються для розрахунку текстурних координат точки P. Далі колір
точки текстури з цими координатами переноситься в точку P на екрані. Побудова
точки завершено.
Недоліки концепції
Розглянутий нами метод працездатний і цілком
надійний. Але у нього є і суттєві недоліки, пов'язані, в першу
чергу, до швидкості побудови зображення. Так, зображення моделі, що складається
з 1250 граней, на комп'ютері з процесором Celeron з тактовою частотою 1,3 ГГц
будується за 1,5 секунди. Ясно, що для застосування в практичних завданнях метод
потрібно оптимізувати, перш за все, зменшенням кількості операцій
множення і ділення чисел.
Насторожують також і вимоги до обсягів оперативної
памяти: один тільки z-буфер, що є, по суті, допоміжною структурою, в
графічному режимі 640х480 пікселів зажадає 1,2 Мб.
Зауважу, що на даний момент описаний алгоритм
реалізований на мові високого рівня, застосування асемблера змогло б кілька
збільшити його швидкодію.
Список літератури
Для підготовки даної роботи були використані
матеріали з сайту http://www.rsdn.ru/
