Codechange: [Linkgraph GUI] Replace line visibility detection algorithm

Use an implementation of the Cohen-Sutherland line-clipping algorithm.
The previous algorithm had an excessive false-positive rate.
Line-rendering is sufficiently expensive that using a line-clipping
algorithm with a much lower false-positive rate is a net performance
benefit.

1 files changed, 61 insertions, 6 deletions

diff --git a/src/linkgraph/linkgraph_gui.cpp b/src/linkgraph/linkgraph_gui.cpp
index 30c4451ee..7923fc26c 100644
--- a/src/linkgraph/linkgraph_gui.cpp
+++ b/src/linkgraph/linkgraph_gui.cpp
@@ -125,12 +125,67 @@ inline bool LinkGraphOverlay::IsPointVisible(Point pt, const DrawPixelInfo *dpi,
  */
 inline bool LinkGraphOverlay::IsLinkVisible(Point pta, Point ptb, const DrawPixelInfo *dpi, int padding) const
 {
-	return !((pta.x < dpi->left - padding && ptb.x < dpi->left - padding) ||
-			(pta.y < dpi->top - padding && ptb.y < dpi->top - padding) ||
-			(pta.x > dpi->left + dpi->width + padding &&
-					ptb.x > dpi->left + dpi->width + padding) ||
-			(pta.y > dpi->top + dpi->height + padding &&
-					ptb.y > dpi->top + dpi->height + padding));
+	const int left = dpi->left - padding;
+	const int right = dpi->left + dpi->width + padding;
+	const int top = dpi->top - padding;
+	const int bottom = dpi->top + dpi->height + padding;
+
+	/*
+	 * This method is an implementation of the Cohen-Sutherland line-clipping algorithm.
+	 * See: https://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm
+	 */
+
+	const uint8 INSIDE = 0; // 0000
+	const uint8 LEFT   = 1; // 0001
+	const uint8 RIGHT  = 2; // 0010
+	const uint8 BOTTOM = 4; // 0100
+	const uint8 TOP    = 8; // 1000
+
+	int x0 = pta.x;
+	int y0 = pta.y;
+	int x1 = ptb.x;
+	int y1 = ptb.y;
+
+	auto out_code = [&](int x, int y) -> uint8 {
+		uint8 out = INSIDE;
+		if (x < left) {
+			out |= LEFT;
+		} else if (x > right) {
+			out |= RIGHT;
+		}
+		if (y < top) {
+			out |= TOP;
+		} else if (y > bottom) {
+			out |= BOTTOM;
+		}
+		return out;
+	};
+
+	uint8 c0 = out_code(x0, y0);
+	uint8 c1 = out_code(x1, y1);
+
+	while (true) {
+		if (c0 == 0 || c1 == 0) return true;
+		if ((c0 & c1) != 0) return false;
+
+		if (c0 & TOP) {           // point 0 is above the clip window
+			x0 = x0 + (int)(((int64) (x1 - x0)) * ((int64) (top - y0)) / ((int64) (y1 - y0)));
+			y0 = top;
+		} else if (c0 & BOTTOM) { // point 0 is below the clip window
+			x0 = x0 + (int)(((int64) (x1 - x0)) * ((int64) (bottom - y0)) / ((int64) (y1 - y0)));
+			y0 = bottom;
+		} else if (c0 & RIGHT) {  // point 0 is to the right of clip window
+			y0 = y0 + (int)(((int64) (y1 - y0)) * ((int64) (right - x0)) / ((int64) (x1 - x0)));
+			x0 = right;
+		} else if (c0 & LEFT) {   // point 0 is to the left of clip window
+			y0 = y0 + (int)(((int64) (y1 - y0)) * ((int64) (left - x0)) / ((int64) (x1 - x0)));
+			x0 = left;
+		}
+
+		c0 = out_code(x0, y0);
+	}
+
+	NOT_REACHED();
 }
 
 /**