I'm sure there's gotta be a simple way to determine sorting order, I'm just not quite sure how to do it. Any help would be great. Thanks!
2D Line Sorting
Author
Hi!
I'm trying to figure out a sorting algorithm for sorting lines based on which one is "in front of" which. Here's the setup:
1. All line end points are above the origin ( ie. y > 0 ).
2. All line end points are in order ( ie. p1 is always to the left of p2, that is p1.x < p2.x ).
3. None of the lines intersect each other ( although they may share end points ).
How would I go about checking if a given line in the list is "in front of" another? Here's what I mean by "in front of" ( green lines are in front of red lines ):
I'm sure there's gotta be a simple way to determine sorting order, I'm just not quite sure how to do it. Any help would be great. Thanks!
I'm sure there's gotta be a simple way to determine sorting order, I'm just not quite sure how to do it. Any help would be great. Thanks!
RegularKid,
From your pictures I'm still a bit confused about your description of "In front of"...
In Image 1 the red line has a positive slope, and the green line exists "beneath" that slope using an inequality test. It also has a p2.x which is greater than red's p2.x, so combined I can see how green would be "in front"
In Image 2 red has a negative slope, green is still "below" all points on red, and again has a p2.x which is greater than red.p2.x. So I can again kind of see what you mean by "in front of"
However in Image 3 green has an x value that is lower than red at all points, and again red has a negative slope.
So I guess I'm confused about your mathematical or visual definition of "in front"? Does in-front have something to do with the value of X? Is it based on slope? If I did a vertical line scan on Image #1 and #2 from the right to left I may very well encounter the green line first, making it "in front", but in Image 3 I'd definitely hit the red line first. Can you elaborate a bit more? Or perhaps I'm just missing something completely obvious.
Cheers!
From your pictures I'm still a bit confused about your description of "In front of"...
In Image 1 the red line has a positive slope, and the green line exists "beneath" that slope using an inequality test. It also has a p2.x which is greater than red's p2.x, so combined I can see how green would be "in front"
In Image 2 red has a negative slope, green is still "below" all points on red, and again has a p2.x which is greater than red.p2.x. So I can again kind of see what you mean by "in front of"
However in Image 3 green has an x value that is lower than red at all points, and again red has a negative slope.
So I guess I'm confused about your mathematical or visual definition of "in front"? Does in-front have something to do with the value of X? Is it based on slope? If I did a vertical line scan on Image #1 and #2 from the right to left I may very well encounter the green line first, making it "in front", but in Image 3 I'd definitely hit the red line first. Can you elaborate a bit more? Or perhaps I'm just missing something completely obvious.
Cheers!
It very much depends on from where to where you look, since like especially your first picture shows, the red line has portions that are in front of the green one lefthand (i.e. one y-coord of red is < than one of green, although they don't intersect).
Author
Sorry, I should have been more clear in my description :)
What I'm writing is a 2.5D engine like DOOM / Duke Nukem 3D. The map is made up of 2D lines ( as if you're looking at a top-down view of the buildings ). Once I get everything projected to the player's view and cull out lines ( walls ) that won't be rendered, what I have left are a list of 2D lines ( walls ) in front of the player. The player is standing at ( 0, 0 ) and looking up the Y-Axis in the positive direction.
Because of the way the rendering works, I need to start with the closest line ( wall ) in front of the player and render it. Then I move on the next wall and render it. And on and on. Basically doing a front to back rendering pass. So here's my psuedo code for this:
What I'm writing is a 2.5D engine like DOOM / Duke Nukem 3D. The map is made up of 2D lines ( as if you're looking at a top-down view of the buildings ). Once I get everything projected to the player's view and cull out lines ( walls ) that won't be rendered, what I have left are a list of 2D lines ( walls ) in front of the player. The player is standing at ( 0, 0 ) and looking up the Y-Axis in the positive direction.
Because of the way the rendering works, I need to start with the closest line ( wall ) in front of the player and render it. Then I move on the next wall and render it. And on and on. Basically doing a front to back rendering pass. So here's my psuedo code for this:
do{ wall = getClosestWall(); renderWall( wall );} while( while );void getClosestWall(){ // Find closest wall to the player // by checking which wall is in front // of all of the other walls. closestWall = walls[ 0 ]; for( int i = 1; i < walls.length; i++ ) { if( wall.InFrontOf( closestWall ) )<br> {<br> closestWall = wall;<br> }<br> }<br><br> <span class="cpp-comment">// Take wall out of wall list</span><br> walls.Remove( closestWall );<br> <span class="cpp-keyword">return</span> closestWall ;<br>}<br><br></pre></div><!–ENDSCRIPT–><br><br>Something along those lines.<br><br>I guess the definiton of "in front of" can be thought of as: wall A is in front of wall B if wall A would cover up part of wall B when looked at from the origin ( ie. player's position ). The obvious case where render order wouldn't matter and it doesn't really matter which wall is "in front of" the other would be when the two lines DO NOT overlap along the x-axis.<br><br>So, my "InFrontOf" currently is something like this ( pseudo code ):<br><br><!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre><br><span class="cpp-comment">// Get line 1 bounding box extents</span><br><span class="cpp-keyword">if</span>( line1.x1 < line1.x2 )<br>{<br> line1MinX = line1.x1;<br> line1MaxX = line1.x2;<br>}<br><span class="cpp-keyword">else</span><br>{<br> line1MinX = line1.x2;<br> line1MaxX = line1.x1;<br>}<br><br><span class="cpp-keyword">if</span>( line1.y1 < line1.y2 )<br>{<br> line1MinY = line1.y1;<br> line1MaxY = line1.y2;<br>}<br><span class="cpp-keyword">else</span><br>{<br> line1MinY = line1.y2;<br> line1MaxY = line1.y1;<br>}<br><br><span class="cpp-comment">// Get line 2 bounding box extents</span><br><span class="cpp-keyword">if</span>( line2.x1 < line2.x2 )<br>{<br> line2MinX = line2.x1;<br> line2MaxX = line2.x2;<br>}<br><span class="cpp-keyword">else</span><br>{<br> line2MinX = line2.x2;<br> line2MaxX = line2.x1;<br>}<br><br><span class="cpp-keyword">if</span>( line2.y1 < line2.y2 )<br>{<br> line2MinY = line2.y1;<br> line2MaxY = line2.y2;<br>}<br><span class="cpp-keyword">else</span><br>{<br> line2MinY = line2.y2;<br> line2MaxY = line2.y1;<br>}<br><br><span class="cpp-comment">// Easy out #1: Lines don't overlap along the x-axis…</span><br><span class="cpp-comment">// doesn't matter who return since render order doensn't matter in this case</span><br><span class="cpp-keyword">if</span>( line1MaxX < line2MinX ||<br> line2MaxX < line1MinX )<br>{<br> <span class="cpp-keyword">return</span> line1;<br>}<br><br><span class="cpp-comment">// Easy out #2: Line #2 is completely behind line #1</span><br><span class="cpp-keyword">if</span>( line2MinY > line1MaxY )<br>{<br> <span class="cpp-comment">// Line 1 is in front</span><br> <span class="cpp-keyword">return</span> line1;<br>}<br><br><span class="cpp-comment">// Easy out #3: Line #1 is completely behind line #2</span><br><span class="cpp-keyword">if</span>( line1MinY > line2MaxY )<br>{<br> <span class="cpp-comment">// Line 2 is in front</span><br> <span class="cpp-keyword">return</span> line2;<br>}<br><br><span class="cpp-comment">// Ok, lines overlap on at least one of the axes</span><br><span class="cpp-comment">// TODO: Figure out how to determine which line</span><br><span class="cpp-comment">// is in front of the other…</span><br><br></pre></div><!–ENDSCRIPT–> 
Quote:Original post by RegularKid
What I'm writing is a 2.5D engine like DOOM / Duke Nukem 3D. The map is made up of 2D lines ( as if you're looking at a top-down view of the buildings ). [...]
Because of the way the rendering works, I need to start with the closest line ( wall ) in front of the player and render it. Then I move on the next wall and render it. And on and on. ...
I'm not sure why you're saying that you need to render from front to back. If you're talking about the "painter's algorithm" don't you need to render from back to front?
Anyway, given your application, what you mean by "in front of" is the following:
for each pair of line segments L1 and L2, L1 is in front of L2 if there exists a line from the origin to a point on L2 that intersects L1. If there doesn't exist such a line then you can render L1 first or L2 first.
Author
Quote:Original post by jwezorekQuote:Original post by RegularKid
What I'm writing is a 2.5D engine like DOOM / Duke Nukem 3D. The map is made up of 2D lines ( as if you're looking at a top-down view of the buildings ). [...]
Because of the way the rendering works, I need to start with the closest line ( wall ) in front of the player and render it. Then I move on the next wall and render it. And on and on. ...
I'm not sure why you're saying that you need to render from front to back. If you're talking about the "painter's algorithm" don't you need to render from back to front?
Anyway, given your application, what you mean by "in front of" is the following:
for each pair of line segments L1 and L2, L1 is in front of L2 if there exists a line from the origin to a point on L2 that intersects L1. If there doesn't exist such a line then you can render L1 first or L2 first.
Yes! That's a perfect description of it! Thank you :)
And the reason I need to do the reverse of the painter's algorithm is because of the way things are rendered. Walls a rendered as vertical strips ( one for each column on the screen ). For each vertical column rendering stops when the entire column is filled ( ie. every pixel has been written to ). Drawing from front to back allows for no pixels to ever be overwritten by a closer pixel. When a wall slice is rendered to a vertical column, clipping information is stored to help render ( or not render ) walls behind it. So in essence, when rendering from front to back it's possible to render a wall or two and then dismiss all of the other walls behind it because those two walls have filled up the entire screen. Just makes for more efficient rendering.
I suppose the following is no news to you, but just to make sure:
Just be carefull when "sweeping" to the left and right (horizontal FOV). A segment that is frontmost at an angle of 0 may not be first in line (no pun intended) anymore a few radians off to the sides. You'll have to evaluate the "first" for every pixel column.
This sort of raycasting only saves the y-Axis, and assumes what is hit in a straight horizontal line from the observer is all there is. But that line still needs proper intersection/hit tests over it's entire width. (There might be another way to cut down on pixels to test fully, I'm not that deep in raycasting.)
I'm sure that this really is too basic to be mentioned, but since it hasn't so far... :)
Just be carefull when "sweeping" to the left and right (horizontal FOV). A segment that is frontmost at an angle of 0 may not be first in line (no pun intended) anymore a few radians off to the sides. You'll have to evaluate the "first" for every pixel column.
This sort of raycasting only saves the y-Axis, and assumes what is hit in a straight horizontal line from the observer is all there is. But that line still needs proper intersection/hit tests over it's entire width. (There might be another way to cut down on pixels to test fully, I'm not that deep in raycasting.)
I'm sure that this really is too basic to be mentioned, but since it hasn't so far... :)
Quote:
Yes! That's a perfect description of it! Thank you :)
So, I think, the easiest way to determine if line segment L1 is in front of line segment L2 would be to project the end points of L1 on to the line that contains L2 i.e. find the points p1 and p2 on the line that contains L2 that are the intersections between the line that contains L2 and the two lines that connect the end points of L1 to the origin. Then, you have to check to see if p1 and p2 are both "to the left" of L2's end points or both "to the right" of L2's end points, if they are then L1 is not in front of L2.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
