Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!icdoc!ra2
From: ra2@doc.ic.ac.uk (Roger Attrill)
Newsgroups: comp.graphics
Subject: Re: I need some depth arrangement/sorting info
Message-ID: <2994@gould.doc.ic.ac.uk>
Date: 8 Mar 91 10:53:05 GMT
References: <14@goblin.ntg.uucp>
Sender: news@doc.ic.ac.uk
Organization: Dept. of Computing, Imperial College, London, UK.
Lines: 26

In article <14@goblin.ntg.uucp> slandrum@ntg.uucp (Stephen Landrum) writes:
>
>Could someone point me to good references for depth arrangement/sorting
>of objects and surfaces?
>

 I was writing a solids modeller a year or two ago and needed a good
routine to sort surfaces into depth order. I was concerned with about
20,000 triangular patches.
 I eventually came up with what I suppose is a very efficient quicksort routine
which took 4.7 seconds on my 8MHz machine to sort 100,000 numbers.
 It appears to be of order nlogn for all cases - random, sorted, and reverse
sorted, The latter two cases of which are faster than the first -
unlike standard quicksort.
 It the fastest sort I've come across, better even than the shell-Metzner sort!
Mail me if you are interested.

Ciao,

 Rog.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
|   Roger C. Attrill   | I don't always think therefore I'm not necessarily. |
|   ra2@doc.ic.ac.uk   |                                                     |
|   Imperial College   |          and other variations on a theme.           |
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-