• ### Announcements

#### Archived

This topic is now archived and is closed to further replies.

# sorting...

## Recommended Posts

daher    100
hi . for making a cool scene i have to use sphere mapping using blending over a base texture on objects i''ve decided to sort planes and draw them far to near using a vector called center_of_plane is there any efficient way to sort''em? and does the center_of_plane do the sorting? i got the camera pos, angles and fov_y. how may i use''em ol? if i should! "The Railgun Master" DaHeR

##### Share on other sites
vincoof    514
quote:
for making a cool scene i have to use sphere mapping

Do you look for info about sphere mapping ?

There''s so many ways of sorting...

First of all, remember that since you''re "only" checking the centre you''ll have some (rare) artefacts.

The simplest way I know is computing all the depth values from software.

AFAIK, You don''t need the fov_y for that operation.

Since you have the camera angles, you can compute the vector of the viewpoint direction. Let''s say you computed it and called it viewpoint_direction.

For each center_of_plane, you can compute its Z value (eg the value of the depth fragment if it went into the depth buffer) with the classic following method :
Z = dot_product( vector_from_viewpoint_center_to_center_of_plane, viewpoint_direction ).

That''s not the real Z value, but it has all the property you look for your sorting algorithm (eg. a closer object will have a lower Z). It''s better than computing the real distance because OpenGL sorting artefacts are due to the depth buffer and nothing else !

Now that you have the Z value for each center_of_plane, you just have to sort that array of depths and draw from ''far'' to ''near''.

Note that negative a Z value may indicate that an object is behind the camera, but in fact it''s not always right.

##### Share on other sites
nitzan    108
I use quick sort for my particle effects. The nice thing about quicksort is that its less expensive if the majority of the elements are already sorted. So once you sort your elements once, each subsequent sort will usually cost less then the original first one.

Nitzan

-------------------------
www.geocities.com/nitzanw
www.scorchedearth3d.net
-------------------------

##### Share on other sites
Validus    122
I think you are it backwards. The Quicksort will perform poory if the file is alardy sorted or nearly sorted, O(n^2/2). If the file is alardy sorted then it will take
N + (N-1)+(N-2)+...+2+1=(N+1)N/2 comparisons so this meast that you are only removing one element ever time so not only do you have O(n^2/2) time but the stack space will be N witch is kinda large for big arrarys.**

Don't get me wrong it is probly the best algo and that is only the worst case, it is O(N lg N) on average.

P.S. if you are looking for a algorithm that will perform well on a nearly sorted data look at the Meargsort is will be O(n lg n) for any data but has a higher mem cost.

** see "Algorithms In C++ 3rd ed." (page 321) for a more indepth disscution about the performence charicistics of Quicksort.

Edited by - Validus on January 11, 2002 2:32:36 PM

##### Share on other sites
daher    100
no i am not looking for info about sphere mapping!

i don''t mean sphere mapping only i mean every thing like glass, chrome.

any way thanx alot for these ideas.
but i dont got the book Validus! but 4sure ill use a quick sorting...

is the quick sort a spicial kind of sorting... or i may use any other algo. like buble?

"The Railgun Master"
DaHeR

##### Share on other sites
Guest Anonymous Poster
Please reframe from using the words "bubble sort" around here .

Quick sort is a algorithm. There''s an implementation in the C Runtime. Search help for qsort.

James

##### Share on other sites
daher    100
sorry....
thanx

"The Railgun Master"
DaHeR

##### Share on other sites
Validus    122
Yea,
Quicksort is just an algorithm, you can ues any algorithm you want to but as some one else said buble sort is very slow. it is said to have O(n^2) time, meaning that the more elements you are trying to sort the function will take longer and longer, growing at that the rake of n^2 plus or minus come constant.

Bubble sort, Selection Sort and Insertion Sort all run at O(n^2)
Shellsort is a bit better but still not good O(n^3/2).

Quicksort and Mergsort run on avarge O(n lg n) witch if you graph you will see that it grows much slower and therfor is a faster algorithm.

Check out http://www.nist.gov/dads/ is a good site for algorithms and look at http://www.nist.gov/dads/HTML/quicksort.html
for some links to implmations to quicksorts, and as was said the C runtime had a bultin quicksort implmation that is a good resource.

##### Share on other sites
Blueshift    122
I use a sorting system on my engine that makes use of frame coherency. It''s rather simple and very fast, average complexity is O(n), worst is O(n log2 n).

I maintain a linked list of all visible transparent nodes in the scene (for the current viewpoint). Now, at every new frame, the sorting order won''t change that much compared to the last one.

So I simply update the visibility list for the current frame: delete nodes, that are now invisible, and add new nodes, that just became visible (to the end of the list). I then run a natural mergesort (a derivative of mergesort, that exploits presorted parts of your data) over the linked list. That sort is very efficient, since most of the list will still be in the right order (from the last frame).

If visibility doesn''t change too much from one frame to the next, average complexity will be O(n).

Another thing to think about (I just recently implemented it in my engine, and it seems worth it): transparent objects, that do not have overlapping 2D projections, don''t need to be sorted, they can be in any order. Or you can sort them by their texture instead, that will minimize state changes.
Just some ideas...

A.H aka Blueshift

##### Share on other sites
daher    100
will ,

i think i messed up somethin, ill tell u the way i am doin it.

i have array of planes[nPlanes]
i got -> (float)planes.distance_from_center_to_view_point.
i want to sort''em in a sorted array which''ll have the indecies of planes based on far->near.
then i''ll call DrawPlane(index); in a loop

- i think the qsort() wont do that for me!
- am i doin it the wrong way?
- if there is a better way to call planes to be drawn without ref. to the index please tell me.
- Blueshift thanx for this gr8 idea, but how may i use it overhere. do u have any suggestions?

thanx ol.

"The Railgun Master"
DaHeR

##### Share on other sites
Blueshift    122
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

##### Share on other sites
daher    100
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

##### Share on other sites
daher    100

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

##### Share on other sites
_DarkWIng_    602
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...

##### Share on other sites
vincoof    514
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 :

          Plane          |          |          |          |          |          |          |   center |   of the *   plane  |          |          |          |projection|                        point to the   * <-----distance-----> *  to plane    |                       project          |

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.

##### Share on other sites
daher    100
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?

##### Share on other sites
vincoof    514
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

##### Share on other sites
daher    100
got it, will try it. thanx

"The Railgun Master"
DaHeR

##### Share on other sites
daher    100
it was bad. the center method was even better.
i got this problem:

        *    |    |    |  here is the plane1    |    *     *--------------------* here is plane2             ^             .             d2             .             v     <--d1-->*  <- view point

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]