From 4b256fed36f6edab42c6a18e5d31e17e38ac669b Mon Sep 17 00:00:00 2001
From: Jonathan G Rennison <j.g.rennison@gmail.com>
Date: Wed, 17 Jan 2018 02:52:40 +0000
Subject: Codechange: [Blitter] Adjust line-drawing algorithm to reduce wasted
 off-screen work

This clips the line segment to be within the screen area prior to pixel iteration.
---
 src/blitter/common.hpp | 76 +++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 66 insertions(+), 10 deletions(-)

(limited to 'src/blitter/common.hpp')

diff --git a/src/blitter/common.hpp b/src/blitter/common.hpp
index 9019dd359..3e4911d00 100644
--- a/src/blitter/common.hpp
+++ b/src/blitter/common.hpp
@@ -15,6 +15,8 @@
 #include "base.hpp"
 #include "../core/math_func.hpp"
 
+#include <utility>
+
 template <typename SetPixelT>
 void Blitter::DrawLineGeneric(int x, int y, int x2, int y2, int screen_width, int screen_height, int width, int dash, SetPixelT set_pixel)
 {
@@ -66,23 +68,50 @@ void Blitter::DrawLineGeneric(int x, int y, int x2, int y2, int screen_width, in
 	if (dash == 0) dash = 1;
 	int dash_count = 0;
 	if (dx > dy) {
+		if (stepx < 0) {
+			std::swap(x, x2);
+			std::swap(y, y2);
+			stepy = -stepy;
+		}
+		if (x2 < 0 || x >= screen_width) return;
+
 		int y_low     = y;
 		int y_high    = y;
 		int frac_low  = dy - frac_diff / 2;
 		int frac_high = dy + frac_diff / 2;
 
-		while (frac_low + dx / 2 < 0) {
+		while (frac_low < -(dx / 2)) {
 			frac_low += dx;
 			y_low -= stepy;
 		}
-		while (frac_high - dx / 2 >= 0) {
+		while (frac_high >= dx / 2) {
 			frac_high -= dx;
 			y_high += stepy;
 		}
-		x2 += stepx;
+
+		if (x < 0) {
+			dash_count = (-x) % (dash + gap);
+			auto adjust_frac = [&](int64 frac, int &y_bound) -> int {
+				frac -= ((int64) dy) * ((int64) x);
+				if (frac >= 0) {
+					int quotient = frac / dx;
+					int remainder = frac % dx;
+					y_bound += (1 + quotient) * stepy;
+					frac = remainder - dx;
+				}
+				return frac;
+			};
+			frac_low = adjust_frac(frac_low, y_low);
+			frac_high = adjust_frac(frac_high, y_high);
+			x = 0;
+		}
+		x2++;
+		if (x2 > screen_width) {
+			x2 = screen_width;
+		}
 
 		while (x != x2) {
-			if (dash_count < dash && x >= 0 && x < screen_width) {
+			if (dash_count < dash) {
 				for (int y = y_low; y != y_high; y += stepy) {
 					if (y >= 0 && y < screen_height) set_pixel(x, y);
 				}
@@ -95,29 +124,56 @@ void Blitter::DrawLineGeneric(int x, int y, int x2, int y2, int screen_width, in
 				y_high += stepy;
 				frac_high -= dx;
 			}
-			x += stepx;
+			x++;
 			frac_low += dy;
 			frac_high += dy;
 			if (++dash_count >= dash + gap) dash_count = 0;
 		}
 	} else {
+		if (stepy < 0) {
+			std::swap(x, x2);
+			std::swap(y, y2);
+			stepx = -stepx;
+		}
+		if (y2 < 0 || y >= screen_height) return;
+
 		int x_low     = x;
 		int x_high    = x;
 		int frac_low  = dx - frac_diff / 2;
 		int frac_high = dx + frac_diff / 2;
 
-		while (frac_low + dy / 2 < 0) {
+		while (frac_low < -(dy / 2)) {
 			frac_low += dy;
 			x_low -= stepx;
 		}
-		while (frac_high - dy / 2 >= 0) {
+		while (frac_high >= dy / 2) {
 			frac_high -= dy;
 			x_high += stepx;
 		}
-		y2 += stepy;
+
+		if (y < 0) {
+			dash_count = (-y) % (dash + gap);
+			auto adjust_frac = [&](int64 frac, int &x_bound) -> int {
+				frac -= ((int64) dx) * ((int64) y);
+				if (frac >= 0) {
+					int quotient = frac / dy;
+					int remainder = frac % dy;
+					x_bound += (1 + quotient) * stepx;
+					frac = remainder - dy;
+				}
+				return frac;
+			};
+			frac_low = adjust_frac(frac_low, x_low);
+			frac_high = adjust_frac(frac_high, x_high);
+			y = 0;
+		}
+		y2++;
+		if (y2 > screen_height) {
+			y2 = screen_height;
+		}
 
 		while (y != y2) {
-			if (dash_count < dash && y >= 0 && y < screen_height) {
+			if (dash_count < dash) {
 				for (int x = x_low; x != x_high; x += stepx) {
 					if (x >= 0 && x < screen_width) set_pixel(x, y);
 				}
@@ -130,7 +186,7 @@ void Blitter::DrawLineGeneric(int x, int y, int x2, int y2, int screen_width, in
 				x_high += stepx;
 				frac_high -= dy;
 			}
-			y += stepy;
+			y++;
 			frac_low += dx;
 			frac_high += dx;
 			if (++dash_count >= dash + gap) dash_count = 0;
-- 
cgit v1.2.3-70-g09d2