`
- 浏览:
399988 次
- 性别:
- 来自:
深圳
-
转载:A Fast Algorithm for Rotating Bitmaps
A Fast Algorithm for Rotating Bitmaps By Karl Lager According to "Tricks of the Game Programming Gurus", rotating
a bitmap in real time generally isn't done because of the complex
math involved and slow speed. However, with a few optimizations
it can be done nearly as fast as bitmap scaling.
To start with, each pixel can be given x,y coordinates. To rotate
these by an angle t about the 0 axis , the new coordinates can be
plotted as (x',y') = (x cos(t) - y sin(t), y cos(t) + x sin(t)).
( for x = right, y = down, clockwise rotations. )
To convert a pixel on screen to the bitmap, the directions would be
reversed:
(x',y') = (x cos(t) + y sin(t), y cos(t) - x sin(t);
To rotate a whole bitmap, you can plot
( for y = min_y to max_y
for x = min_x to max_x
x' = (x cos (t) + y sin(t))
y' = (y cos(t) - x cos(t))
if (x', y') is in the bounds of the bitmap,
get pixel(x',y') and plot the pixel to (x,y) on screen.
)
Now, you might want to rotate the bitmap about an arbitrary pixel(x1',y1'),
and put it to an arbitrary point on screen(x1,y1), and to do this you
could get pixel(x'+ x1', y'+ y1') and put it to (x + x1, y + y1) on screen.
To speed this procedure up, you can start by taking the trig equations
out of the inner loop. The angle doesn't change, so these calculations
should only be done once.
double cosT,sinT;
cosT = cos(t);
sinT = sin(t);
for (y = min_y - y1; y <= max_y - y1; y++)
for (x = min_x - x1; x <= max_x - x1; x++)
{ x' = (x * cosT + y * sinT);
y' = (y * cosT - x * sinT);
if (x'+ x1', y'+ y1') is in the bounds of the bitmap,
get pixel(x'+ x1', y'+ y1') and plot the pixel to
(x + x1, y + y1) on screen.
}
Since x and y are incremented by a constant value, the code can be
streamlined further by removing the multiplications from the inner loop:
double cosT,sinT;
cosT = cos(t);
sinT = sin(t);
for (y = min_y - y1; y <= max_y - y1; y++)
{ x' = (min_x-x1) * cosT + y * sinT;
y' = y * cosT - (min_x-x1) * sinT;
for (x = min_x-x1; x <= max_x - x1; x++)
{ if (x'+ x1', y'+ y1') is in the bounds of the bitmap,
get pixel(x'+ x1',y'+ y1') and plot the pixel to
(x + x1,y + y1) on screen.
x' += cosT;
y' -= sinT;
}
}
Finally, remove the extra additions from the inner loops:
double cosT,sinT;
cosT = cos(t);
sinT = sin(t);
for (y = min_y; y <= max_y; y++)
{ x' = (min_x-x1) * cosT + (y-y1) * sinT + x1';
y' = (y-y1) * cosT - (min_x-x1) * sinT + y1';
for (x = min_x; x <= max_x; x++)
{ if (x', y') is in the bounds of the bitmap,
get pixel(x', y') and plot the pixel to
(x, y) on screen.
x' += cosT;
y' -= sinT;
}
}
Thus you have gone from doing 4 transcendental functions (or 4 lookups
and 4 multiplications if you are using lookup tables) per pixel to
doing 2 additions per pixel. That's going from instructions that take
a couple hundred CPU cycles with a coprocessor or thousands without
one to instructions that take one cycle.
Further gains can be made by making your max and min values exactly
fit the bounds of the bitmap and the video screen or window.
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
本论文首次提出了SMO算法,用于优化二次规划问题,显著提高了SVM算法速度和准确性,为机器学习的发展做出了巨大贡献。
Vertex Component Analysis:A Fast Algorithm to Vertex Component Analysis:A Fast Algorithm to Vertex Component Analysis:A Fast Algorithm to
Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem*中文
关于论文MaPle A Fast Algorithm for Maximal Pattern-based Clustering∗的翻译
A Fast Algorithm for Recovery of Jointly Sparse Vectors based on
程序算法来自2009有关反问题的文章《A fast algorithm for the total variation model of image denoising》
It shows howtouse“complementarypriors”toeliminatetheexplaining- awayeffectsthatmakeinferencedifficultindenselyconnectedbeliefnets that have many hidden layers.
A Fast Computational Algorithm for the Discrete Cosine Transform A Fast Computational Algorithm for the Discrete Cosine Transform
K_SVD:An Algorithm for Designing Overcomplete Dictionary for Sparse Representation
这篇paper是Hinton大牛在2006你那发表的文章,该文在神经网络的深度学习领域取得重大突破。
A Fast Learning Algorithm for Deep Belief Nets
Sequential Minimal Optimization A Fast Algorithm for Training
A fast learning algorithm for deep belief nets
A fast algorithm fortwo-dimensional median filtering
同学发表的一篇论文, 水会。 上传到这里,还是希望更多的人能够了解,和指正。
SMO algorithm.pdf
PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing 原文
A Fast Learning Algorithm for Deep Belief Netsep Belief Nets 希望学习模式识别的同学能用上
Pixeltrack: A fast adaptive algorithm for tracking non-rigid objects. In ICCV, pages 2480-2487, 2013 论文源代码.下载于http://u0016403263.user.hosting-agency.de/research_pixeltrack.html.非刚性跟踪算法...
The fast, greedy algorithm is used to initialize a slower learning procedure that fine-tunes the weights using a contrastive version of thewake-sleep algorithm. After fine-tuning, a networkwith three...