Задача на хаотичное раскидывание точек в пространстве

Думаю вот над такой задачей:

Пусть в пространстве каким-то образом хаотично раскиданы точки. Конкретный сопособ раскидывания - на усмотрения решающего задачу, какой угодно, лишь бы "на глаз" раскидка смотрелась хаотичненько. Ограничено количество точек или нет - также на усмотрение решающего, но лучше чтобы не ограничено.

Задача - быстрый способ перечислить все точки, попавшие в заданное подпространство - сферу или кубик - подойдет любой вариант. В идеале - o(N), где N - число точек, попавших в заданное подпространство. То есть распределение точек должно задаваться способом из перечисления в заданном подпространстве. Решение нужно в координатах. Также нужно уметь контролировать через параметр густоту точек в пространстве.

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

Какие будут идеи?

 

То есть распределение точек должно задаваться способом их перечисления в заданном подпространстве.

 

_DEN_
известны координаты всех точек - нужно узнать какие из них попали в сферу/кубик? - тогда непонятно про их неограниченное количество.

или

координаты всех точек решающему неизвестны и их нужно искать в пределах сферы/кубика? тогда встаёт вопрос о размерах точки - насколько мелким ситом их процеживать.

 

Приведу конкретный пример. Разобьем пространство на координатную сетку. Возьмем за (x, y, z) - единичный кубик пространстра с координатами (x, y, z). Тогда:

Количество точек в кубике: f(x, y, z) = 10 * round(abs(sin(x + y + z)))
Относительные координаты N-ной точки в кубике: g(x, y, z) = round(abs(cos(x + y + z + N + i))), где i - номер координаты (x = 0, y = 1, z = 2).

Конечно же такие формулы скорее всего дадут не хаотичное распределение с каким-то просматриваемым паттерном, но суть решения они отражают. Нужно придумать тоже самое, но в движении.

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

 

Y_Mur

Ни то, ни другое. Точки заданы псевдослучайным распределением. В теорвере мы привыкли задавать случайную величену ее распределением по правилу: F(x) = P, где "P" - вероятность того, что значение случайной величины меньше чем "x".

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

 

т.е. вероятность нахождения точки в заданном подпространстве задано как F(x) = P? и её конкретные координаты не важны?
или все координаты самостоятельны и верятностно заданы как F(x) = ..., F(y) = ..., F(z) = ... и нужно определить попали ли точки куда нужно?

 

Y_Mur

Ой, в примере прогнал. g(x, y, z) - без раунда.

Да не, ничего не задано Задача как раз в том и заключается, чтобы все придумать самому. Ничего не дано, нужно все придумать, любой способ. Есть пространство, в нем хаотично раскиданы точки. Все точки в памяти хранить нельзя - их бесконечно много. Их координаты определяются какой-то псевдослучайной функцией. Нужно: 1) уметь перечислить все точки в заданном подпространстве и 2) дать юзеру возможность контролировать эту псевдослучайную функцию.

 

Один из способов задания псевдослучайной величины - это задание способа последовательного перечисления ее значений. Ну вот например псевдослучайная величина f(N) = 2^N^N % 10
А мне нужно 1) тоже самое но в 3D и 2) с таким способом перечисления, который позволял бы не просто последовательно перечислить значения, а в заданом подпространстве

 

http://en.wikipedia.org/wiki/Bounding_volume_hierarchy

 

Booster

Эта такая мода пошла на васме отвечать ссылками и ключевыми словами, без словесного сопровождения? Я знаю что такое баунды, спасибо, Кэп. Было бы еще неплохо если бы ты рассказал, как это мне поможет.

 

Что за манера пошла называть меня кэпом? Нет я не против, но всего хорошего по-немногу. Ссылками стал отвечать, так как это cнижает шансов зафлеймиться/затроллиться/забаниться.

BHV - иерархия ограничивающих объёмов, драматически снижает сложность поиска коллизий - logN, где N глубина дерева. Реализаций тьма, октодерево например.

 

Booster

Потому что ты - Капитан Очевидность дзена

Это все подходит когда количество объектов ограничено. А в моем случае log(+inf) это все та же +inf.

 

Тебе конечно видней, только мне непонятно за что я удостоился такого почётно звания.

>Это все подходит когда количество объектов ограничено. А в моем случае log(+inf) это все та же +inf.
Конечно, к коню в сферическом вакууме это не подойдёт.

 

_DEN_
А вообще хамить не хорошо. Ещё одна причина отвечать ссылками, меньше шансов нарваться на хамство.

 

Booster

Я не хамлю. Просто 90% твоих ответов это либо полная очевидность, либо совершенно не в тему.

Баунды и всякие там октри подходят (или - "обычно используют") когда ты оперируешь "ручными" объектами - например объектами, которые моделлер намоделил в максе и расставил по сцене руками. У меня же объекты не расставлены руками, а задаются некоторой функцией псевдослучайных точек. Сферический конь тут совершенно не при чем - это просто задача другого рода. Баунды работают на других классах задачь.

 

_DEN_

Пруф?

Если на п. 1 нет пруфа, то это хамство.

Да? По-моему кэп как раз ты. Откуда ты откопал сей постулат? Речь не баундах, а о bvh.

 

Booster

Пруф - личный опыт. В следующий раз увижу - обязательно дам знать. Искать старое не буду.

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

 

тогда вижу два решения:
1) генерируешь точки генератором псевдослучайных чисел (они же с и с равномерным и с заданным распределением есть), затем проверяешь попала ли точка в дипазон. Повторяемость при перечислении будет, т.к. генераторы псевдослучайные. И сразу получишь счётчик - статистику - сколько попало сколько нет.

Но если не попавшие в дипазон точки совсем не интересуют (даже в плане количества) то:
2) задаёшь границы для равномерных генераторов псевдослучайных чисел так чтобы все выдаваемые ими точки попадали в дипазон (при сложной фигуре диапазон y будет зависеть от значения x, а дипазон z от значений x и y)
тогда все точки сразу попадут куда надо (будет перечисление без промахов).
Но если распределение неравномерное то метод 2 не пойдёт, поскольку там как правило нельзя чётко задать дипазон.

 

Значит хам, иначе никак.

У тебя что-то принципиально другое? Ну да геймдевелопментом это не назвать. Конечные алгоритмы также очень редко ложатся на бесконечность.
Ладно не следовало мне ввязываться в эту полемику, с некоторыми это бесполезно по-определению.

 

Y_Mur

Метод 2 подходит, и я так себе это и представляю. Только он не показывает, как сделать так, чтобы точки могли двигаться по псевдослучайным направлениям и скоростям.