Jump to content
Posted 13 November 2012 - 09:02 PM
Posted 13 November 2012 - 09:38 PM
Posted 14 November 2012 - 11:28 PM
I have a suspicion that anything reasonable that you do will be plenty fast enough.
The standard/obvious thing to do would be to convert your line segments to quads ahead of time, store them in some kind of spatial data structure (e.g., quad- or KD- tree, regular grid, or just arrays sorted by x and y position), do a conservative cull against your view box, and then and draw what's left with hardware texture mapping if available.
The line-segment--to-quad math, by the way, is pretty cheap. If you have a line from p1 to p2, then the tangent to the line is T=normalize(p2-p1), and the normal is N=J T, where J is the 90-degree rotation matrix (it exchanges the x and y coordinates and flips the sign of one). Then, if the road width is w, and if we define an "offset vector" by d = 0.5 w N, then you can just write the vertices as p1 + d, p1 - d, p2 + d, and p2 - d.
Back to spatial data structures: The only other thing that springs to mind is to exploit temporal coherence and the fact that your world is a graph, by storing neighbor/linkage information in the line segments, maintaining a list of the edges currently intersecting the edge of the view box, and, each frame, only doing intersection tests with those edges and their neighbors, to determine which of these line segments are entering or leaving the view. The assumption this would make is that you can never move more than the length of an edge in a frame. This is probably the fastest method, but also the least flexible, and, since you could probably get away with brute-forcing this, I can't really recommend it, even if it is the most amusing.
Posted 29 November 2012 - 10:01 PM