Author Topic: Poly sorting in DirectX (Read 7595 times)

PumpkinPieman · « **on:** 2004-10-10 18:42:10 »

I'm sure a few of you use DirectX, or at least have used DirectX at sometime. Right now (because I took a break a while ago), I'm at the stage of creating scene buffers, or at least thinking of designs of some. Since changing the textures and states cause, or seem to cause a little overhead; a presorting of the poly's before when the scene is loaded is neccessary to optimize the output and reduce these calls. What I'm thinking of doing is first sorting these by opacity, then sorting them by texture. Since most of this is static geometry, I'll leave all the dynamic geometry to objects that you attach to the scene.

Is there anyone here that has dome something like this that could give me some idea's towards how everything should be rendered?

mirex · « **Reply #1 on:** 2004-10-11 14:29:32 »

I've done polygon sorting in OpenGl ... because i had to sort them if they were transparent. OpenGl does not draw transparencies properly if not sorted. So I had to rotate them (into current positions) and then to calculate distances from the camera.

But no idea about DirectX or your problem though ...

Kislinskiy · « **Reply #2 on:** 2004-10-11 15:55:28 »

Vertex/Index buffer switches are most expensive followed by texture changes and state changes. There are many articles at developer.nvidia.com etc. that cover this topic.

Render polygons with an opacity < 100% from back to front, then with a z-buffer enabled you render opaque polygons from front to back but remember to minimize vertex buffer switches / changes.

Micky · « **Reply #3 on:** 2004-10-11 17:27:03 »

Quote from: Kislinskiy

Render polygons with an opacity < 100% from back to front, then with a z-buffer enabled you render opaque polygons from front to back but remember to minimize vertex buffer switches / changes.

You could store your transparent polygons in a bsp, then you can extract them depending on your viewpoint in the correct order. The disadvantage of that is that you can't build strips of your triangles.
One other technique I heard of was to sort triangles "inside-out", then first render the backfacing triangles and then render the frontfacing triangles. That is good enough for many convex shapes.
Many games (for example Jak + Daxter on PS2) don't bother depth-sorting all triangles, because the "transparent object over transparent object" case is rare enough, and you're normally busy enough running around and dealing with traps and monsters to not see the sorting errors.

One other method is to draw your transparent polygons with a locked colour buffer, so you only get the Z values. Then you draw them again with the depth test set to "equal". This of course doesn't allow "transparent on transparent", you'll only get the frontmost triangle rendered over the opaque triangles.

If you're concerned about the rendering order to minimise state changes I agree with Kislinskiy's advice.

Kislinskiy · « **Reply #4 on:** 2004-10-11 18:22:28 »

This whole sorting-thing depends on what your engine are destined to render. You have to experiment a lot. For example it could be that brute force rendering a certain scene is faster than using sorting algorithms on newer machines. You should clarify what your render engine is destined to render and what are your target machines before coding.

PumpkinPieman · « **Reply #5 on:** 2004-10-11 21:01:18 »

Well, the engine I'm planning on making is designed towards rendering 3D scene's as opposed to 3D worlds. It's going to eventually be a fighting engine with both 2D and 3D qualities. A good example of this is:
http://img84.exs.cx/img84/2213/capcomvssnk2_1004_screen028.jpg

I'm going to write collision detection with 3D objects, but I'm guessing I won't really need it as much as 2D collision.

I've read that 2MB ~ 4MB vertex buffers are a good size to be loading every frame with and you should stick to around 150 polys per batch. Index's are alot classified as "first class citizens" to the video card, so they increase preformance as well.

I still haven't grasped the concept of rendering transparent objects front to back, as far as I was aware; as long as you have a z-buffer it will do a check weither or not it's visible anyhow. The topic of semi-transparent objects confuses me a bit.

Kislinskiy · « **Reply #6 on:** 2004-10-11 22:09:15 »

The z-buffer does not know whether a polygon is semi-transparent or opaque. Therefore you have to disable the z-buffer during rendering semi-transparent polygons and render back to front. Then the rasterizer multiplies the pixels correctly. At developer.nvidia.com is a very detailed document about optimal vertex buffer use/size etc... It also important that a vertex-size is - as far as possible - 16/32 bytes so that they fit into the cache lines. With those vertices you have the best performance...

http://developer.nvidia.com/object/perf_docs_by_date.html

Scroll down to the bottom and look at the topics...

sfx1999 · « **Reply #7 on:** 2004-10-12 00:58:32 »

http://www.riaz.de/tutorials/d3d07/d3d07.html

PumpkinPieman · « **Reply #8 on:** 2004-10-12 02:33:21 »

Hmmm, yeah. I understand that part fine, it's just having to order them front to back.

sfx1999 · « **Reply #9 on:** 2004-10-12 02:54:34 »

Front to back?

You render transparent polygons back to front.

PumpkinPieman · « **Reply #10 on:** 2004-10-12 06:19:22 »

Alright, so with solid poly's I don't need to oder them because of the z-buffer. As for the transparent polys, does this mean I have to lock\unlock the vertex buffers and sort them per frame?

Micky · « **Reply #11 on:** 2004-10-12 07:00:54 »

Quote from: PumpkinPieman

Alright, so with solid poly's I don't need to oder them because of the z-buffer. As for the transparent polys, does this mean I have to lock\unlock the vertex buffers and sort them per frame?

It is actually quite easy. For every pixel drawn the gpu compares the new Z value with the value already in the framebuffer. If you set this operation to "bigger than", it will only overdraw pixels that are further to the front than existing pixels.
The problem is, if you draw a transparent pixel you want to see anything that is behind it. But you cannot "squeze" a new pixel behind the transparent pixel, because you only have information about the frontmost pixel.
As I said before, a lot of games don't sort transparent triangles by depth, as you are normally distracted by the game to notice small sorting errors.
If your fighting engine shows the scene only from one direction (like Street Fighter) you can just sort the triangles once as a preprocess relative to the front and then draw them normally. If you can look around (like in DoA) you could sort them relative to the central arena.

PumpkinPieman · « **Reply #12 on:** 2004-10-12 13:07:17 »

Well, that makes sense. Hmm, what are the easiest ways to sort them? I plan on updating it once per frame (or atleast have the option to update them once per frame).

mirex · « **Reply #13 on:** 2004-10-13 06:06:58 »

Whats kind of game is it ? If its 2D you could simply compare polygons distance and sort them into some kind of array by distance. Then draw them from furthest to closest one and its done.
If its 3D then its more complicated....

PumpkinPieman · « **Reply #14 on:** 2004-10-13 07:01:36 »

It's 2D \ 3D.
I may want to have the option of being able to change camera angles and so on, so I don't want to limit myself to a pure 2D engine.

Also, the backgrounds are going to be 3D animated, while the foregrounds\players are going to be sprites.

mirex · « **Reply #15 on:** 2004-10-13 09:03:55 »

In 3D i do it like this:
1) calculate center of the triangles/polygons (by simple math)
2) sort the distances from the camera (if you are in 2D just compare Z coords of the polygons)
3) draw them in that order

you dont have to sort non-transparent and non-textured polygons to speed up the process

Micky · « **Reply #16 on:** 2004-10-13 16:45:15 »

Quote from: PumpkinPieman

Well, that makes sense. Hmm, what are the easiest ways to sort them? I plan on updating it once per frame (or atleast have the option to update them once per frame).

Don't worry about it too much in the beginning. Try to get something on screen and working, before you optimise it.

PumpkinPieman · « **Reply #17 on:** 2004-10-13 17:10:27 »

Quote from: Micky

Quote from: PumpkinPieman
Well, that makes sense. Hmm, what are the easiest ways to sort them? I plan on updating it once per frame (or atleast have the option to update them once per frame).

Don't worry about it too much in the beginning. Try to get something on screen and working, before you optimise it.

I know.

Quote from: mirex

In 3D i do it like this:
1) calculate center of the triangles/polygons (by simple math)
2) sort the distances from the camera (if you are in 2D just compare Z coords of the polygons)
3) draw them in that order

you dont have to sort non-transparent and non-textured polygons to speed up the process

So I'm guessing indices would be the best way to implement this.