Ви є тут

Методи та засоби підвищення продуктивності зафарбовування тривимірних об'єктів у системах комп'ютерної графіки

Автор: 
Чорний Анатолій Вікторович
Тип роботи: 
Дис. канд. наук
Рік: 
2004
Артикул:
0404U004667
129 грн
Додати в кошик

Вміст

РОЗДІЛ 2
ТЕОРЕТИЧНІ ЗАСАДИ ЩОДО ВИЗНАЧЕННЯ ВИХІДНИХ ПАРАМЕТРІВ ДЛЯ ЗАФАРБОВУВАННЯ ТРИВИМІРНИХ
ГРАФІЧНИХ ОБ'ЄКТІВ

У даному розділі дисертаційної роботи проведено дослідження методів Гуро і Фонга з метою отримання більш простих аналітичних залежностей по визначенню вихідних параметрів для зафарбовування тривимірних графічних об'єктів.

2.1. Дослідження граничних ефектів, обумовлених дискретним
характером формування крокових траєкторій полігонів

Генерація об'ємних зображень є складною обчислювальною задачею, в зв'язку з чим на практиці виконують її декомпозицію. Складні зображення формують фрагментарно, для чого їх розбивають на складові частини. Процес розбиття поверхні об'єктів на полігони одержав назву теселяції [14, 29].
Процес розбиття полігональної області зі складною конфігурацією в набір трикутників називається тріангуляцією [29].
Поява точок "просікання" можлива під час тріангуляції з таких причин:
1) одна і та ж вершина полігональної сітки в наслідок похибок округлення може в різних трикутниках мати різні значення координат [35];
2) у ряді випадків тріангуляція полігону може призвести до появи трикутника зі стороною в один піксел. Наприклад, при розпаралеленні процедури зафарбовування з використанням медіанного перетину для тріангуляції [33] ;
3) для збалансованого завантаження рендерерів при розпаралеленні процедури зафарбовування вихідний трикутник розбивається на ряд однакових трикутників [35], які можуть частково не перекриватись.
У зв'язку з цим виникає задача дослідження краєвих ефектів, які можуть привести до появи точок "просікання". Для цього необхідно дослідити, при яких зміщеннях двох базових векторів, прирости яких можуть відрізнятись не більше ніж на одну дискрету, можлива поява точок "просікання".
Властивість 1. Якщо два відрізки мають спільну початкову точку, а їх кінцеві точки відрізняються на одну горизонтальну (вертикальну) дискрету, то під час формування таких відрізків в однаковому напрямку між ними будуть відсутні точки "просікання".
Доведення. Розглянемо в першому октанті два відрізки AB і АС таких, що , а (рис. 2.1). Враховуючи те, що кінець відрізка попадає в точку координатної сітки, з найбільшою вірогідністю точка "просікання" може з'явитись між передостанніми точками відповідних відрізків. Це пояснюється тим, що для даного випадку має місце максимальне відхилення відрізків АВ та АС один від одного за умови, що точки L і M відрізків не попадають у вузли P і Q координатної сітки (рис. 2.1).
Між точками P і Q "просікання" будуть відсутні, якщо відстань між ними, з урахуванням похибок, буде меншою двох дискрет.
Складемо нерівність:
. (2.1)
Найчастіше для формування відрізків використовують алгоритми [26], в яких максимальне відхилення крокової траєкторії від ідеального відрізка прямої складає не більше половини кроку дискретизації. Тому = =0.5. Підставляючи відповідні значення і в формулу (2.1), отримуємо
. (2.2)
Якщо , а , тоді , .
Підставляючи вказані значення в формулу (2.2), отримуємо
; ; . (2.3)
Оскільки координата х точки, де найвірогідніша поява точки "просікання", дорівнює БП - 1, то умова (2.3) завжди є правильною.
Аналогічно доводиться відсутність точок "просікання" і для випадку, коли кінцеві точки відрізків відрізняються на одну горизонтальну дискрету.
Властивість 2. Якщо два відрізки мають спільну початкову точку, а їх кінцеві точки відрізняються на один діагональний крок за умови, що відрізок з більшим нахилом по провідній координаті довший, то під час побудови таких відрізків в однаковому напрямку точки "просікання" між ними
відсутні (рис. 2.2).
Доведення. Точки "просікання" будуть відсутні, при виконанні умови:
.
Нехай , а , тоді , .
; .
Підставимо в останній вираз значення координати , де з найбільшою вірогідністю може виникнути точка "просікання".
. (2.4)
, а , тому умова (2.4) завжди вірна.
Властивість 3. Якщо два відрізки мають спільну початкову точку, а їх кінцеві точки відрізняються на один діагональний крок за умови, що відрізок з більшим нахилом по провідній координаті - коротший, то під час побудови таких відрізків в однаковому напрямку точки "просікання" між ними відсутні лише за умови, що max(МП1, MП2)?{0,1,2}, де МП1 - менший приріст відрізка, який має менший кут нахилу до осі ОХ, а MП2 - менший приріст відрізка, який має більший кут нахилу до осі ОХ.
Доведення. Розглянемо випадок, зображений на рис. 2.3.
Складемо нерівність:
. (2.5)
Нехай , а .
Підставляючи вказані значення в формулу (2.5), отримуємо:
; ;
Підставимо в останній вираз значення координату , в якій з найбільшою вірогідністю може виникнути точка "просікання":
. (2.6)
Перетворивши вираз (2.6), отримаємо:
. (2.7)
Нерівність (2.7) виконується тільки за умови, що МП приймає значення, не більше двох.
Властивість 4. Якщо під час формування відрізків в одному напрямку їх початкові точки відрізняються на одну дискрету, а кінцеві - відповідно на одну вертикальну(горизонтальну) дискрету, то між ними точки "просікання" будуть відсутні (рис. 2.4).
Доведення. На рис. 2.4 представлені всі можливі комбінації розташування двох відрізків в першому октанті, які задовольняють умовам властивості 4. Для доведення розглянемо лише випадок 2.4а, оскільки випадок, зображений на рисунку 2.4б, аналогічний випадку 2.4а, а випадки, зображені на рисунках 2.4в і 2.4г, відповідають умовам властивості 1,
оскільки відрізки мають точку перетину. Для точок L і М (рис. 2.4) складемо нерівність: