#### Archived

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

# sorting...

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

## Recommended Posts

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
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
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
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
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
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
sorry....
thanx

"The Railgun Master"
DaHeR

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

1. 1
2. 2
Rutin
20
3. 3
khawk
17
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633759
• Total Posts
3013715
×