Z-Sorting

Ok. I'm on to one of the final pieces of the rendering engine puzzle, which is Z-Sorting. I need to Z-Sort all of the objects in the scene (before run-time, since the objects are created and loaded from a file), so that blending will work correctly, and eventually so I can use occlusion culling.

For starters, do I need to use a BSP system to do Z-Sorting? Or is there any way I could use a function like qsort() to sort the objects?

erm, z-sorting will be dependant on the viewpoint (which I assume will be changing). I don't see how you can pre-process this before run-time.

Once you have all the distances to the viewpoint you can sort with whatever algo you want.

I was about to say the same thing. Unfortunately Z sorting is view-dependent and thus you must sort per frame. You can use frame coherence to speed this up. Do NOT sort by faces or per poly. I would do a per bounding volume sort since this would be much faster, but less accurate. BSPs would be the way to go for a static scene, but for a non-static scene you must determine which moving objects are in the frustum and then sort those front to back. If you really think about any one scene, it's not that much overhead since most of everything in your scene is either a room, thus part of a static mesh created in 3DS Max, or it's terrain which uses a different algo.

You could do this at run time, but there is no point in this at all. The z order is going to be changing all the time so there is no point in doing it in the beginning. You should update all your objects, find there z orders based on where your camera is pointing, then do what ever you need to with the information, do this every frame right after updating there world positions and right before rendering, so that you can use if for culling when you get around to that later.

>>erm, z-sorting will be dependant on the viewpoint<<
Ooops! I didn't even realize that.

Ok, determining which objects are in the frustum is simple enough, but its actually sorting the objects that I can't seem to get my head around.

With the view direction, how do I determine the sorted order of the objects (walls, floors, meshs, etc)?
:: ponders this for some time ::
Hmm, ok. Suppose my viewers direction vector is (1.0,0.0,0.0) and its positioned at (0.0,0.0,0.0), indicating the viewer is looking straight down the positive x-axis from the origin. Would this mean that objects would be sorted based on their x-position? Any object with a positive x position being in front of the viewer, and any object with a negative x position being behind the viewer? But what if the viewer isn't looking straight down the axis? With a view vector of (0.5,0.0,0.5), how would you sort on two axis? Am I looking at this completely wrong?

If you have the unit view vector and the center of each object (you don't even really need the center, but it makes the most sense), you can simply measure the distance as:

(Object_Center - PlayerPosition) dot ViewVector;


Then you can sort your objects using that as distance. This is how rendering is done in the depth buffer actually, although the 'view vector' just becomes the Z Axis as the camera stays the same and the modelview matrix rotates the world around you (to make it look like you're the one doing the moving).

If you want to use a BSP tree to speed up the sorting process, look up the painter's algorithm. Basically, when you are traversing a BSP tree to find what node you are in, at each node if you are in front of the plane, traverse the back of the BSP tree, if you are behind the plane, traverse the front of the BSP tree. This will make you arrive in sectors (leafs) that are furthest away from you first (then you still have to sort those renderable items in that leaf with respect to themselves). I believe this was how Doom was able to fake Z-Sorting, although nowadays with lighting and all that hoopla it's actually a lot faster using a depth buffer.

Ok I tried this:

(code may be inaccurate; I'm at school, and can't remember exactly what I did at home)

Code:

---

int comparedist(const void *a, const void *b)
{
  objectdata *od1 (objectdata *) a;
  objectdata *od2 (objectdata *) b;

  GLfloat diff = od1->sortdist - od2->sortdist;

  if (diff > 0)
    return 1;
  if (diff < 0)
    return -1;
  return 0;
}

void zsort()
{
  for(int i=0; i<num_objects; i++)
  {
    vector3d dist = objectP[i].pos-pCam.m_vPosition;
    float objectP[i].sortdist = (dist.x*pCam.m_vView.x)+(dist.y*pCam.m_vView.y)+(dist.z*pCam.m_vView.z);
  }

  qsort(objectP, num_objects, sizeof(objectP[0]), comparedist);
}

---

It works better than before, but it's really buggy. The biggest issue is that it only works in one direction (ie, if i'm looking down positive X, its sorted; if I look the other way, it dosen't seem to sort correctly). And yes, I am calling zsort() before the render loop.

Remember to use an epsilon range for floating point operations since they are not precise.

Ok, I tried the epsilon range, and I didn't seem to make a difference. However, this could be because Google taught me what an epsilon range is just a few seconds ago. I modified a line in my comparison code to this:

Code:

---

float diff = fabs(od1->sortdist - od2->sortdist) < 0.00001;

---

you can also determine what objects are in side of your camera view if you take the dot product divided by there magnitids and taking the arc cosine to find that angle between them.