Fix depth sorting

[jdan]

My current depth sorting implementation is incredibly naive. Essentially, when Isomer.prototype.add is given a shape, it first orders its faces, then draws them.

Ordering the faces currently involves sorting them by the average distance of their points to the arbitrary point:

var observer = new Point(-10, -10, 10);

This fails for a number of reasons. Most notably, points located to the extreme left and right edges of the canvas (+x, -y) and (-x, +y) respectively, will be calculated to be further away than something close to the origin. Drawing shapes at these locations will cause their faces to be out of order.

Because of this limitation, drawing shapes with convex polygons as sides does not currently work, as you can see in the "star" example on the test page.

So, we need to implement some form of proper depth sorting. I imagine there are many neat tricks we can do with an isometric projection.

[fplam]

You might want to look into the following answer by munificent on the gamedev stackexchange: http://gamedev.stackexchange.com/a/8355
x+y+z gives you a nearness value for a point (for the coordinate system described in the link). I guess you could compute the nearness of a face as the nearness of its nearest point. You could then use that "face nearness" value as a sort key to determine the rendering order of all the faces in the scene.

[jdan]

@fplam been playing around with it, but the trick here is ordering planes. Choosing the nearest point rarely works.

[jdan]

The latest patches – 0.1.2 and 0.1.3 – both contain improvements to orderedPaths().

Each Point is now assigned a depth, calculated by:

x + y - 2*z

z is weighted to fix most arrangements where two planes come in contact at a right angle. You'll notice the "extrude" example on the homepage is now fixed (it used to have a bug, did you notice?)

Happy to track down some more edge cases. Please report any funny rendering you come across.

[fplam]

Cool. I guess there are always going to be edge cases, since filling canvas paths cannot be as accurate as pixel-by-pixel rendering with z-buffering.

[Mysterix]

Sorry misclick, I write it again :
Let H be the hyperplane induced by pathA.
PathA must be drawn before PathB if at least one of PathB vertices is on the same side of H than the observer.

I will PR this soon, with a drawing to explain in a simpler way

[Mysterix]

Problem seems to be solved on my repo (even with jdan's temple from the gallery !)
I don't PR it yet because it is still slow (because of the overlap detection, i have ideas to fix that soon) and I have to remove the test code and some comments.
It was much more complex than what I thought when I wrote the previous post (many, many exceptions), but I had free time this week-end !

Examples :
http://rdelav.fr/isomer/isomer3.html (simple example)
http://rdelav.fr/isomer/isomer4.html (@jdan basic example, withou the animation)
http://rdelav.fr/isomer/isomer5.html (quite long to load : @Wouwi flappy bird sorted (funny compared to the original))
http://rdelav.fr/isomer/isomer6.html (@jdan parthenon, long to load)

Edit : I just tested with chrome instead of firefox : it is much faster, but we can see a little bug with isomer3.html, I will watch that (probably another rounding problem)