Comments 17
«Получив список всех переместившихся объектов, мы начнём с текущего узла и попробуем обходить дерево вверх, пока не найдём узел, полностью вмещающий в себя переместившийся объект»
Зачем такие сложности? При глубине в 9-10 шагов (да даже если и несколько больше, не страшно) проще просто удалять объект из дерева и вставлять заново «сверху». Иначе у тебя появляется неявное дублирование кода которое может привести к проблемам.
Зачем такие сложности? При глубине в 9-10 шагов (да даже если и несколько больше, не страшно) проще просто удалять объект из дерева и вставлять заново «сверху». Иначе у тебя появляется неявное дублирование кода которое может привести к проблемам.
Я в свое время использовал разреженный массив: пространство бьется на кубы по 2*largeObjectSize, потом каждый объект попадает в тот или иной куб. Потом просто прохожусь по всем объектам, смотрю кто в каком кубе и есть ли в этом кубе еще кто-нибудь. Итоговая сложность получается O(N).
Это ОЧЕНЬ полезно при поиске коллизий в гигантском объеме(писал космосим. Расстояния — соответствующие).
Это ОЧЕНЬ полезно при поиске коллизий в гигантском объеме(писал космосим. Расстояния — соответствующие).
Делал похоже, только разбивал пространство на кубы со стороной 2^N, чтобы преобразование координат для проверки вхождения в куб можно было считать через битовые сдвиги (x>>N; y>>N; z>>N).
Вроде бы как, сейчас процессор одинаково обрабатывает деление и битовый сдвиг — за один такт(если конвейер не сброшен). Больше времени занимает пересылка данных. Но тут уже надо мучаться с ассемблерными вставками.
Зачем они? Компиляторы и сами не плохо справляются, хотя конечно понимать придется, как и что компилятор может соптимизировать. Опять же для simd уже есть готовые библиотеки.
Вроде бы как, сейчас процессор одинаково обрабатывает деление и битовый сдвиг — за один такт(если конвейер не сброшен).Деление? За один такт? Это кто ж продаёт такие грибы и сколько они стоят?
Skylake — 23 для восьмибитовых регистров, от 42 — для 64-битовых, на старых процессорах ещё медленнее, на многих ARM'ах вообще реализация через подпрограмму в ядре. Для разных видов x86 тайминги есть тут.
Больше времени занимает пересылка данных.Только если уж совсем в оперативную память «мимо» всех кешей. Деление — это вообще самое медленное, что процессор умеет делать с целыми числами. С огроооомным отрывом от умножения (не зря компиляторы заменяют деление на константу умножением, ох не зря).
Точно такой же способ был в Казаки-1, там через битовые сдвиги тоже считалось в какой зоне юнит.
Так это же стандартные алгоритмы: Barnes–Hut simulation и Сell linked-lists
А разве при этом объект не может всё равно оказаться на границе двух кубов?
В этом случае нужно проверять 8 кубов, а не один. Но теперь становится очевидно, что 2*largeObjectSize — это лишнее и достаточно куба размером строго больше наибольшего объекта. Всё равно же проверять 8 таких кубов.
Хотя… У вас пространство разбито на кубы размером 2*X, но с шагом X? Объект находится всегда сразу в 8 кубах?
Я правильно вас понял?
В этом случае нужно проверять 8 кубов, а не один. Но теперь становится очевидно, что 2*largeObjectSize — это лишнее и достаточно куба размером строго больше наибольшего объекта. Всё равно же проверять 8 таких кубов.
Хотя… У вас пространство разбито на кубы размером 2*X, но с шагом X? Объект находится всегда сразу в 8 кубах?
Я правильно вас понял?
Граница двух кубов — это очень и очень тонкая грань. Я использовал Double, и тут граница куба 2^ значение порядка /2^52. И в таком виде она достигает всего-навсего миллиметра. Ну, в моих масштабах.
В общем и целом, таким случаем можно пренебречь.
В общем и целом, таким случаем можно пренебречь.
Вы не поняли. Я имею в виду, что объект-то имеет размер и может залезть своим объёмом сразу в 8 кубов так, что коллизия возможна между объектами, центры которых в соседних кубах прописаны.
А в вашем смысле граница не должна никого волновать. a<=x<b решает вопрос. В этом случае нет спорных областей.
А в вашем смысле граница не должна никого волновать. a<=x<b решает вопрос. В этом случае нет спорных областей.
А зачем по центру?
На момент создания объекта прописываются 8 точек ограничивающего его параллепипеда. Эти 8 точек могут быть как изменяемы(при вращении объекта), так и константны(высчитываются так, чтобы ни при каком вращении объект не вылезал за границы параллепипеда. Меньше вычислений при вращении, но это куб с наибольшей длиной. При сравнении двух длинных объектов не совсем хорошо). А дальше, эти самые точки залетают в кубы.
Есть еще одна альтернатива — перекрывающиеся кубы строятся так: первый ряд, второй появляется на точках пересечения первого ряда, третий — второго. Ну то есть, каждый шаг сдвигается. И потом центр объекта попадает в ближайший куб. Но там придется брать такой размер куба, чтобы у обоих возможных объектов ближайший центр был бы один. Вроде бы 4х должно хватить. Но это надо считать(я так не делал… и может, очень зря).
На момент создания объекта прописываются 8 точек ограничивающего его параллепипеда. Эти 8 точек могут быть как изменяемы(при вращении объекта), так и константны(высчитываются так, чтобы ни при каком вращении объект не вылезал за границы параллепипеда. Меньше вычислений при вращении, но это куб с наибольшей длиной. При сравнении двух длинных объектов не совсем хорошо). А дальше, эти самые точки залетают в кубы.
Есть еще одна альтернатива — перекрывающиеся кубы строятся так: первый ряд, второй появляется на точках пересечения первого ряда, третий — второго. Ну то есть, каждый шаг сдвигается. И потом центр объекта попадает в ближайший куб. Но там придется брать такой размер куба, чтобы у обоих возможных объектов ближайший центр был бы один. Вроде бы 4х должно хватить. Но это надо считать(я так не делал… и может, очень зря).
А будет про SVO, SVO DAG, SSVDAG?
А через вертексные шейдеры обработать это дерево можно ведь?
В своё время баловался с генерацией из obj формата (текстовый формат описывающий полигоны модели) в октодерево
В итоге если заморачиваться с рендером всего этого на видеокарте оптимальнее всего хранить не разряженное дерево, а на cpu (писал на java) рейтрейсинг у меня жутко тормозил (5cps на томографных снимках крокодильей головы), хотя не исключаю криворукости
В итоге если заморачиваться с рендером всего этого на видеокарте оптимальнее всего хранить не разряженное дерево, а на cpu (писал на java) рейтрейсинг у меня жутко тормозил (5cps на томографных снимках крокодильей головы), хотя не исключаю криворукости
Sign up to leave a comment.
Введение в октодеревья