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

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

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

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

MiraПостоялецwww13 ноя. 20170:32#0
есть такая битовая карта
+ Показать

на ней есть участки пикселей определенного цвета.
как можно вычислить все такие кластеры и узнать примерно центральный пиксель в них.
+ Показать

на ум чето не приходит годных алгоритмов...

в идеале чтоб эти кластеры создавались в процессе попиксельного добавления добавления , а не постпроцессинг.
типа : хоп добавился пиксель, если он нисчем не связан - то создаем новый кластер, если примыкает - то добавляем в имеющийся. при слиянии чтоб объединялись в один.

кто что может посоветовать?

интересно какой структурой хранить эти кластеры, и максимально быстро находить примыкание к ним. не массивом же?

Правка: 13 ноя. 2017 0:48

skalogryzПостоялецwww13 ноя. 20170:56#1
Массив(или список)-списков. В каждом элементе начальный пиксель и длинна отрезка, а также нормер (ну или объект указывающий на кластер)

Прт добавлении пиксела в x, y
Пробегаешь список[y], и либо меняшь один из элементов (пиксель рядом с кластером, либо добовляешь новый, либо слияние)
Потом делаешь подобную проверку для [y-1], [y+1]

Если маска маленькая то можно и двумерный массив

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

MiraПостоялецwww13 ноя. 20170:58#2
skalogryz
в каждом пикселе чтоли хранить ссылку ссылку? жестковато но вариант конечно..
skalogryzПостоялецwww13 ноя. 20171:02#3
В каждом пикселе, это только если двумерный массив.
В списке хранить только кластерные пиксели. При это хранить их как первый пиксель+длинна

Правка: 13 ноя. 2017 1:03

MiraПостоялецwww13 ноя. 20171:09#4
сразу скажу что задачка для поиска пути. например это процедурно сгенереные лужи, и нужно найти ближайшую в которую залезть.
возможно еще есть какойто способ заставить пазфиндер зайти в "ближайшую лужу", но пока не придумал как =)
MiraПостоялецwww13 ноя. 20171:23#5
еще можно попытаться Breadth First или Djkstra алгоритмом найти ближайшую, но он прожорливый писец. поэтому зная направления поиска кластеров можно использовать эвристические методы, куда более шустрые и эффективные

Правка: 13 ноя. 2017 1:24

skalogryzПостоялецwww13 ноя. 20172:15#6
А*
skalogryzПостоялецwww13 ноя. 20173:06#7
Подумал ещё над тем вариантом, если «лужи» начнут «высыхать»
Если пиксель убрали, то куски кластера (к которому принадлежал пиксель) нужно проверять на сохранение целостности.

Либо заново пересматривать карту

SuslikМодераторwww13 ноя. 20173:19#8
ну соседний тред же http://www.gamedev.ru/code/forum/?id=231381
MrShoorУчастникwww13 ноя. 20173:32#9
Mira
Выглядит как что-то простое. Сложить все зеленые пиксели в хешсет (в делфи можно взять TDictionary<TVec2i, boolean>). Брать из хешсета первый попавшийся, и выгребать всех соседей (попутно удаляя из хешсета), как только соседей не останется - кластер закончен, можно выгребать новый первый попавшийся пиксель из хешсета. Короче проще кодом объяснить
TCluster = TList<TVec2i>;

procedure BuildClusters(const AClusters: TList<TCluster>);
  procedure ExtractCluster(const APt: TVec2i; const ACluster: TCluster; const AGreens: TDictionary<TVec2i, boolean>);
  begin
    if not AGreens.Contains then exit; //пиксель либо не зеленый, либо уже был обработан
    //добавляем не обработанный пиксель в текущий кластер
    AGreens.Remove(APt);
    ACluster.Add(APt);  
    //и выполняем то же самое для соседей
    ExtractCluster(Vec(APt.x+1, APt.y), ACluster, AGreens);
    ExtractCluster(Vec(APt.x-1, APt.y), ACluster, AGreens);  
    ExtractCluster(Vec(APt.x, APt.y+1), ACluster, AGreens);
    ExtractCluster(Vec(APt.x, APt.y-1), ACluster, AGreens);
  end;
var 
  i, j: Integer;
  greens: TDictionary<TVec2i, boolean>;
  pt: TVec2i;
  newcluster: TCluster;
begin
  greens := TDictionary<TVec2i, boolean>.Create;

  // добавляем все зеленые пиксели
  for j := 0 to Map.Height - 1 do
    for i := 0 to Map.Width - 1 do
      if Map[i, j].IsGreen() then 
        greens.Add(Vec(i, j), false);

  // пока в greens есть пиксели - у нас будут кластеры
  while greens.Count > 0 do
  begin
    for pt in greens.Keys do //извлекаем первый попавшийся пиксель, чтобы от него строить кластер
    begin
      newcluster := TCluster.Create;
      ExtractCluster(pt, newcluster, greens);
      AClusters.Add(newcluster);
      Break; // мы удаляли из greens, значит итератор не валидный
    end;
  end;
end;

Правка: 13 ноя. 2017 3:41

MrShoorУчастникwww13 ноя. 20173:40#10
Код выше - это именно постпроцесс.
Для:
в идеале чтоб эти кластеры создавались в процессе попиксельного добавления добавления , а не постпроцессинг.
типа : хоп добавился пиксель, если он нисчем не связан - то создаем новый кластер, если примыкает - то добавляем в имеющийся. при слиянии чтоб объединялись в один.

в случае добавления пикселей все тривиально. Добавляем пиксель, поверяем 4-х соседей. Если среди соседей
  • 0 кластеров. Значит пиксель становится новым кластером
  • 1 кластер. Значит пиксель добавляется в этот кластер
  • >=2 кластров. Значит все эти кластеры нужно объединить в один, а пиксель добавить в получившийся один кластер.

    В случае удаления пикселя уже не все так тривиально. Возможно там и есть какой-то интересный алгоритм, позволяющий сделать все быстро, но скорее всего придется постпроцессить. Постпроцесс можно сильно локализовать. Достаточно рассматривать только один кластер. Для этого подойдет код выше, но только изменить чуть заполнение greens вначале, и заполнять его не из карты, а из кластера.

    Было:

      // добавляем все зеленые пиксели
      for j := 0 to Map.Height - 1 do
        for i := 0 to Map.Width - 1 do
          if Map[i, j].IsGreen() then 
            greens.Add(Vec(i, j), false);
    Заменить на:
      for i := 0 to OldCluster.Count - 1 do
        greens.Add(OldCluster[i], false);

  • Правка: 13 ноя. 2017 3:41

    skalogryzПостоялецwww13 ноя. 20174:14#11
    Рассмотреть нужно все 4 кластера рядлм с удалённым пикселеи (нр удалили центр креста)
    (Полный) Постпроцесс точно не нужен
    MrShoorУчастникwww13 ноя. 20174:32#12
    skalogryz
    > Рассмотреть нужно все 4 кластера рядлм с удалённым пикселеи (нр удалили центр креста)
    > (Полный) Постпроцесс точно не нужен
    Ну рассмотрели. И какой вывод из этого можно сделать?
    skalogryzПостоялецwww13 ноя. 20174:59#13
    MrShoor
    > Ну рассмотрели. И какой вывод из этого можно сделать?
    (понятно, что все соседние отрезки к удалённо пикселу принадлежат одному класетру)
    при рассмотрении каждого из соседних к удаёлнном пикеселу отрезков, нужно помечать "общим цветом" каждый соседний отрезок (через обход графа).
    + Показать

    Такой обход не попадут те отрезки, которые принадлежали тому же кластеру, но соседей уже не имеют.

    т.к. рассмотреть нужно каждого из соседей удалённого пиксела, то в итоге все все рассоединённые отрезки (и их соседи) получат свой "уникальный цвет".

    В частном случае 2д поля, "худший" случай это разбиение 1 кластера на 4.

    Метод эффективен, если данные находятся соответсвтующей структуре, и у отрезка есть данные о его соседях.

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

    MrShoorУчастникwww13 ноя. 20175:18#14
    skalogryz
    Ну так ты все равно переберешь весь кластер, из которого удалили пиксель. У меня ровно такая же сложность алгоритма в посте #10.

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

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

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