[Adonthell-devel] Drawing order

[Kai Sterker]

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

draw-order.png
Description: PNG image