Опорный конспект лекций по дисциплине Вычислительная геометрия и компьютерная графика (стр. 4 )

Пример - Обобщенный алгоритм Брезенхема

Для иллюстрации общего алгоритма Брезенхема рассмотрим отрезок из точки (0,0) в точку (-8, -4):
x1 = 0
у1 = 0
х2 = 8
y2 = 4
s1 = -1
s2 = -1
Обмен = 0
ē = 0
Результаты пошагового исполнения основного цикла:

i 1 2 3 4 5 6 7 8

Plot (0, 0) (-1, -1) (-2, -1) (-3, -2) (-4, -2) (-5, -3) (-6, -3) (-7, -4)

ē 0 -16 -8 0 -16 -8 0 -16 -8 0 -16 -8 0

x 0 0 -1 -2 -2 -3 -4 -4 -5 -6 -6 -7 -8

y 0 -1 -1 -1 -2 -2 -2 -3 -3 -3 -4 -4 -4

На рис. 2.5 продемонстрирован результат.

5.2Алгоритм Брезенхема построения окружности.

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

Любая геометрическая фигура может быть определена как некоторое множество точек плоскости. В геометрии это множество, как правило, бесконечно; даже отрезок содержит бесконечно много точек.

В компьютерной графике дело обстоит иначе. Элементарная составляющая всех фигур - точка - обретает реальные физические размеры, а вопросы вида "сколько точек содержит данная фигура?" никого не удивляют. Мы попадаем в конечный мир, где все можно сравнить, измерить, подсчитать. Даже само слово "точка" употребляется редко. Его заменяет термин пиксель (pixel - от picture element - элемент картинки). Если взглянуть на экран дисплея сквозь увеличительное стекло, то можно увидеть, что фрагмент изображения, который невооруженному глазу кажется сплошным, на самом деле состоит из дискретного множества пикселей. Впрочем, на дисплеях с невысокой разрешающей способностью это можно наблюдать и без увеличительного стекла.

Пиксель нельзя разделить, так как он является минимальным элементом изображения - не бывает "двух с половиной пикселей". Таким образом, в компьютерной графике мы фактически располагаем целочисленной координатной сеткой, в узлах которой ставятся точки. Во всех алгоритмах, обслуживающих компьютерную графику, должно быть учтено это обстоятельство.

Имеется и другой аспект проблемы. Допустим, вы хотите съесть яблоко. Имеет ли для вас значение, съедите вы все яблоко целиком или разделите его на 2 половинки и съедите каждую из них отдельно? Скорее всего, если яблоко достаточно вкусное, вы охотно согласитесь на оба варианта. А вот с точки зрения программиста, поделив прекрасное целое яблоко пополам, вы совершаете огромную ошибку. Ведь вместо замечательного целого числа вам приходится иметь дело с двумя дробными, а это значительно хуже. По той же самой причине из двух равенств 1+1=2 и 1,5+0,5=2 программист всегда выберет первое - ведь в нем нет этих непрятных дробных чисел. Такой выбор связан с соображениями повышения эффективности работы программ. В нашем случае, когда речь идет об алгоритмах построения элементарных графических объектов, которые предполагают многократное применение, эффективность является обязательным требованием. Большинство микропроцессоров имеет лишь средства целочисленной арифметики и не располагает встроенными возможностями для операций над вещественными числами. Безусловно, такие операции реализуются, но при этом бывает, что одна операция требует выполнения компьютером до десятка и более команд, что существенным образом влияет на время выполнения алгоритмов.

Статья посвящена рассмотрению одного из шедевров искусства программирования - алгоритму построения окружности, предложенному Брезенхемом (Brezenham). Требуется разработать метод построения окружности на целочисленной координатной сетке по координатам центра и радиусу. Мы должны также максимально сократить время выполнения алгоритма, что заставляет оперировать по возможности целыми числами. Каким графическим инструментарием мы располагаем? Практически никаким. Безусловно, мы должны уметь ставить точку (pixel) в нужном месте экрана. К примеру, языки программирования фирмы Borland содержат процедуру putpixel, с помощью которой можно оставить на экране точку, имеющую нужные координаты и цвет. Цвет для нас значения не имеет, для определенности пусть он будет белым.

Представим себе, что мы не ограничены в средствах. Что мы не только можем оперировать с дробными числами, но и использовать трансцендентные тригонометрические функции (такое, кстати, вполне возможно на машинах, оснащенных математическим сопроцессором, который берет на себя подобные вычисления). Задача все та же - построить окружность. Что мы станем делать? Вероятно, мы вспомним формулы, параметрически определяющие окружность. Эти формулы достаточно просты и могут быть получены непосредственно из определения тригонометрических функций. Согласно им окружность радиуса R с центром в точке (x0, y0) может быть определена как множество точек M(x, y), координаты которых удовлетворяют системе уравнений

x = x0 + R cos a y = y0 + R sin a, где a Î [0;2p).

Составить программу, реализующую построение окружности по приведенным формулам, совсем не сложно. Мы приведем такую программу на Паскале. При этом воспользуемся процедурами moveto и lineto, первая из которых устанавливает графический курсор на место с указанными координатами, а вторая - проводит линию от текущего положения курсора до точки, координаты которой являются ее параметрами. Использование этих процедур, безусловно, является еще одним отступлением от сформулированных нами правил, но ведь мы уже и так отошли от них, воспользовавшись тригонометрическими функциями.

procedure my_circle(x, y,r:integer);

var alfa: integer;

begin

moveto(x+r, y);

for alfa:=1 to 360 do

{ угол измерятся в градусах }

lineto(round(x+r*cos(alfa*pi/360)), round(y+r*sin(alfa*pi/360)))

{ здесь используется радианная мера углов }

end;

Если вы располагаете временем и достаточно любопытны, то можете попробовать определить время, которое потребуется для изображения, к примеру, тысячи произвольных окружностей с помощью нашей процедуры, и сохранить его с временем, которое понадобится на то же самое с использованием стандартной процедуры circle. Не сомневаемся, что полученные результаты убедят вас в правильности названия этого параграфа. Кроме всего прочего, необходимо сделать следующее замечание: на самом деле мы строим не окружность, а правильный 360-угольник. Весьма вероятно, что в недалеком будущем аппаратные средства позволят добиться такой разрешающей способности дисплеев, что отличие многоугольника от окружности станет заметным на глаз. Что мы станем делать тогда? Уменьшим шаг приращения угла? Это неплохой выход, но такая ситуация обещает повториться. Итак, приведенный алгоритм нас не устраивает. Надо поискать что-нибудь свободное от упомянутых недостатков.

Математики любят удивлять. Загадайте... умножьте... разделите... сложите... теперь забудьте то, что вы задумали, и назовите первое число, которое вам придет в голову... Вы задумали... Это, конечно, развлечение. Но и настоящая, серьезная математика способна преподносить не менее удивительные сюрпризы. Алгоритм Брезенхема является одним из таких сюрпризов. Ниже приведена реализация этого алгоритма на Паскале. Изучите ее. Убедитесь, что программа действительно работает. Удивитесь, ибо ничего другого вам не остается. В следующем параграфе вас ждет увлекательный разбор алгоритма.

procedure bres_circle(xc, yc, r:interger):

var x, y,d:integer:

procedure sim(x, y;integer);

begin

putpixel(x+xc, y+yc, White);

putpixel(x+xc,-y+yc, White);

putpixel(-x+xc,-y+yc, White);

putpixel(-x+xc, y+yc, White);

putpixel(y+xc, x+yc, White);

putpixel(y+xc,-x+yc, White);

putpixel(-y+xc,-x+yc, White);

putpixel(-y+xc, x+yc, White);

end;

begin

d:=3-2*y;

x:=0;

y:=r;

while(x <= y) do

begin

sim(x, y);

if d<0 then d:=d+4*x+6

else begin

d:=d+4*(x-y)+10;

dec(y)

end;

inc(x)

end;

end;

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

Обратимся к тексту процедуры bres_circle. Она использует процедуру sim, которая, как можно видеть, расставляет восемь точек вокруг точки (xc,yc) (центра нашей окружности). Эта процедура реализует следующее: окружность обладает центром симметрии и бесконечным количеством осей симметрии. Поэтому нет необходимости строить всю окружность, достаточно построить некоторую ее часть и последовательным применением преобразований симметрии получить из нее полную окружность. Мы станем строить 1/8 часть окружности, заключенную в ÐAOB (рис. 1).

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

Рис. 1

Кроме того, именно процедура sim отвечает за расположение центра окружности. Главная процедура вполне может считать, что она строит окружность с центром в начале координат.

Приступим к разбору ключевой идеи алгоритма. Пусть мы находимся в некоторой промежуточной фазе построения. Мы только что поставили точку (xi, yi) и теперь должны сделать выбор между точками 1(xi+1, yi-1) и 2(xi+1, y) (рис. 2). (Напомним, что мы строим часть окружности, заключенную в ÐAOB, следовательно, подняться выше мы не можем и спуститься вниз более чем на одну точку не можем тоже.)

Рис. 2

Реальная окружность может быть расположена относительно точек 1 и 2 одним из пяти способов 1-5. Если мы выбераем точку 1, то тем самым говорим, что (xi+1)2+(yi-1)2 » R2. Если же выбераем точку 2, то допускаем, что (xi+1)2+(yi)2 » R2. Рассмотрим две погрешности Di1 и Di2:

Di1 = (xi+1)2+(yi-1)2-R2

Di2 = (x1+1)2+(yi)2-R2

и контрольную величинуDi = Di1+Di2. При выборе точки, следующей за (xi, yi), станем руководствоваться следующим критерием:

если Di > 0, выберем точку 1;

если Di £ 0, выберем точку 2.

Обоснуем разумность такого выбора. Рассмотрим знаки погрешностей Di1 и Di2 и их влияние на знак контрольной величины Di для всех пяти возможных положений окружности.

Для положения 1.

Di1 < 0, Di2 < 0 Þ Di1+Di2 < 0 Þ выбирается 2.

Для положения 2.

Di1 < 0, Di2 = 0 Þ Di1+Di2 < 0 Þ выбирается 2.

Для положения 3 возможны варианты (учитывая, что Di1 < 0, Di2 > 0).

Вариант 3.1. |Di1| ³ |Di2| Þ Di1+Di2 < 0 Þ выбирается 2.

Вариант 3.2. |Di1| < |Di2| ÞDi1+Di2 > 0 Þ выбирается 1.

Для положения 4.

Di1 = 0, Di2 > 0 Þ Di1+Di2 > 0 Þ выбирается 1.

Для положения 5.

Di1 > 0, Di2 > 0 Þ Di1+Di2 > 0 Þ выбирается 1.

Далее получим выражение для контрольной величины Di

Di = Di1+Di2 = (xi+1)2+(yi-1)2-R2+(xi+1)2+(yi)2-R2 = 2xi2+2yi2+4xi-2yi+3-2R2.

Выражение для Di+1 существенным образом зависит от выбора следующей точки. Необходимо рассмотреть два случая: yi+1 = yi и yi+1 = yi-1.

Di+1 [при yi+1 = yi] = 2x2i+1+2y2i+1+4xi+1-2yi+1+3-2R2 = 2(xi+1)2+2yi2+4(xi+1)-2yi+3-2R2 = Di+4xi+6.

Di+1 [при yi+1 = yi-1] = 2x2i+1+2y2i+1+4xi+1-2yi+1+3-2R2 = 2(xi+1)2+2(yi-1)2+4(xi+1)-2(yi-1)+3-2R2 = Di+4(xi-yi)+10.

Теперь, когда получено рекуррентное выражение для Di+1 через Di, остается получить D1 (контрольную величину в начальной точке.) Она не может быть получена рекуррентно, ибо не определено предшествующее значение, зато легко может быть найдена непосредственно

x1 = 0, y1 = R Þ D11 = (0+1)2+(R-1)2-R2 = 2-2R,

D12 = (0+1)2+R2-R2 = 1

D1 = D11+D12 = 3-2R.

Таким образом, алгоритм построения окружности, реализованный в bres_circle, основан на последовательном выборе точек; в зависимости от знака контрольной величины Di выбирается следующая точка и нужным образом изменяется сама контрольная величина. Процесс начинается в точке (0, r), а первая точка, которую ставит процедура sim, имеет координаты (xc, yc+r). При x = y процесс заканчивается.

Тема 6 Двумерное отсечение

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

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

Поскольку в обычных сценах или картинках необходимо отсекать большое число отрезков или точек, то эффективность алгоритмов отсечения представляет особый интерес. Во многих случаях подавляющее большинство точек или отрезков лежит целиком внутри или вне отсекающего окна. Поэтому важно уметь быстро отбирать отрезки, подобные ab, или точки, подобные р, и отбрасывать отрезки, подобные ij, или точки, подобные q на рис. 3.1.

Точки, лежащие внутри отсекающего окна, удовлетворяют условию: xл <= х <= xп, yн <= y <= yв. Знак равенства здесь показывает, что точки, лежащие на границе окна, считаются находящимися внутри него.

Отрезок лежит внутри окна и, следовательно, является видимым, если обе его концевые точки лежат внутри окна, например отрезок ab на рис. 3.1. Однако если оба конца отрезка лежат вне окна, то этот отрезок не обязательно лежит целиком вне окна, например отрезок gh на рис. 3.1. Если же оба конца отрезка лежат справа, слева, выше или ниже окна, то этот отрезок целиком лежит вне окна, а значит, невидим. Проверка последнего условия устранит все отрезки, помеченные ij на рис. 3.1. Но она не устранит ни отрезка gh, который видим частично, ни отрезка kl, который целиком невидим.

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

Простой алгоритм определения видимости
a, b - концевые точки отрезка в координатном пространстве (х, у)

для каждого отрезка проверить полную видимость отрезка если одна из координат какого-нибудь конца отрезка находится вне окна, то отрезок не является полностью видимым if хa < хл оr хa > хп then 1 if хb < хл оr хb > хп then 1 if ya < yн оr ya > yв then 1 if yb < yн оr yb > yв then 1 отрезок полностью видимый визуализировать отрезок go to 3 проверить полную невидимость отрезка если оба конца отрезка лежат слева, справа, сверху или снизу от окна, то факт невидимости отрезка тривиален

1. if хa < хл and хb < хл then 2 if хa > хп and хb > хп then 2 if ya > yв and yb > yв then 2 if ya < yн and yb < yн then 2 отрезок частично видим или пересекает продолжение диагонали, оставаясь невидимым определить пересечения отрезка с окном

2. отрезок невидим

3. переход к следующему отрезку

Пересечение двух отрезков можно искать как параметрическим, так и непараметрическим способами. Очевидно, что уравнение бесконечной прямой, проходящей через точки Р1(х1, y1) и Р2(х2,y2), имеет вид y = m(х - х2) + y2 или у = m(х - х2) + у2, где m = (y2 - y1)/ (х2 - х1) - это наклон данной прямой. Точки пересечения этой прямой со сторонами окна имеют следующие координаты:

с левой: хл, y = m(хл - х1) + y1 m <> бесконечность

с правой: хп, y = m(хп - х1) + y1 m <> бесконечность

с верхней: yв, х = х1 + (1/m)(yв - y1) m <> 0 m <> 0

с нижней: yн, х = х1 + (1/m)(yн - у1)

Чтобы разработать схему эффективного алгоритма отсечения, необходимо сначала рассмотреть несколько частных случаев. Если наклон отрезка бесконечен, то отрезок параллелен левой и правой сторонам окна и надо искать его пересечения только с верхней и нижней сторонами. Аналогично, если наклон равен нулю, то отрезок параллелен верхней и нижней сторонам окна, а искать его пересечения надо только с левой и правой сторонами.

6.1Основные алгоритмы двумерного отсечения и их идеи

Алгоритмов двумерного отсечения огромное количество. Кратко рассмотрим некоторые из них:

6.2Простой алгоритм двумерного отсечения

В этом алгоритме отрезок отсекается поочередно каждой из сторон окна, а для полученных точек пересечения проверяется их принадлежность внутренней области окна, т. е. корректность пересечения. Эта процедура применяется сначала к исходному отрезку Р1Р2 и получается отрезок Р1'Р2, а затем к отрезку Р1'Р2 и получается результирующий отрезок Р1'Р2'.
1. Вычисление кодов концевых точек отрезка.
2. Занесение этих кодов в 2 массива, размерностью 1х4 каждый.
3. Проверка полной видимости отрезка. Если отрезок полностью видим goto 13.
4. Проверка тривиальной невидимости отрезка. Если отрезок полностью невидим goto 13.
5. Отрезок может быть частично видим. Проверяется попадание концевых точек отрезка внутрь окна. Если концевые точки внутри окна есть, goto 8.
6. Внутри окна нет концов отрезка.
7. Инициализация номера конца отрезка. Если обработано оба конца отрезка, goto 13.
8. Проверяется вертикальность отрезка. Если отрезкок вертикален, goto 11.
9. Ищутся точки пересечения отрезка с левым и правым краями окна. Если пересечение обнаружено, goto 7.
10. Проверяется горизонтальность отрезка. Если отрезок горизонтален, goto 7.
11. Проверяется пересечение отрезка с верхним и нижним краями окна. Если пересечение обнаружено, goto 7.
12. Если пересечений не обнаружено, то отрезок невидим.
13. Завершение работы и вызов процедуры черчения.
14. Перейти к обработке следующего отрезка.

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

Пример - Простое двумерное отсечение.

Рассмотрим отсекающее окно и отрезки, изображенные на рис. 3.2.

Наклон отрезка от Р1(- 3/2,1/6) до Р2(1/2,3/2) равен m = (y2 - y1) / (x2 - x1) = (3/2 - 1/6) / [1//2)] = 2/3. Его пересечения со сторонами окна таковы:
с левой: х = -1   y = (2/3)[-/2)] + 1/6 = 1/2
с правой: х = 1   y = (2/3)[/2)] + 1/6 = 11/6
(последнее число больше, чем yв, и поэтому отвергается)
с верхней: y = 1   x = -3/2 + (3/2)[1 - 1/6] = -1/4
c нижней: y = -1   х = -3/2 + (3/2)|-1 - 1/6] = -13/4
(последнee число меньше, чем хп, и поэтому отвергается)
Аналогично, отрезок от Р3(-3/2,-1) до Р4(3/2,2) имеет

и пересечения:
с левой: х = -1   y = (1)[-/2)] + (-1) = -1/2
с правой: х = 1   y = (1)[/2)] + (-1) = 3/2
(последнее число больше, чем yв, и поэтому отвергается)
с верхней: y = 1   x = -3/2 + (1)[] = 1/2
c нижней: y = -1   х = -3/2 + (1)|-] = -3/2
(последнee число меньше, чем хл, и поэтому отвергается)

6.3Алгоритм отсечения Сазерленда-Коэна.

В алгоритме Сазерленда-Коэна отрезок тоже разбивается сторонами окна. Отличие состоит в том, что здесь не производится проверки попадания точки пересечения внутрь окна, вместо этого каждая из пары получающихся частей отрезка сохраняется или отбрасывается в результате анализа кодов ее концевых точек. Для определения той из девяти областей, которой принадлежит конец ребра, вводится четырехразрядный (битовый) код. Крайний правый бит кода считается первым. В соответствующий бит заносится 1 при выполнении следующих условий:
для первого бита - если точка левее окна
для второго бита - если точка правее окна
для третьего бита - если точка ниже окна
для четвертого бита - если точка выше окна
В противном случае в бит заносится нуль.
Ключом к алгоритму Сазерленда-Коэна является информация о том, что одна из концевых точек отрезка лежит вне окна. Поэтому тот отрезок, который заключен между этой точкой и точкой пересечения, можно отвергнуть как невидимый. Фактически это означает замену исходной концевой точки на точку пересечения. В содержательных понятиях алгоритм Сазерленда - Коэна формулируется следующим образом:
Для каждой стороны окна выполнить:
1. Для каждого отрезка Р1P2 определить, не является ли он полностью видимым или может быть тривиально отвергнут как невидимый.
2. Если Р1 вне окна, то продолжить выполнение, иначе поменять Р1 и Р2 местами.
3. Заменить Р1 на точку пересечения Р1Р2 со стороной окна.
Этот алгоритм иллюстрирует следующий пример.

Пример - Алгоритм отсечения Саэерленда-Коэна.

Рассмотрим вновь отсечение отрезка Р1Р2 окном, показанным на рис. 3.2. Коды концевых точек Р1(- 3/2,1/6) и Р2(1/2,3/2) равны (0001) и (1000) соответственно. Этот отрезок не является ни полностью видимым, ни тривиально невидимым. Отрезок пересекает левую сторону окна. Р1 - вне окна.
Пересечение с левой стороной (х = -1) окна происходит в точке Р1'(-1,1/2). Замена Р1 на Р1' дает новый отрезок от Р1 (-1,1/2) до Р2(1/2,3/2).
Коды концевых точек Р1 и Р2 теперь стали (0000) и (1000) соответственно. Отрезок не является ни полностью видимым, ни тривиально невидимым.
Отрезок не пересекается с правой стороной окна. Перейти к нижней стороне.
Коды концевых точек Р1 и Р2 остаются по-прежнему равными (0000) в (1000) соотвественно. Отрезок не является ни полностью видимым, ни тривиально невидимым.
Отрезок не пересекается с нижней стороной окна. Перейти к верхней стороне.
Коды концевых точек Р1 и Р2 остаются равными (0000) и (1000) соответственно. Отрезок не является ни полностью видимым, ни тривиально невидимым.
Отрезок пересекается с верхней стороной окна. Р1 - не снаружи окна. Поменяв Р1 и Р2 местами, мы получим новый отрезок от Р1(1/2,3/2) до P2(-1,1/2).
Точка пересечення отрезка с верхней стороной окна (y = 1) равна Р1'(-1/4,1). Заменив Р1 на P1', получаем новый отрезок от Р1(-1/4,1) до P2(-1,1/2).
Теперь коды концевых точек Р1 и Р2 равны (0000) и (0000) соответственно. Oтрезок полностью видим. Процедура завершена.
Начертить отрезок.

6.4Алгоритм разбиения средней точкой.

В предыдущем алгоритме требовалось вычислить пересечение отрезка со стороной окна. Можно избежать непосредственного вычисления, если реализовать двоичный поиск такого пересечения путем деления отрезка его средней точкой. Программная реализация этого алгоритма медленнее, чем реализация предыдущего алгоритма. Аппаратная же реализация быстрее и эффективнее, поскольку аппаратные сложения и деления на 2 очень быстры. Деление на 2 аппаратно эквивалентно сдвигу каждого бита вправо.

В алгоритме используются коды концевых точек отрезка и проверки, выявляющие полную видимость и тривиальную невидимость отрезков. Те отрезки, которые только с помощью таких простых проверок нельзя отнести к одной из двух категорий, разбиваются на две равные части. Затем те же проверки применяются к каждой из половин до тех пор, пока не будет обнаружено пересечение со стороной окна или длина разделяемого отрезка не станет пренебрежимо малой, т. е. пока он не выродится в точку. После вырождения определяется видимость полученной точки. В результате процесс обнаружения пересечения сводится к двоичному поиску. Максимальное число разбиений пропорционально точности задания координат концевых точек отрезка.