Оптимизация анализа видимости трёхмерных элементов
Предлагаю идею оптимизации анализа видимости трёхмерных элементов, фигур, граней, линий, точек.
Идея предназначена для трёхмерных программ проектирования, конструирования, рисования, игр и т.п.
Идея использует уменьшение машиноёмкости перебора вариантов отсечением ветвей, а также перенос машиноёмкости анализа из краткосрочного сейчас в прошлое с растяжением машиноёмкости на большой период времени.
Идея предполагает использование в современных программах трассировки лучей из экрана на модель для анализа видимости (попадает луч на точку или грань или не попадает).
Суть идеи.
1) В информации о каждом элементе добавляется местная система координат.
2) Информация о положении чего-то в этой местной системе координат каждого элемента записывается как цифры 1, 2, 3... 16 по числу квадрантов пространства местной системы координат.
Идею можно совершенствовать используя вместо квадрантов более мелкие сектора, это ускорит алгоритм, но увеличит объём памяти для файла.
3) При внесении в пространство нового элемента сразу же анализируется его ближайшее окружение в радиусе устанавливаемом пользователем или авторами программы.
После этого взаимное положение каждого элемента относительно каждого другого ближайшего элемента записывается в виде этих обозначений квадрантов.
Например, есть 2 элемента. Запись в первом элементе выглядит так:
Элемент номер 1, ..., рядом в квадранте номер 2 есть элемент номер 2.
Элемент номер 2, ..., рядом в квадранте номер 7 есть элемент номер 1.
4) Дополнительные описания каждого элемента увеличат вес файла, но ценой этого уменьшится машиноёмкость анализа видимости. При этом будет привнесена некоторая погрешность модели, её искажение. % искажений можно будет регулировать радиусом (см. выше) взаимосвязи элементов.
5) Далее при повороте модели и отображении видимых элементов заново происходит следующее.
5а) Определяется центр тяжести всех элементов, направление и пирамида или параллелепипед отсечения взгляда.
5б) Определяются ближайшие к взгляду элементы.
5в) В каждом элементе считываются ближайшие элементы и их взаимное расположение.
5г) Заранее в настройках задаётся количество последующих элементов анализируемых на видимость.
5д) При расположении следующего элемента позади первого (относительно камеры) определяется какой он по счёту от первого. Этот счёт сравнивается с количеством по п. 5г.
5е) По элементам проходят волны расчётов совместной близости. При достижении счётчика последующих элементов расчёт этих волн прекращается.
5ж) Теперь определены ближайшие к камере элементы.
5з) Далее видимость элементов на экране определяется обычным образом. Но большая часть элементов из такого анализа отсекается. Отсечение позволяет уменьшить машиноёмкость в несколько раз.
Но, в таком случае, отдалённые элементы от камеры не будут отображаться.
6) Чтобы исправить эту ошибку алгоритма предлагается добавить к информации об объекте, кроме данных о взаимном расположении также и данные о группе элементов.
Например, при добавлении элемента при анализе взаимного расположения другой алгоритм делает выводы об отнесении части совместных элементов в группы.
Также такое отнесение в группы может быть задано изначально. Например, это могут быть все грани куба задаваемые пользователем единой фигурой.
Например, есть 2 элемента. Запись в первом элементе выглядит так:
Элемент номер 1, ..., рядом в квадранте номер 2 есть элемент номер 2, элемент входит в группу элементов номер 1.
Элемент номер 2, ..., рядом в квадранте номер 7 есть элемент номер 1, элемент входит в группу элементов номер 1.
Элемент номер 3, ..., рядом в квадранте номер 3 есть элемент номер 1 (но он очень далеко), элемент входит в группу элементов номер 2.
Таким образом все элементы, например, одного станка попадут в одну группу, а другого в другую.
7) Каждая такая группа элементов должна анализироваться алгоритмом из п. 5 отдельно.
Таким образом для анализа видимости будут доступны только предположительно видимые грани групп элементов. То есть при расположении, например, станков вдали друг от друга для анализа видимости будут доступны только их предположительно видимые грани.
В алгоритм можно добавить прозрачность (например окон).
Для этого надо добавить данные о прозрачности. После этого отбросить все прозрачные видимые элементы и повторить алгоритм ещё раз.
Уменьшение машиноёмкости происходит за счёт:
отнесения части расчётов на период создания каждого элемента;
отсечение большей части переборов совместного расположения элементов за счёт Количества элементов позади первого;
замены части расчётов с решения о попадании луча в грань (решение квадратного уравнения) на простой перебор цифр с анализом их совпадения типа х=у или х не = у (тут спорно, так как переборов много);
значительного уменьшения элементов для анализа отображения на экране.
Плюсы:
Быстрота отображения большой точной модели.
Минусы:
Увеличение объёма файла.
Погрешности отображения всё-таки будут. Вероятно, их можно будет уменьшить дополнительным алгоритмом.
