6

密度テクスチャといくつかのポイントを持つ (おそらく開いた) メッシュが与えられた場合、メッシュの密度に従ってこれらのポイントを分散する必要があります。

これまでのところ、いくつかのソリューションを作成してきましたが、そのうちのいくつかは機能し、他のソリューションは機能しませんでした。私が試したアルゴリズムの 1 つは、ポイントをスプリングで接続し、平衡になるまで (またはソリューションがユーザーのニーズに適合するまで) 分布をシミュレートすることでした。ソースのリタイリング ポリゴン サーフェス 残念ながら、これはポイント数が多い場合 (>2k) には多少時間がかかるため、ポイント数が多い場合には実現可能なソリューションが必要です。

すでにいくつかのアイデアがありますが、これに対する標準的な解決策があるかどうかを知りたいです。私はグーグルを試しましたが、私が使用したキーワード（分布密度離散）は、私以外の問題を処理するページしか表示しませんでした. ですから、検索するのに適切な単語を教えていただければ幸いです。

4

3 に答える 3

5

一般に、任意の密度関数を持つ任意の空間にわたって、棄却サンプリングを介して妥当な近似を得ることができます。

  • あなたの最大密度を見つけてくださいD。
  • ランダムな点を選びますp。
  • r範囲から乱数を選択します[0,D)。
  • の密度pが、より大きい場合は、ポイントの1つとしてr受け入れpます。

これをあなたのケースに適用するのがどれほど簡単かはわかりません。メッシュ全体にランダムで均一に分散されたポイントを生成すること自体は、難しい問題のように聞こえます。私が考えることができる唯一の解決策は、メッシュ内のすべての三角形の面積を計算し、その面積に比例する確率で三角形をランダムに選択し、三角形内のランダムな点を選択することです。この選択は、N個の三角形のO（logN）で実行できると思います。

しかし、これらのポイントのほとんどを捨てる可能性があることを考えると、十分な大きさのメッシュと不快な十分な密度関数（つまり、平均よりもはるかに大きい最大値を持つもの）を考えると、これは現在のアプローチよりもはるかに悪い結果になる可能性があります。


他の種類のランダムサンプリングと同様に、基礎となる分布に似始めるまでにはかなりのポイントが必要です。ポイントの小さなセットは、おそらく多かれ少なかれランダムに見えます。しかし、ポイント配置のある種の準ランダムな方法でこれを回避できる可能性があります（そして、大きなセットでも、より良い結果が得られる可能性があります）。

頭に浮かぶことの1つは、上記のアプローチと@BlackBearのアルゴリズムのハイブリッドです。各三角形の面積と平均密度を計算し、これを使用して、各三角形に含まれる必要のあるポイントの数を決定できます。次に、実際に三角形内にポイントを配置するには、棄却サンプリング法を使用します。

于 2012-02-15T15:23:14.093 に答える
4

ここに私の考えがあります：

  1. 密度テクスチャを等しい長方形の部分に分割します。
  2. 各パーツについて、0.0 から 1.0 の間の数値を計算します。ここで、1.0 は「ポイントの密度が最も高い」ことを意味し、0.0 はその反対である「ポイントがまったくない」ことを意味します。
  3. 配置するポイントの合計数とすべての平均値の合計を割って、1.0 値に対応するポイント数を計算します。
  4. 次に、すべての長方形に描画する必要があるポイントの数がわかるので、それらを均一に描画します。

長方形が小さいほど、より正確な結果が得られます。私は小さなテスト プログラム (遅いメソッド、つまりビットマップで GetPixel と SetPixel を使用する C#) を実行しました。ここに、10k ポイント、256x256 ピクセルの画像を想定した結果を示します。写真は、アルゴリズムが 2^2、10^2、50^2、および 90^2 部分で動作することを示しています。

ここに画像の説明を入力

これがベンチマークです。

parts   time
------------------------
2      00:00:00.7957087
10     00:00:00.6713345
50     00:00:00.5873524
90     00:00:00.4153544
于 2012-02-15T15:13:51.440 に答える