summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJonathan G Rennison <j.g.rennison@gmail.com>2018-01-18 20:38:27 +0000
committerNiels Martin Hansen <nielsm@indvikleren.dk>2019-01-28 19:15:21 +0100
commit64f1847becbb6ec5c0cf6c1ceaa8812893031713 (patch)
tree2efd15e0a13cabc51138639d221eefc46c485f55
parent9c6ac309e0b51fe7952f42ca9a8e2ee30debc473 (diff)
downloadopenttd-64f1847becbb6ec5c0cf6c1ceaa8812893031713.tar.xz
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.
-rw-r--r--src/linkgraph/linkgraph_gui.cpp67
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();
}
/**