Thread: Z-Sorting

  1. #1
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,071

    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?
    M.Eng Computer Engineering Candidate
    B.Sc Computer Science

    Robotics and graphics enthusiast.

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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.

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  4. #4
    Call me AirBronto
    Join Date
    Sep 2004
    Location
    Indianapolis, Indiana
    Posts
    195
    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.

  5. #5
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,071
    >>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?
    Last edited by psychopath; 02-27-2006 at 01:54 PM.
    M.Eng Computer Engineering Candidate
    B.Sc Computer Science

    Robotics and graphics enthusiast.

  6. #6

    Join Date
    May 2005
    Posts
    1,042
    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.
    Last edited by BobMcGee123; 02-27-2006 at 04:23 PM.
    I'm not immature, I'm refined in the opposite direction.

  7. #7
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,071
    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.
    M.Eng Computer Engineering Candidate
    B.Sc Computer Science

    Robotics and graphics enthusiast.

  8. #8
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Remember to use an epsilon range for floating point operations since they are not precise.

  9. #9
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,071
    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;
    M.Eng Computer Engineering Candidate
    B.Sc Computer Science

    Robotics and graphics enthusiast.

  10. #10
    Call me AirBronto
    Join Date
    Sep 2004
    Location
    Indianapolis, Indiana
    Posts
    195
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 05:50 PM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM
  5. selection sorting
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-13-2001, 08:05 PM