cpp/openttd-patchpack/source Changeset - r23224:c7cfd7dd8fd8

Changeset - r23224:c7cfd7dd8fd8

Parent rev.

Child rev.

[Not reviewed]

master

0 1 0

Jonathan G Rennison - 7 years ago 2018-01-18 20:38:27
j.g.rennison@gmail.com

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 file changed with 61 insertions and 6 deletions:

src/linkgraph/linkgraph_gui.cpp

0 comments (0 inline, 0 general)

src/linkgraph/linkgraph_gui.cpp

➞

Show inline comments

@@ @@ -122,18 +122,73 @@ inline bool LinkGraphOverlay::IsPointVis @@
  * @param dpi Visible area.
  * @param padding Width or thickness of the link.
  * @return If the link or any of its "thickness" is visible. This may return false positives.
  */
 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();
+}
 /**
  * Add all "interesting" links between the given stations to the cache.
  * @param from The source station.
  * @param to The destination station.

0 comments (0 inline, 0 general)