Sign in to follow this  

Depth Sorting Algorithms

This topic is 2848 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello I am writing 3D software rendering engine for my hobby OS. So far i have world cut and sorted within AACube tree. And i use viewing frustum to determine visible parts. Visible edges are clipped to frustum in 3D space for speed. My polygon filler builds and renders list of scan lines. Now i need to depth sort for proper rendering order. I use high rez (1024x768x32bpp) so z-buffer is no option. First i thought of span/edge sorting but it seem very slow. If you have any ideas or refs i would be grateful to know them. Thanks for your time.

Share this post


Link to post
Share on other sites
A modern computer has no problem with a 1024x768 depth buffer, even in software.

Old 3D games - that did not actually have z-buffers available - commonly used a sort based on the centroid of the triangles. This causes some flickering in the worst case, but is relatively fast. The alternative is to split all the tris at their intersections, and sort the split triangle fragments by depth; while producing correct results, this can be very inefficient (at least O(n2) complexity where n is number of triangles).

Share this post


Link to post
Share on other sites
Also, the optimal algorithm used for the sort depends on how many triangles there is to sort, and whether or not they are already in approximately correct order before sorting (in case you sort at object level before rendering).

Share this post


Link to post
Share on other sites

I use a binary tree, sorting a pythagorean-squared distance from camera to triangle/mesh, and just re-build the tree every frame.. but perhaps rebuild the tree only when the camera moves beyond a certain threshold distance? and maybe this distance threshold decreases as the number of tris/meshes in the scene increases ?

It's pretty fast, but I use it only for sorting blended particles with varying blend functions in OpenGL.. I don't know how it would perform sorting an entire scene of triangles.

Share this post


Link to post
Share on other sites
Seems like i will have to implement a few ideas and benchmark them...
I work with polygons (not always triangles) so splitting tri's wastes time.
Basically i am creating a span array from n-sided convex polyhedra.
I am reading Abrash's article on span sorting at the moment.
Seems like they abandoned the idea for Quake and stuck with BSP sorting.
But my engine is for mostly outdoor so i choose AACube-tree design.
Maybe to have the best of both worlds my engine needs both methods.
To use BSP/portal when indoor and AACube-tree when outdoor.
So many choices to play with in such a short lifetime...

I take all the advice i can get :)
An old wiseman once told me:
Experience is cheap when it is second hand.
Now i see what he means :P

Share this post


Link to post
Share on other sites

This topic is 2848 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this