Как интерполировать столкновения между событиями рисования

В последнее время я исследовал всевозможные причудливые алгоритмы обнаружения столкновений и деревья квадрантов для двумерного приложения, и мое приложение находится в той точке, где я хочу начать реализацию этих алгоритмов столкновений. Мой игровой цикл способен вычислять Δt мои кадры, и я хочу выполнить «интерполяционные» проверки столкновений между нарисованными кадрами (в отличие от метода «грубой силы»: рисовать как можно быстрее, что приводит к общему снижению производительности и качества анимации).

Итог

Каков наиболее эффективный способ реализации «интерполяционных» проверок столкновений и, кроме того, существуют ли какие-либо алгоритмы столкновений, которые могут просто учитывать Δt и скорость для выполнения интерполяции за меня?

Дополнительные размышления и информация

Я использую пересечение пикселей на изображениях после AABB в дереве квадрантов. Изображения по своей сути выражаются в виде прямоугольников, и я считаю слишком неэффективным вычислять выпуклые/вогнутые многоугольники вокруг пикселей изображения, которые соответствуют определенному порогу альфа-прозрачности, а затем выполнять какой-либо другой алгоритм, такой как уточнение портала Минковского или рекурсивные круги. Я выбираю попиксельно, несмотря на то, что это неэффективно с точки зрения скорости из-за прямоугольной ограниченной формы изображений (зная это, я уменьшаю количество проверок на пиксель, обертывая проверку проверкой столкновений AABB). В будущем я мог бы попытаться повторно оптимизировать/использовать метод, отличный от AABB, потому что мои изображения будут вращаться под разными углами.

Код игрового цикла: где update() обрабатывает догоняющие операции.

currentUpdateTime = System.nanoTime();

    while(true) {
        beginLoopTime = System.nanoTime();

        drawPanel.repaint();

        lastUpdateTime = currentUpdateTime;
        currentUpdateTime = System.nanoTime();
        update((int) ((currentUpdateTime - lastUpdateTime)/( Math.pow(10,-9) )));//1000*1000

        endLoopTime = System.nanoTime();
        deltaLoop = endLoopTime - beginLoopTime;

        if(deltaLoop <= desiredDeltaLoop) {
           try {
           /*Refer to: 'http://stackoverflow.com/questions/1036754/difference-between-wait-and-sleep'
           on differences between Thread.sleep() and wait()*/
               wait((long) ((desiredDeltaLoop - deltaLoop)/( Math.pow(10,-6) )));
           } catch(InterruptedException e) {
               e.printStackTrace(System.out);
           }
        }
    }

java algorithm game-loop collision-detection
person Bennett Yeo    schedule 03.01.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Начну с того, что это, возможно, не лучший ответ. Это техника, которую я могу придумать «с места в карьер», но я не знаю, что она используется на практике. Было сказано, что:

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

person davmac    schedule 03.01.2015
comment
Короче говоря, найдите, перекрываются ли произвольно созданные области между начальным пространством и конечным пространством. Это то, о чем я думал, но я чувствовал, что есть лучшее решение. Я думаю, что это будет работать нормально, хотя. - person Bennett Yeo; 04.01.2015
comment
@KiroYakuza находит, перекрывается ли произвольно созданная область между начальным пространством и конечным пространством - нет, это неправильно; Я не уверен, что ты понимаешь. Вы должны расширить объект в третьем измерении (времени) и посмотреть, перекрывается ли расширение 3D с расширением любых других подобных расширенных объектов. В любой момент времени объект по-прежнему занимает только свое обычное пространство. - person davmac; 05.01.2015
comment
(т. е. используйте проверку 3D-столкновений, а не проверку 2D-столкновений с расширенной областью). - person davmac; 05.01.2015
comment
Боюсь, я не совсем уверен, как использовать время в качестве третьего измерения для проверки столкновений. Любой совет? - person Bennett Yeo; 10.01.2015
comment
В трехмерном пространстве ваши координаты имеют три измерения (x, y, z) вместо двух (x, y). В вашей системе у вас есть двумерные координаты, и вы используете время (t) вместо третьей координаты (z), где x и y являются функциями от t. Таким образом, для некоторого диапазона значений t у вас есть значения x и y для каждого t, и для каждого 2D-объекта в исходном пространстве у вас теперь есть 3D-форма. Затем вы можете использовать любой метод проверки 3D-столкновений, чтобы найти перекрытия между вашими объектами. (Я заметил, что вы сейчас упоминаете вращение в вопросе - это все усложняет! Но общий принцип все еще применяется). - person davmac; 10.01.2015