Russian Qt Forum
Ноябрь 11, 2024, 04:35 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 [2]   Вниз
  Печать  
Автор Тема: Ищу алгоритм деления неравномерных данных  (Прочитано 15826 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #15 : Май 17, 2010, 22:45 »

мне кажется, что хоть тема и хорошая, но более подробно она обсуждалась (обсуждается и будет обсуждаться) на gamedev.ru
Насколько я знаю, в играх эта проблема решается вручную (т.е. разработчик указывает кластера руками). Также некоторые утверждают что для таких ситуаций BSP не годится вообще и следует использовать octree. Однако я могу ошибаться, поэтому буду благодарен за наводки/ссылки.
Записан
spectre71
Гость
« Ответ #16 : Май 17, 2010, 23:32 »

1) Данные распределены неравномерно, в относительно маленьких участках (от общего пространства) может быть сконцентрирована их подавляющая масса. К слову сказать, достигается это очень просто: напр сделал пользователь какую-то модель вазы. 100 тысяч точек и она влазит в кубик 1х1х1. А потом сделал пол для нее - вот в нем аж 10 точек, зато размер 1000x1000 - готово!

Это понятно, и давно Улыбающийся

2) Делить по размеру (расстоянию) плохо, вся сила дерева уходит на деление больших площадей

Это понятно.

3) Делить по числу точек - тогда "дерево сбалансировано" но другая беда - медленный спуск (и медленное построение)

А это не понятно, особенно выделенное.

4) Возникает мысль разделить области с большой и малой плотностью.

По сути не отличается от деления по кол-ву точек, с  интервалами разного размера.

Да, я могу строить любые гистограммы (если я правильно употребляю этот термин), ну и что с ними делать? Напр. получил что-то такое (число данных в интервалах)

1, 5, 10, 100, 1, 200, 1, 2. 1000, 500, и.т.д

Как выбрать место деления? Из каких соображений выбирать длину интервалов?

Не понял!!!
Так есть хоть какой-то критерий разделения. Можно на примере выше, например вложенными круглыми скобками.


« Последнее редактирование: Май 17, 2010, 23:36 от Spectre » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #17 : Май 18, 2010, 21:47 »

3) Делить по числу точек - тогда "дерево сбалансировано" но другая беда - медленный спуск (и медленное построение)

А это не понятно, особенно выделенное.
Да, поделить по числу точек можно, получится сбалансированное дерево. Да, для такого дерева поиск log2(N) операций - для любого запроса. И это было бы прекрасно - для поиска тех самых точек которые использовались для построения дерева. Но вот напр "найти все точки в радиусе R от заданной" - и, как ни странно, сбалансированное дерево работает плохо. Для любой точки будет выполняться напр 20 спусков, как если бы все пространство было равномерно заполнено. Очевидно что если бы в примере "ваза стоит на полу" мы бы использовали 2 дерева (одно для вазы, др. для пола) то для всех точек пола (которые запрашиваются) мы бы нашли соседей намного быстрее.

Не понял!!!
Так есть хоть какой-то критерий разделения. Можно на примере выше, например вложенными круглыми скобками.
Я такой критерий и ищу. Вот максимально упрощенный пример

Длина      Число точек
---------------------
(0-8)        1
(8-11)      100
(11-100)     1

Здесь все ясно, разбиваем на 3 интервала, как они записаны в левом столбце. Но откуда их взять, ведь у меня никаких интервалов (еще) нет, я только могу их создавать используя сортированный массив. И плотности могут быть совсем не такими красивыми и круглыми как в примере. Мне надо как-то поймать ситуацию "скопление", а если ее нет, то не мудрствуя лукаво, делить пополам по длине.
Записан
spectre71
Гость
« Ответ #18 : Май 19, 2010, 12:52 »

Да, поделить по числу точек можно, получится сбалансированное дерево. Да, для такого дерева поиск log2(N) операций - для любого запроса. И это было бы прекрасно - для поиска тех самых точек которые использовались для построения дерева. Но вот напр "найти все точки в радиусе R от заданной" - и, как ни странно, сбалансированное дерево работает плохо. Для любой точки будет выполняться напр 20 спусков, как если бы все пространство было равномерно заполнено. Очевидно что если бы в примере "ваза стоит на полу" мы бы использовали 2 дерева (одно для вазы, др. для пола) то для всех точек пола (которые запрашиваются) мы бы нашли соседей намного быстрее.

Это уже другая задача. И зачем вообще использовать дерево!
Опять все та-же таблица:
интервал   точек  суммы  упорядоченные
                                     списки точек в интервале
1                3         3          *
2                4         7          *
4                2         9          *
5                1         10        *
8                2         12        *   

C*log(N) для любого запроса, в том числе и нахождения интервала где точки отстоят от заданной на расстоянии R+/-Delta. Delta зависит от способа построения таблицы, в пределах Delta прямой перебор точек. Если нет ограничения на кол-во записей в таблице, то Delta == 0 и понятие интервал исчезает - вместо него получаем координату точки и ее кратность.

Мне до сих пор мне не понятно для чего строиться дерево! Какие операции(запросы) будут с ним делаться далее. Какая частота этих операций, их кол-во, ... От этого все зависит. Отимизировать построение необходимо по конкретное использование получаемых данных.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #19 : Май 19, 2010, 19:21 »

Это уже другая задача. И зачем вообще использовать дерево!
Опять все та-же таблица:
Совершенно верно, для 1-мерного случая проще обойтись поиском  Улыбающийся, я об этом говорил в первом посте. Но это не распространяется на 2 и более измерений. В 2 измерениях (на плоскости) дерево выглядит как прямоугольники, который разбиваются на дочерние прямоугольники. Использование такого дерева:

- для луча с заданным направлением и выходящим из заданной точки найти все прямоугольники в порядке их пересечения лучом. Для всех найденных прямоугольников если они листья дерева - перебрать все данные на которые прямоугольники ссылаются

3-х мерный случай ничем не отличается, проблема общая для любой размерности.
Записан
ieroglif
Гость
« Ответ #20 : Май 19, 2010, 21:29 »

а я бы предложил другую схему.
обычно она как раз применяется в играх. но если делается 3д дизайнерский софт, то применить тоже логично и не сложно.
У нас имеется 3д пространство с 3д объектами.
Начнём с того, что каждый объект мы кладём в ббокс.
Ббокс = boundary box = bbox.
тем самым мы без проблем сможем находить с каким глобальным объектом пересёкся луч (например, траеторию пули моделируем с повреждением объектов) - быстро получили (к примеру) стол, стул и пол.
Допустим, каждый из этих объектов у нас весьма и весьма полигональный (ну пусть будет под 10000 полигонов каждый).
Разумеется, перебирать каждый для поиска луча - офигеешь.
ну в таком случае мы заранее определяем 2-3 уровня внутренних ббоксов типа "дерево" к последнему уровню которых привязаны реальные полигоны. к примеру, ббокс 1 будет состоять из 50 полигонов  - перебрать не сложно. находим нужные полигоны, и от них деревом берём ещё штук 50 полигонов ббокса 2 уровня, чекаем их, и там уже по дереву чекаем последние реальные полигоны для поиска нужного.

Вроде неплохо, но, на самом деле, тут будут и свои особенности.
Например при разработке игры нам требуются модельки монстриков, которым можно отдельно отстреливать конечности.
В самом начале мы отдаём дизайнерам задание - при разработке моделей определять им дополнительные ббоксы, и написать небольшую утилитку, которая будет перегонять эти модельки с ббоксами в удобоваримый рендеру-физике-движку вид.
Таки образом траектория пули определяется просто:
пересечение с глобальным ббоксом монста? - ок. понеслась.
пересечение с ббокс "голова"? - нет. дальше
пересечение с ббокс "рука"? - ок. понеслась.
пересечение с ббокс "локоть"? - нет. дальше
пересечение с ббокс "плечо"? - да.
для плеча ищем нужный полигон, рисуем на нём дырку, модифицируем как-то, если надо, заодно по всем полигонам  в группе "рука" накладываем текстуры кровяки (а точнее просто переключаем модель), в AI ставим флаги "невозможность действовать правой рукой кроме как дубиной" и радуемся жизни =) главная задача - это корректное разбиение по ббоксам внутреннего уровня - ну за этим уже следить сразу надо.

если же у нас не игра а 3д редактор, то нужно писать алгоритм (но с моей точки зрения не очень сложный) добавления объектам ббоксов.
алгоритм должен учитывать размер полигонов, туда включённых, или какие-то пользовательские группировки полигонов..
зато всё это настроить и сделать вполне реально и работать будет хорошо. =)
вполне возможно, что в большинстве случаев математический поиск сведётся всего лишь к перебору ббоксов, и до полигонов не дойдёт.
Записан
spectre71
Гость
« Ответ #21 : Май 20, 2010, 08:56 »

Это уже другая задача. И зачем вообще использовать дерево!
Опять все та-же таблица:
Совершенно верно, для 1-мерного случая проще обойтись поиском  Улыбающийся, я об этом говорил в первом посте. Но это не распространяется на 2 и более измерений. В 2 измерениях (на плоскости) дерево выглядит как прямоугольники, который разбиваются на дочерние прямоугольники. Использование такого дерева:

- для луча с заданным направлением и выходящим из заданной точки найти все прямоугольники в порядке их пересечения лучом. Для всех найденных прямоугольников если они листья дерева - перебрать все данные на которые прямоугольники ссылаются

3-х мерный случай ничем не отличается, проблема общая для любой размерности.

Вводим дополнительную индексацию прямоугольников. Для двумерного случая например сетка 100*100. Каждый элемент сетки так или иначе ссылается на  прямоугольники пересекающихся с ним. Нахождение элементов сетки пересекаемых лучем простое вычисление. Елементы сетки для оптимизации поиска и хранения индексов прямоугольников в них могут иметь разные типы, например: пустая, простой короткий список прямоугольников, список точек, дерево некоторого типа, подсетка, итд.

« Последнее редактирование: Май 20, 2010, 08:59 от Spectre » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #22 : Май 20, 2010, 10:26 »

а я бы предложил другую схему.
обычно она как раз применяется в играх. но если делается 3д дизайнерский софт, то применить тоже логично и не сложно.
Я Вас прекрасно понял. Дело в том что мой случай "общий", я не могу делать никаких предположений. Да, сцена всегда сгруппирована по объектам и  эта информация мне известна. Но работать только по ббоксам - не проходит. Тысяча и более объектов в сцене - рядовой случай. 10-20 тысяч - тоже никого не удивишь. Так что даже перебор ббоксов может быть медленным.

Разумно выбирать делители на границе ббоксов объектов. Но тут начинается масса частных случаев. Объект может иметь мало полигонов, тогда деление по его границе ничего не даст. Или ббокс "закопан" в другие ббоксы. Словом, реализация получается хлопотливая. "Одно дерево на всех" намного проще.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #23 : Май 20, 2010, 10:32 »

Вводим дополнительную индексацию прямоугольников. Для двумерного случая например сетка 100*100. Каждый элемент сетки так или иначе ссылается на  прямоугольники пересекающихся с ним. Нахождение элементов сетки пересекаемых лучем простое вычисление. Елементы сетки для оптимизации поиска и хранения индексов прямоугольников в них могут иметь разные типы, например: пустая, простой короткий список прямоугольников, список точек, дерево некоторого типа, подсетка, итд.
Ну эта сетка выглядит ненужной надстройкой над деревом  Улыбающийся  Если у нее много (полу) пустых ячеек - их придется все равно перебирать на пути луча
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #24 : Май 20, 2010, 10:46 »

Добрый день

В общем нашел я решение. Алгоритм

- делю пополам по расстоянию
- смотрю сколько попало в левую и правую части. Нахожу отношение t = min/max. Если t > 0.1, все хорошо, приступаю к делению получившихся нодов. Иначе сдвигаю делитель в нужную сторону и повторяю деление. И так 8 раз, выход если t > 0.1

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

Спасибо всем принявшим участие в обсуждении, особенно Spectre. Как говорил мой старый друг "идеи приходят от общения"  Улыбающийся
Записан
Страниц: 1 [2]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.154 секунд. Запросов: 23.