25. Задача удаления невидимых линий и поверхностей. Объектное пространство, пространство изображений. - p1xelse/CG GitHub Wiki

Задача удаления невидимых линий и поверхностей является одной из наиболее сложных в машинной графике. Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер, поверхностей или объемов, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства.

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

Существует связь между скоростью работы алгоритма и детальностью его результата – ни один алгоритм не может достигнуть хороших показателей одновременно.

Алгоритмы делятся на:

1. Работающие в объектном пространстве (мировая ск, высокая точность). Сложность ~ O(N^2)
2. Работающие в пространстве изображений (ск связана с дисплеем, точность ограничена разрешающей способностью дисплея). Сложность ~ O(N*M)

N – количество объектов, M – количество пикселей. N^2<N*M, но алгоритмы, работающие в пространстве изображений могут быть эффективнее в силу свойства когерентности при растровой реализации (близко расположенные пиксели чаще обладают одинаковыми свойствами).