explorers' club

explorations in dev, science, sci-fi, games, and other fun stuff!

Absolute Isometric Depth Sorting

6 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

[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);
}
About these ads

6 thoughts on “Absolute Isometric Depth Sorting

  1. Hi there. Nice work on the isometric project. Just wondering where you wound up with this. Were you happy with the final result, and did you feel that the final algorithm worked well in all 3 dimensions?

    • Luck would have it that a user of the as3isolib who happened to be a mad scientist came up with a brute-force algorithm. It has worked in every case thus far. Check out the as3isolib (http://code.google.com/p/as3isolib/) and specifically you want to take a look at the DefaultSceneLayoutRenderer which contains the algorithm.

      • Hey, is the algorithm still basically the same as the one outlined in the original post? Has it changed at all?

      • The algorithm in the DefaultSceneLayoutRenderer hasn’t changed in several years (aside from minor optimizations), however it is not like the one outlined in the original post. Are you looking for something in particular?

  2. Pingback: About isometric world depth sorting « CODE@蝴蝶。夢

  3. This is very good post.
    Am the new bird of this as3isolib. Can u give me some ideas of override render method , when i used this method , it’s throwing some errors, like camera variable is not defined , so can u tell me , how i defined this camera .
    Please suggest me to overcome this issue ..

    Thanks,
    M.Raju

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.