Физика на растровых картах

---

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

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

Черновой вариант такого обработчика карт был сделан достаточно быстро, в качестве хранилища результата сначала был использован класс BitmapData, который позже был заменён на ByteArray. Алгоритм незамысловат и не оптимизирован, прозрачность каждого пикселя сверяется с пороговым значением, чтобы определить материален он или нет. Далее по окружности с постепенно увеличивающимся радиусом ищется пиксель с противоположным значением (т.е. если центральный материален, то ищется ближайший не материальный). Когда такой пиксель находится, то радиус полученной окружности считается расстоянием для него, а угол расчитывается. Если такой пиксель был найден сразу же рядом, то центральный пиксель считается частью поверхности с расстоянием 0 и для него считается угол нормали. Само собой, даже при расчёте небольших карт время "рендера" было довольно велико, поэтому для увеличения производительности для расчёта каждого пикселя используются уже готовые данные соседнего. Правда расчёт в итоге всё равно долгий, пример на моём амд64 3700+ 2.2 ГГц считается 6.5 секунд.

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

Подозреваю, что подобные методы существуют уже давно, хотелось бы узнать про них по-больше, просто подискутировать на эту тему или рассмотреть недостатки данного примера.

Флэшку я залил себе на юкоз для тех, кому лень качать отсюда и распаковывать. Там просто ждём пока будет 100% и водим по картинке мышкой.

Вложения

angleCalculator.rar (185.5 Кб, 188 просмотров)