Комментарии 18
А не расскажите почему в качестве AABB выбирается куб или квадрат, но не окружность описывающую фигуру?
Возможно потому, что квадрат можно быстрее и проще просчитать.
Наверное, потому, что с прямоугольником быстрее производить вычисления — с окружностью же нужно учитывать радиусы, которые, в свою очередь, ведут к использованию квадратической функции. Не исключаю, что иногда окружность удобнее — например, если объект вращается.
// предыдущий коммент меня опередил.
// предыдущий коммент меня опередил.
Я может не прав, но что бы посчитать пересекаются ли две окружности, нам нужно сложить два радиуса и сравнить с расстоянием между центрами.
Конечно. Но если, например, размер объекта динамичный — операция вычисления радиуса становится затратной.
Да, но чтобы вычислить расстояние между центрами нужны операции возведения в квадрат и извлечение корня, а они затратные.
Поэтому пересекать кубы быстрее.
Поэтому пересекать кубы быстрее.
Расстояние между центрами — число с плавающей точкой. Его вычисление вероятно дороже, чем сравнение нескольких пар целых чисел.
К тому же, если в box2d всё считается в целых числах, то и работать проще с целыми.
К тому же, если в box2d всё считается в целых числах, то и работать проще с целыми.
для вычисления расстояния придется числа в квадраты возводить или по модулю брать, а с прямоугольными областями (стороны которых параллельны осям координат) достаточно операций сравнения
Вам дали кучу ответов, но пропустили самый важный — соотношение площади описанного прямоугольника к площади фигуры почти всегда заметно меньше, чем соотношение площади описанной окружнасти к площади фигуры. Т.е. имея длинную «палку», т.е. прямоугольник с длиной намного большей его ширины, описывать его окружностью очень неудобно, в реальных случаях проверки коллизии будут выполняться слишком часто. Для сравнения представьте, что вокруг фигур тетриса описаны окружности — сколько можно таких фигур поместить в игровой «колодец», чтобы описанные окружности не пересекались? Теперь представьте, что вокруг фигур описаны AABB прямоугольники и снова ответьте на этот вопрос.
Что интересно, в «больших» 3D физических движках иногда есть смысл использовать и баундинг сферы, и баундинг боксы, но это уже отдельный разговор.
Что интересно, в «больших» 3D физических движках иногда есть смысл использовать и баундинг сферы, и баундинг боксы, но это уже отдельный разговор.
Наверно потому что параллелепипеды удобнее и быстрее считаются. У окружности на границе погрешность, поэтому супер точно определить соприкосновения не получится.
AABB (axis-aligned bounding box) — по определению прямоугольник или параллелепипед, а то, о чём вы хотели спросить, — виды ограничивающих объёмов.
Помимо вышеупомянутой простоты арифметики при расчётах, ориентированные по осям коробки проще строить, чем описанные вокруг многоугольников и многогранников окружности и сферы.
Помимо вышеупомянутой простоты арифметики при расчётах, ориентированные по осям коробки проще строить, чем описанные вокруг многоугольников и многогранников окружности и сферы.
На самом деле, что проще посчитать — пересечение ААВВ, или сфер-окружностей, вопрос спорный. Считается, что окружность — самая простая геометрия для расчёта пересечений. ААВВ чуть по-сложнее. При этом у окружности есть еще одно преимущество — её не надо пересчитывать при вращении — перемещении объекта, а ААВВ — надо. Зато ААВВ проще пересчитывать в случае деформации объектов.
И есть еще одно преимущество — обычно ААВВ имеет меньший объём по сравнению с габаритной сферой, а значит точнее аппроксимирует целевой объект и реже происходят ситуации, когда коллизия между контейнерами произошла, а между реальной геометрией — нет, что гораздо важнее, чем сомнительное преимущество в скорости расчета коллизии между самими габаритными контейнерами.
И есть еще одно преимущество — обычно ААВВ имеет меньший объём по сравнению с габаритной сферой, а значит точнее аппроксимирует целевой объект и реже происходят ситуации, когда коллизия между контейнерами произошла, а между реальной геометрией — нет, что гораздо важнее, чем сомнительное преимущество в скорости расчета коллизии между самими габаритными контейнерами.
Сферы гораздо проще и дешевле в использовании, чем баундингбоксы. Открою страшный секрет, что квадрат не обязательно извлекать для определения пересечения двух сфер.
Не совсем так. Баундингбоксы бывают разные. Есть ориентированные баундингбоксы (OBB), которые поворачиваются вместе с объектом, они действительно на порядок дороже, чем окружности. Но в статье говорится о AABB — это баундингбоксы, которые ориентированы по главным осям мировых координат. Посчитать их пересечение значительно проще, достаточно вычесть центры прямоугольников и сравнить компоненты полученного вектора с суммой полуразмеров прямоугольников. То есть, 4 операции сложения-вычитания и две операции сравнения. Для двух окружностей требуется 4 операции сложения-вычитания, две операции умножения и одно сравнение. То есть, сложности сопоставимы, но на современных процессорах с глубокими конвейерами операции сравнения могут оказаться дороже, чем операции умножения. К тому же, AABB нужно пересчитывать при каждом вращении объекта.
P.S.: в своём физическом движке мы использовали именно сферы для объектов и бинарные деревья OBB для полигональных сеток. А вот для облака точек лучше подходит окто-дерево AABB. Так что, всему своё место.
P.S.: в своём физическом движке мы использовали именно сферы для объектов и бинарные деревья OBB для полигональных сеток. А вот для облака точек лучше подходит окто-дерево AABB. Так что, всему своё место.
Операции сравнения несравненно дороже, кроме того Вы пропустили +2 операции сравнения для прямоугольников. После вычитания центров надо определить их знак. Впрочем, это все копейки.
Я (в некоторых приложениях) пересечения объектов определяю условно бесплатно — рисуя любой Image, заношу цветные пикселы в цветной растр, а индексные пикселы — в индексный растр. Каждый объект имеет свой индекс. Попали в одну точку индексного растра разные индексы? Да — значит объекты с этими индексами визуально прикоснулись.
Я (в некоторых приложениях) пересечения объектов определяю условно бесплатно — рисуя любой Image, заношу цветные пикселы в цветной растр, а индексные пикселы — в индексный растр. Каждый объект имеет свой индекс. Попали в одну точку индексного растра разные индексы? Да — значит объекты с этими индексами визуально прикоснулись.
В процессе выполнения функции Step, когда Box2D определяет, что произошел контакт, он выполняет обратный вызов определенных функций слушателя, чтобы уведомить вас.
Мне кажется, лучше не переводить это и оставить «колбек» как кальку, или же просто писать callback. Минусы к этому комменту покажут, насколько это удачная идея.
На мой вкус только gif'ок не хватает для наглядности. А так отличная статья, спасибо!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Box2d: анатомия коллизий