z-sorting algorithm?

Talk about your skill passion! Ask questions, get feedback, post something cool!

Moderator: samw3

User avatar
Posts: 9
Joined: Thu May 14, 2009 9:44 am

z-sorting algorithm?

Postby gnat56 » Tue May 19, 2009 11:47 am


Right now I'm working on a small 3D game engine. I've been having some problems with sorting my objects so they draw in the right order. All my objects are meshes made of triangles. Here's a couple screenshots of the program:



Here's some of my code. I sort all the triangles based on what they return from these functions:

This finds the average position of the triangles on the Z axis:

Code: Select all

    def z_avg(self):
        #return (self.coords[0][2] + self.coords[1][2] + self.coords[2][2]) + self.center
        dist = 0
        for corner in (0,1,2):
            dist += self.coords[corner][2] + self.center[2]
        return dist
This finds the triangle's average distance from the camera (0,0,0):

Code: Select all

    def distance(self):
        dSquared = 0

        for axis in (0,1,2):
            d = (self.coords[0][axis] + self.coords[1][axis] + self.coords[2][axis])/3.0 + self.center[axis]
            #d = max(self.coords[0][axis], self.coords[1][axis], self.coords[2][axis])
            dSquared += d**2

        result=dSquared #sqrt(dSquared)

        return result
If someone has any insight on z sorting, advice would be appreciated.

Elyon's Strength,

Last edited by gnat56 on Sun May 24, 2009 12:20 pm, edited 1 time in total.
User avatar
Site Admin
Posts: 1239
Joined: Sun Dec 16, 2007 2:00 pm
Location: Toccoa, GA

Re: z-sorting algorithm?

Postby samw3 » Tue May 19, 2009 5:24 pm

Welcome to CDN :)

Firstly, you probably know this, but z-sorting will give you problems if you have any intersections.

Now, I'm not a 3d expert, but it appears here that your problem is y-sorting not z-sorting. Triangles that are lower (y) than the camera should sort ascending, those higher than the camera should sort descending.

God Bless!

EDIT: Just had a thought.. you could always sort descending on abs(vert.y-camera.y)
User avatar
Posts: 9
Joined: Thu May 14, 2009 9:44 am

Re: z-sorting algorithm?

Postby gnat56 » Wed May 20, 2009 10:41 am

Thank you Sam! Using the abs() function really helped. We tweaked it a little more and now it looks much better. There's still some glitches, but it's good enough to move on to other things.

Elyon's Strength,

Posts: 40
Joined: Fri Mar 28, 2008 12:10 pm

Re: z-sorting algorithm?

Postby popsoftheyear » Wed Jun 03, 2009 7:04 am

What is your target system? This problem has been solved many times, but it just depends what you're going for. Typically these days, even software renderers implement a zbuffer so that you don't have these render glitches. Z sorting is still useful of course to keep from doing any more complex calculations on the pixels that end up being drawn. We have a software renderer that runs pretty well in production code and we haven't even optimized it with simd instructions of any sort yet, and it's not multithreaded either. That's with a zbuffer and gouraud shading (I know it's not much but it's a start).

If you're targeting slower, older systems, this is the exact problem a bsp tree can help to solve. So what is your goal?
User avatar
Posts: 633
Joined: Sun Dec 16, 2007 5:57 pm
Location: Canada

Re: z-sorting algorithm?

Postby PFC » Wed Jun 03, 2009 11:42 am

I see your using python

are you using pygame/pyopengl or something else?

I had created a game engine using pygame/pyopengl
looking back at my code, I had used three functions for sorting

the first one was simply sort by distance between camera and average of the face's verts
This is the most common sorting method

this represents an issue in special conditions where two faces of different sizes and different angles are close to each other

Code: Select all

..   w
. . w
.  w
c = camera
b = bullet
w = big wall
the wall is closer to the camera on average however the bullet is in front of the wall

a special function can be created to take this into consideration (using the angles and distance as opposed to just the distance) This is a bit more math and allot more CPU power

In most cases, the third option will work best (and from those pictures you posted, should work great for what your doing)
if you have a background that will never intersect or hide objects, you can render in layers

First render your background (that long path in your picture)
Then clear the Z-buffer but do NOT clear the screen buffer
then re-render all the objects using the first sorting algorithm, but do not clear the screen or place a background colour(if you need to, then place a transparent background, though try to avoid this if you can)

I would post some example code... but my code is pretty bad
Posts: 57
Joined: Sun Dec 16, 2007 9:30 am

Re: z-sorting algorithm?

Postby PatrickXX » Mon Jun 15, 2009 8:21 am

Assuming your goal is to sort for efficient rendering: I'd also like to point out that the sorting function can become a performance bottleneck depending on the complexity of the scene and the speed of the processor.

If it's a rendering glitch/artifact issue, then I'd have to echo the comment on implementing a zbuffer.

Who is online

Users browsing this forum: No registered users and 4 guests