26. Алгоритм Робертса. Основные этапы и математические предпосылки.
Алгоритм удаления невидимых линий в объектном пространстве. Работает только с выпуклыми телами. Сортировка тел по мере их удалённости от наблюдателя. Сложность ~N2
Основные этапы
- Подготовка исходных данных
- Удаление линий, экранируемых самим телом
- Удаление линий, экранируемых другими телами
- Удаление линий пересечения тел, экранируемых самими телами, связанными отношением протыкания и другими телами
Формирование матрицы
Уравнение произвольной плоскости в трехмерном пространстве имеет вид aх + by + cz + d = 0. В матричной форме [x y z 1][P]T = 0, где [P]T = [a b c d] представляет собой плоскость. Поэтому любое выпуклое твердое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей, т. е.
Если же [S] не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают отрицательное скалярное произведение, т. е. нормали направлены наружу.
