17. Удаление невидимых линий и поверхностей

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

В объектном пространстве первый этап – удаление граней, ребер закрываемых самим телом.Второй этап – проверка видимых ребер на закрытие другими телами.Вычислительная трудоемкостьn²(количество объектов в сцепе).Условие алгоритма– все тела выпуклые.p= [abcd] - плоскость

a

b

ax + by + cz + d = 0 [ x y z₁ ] c = 0 или [ x y z₁ ] [ p ]^T = 0

d

a₁ . . . a_n

b₁ b_n

V = c₁ c_n матрица тела [ S ] = [ x y z₁ ]

d₁ d_n

>

[s] [p]^T= 0 по какую сторону от плоскости

<

В алгоритме Робертсапредполагается, что точки внутри дают > 0.

Чтобы этого добиться нужны коррективные уравнения.

АЛГОРИТМ ВАРНОКА (удаление невидимых поверхностей)

Рассматривается сцена, состоящая из многоугольников (полигонов). Требуется определить только видимые части полигонов. По взаимному положению полигонов и окна (экрана) можно выделить следующие типы полигонов:

a) внешний б) внутренний в) пересекающий г) охватывающий