From 64f1847becbb6ec5c0cf6c1ceaa8812893031713 Mon Sep 17 00:00:00 2001 From: Jonathan G Rennison Date: Thu, 18 Jan 2018 20:38:27 +0000 Subject: 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. --- src/linkgraph/linkgraph_gui.cpp | 67 +++++++++++++++++++++++++++++++++++++---- 1 file changed, 61 insertions(+), 6 deletions(-) (limited to 'src') 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(); } /** -- cgit v1.2.3-70-g09d2