English Amiga Board   Amiga Lore


Go Back   English Amiga Board > Coders > Coders. General

 
 
Thread Tools
Old 11 November 2008, 22:19   #1
rbw
 
Posts: n/a
Weird quicksort routine

(Or perhaps just me being stupid.)

I've been trying to understand why I can't get this quicksort routine to work, it was originally a part of the "howtocode" series of articles (that you can find for instance here: http://www.mways.co.uk/amiga/howtocode/text/vectors.php

In that version, the quicksort routine is incomplete, i've got my example here: http://www.itsahit.com/ola/qsort/qsort.s

What I'm trying to do - is to sort my coordinates (Rotcoords) with respect to Z. The coords are arranged in a linked-list, formed as per description in the qsort rout (at least the way I interpreted them).

dc.w nextpointer2, x1, y1, z1
dc.w nextpointer3, x2, y2, z2
.
.

After the sorting is done; I should have the pointer to the element with the largest Z-factor in d0 and just follow the next pointer to go down the list... but... no.. It seems like the re-ordering of the list makes it stuck in an infinite loop, so that the next pointer is points to the same element again. And that really puzzles me, since the routine is wide spread (and old) and I can't really imagine it being incorrect, or?

"dumplist" just moves the z-factor of element1 into d1, second into d2.. to d7. An easier way of debugging is to hex-view the result (in asmone: h (a0) )

I'd appreciate if someone could shed some light on this..
 
AdSense AdSense  
Old 11 November 2008, 23:34   #2
Kalms
Registered User
 
Join Date: Nov 2006
Location: Stockholm, Sweden
Posts: 131
Quick observation:

Code:
permute        
		cmp.w WghtOffs(a5,d3.w),d2 ;entry weight<pivot weight?
		ble.s lower
		move.w d6,NextOffs(a5,d3.w) ;Insert BEFORE Nentry  [1]
		addq.w #1,d4 ;increase size of list 1
		move.w d3,d6 ;Set new Nentry
		bra.s done ;Continue the loop...
lower		
		move.w NextOffs(a5,d0.w),NextOffs(a5,d3.w)  [2]
		move.w d3,NextOffs(a5,d0.w) ;insert AFTER first entry
		addq.w #1,d5 ;size of list 2
done		
		move.w NextOffs(a5,d3.w),d3 ;Get next entry   [3]
		dbf d1,permute
The above loop will iterate through one list, and build two new lists. However, locations marked [1] and [2] will stomp over the next-ptr which is subsequently read at [3]. Thus, fetch the old next-ptr at the beginning of the permute-loop, and keep it around in a register, so [1] and [2] don't affect you when you want to go to the next element in the original list.

Other than that, well, I've never seen qsort implemented using singly linked lists so I can't vouch for the validity of the rest of the code. Wish you luck.


[edit] By the way, if you really are sorting polygons then you probably don't need exact sorting results. Create 256 linked lists (heretofore referred to as "buckets"). Initialize them all to be empty. Go through your set of items, and depending on the sort key (say, the upper byte of the Z-value), throw the item into the corresponding bucket.

Once this is done, go through the buckets in order and render their contents.

This gives you sorting which is accurate on 8 of the 16 bits of your Z values. Works "good enough" for low-polygon 3D graphics (and this is pretty much how many PS1 games did their sorting, along with various tweaks). The algorithm is normally referred to as "bucket sort", by the way.

Other algorithms of interest are radix sort + insert counting (aka counting sort). Radix sort + insert counting, or radix sort + bucket sort, allows you to sort on the full key (be it 16 bits or 32 bits) in linear time.

Last edited by Kalms; 11 November 2008 at 23:45.
Kalms is offline  
Old 12 November 2008, 13:15   #3
Photon
Moderator
Photon's Avatar
 
Join Date: Nov 2004
Location: Hult / Sweden
Age: 100
Posts: 4,088
I have a source of a vectorbobs part I made in 1991 that uses 6 top bits of Z-coord+tweaks to not have to clear the "buckets". Bucket sort, hm. Never knew the name existed When was it invented?

Ola, Quicksort is great when the number of items is large. If it's like 50-80 polygons you might just use a scan for most distant poly, draw it and mark it as drawn, then scan again for the next poly.

Last edited by Photon; 12 November 2008 at 13:21.
Photon is offline  
Old 12 November 2008, 15:29   #4
Kalms
Registered User
 
Join Date: Nov 2006
Location: Stockholm, Sweden
Posts: 131
An alternative name for bucket sort is "bin sort". It's probably older than the Grand Canyon.
Kalms is offline  
Old 12 November 2008, 17:33   #5
Samurai_Crow
Team Chaos Member

Samurai_Crow's Avatar
 
Join Date: Aug 2007
Location: Loveland, CO USA
Age: 40
Posts: 286
Send a message via Yahoo to Samurai_Crow
If I have to use a comparison sort, I use a natural merge sort. Unlike a quicksort, which degenerates to n^2 passes if you have an already sorted list, it sorts stuff that's in order already using only a single pass.

Here's how it works: You go through the list adding every item to a region list and any time you find something out of order, you start a new region. You may have some regions that are one item long and some that are very long. Then on to the merge phase: You check if there are two or more regions on the first region list. If not then you're already sorted. If so, then take the top two regions and compare the top two entries adding the lower one to another region on a second region list. When one of the regions is empty just copy the rest of the other region to the destination region. Once those two regions are empty, remove them from the source region list and take the next two. If you have one region left at the end, just copy it to the destination list. Switch lists and repeat until you have only one sorted region.

For a Z-buffer, I wouldn't use a comparison sort though. I'd use a base-16 radix sort.
Samurai_Crow is offline  
Old 12 November 2008, 19:46   #6
rbw
 
Posts: n/a
Thanks a lot guy's, I'll greet you all when the demo is done .
 
Old 12 November 2008, 21:46   #7
Photon
Moderator
Photon's Avatar
 
Join Date: Nov 2004
Location: Hult / Sweden
Age: 100
Posts: 4,088
Quote:
Originally Posted by Kalms View Post
An alternative name for bucket sort is "bin sort". It's probably older than the Grand Canyon.
Had a look at Wikipedia. Earliest mention is from 1992, but then again it's Wikipedia. Not that ordinary encyclopedias usually care about these things.

Mine bypasses the histogram/scatter phase, improves coord bit precision by one, and needs no clearing of buckets.

But basically, I was just curious who implemented the first working BucketSort() Since I'm into algorithm history.
Photon is offline  
AdSense AdSense  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Workbench execute routine BlueAchenar Coders. General 4 14 January 2009 17:38
Keyboard routine bippym Coders. General 2 15 July 2007 13:15
SetPoint routine MidJasper request.Other 2 03 February 2007 21:10
problem with txt routine. redblade Coders. General 6 02 June 2006 09:51
Looking for some routine code Akira Coders. General 4 18 December 2003 00:51

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 11:53.


Powered by vBulletin® Version 3.8.8 Beta 1
Copyright ©2000 - 2014, vBulletin Solutions, Inc.
Page generated in 0.13551 seconds with 11 queries