Hi Ken, sorry to bother you...I've said before I'm making a Build clone based on my experience and I have some kind of trouble with bunches sorting. How does build sort the bunches in the case from the image below (the bunches are formed only by walls and not portals)? I think you've said that Build does a double sort checking. I've maid a sorting algorithm based on normal checking...but in this case it doesn't work very well. In short I thought this way: if a line (from the first bunch) has both vertexes on the other side of another lines's normal (from the second bunch) the first bunch is the farthest, if that line has a vertex on a side, and the second on the other side then the first bunch is the nearest etc.
All walls must be sorted in the bunches. Portals (red lines) are treated exactly like white line walls. First, check to see whether the bunches overlap. If they do, then find a wall of each that overlaps. By overlap, I mean that walls cross when projected to 2D. In your diagram, lines 2 and 3 overlap. The sorting order of the bunches must be the same as the sorting order of these 2 walls/lines.
To sort walls, first find the wall that, if extended to infinity, does not slice the other line segment. There will always be one, assuming the lines do not intersect. Sometimes both can be used - it doesn't matter which one in this case. In your diagram, line 3 can be extended without slicing line 2, but not the other way. To get the sort order, you look at either vertex of line 2, and your viewing position. If they are on the same side of line 3, then line 2 would be in front. In your diagram, they are on opposite sides. Line 2 is therefore behind, which means bunch 1 is behind bunch 2.
Apprentice at
Thanks a lot Ken!...the algorithm you've presented is extremely similar to the one I've thought...except that in mine the sorting walls method that does not involve use of camera position like in yours (I think this is the bug that prevented my bunch sorting method to work on all cases).
Apprentice at
Sorry to bother you again Ken...I've seen you mentioned that the lines in the bunches must also be sorted. I thought you can tell me if my assumption is corect (I thought at an idea to avoid wall sorting in bunches). From yours replies I understood that bunches are a group of neighbour lines (without any gaps in the links) that are in front of the camera. I think the best scenario where you must sort the lines I can think is something like this (maybe a spiral):
My algorithm does something like this: first picks up a line that is in front of the camera and was not picked up before. Let's say line1...then walks into it's vertexes and picks up lines that are in front of the camera, not picked up before and that aren't entirely behind the camera...and adds that lines to the bunch (when it finds a bad line it stops adding lines to the bunch of the current direction). In this case there are no lines that are linked on vertex1 so the in the bunch are added: line1,line2,line3,line4,line5,line6,line7,line8 (liked on vertex2) and for now it stops here because (I assume) he finds out that line 9 (the virtual end line of the bunch) collides (when projected to 2D) with the first line of the bunch (line1) so it makes another bunch and puts there line9 as the first line. Then it continues with the other lines and puts them in the second bunch (the ones with double lines on the drawing) without verifying the collision condition again (I thought that a bunch cannot be split up in more that 2 bunches in this way...I may be wrong). So at finaly we have: bunch1 (line1...8 ) and bunch2 (line9...12 ). Now they can be freely sorted with your algorithm (line1 and line9 collides so we find line 9 behind line1 then bunch2 is behind bunch1).
Please tell me if you find an error on my idea. (I'm not pretty sure it works on all cases)
Awesoken at
In Build, I do NOT sort walls to assist with generating bunches. First, I rotate and translate each wall. Then I do back-face culling: any wall not facing you is discarded. Then I clip the wall to the left and right side of the viewing frustum. I add the wall to the current bunch if the previous wall index also made it through. Otherwise, I start a new bunch. In order to avoid the case where the first wall of a sector would be in the middle of a bunch, I would do a little hack and start at the first back-face culled wall.
Your diagram is misleading because all sectors must be closed loops. Ignoring that, I would say that my bunching algorithm would generate the following 2 bunches:
Your diagram is misleading because all sectors must be closed loops.
I know...I only considered drawing (in the picture) back faced walls (sorry I didn't mentioned). I was curious on how does your algorithm pick the walls to form the bunches. My algorithm is a bit different because I make 2D clipping (I understood that you make 3D clipping before 2D projection), I first form the bunches with back faced walls, not picked up before and that are not entirely behind the camera and then I eliminate the ones you can never see (after screen projection). But ignoring the fact that I didn't draw the all sector and if we pressume that your camera has a FOV of 180 or almost 180 degree which would be the bunches? The same mentioned in my last reply? I forgot to mention...although in my drawing the camera seems the be behind line5 and line6 it is in front of them.
Awesoken at
Build does bunch and wall sorting in 2D, using the top view like in your diagrams. If my algorithm used a 180 degree FOV for your diagram, no walls would be back-face culled, and only walls 5 and 6 would be frustum clipped. It would generate the following bunches: bunch 1: 5,4,3,2,1 bunch 2: 12,11,10,9,8,7,6