REQ: Sorting method for faces

REQ: Sorting method for faces

Post by Mark Car » Tue, 17 Jan 1995 17:47:13



Hello all,
   I am looking for a fast method to sort faces.  Here's the low down: I know
the 3D face center, and have a smallish number of faces in any given scene
(about 250-400).  I am looking for a z-buffering method that will give me
optimal speed on this number of faces.  This is a general case, not for a PC
or Mac specificaly.  I have a working method for a mostly sorted list, but
would like a really fast one :-).  All suggestions are welcome!

        Thanks in advance!
        Mark Carey.

--
---

All these opinions are mine, and do not reflect the position of my company.
If the above disclaimer is not applicable, insert your favorite one instead.
3DO/NeXT Programming is more than a hobby.  It's a source of income. :-)
---

 
 
 

REQ: Sorting method for faces

Post by Wolfgang H. A. Fandry » Wed, 18 Jan 1995 18:16:00



On 16.01.95, you thought you had to write about
"REQ: Sorting method for faces":

Quote:> Hello all,
>    I am looking for a fast method to sort faces.  Here's the low down: I
> know the 3D face center, and have a smallish number of faces in any given
> scene (about 250-400).  I am looking for a z-buffering method that will give
> me optimal speed on this number of faces.  This is a general case, not for a
> PC or Mac specificaly.  I have a working method for a mostly sorted list,
> but would like a really fast one :-).  All suggestions are welcome!

>    Thanks in advance!
>    Mark Carey.

What about a simple QuickSort algorithm?
I've used it a many times in 3d games and think that it should be fast  
enough. You'll find the algorithm in any good book.
_Warning!_ it is _very_ slow on mostly sorted lists. The more unsorted  
your list, the more efficient QuickSort will be!

Bye
                Alwin.
--
Computers aren't live.                              Wolfgang Hermann Alwin
Computers are my live.                                      Fandrych

## CrossPoint v3.02 ##

 
 
 

REQ: Sorting method for faces

Post by Champailler Stepha » Fri, 27 Jan 1995 17:03:16


Well, someone (W.FANDRY) spoke about depth sorting with quicksort... Hmmm...
Using a normal sorting algorithm is (I think) not the very best way to sort !
It's better to use a comparison" sort algorithm...

All in all, this means that at each frame you draw, the objects (most of the
time) won't move that much. This means that the way your Z-coordinates are
sorted won't vary very much. So what you "just" have to do is to take care
of what you did before what you'll do.

A good method for solving this problem is to take one Z crd and to compare
it with its neighbourers... It should not take more than 2 or 3 trials to
find out it's new position in the ordered list.

Hope this will help someone..

Stefan (aka Wiz of Imphobia)

 
 
 

REQ: Sorting method for faces

Post by Wolfgang H. A. Fandry » Sun, 29 Jan 1995 19:55:00



On 26.01.95, you thought you had to write about
"Re: REQ: Sorting method for faces":

Quote:> Well, someone (W.FANDRY) spoke about depth sorting with quicksort... Hmmm...

                ^^^^^^^^^^ W.Fandrych, but i'll forgive you ;)

Quote:> Using a normal sorting algorithm is (I think) not the very best way to sort
> ! It's better to use a comparison" sort algorithm...

> All in all, this means that at each frame you draw, the objects (most of the
> time) won't move that much. This means that the way your Z-coordinates are
> sorted won't vary very much. So what you "just" have to do is to take care
> of what you did before what you'll do.

> A good method for solving this problem is to take one Z crd and to compare
> it with its neighbourers... It should not take more than 2 or 3 trials to
> find out it's new position in the ordered list.

AAAAAAAAARRRRRRRGGGGGG!!!!!

You're right.  WHY DID I NEVER SEE IT????  (Banging the head against the
wall, when realizing my own stupidity)

I've  been  programmming  3d-graphics  for  several years, and I _never_
realized this fact.  I replaced the quicksort in a simple 3d-engine last
night and now it's a real lot faster, most of the time!

But I still think, I  can't drop the quicksort completly.  Z-coordinates
remain quite the same, as long  as  you  don't  turn  around  too  much.
Question  now  is:  How  do  I  decide, which algorithm suits the actual
situation?

Hmmm..  I'll have to think about this later - it was a long night.

Quote:> Hope this will help someone..

It helped at least one. Thank you very much! :)

Quote:> Stefan (aka Wiz of Imphobia)

Bye
                Alwin.
--
Computers aren't alive.                             Wolfgang Hermann Alwin
Computers are my live.                                      Fandrych

## CrossPoint v3.02 ##
 
 
 

REQ: Sorting method for faces

Post by Kenneth Slo » Mon, 30 Jan 1995 06:50:48




Quote:> ...
>> A good method for solving this problem is to take one Z crd and to compare
>> it with its neighbourers... It should not take more than 2 or 3 trials to
>> find out it's new position in the ordered list.

>AAAAAAAAARRRRRRRGGGGGG!!!!!

>You're right.  WHY DID I NEVER SEE IT????  (Banging the head against the
>wall, when realizing my own stupidity)

>I've  been  programmming  3d-graphics  for  several years, and I _never_
>realized this fact.  I replaced the quicksort in a simple 3d-engine last
>night and now it's a real lot faster, most of the time!

>But I still think, I  can't drop the quicksort completly.  Z-coordinates
>remain quite the same, as long  as  you  don't  turn  around  too  much.
>Question  now  is:  How  do  I  decide, which algorithm suits the actual
>situation?

The answer is: Insertion Sort.

It's among the easiest sorting routines to code.

It has very little overhead.

It works in linear time when the list is "almost sorted"

(for the nit-pickers: by that I mean: if you can guarantedd that no
element is more than 'k' away from its proper location is a list of n
elements, then Insertion Sort is O(kn).)

And...(getting esoteric)...it's "stable" (which may help avoid numerical
problems)

If you have a list which changes sorted order slowly, then Insertion
Sort is the sort for you.   It is (in my opinion) the one sort that
*everyone* should have in their toolkit.

--
Kenneth Sloan                   Computer and Information Sciences

(205) 934-2213                  115A Campbell Hall, UAB Station
(205) 934-5473 FAX              Birmingham, AL 35294-1170

 
 
 

REQ: Sorting method for faces

Post by Bretton Wa » Mon, 30 Jan 1995 10:11:40




> The answer is: Insertion Sort.

> It's among the easiest sorting routines to code.

> It has very little overhead.

> It works in linear time when the list is "almost sorted"

Or you could use a BSP tree, unless your scene is heavily dynamic.

--

http://www.graphics.cornell.edu/~bwade/

 
 
 

REQ: Sorting method for faces

Post by Wolfgang H. A. Fandry » Fri, 03 Feb 1995 06:52:00



On 28.01.95, you thought you had to write about
"Re: REQ: Sorting method for faces":

Quote:> Or you could use a BSP tree, unless your scene is heavily dynamic.

I use BSP trees, where possible and a lot of other techniques, depending
on the situation.  I just  used  to  quicksort  things like the faces of
independent objects.  For any reason I allways  looked  at  them  as  an
unsorted  mess  of  polygons  and  didn't see that they aren't after the
first time I  sorted  them...   (It  still  hurts,  to  think about that
ignorance.)

Bye
                Alwin.
--
Computers aren't alive.                             Wolfgang Hermann Alwin
Computers are my live.                                      Fandrych

## CrossPoint v3.02 ##

 
 
 

REQ: Sorting method for faces

Post by James 'Emul' Sharma » Thu, 09 Feb 1995 21:08:25




> On 28.01.95, you thought you had to write about
> "Re: REQ: Sorting method for faces":

> > Or you could use a BSP tree, unless your scene is heavily dynamic.

> I use BSP trees, where possible and a lot of other techniques, depending
> on the situation.  I just  used  to  quicksort  things like the faces of
> independent objects.  For any reason I allways  looked  at  them  as  an
> unsorted  mess  of  polygons  and  didn't see that they aren't after the
> first time I  sorted  them...   (It  still  hurts,  to  think about that
> ignorance.)

> Bye
>                 Alwin.
> --
> Computers aren't alive.                             Wolfgang Hermann Alwin
> Computers are my live.                                      Fandrych

> ## CrossPoint v3.02 ##

I sort moy polygons by meens of a doubly linked list, a polygon is
inserted into the list by a routine that looks at the current element in
the list and moves backwards or forwards along the list depending on
weather the current polygon is infront or behind the current polygon
untill it finds the appropriate position to insert the poly into the
list.  

The key element for speed in this algorithum is how to pass polygons to
this routine,  the world culling algorithum passes out a list of *maybe*
visible polygons that are *roughly* in z order so these sort into the
list very fast,  the objects are similer and are processed one at a time
so when i stat to process an object there may be a rapid movement in the
list but only they small movements around the list are erquired after
that.

This is very fast and works as faster than bsp based sorting in my
specific situation because of the manner to which the world culling
system passes its data out.

James

--[James E. Sharman]----------------------------------------------------------
Beavis: Wouldnt it be like cool if people on newsgroups just     68 Renny Road
        like talked total hu- rubish,                            Fraton
Butthead: Cool, huh h h huh  and like flamed people who said     Portsmouth
          something intelegent because like their to stupid      PO1 5BA
          to understand. . hey it is like that - shutup Beavis!  England


 
 
 

1. Fastest sorting method for 030/040/060

Hi, readers!

I think thissubject has been discussed to death, but this is the
first time I read this newsgroup, due to a problem with the game
we`re workin` on.

The problem is, that we use an "average z-sorting routine"
which seems not to be accurate enough.

Has there been found any newer/better way to sort polygons (triangles)
on slower computers ?

Later,
Emmanuel, Team *AMIGA*  (A1200/060/16MB/4xCD)
--
Producer of PHOENIX, a new 3-D-space-opera for Amiga
C4D4-Artist, DpaintV-Fanatic,SciFi-Shortstory-Writer
Visit the FUTURE TALES Site under:    http://www.xgw.fi/~slice/ftales/
----------------------------------------------------------------------
"Tell me something about...Your mother?"
"My mother ? I`ll tell You about my mother..."

2. Opening maya up with a mel script.

3. Sorting list of face edges into clockwise order?

4. acceleration

5. Face sorting

6. 3DSR4 - Various questions

7. sorting 3d faces please help !!!

8. View Frustum eqn's?

9. Face Sorting

10. Best face sorting algo for a 3D engine?

11. Req: Assembly 320x240x256 Line Drawing Method

12. req: Apple Smiling Face

13. Phantom face Image Program -like the police use - make faces from face parts