Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / Polygon sorting algorithms Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Aries

June 29, 1999, 02:32 PM

i am an average competent c programmer, and i am working on a 3d game and engine in my spare
time ive come to the conclusion that since i love fps games so much i might as well do a fps.
i am trying to decide what is the best way to go about doing my poly gong sorting and collision
detection against those polygons. ive had thoughts of doing a straight bsp system but that in
the long run is too slow i think, portals i cant seem to find any real good documentation on,
there is also the thought of using the quake/2 bsp. i suppose i came here for a good debate and
information on these thecniques and other possible techniques. if it is posible what ever
possible soultions come up it would be much appericated if there is implememntation info or
even source to go with it.

P.S.
although i am a good programer i would like to keep things as simple as possible for future
reference and to pass out my source code when the project is finished. i am targeting my engine
at win9x/nt and opengl/???d3d??.

Aries

 
Tim Smith

June 29, 1999, 03:31 PM

I would checkout the Harmless Algorithms here on flipcode in the features section. On Harmless's website, there is also a letters section that talks in depth about different systems.

FYI: In my engine, I ended up using a leafy BSP tree with precomputed visibility information from the portals generated by the BSP tree. However, do to some other requirements I have, I am also doing edge rendering, some portal rendering, and just a dash of active edge stuff. Like someone said in his feature here on flipcode, feel free to use a combination of techniques. BSP, portals, active edges, etc... are all tools and not whole solutions.

 
Parashar Krishnamachari

July 01, 1999, 02:36 PM

Aries wrote:
>>i am trying to decide what is the best way to go about doing my poly gong sorting and collision
>>detection against those polygons. ive had thoughts of doing a straight bsp system but that in
>>the long run is too slow i think, portals i cant seem to find any real good documentation on,
>>there is also the thought of using the quake/2 bsp.

If you just want a straight sorting algo for each frame in some dynamic world, I think the best option would be the "ordering table." Yep, it's another algo in flipcode's document archives. It's one-pass, and is always O(n).
It works just like a hash-table... You have an array of pointers to polygons. The indices in the ordering table correspond to average Z of each poly. If two polys share the same average Z, you make a linked list out of it. For speed's sake, insertion into some linked list is at the front of the list.
As mentioned in the document this is about as fast as regular sorts can get and is the same one used in the Playstation hardware. For static worlds, of course BSP's are usually fast. Ordering tables are also not all that fast when the polygon counts are very low, and like any straight sort, it doesn't handle interpenetrating polys. With high poly counts, of course, BSP's have problems, because you have to deal with recursive list traversals.
You'll have to include something to deal with overdraw... no sort algo can handle that... you can use portals, S-Buffers, C-Buffers, whatever... The site is loaded with DOC's about that stuff and you'll have to decide what you want to do.

- C.P.I. / ASMiNC

 
This thread contains 3 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.