二維光柵圖像視線算法

我正在研究一個簡單的繪圖應用程序以獲得樂趣，我需要做的事情之一是查找（並着色）從當前位置可見的所有點。在這種情況下，點是像素。我的地圖是一個光柵圖像，透明像素是開放的空間，其他任何像素都是不透明的。（沒有半透明像素; alpha可以是0或100％）。從這個意義上講，它有點像普通的泛洪填充，約束是每個填充的像素必須有一個清晰的視線原點。下圖顯示了一對情侶在有色等方面的（微小的十字線的原點，而白色=透明）：二維光柵圖像視線算法

（http://tinyurl.com/nf3nqa4）

此外，什麼我對最終感興趣的點是「邊框」其他顏色，即我想要組成可見區域邊緣的點列表。

我目前和非常低效的解決方案是上面描述的修改後的填充填充。此方法返回正確的結果，但由於需要將每行上的每個像素都迭代到洪水填充中每個像素的原點，所以它非常緩慢。我的圖像縮小了尺寸並進行了量化，但我仍然需要大約100萬像素以獲得可接受的精度，而典型的LoS區域每個像素至少有100,000個像素。

我可能會使用錯誤的搜索條件，但我一直沒能找到解決這個（柵格化）LoS情況的算法的任何討論。

來源

2013-08-29 Luk232

我懷疑如果你的「牆」被表示爲方程而不是光柵圖像中的像素，那麼這可以更有效地完成。例如，多邊形/三角形，圓形，橢圓形。

然後它就像2D中的光線跟蹤（搜索這個術語）。換句話說，您可以考慮從圖像中的每個像素到感興趣的點的射線/線條，並且僅當像素與任何對象不相交時才爲像素着色。

此方法確實要求您測試圖像中每個像素與每個對象的交點;然而，如果你查看光線跟蹤，你會發現一些有效的方法來測試這些交點。他們將主要用於3D案例，但它應該直接將它們轉換爲2D。

在很多較大的圖像上有很快的3D光線追蹤，所以這應該是非常可行的。

來源

2013-08-29 02:54:13 idfah

感謝您的建議！我熟悉光線追蹤技術，但不幸的是我的輸入數據全部來自照片，我通過過濾/量化生成透明區域。與我提供的原始樣本圖像不同，實際區域是不規則的形狀 - 不是（通常情況下）任何我可以用小數量的多邊形，橢圓或曲線近似的東西。或者還有其他方法可以解決嗎？ – Luk232

@ Luk232我明白了，你現在的算法是如何工作的？你用Bresenham的？你是否圍繞圖像的邊緣/邊界移動或者檢查每個像素？ – idfah

@ Luk232另外，您是指「與其他顏色相接的點」是什麼意思？你是指所有興趣點的視線邊界的結合？ – idfah

您可以嘗試每種顏色的delaunay三角測量。我的意思是你可以嘗試用DT找到每種顏色的形狀。

來源

2013-08-29 05:16:14 Bytemain

感謝您的支持，但恐怕我不會關注。我瞭解DT算法，只是不適用於我的問題。你介意給你的想法多一點細節？ – Luk232

我的意思是你可以嘗試用DT找到每種顏色的形狀。 – Bytemain

二維光柵圖像視線算法

回答

相關問題