Wish I could report completion of that part, but in fact I didn't get much done since my last commit.
Besides, what I had done started looking like spaghetti code where it should have been a simple and elegant algorithm. So I just drew a little scene (see attached image) and tried figuring out a more algorithmic solution. The image itself shows the scene seen from the side, with an (invisible) scary eye looking at it from the top right. To figure out the drawing order, two rays are projected through a shapes min and max corner points. If those rays do not pass through any other shape, we can render it and remove it from the queue. For that scene, that's all there is to it. For shapes that do not overlap, it is obviously not important in which order they are rendered (hence they share the same level of drawing order). A more formal algorithm would look as follows: while drawing_queue not empty: for each shape in drawing_queue: do ray test against every other shape if ray test negative: // rays didn't pass through any other shape draw shape remove shape from drawing_queue That means that we must make several passes over the queue, until it is empty. Not sure if we could do faster ... we ought to, but lets start simple :-). Remains the question how the ray test works. Obviously, by projecting the object shadow on the y-axis, we can check if two objects overlap, but it doesn't tell us which object is in the path of the rays. Figuring out boils down to a ray - AABB intersection test in 2D. From what I've seen, one could turn the ray(s) into an AABB too and check both boxes for overlap. Again, there could be something more simple, but for now lets try that ... But enough talk, on to the implementation. I'll let you know how it goes :-) Kai
<<attachment: draw-order.png>>
_______________________________________________ Adonthell-devel mailing list Adonthell-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/adonthell-devel