Thread: [Algorithms] Sorting polys

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Hi, i need to sort polygons for alpha blended objects.
Can you point me to some resource to do that?

thank you

You could try using a hash table indexed on a quantized z-depth.
Intersecting polys present a bit of a problem - perhaps a dynamic
form of BSP with pooled nodes to avoid dynamic allocation overhead.

Mark

----- Original Message ----- 
From: "Stefano 'Panda' Baraldi" <pa...@in...>
To: "ALGORITHMS" <alg...@3d...>
Sent: Friday, September 08, 2000 4:24 AM
Subject: [Algorithms] Sorting polys

> Hi, i need to sort polygons for alpha blended objects.
> Can you point me to some resource to do that?
> 
> thank you
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Bin-sorting works fine in general and it's quite fast. I find the average
of the z values for the triangles and bin them. You can even do it on
a per-object basis and use the center of the bounding box/sphere.

----- Original Message ----- 
From: "Mark Wayland" <mwa...@to...>
To: <gda...@li...>
Sent: Thursday, September 07, 2000 7:33 PM
Subject: Re: [Algorithms] Sorting polys

> You could try using a hash table indexed on a quantized z-depth.
> Intersecting polys present a bit of a problem - perhaps a dynamic
> form of BSP with pooled nodes to avoid dynamic allocation overhead.
> 
> Mark
> 
> ----- Original Message ----- 
> From: "Stefano 'Panda' Baraldi" <pa...@in...>
> To: "ALGORITHMS" <alg...@3d...>
> Sent: Friday, September 08, 2000 4:24 AM
> Subject: [Algorithms] Sorting polys
> 
> 
> > Hi, i need to sort polygons for alpha blended objects.
> > Can you point me to some resource to do that?
> > 
> > thank you
> > 
> > 
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Of course this has to be done on manually transformed vertex coords.
Anyone knows how commercial quality engines (Q3,UnrealT,...) handle polygon
sorting for alpha blending?
Do they use underlying structures like bsp?

thanks

----- Original Message -----
From: "Amit Bakshi" <am...@de...>
To: <gda...@li...>
Sent: Friday, September 08, 2000 4:18 AM
Subject: Re: [Algorithms] Sorting polys

> Bin-sorting works fine in general and it's quite fast. I find the average
> of the z values for the triangles and bin them. You can even do it on
> a per-object basis and use the center of the bounding box/sphere.
>
> ----- Original Message -----
> From: "Mark Wayland" <mwa...@to...>
> To: <gda...@li...>
> Sent: Thursday, September 07, 2000 7:33 PM
> Subject: Re: [Algorithms] Sorting polys
>
>
> > You could try using a hash table indexed on a quantized z-depth.
> > Intersecting polys present a bit of a problem - perhaps a dynamic
> > form of BSP with pooled nodes to avoid dynamic allocation overhead.
> >
> > Mark
> >
> > ----- Original Message -----
> > From: "Stefano 'Panda' Baraldi" <pa...@in...>
> > To: "ALGORITHMS" <alg...@3d...>
> > Sent: Friday, September 08, 2000 4:24 AM
> > Subject: [Algorithms] Sorting polys
> >
> >
> > > Hi, i need to sort polygons for alpha blended objects.
> > > Can you point me to some resource to do that?
> > >
> > > thank you
> > >
> > >
> > > _______________________________________________
> > > GDAlgorithms-list mailing list
> > > GDA...@li...
> > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Stefano 'Panda' Baraldi wrote:
> Of course this has to be done on manually transformed vertex coords.
> Anyone knows how commercial quality engines (Q3,UnrealT,...) handle polygon
> sorting for alpha blending?
> Do they use underlying structures like bsp?

As far as i know q3 uses qsort for dynamic objects, but there's no sorting for bsp faces. Those
polygons are only sorted at the beginning depending on their sort number and material.

Ignacio Castano
ca...@cr...

I have written a similar shader system. Each shader can be potentially given
a sort number. A mesh (be it dynamic or scenery) has its parts designated to
a shader - there is no copying involved here. The renderer iterates through
the shaders and then for each shader iterates through the mesh chunks
rendering them. I repeat, there is no copying or sorting here. At startup,
each shader is inserted into the shader list in sort order.

I use D3D vertex buffers although I would imagine you can use OpenGL vertex
arrays just the same.

Ok, you can get artifacts with transparent polys but with a little cunning
(fiddling about with the sort orders) you can get rid of most of them. Q3
suffers from the same artifacts.

Bite the bullet. Handling transparent polys properly is a time consuming
pain.

Justin Johnson - Technical Director
Mobius Entertainment
ju...@mo...

----- Original Message -----
From: Ignacio Castano <i6...@ho...>
To: <gda...@li...>
Sent: Thursday, August 10, 2000 10:34 PM
Subject: RE: [Algorithms] Sorting polys

> Stefano 'Panda' Baraldi wrote:
> > Of course this has to be done on manually transformed vertex coords.
> > Anyone knows how commercial quality engines (Q3,UnrealT,...) handle
polygon
> > sorting for alpha blending?
> > Do they use underlying structures like bsp?
>
> As far as i know q3 uses qsort for dynamic objects, but there's no sorting
for bsp faces. Those
> polygons are only sorted at the beginning depending on their sort number
and material.
>
> Ignacio Castano
> ca...@cr...
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Hi

I need a random number sequence with Gauss distribution. Do you know of an
algorithm that can do this. I asume that rand() generates white noise.

Johan Hammes

On Thu, 7 Sep 2000, Johan Hammes wrote:

> Hi
> 
> I need a random number sequence with Gauss distribution. Do you know of an
> algorithm that can do this. I asume that rand() generates white noise.

I've been using this:

double dgauss() {
        return sqrt(-2 * log(drand())) * cos(6.283185307 * drand());
}

drand() gives evenly distributed numbers.

The other alternative is sum of n evenly distributed numbers, with n = 30
the result should have gaussian distribution. AFAIK.

Search for "+random +number +gaussian +generator +source +code".

Does anyone know of a good book or other reference that'd explain various
aspects of generating random numbers to someone that's not so much
mathematically inclined? E.g. how to test whether a random number
generator is good etc? 

Ismo

-------------------| 
 M.Sc., Assistant  | My ehticator machine must've had a built-in moral
 Dept. of CS       | compromise spectral release phantasmatron! I'm a
 Univ. of Joensuu  | genius!
 ia...@cs... |                                        -- Calvin
 Tel:(013)251 5329 | 
 GSM: 040 774 3722 | 

Hi all..

There are two chapters of information on pseudo-random number generators in
a book called "Applied Cryptography" by "Bruce Schneier". Explains a few
methods for generating (almost)  random sequences, mainly aimed at crypto,
but useful none the less.

It shows how to set up a random number generator with a specific and
provable maximum period (number of iteration before it starts to repeat) and
how to use these together to get better randomness.

Note sure if that is of too much interest to you but there are some
applications when this is cool (pixelated fade between images for instance,
when you set the period to be the number of pixel and your guaranteed to
cover all the screen eventually).

Also highly recommend this book to anyone that has to do any security or
cryptography etc for their game (eg networking code). It has C code for alot
of the algorithms and easy to understand explanations for protocol and
algorithms for all sorts of cool things.

Ash.

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On
> Behalf Of Ismo
> Kärkkäinen
> Sent: Friday, 8 September 2000 6:50 PM
> To: gda...@li...
> Subject: Re: [Algorithms] Random Numbers
>
>> [...]
>
> Does anyone know of a good book or other reference that'd
> explain various
> aspects of generating random numbers to someone that's not so much
> mathematically inclined? E.g. how to test whether a random number
> generator is good etc?