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.

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
-------------------------

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

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

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.

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