Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / кластеризация пикселей оО (2 стр)

кластеризация пикселей оО (2 стр)

Поделиться
Advanced: Тема повышенной сложности или важная.

Страницы: 1 2 3 4 5 Следующая

skalogryzПостоялецwww13 ноя. 20175:54#15
MrShoor
> Ну так ты все равно переберешь весь кластер, из которого удалили пиксель. У
> меня ровно такая же сложность алгоритма в посте #10
согласен!
+ Показать

я больше упираю на:
> интересно какой структурой хранить эти кластеры
твой алгоритм предлагает структуры пересобирать
я предлагаю переиспользовать существующие

Правка: 13 ноя. 2017 6:01

MrShoorУчастникwww13 ноя. 20177:55#16
skalogryz
> мелочь конечно, но у меня такого нет! xD
У тебя пока никакой реализации нет. Предлагаю тебе набросать свою реализацию, и убедиться что эти лишние проверки будут и у тебя. У меня это например обычный dfs, хоть это сразу и не бросается в глаза.

skalogryz
> твой алгоритм предлагает структуры пересобирать
> я предлагаю переиспользовать существующие
От хешсета там особо никуда не уйдешь. А от кластеров через TList можно (но может быть не нужно) избавиться введя поле ClusterID в ячейки карты.

MiraПостоялецwww13 ноя. 20178:40#17
Всем спасибо,  сегодня попробую)  вчера много сделал,  но на это уже не хватило ума.

Я вот че вчера думал, если эти острова большого обьема,  например не лужа а река рядом или озеро, не разумнее ли хранить кластер описанием периметра?  Ибо граф или массив с лужей 700*700 точек монстроузно имхо.  Если допустить что в лужах нет дыр.

MrShoorУчастникwww13 ноя. 20178:51#18
Mira
> не разумнее ли хранить кластер описанием периметра?
Может быть разумнее. Но тогда и сложность алгоритмов возрастает. Поэтому как мне кажется сейчас можно реализовать максимально просто. Главное сделать правильный уровень абстракции, чтобы потом можно было просто заменить реализацию, и не приходилось перелопачивать весь проект.
MrShoorУчастникwww13 ноя. 20178:53#19
Ну и как годная альтернатива предложенному тобой периметру - это sparse карта. Так что пока непонятно как лучше - стоит делать по простому.
MrShoorУчастникwww13 ноя. 201711:10#20
Кстати процесс удаления пикселя можно хорошо соптимизировать дополнительной проверкой вначале.
Если после удаления пикселя все 8 соседей можно представить как один маленький кластер, то запускать проверку по целому кластеру не надо.
MiraПостоялецwww13 ноя. 201711:25#21
В общеи случае,  удаления не будет.  Нужно упор на скорость кластеризации и минимизацию ресурсов. Я думаю,  если наоборот мы окажемся островом на море,  то мы окажемся в центре многомегабайтного кластера не имеющего центра...  Как тогда прокладывать путь до воды?
С мелкими лужицами хватит в принципе хештаблицы,  да.
RuslanПостоялецwww13 ноя. 201711:54#22
Mira
Как вариант, можно запилить шейдером в несколько проходов, что-то вроде того:
- если текущий тексель не "пустой" и рядом находится хотя бы еще один не пустой тексель, тогда текущий тексель помечаем как пустой
- повторяем пока не останутся тексели без "соседей"

MrShoorУчастникwww13 ноя. 201712:32#23
Mira
> Как тогда прокладывать путь до воды?
Дейкстрой. Пока непонятно что ты там мутишь. :)
MiraПостоялецwww13 ноя. 201712:49#24
MrShoor
Представь что эти пиксели водичка,  и нужно найти ближайшую воду. Дейкстра без эвристики,  очень тупой поиск.  Если водичка будет далеко,  то будет поиск по графу огромного размера.  Астар умный,  но ему надо знать куда пробиваться,  поэтому пытаюсь кластеры.  Опять же в случае острова -  выдет херня,  придется костылить
}:+()___ [Smile]Постоялецwww13 ноя. 201715:13#25
Mira
> не разумнее ли хранить кластер описанием периметра?
На мой взгляд, очень интересная идея. По крайней мере, в случае удаления алгоритм упрощается.
Но вот для определения принадлежности пикселя кластеру придется пускать луч.
Соответственно, вместо хешмапы надо использовать просто мапу, в которой пускание луча будет тривиально.
В общем, каждое ребро контура должно быть в мапе по координатам и мапе по длине контура, тогда будет оптимально.
Кстати, один кластер может содержать несколько контуров: основной внешний и произвольное количество внутренних дырок.
MiraПостоялецwww13 ноя. 201717:51#26
MrShoor
попробовал твой код чето он мне из битмапа 500+ кластеров наделал =)
+ Показать

кластеры это красненькое
у тебя вроде логично все, может где сам ошибся -_-

PS а нет все правильно, 5. забыл счетчик инициализировать нулем =)

Правка: 13 ноя. 2017 17:55

skalogryzПостоялецwww13 ноя. 201719:01#27
Mira
> кластеры это красненькое
а синее это что?
работаю над своей версией, со списками отрезков
MiraПостоялецwww13 ноя. 201719:25#28
skalogryz
просто для красоты =)
тоже попробую дополнить этот код дополнить

Правка: 13 ноя. 2017 19:26

MrShoorУчастникwww13 ноя. 201719:39#29
Mira
> Представь что эти пиксели водичка,  и нужно найти ближайшую воду. Дейкстра без
> эвристики,  очень тупой поиск.  Если водичка будет далеко,  то будет поиск по
> графу огромного размера.
Пока тяжело представляется. Сначала я представлял лужи. Потом ты сказал представить остров окруженный водой, когда воды много (а суши значит мало?) и вся память уходит на кластер воды. Теперь ты говоришь,  что вода далеко и дейкстра будет тормозить. Значит суши теперь стало много, а воды мало? Так чтоль?

Страницы: 1 2 3 4 5 Следующая

/ Форум / Программирование игр / Общее

2001—2017 © GameDev.ru — Разработка игр