 | | | Crosspost: Re: z-depth ordering bug | Crosspost: Re: z-depth ordering bug 2004-03-29 - By NoiseCrime
Back
Hi,
This was a post i made to dirgames-l over the weekend. Seeing as someone has
just asked about sorting issues i thought i might as well post it here. Its
constructed out of several aborted replies to the original post on that list
due to discovering more bizarre things as i progressed.
It should be noted that at the moment i don't claim to know exactly what is
going on within sw3d, but this is behaviour that i've observed when using
it. Hopefuly the information will prove useful.
MODEL PER POLYGON SORTING
My initial claim was to be that this is distinctly possible to achieve,
albeit via lingo and mesh manipulation. Indeed I actually have a tech demo
that shows the method does work, but when trying to apply the same to a
simple tree foliage set-up it fails. As it is now I'm left scratching my
head as to why it worked in specific cases and not others.
The concept is simple, assuming that sw3d renders each model in the order of
the polygons defined in the face list, it would be possible to remap
polygons via there vertices to always ensure the model is drawn back to
front. That is once a model is built we assume the polygon face order is
consistent and so by placing the vertices of the furthest polygon of the
camera into the vertices referenced by the first face and so on we can get
the desired draw order. There are some cravats, each polygon must be defined
by unique indexes, in other words no vertices, UV's or normals can be
referenced more than once, they must be duplicated to avoid dependencies.
Further more when changing the order via re-mapping vertices you must do the
same for uv's and normals, affecting the overall performance of such a
method in lingo.
Like I said I had reasonable success with a tech demo I called 'platoon'
which was inspired by the Total War RTS games (Shogun, Medieval). These
games display armies of several thousand individual entities and is able to
do so by having each entity represented by a billboard or point sprite.
Clearly doing the same in SW3D is possible but I summarised that the per
model overhead would make a generic solution far too slow. So instead I
looked to combining entity billboards/quads into larger meshes finding a
balance between the speed of rendering a single model with the requirement
to update all the quad vertices within the mesh each frame. Of course one
big drawback I soon discovered was the draw order within the meshes would
get messed up. However working off the concept i outline above I was able to
get correct draw ordered meshes of any number of quad entities. For the
purpose of the test i called each mesh a 'platoon'. A platoon can contain
any number of entities and there can be any number of platoons, although in
practice specific ranges for these values where selected. e.g 20 platoons of
81 entities.
In testing I could orbit around these meshes and each frame update the quad
to face the camera and sort the draw order. It worked flawlessly, never
having polygons within a single mesh draw in the incorrect order. However it
proved to much of a performance drain to develop it any further and the per
model sorting obviously failed when the volumes of two models or platoons
mixed (see Woes of Polygon Sorting)
So in the context of replying to the original method I thought I'd have
another go of applying the same concept to tree foliage. I had done some
previous tests, but never really put much effort into it. Alas it turned out
to be much more complex than i initially imagined, and sadly has proven to
be extremely problematic. Indeed I've yet to make it work for a simple tree,
but puzzled as to why, lots of theories but nothing concrete.
WOES OF POLYGON SORTING
Whilst initially I was going to agree with the original posters claim of
just having per polygon sorting per model I realise now from trying to do it
myself just how difficult and performance draining it can be if done
correctly. This is for the simple reason that when rendering transparent
polygons you are effectively reverting to the old 'painters algorithm'
method. You are using a simple sort mechanism using either the triangles
min, max or avg depth from the camera. As such there are many cases where
the draw order becomes ambiguous, most obviously if two triangles intersect
each other, but others exist and are quite common (esp true of most tree
foliage models). I'd say the only time per polygon sorting will work is when
dealing only with convex hull meshes.
I tried to fix this in my own tests by modelling which polygons needed
splitting to remove ambiguities, and whilst this helped it did not resolve
all issues. In fact I'd say that the only way to sort a models polygon soup
accurately and quickly is to use a BSP tree. These can be written so that
they split polygons (resolving ambiguities) and can provide a guaranteed
back to front (or reverse) order. Unfortunately BSP trees really need to be
precompiled and not dynamically generated and this can be relatively slow.
So using them would constrain the mesh to being fixed, that is no further
geometry manipualtion, either via lingo or modifiers.
However the problems don't stop there, as alluded to in the discussion of
the 'platoon' tech demo a real issue occurs if the volumes of two models
intersect. here no matter what the draw order of polygons per model is,
whether they be sorted or not, the fact that one model will always be drawn
before the other means that its impossible to correctly order all polygons.
The only solution is to expand sorting to take into account all transparent
polygons within the current view from all models. This will of course be
prohibitively expensive in most cases. Worse is that if done using simple
depth sorting you'll still have the flaws exhibited by the 'Painters
Algorithm'.
SW3D DOES SORT POYLGONS
Now the most bizarre thing that happening whilst researching this is, was
the production of a simple w3d model that DOES have polygon sorting! I'm
somewhat reluctant to say as I'm sure I must be missing something obvious,
but i have a simple w3d that appears to show that sw3d does sort polygons
within a model under certain conditions. Trouble is I have no idea what
these conditions are, and indeed cannot think of any rules that actually
make much sense. My initial thoughts would be along the lines of a polygon
cap, under which polygons are sorted via simple depth sort. However this
doesn't make much sense as its an arbitrary value, and in true development
needs you'll always have a model that needs just one more polygon to be
sorted over the cap value.
I'll post the w3d on my site so others can check it out and make sure i'm
not going mad.
http://www.noisecrime.com/temp/tree_test.zip
Its a tree mesh with a relatively high trunk polygon count, but the leaf
foliage is created through the use of 3 quads placed in a triangular
arrangement (looking down from above) where no quad touches another quad.
For ease of use I've got a single texture split into four sections, each
section with the same foliage texture but colorized to either R,G or B. All
the quads are collapsed into a single model/mesh and so should not be sorted
based on what we know of sw3d. You'll have to set the leaf model visibility
to both though.
When orbiting the model in the sw3d viewer, the draw order of each quad is
constantly correct. If they were not being sorted you'd expect from at least
one direction the draw order being incorrect. That is if the red quad is
drawn in front of blue and green and you rotated around 180 degrees, then
the same order would produce incorrect results from this view. But what i
see is still the correct draw order! Now if each quad was a separate model I
could understand the draw order being correct (although its unlikely it
would), what I have trouble with is how on earth the draw order is
maintained with these quads all being part of a single mesh!
So all in all lots to mull over. I hope that some people try to push the per
polygon lingo sorting further, perhaps someone can determine if sw3d does
its own sorting and under what criteria, but above all when calling for per
polygon sorting you understand the complexities of what you ask for, and
perhaps some of the cravats you'll have to accept.
Noisecrime 2004
__ ____ ____ ____ ____ ____ ____ ____ ____ ____
dirGames-L mailing list - dirGames-L@(protected)
http://nuttybar.drama.uga.edu/mailman/listinfo/dirgames-l
__ ____ ____ ____ ____ ____ ____ ____ ____ ____
Dir3d-l mailing list
Dir3d-l@(protected)
http://nuttybar.drama.uga.edu/mailman/listinfo/dir3d-l
|
|
|