IMO, quicksort is not very well suited for z-sorting of faces or objects. First, it is recursive and I don''t like recursive functions in the render loop of my engine (efficiency and the risk of stack overflows).

The second point is more important: qsort has a worst case behaviour of O(N²), that''s enormeous. On the average data, this worst case scenario is almost never met, but z-sorted faces are no average data. Depending on how you manage your 3D structures, it is very likely, that they are already sorted in the more or less correct order (from the last frame). Now qsort will expose it''s worst case behaviour on exactly this type of data. Not good.

I like natural mergesort for this task. Worst case behaviour is O(N log2 N), which corresponds to the best case behaviour of qsort. But NAT-mergesort''s best case behaviour is only O(N), and that''s very fast. It is met, when most parts of your data are already sorted in the right order. Furthermore, NAT-mergesort is *not* recursive, stable and very simple to implement.

Just make sure, that you store the results of your sort from the previous frame to be able to take advantage of the algorithm.

There are good documents on the net about natural mergesort, it''s a well known algorithm, just use Google. But there is one page that proposes a slightly modified version of it, which runs about 60% faster, unfortunately the page is in german only. You could try to translate it somehow, or just rip the code http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/natmerge.htm

For your problem, you could do it as follows:

* Make an initial empty plane list

Then for each frame:
1) update your list with newly visible planes (and delete invisible ones), but do not destroy the old sort order of the list.
2) Sort the planes based on z distance (the algorithm will take advantage of the old sort order from the previous frame).
3) Render your list (but do *not* delete the entries !)
4) goto 1

hope it helped.

A.H aka Blueshift

hi,
thanx all for the help... i used natural mergsort it''s on:
http://animal.myip.org/osborne/Alg_DS/proj1.html

All done, You may check the demo and email me the log.

here you go:
http://www.geocities.com/d_a_h_e_r/DaherEngine.zip



"The Railgun Master"
DaHeR

sorry for the delay; i was on a vacation.

thanx guys for testing...

vincoof thanx for the tips. i fixed the console, but it's not updated on my site yet.
validus thanx two , but i think u have problem with your gef3 some voodoo2 got the same frames as your gef3 did! or it might be the cpu? ( the voodoo2's cpu was K62-500 mhz and yours PII-400 mhz which is better two!!! ). try to test it without droping the console if u r interested.

===============================================
Still got a problem:
i am testing planes by distance from the center of plane ( avarage of verticese ) to the camera pos. after making a more complix map some planes were very large that its distance was a bigger number than the distance of some smaller planes behind the large one. then they were on the screen!

am i calculating the wrong distance? or should i devide these planes?


"The Railgun Master"
DaHeR

Edited by - daher on March 11, 2002 8:09:06 PM

If you don''t have to much triangls you should look at radix sort... it has O(n) complexity

There are more worlds than the one that you hold in your hand...

For planes, you have problems because you compute the distance with the center of the plane.
I recommend computing the distance to the projection of the viewpoint on the plane, which is easily computed by the following mathematical formula :

Say the plane equation is defined by points whose coordinates (x,y,z) verify :
a*x + b*y + c*z + d = 0

Then the distance of a point (x0,y0,z0) to its projection on this plane is :
abs( a*x0 + b*y0 + c*z0 + d ) / ( a*a + b*b + c*c )

If the normal vector (a,b,c) is normalized, then you can shave off the division.

Here is a little scheme for explaining that is 2D :




In your case, the point to project is the viewpoint (the center of the camera).
And the plane equation is defined by the triangle/quad that you have to draw.
Note that if this plane is static (ie never moves in the world), then you only have to compute its equation once.

quote:

---

Original post by vincoof
For planes, you have problems because you compute the distance with the center of the plane.
I recommend computing the distance to the projection of the viewpoint on the plane, which is easily computed by the following mathematical formula :

Say the plane equation is defined by points whose coordinates (x,y,z) verify :
a*x + b*y + c*z + d = 0

Then the distance of a point (x0,y0,z0) to its projection on this plane is :
abs( a*x0 + b*y0 + c*z0 + d ) / ( a*a + b*b + c*c )

If the normal vector (a,b,c) is normalized, then you can shave off the division.

---

i don''t got any plane equations. should i get one? or should i learn about it?

If you have three point on your plane, you can get the plane equation.

In the equation :

a*x + b*y + c*z + d = 0

you need to know what are a, b, c and d.

(a, b, c) are the coordinates of the normal of the plane.
You can compute the normal with a cross product if you know three non-aligned points in the plane.

If the triangle is ABC, compute the normal with :
N = AB x AC ("x" being the cross product)
and the x, y and z coordinates of the normal N are respectively the a, b and c values.

Note that you may want to normalize N for faster computations if the plane is static. If the plane moves, don''t normalize.

Once you have a, b and c, you just have to inject those values in the equations to compute d :

d = -a*x - b*y - c*z

where a, b and c are the coordinates of the normal, and where x, y and z are the coordinates of any point in the plane (for example A, B or C)

Hope this helps

got it, will try it. thanx

"The Railgun Master"
DaHeR

it was bad. the center method was even better.
i got this problem:


the distance d1 is less than d2 so the plane1 is drawn at last and this is a very bad problem. any one got any idea


"The Railgun Master"
DaHeR


[edited by - daher on March 13, 2002 10:25:37 PM]

oic.
sorry. obviously you''re not working with infinite planes

there''s no fast method that works 100%.