summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorfrosch <frosch@openttd.org>2011-04-09 11:32:11 +0000
committerfrosch <frosch@openttd.org>2011-04-09 11:32:11 +0000
commitecb3701210f7bf5fbcea79849f8514997eecb25f (patch)
tree4457e65aa16a51f782779467368cebd7121f2af5 /src
parent1e64012e9f4f474867cc91b138406671564db709 (diff)
downloadopenttd-ecb3701210f7bf5fbcea79849f8514997eecb25f.tar.xz
(svn r22302) -Codechange: Replace a linear search with a binary search.
Diffstat (limited to 'src')
-rw-r--r--src/blitter/base.cpp13
1 files changed, 12 insertions, 1 deletions
diff --git a/src/blitter/base.cpp b/src/blitter/base.cpp
index 312ec1025..d8e33cede 100644
--- a/src/blitter/base.cpp
+++ b/src/blitter/base.cpp
@@ -50,8 +50,19 @@ void Blitter::DrawLine(void *video, int x, int y, int x2, int y2, int screen_wid
int frac_diff = width * max(dx, dy);
if (width > 1) {
+ /* compute frac_diff = width * sqrt(dx*dx + dy*dy)
+ * Start interval:
+ * max(dx, dy) <= sqrt(dx*dx + dy*dy) <= sqrt(2) * max(dx, dy) <= 3/2 * max(dx, dy) */
int frac_sq = width * width * (dx * dx + dy * dy);
- while (frac_diff * frac_diff < frac_sq) frac_diff++;
+ int frac_max = 3 * frac_diff / 2;
+ while (frac_diff < frac_max) {
+ int frac_test = (frac_diff + frac_max) / 2;
+ if (frac_test * frac_test < frac_sq) {
+ frac_diff = frac_test + 1;
+ } else {
+ frac_max = frac_test - 1;
+ }
+ }
}
if (dx > dy) {