Ep. 302 - Comparison Sort for HMH

Quoting myself (must be a new one), but I think I need a new thread for this.

roam00010011
First apologies, I don't fully ask my questions as I mean them, so "full 3d sorting" is not sorting by the 3d point position, it's sorting by the entity's 3d volume, and that was explained.
As for 3d, as is done when all your data is lists of triangles, etc... and you have a z-buffer and drawing front to back.
This was my "if", if you had the data to consider every entity as a 3d with volume, how much work with it take? and once that work was done, can we take a step backwards to our current entity data and remove parts of the algorithm that are irrelevant?

So first, I'd love it if you went the z-buffer route, because I want to learn how its done :)

However as promised, I want to try and give a proper comparison sort, the 'operator <' between entities for a total ordering solution.

Before I start, some things that must be known:
A. The camera is always perpendicular to the X axis.
B. The camera rotation range is always from parallel to the Z axis to parallel to the Y axis (see inage below).
C. No slopes, entities bounding boxes are axis aligned (and I hope I'm using the right working here).

So, for the ordering I'm using a tree, which is O(NlogN) as insertion goes, and it gives us the ability to compare each entity to all the others, without O(N^2).

Well, I'm going to put code where my mouth is.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
struct v3
{
  float x,y,z;
}
struct cube
{
  v3 top, bottom;
}
bool operator < (cube A, cube B)
{
  // any entity that does not overlap on the Z, is behind if its max Z is less or equal to the min Z of the compared to entity
  if (A.bottom.z <= B.top.z)
	return true;

  float diffZ = Max(A.top.z, B.top.z) - Min(A.bottom.z, B.bottom.z);
  // an entity that overlaps on the Z, is behind if its topmost Y is equal or less than the compared to entity
  if (0.0f >= diffZ)
  	return (A.top.y <= B.top.y);
  return false;
}
Logically this solution is valid for any camera position from a top down view (on the Y) to a side view (on the Z),
Now if we use a tree, or any binary inserted list, we will have a total ordering solution that will be valid for any insert order.

The entity positioning I've used to test the ordering is here:
I've placed entities A-E, and the drawing order (back to front) is
1. A
2. D
3. B
4. E
5. C

I've based my logic on the fact that if we take the top right most point of any bounding box, and extend a virtual shadow down the Y and Z to infinity, any bounding box that falls into it is considered behind (as long as we keep the camera positioning rules).
This logic should work with slopes, but I did not test the code above, so no guarantees.

Bottom line, I think this is as near to an almost perfect ordering solution as we can get, without cheating.
And if we do need to cheat to get an optimal map, level generator should be able to create levels that would not break the sort logic.
And again, z-Buffer is always there to save the day.

Cheers,
Roman