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

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

В этой статье я расскажу:

• Что за задача такая, о которой идет речь;
• Подробнее об интегральных изображениях;
• Как использовать интегральные изображения для приближенного решения гравитационной задачи N тел применительно к дискретному полю импульсов (масс-скоростей);
• Какой недостаток имеет это решение и как его исправить;
• И, наконец, как за константное время вычислить центр масс для произвольного региона.

Для того, чтобы получить реалистичный мир внутри игры, необходимо учитывать взаимодействие различных форм рельефа между собой и с другими моделями. И если видимые линии пересечения между 3D-моделями портят органичность изображения, стоит задуматься над тем, как их устранить. Самый распространенный случай таких линий, который может быть знаком многим, — пересечение билбордов частиц с непрозрачной геометрией.



Другой пример — нарушающие естественность композиции пересечения скал и растительности с поверхностью ландшафта в сценах «на открытом воздухе».



Помимо разнообразных методов сглаживания (SSAA, MSAA, CSAA, FXAA, NFAA, CMAA, DLAA, TAA и др.), которые пусть и смягчают вызывающий внешний вид таких линий пересечений, но не исправляют ситуацию в полной мере, существуют и более действенные приемы. Их мы и рассмотрим.