Методическое пособие по курсу "Интерактивные графические системы". Найханов В.В - 35 стр.

                       3.2.2 Алгоритм Робертса

      Самым первым алгоритмом, предназначенным для удаления
невидимых линий, был алгоритм Робертса, требующий, чтобы каждая грань
была выпуклым многогранником.
      Опишем этот алгоритм.
      Сначала отбрасываются все ребра, обе определяющие грани которого
являются нелицевыми (ни одно из таких ребер не будет видно).
      Следующим шагом является проверка каждого из оставшихся ребер
со всеми гранями многогранника на закрытие. Возможны следующие
случаи:
      • грань не закрывает ребро;
      • грань полностью закрывает ребро (и оно тогда удаляется из списка
        рассматриваемых ребер);
      • грань частично закрывает ребро (в этом случае ребро разбивается
        на несколько частей, из которых видимыми являются не более двух;
        само ребро удаляется из списка, но в этот список проверенных
        ребер добавляются те его части, которые не закрываются данной
        гранью).
      Если общее количество граней равно n, то временные затраты для
данного алгоритма составляют О (n2).
      Можно заметно сократить количество проверок, если воспользоваться
разбиением картинной плоскости.
      Картинная плоскость разбивается на равные клетки, и для каждой
клетки составляется список тех граней, проекции которых имеют непустое
пересечение с данной клеткой. Для проверки произвольного ребра сначала
находятся все клетки, в которые попадает проекция этого ребра, и
рассматриваются только те грани, которые содержатся в списках данных
клеток.
      Несмотря на то, что этот вариант алгоритма требует определенных
затрат для построения разбиения и соответствующих списков, при удачном
выборе разбиения он имеет порядок О (n).


                         3.2.3 Алгоритм Аппеля

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