Sorting options

agamemnus · Post by **agamemnus** » Sat Jan 29, 2011 7:58 pm

So, as some may know, I figured out my problem with "clipping" (it was a z-sorting issue). The basic issue is that the distance-to-camera for the sea rectangle was always changing if I had moving nodes. I don't exactly know how that works, but I solved it partially by putting the sea rectangle into the skybox rendering phase so that it is always drawn first.

----

It isn't entirely solved because I need all my roads and rivers drawn on top of all my areas, and everything else drawn on top of the sea, areas, roads, and rivers. Blindside suggested that I modify the sorting function in CSceneManager to sort certain objects by ID instead of by distance. So, I do have that route.

I also could render things with several drawAll() calls, turning certain nodes visible or invisible as necessary, but that is a bit slow. I could also render individual meshes, but then I need my own culling, transformation, and ray-hit functions.

----

The option to "hack" (as Blindside put it) CSceneManager is the best option for me. But, I guess this will need some maintenance. I do think that what I experienced someone else could have problems with down the road, and custom (or very light) GUIs also need specific and non-(rough)-distance-based, sorting if they are to use drawAll().

----

So... my request/suggestion is that the sorting function be modified to allow for a preset index-based sorting, as opposed to rough distance-based sorting. Here's one way of how I envision it could work:

* Every node would have two extra attributes: call them zIndex (unsigned int) and zIndexSortingEnabled (unsigned byte).
* Currently, there is a node array per render pass, as far as I know. Double these arrays to include nodes with zIndexSortingEnabled equal to 1.
* When IndexSortingEnabled is set, move them to the appropriate array.
* For those arrays where zIndexSortingEnabled is true, sort by the zIndex value instead of by distance.

With this approach, my request/suggestion would be fully implemented, the current rendering speed would not be affected, and nodes would still further be sorted by their render pass type.

----

The one speed hitch is that I don't know how the render pass arrays are implemented. If they are implemented as a simple array (instead of a tree), then setting IndexSortingEnabled for a node would mean having to re-allocate space for the array every time that value changes.
If they are implemented as an array, then it should be made possible to make IndexSortingEnabled set on the node's creation, which could affect many functions.

Perhaps the best solution is to set a global value ("sortNewNodesByIndex"?) that determines whether new nodes are added to the regular distance or the index sorting arrays.

hybrid · Post by **hybrid** » Sun Jan 30, 2011 9:50 pm

The basic idea of extending the sprting algorithm is a good idea. Your approach is only as good as your programming experience, to be honest. It's as complicated and restricted as you need it. Making it more general will allow also others to benefit from this extension, and help in other situations.
Other options or suggestions for this case?

bitplane · Post by **bitplane** » Mon Jan 31, 2011 12:19 am

This case is an odd use case, you have nodes that are very flat and positioned directly on top of each other, which causes the sorting problems. In this case I guess the correct thing is to have your own sorting algorithm.

Maybe renaming and generalizing the light manager into a "node sorter" could help here, it would allow people to use whatever algorithm they liked to sort their nodes, and it would only add one extra function to the scene manager.

agamemnus · Post by **agamemnus** » Mon Jan 31, 2011 3:12 am

Bitplane: Could you explain what you mean about the light manager? I am not sure how it fits into this. ALSO, I actually tried slight z-coordinate differences and they didn't help: I think they need to be fairly big z-coordinate differences, too.

hybrid wrote: The basic idea of extending the sprting algorithm is a good idea. Your approach is only as good as your programming experience, to be honest. It's as complicated and restricted as you need it. Making it more general will allow also others to benefit from this extension, and help in other situations.
Other options or suggestions for this case?

Indeed.

Why I posted how I'd like it to work, as opposed to suggesting to generalize the sort into a function is that it would slow down the sort dramatically. (I am assuming you are using a quicksort?)

A quicksort with a fixed comparison algorithm is faster than a quicksort that calls a function for the comparison. I tested this myself with nearly identical quicksort algorithms: one algorithm called a function, one didn't. The one that didn't was 2 times faster.

For both the Irrlicht distance-based sort and my proposed index-based sort, only a numerical comparison is needed, and if it is generalized with an unnecessary function call, that wastes precious speed.

Besides a distance-based sort or an index-based sort, I really don't know any other sane way you could sort something.

Edit: Ok, a way to generalize this would be to keep the sort as it is, but the actual values of the array the sort is using could be set by the engine user... perhaps a pointer could be passed to the sort array. Something like that...

hybrid · Post by **hybrid** » Mon Jan 31, 2011 11:13 pm

You can safely let such optimization issues to us. If you really want to optimize a few hundred calls per frame you won't get anywhere. So just make some general suggestions...

agamemnus · Post by **agamemnus** » Tue Feb 01, 2011 2:44 am

Well, the general suggestion is "give us the option to sort the drawing calls ourselves", I guess.

agamemnus · Post by **agamemnus** » Fri Feb 25, 2011 9:14 pm

I heard there was some initial stuff for this... anything I can test, yet?

agamemnus · Post by **agamemnus** » Mon Feb 28, 2011 9:37 am

Edit:

OK, I modified the code myself... I must admit that even though I have serious reservations about the efficiency of the sorting method in terms of the number of function and sort calls, the process to change the sort method was relatively painless!

Edit 3 (removed 2, was silly): making it u32 now.

Edit 4: On second thought, s32 actually makes more sense.

Line 518 in CSceneManager.h:

Code: Select all

		struct DefaultNodeEntry
		{
			DefaultNodeEntry(ISceneNode* n) :
				Node(n), sortValue(0) {
     sortValue = n->sortValue;
			}

			bool operator < (const DefaultNodeEntry& other) const
			{
				return (sortValue < other.sortValue);
			}

			ISceneNode* Node;
			private:
			s32 sortValue;
		};

Line 261 in ISceneNode.h: (I am not sure why variables like ID are protected. (?) I made this public. I think)

Code: Select all

  // Sort value of the node.
  s32 sortValue;

devsh · Post by **devsh** » Mon Feb 28, 2011 9:59 pm

screenshot would help...

agamemnus · Post by **agamemnus** » Mon Feb 28, 2011 11:44 pm

?

Edit: I guess you only read my first post... there's a screenshot link in the link there that shows the kinds of problems I had. With the custom index-based sorting solution that I give the code for in my previous post, these problems are now fixed.