アイソグリッド上のマップブラシのためのMidpoint Circleよりも優れたアルゴリズム

Question

私はこのisoグリッドゲーム（より正確には、dimetric投影、典型的なダイヤモンドレイアウトで索引付けされています）で作業しています。あなたはどんな画像編集ソフトウェアでもそうです。私はMidpoint Circle Algorithmで始めたが、結果は、私は小さなブラシサイズ

1〜7、私はむしろこのような何かを持っているでしょうのために欲しいもののように見えていないことを、すぐに気づいた：

もちろん容易であること、最初の円が満たされていないことを、無視します。 isoグリッドでシェイプ生成に適したアルゴリズムはありますか？私はおそらく円形の形をしたくないですが、四角形と十字形/ x形を交互に使います。ここで

はウィキペディアから撮影した最初の画像サンプルのコードです：

static List<IntVector2> GetBrushCircleCoords(int x0, int y0, int radius) 
{ 
    List<IntVector2> coords = new List<IntVector2>(); 
    int x = radius; 
    int y = 0; 
    int err = 0; 

    while (x >= y) 
    { 
     coords.Add(new IntVector2(x0 + x, y0 + y)); 
     coords.Add(new IntVector2(x0 + y, y0 + x)); 
     coords.Add(new IntVector2(x0 - y, y0 + x)); 
     coords.Add(new IntVector2(x0 - x, y0 + y)); 
     coords.Add(new IntVector2(x0 - x, y0 - y)); 
     coords.Add(new IntVector2(x0 - y, y0 - x)); 
     coords.Add(new IntVector2(x0 + y, y0 - x)); 
     coords.Add(new IntVector2(x0 + x, y0 - y)); 

     y += 1; 
     err += 1 + 2 * y; 
     if (2 * (err - x) + 1 > 0) 
     { 
      x -= 1; 
      err += 1 - 2 * x; 
     } 
    } 
    return coords; 
} 

Answer 1

あなたの等角投影グリッドのレイアウトを指定しませんでした。私はそこに実装する方が簡単なので、ダイヤモンドを仮定しています。しかし、整数演算では、実際には半径の半分のセル分解能を実装するのは難しいです。完全なセル分解能の半径ディスクの充填のために、内円試験を伴う簡単な2つのネストされたforを使用する。

ちょうど私のアイソメエディタの木とタイルリストオーバーレイを無視する：結果は次のようになります。ここでは、このためのC++ソースコードは：より良い探して結果を微調整四捨五入いくつかの整数で

(x-x0)^2+(y-y0)^2<=r^2 

：

void isometric::brush_circle(int x0,int y0,int z0,int r) 
    { 
    r--; if (r<0) return; 
    int tp=16; // filling tile 
    int x,y,rx,ry,rxx,ryy,rr=(r+1)*(r+1)-(r>>1); 

    if ((z0>=0)&&(z0<gzs)) 
    for (rx=-r,x=x0+rx,rxx=rx*rx;rx<=r;rx++,x++,rxx=rx*rx) 
    for (ry=-r,y=y0+ry,ryy=ry*ry;ry<=r;ry++,y++,ryy=ry*ry) 
     if (rxx+ryy<rr) 
     if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) 
     map[z0][y][x]=tp; 

    _redraw=true; 
    } 

これは、ディスク/円の方程式を使用しています。コードは、私のこのアイソメトリックエンジンに基づいています：あなたが実装する場合

：結果エッジのスムージングを適用した後

• Improving performance of click detection on a staggered column isometric grid

このようなものです半セル半径の解像度にはさらに多くのオプションがあります：

の
1. 使用浮動または固定小数点算術演算
2. （丸め回避して）それに応じので、あなただけの方程式を更新する代わりにradius のオペランドを呼び出すとして使用diameter私は＃2そこらのために行く

使用：

(x-x0)^2+(y-y0)^2<=(d^2)/4 

最も近いのはこれですd=2）：

void isometric::brush_circle(int x0,int y0,int z0,int d) 
    { 
    if ((z0<0)||(z0>=gzs)) return; 
    int tp=16; // filling tile 
    int x,y,rx,ry,rxx,ryy,r=(d>>1)+1,rr=((d*d)-(d>>1))>>2; 
    if (d==2) 
     { 
     x=x0; y=y0; if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp; 
     x++;  if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp; 
     y++;  if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp; 
     x--;  if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp; 
     } 
    else 
    for (rx=-r,x=x0+rx,rxx=rx*rx;rx<=r;rx++,x++,rxx=rx*rx) 
     for (ry=-r,y=y0+ry,ryy=ry*ry;ry<=r;ry++,y++,ryy=ry*ry) 
     if (rxx+ryy<=rr) 
     if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) 
     map[z0][y][x]=tp; 
    _redraw=true; 
    } 

それは少なくとも一つの特殊なケースを追加する必要があり、またはrr定数もう少し微調整のように見えます。

[EDIT1]昼食の後、一部はもっと教え...はるかに良いビュー方程式の整数観点から

は次のとおりです。

4*((x-x0)^2 + (y-y0)^2) <= (d^2) 

どのように

void isometric::brush_circle(int x0,int y0,int z0,int d) 
    { 
    if ((z0<0)||(z0>=gzs)) return; 
    int tp=16; // filling tile 
    int x,y,rx,ry,rxx,ryy,r=(d>>1)+1,dd=(d*d)+d; 
    if (d==2) 
     { 
     x=x0; y=y0; if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp; 
     x++;  if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp; 
     y++;  if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp; 
     x--;  if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp; 
     } 
    else 
    for (rx=-r,x=x0+rx,rxx=rx*rx;rx<=r;rx++,x++,rxx=rx*rx) 
     for (ry=-r,y=y0+ry,ryy=ry*ry;ry<=r;ry++,y++,ryy=ry*ry) 
     if ((rxx+ryy)<<2<dd) 
     if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) 
     map[z0][y][x]=tp; 
    _redraw=true; 
    }