Обновлять приходится на каждом шаге, но вычисление интегрального изображения — это самый простой этап по абсолютным вычислительным затратам. Вообще, целиком алгоритм эволюции поля примерно такой: 1) вычисление интегрального изображения масс O(N), 2) вычисление сил — O(NlogN), 3) решение дифференциальных уравнений движения O(N) и 4) перераспределение масс O(N). Здесь N = X*Y — Общее количество дискретных элементов в поле.
Вычисление интегрального изображения — это просто суммирование по строкам, транспонирование, еще одно суммирование по строкам и еще одно транспонирование.
Решение дифференциальных уравнений — это алгоритм RK4, и в абсолютном отношении оно примерно вчетверо сложнее вычисления интегрального изображения.
Спасибо! Попробую сгенерировать иллюстрацию со строгим решением, хотя не уверен, что GPU это решение осилит. Может быть для поля небольшого размера и получится.
Верно, cumulative distribution function. На второй вопрос я к сожалению не смогу ответить, моя математическая подготовка будет несколько пониже уровнем :(
В любом случае, Fast Multipole Method никакая моя реализация не побьет :) Но в отличие от FFT, которая решает только задачу N тел и более ничего, у интегральных изображений потенциал все же больше.
Любопытно. Но у меня как правило получается изображение со сравнительно однородным распределением и несколькими областями-экстремумами, значения которых отличаются на несколько порядков в большую сторону.
Наверное, мне просто нравится интуитивно понятный алгоритм, который превращает сложность O(M*N) в O(1), и вероятно может быть адаптирован для многих вычислительных задач, где нужно складывать и умножать по регионам.
И да и нет. Для двоичного поиска тоже нужно отсортировать массив. А это O(NlogN) в лучшем случае. Но двоичный поиск при этом остается O(logN), не так ли?
Вычисление интегрального изображения — это просто суммирование по строкам, транспонирование, еще одно суммирование по строкам и еще одно транспонирование.
Решение дифференциальных уравнений — это алгоритм RK4, и в абсолютном отношении оно примерно вчетверо сложнее вычисления интегрального изображения.
i.gyazo.com/ebc4692a9eef443a02c78f9ff39664f0.mp4
i.gyazo.com/4aaad521d738cca3313e49c81f369837.mp4
i.gyazo.com/2c1a400b6d7d06f37234a95197b587fc.mp4
i.gyazo.com/d696338b5ded31ad627bc348309fa2ef.mp4