Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 29
Поиграться в онлайн
Спасибо за статью. Именно ёё мне не хватало года 4 назад, когда хотел написать свой клон Космических Рейнджеров.
Прилично. Мне понравилось. Спасибо большое.
Ещё из похожей геометрии мне очень нравилсь триангуляция Делоне. Очень красиво получается, когда при добавлении точки перестраивается почти вся сеть.
Ещё из похожей геометрии мне очень нравилсь триангуляция Делоне. Очень красиво получается, когда при добавлении точки перестраивается почти вся сеть.
Так Делоне обычно с помощью Форчуна и делают (если речь о произвольных точках).
Если нужна просто сетка — то там есть и другие способы.
Если нужна просто сетка — то там есть и другие способы.
Дело было больше чем 25 лет назад. Не помню какой был алгоритм. Думаю, что придумывал что-то своё. Помню только — на С++, и что это был итерационный процесс. Ещё помню — очень нравилась визуализация процесса — как сеть перестраивается шаг за шагом… А потом стал искать — как добавить точку так, чтобы максимизировать количество перестановок рёбер… В общем — как-то так. Ничего уже не помню, кроме того, что выглядел этот процесс красиво (с моей точки зрения).
А не знает ли кто-нибудь адекватного способо построения сетки на торе? В смысле — циклически замкнутой?
А то ничего умнее построения сети с дублированием точек с противоположного края и последующим их пересоединением так и не придумал. В принципе метод работает, но напрягает непредсказуемое количество доп. точек. И их количество. Когда сама сеть имеет многие десятки тыс. точек то дополнение даёт ещё похожий порядок.
А то ничего умнее построения сети с дублированием точек с противоположного края и последующим их пересоединением так и не придумал. В принципе метод работает, но напрягает непредсказуемое количество доп. точек. И их количество. Когда сама сеть имеет многие десятки тыс. точек то дополнение даёт ещё похожий порядок.
Взглянув на картинку (прочитав только условие), подумал, что графически это можно решать так: Строим воображаемую линию от места до места, находим середину, рисуем перпендикуляр. Ячейки будут образовываться пересечением этих перпендикуляров. (потом подумал что это же медианы треугольников с вершинами в местах)
Алгоритм же использует совсем другой подход. Очень интересно. Спасибо.
Алгоритм же использует совсем другой подход. Очень интересно. Спасибо.
В boost есть хорошая реализация диаграмы Вороного. Причем не только для точек, но и для отрезков.
На счёт точно равной ничего не скажу, но примерно равную можно получить прогнав несколько (2..3 минимум) проходов релаксации. Собственно обычно так и делают.
Про края ничего не скажу, однако метод вполне рабочий и для конечной. Достаточно зафискировать точки, которые на границе.
Про неправильную речи не было — таким образом разбить её на выпуклые (тут ячейки всегда выпуклые) в общем случае вообще невозможно. Если невыпуклые — можно изгалиться например разбив Вороным а потом выбрав рандомные точки и присоединяя к ним постепенно соседние ячейки, благо связность сетки позволяет это делать довольно легко. При дисбалансе соседних ячеек можно перераспределять, пока не дойдёт примерно до баланса.
Про неправильную речи не было — таким образом разбить её на выпуклые (тут ячейки всегда выпуклые) в общем случае вообще невозможно. Если невыпуклые — можно изгалиться например разбив Вороным а потом выбрав рандомные точки и присоединяя к ним постепенно соседние ячейки, благо связность сетки позволяет это делать довольно легко. При дисбалансе соседних ячеек можно перераспределять, пока не дойдёт примерно до баланса.
Собственно приведённый выше вариант должен решить проблему (для произвольной геометрии).
1. Диаграмму строить мелкую, по всему полю. Добавить точки строго по границе суши. Если использовать релаксацию, то эти точки не трогать. Тогда получим более-менее точную триангуляцию отдельно суши, а отдельно воды.
2. Отмечаем как-то треугольники, которые попали на воду им забываем про них.
3. Вычисляем площадь одной группы (т.е. по сути делим кол-во треугольников суши на кол-во групп)
3. Выбираем точку где-нибудь на границе и начинаем прицеплять к ней соседние полигоны (из диаграммы они известны) пока не получим нужное кол-во. Повторяем, пока площадь не кончится. Будет примерно равное разбиение. Если нужно прямо совсем точное — границы потом можно передвинуть в нужную сторону.
Для клеточного варианта можно пропустить диаграмму и работать непосредственно с соседними клетками.
Можно добавить так-же вероятность НЕ включения ячейки, чтобы граница была не ровной. Чтобы не случилось цикла вероятность можность делать пропорциональной расстоянию от начальной точки, чтобы вблизи хватали всё, а дальше уже как получится. Или при получении цикла просто заполнять всю захваченную зону а потом отрезать от границы лишнее.
Стоит учесть, что если река делит сушу на неравные куски, либо на равные, но нечётное число групп — то равномерное распределение невозможно в принципе. Всегда будет где-то больше, где-то меньше. Тогда придётся цеплять остаток кому-то.
Можно это оформить и в виде клеточного автомата, чтобы оно само балансировалось. Правда придётся прогонять много итераций.
1. Диаграмму строить мелкую, по всему полю. Добавить точки строго по границе суши. Если использовать релаксацию, то эти точки не трогать. Тогда получим более-менее точную триангуляцию отдельно суши, а отдельно воды.
2. Отмечаем как-то треугольники, которые попали на воду им забываем про них.
3. Вычисляем площадь одной группы (т.е. по сути делим кол-во треугольников суши на кол-во групп)
3. Выбираем точку где-нибудь на границе и начинаем прицеплять к ней соседние полигоны (из диаграммы они известны) пока не получим нужное кол-во. Повторяем, пока площадь не кончится. Будет примерно равное разбиение. Если нужно прямо совсем точное — границы потом можно передвинуть в нужную сторону.
Для клеточного варианта можно пропустить диаграмму и работать непосредственно с соседними клетками.
Можно добавить так-же вероятность НЕ включения ячейки, чтобы граница была не ровной. Чтобы не случилось цикла вероятность можность делать пропорциональной расстоянию от начальной точки, чтобы вблизи хватали всё, а дальше уже как получится. Или при получении цикла просто заполнять всю захваченную зону а потом отрезать от границы лишнее.
Стоит учесть, что если река делит сушу на неравные куски, либо на равные, но нечётное число групп — то равномерное распределение невозможно в принципе. Всегда будет где-то больше, где-то меньше. Тогда придётся цеплять остаток кому-то.
Можно это оформить и в виде клеточного автомата, чтобы оно само балансировалось. Правда придётся прогонять много итераций.
А зачем знать — разделится или нет, если у вас задача строго не делить. Сделайте клетки меньше, чем ширина водоёма раза в 2 и тогда гарантированно можно присоединять всех не-водных соседей.
Да это понятно. Вопрос — надо ли так принципиально использовать большие клетки? Если уменьшить из размер в 2 раза — задача решаема, причём сразу 2мя способами. А если принципиально, то стоит тщательнее подбирать структуру поля под количество групп. В играх такое деление идёт либо на 4 группы, либо на 2 + ничейные земли под захват.
Ну и тут как раз вариант, который на 2 ровно не делится без весьма большой погрешности.
Кстати именно с такой структурой и мелкими клетками и мой вариант может не справиться без дополнительных эвристик. Если перекрыть проходы в центре, то второму достанутся 3 изолированных лепестка. Правда если добавить механизм захвата (для клеточного автомата) то он через некоторое время может сбалансироваться и на таком поле.
Ну и тут как раз вариант, который на 2 ровно не делится без весьма большой погрешности.
Кстати именно с такой структурой и мелкими клетками и мой вариант может не справиться без дополнительных эвристик. Если перекрыть проходы в центре, то второму достанутся 3 изолированных лепестка. Правда если добавить механизм захвата (для клеточного автомата) то он через некоторое время может сбалансироваться и на таком поле.
Недавно увидел на дороге очень выразительную трещину на асфальте.
Задумался о ней, как о динамической системе: все эти напряжения в материале, разрывы, их направления и изгибы, где-то ближе, где-то дальше. А результат даже композиционно эстетичен. Стало интересно — смогу ли я смоделировать правдоподобно выглядящую трещину. В итоге пришёл к выводу что оптимально для этого подойдёт именно диаграма Вороного. Но посмотрев на алгоритмы её построения, отложил это развлечение в долгий ящик.
Задумался о ней, как о динамической системе: все эти напряжения в материале, разрывы, их направления и изгибы, где-то ближе, где-то дальше. А результат даже композиционно эстетичен. Стало интересно — смогу ли я смоделировать правдоподобно выглядящую трещину. В итоге пришёл к выводу что оптимально для этого подойдёт именно диаграма Вороного. Но посмотрев на алгоритмы её построения, отложил это развлечение в долгий ящик.
На самом деле похожая сетка получается элементарно:
1. Строим диаграмму на рандомных точках.
2. Каждую прямую разбиваем на №дцать отрезков.
3. Все вершины смещаем как
x+= perlin_noise(x,y) * scale;
y+= perlin_noise(x+const1,y+const2) * scale;
В этом плане гораздо интереснее старые наклейки. Они ссыхаясь рвутся иерархически — т.е. сначала на крупные ячейки, потом крупные на более мелкие.
1. Строим диаграмму на рандомных точках.
2. Каждую прямую разбиваем на №дцать отрезков.
3. Все вершины смещаем как
x+= perlin_noise(x,y) * scale;
y+= perlin_noise(x+const1,y+const2) * scale;
В этом плане гораздо интереснее старые наклейки. Они ссыхаясь рвутся иерархически — т.е. сначала на крупные ячейки, потом крупные на более мелкие.
Элементарно? Но ведь сложность генерации шума Перлина для двумерного пространства квадратична, а для алгоритма Форчуна строящего диаграмму Вороного
n * log nЭлементарно с точки зрения реализации, а не вычислительной сложности. Но и последнюю вы оценили не совсем корректно.
1. У вас на картинке примерно 60..80 точек для диаграммы, что совсем ни о чём. Я много играюсь с этим, и могу сказать, что нормальная либа строит диаграмму в сотни тысяч точек за какое-то незначительное время (не засекал, но на глаз — какие-то доли секунды.)
2. Для смещения сетки не требуется полное заполенние всей площади шумом. Достаточно (количество_рёбер*количество_отрезков), что очень сильно отличается от полного заполнения.
3. Если вдруг душа требует полного заполнения — на ГПУ (даже на древнем встроенном интеле) шум Перлина без проблем генерится в реальном времени с пристойным фпс. Собственно когда замучался ждать, пока сгенерится несколько больших слоёв 2D или 3D (последнее на ЦПУ просто невероятно долго) — переделал на ГПУ и забыл про эту проблему.
Навскидку вот такое сгенерилось. Я не парился с подбором коэффициентов и разбросом точек, но, при желании, можно подобрать так, что будет не особо отличимо от вашей картинки.
Кстати теоретически подобную картинку можно получить и один фрагментным шейдером (Вороной тоже вполне на ГПУ строится). Правда при этом информацию о границах не получить (адекватным способом. всякие детекторы границ не в счёт)
1. У вас на картинке примерно 60..80 точек для диаграммы, что совсем ни о чём. Я много играюсь с этим, и могу сказать, что нормальная либа строит диаграмму в сотни тысяч точек за какое-то незначительное время (не засекал, но на глаз — какие-то доли секунды.)
2. Для смещения сетки не требуется полное заполенние всей площади шумом. Достаточно (количество_рёбер*количество_отрезков), что очень сильно отличается от полного заполнения.
3. Если вдруг душа требует полного заполнения — на ГПУ (даже на древнем встроенном интеле) шум Перлина без проблем генерится в реальном времени с пристойным фпс. Собственно когда замучался ждать, пока сгенерится несколько больших слоёв 2D или 3D (последнее на ЦПУ просто невероятно долго) — переделал на ГПУ и забыл про эту проблему.
Навскидку вот такое сгенерилось. Я не парился с подбором коэффициентов и разбросом точек, но, при желании, можно подобрать так, что будет не особо отличимо от вашей картинки.
Кстати теоретически подобную картинку можно получить и один фрагментным шейдером (Вороной тоже вполне на ГПУ строится). Правда при этом информацию о границах не получить (адекватным способом. всякие детекторы границ не в счёт)
Действительно очень похоже, хотя это разбиение и выглядит более равномерным. Интересно было бы дать строгое обоснование почему то или иное разбиение больше или меньше похоже на настоящие трещины, но для этого, наверное, надо одолеть нетривиальную (для меня) физику явления.
Кстати, по вашему алгоритму есть какие-то статьи/мануалы? «Строим диаграмму на рандомных точках», — какую именно всё-таки диаграмму и как строим? А для какой задачи, кстати, Вам потребовалось строить на сотнях тысяч точек, если не секрет?
P.S. Мне не для дела — праздный интерес.
Кстати, по вашему алгоритму есть какие-то статьи/мануалы? «Строим диаграмму на рандомных точках», — какую именно всё-таки диаграмму и как строим? А для какой задачи, кстати, Вам потребовалось строить на сотнях тысяч точек, если не секрет?
P.S. Мне не для дела — праздный интерес.
Равномерность зависит от изначального разброса точек. У меня они просто рандомные. Если использовать для точек не чисто случаную выборку, а клеточно-случаную (как в шейдерах, там всё поле делится на клетки и в каждой выбирается случайная точка с тем или иным разбросом относительно центра) может получаться как раз похожая картина групп крупных и редких пятен.
Единого обоснования быть не может, поскольку причин появления трещин много, и, как следствие, разные процессы могут описываться разными закономерностями. Например асфальт часто трескается не сам по себе (ему это вообще не свойственно), а из-за локального изгиба, за который может отвечать неравномерная подложка или наоборот, локальная перегрузка сверху. Например тяжелые грузовики очень хорошо проламывают асфальт со слабой подложкой. В тех случаях, когда материал трескается сам — там уже зависит от конкретного процесса. Например ссыхающаяся краска и упомянутые мной наклейки трескаются по разному.
Алгоритм стандартный, тот же Форчун. Если интересно — вот эти исходники. Чистый С, очень быстрый.
Пардон, диаграмму Вороного, естественно.
Задачи, на самом деле, очень разные. Я много эксперементирую со всякими (иногда странными) идеями. Да и Вороной вообще очень много где используется. Везде, где требуется неравномерное разбиение пространства, поскольку это самый эффективный способ получить случайную связную сеть.
У меня самые большие сетки были для симуляции эррозии на больших пространствах. Реально такого количества не требовалось, но ради эксперемента проверял, потянет ли большой масштаб. Да и 100К — на самом деле не так много. Достаточно мелкая сетка на поле 1024*1024 легко потянет в разы больше.
Единого обоснования быть не может, поскольку причин появления трещин много, и, как следствие, разные процессы могут описываться разными закономерностями. Например асфальт часто трескается не сам по себе (ему это вообще не свойственно), а из-за локального изгиба, за который может отвечать неравномерная подложка или наоборот, локальная перегрузка сверху. Например тяжелые грузовики очень хорошо проламывают асфальт со слабой подложкой. В тех случаях, когда материал трескается сам — там уже зависит от конкретного процесса. Например ссыхающаяся краска и упомянутые мной наклейки трескаются по разному.
Алгоритм стандартный, тот же Форчун. Если интересно — вот эти исходники. Чистый С, очень быстрый.
Пардон, диаграмму Вороного, естественно.
Задачи, на самом деле, очень разные. Я много эксперементирую со всякими (иногда странными) идеями. Да и Вороной вообще очень много где используется. Везде, где требуется неравномерное разбиение пространства, поскольку это самый эффективный способ получить случайную связную сеть.
У меня самые большие сетки были для симуляции эррозии на больших пространствах. Реально такого количества не требовалось, но ради эксперемента проверял, потянет ли большой масштаб. Да и 100К — на самом деле не так много. Достаточно мелкая сетка на поле 1024*1024 легко потянет в разы больше.
Аа, так всё-таки в основе диаграмма Вороного! Я вначале подумал, что тупо случайный граф по ближайшим соседям, но по картинке заподозрил неладное. Теперь стало гораздо понятнее.
А для чего нужно было симулировать эррозию? Интересно конечное практическое применение: был ли это GameDev, или собственно развлекательное программирование или что-то научно-промышленно?
А для чего нужно было симулировать эррозию? Интересно конечное практическое применение: был ли это GameDev, или собственно развлекательное программирование или что-то научно-промышленно?
Не, для промышленного обычно используется симуляция на регулярной сетке. А так эррозия (или её подобие) нужна везде, где нужен более-менее реалистичный ландшафт. В частности я балуюсь всяческой процедурной генерацией (больше из любопытства, чем по делу).
Вот хороший пример использования Вороного для прокладки рек.
Вот хороший пример использования Вороного для прокладки рек.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм Форчуна, подробности реализации