25. Задача удаления невидимых линий и поверхностей. Объектное пространство, пространство изображений. - chrislvt/CG GitHub Wiki
Задача удаления невидимых линий и поверхностей является одной из наиболее сложных в машинной графике. Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер, поверхностей или объемов, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства.
Единого и наилучшего способа решения задачи нет. Возникло множество алгоритмов, многие ориентированы на специализированные приложения. Все алгоритмы включают в себя сортировку. Главная – сортировка по расстоянию от точки наблюдения до тела-поверхности-ребра-точки. Также есть сортировка по загораживанию тел друг другом. Эффективность алгоритмов в большой степени зависит от эффективности алгоритма сортировки.
Существует связь между скоростью работы алгоритма и детальностью его результата – ни один алгоритм не может достигнуть хороших показателей одновременно.
Алгоритмы делятся на:
- Работающие в объектном пространстве (мировая ск, высокая точность). Сложность ~ O(N^2)
- Работающие в пространстве изображений (ск связана с дисплеем, точность ограничена разрешающей способностью дисплея). Сложность ~ O(N*M)
N – количество объектов, M – количество пикселей. N^2<N*M, но алгоритмы, работающие в пространстве изображений могут быть эффективнее в силу свойства когерентности при растровой реализации (близко расположенные пиксели чаще обладают одинаковыми свойствами).