Changeset - r23224:c7cfd7dd8fd8
[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:
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)