旋转二维数组 ->反转循环
我使用以下代码来旋转位掩码(压缩的二维数组)。老实说,我对所使用的算法没有牢固的掌握,我从 pygame 库复制并修改了旋转代码(它用于旋转表面)。由于位掩码的实现,我可以通过反转内部循环来大大加快旋转速度。我的意思是,我需要执行 foreach x { foreach y { ... } }
,而不是执行 foreach y { foreach x { ... } }
。我在反转循环时遇到困难,因为必须以我目前看不到的方式调整三角学。
代码如下:
typedef struct bitmask {
int w,h;
BITMASK_W bits[1];
} bitmask_t;
bitmask_t* bitmask_rotate(const bitmask_t *mask, float angle) {
bitmask_t *newmask = NULL;
double radangle, sangle, cangle;
int isin, icos;
double cx, cy, sx, sy;
int x, y, ax, ay, xd, yd, dx, dy;
int nxmax, nymax, xmaxval, ymaxval;
radangle = angle * DEG_TO_RAD;
sangle = sin(radangle);
cangle = cos(radangle);
isin = (int)(sangle * 65536);
icos = (int)(cangle * 65536);
x = mask->w;
y = mask->h;
cx = cangle*x;
cy = cangle*y;
sx = sangle*x;
sy = sangle*y;
nxmax = (int) (MAX (MAX (MAX (fabs (cx + sy), fabs (cx - sy)), fabs (-cx + sy)), fabs (-cx - sy)));
nymax = (int) (MAX (MAX (MAX (fabs (sx + cy), fabs (sx - cy)), fabs (-sx + cy)), fabs (-sx - cy)));
newmask = bitmask_create(nxmax, nymax, 0);
if (!newmask) return NULL;
cy = newmask->h / 2;
xd = ((mask->w - newmask->w) << 15);
yd = ((mask->h - newmask->h) << 15);
ax = ((newmask->w) << 15) - (int)(cangle * ((newmask->w - 1) << 15));
ay = ((newmask->h) << 15) - (int)(sangle * ((newmask->w - 1) << 15));
xmaxval = ((mask->w) << 16) - 1;
ymaxval = ((mask->h) << 16) - 1;
for (y = 0; y < newmask->h; y++) {
dx = (ax + (isin * (cy - y))) + xd;
dy = (ay - (icos * (cy - y))) + yd;
for (x = 0; x < newmask->w; x++) {
if (!(dx < 0 || dy < 0 || dx > xmaxval || dy > ymaxval)) {
if (bitmask_getbit(mask, dx >> 16, dy >> 16)) {
bitmask_setbit(newmask, x, y);
}
}
dx += icos;
dy += isin;
}
}
return newmask;
}
在人们问“你尝试过什么?”之前,我在维基百科上循环了旋转矩阵,我可以看到那里发生了什么以及他们如何在这个算法中实现它(预先计算起始 dx 和 dy,然后用 icos 和 isin 递增),但是位移和参数我不明白(ax
例如)让我很难跟上。
I use the following code to rotate a bitmask (a packed 2d array). To be honest I do not have a firm grip of the algorithm used, I copied and modified the rotation code from the pygame library (where it was used to rotate surfaces). Due to the implementation of bitmask
I can speed this rotation up a lot by reversing the inner loop. With that I mean, instead of doing foreach y { foreach x { ... } }
I need to do foreach x { foreach y { ... } }
. I have trouble reversing the loop because the trigonometry has to be adapted in a way I don't currently see at this moment.
Here's the code:
typedef struct bitmask {
int w,h;
BITMASK_W bits[1];
} bitmask_t;
bitmask_t* bitmask_rotate(const bitmask_t *mask, float angle) {
bitmask_t *newmask = NULL;
double radangle, sangle, cangle;
int isin, icos;
double cx, cy, sx, sy;
int x, y, ax, ay, xd, yd, dx, dy;
int nxmax, nymax, xmaxval, ymaxval;
radangle = angle * DEG_TO_RAD;
sangle = sin(radangle);
cangle = cos(radangle);
isin = (int)(sangle * 65536);
icos = (int)(cangle * 65536);
x = mask->w;
y = mask->h;
cx = cangle*x;
cy = cangle*y;
sx = sangle*x;
sy = sangle*y;
nxmax = (int) (MAX (MAX (MAX (fabs (cx + sy), fabs (cx - sy)), fabs (-cx + sy)), fabs (-cx - sy)));
nymax = (int) (MAX (MAX (MAX (fabs (sx + cy), fabs (sx - cy)), fabs (-sx + cy)), fabs (-sx - cy)));
newmask = bitmask_create(nxmax, nymax, 0);
if (!newmask) return NULL;
cy = newmask->h / 2;
xd = ((mask->w - newmask->w) << 15);
yd = ((mask->h - newmask->h) << 15);
ax = ((newmask->w) << 15) - (int)(cangle * ((newmask->w - 1) << 15));
ay = ((newmask->h) << 15) - (int)(sangle * ((newmask->w - 1) << 15));
xmaxval = ((mask->w) << 16) - 1;
ymaxval = ((mask->h) << 16) - 1;
for (y = 0; y < newmask->h; y++) {
dx = (ax + (isin * (cy - y))) + xd;
dy = (ay - (icos * (cy - y))) + yd;
for (x = 0; x < newmask->w; x++) {
if (!(dx < 0 || dy < 0 || dx > xmaxval || dy > ymaxval)) {
if (bitmask_getbit(mask, dx >> 16, dy >> 16)) {
bitmask_setbit(newmask, x, y);
}
}
dx += icos;
dy += isin;
}
}
return newmask;
}
Before people are going to ask "what have you tried?", I looped up rotating matrices on Wikipedia, and I could see what is going on there and how they implemented it in this algorithm (precalculate a starting dx
and dy
and then increment with icos
and isin
), but the bitshifts and parameters I don't understand (ax
for example) make it hard for me to follow.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)