有没有更有效的圆纹理方法?

Question

我正在尝试创建一个随机生成的"行星"(圆)，我希望水，土地和树叶的区域由柏林噪声或类似的东西决定。目前我有这个(psudo)代码：

for (int radius = 0; radius < circleRadius; radius++) {
for (float theta = 0; theta < TWO_PI; theta += 0.1) {
float x = radius * cosine(theta);
float y = radius * sine(theta);
int colour = whateverFunctionIMake(x, y);
setPixel(x, y, colour);
}
}

这不仅不起作用(由于精度问题，圆圈中存在"间隙")，而且速度非常慢。即使我通过将增量更改为 0.01 来提高分辨率，它仍然缺少像素，甚至更慢(我在使用 Java 的平庸计算机上获得 10fps(我知道不是最好的)和 0.01 的增量。这对于游戏来说当然是不可接受的)。

我怎样才能在计算成本低得多的同时获得类似的结果？

提前谢谢。

Answer 1

为什么不使用：

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

很简单：

int x0=?,y0=?,r=?; // your planet position and size
int x,y,xx,rr,col;
for (rr=r*r,x=-r;x<=r;x++)
for (xx=x*x,y=-r;y<=r;y++)
if (xx+(y*y)<=rr)
{
col = whateverFunctionIMake(x, y);
setPixel(x0+x, y0+y, col);   
}

全部在整数上，没有浮动或缓慢的操作，没有间隙......不要忘记使用兰德籽进行着色功能...

[编辑1] 更多的东西

现在，如果你想要速度，你需要直接的像素访问(在大多数平台中，像素，SetPixel，PutPixel等都是懒惰的，因为它们执行了很多东西，如范围检查，颜色转换等...... 如果您可以直接访问像素或渲染到您自己的数组/图像中，则需要添加屏幕剪辑(因此您无需检查每个像素的像素是否在屏幕内)，以避免在圆圈重叠屏幕时违反访问冲突。

如注释中所述，您可以使用以前的值摆脱x*x并在内部循环y*y(因为两个x,y都只是递增)。有关它的详细信息，请参阅：

• 32 位 SQRT 在 16T 中，无需乘法

数学是这样的：

(x+1)^2 = (x+1)*(x+1) = x^2 + 2x + 1

因此，我们不是xx = x*x而是xx+=x+x+1尚未增加x，或者如果x已经增加，则xx+=x+x-1。

当放在一起时，我得到了这个：

void circle(int x,int y,int r,DWORD c)
{
// my Pixel access
int **Pixels=Main->pyx;         // Pixels[y][x]
int   xs=Main->xs;              // resolution
int   ys=Main->ys;
// circle
int sx,sy,sx0,sx1,sy0,sy1;      // [screen]
int cx,cy,cx0,    cy0    ;      // [circle]
int rr=r*r,cxx,cyy,cxx0,cyy0;   // [circle^2]
// BBOX + screen clip
sx0=x-r; if (sx0>=xs) return; if (sx0<  0) sx0=0;
sy0=y-r; if (sy0>=ys) return; if (sy0<  0) sy0=0;
sx1=x+r; if (sx1<  0) return; if (sx1>=xs) sx1=xs-1;
sy1=y+r; if (sy1<  0) return; if (sy1>=ys) sy1=ys-1;
cx0=sx0-x; cxx0=cx0*cx0;
cy0=sy0-y; cyy0=cy0*cy0;
// render
for (cxx=cxx0,cx=cx0,sx=sx0;sx<=sx1;sx++,cxx+=cx,cx++,cxx+=cx)
for (cyy=cyy0,cy=cy0,sy=sy0;sy<=sy1;sy++,cyy+=cy,cy++,cyy+=cy)
if (cxx+cyy<=rr)
Pixels[sy][sx]=c;
}

这将呈现一个半径512 px的圆，~35ms以便23.5 Mpx/s在矿井设置时填充(AMD A8-5500 3.2GHz Win7 64 位单线程 VCL/GDI 32 位应用程序，由 BDS2006 C++ 编码)。只需将直接像素访问更改为您使用的样式/API 即可...

[编辑2]

要测量 x86/x64 上的速度，您可以在此处使用 ASM 指令RDTSC一些我很久以前使用的古老C++代码(在没有本机 64 位内容的 32 位环境中)：

double _rdtsc()
{
LARGE_INTEGER x; // unsigned 64bit integer variable from windows.h I think
DWORD l,h;       // standard unsigned 32 bit variables
asm {
rdtsc
mov l,eax
mov h,edx
}
x.LowPart=l;
x.HighPart=h;
return double(x.QuadPart);
}

它会返回 CPU 自通电以来经过的时钟。请注意，您应该考虑溢出，因为在快速机器上，32 位计数器会在几秒钟内溢出。此外，每个内核都有单独的计数器，因此请将关联设置为单个 CPU。在测量前的变速时钟上加热 upi CPU 通过一些计算并转换为时间只需除以 CPU 时钟频率。要获得它，只需执行以下操作：

t0=_rdtsc()
sleep(250);
t1=_rdtsc();
fcpu = (t1-t0)*4;

和测量：

t0=_rdtsc()
mesured stuff
t1=_rdtsc();
time = (t1-t0)/fcpu

如果t1<t0溢出，则需要再次将常量添加到结果或度量。此外，测量的过程必须少于溢出时间。要提高精度，请忽略操作系统粒度。有关详细信息，请参阅：

• 测量缓存延迟
• 系统上的缓存大小估计？ 设置关联示例
• 使用背靠背rdtsc进行负时钟周期测量？