С ростом мощности компьютеров всё большая часть людей пробует работать с графикой. На первый взгляд многие алгоритмы кажутся интуитивно понятными, но, если вы хотите, чтобы ваше приложение работало с приемлемой скоростью, вам придётся изучить классические алгоритмы.
Этот пост посвящён разбору нескольких алгоритмов, направленных на одну и ту же задачу, задачу отсечения отрезков. При генерации изображений могут получаться фигуры произвольной формы и размеров. Зачастую мониторы не могут отобразить сгенерированные изображения целиком. Также иногда возникают ситуации, когда необходимо задать область изображения на экране и выводить изображения только внутри этой области. Для решения этих задач и придуманы алгоритмы отсечения.
Самой простой задачей отсечения является задача отсечения отрезков. Сформулируем её на конкретном примере. Будем считать, что область вывода задаётся прямоугольником ABCD. Рассмотрим пример, и в качестве отсекаемой фигуры возьмём треугольник PRQ.
Процесс отсечения должен выполняться полностью автоматически. Т.е. для отрисовки треугольника PRQ должны выполниться только команды отрисовки отрезков PQ;PP';Q' Q. При этом координаты точек P';Q' заранее не известны.
На практике возможно большое количество взаимных расположений точек отрезка и области вывода. Это разнообразие делает операцию отсечения весьма нетривиальной с алгоритмической точки зрения. Для решения этих задач созданы алгоритмы отсечения.
Весьма интересен алгоритм отсечения, предложенный Сазерлендом и Коэном. Суть алгоритма заключается в том, что концам отрезка присваивается четырёхбитный код: b0,b1,b2,b3. Этот четырёхбитный код содержит информацию о положении точки относительно области вывода. На практике возможны 9 комбинаций:
Поясним эти коды:
Поясним эти коды:
После того, как коды получены, возможны следующие варианты:
Первые два случая легко проверяются с помощью побитовых логических операций. Наибольший интерес представляет именно третий случай. Рассмотрим его на небольшом конкретном примере.
Если код любого из концов содержит единичный бит, то либо P1, либо P2 перемещается из-за пределов окна к одной из его границ (или к её продолжению). Т.е. точка P1 перемещается в точку R, а P2 в точку U. Для новых точек мы вновь вычисляем четырёхбитные коды. В нашем случае концы отрезка по-прежнему лежат вне окна, т.е. нам понадобится ещё одно перемещение: точка R переместиться в точку S, а точка U переместиться в точку T. Получается, что процесс отсечения является итеративным. Так как на каждом шаге уменьшается расстояние между концами отрезка, мы можем утверждать, что алгоритм сойдётся. В итоге будет получен отрезок (в нашем случае (S;T), который и надо отобразить).
Рассмотрим работу этого алгоритма на ещё одном примере.
Расположение отрезка (P1;P2) не соответствует ни условиям полной видимости, ни условиям полной невидимости, поэтому в этом случае тоже прибегнуть к операции переноса точек.
После выполненных переносов коды концов отрезка удовлетворяют второму условию, т.е. отрезок целиком не будет выводиться на экран.
В алгоритме Сазерленда-Коэна поиск точки пересечения отрезка с границей окна может занять несколько итераций. Этого можно избежать, если реализовать поиск точки пересечения с помощью двоичного поиска. Эта идея была предложена Спруллом и Сазерлендом. Программная реализация этого алгоритма медленнее, чем алгоритм Сазерленда-Коэна, но аппаратная реализация быстрее, так как основные операции алгоритма весьма эффективно реализуются в аппаратуре.
Этот метод также использует четырёхбитный код, описанный выше. С помощью этих кодов легко выявляются случаи тривиальной видимости (a) и тривиальной невидимости (b). Остальные (нетривиальные) отрезки разбиваются на две равные части, и проверки выполняются для двух вновь полученных отрезков. Деление и проверки будут выполняться до тех пор, пока не будет обнаружено пересечение со стороной окна, или пока отрезок не выродится в точку. После того, как отрезок выродился, мы определяем его видимость и в зависимости от результата либо отрисовываем току, либо нет.
Рассмотрим отрезок c. Очевидно, что этот отрезок целиком лежит вне границ окна, но он не может быть отвергнут сразу. Именно поэтому мы выполняем половинные деления и исключаем некоторые части отрезка. Деление заканчивается в тот момент, когда отрезок превращается в точку. Убедившись, что полученная точка невидима, мы делаем вывод, что и весь отрезок не должен быть отрисован.
Отрезок d тоже не определяется тривиально. Его деление на две половины (точкой 3) приводит к одинаковым результатам для обеих половин. Отрезок (3;2) разбиваем пополам точкой 4. Теоретически можно уже отрисовать отрезок (3;4), но это не очень эффективно. Правильнее запомнить точку 4, как наиболее удалённую от точки 1 видимую точку, а отрезок (4;2) продолжить разбивать до пересечения с нижней границей окна. Полученная точка и будет считаться наиболее удалённой от точки 1 видимой точкой. Аналогично обрабатывается отрезок 3;1, и находится видимая точка, наиболее удалённая от точки 2. Потом между двумя этими точками и происходит отрисовка.
Для отрезков типа d необходимо выполнять два двоичных поиска видимых точек, наиболее удалённых от концов отрезка. Для отрезков типа e необходимость в одном из двоичных поисков отпадает.
В работе алгоритма Кируса-Бека используется параметрическое представление отрезка: Ps (t)=P1+(P2-P1)*t;t∈[0;1]. Данный алгоритм позволяет выполнять отсечение не только прямоугольным окном, но и любым выпуклым многоугольником.
Рассмотрим отдельное ребро Ei отсекающего многоугольника. Ориентируем нормаль к этому ребру во внешнюю сторону отсекающего многоугольника. Также будем считать, что отсекающий многоугольник обходится против часовой стрелки. Тогда, если ребро – это вектор P(E(i1)) PEi2, то нормаль NEi будет пропорциональна (yEi2-yEi1; xEi1-xEi2).
Обозначим прямую, на которой лежит ребро через Li. Тогда область, отсекаемая прямой Li, соответствует точкам P, для которых скалярное произведение векторов (P-PEi)) и NEi больше 0 (PEi — любая точка на ребре Ei). Точка пересечения прямой, на которой лежит отрезок, с отсекающей прямой Li находится из уравнения ((Ps(t)-PEi,NEi=0. Решая это уравнение, находим t.
Для описываемого алгоритма также важно в каком направлении (внутрь окна или из него) проходит точка при движении по отрезку от P1 к P2. Это определяется знаком ((P2-P1 ),NEi. Будем обозначать такие точки пересечения как:
После того, как рассчитаны координаты t для всех возможных пересечений с прямыми Li, следует выбрать максимальную координату из потенциально входящих и минимальную из потенциально выходящих (tВхМакс;tВыхМин). Если прямая, на которой лежит отрезок P1 P2, пересекает отсекающий многоугольник, то tВхМакс<tВыхМин. В этом случае, если пересечение [t1,t2]=[tВхМакс,tВыхМин]∩[0,1] непусто, то Ps(t1) Ps(t2) и будет искомым отсечённым отрезком, в противном случае отрезок полностью лежит вне отсекаемой области.
На этих алгоритмах тема отсечения, разумеется, не заканчивается. Отдельный вопрос — алгоритмы отсечения многоугольников. Если тема будет интересна хабрасообществу, я обязательно раскрою и эту тему.
Этот пост посвящён разбору нескольких алгоритмов, направленных на одну и ту же задачу, задачу отсечения отрезков. При генерации изображений могут получаться фигуры произвольной формы и размеров. Зачастую мониторы не могут отобразить сгенерированные изображения целиком. Также иногда возникают ситуации, когда необходимо задать область изображения на экране и выводить изображения только внутри этой области. Для решения этих задач и придуманы алгоритмы отсечения.
Отсечение отрезков
Самой простой задачей отсечения является задача отсечения отрезков. Сформулируем её на конкретном примере. Будем считать, что область вывода задаётся прямоугольником ABCD. Рассмотрим пример, и в качестве отсекаемой фигуры возьмём треугольник PRQ.
Процесс отсечения должен выполняться полностью автоматически. Т.е. для отрисовки треугольника PRQ должны выполниться только команды отрисовки отрезков PQ;PP';Q' Q. При этом координаты точек P';Q' заранее не известны.
На практике возможно большое количество взаимных расположений точек отрезка и области вывода. Это разнообразие делает операцию отсечения весьма нетривиальной с алгоритмической точки зрения. Для решения этих задач созданы алгоритмы отсечения.
Алгоритм Сазерленда-Коэна
Весьма интересен алгоритм отсечения, предложенный Сазерлендом и Коэном. Суть алгоритма заключается в том, что концам отрезка присваивается четырёхбитный код: b0,b1,b2,b3. Этот четырёхбитный код содержит информацию о положении точки относительно области вывода. На практике возможны 9 комбинаций:
Поясним эти коды:
Поясним эти коды:
- b0=0, если x≥xmin;
- b0=1, если x<xmin;
- b1=0, если x≤xmax;
- b1=1, если x>xmax;
- b2=0, если y≥ymin;
- b2=1, если y<ymin;
- b3=0, если y≤ymax;
- b3=1, если y>ymax;
После того, как коды получены, возможны следующие варианты:
- Коды содержат только 0, а значит отрезок целиком лежит внутри окна и должен быть отрисован целиком;
- Коды содержат единичный бит в одной и той же позиции, а значит, отрезок лежит за пределами окна и не будет отрисован;
- Во всех остальных случаях в окне лежит только часть отрезка, и это значит, что есть необходимость в отсечении.
Первые два случая легко проверяются с помощью побитовых логических операций. Наибольший интерес представляет именно третий случай. Рассмотрим его на небольшом конкретном примере.
Если код любого из концов содержит единичный бит, то либо P1, либо P2 перемещается из-за пределов окна к одной из его границ (или к её продолжению). Т.е. точка P1 перемещается в точку R, а P2 в точку U. Для новых точек мы вновь вычисляем четырёхбитные коды. В нашем случае концы отрезка по-прежнему лежат вне окна, т.е. нам понадобится ещё одно перемещение: точка R переместиться в точку S, а точка U переместиться в точку T. Получается, что процесс отсечения является итеративным. Так как на каждом шаге уменьшается расстояние между концами отрезка, мы можем утверждать, что алгоритм сойдётся. В итоге будет получен отрезок (в нашем случае (S;T), который и надо отобразить).
Рассмотрим работу этого алгоритма на ещё одном примере.
Расположение отрезка (P1;P2) не соответствует ни условиям полной видимости, ни условиям полной невидимости, поэтому в этом случае тоже прибегнуть к операции переноса точек.
После выполненных переносов коды концов отрезка удовлетворяют второму условию, т.е. отрезок целиком не будет выводиться на экран.
Алгоритм средней точки
В алгоритме Сазерленда-Коэна поиск точки пересечения отрезка с границей окна может занять несколько итераций. Этого можно избежать, если реализовать поиск точки пересечения с помощью двоичного поиска. Эта идея была предложена Спруллом и Сазерлендом. Программная реализация этого алгоритма медленнее, чем алгоритм Сазерленда-Коэна, но аппаратная реализация быстрее, так как основные операции алгоритма весьма эффективно реализуются в аппаратуре.
Этот метод также использует четырёхбитный код, описанный выше. С помощью этих кодов легко выявляются случаи тривиальной видимости (a) и тривиальной невидимости (b). Остальные (нетривиальные) отрезки разбиваются на две равные части, и проверки выполняются для двух вновь полученных отрезков. Деление и проверки будут выполняться до тех пор, пока не будет обнаружено пересечение со стороной окна, или пока отрезок не выродится в точку. После того, как отрезок выродился, мы определяем его видимость и в зависимости от результата либо отрисовываем току, либо нет.
Рассмотрим отрезок c. Очевидно, что этот отрезок целиком лежит вне границ окна, но он не может быть отвергнут сразу. Именно поэтому мы выполняем половинные деления и исключаем некоторые части отрезка. Деление заканчивается в тот момент, когда отрезок превращается в точку. Убедившись, что полученная точка невидима, мы делаем вывод, что и весь отрезок не должен быть отрисован.
Отрезок d тоже не определяется тривиально. Его деление на две половины (точкой 3) приводит к одинаковым результатам для обеих половин. Отрезок (3;2) разбиваем пополам точкой 4. Теоретически можно уже отрисовать отрезок (3;4), но это не очень эффективно. Правильнее запомнить точку 4, как наиболее удалённую от точки 1 видимую точку, а отрезок (4;2) продолжить разбивать до пересечения с нижней границей окна. Полученная точка и будет считаться наиболее удалённой от точки 1 видимой точкой. Аналогично обрабатывается отрезок 3;1, и находится видимая точка, наиболее удалённая от точки 2. Потом между двумя этими точками и происходит отрисовка.
Для отрезков типа d необходимо выполнять два двоичных поиска видимых точек, наиболее удалённых от концов отрезка. Для отрезков типа e необходимость в одном из двоичных поисков отпадает.
Алгоритм Кируса-Бека
В работе алгоритма Кируса-Бека используется параметрическое представление отрезка: Ps (t)=P1+(P2-P1)*t;t∈[0;1]. Данный алгоритм позволяет выполнять отсечение не только прямоугольным окном, но и любым выпуклым многоугольником.
Рассмотрим отдельное ребро Ei отсекающего многоугольника. Ориентируем нормаль к этому ребру во внешнюю сторону отсекающего многоугольника. Также будем считать, что отсекающий многоугольник обходится против часовой стрелки. Тогда, если ребро – это вектор P(E(i1)) PEi2, то нормаль NEi будет пропорциональна (yEi2-yEi1; xEi1-xEi2).
Обозначим прямую, на которой лежит ребро через Li. Тогда область, отсекаемая прямой Li, соответствует точкам P, для которых скалярное произведение векторов (P-PEi)) и NEi больше 0 (PEi — любая точка на ребре Ei). Точка пересечения прямой, на которой лежит отрезок, с отсекающей прямой Li находится из уравнения ((Ps(t)-PEi,NEi=0. Решая это уравнение, находим t.
Для описываемого алгоритма также важно в каком направлении (внутрь окна или из него) проходит точка при движении по отрезку от P1 к P2. Это определяется знаком ((P2-P1 ),NEi. Будем обозначать такие точки пересечения как:
После того, как рассчитаны координаты t для всех возможных пересечений с прямыми Li, следует выбрать максимальную координату из потенциально входящих и минимальную из потенциально выходящих (tВхМакс;tВыхМин). Если прямая, на которой лежит отрезок P1 P2, пересекает отсекающий многоугольник, то tВхМакс<tВыхМин. В этом случае, если пересечение [t1,t2]=[tВхМакс,tВыхМин]∩[0,1] непусто, то Ps(t1) Ps(t2) и будет искомым отсечённым отрезком, в противном случае отрезок полностью лежит вне отсекаемой области.
На этих алгоритмах тема отсечения, разумеется, не заканчивается. Отдельный вопрос — алгоритмы отсечения многоугольников. Если тема будет интересна хабрасообществу, я обязательно раскрою и эту тему.
