4.3. АЛГОРИТМ РОБЕРТСА

Алгоритм получения изображений одиночных выпуклых объектов, составленных из плоских граней, был впервые разработан Робертсом. В переводной литературе метод описан в [41] и наиболее подробно - в [49]. Алгоритм Робертса может быть с успехом применен для изображения множества выпуклых многогранников на одной сцене в виде проволочной модели с удаленными невидимыми линиями. Метод не пригоден непосредственно для передачи падающих теней и других сложных визуальных эффектов. Рассмотрим основные идеи метода на примере одиночного выпуклого многогранника.

4.3.1. МОДЕЛЬ ОБЪЕКТА

Объект - многогранник, состоящий из  граней, описывается матрицей  размера , каждый -й столбец которой содержит описание -й  плоскости  в объектной системе координат :

.

Минимальное число граней  наблюдается у тетраэдра.

Важное требование к модели объекта в алгоритме Робертса заключается в достижении такой формы (знака) в функции каждой плоскости , при которой справедливо  для любой точки , заведомо принадлежащей телу многогранника. Достижение этого условия осуществляется путем опытной проверки знака функции относительно внутренней точки, в качестве которой может выступать точка со средним геометрическим положением относительно всех вершин многогранника. Формально правило формирования "положительной" грани может быть представлено в виде , где  - функция, описывающая -ю грань с априори неизвестным знаком относительно внутренней точки;  - та же функция, но с положительным значением. При достижении "положительности" всех граней автоматически достигается ориентация нормали  к любой из граней внутрь фигуры.

Кроме параметров уравнений граней необходимо знать координаты вершин каждой грани. Вершины могут быть заданы или вычислены из матрицы  путем определения общих решений каждой плоскости со всеми остальными. В любом случае для каждой -й грани должна быть составлена матрица  - числа вершин:

.