Please clear all the walls and drag to draw lines randomly. Click show walls to see the result.
This article is a discussion about sorting the depths of those walls. The source file is in MX2004 format just for convenience. It can be done with MX only.
Getting the intersect points between lines is beyond discussion.
The depths in 3d space
It is common to handle the depths of 3d objects by the z coordinates. The z-order is roughly the same as the z coordinates. If we have several balls scattered in 3d space, the near one should have the higher depths value while the far one has the lower depths value. If they get overlapped, we see only the near one.
It is about balls. What about a stick or a wall ? A stick may have its head at the near and the tail at the far. What is the z coordinate ? If we have many sticks, how do we arrange the depths ?
Well, it is not always possible. For example, we arrange 3 sticks into a triangle. Each head of the stick cross over the tail of the next stick. So, A stick is over B, B stick is over C and C stick is over A. There is no way to make the depths correct.
The walls in isometric 3d
In many occasions, we need to arrange a 3d walls on a flat plane. In fact this is more like 2d , not a 3d. The coordinate for each wall is (x,y) for head and (x,y) for tail. We don't have z coordinate. For example, isometric 3d tile game. Characters and obstacles are arranged on a plane. Each character or obstacle is located at (x,y).
Most of the time, In such game, each character or obstacle occupies a single tile with single (x,y) coordinate to represent the position. Usually, they don't occupy two or more tiles. The depths are calculated mainly with the y. No problem. This is not what we are going to discuss.
What we are going to solve is scenario like these:
A furniture plane. User drags furniture on to the floor of the room. The furniture may include a big bed, a long closet or a bench that covers several "tiles". We need two cordinates (x1,y1) and (x2,y2) to represent the bounds. How do we arrange the z-order of these furniture ?
A 3d maze game. There are many walls. Some goes obliquely from near (x1,y1) to far (x2,y2). How do we arrange the z-order ?
In the movie on this page, there are walls going obliquely without definite regularity or rules. How do we arrange the z-order ?
Is there an algorithm to handle the z-order ?
The order is Relative not Absolute
We have two walls A and B. When A and B do not get overlapped, the order can not be determined. Or, either A in front of B or B in front of A will work. When another wall C appears, the orientation of the C affects the order of A and B. The upper one makes A in front of B and the lower one makes B in front of A.
When we say "un-determined", it does not mean A and B has the same order. The order is determined by other walls that overlaps with them. In other words, the order of walls are determined "relatively" not "absolutely". There is no single algorithm that is able to calculate "absolute" depths value. So, we can not use the "array.sort" function to handle the z-order. The sort function will get a premature "stop".
The order
How do we determine the order between two overlapped walls ?
Lets imagine that the C wall goes "horizontally" from left to right. In the upper half, the wall A falls completely in front of the C , so A is in front of A. For the B wall, it falls completely "behind" the C wall, so B is behind the C wall.
The check is done through cross product. I am not going to discuss this in details. Briefly, if cross product is positive, these 3 points are sampled counter-Clockwise and if cross product is negative, the sampling was done clockwise.
What if we take A as reference ? The C wall does not fall completely behind or in front of the A wall, how do we decide the order ? No, we do not We check both the relationship of A relative to C and C relative to A. One of the algorithm will tell the result we want.
Only if A overlaps with C, the algorithm will succeed. The only exception is when A intersects C like the letter "X". This is not allowable in our movie. Flash always render a wall as a unit. It has not ability to render intersected walls. Anyway, I add a procedure to convert intersect two walls into 4 walls.
The sort
The sort is performed by insertion.
An array of buffer is used to hold the sorted walls. Roughly, the sorted buffer is mean to be arranged from behind to front. For new added wall, we scan through the buffer until we meet an element that is in front of the new wall. We insert it here. In other words, the new added wall advances toward us until it gets blocked.
If we had absolute order, then we would had stopped here. However, our order is relative. So we continue our scanning for validity.
We re-do the sorting of the elements after the insertion point but with backward comparing. Each element that is not definitely in front of our wall is picked and move backward until it find a stop point - a wall behind it. In other words, the element goes away from us until it gets blocked.
The sorting process is very slow. Computer might freeze for a while.
ericlin@ms1.hinet.net