Jump to content
  • Advertisement


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


Sorting Ques.

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

Can anyone give me a good well written explanation of the different methods of sorting polygons for an indoor/outdoor based engine? I''m currently writting my own, but im not entirely sure how to group the polys. I see myslef coming across a few different problems. 1 - Which should have priorety? Sorting polys in a front to back order or sorting them by texture/material? 2 - How do I handle polygons that need to be drawn with multiple textures? I considered sorting them by ''materials'' like in 3ds max, where a 3ds max material can have a diffuse texture, bump maps, etc. but even that is complicated to sort. 3 - When I sort would I be better to add all of these polys into an index/vertex buffer that holds the group? And then render the whole group from one vertex buffer? Or should I just make the group class hold a list of structures that tell it which vertex buffers to render from and where to begin and end? Please help me out with this. Thanks ~Vendayan

Share this post

Link to post
Share on other sites
As long as you are using an algorithm to cull all unseen polys you should be fine with sorting by texture. There is really no reason to sort front to back since hardware z buffer is pretty cheap. Changing textures does not come cheap so this should be your main sorting criteria.

As far as sorting with multiple textures there is no right answer.

You are better off batching all your polys into a single vertex buffer. There is a good article about this on The X-Zone.


[edited by - yzzid on December 4, 2002 7:34:38 AM]

Share this post

Link to post
Share on other sites
I would not sort all the polys just according to their textures, but to their location. Yes, there is a z-buffer that allows you to render your polys in any order and get the correct result, but you loose large amounts of time in testing each pixel, to see wether it sould be rendered or not.
If you sort your polys by location (like in the BSP-Tree sorting method), you only render what you exactly need, and then you can consider loosing time in texture swaping. When you need to render multiple times the same polygon, just change the texture and render it again.
The best thing to do is certainly a mix of both sorting methods, maybe a BSP tree for each texture in the scene.
The utimate method is to split your scene into smaller parts (on part per room for instance, or one part per visible set of polygons given a viewpoint), and build a tree for each part.

Why should you use BSP trees:
- they are used in Half-Life, Quake, Unreal engines, and probably many others
- they not only sort, they also provide a way to tell if any position is IN our OUT of your world. (that is why Quake-style map editors warn you if you have a leak in your world; i.e. a "hole" in your walls). This allows you to test VERY effeciently collisions against walls (and scene elements since you may add dynamic objects into the tree).

Why you should not use BSP trees:
- they must be built in a separate process, because building a tree is highly time expensive. Thus your scene must be static. This is why in a game like Half Life, all mobile elements (like crates, doors, ...) are not part of the BSP tree, and are not rendered the same way (they are not lit with beautiful shadows and all other stuff that need preprocessing)
- it does no z-order rendering (back2front, or front2back), but it''s not a problem since all 3D cards do the work for you with z-buffers, as said yzzid.

About BSP polygon sorting:
* How it works: when you tree is built, each node contains all polygons that lie within the same 3d plane. Taking any other polygon in your scene, it is either:
- in the front side of your plane
- in the back side
- intersecting your plane. In this case, split it into two polygons, one in the back side, and one in the front side.

* When you want to know the position of a 3d point, you test against each node plane if the point is in the back list or the front list. You only have to traverse the tree to find out if the point is inside or outside the world.
* When you want to render the world from a given viewpoint, you know what are the polygons that are behind the eye, and thus that need no rendering. Given the view frustrum parameters, you can skip even more polygons, so that you only render the ones that are seen.


Share this post

Link to post
Share on other sites
Maybe this shouldn't need explained but it seems that you are a bit confused about z-buffers You see, its still a good idea to sort front-to-back because a z-buffer will only make things slower if you order back-to-front. When everything is ordred front to back the z-buffer will tell the hardware what it doesn't have to draw because something will cover it. It will let you give the polys to DX in ANY order with only a small overhead expense and still allow you to get the correct picture, but ordering front to back will let it save the rastuerizer (sp?) from drawing many pixels that may just be drawn over many many times until it draws the closest one.

Another question to add though. Is it really nessesary to keep ALL the verts in 2 different VBs just so that I can draw them all from one? Or is it optimaler ( I like that word ) to load all of the polys in each texture group into the 'drawing VB' one at a time for rendering?


[edited by - Vendayan on December 5, 2002 3:07:42 AM]

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!