Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

torrvic, возможно, Вам нужно добавить -lGLU
Извините за тупой вопрос. У меня при сборке Вашего примера выходит ошибка: "undefined reference to gluLookAt". Не могу найти в какой библиотеке находится эта функция. У меня задано: -lGL -lglut ... Искал в /usr/lib таким образом: nm lib*so* | grep...
Здравствуйте. Спасибо за проект. У меня вопрос, по какой причине определение принадлежности точки многоугольнику работает некорректно, если координаты из больших чисел состоят, например: int[] vertex = new int[] {...
Сейчас проверила нашла причину не запускания // Создание контекста воспроизведения OpenGL и привязка его к панели на форме OpenGLControl1:=TOpenGLControl.Create(Self); with OpenGLControl1 do begin Name:='OpenGLControl1'; //вот тут...
Ну..кажется что то пошло не так http://pp.usera...

Счетчики и рейтинг

Рейтинг@Mail.ru

На практике графические объекты всегда отображаются на конечном растре, границы которого соответствуют границам экрана или внеэкранного буфера. Растеризация на конечном растре требует возможности отсечения растеризуемого объекта относительно границ растра, т.е. удаления частей растеризуемого объекта, лежащих за пределами растра. Выполнение алгоритма растеризации без предварительного отсечения приведет к ошибке при попытке осуществить изменение цвета пикселя с координатами за пределами растра (это может привести к изменению цвета не того пикселя или даже к системному сбою).

Самой простой задачей отсечения является задача отсечения отрезков. Одним из алгоритмов, позволяющих осуществлять отсечение отрезка, является Алгоритм Сазерленда-Коэна.

Алгоритм Сазерленда-Коэна разделяет плоскость на 9 частей прямыми, которые образуют стороны прямоугольника. Каждой из 9 частей присваивается четырёхбитный код. Биты (от младшего до старшего) значат «левее», «правее», «ниже», «выше». Иными словами, у тех трёх частей плоскости, которые слева от прямоугольника, младший бит равен 1, и так далее.

После того, как коды получены, возможны следующие варианты:

1) Коды содержат только 0, а значит отрезок целиком лежит внутри окна и должен быть отрисован целиком;

2) Коды содержат единичный бит в одной и той же позиции, а значит, отрезок лежит за пределами окна и не будет отрисован;

3) Во всех остальных случаях в окне лежит только часть отрезка, и это значит, что есть необходимость в отсечении.

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

Если код любого из концов содержит единичный бит, то либо P1, либо P2 перемещается из-за пределов окна к одной из его границ (или к её продолжению). Т.е. точка P1 перемещается в точку R, а P2 в точку U. Для новых точек мы вновь вычисляем четырёхбитные коды. В нашем случае концы отрезка по-прежнему лежат вне окна, т.е. нам понадобится ещё одно перемещение: точка R переместиться в точку S, а точка U переместиться в точку T.

Получается, что процесс отсечения является итеративным. Так как на каждом шаге уменьшается расстояние между концами отрезка, мы можем утверждать, что алгоритм сойдётся. В итоге будет получен отрезок (в нашем случае (S;T), который и надо отобразить).

Рассмотрим работу этого алгоритма на ещё одном примере.

Расположение отрезка (P1;P2) не соответствует ни условиям полной видимости, ни условиям полной невидимости, поэтому в этом случае тоже прибегнуть к операции переноса точек.

После выполненных переносов коды концов отрезка удовлетворяют второму условию, т.е. отрезок целиком не будет выводиться на экран.

Таким образом, данный алгоритм определяет код концов отрезка. Если оба кода равны нулю, то отрезок полностью находится в прямоугольнике. Если битовое И кодов не равно нулю, то отрезок не пересекает прямоугольник (так как это значит, что оба конца отрезка находятся с одной стороны прямоугольника). В прочих случаях, алгоритм выбирает конец отрезка (или один из концов), имеющий ненулевой код (то есть находящийся вне прямоугольника), находит ближайшую к нему точку пересечения отрезка с одной из прямых, образующих стороны прямоугольника, и использует эту точку пересечения как новый конец отрезка. Укороченный отрезок снова пропускается через алгоритм.

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