25. Задача удаления невидимых линий и поверхностей. Ее значение в машинной графике. Классификация алгоритмов по способу выбора системы координат (объектное пространство, пространство изображений).

Задача удаления невидимых линий и поверхностей

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

• В компьютерной графике нет единого алгоритма для решения этой задачи. Поэтому, существует куча алгоритмов для разных областей.
• Существует тесная взаимосвязь между скоростью работы алгоритма и детальностью его результата. Ни один из алгоритмов не может достигнуть хороших оценок в обоих показателях.
• Все алгоритмы удаления невидимых линей включают в себя сортировку.

Про сортировки

Главная сортировка (первая) ведется по гоеометрическому расстоянию от тела, поверхности, ребра или точки до точки наблюдения.

Основная идея этой сортировки, заключается в том, что чем дальше расположен объект от точки наблюдения, тем больше вероятность, что он будет полностью или частично заслонен одним из объектов, более близких к точке наблюдения.

Сортировка по горизонтали и вертикали (выполнятеся после главной) - нужна чтобы выяснить, будет ли рассматриваемый объект действительно заслонен объектом, расположенным ближе к точке наблюдения.

Классификация алгоритмов

Алгоритмы можно классифицировать по:

• способу выбора системы координат
• пространства, в котором они работают

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

ГРУБАЯ ОЦЕНКА СЛОЖНОСТИ: O(N^2). N - число объектов.

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

ГРУБАЯ ОЦЕНКА СЛОЖНОСТИ: O(nN), N - число объектов, n - число пикселей.

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

Когерентность сцены - тенденция неизменяемости характеристик сцены в целом.

Следующий вопрос: 26. Алгоритм Робертса. Основные этапы и математические основы каждого этапа.

Предыдущий вопрос: 24. Алгоритм плавающего горизонта.