在圖像中查找單獨的塊

Question

對於某個項目，我有一個有點不尋常的問題，我沒有找到任何答案。我建立了一個遊戲，嚴重依賴圖像處理來處理每像素碰撞和非常頻繁的tickrate計算，我需要做的事情之一是檢查一個圖像（在這種情況下，代表一艘船）被破壞並且構成不止一個部分。

例子：

正如你可以看到這個船分割（比如通過一些武器影響）和左翼現在已經摺斷。我需要確定哪些像素是分開的（例如通過用0標記它們的alpha通道）。

到現在爲止，我的程序的圖像處理部分的方法涉及DirectCompute。它可以有效地工作，因爲所有當前實現的功能都可以並行化 - 比方說，計算圖像質量的中心就像平均α不爲0的像素的位置一樣容易。

這個問題是不同的。我一開始就想到的是在該位置使用駕駛艙位置（即船的核心）和填充（使用alpha> 0作爲連接），然後過濾未在操作中更改的像素。然而，這個操作是不可並行化的（floodfill本質上是遞歸的）並且在CPU端實現它會導致巨大的性能損失或可見的滯後（降低tickrate使得分裂反應非常無響應）。

這個問題可以在並行的基礎上解決嗎，還是我需要訴諸某種其他技術？任何幫助表示讚賞:)

Answer 1

這裏有幾個問題：

是否檢測到它破損或檢測片 - 我認爲後者是根據您的描述

洪水填充並非天生遞歸，可以通過在隊列上運行來加以說明;並從這個答案開始Is there a parallel flood fill implementation?給出了基本的基本原理，雖然不是如何實現它;你必須思考並弄清楚如何實現它（用「並行填充」搜索會給你很多結果）。

至於其他的想法，這是連接組件分析，它基本上是你所描述的洪水填充。