Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 45
Просто шикарно! Огромное спасибо. Недавно как раз была задача ускорить работу самого тормознутого алгоритма из вышеприведенных. Сделал что-то похожее на Sweep & Prune, а теперь все стало на свои места! Пошел переписывать правильно. Спасибо!
Я так понимаю это навеяно вот этим^
www.gamedev.net/blog/1350/entry-2253939-intelligent-2d-collision-and-pixel-perfect-precision/
или просто совпадение, но в любом случае почитать было интересно и познавательно.
Только и тут (и в той статье к слову тоже), лично мне не понравилось, что не хватает самого интересного: как использовать KD-tree для таких задач.
www.gamedev.net/blog/1350/entry-2253939-intelligent-2d-collision-and-pixel-perfect-precision/
или просто совпадение, но в любом случае почитать было интересно и познавательно.
Только и тут (и в той статье к слову тоже), лично мне не понравилось, что не хватает самого интересного: как использовать KD-tree для таких задач.
Эту статью вижу первый раз.
KD-tree далеко не самый лучший вариант для collision detection, у них немного другая область применения. Их хорошо использовать, например, для поиска в пространстве или при рендеринге.
KD-tree далеко не самый лучший вариант для collision detection, у них немного другая область применения. Их хорошо использовать, например, для поиска в пространстве или при рендеринге.
Зависит от масштаба. Если размер частиц большой и клеток регулярной сетки получается немного, то сетка лучше. Если же частицы маленькие, распределены неравномерно, а область пространства большая — то я бы строил дерево. Конечно, алгоритмы там будут посложнее (рекурсивно спускаться, отслеживая 4 соседних ветки, а когда дошли до размера одной из частиц — полностью просматривать все оставшиеся ветки). И перемещать частицу из одной ячейки в другую совсем непросто. Но при малой плотности может быть выигрыш — и по времени, и по памяти.
Мне кажется наоборот будет проигрыш, как по памяти, так и по времени работы алгоритма, причем на большем количестве частиц это будет сильнее заметно. Ведь это можно легко проверить опираясь на сложность алгоритмов.
Сложность работы по сетке — не меньше O(N+M), где N — число частиц, а M — число ячеек сетки. Ведь их надо просмотреть… Конечно, можно просматривать только частицы, а ячейки вычислять по ним — тогда скорость будет O(N), но память все равно O(N+M). В случае дерева сложность будет порядка O(N*log(M)), где log(M) — глубина дерева, а память — O(N), если мы будем останавливать рост дерева когда в ветке останется одна точка. Если M много больше N, то дерево предпочтительнее.
На сколько я знаю (хотя возможно ошибаюсь), большинство физических движков для поиска столкновений (особенно со статик геометрией) используют деревья.
Например farseer: farseerphysics.codeplex.com/SourceControl/changeset/view/94324#1436486
Например farseer: farseerphysics.codeplex.com/SourceControl/changeset/view/94324#1436486
Думаю для Collision detection частиц регулярная сеть будет быстрее чем проверка пересечения с узлами Kd-tree. Но это скорее связано именно с частицами и 2d. В 3d для поиска коллизий между полигональными объектами подойдет KD-tree для быстрого отсечения потенциально невозможных объектов взаимодействия
спасибо, интересно было почитать, алгоритмами надо заниматься!
Делал на основе регулярной сети, только со своими оптимизациями, сторона ячейки сети имеет размер 2^n, где n можно регулировать. При поиске столкновений координаты объектов преобразовывал из реальных в координаты сети по следующей формуле:
Xs=x>>n
Ys=y>>n, простым побитовым сдвигом, при совпадающих ячейках проверял столкновение. Способ работает очень быстро. Не требуется деление при переводе координат.
Xs=x>>n
Ys=y>>n, простым побитовым сдвигом, при совпадающих ячейках проверял столкновение. Способ работает очень быстро. Не требуется деление при переводе координат.
Точно, раньше я тоже до этого доходил, но когда писал статью совсем забыл. Это действительно очень эффективно.
А можно, пожалуйста, по-подробнее?
Не до конца понял про сторону = 2^n.
в описанном в статье алгоритме сторона ячейки равна диаметру частицы. А у вас сторона ячейки = 2^n чего? даже не знаю… пикселей?.. метров? :-)
Не до конца понял про сторону = 2^n.
в описанном в статье алгоритме сторона ячейки равна диаметру частицы. А у вас сторона ячейки = 2^n чего? даже не знаю… пикселей?.. метров? :-)
Еще забыли диаграммы Вороного. Перекликается со «Sweep and Prune».
Диаграммы Вороного используют как один из методов построения sweepline algorithm. Sweepline это их единственное перекликание. В остальном там все гораздо сложнее и в этой статье не нужно…
> В остальном там все гораздо сложнее и в этой статье не нужно…
Сложнее для понимания или вычислительная нагрузка выше. Этот метод за «n*logn» построит граф, из которого для каждого узла известны соседние. Как минимум упоминания достоен, пусть и понять снаскока Fortune's Sweepline не всякому под силу.
Сложнее для понимания или вычислительная нагрузка выше. Этот метод за «n*logn» построит граф, из которого для каждого узла известны соседние. Как минимум упоминания достоен, пусть и понять снаскока Fortune's Sweepline не всякому под силу.
К тому же после первого построения этот подход упрощает обработку ситуации добавления еще одного узла и перемещения уже имеющихся.
Я конечно извиняюсь, но использовать Вороного для Моделирования большого количества взаимодействующих друг с другом частиц в рамках данной статьи — это как использовать 4-х физиков для забивания 3-х гвоздей — можно, но к чему это вообще?
> Сложность: O(n ^ 2) — в худшем случае, O(n * log(n)) — в среднем случае
Я тоже извиняюсь, если ошибаюсь, но Fortune's Sweepline дает в худшем случае n*logn. Даже если я ошибаюсь, то в худшем случае будет все таже сложность n^2. Так что мне кажется очень даже уместно.
В представленном выше методе также используется сортировка. Алгоритм Фортуна, также ускоряется при выполнении операций над уже обработанным набором. Так что все то же с точки зрения нагрузки. А при имеющейся реализации сложность восприятия неактуальна.
Я тоже извиняюсь, если ошибаюсь, но Fortune's Sweepline дает в худшем случае n*logn. Даже если я ошибаюсь, то в худшем случае будет все таже сложность n^2. Так что мне кажется очень даже уместно.
В представленном выше методе также используется сортировка. Алгоритм Фортуна, также ускоряется при выполнении операций над уже обработанным набором. Так что все то же с точки зрения нагрузки. А при имеющейся реализации сложность восприятия неактуальна.
> К тому же после первого построения этот подход упрощает обработку ситуации добавления еще одного узла и перемещения уже имеющихся.
> Алгоритм Фортуна, также ускоряется при выполнении операций над уже обработанным набором.
В смысле, у вас есть инкрементальный вариант алгоритма Фортуна? В студию!
> Алгоритм Фортуна, также ускоряется при выполнении операций над уже обработанным набором.
В смысле, у вас есть инкрементальный вариант алгоритма Фортуна? В студию!
Думаю там все нативно имеется. Во всяком случае мое понимание таково: 2 кейса
1) Если нового узла не добавляется, то просто обновляем позиции и опять же проверяем расстояния с «соседями в логическом графе». Исключения в случаях когда должно произойти схлопывание одного из полигонов. Но не вижу проблемы чекать два положения узла — прошлое и новое.
2) Если добавляется узел — есть альтернативный Фортуновскому алгоритм разбиения области на полигоны вороного. Забыл как называется — что-то типа «половинного деления площади». Может найду попозже. Эта альтернатива позволяет вообще с нуля строить диаграмму. В нашем же случае нужно просто по графу найти узел в чью зону попадаем и построить новые границы полигона, обойдя по часовой стрелке или против границы полигона в который новый узел угодил.
Принципиальных сложностей не вижу.
1) Если нового узла не добавляется, то просто обновляем позиции и опять же проверяем расстояния с «соседями в логическом графе». Исключения в случаях когда должно произойти схлопывание одного из полигонов. Но не вижу проблемы чекать два положения узла — прошлое и новое.
2) Если добавляется узел — есть альтернативный Фортуновскому алгоритм разбиения области на полигоны вороного. Забыл как называется — что-то типа «половинного деления площади». Может найду попозже. Эта альтернатива позволяет вообще с нуля строить диаграмму. В нашем же случае нужно просто по графу найти узел в чью зону попадаем и построить новые границы полигона, обойдя по часовой стрелке или против границы полигона в который новый узел угодил.
Принципиальных сложностей не вижу.
У меня мысли такие же, но мои попытки ускоренной реализации для движущихся точек, при готовом графе, ни к чему ускоренному не превели. Если много точек появляется-исчезает в небольшом «объёме», то одни и те же куски графа перестариваются много раз, при некоторый «плотности» обновлений, выгоднее просто пускать полное перестроение.
Вся прелесть Фортуна в том, что однажды обработав некоторую область, второй раз он ей не занимается. Поэтому и заинтересовал ваш опыт в этом вопросе, вот если бы был какой-то «локальный Фортун», который, при готовом графе и заданном списке удалённых-добавленных точек, умел интегрировать изменения в граф «за один проход», это было бы да.
Вся прелесть Фортуна в том, что однажды обработав некоторую область, второй раз он ей не занимается. Поэтому и заинтересовал ваш опыт в этом вопросе, вот если бы был какой-то «локальный Фортун», который, при готовом графе и заданном списке удалённых-добавленных точек, умел интегрировать изменения в граф «за один проход», это было бы да.
Удивительно доходчиво написанная статья на интересующую меня тему, спасибо!
Интересно, какой алгоритм пересчета используется в CortextCommand.
Если действительно интересно можно начать копать здесь: habrahabr.ru/blogs/gdev/135794/
А списки Верле плюс списки ячеек в этом случае можно использовать? Там тоже, вроде бы, сложность O(n*log(n)), и проблемы с разными размерами не должно быть.
Очень интересно! Решал похожую задачку, решение нашел в книге по созданию игр, но там все было не так систематично. А тут все четко! Спасибо!
Во-первых, не понимаю, зачем писать статью про 3 алгоритма, если не читая ее, понятно, что рабочий из них только один. Вы бы могли сократить объем и потраченное читателями время в 3 раза, если бы написали только про 1 алгоритм!
Во-вторых, у вас есть if () с комментарием // если индекс частицы изменился и в новой ячейке есть свободные места. А где else? А если свободных мест нет?
Не лучше ли (да конечно лучше, это же очевидно) сделать массив хеш-таблиц? В хеш-таблие хранятся ид всех частиц в данной клетке. В Си это вроде бы std::set или std::map, не знаю, что лучше для этой цели. Хотя, конечно, лучше или нет, можно проверить только бенчмарком. Наверно, если у нас в клетке несколько частиц, тупо перебирать массив может оказаться быстрее.
Вот код на явакрипте (так компактнее и понятнее) для этой задачи.
var clusters = new Array(xCellsCount * yCellsCount);
for (var i in particles) {
var particle = particles[i];
var oldClusterNumber = particle.cluster;
var newNumber = Math.floor(particle.x / xCellSize) + Math.floor(particle.y / yCellSize);
if (oldClusterNumber != newNumber) {
// переместим частицу
delete clusters[oldClusterNumber][particle.id];
clusters[newNumber] || (clusters[newNumber] = {});
clusters[newNumber][particle.id] = true;
}
}
Проверка на столкновение делается так:
for (var i in particles) {
var particle = particles[i];
var cluster = clusters[particle.cluster];
cluster || (throwError('Empty cluster! Thats impossible'));
for (var j in cluster) {
var other = particles[cluster[j]];
if (other.id >= particle.id) { continue; };
checkCollision(particle, other);
}
}
Во-вторых, у вас есть if () с комментарием // если индекс частицы изменился и в новой ячейке есть свободные места. А где else? А если свободных мест нет?
Не лучше ли (да конечно лучше, это же очевидно) сделать массив хеш-таблиц? В хеш-таблие хранятся ид всех частиц в данной клетке. В Си это вроде бы std::set или std::map, не знаю, что лучше для этой цели. Хотя, конечно, лучше или нет, можно проверить только бенчмарком. Наверно, если у нас в клетке несколько частиц, тупо перебирать массив может оказаться быстрее.
Вот код на явакрипте (так компактнее и понятнее) для этой задачи.
var clusters = new Array(xCellsCount * yCellsCount);
for (var i in particles) {
var particle = particles[i];
var oldClusterNumber = particle.cluster;
var newNumber = Math.floor(particle.x / xCellSize) + Math.floor(particle.y / yCellSize);
if (oldClusterNumber != newNumber) {
// переместим частицу
delete clusters[oldClusterNumber][particle.id];
clusters[newNumber] || (clusters[newNumber] = {});
clusters[newNumber][particle.id] = true;
}
}
Проверка на столкновение делается так:
for (var i in particles) {
var particle = particles[i];
var cluster = clusters[particle.cluster];
cluster || (throwError('Empty cluster! Thats impossible'));
for (var j in cluster) {
var other = particles[cluster[j]];
if (other.id >= particle.id) { continue; };
checkCollision(particle, other);
}
}
На сколько я понял, алгоритм с сеткой работает для частиц одинакового диаметра. Остальные — со всеми частицами. Так что иногда нужен, я полагаю, не только последний описанный алгоритм.
Ну а самый первый, наверное, нужен для того, чтобы задать основу, или базис. Типа того :-) Иногда ведь сгодится и он, если частиц не так много
Ну а самый первый, наверное, нужен для того, чтобы задать основу, или базис. Типа того :-) Иногда ведь сгодится и он, если частиц не так много
Что ж, отвечу по порядку.
Рабочие все 3 алгоритма, выбрать можно любой, нужно исходить из исходных данных, если частиц мало, не долго думая выбираем 1 алгоритм, потратив на его написание 10 секунд и не паримся. 2 алгоритм очень популярен, особенно, когда хочется и производительность и не очень хочется копаться в более сложных вещах, тратим на его понимание несколько минут и меньше минуты на кодирование.
Так же мне хотелось сравнивать все алгоритмы по времени работы.
Про условие, очевидно, что, если свободных мест нет, условие не выполняется и частица остается на своем месте, да, это не хорошо, да, вероятно, какие-либо столкновения с ней не обработаются, но об этом в статье я немного написал, если вы смотрели код, то вы могли заметить, что в ячейке хранится максимум 4 частицы, при хорошем расталкивании частиц этого достаточно, можно увеличить это число, можно использовать динамический массив, но это заметно скажется на производительности.
По сути, эта сеть и является хеш таблицей, которая хранит указатели на частицы.
Извините, но ваш код я не читал.
Рабочие все 3 алгоритма, выбрать можно любой, нужно исходить из исходных данных, если частиц мало, не долго думая выбираем 1 алгоритм, потратив на его написание 10 секунд и не паримся. 2 алгоритм очень популярен, особенно, когда хочется и производительность и не очень хочется копаться в более сложных вещах, тратим на его понимание несколько минут и меньше минуты на кодирование.
Так же мне хотелось сравнивать все алгоритмы по времени работы.
Про условие, очевидно, что, если свободных мест нет, условие не выполняется и частица остается на своем месте, да, это не хорошо, да, вероятно, какие-либо столкновения с ней не обработаются, но об этом в статье я немного написал, если вы смотрели код, то вы могли заметить, что в ячейке хранится максимум 4 частицы, при хорошем расталкивании частиц этого достаточно, можно увеличить это число, можно использовать динамический массив, но это заметно скажется на производительности.
По сути, эта сеть и является хеш таблицей, которая хранит указатели на частицы.
Извините, но ваш код я не читал.
Даже если был бы лишь один рабочий, рассмотреть стоило бы хотябы для понимания.
Вот пример:
The «Double-Checked Locking is Broken» Declaration
Обратите на подразделы: «A fix that doesn't work», «More fixes that don't work» и пр.
Вот пример:
The «Double-Checked Locking is Broken» Declaration
Обратите на подразделы: «A fix that doesn't work», «More fixes that don't work» и пр.
Для метода частиц в ячейках используется стандартный алгоритм, для которого надо завести дополнительный целочисленный массив частиц. В массиве ячеек хранится индекс первой частицы попавшей в ячейку. В массиве частиц хранится номер следующей частицы попавшей в эту же ячейку. В этом случае не нужны ограничения на глубину массивов и прочие бяки. Пользуюсь этим для алгоритма SPH.
По вашим результатам времена работы второго и третьего алгоритмов растут одинаково линейно (с небольшим различием линейного коэффициента).
Можете привести сравнение скорости выполнения не в миллисекундах (тем более про железо ничего не сказано), а в количестве операций?
Еще было бы интересно посмотреть как изменится производительность алгоритмов от плотности распределения частиц?
Кстати, сложность алгоритма поиска соседей не может быть O(n), потому что количество пар соседей — это даже не линейная функция от n. То есть, чтобы найти все пары соседей среди n точек не достаточно n операций. Например, для четырех близко расположенных точек, количество пар соседей будет равно шести.
FYI:
Во втором или третьем номере журнала «Программные продукты и системы» (2012) выйдет статья «Алгоритм поиска ближайших соседей» применительно к SPH. Там будет алгоритм со сложностью O(N^2/k), где k > 2 зависит от распределения частиц в пространстве.
Там, например, есть такой эксперимент, где показано, что для поиска очередной пары соседей требуется в среднем 1,3 операции (точки равномерно распределены в квадрате при плотности частиц от 40 до 98 процентов, сторона квадрата от 50 до 100 точек, то есть n было в диапазоне от 2500 до 10000, радиус взаимодействия равен 5, k получилось в диапазоне от 10 до 20). Интересно было бы посмотреть на ваши цифры.
Можете привести сравнение скорости выполнения не в миллисекундах (тем более про железо ничего не сказано), а в количестве операций?
Еще было бы интересно посмотреть как изменится производительность алгоритмов от плотности распределения частиц?
Кстати, сложность алгоритма поиска соседей не может быть O(n), потому что количество пар соседей — это даже не линейная функция от n. То есть, чтобы найти все пары соседей среди n точек не достаточно n операций. Например, для четырех близко расположенных точек, количество пар соседей будет равно шести.
FYI:
Во втором или третьем номере журнала «Программные продукты и системы» (2012) выйдет статья «Алгоритм поиска ближайших соседей» применительно к SPH. Там будет алгоритм со сложностью O(N^2/k), где k > 2 зависит от распределения частиц в пространстве.
Там, например, есть такой эксперимент, где показано, что для поиска очередной пары соседей требуется в среднем 1,3 операции (точки равномерно распределены в квадрате при плотности частиц от 40 до 98 процентов, сторона квадрата от 50 до 100 точек, то есть n было в диапазоне от 2500 до 10000, радиус взаимодействия равен 5, k получилось в диапазоне от 10 до 20). Интересно было бы посмотреть на ваши цифры.
Каюсь, время работы алгоритмов, по факту является временем работы всего Solver-а, а он включает в себя еще и расталкивание частиц, которое занимает значительное время. Т.е. это не совсем время работы именно алгоритма.
Рост времени 2 алгоритма не такой, какой ожидается, из-за того, что частицы на каждом шаге уже практически отсортированы.
Если выключить расталкивание частиц и на каждой итерации все частицы перемешивать, то рост времени у 2 алгоритма будет совсем другой, ближе в ожидаемому. На таких же условиях проверил 3 алгоритм, линейность во всей своей красе:
10000 — 1 мс
20000 — 2 мс
30000 — 3 мс
100000 — 10-11 мс
Можете убедиться в этом сами, в методе Collision, первой строкой сделать return, и на каждой итерации вызывать InitParticles.
Как измерить скорость работы в количестве операций я не совсем понимаю.
Рост времени 2 алгоритма не такой, какой ожидается, из-за того, что частицы на каждом шаге уже практически отсортированы.
Если выключить расталкивание частиц и на каждой итерации все частицы перемешивать, то рост времени у 2 алгоритма будет совсем другой, ближе в ожидаемому. На таких же условиях проверил 3 алгоритм, линейность во всей своей красе:
10000 — 1 мс
20000 — 2 мс
30000 — 3 мс
100000 — 10-11 мс
Можете убедиться в этом сами, в методе Collision, первой строкой сделать return, и на каждой итерации вызывать InitParticles.
Как измерить скорость работы в количестве операций я не совсем понимаю.
Фактическое количество операций можно посчитать, если делать counter++ на каждой итерации самого глубокого цикла (циклов, если их несколько на одном уровне). Например,
counter = 0;
for (int i...) {
for (int j...) {
if (...) {
for (k...) {
counter++;
}
} else {
…
counter++;
}
}
}
Сделайте эту штуку только для части, где ведется поиск соседей. Если у вас моделируется поведение частиц в итераций — 1) найти соседей, 2) применить физику, 3) отрисовать, и опять сначала с шага 1) — то нужно сделать только замер первого прохода шага 1, т.е. когда частицы еще находятся в перемешанном состоянии. Можно, конечно, привести и замеры для второго и следующих проходах, но они будут не так показательны.
Еще, третий алгоритм зависит не только от количества частиц, но и от площади распределения частиц и от плотности распределения. Можете эти цифры тоже привести?
counter = 0;
for (int i...) {
for (int j...) {
if (...) {
for (k...) {
counter++;
}
} else {
…
counter++;
}
}
}
Сделайте эту штуку только для части, где ведется поиск соседей. Если у вас моделируется поведение частиц в итераций — 1) найти соседей, 2) применить физику, 3) отрисовать, и опять сначала с шага 1) — то нужно сделать только замер первого прохода шага 1, т.е. когда частицы еще находятся в перемешанном состоянии. Можно, конечно, привести и замеры для второго и следующих проходах, но они будут не так показательны.
Еще, третий алгоритм зависит не только от количества частиц, но и от площади распределения частиц и от плотности распределения. Можете эти цифры тоже привести?
Всегда хотел замоделировать процесс формирования солнца и планет из частиц, но сложность моделирования взаимодействия всех частиц со всеми останавливала.
С гравитацией по-любому придется считать или каждую частицу с каждой, или использовать particle-mesh методы. Быстрые и простые алгоритмы есть только для короткодействующих сил.
нет ничего сложного — smothe particle hydrodynamics (SPH) решит вашу задачу на десктопе за пару дней с приемлемой точностью.
Броуновское движение — Броуновская динамика — примера программных решений довольно много (понимаю, что для вас это была просто алгоритмическая игра, но...)
www.ifr.ac.uk/materials/fractures/brownian.html
mccammon.ucsd.edu/uhbd.html
www.ifr.ac.uk/materials/fractures/brownian.html
mccammon.ucsd.edu/uhbd.html
Извиняюсь, вопрос не по теме. А в какой программе Вы рисовали эти графики?
Пытаюсь понять, как работает sweep test в bullet (трассировка шейпом), но гуглится только sweep and prune xD Может кто-то подскажет, где почитать
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Моделирование большого количества взаимодействующих друг с другом частиц