Jump to content
  • Advertisement

Archived

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

bzroom

Fastest way to sort and render?

This topic is 5573 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

I have a linked list of classes, containing an x, y, and a Render. I also have a seperate x,y. Whats the fastest algorithm to run through this list rendering from farthest to closest compared to the stray xy i have? I was originaly trying to like bubble sort the linked list into another linked list hten runing through that rendering. Any suggestions?

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Quicksort is probably the fastest for this. But, there might be other ways to optimize. Are you using this list so that you render transparent polys last?

Share this post


Link to post
Share on other sites
This list only contains transparent polys, i render all my solid stuff then i will go into this algorithm.



edit: Correct me if im wrong, this list contains billboards that are transparent (trees). I do want to render these back to front correct?

[edited by - honayboyz on June 17, 2003 4:14:59 PM]

Share this post


Link to post
Share on other sites
How about as i go through the list, i render the farthest, pull it out - put it in a new list, go throught the original list (loop untill original list is empty), then set the original list pointer to the new lists first element.

Share this post


Link to post
Share on other sites
That would mean traversing the list for each thing you render which would be Bad. What you ideally want to do is sort the list as you insert things. A balanced tree of some sort would be ideal (AVL Tree, red/black tree), but might be a bit of overkill. Simply making sure that things are inserted into the list, ordered based on their distance from the camera should do the trick.

Share this post


Link to post
Share on other sites
Unfortunately, sorting the list as you insert them doesn''t really help if you camera moves a lot - you want to have the list sorted back to front in camera space, not in world space. If you have a system of dynamic particles, then yes, sort it as you insert them since they are being created each frame, but if you have a list of trees in world space they''ll have to be sorted every frame with respect to the camera.

Share this post


Link to post
Share on other sites
I just like keeping track which objects are on the screen and I just render those. As for the rest I just just test if they are on the screen. I am terrible at sorting, though.

Hey, don''t forget to visit my page... by clicking here!

Share this post


Link to post
Share on other sites
Merge sort works quite well for linked lists. I use this in commercial games with very nice results. Not sure who Simon Tatham is, but he came up with something good.

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Share this post


Link to post
Share on other sites
A quad tree or BSP tree gives you a static order that results in a nearly costless ( quasi-linear, n log(n) ) viewdependent back to front sort. Considering the memory cache I think the quad tree could be the best.

But a more simple solution is a double linked list and insert sort. Due to frame to frame coherency, specially if your FPS is high and your rotations are not too fast I suppose this is OK. That is nearly linear when you reorder your list element by element each frame. It think it's called insert sort. ( I have always been bad with naming conventions in software engineering ( ).

I think a binary tree is not relevant in this case. It would become quickly unbalanced and rebalancing it is a painful code and not so efficient : more nodes to process, more memory indirections, cache misses, etc ...

An insert sort was used in Quake1 for ordering the polygon edges (active edge list) in the inner loop their software rasterizing process.



[edited by - Charles B on June 18, 2003 4:57:31 AM]

Share this post


Link to post
Share on other sites
Insert sort is a n2 algorithm for worst case, however, it is n for best case. Quicksort is nlog(n) for worst case and best case. It is why Insert sort is prefered over Quicksort for almost sorted lists.


Oooh, you found the horadric nuke!
Did you know, that by using a horadric nuke, you can blow up Diablo and solve all our problems!

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!