Студопедия — Алгоритм Сазерленда-Ходжмана
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритм Сазерленда-Ходжмана






Этот алгоритм (Sutherland-Hodgman algorithm) предназначен, на самом деле, для отсечения произвольного полигона (даже не обязательно выпуклого, хотя использовать невыпуклые полигоны довольно, на мой взгляд, нерационально) в полуплоскость, или, для 3D случая, в полупространство; другими словами, отсечения полигона прямой или плоскостью. Применяя алгоритм несколько раз, получаем методы отсечения в выпуклый полигон (например, прямоугольник, которым является экран) или выпуклый объем (например, ту часть пространства, которую видно из камеры).

Итак, пусть у нас есть полигон с N вершинами, заданными в каком-то порядке, то есть, по часовой стрелке или против; в каком именно, алгоритму все равно. Занумеруем их от 0 до N-1. Теперь последовательно обходим все ребра полигона: ребро от вершины 0 до вершины 1, от 1 до 2,..., от N-2 до N-1, от N-1 до 0.

Вершины, являющиеся началом и концом ребра, могут лежать в области отсечения, (область отсечения - либо полуплоскость для 2D случая, либо полупространство для 3D случая) могут и не лежать; возможны следующие случаи:

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

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

- начало не лежит в области отсечения, конец лежит. Тоже считаем точку пересечения, и добавляем только ее.

- начало не лежит в области отсечения, конец тоже. Переходим к следующему ребру, никак не изменяя результат.

 

Рассмотрим простенький пример работы алгоритма в 2D случае, а именно отсечем 2D треугольник прямой. Она делит плоскость на две полуплоскости, две области, нужную и ненужную.

|

отсекаемая | нужная

область | 1 область

| /..\

| /.....\

A........\

/ |.........\

/ |..........\

0-----B-----------2

|

|

- шаг 1, ребро 0-1: вершина 0 не лежит в нужной области, вершина 1 лежит.

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

- шаг 2, ребро 1-2: обе вершины лежат в области, добавляем вершину 1.

Результат теперь являет собой список A, 1.

- шаг 3, ребро 2-0: 2 лежит в области, 0 не лежит. Добавляем вершину 2 и

точку пересечения B. После последнего шага, таким образом, получили

корректный результат отсечения - полигон с вершинами A, 1, 2, B.

В случае, когда надо сделать отсечение в экран, последовательно применяем алгоритм, отсекая полигон прямыми sx=0, sx=XSIZE, sy=0, sy=YSIZE. Из-за такого простого вида уравнений прямых соответственно упрощается код для выяснения принадлежности вершины нужной области и поиска точки пересечния. Вот, например, кусок кода для отсечения полигона прямой sx=0 (оставляющий область sx > 0).

// dst - массив для сохранения вершин результата

// src - массив вершин исходного полигона

// n - число вершин исходного полигона

// функция возвращает число вершин результата

int clipLeft(vertex *dst, vertex *src, int n) {

int i, r;

vertex p1, p2;

float k;

r = 0;

for (i = 0; i < n; i++) {

p1 = src[i];

p2 = src[(i + 1) % n];

if (p1.sx >= 0) { // если начало лежит в области

if (p2.sx >= 0) { // если конец лежит в области

dst[r++] = p1; // добавляем начало

} else { // если конец не лежит в области

dst[r++] = p1; // добавляем начало

k = -p1.sx / (p2.sx - p1.sx); // добавляем точку пересечения

dst[r].sx = 0;

dst[r].sy = p1.sy + k * (p2.sy - p1.sy);

dst[r].u = p1.u + k * (p2.u - p1.u);

dst[r].v = p1.v + k * (p2.v - p1.v);

r++;

}

} else { // если начало не лежит в области

if (p2.sx >= 0) { // если конец лежит в области

k = -p1.sx / (p2.sx - p1.sx); // добавляем точку пересечения

dst[r].sx = 0;

dst[r].sy = p1.sy + k * (p2.sy - p1.sy);

dst[r].u = p1.u + k * (p2.u - p1.u);

dst[r].v = p1.v + k * (p2.v - p1.v);

r++;

}

}

}

return r;

}

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

// dst - массив для сохранения вершин результата

// src - массив вершин исходного полигона

// n - число вершин исходного полигона

// функция возвращает число вершин результата

int clipLeft(vertex *dst, vertex *src, int n) {

int i, r;

vertex p1, p2;

float k;

r = 0;

for (i = 0; i < n; i++) {

p1 = src[i];

p2 = src[(i + 1) % n];

if (p1.sx >= 0) { // если начало лежит в области

dst[r++] = p1; // добавляем начало

}

if (((p1.sx > 0) && (p2.sx < 0)) || // если ребро пересекает границу

((p2.sx >= 0) && (p1.sx < 0))) // добавляем точку пересечения

{

k = -p1.sx / (p2.sx - p1.sx);

dst[r].sx = 0;

dst[r].sy = p1.sy + k * (p2.sy - p1.sy);

dst[r].u = p1.u + k * (p2.u - p1.u);

dst[r].v = p1.v + k * (p2.v - p1.v);

r++;

}

}

return r;

}

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







Дата добавления: 2015-10-02; просмотров: 542. Нарушение авторских прав; Мы поможем в написании вашей работы!



Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Педагогическая структура процесса социализации Характеризуя социализацию как педагогический процессе, следует рассмотреть ее основные компоненты: цель, содержание, средства, функции субъекта и объекта...

Типовые ситуационные задачи. Задача 1. Больной К., 38 лет, шахтер по профессии, во время планового медицинского осмотра предъявил жалобы на появление одышки при значительной физической   Задача 1. Больной К., 38 лет, шахтер по профессии, во время планового медицинского осмотра предъявил жалобы на появление одышки при значительной физической нагрузке. Из медицинской книжки установлено, что он страдает врожденным пороком сердца....

Типовые ситуационные задачи. Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт. ст. Влияние психоэмоциональных факторов отсутствует. Колебаний АД практически нет. Головной боли нет. Нормализовать...

Образование соседних чисел Фрагмент: Программная задача: показать образование числа 4 и числа 3 друг из друга...

Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия