Greetings.

I'm developing for my software D-form a depth sort renderer.
For the first draft I did a raw bubblesort and it worked OK.

Now, which algorithm is faster betwenn quicksort, mergesort, and
heapsort (or any other)?

I have read that mergesort is better than quicksort when data is
partially ordered. This seems to be the case.
Where to find on the net the algorithms (not the sources, just theory)?

A last question. I confronted the average Z coordinates of each poly to
determine the nearer. Are there better methods?

Thank you in advance
(---------------------------------------------------------------)
( Diego Krota   http://www.geocities.com/SiliconValley/Way/2419 )
(---------------------------------------------------------------)
(      Never do anything you wouldn't be caught dead doing      )
(---------------------------------------------------------------)

Post a reply to this message

Diego Krota <Xdk### [at] geocitiescom> wrote:
: I'm developing for my software D-form a depth sort renderer.
: For the first draft I did a raw bubblesort and it worked OK.

: A last question. I confronted the average Z coordinates of each poly to
: determine the nearer. Are there better methods?

  With that method you will get errors, since it's very difficult, if not
impossible (I don't know which one) to sort all polygons perfectly.
Imagine the following case:

     \
      \
    A/ \
    /   \B
         \
          \
           \
            \

     V <- eye

  There are two polygons here, A and B. If you sort them with that average Z
method, you will get that A is behind B, which isn't true.
  What you need is to maintain a Z-buffer. When you draw a polygon, you
store the z value of each pixel in the buffer, unless there is a value
which is smaller.
  This allows also making space cutting of polygons.

-- 
                                                           - Warp. -

Post a reply to this message

In article <360### [at] geocitiescom> , Diego Krota <Xdk### [at] geocitiescom>  wrote:
>I'm developing for my software D-form a depth sort renderer.
>For the first draft I did a raw bubblesort and it worked OK.

Why don't you use QuickDraw 3Ds RAVE interface. It supports all you need and is 
(relatively) easy to program, all you will have to develop is a efficient algorithm
for clipping (RAVE does not support it, only the QuickDraw 3D high-level interface
does). This would take advantage of the 3D hardware acceleration that more and more
Macs have build-in (all G3 Macs).  You can get the SDK at the usual Apple site. And as
RAVE is a part of QD 3D you don't have to worry (much) about licensing, I think, as QD
3D is available on most Macs today.


Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany

Post a reply to this message

Diego Krota wrote:
> 
> Greetings.
> 
> I'm developing for my software D-form a depth sort renderer.
> For the first draft I did a raw bubblesort and it worked OK.
> 
> A last question. I confronted the average Z coordinates of each poly to
> determine the nearer. Are there better methods?
> 

Yes!  If you are sorting polygons then you can store depth information
in a data structure called a BSP tree (Binary Spatial Partitioning
Tree).

BSP trees are built by BSP tree compilers.  They simply take the data of
the polygons in and output the corresponding tree.   Once the tree is
built, there is no need to do depth sorting of any kind no matter where
the veiwpoint is, because back-to-front information is already stored in
the shape of the tree.  For each position that the veiwpoint takes, its
current position is 'clipped' into the tree, and then an inorder walk of
the tree gives you the polygons in back-to-front order.

The best source that I can refer you to is a book called "The Black Book
of Graphics Programming" by John Abrash.  Beware, the book is very large
and tends to be expensive. According to the book though, Abrash has
published many (if not all) of these articles in Doctor Dobb's Journal,
which may be on the internet in some form.  The book contains a CD with
the full text and more.  Chances are, this CD may have been copied
illegally onto a Warez server somewhere.  Good luck.
.
Steve Horn

Post a reply to this message