19

計算上高速な方法で「ブロブ」を作成しようとしています。ここでのブロブは、任意の形状のピクセルの集合として定義されますが、すべて接続されています。例:

.ooo....  
..oooo..  
....oo..  
.oooooo.
..o..o..  

...ooooooooooooooooooo...  
..........oooo.......oo..  
.....ooooooo..........o..  
.....oo..................  


......ooooooo....  
...ooooooooooo...  
..oooooooooooooo.  
..ooooooooooooooo  
..oooooooooooo...  
...ooooooo.......  
....oooooooo.....  
.....ooooo.......  
.......oo........

どこ 。はデッド スペースであり、o はマークされたピクセルです。「バイナリ」生成のみを気にします-ピクセルはオンまたはオフです。たとえば、これらは架空のケチャップの塊、架空のバクテリア、その他の有機物質のように見えます。

どのようなアルゴリズムでこれを達成できますか? 私は本当に途方に暮れています

4

3 に答える 3

24

David Thonley のコメントは正しいですが、「有機的な」形状と滑らかなエッジを持つブロブが必要であると仮定します。そのために、メタボールを使用できます。メタボールは、スカラー フィールドで動作するベキ関数です。スカラー フィールドは、マーチング キューブ アルゴリズムを使用して効率的にレンダリングできます。ボールの数、位置、半径を変えることで、さまざまな形を作ることができます。

2D メタボールの概要については、https: //web.archive.org/web/20161018194403/https ://www.niksula.hut.fi/~hkankaan/Homepages/metaballs.html を参照してください。

マーチング キューブ アルゴリズムの紹介はこちら: https://web.archive.org/web/20120329000652/http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/

3D での交点の 256 の組み合わせは、2D では 16 の組み合わせのみであることに注意してください。実装はとても簡単です。

編集：

GLSL シェーダーを使った簡単な例をまとめました。これは、hkankaan のホームページのエネルギー関数を使用して、50 個のブロブを使用した結果です。 代替テキスト

これは実際の G​​LSL コードですが、このフラグメントごとに評価します。マーチング キューブ アルゴリズムは使用していません。機能させるには、全画面クワッド (2 つの三角形) をレンダリングする必要があります。vec3 ユニフォーム配列は、 で渡された個々のブロブの単純な 2D 位置と半径ですglUniform3fv。

/* Trivial bare-bone vertex shader */
#version 150
in vec2 vertex;
void main()
{
    gl_Position = vec4(vertex.x, vertex.y, 0.0, 1.0);
}

/* Fragment shader */
#version 150
#define NUM_BALLS 50
out vec4 color_out;
uniform vec3 balls[NUM_BALLS]; //.xy is position .z is radius

bool energyField(in vec2 p, in float gooeyness, in float iso)
{
    float en = 0.0;
    bool result = false;
    for(int i=0; i<NUM_BALLS; ++i)
    {
        float radius = balls[i].z;
        float denom =  max(0.0001, pow(length(vec2(balls[i].xy - p)), gooeyness));
        en += (radius / denom);
    }
    if(en > iso)
        result = true;
    return result;
}
void main()
{
    bool outside;
    /* gl_FragCoord.xy is in screen space / fragment coordinates */
    outside = energyField(gl_FragCoord.xy, 1.0, 40.0);
    if(outside == true)
        color_out = vec4(1.0, 0.0, 0.0, 1.0);
    else
        discard;
}
于 2010-08-27T20:42:36.627 に答える
1

おそらく、一連のランダムな迷路生成アルゴリズムのマイナーな変形である、これを行うアルゴリズムを設計できます。ユニオン検索法に基づいたものを提案します。

union-find の基本的な考え方は、ばらばらな (重複しない) サブセットに分割されたアイテムのセットが与えられた場合に、特定のアイテムが属するパーティションをすばやく識別することです。「結合」は、2 つのばらばらなセットを結合してより大きなセットを形成することであり、「検索」は、特定のメンバーが属するパーティションを決定することです。セットの各パーティションはセットの特定のメンバーによって識別できるため、ポインターがメンバーからルートに向かってメンバーを指すツリー構造を形成できます。最初に各パーティションのルートを見つけ、次に一方のルートの (以前は null) ポインタを変更して他方を指すようにすることで、(それぞれに任意のメンバを指定して) 2 つのパーティションを結合できます。

問題を互いに素な和集合の問題として定式化できます。最初は、個々のセルはそれぞれ独自のパーティションです。必要なのは、接続されたセルのパーティションが少数 (必ずしも 2 つとは限りません) になるまで、パーティションをマージすることです。次に、パーティションの 1 つ (おそらく最大のもの) を選択して描画します。

セルごとに、結合用のポインター (最初は null) が必要になります。隣接するセルのセットとして機能するには、おそらくビット ベクトルが必要になるでしょう。最初は、各セルには 4 つ (または 8 つ) の隣接するセルのセットがあります。

反復ごとにセルをランダムに選択し、ポインター チェーンをたどってそのルートを見つけます。ルートからの詳細では、その隣接セットが見つかります。その中からランダムなメンバーを選択し、そのルートを見つけて、隣接する領域を特定します。2 つの領域をマージするには、結合 (一方のルートを他方に向けるなど) を実行します。領域の 1 つに満足するまで繰り返します。

パーティションをマージする場合、新しいルートの新しい隣接セットは、前の 2 つのルートの隣接セットのセット対称差 (排他的論理和) になります。

各ルート要素でパーティション (サイズなど) を拡大するときに、おそらく他のデータを維持したいと思うでしょう。これを使用して、特定のユニオンを進めることについてもう少し選択的になり、いつ停止するかを決定するのに役立ちます。パーティション内のセルの散乱の何らかの尺度が関連している可能性があります。たとえば、小さな逸脱または標準偏差 (大きなセル数と比較して) は、おそらく密集したほぼ円形のブロブを示しています。

終了したら、すべてのセルをスキャンして、選択したパーティションの一部であるかどうかをテストし、個別のビットマップを作成します。

このアプローチでは、反復の開始時にセルをランダムに選択すると、より大きなパーティションを選択する傾向が強くなります。隣人を選択する場合、より大きな隣接パーティションを選択する傾向もあります。これは、明らかに優勢な 1 つのブロブを非常に迅速に取得する傾向があることを意味します。

于 2010-08-27T20:41:32.497 に答える