Mercurial > hg > openttd

changeset 17538:89cafd5c3d9d draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
(svn r22302) -Codechange: Replace a linear search with a binary search.
author frosch <frosch@openttd.org>
date Sat, 09 Apr 2011 11:32:11 +0000
parents 16ddd3699d62
children b05872fd9c03
files src/blitter/base.cpp
diffstat 1 files changed, 12 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- a/src/blitter/base.cpp
+++ b/src/blitter/base.cpp
@@ -50,8 +50,19 @@
 
 	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) {