Absolute Isometric Depth Sorting

Wednesday, September 3, 2008 by jusopi 7 Comments

[update – 2010.01.27]

This should have been updated ages ago however I haven’t gotten around to it sorry 😦

A solution was found, check out the as3isolib’s DefaultSceneLayoutRenderer

• as3isolib
• docs

[update – 20080909]

As I suspected, it was too good to be true.  More testing is necessary, however I feel I am on the right path.

[update – 20080908]

Finally did it!!!  Or at least it appears that I have accomplished my goals through initial testing phases.  I’ll restate those goals for clarity:

• absolute isometric depth sorting – position & size determine depth without the aid of a tile based system.
• objects residing at higher depths are still sorted by their intended visual placement including the possibility of appearing behind objects in the foreground whose heights may extend above the plane of the higher object.

Keep in mind this has only been tested against the case found in the previous updates where one object residing on a higher plane is tested against one object residing at a lower plane whose height is above the first object.  Further testing needs to take place in order to ensure this remains solid when multiple object are tested against one another.  Here is a quick rundown of a render phase:

• container checks children for any size, depth, or geometry invalidation.  If so set a flag for further logic.
  • sort children by the following order:
    • elevation plane
    • isometric x value
    • isometric y value
  • if more than one elevation plane exists (simple check does children[0].z != children[children.length – 1].z), then we do a recursive manual sort by:
    • if A == B, continue
    • if A is intended to appear behind B (by performing a few simple position/geometry checks) then place B to A’s index + 1.
    • repeat loop
  • set each child’s depth to their index value within the sorted children.
• call render on all children

[update – 20080907]

Ok so I made a big breakthrough.  I almost have it, I just need to refine the sorting algorithm just a tad bit more and it will be ready for a new round of testing.  Check out the screen shots (these are actual screen shots of the SWF, whereas the others from the earlier update were done using Sketchup):

The following 3 shots are obviously the good ones.  This test swf is animated with the blue box moving clockwise INSIDE the perimeter of the white boxes area and the orange box moving clockwise OUTSIDE the perimeter of the white boxes area.

Now here is the kink where I need to refine the sorting algorithm.  If the blue box’s screen y value is greater than the orange box’s screen y value, you don’t get the correct overlap.  Just a bit more tweaking and it should be good.

[update – 20080905]

After reaching out to a few contacts I thought I had made some progress.  Before I get started on this maybe I should post an image of what the problem is.  This is what I want to do:

Notice how the orange box is at a higher elevation than the gray boxes?  But using my current depth sorting algorithm the front-most gray box gets rendered behind the orange box like this:

My current algorithm slices up the scene based on elevations into an array.  The first array element would contain an array of all the gray boxes, the second element would contain an array with one element, the orange box.   Then I would sort both elements from front to back and order there depths recursively.  The issue with this sorting is that is still 2D depth sorting for a quasi 3D scene.

Any suggestions?

[update – 20080904]

So I kinda realized that this is great if you plan to not have stacked isometric objects.  In other words this works great if you are on a flat terrain map.  However this does not address issues with variable terrain (e.g. Diablo, Marble Madness).

I am still in the process of finding a smart, performance-friendly solution for this.  I am also thinking about setting a property on any container-type class that requires depth sorting to be able to use either the flat terrain approach (found here) or a variable terrain approach in order to maximize performance.

Thoughts?

[original post]

Recently I have been working on my Flash-oriented projects.  Specifically I started working again on isolib, an AS3 isometric library.

Used to in AS2 you could delegate the task of depth sorting to the flash player by doing some calculations and assingning a number without regards to wether or not a depth preceeding it was filled.  For example, I have 5 Sprites.  In AS2 you could assing Sprite #1 to depth 0, Sprite#2 to depth 50 and the other 3 Sprites could have arbitrary numbers assigned to them.  The flash player took on the task of ordering the display list for you.  In AS3 that is not the case as you will run into Run Time Errors if you try to assing a DisplayObject to a depth without the prior depths being occupied.  So now the task is assigned to the developer.

Now as many ways as there are to skin a cat, there are as many ways to do isometric depth sorting.  Almost all that I have found utilize tile-based algorithms.  Though they work with respect to tile-based applications, they don’t seem to do that great for absolute positioning.

Anyway to cut to the fat here is how I achieved Absolute Isometric Depth Sorting without the need to have tile-based logic assigned.  Before I jump in tho, my coordinate space is somewhat diffenent than that of traditional isometric coordinate spaces: x values go from the top-left to the bottom-right portion of your screen, y values go from the bottom-left to the top-right portion of your screen and z values go from bottom to top of your screen.  Make sense?  Okay, let’s go:

Almost any renderable element in my iso-world has to have x, y, z, width, length, and height depending on how many dimensions they occupy (2 vs 3 dimensions is like comparing a plane to a cube).  Let’s assume we are dealing with a cube.  Now since we the viewer represent the vantage point, I created a reference point to compare distances to which resides at x:100000, y:100000 and z:100000 (hopefully we will not exceed any points outside of that).  My sorting method simply compares distances from the right-front-most point of an object from the reference point.  That point is basically x:cube.x + cube.width, y:cube.y + cube.length, z:cube.z Now this is not fail safe but it does a good job in absolute coordinate spaces.

Obviously there is some more robust logic occurring in my IsoScene class in order to depth-sort but this is the basis for the sort.  Check out the demo app here – link

override public function render (recursive:Boolean=true):void
{
	var depthArray:Array = [];
	var infoObj:Object = {};

	var child:IPrimitive;
	for each (child in children)
	{
		infoObj = {};
		infoObj.child = child;
		infoObj.distance = Math.sqrt((camera.x - child.right) * (camera.x - child.right) +
			(camera.y - child.front) * (camera.y - child.front) +
			(camera.z - child.z) * (camera.z - child.z)) * -1;

		depthArray.push(infoObj);
	}

	depthArray = depthArray.sortOn(["distance", "x", "y", "z",], Array.NUMERIC);

	var i:int;
	for each (infoObj in depthArray)
	{
		if (infoObj.depth != i && (infoObj.child.positionInvalidated || infoObj.child.geometryInvalidated))
			setChildIndex(infoObj.child, i);

		i++;
	}

	super.render(recursive);
}