半透明の壁といくつかの光源を持つ長方形の領域があります。平面図のみを考慮しているため、2D の問題です。エリアの各ポイントでおおよその照明 (信号強度) を見つける必要があります。
アルゴリズムを本当に高速にする必要があります。ブルートフォース方式は、私たちの目的には遅すぎました。すべての壁が同じ量だけ減衰すると想定できます。減衰量が一定であっても許容されます。
領域は最大で 1000x1000 で、光源の数は 100 を超えません。光源の範囲は約 50 ～ 100 単位 (無限ではありません)。より高速だが近似アルゴリズムは大歓迎です。
前もって感謝します！
私が試したのは、基本的に力ずくの方法でした。各サンプル ポイントを各壁と光源と比較して、その明るさを決定しました。明らかに、それは O(n^3) であり、容認できないほど遅いです。
時間までに、特定の制限を意味するものではありませんでしたが、画像全体を 100 ミリ秒以内またはそれより速く処理できればよいでしょう。覚えておいてください、私はスピードほど正確さを必要としません。
暗闇の中で突き刺すだけです:(GPUで高速化された）フォトンマッピングを調べましたか？
品質を直線的に失うことにより、同様のアルゴリズムの実行時間を2次的に短縮できます（たとえば、2番目のxとyごとにスキップします）（画像の直径が半分になり、同じサイズにリサンプリングします）。
ビットマップを使用して光度を保存し、すべてのポイントラインatcを小さいサイズのビットマップ（近似係数で除算）でレンダリングし（ただし、すべてのポイントを近似係数で除算します）、ガウスぼかしを使用して目的のサイズにリサンプリングします。次に、ピクセルから明度を抽出します。
私はYouTubeにビデオをアップロードして、それが機能するかどうかを試すためにコードを実行したテストの実行を示しました。それはあなたが必要とするものに似ているようです（単一のスレッドで「ほぼリアルタイム」でそれを行う）：
もちろん、ここでは壁は透明度のある線であり、光は期待どおりに拡散せず、直線的に拡散しますが、「近似」はアルゴリズムで使用できる必要があります。速度が十分な場合は、これを適応させることができます。そして、私が単に実験していたので、コードが非常にひどく書かれていることに注意してください。
ここでは、光度が正規化されています。おそらく、対数目盛の光度をピクセルに埋め込むことで、元の値を維持するために、より広い範囲に合わせることができます。
あなたはそれを何かに使うことができますか：これがプロジェクトです：
最適化してスレッド化すると、直径300のライトが100個あり、長さが200の壁が20個ある、1000x1000の画像の場合はおそらく100ミリ秒で、約5が達成可能です。