Ищу алгоритм деления неравномерных данных

[Igors]

мне кажется, что хоть тема и хорошая, но более подробно она обсуждалась (обсуждается и будет обсуждаться) на gamedev.ru

Насколько я знаю, в играх эта проблема решается вручную (т.е. разработчик указывает кластера руками). Также некоторые утверждают что для таких ситуаций BSP не годится вообще и следует использовать octree. Однако я могу ошибаться, поэтому буду благодарен за наводки/ссылки.

[spectre71]

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

Это понятно, и давно

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

Это понятно.

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

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

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

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

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

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

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

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

[Igors]

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

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

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

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

Я такой критерий и ищу. Вот максимально упрощенный пример

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

Здесь все ясно, разбиваем на 3 интервала, как они записаны в левом столбце. Но откуда их взять, ведь у меня никаких интервалов (еще) нет, я только могу их создавать используя сортированный массив. И плотности могут быть совсем не такими красивыми и круглыми как в примере. Мне надо как-то поймать ситуацию "скопление", а если ее нет, то не мудрствуя лукаво, делить пополам по длине.

[spectre71]

Да, поделить по числу точек можно, получится сбалансированное дерево. Да, для такого дерева поиск 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]

Это уже другая задача. И зачем вообще использовать дерево!
Опять все та-же таблица:

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

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

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

[ieroglif]

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

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

если же у нас не игра а 3д редактор, то нужно писать алгоритм (но с моей точки зрения не очень сложный) добавления объектам ббоксов.
алгоритм должен учитывать размер полигонов, туда включённых, или какие-то пользовательские группировки полигонов..
зато всё это настроить и сделать вполне реально и работать будет хорошо. =)
вполне возможно, что в большинстве случаев математический поиск сведётся всего лишь к перебору ббоксов, и до полигонов не дойдёт.

[spectre71]

Это уже другая задача. И зачем вообще использовать дерево!
Опять все та-же таблица:

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

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

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

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

[Igors]

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

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

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

[Igors]

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

Ну эта сетка выглядит ненужной надстройкой над деревом    Если у нее много (полу) пустых ячеек - их придется все равно перебирать на пути луча

[Igors]

Добрый день

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

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

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

Спасибо всем принявшим участие в обсуждении, особенно Spectre. Как говорил мой старый друг "идеи приходят от общения"