Z-Sorting in Software Without Traditional Sorting – PlayBASIC Demo

[Member]

Z-Sorting in Software Without Traditional Sorting – PlayBASIC Demo

In this video, we explore an efficient and surprisingly powerful method for Z-sorting objects in software—without relying on traditional sorting algorithms like quicksort or merge sort.

Instead of comparing and rearranging objects, we use a Z-depth indexed array to organize our scene. Each unique Z-depth becomes a key that points to the first object at that depth, with each object linking to the next—effectively creating linked lists per depth level. At render time, we walk this structure from the farthest (highest Z) to the closest (lowest Z), drawing each object in order.

📌 Key Highlights:

• Demonstrates a scene with up to 1,000,000 objects rendered in software.
• Implements a Z-buffer using a heap + depth map array.
• Shows the benefits of a non-comparative sorting approach (similar in spirit to radix sort).
• Discusses practical object culling, memory usage, and overdraw.
• Demonstrates real-time rendering performance scaling with 10K, 25K, 100K, and even 1M objects.

This method is ideal for software renderers and game devs who want fast Z-sorting without complex algorithms. Whether you're coding games in PlayBASIC or just interested in alternative sorting strategies, this video offers a great breakdown of a simple but effective approach.

Download

  - Download From PlayBASIC

  - Attached bellow

[Member]

thanks for the demo kev.

i will go though this step by step to properly understand it, as it is not what i usually am familiar with.
i undertand using a second array but not adding to a stack or pointing to the next object.

[Member]

  Here's a single file variation.  Using the row as the scene order.

PlayBASIC Code: [Select]

    //  limited refresh rate to 60 or less frames per second
    setfps 60

    // Max possible objects in scene.  
    MaxPossibleObjects = 1000

    //  Object structure.  
    Type tObject
            Link            // Next Object Link    
            x#,y#            // Location on screen    
            size            // Size
            colour        // Colour    
    EndType    


    //  CReate a bank as place object data into each update
    ObjectBank=NewBank(sizeof(tObject)*MaxPossibleObjects)
    


    Dim Row_list(GetScreenHeight())
            

    Dim ThisObject as tObject pointer

    // ------------------------------------------------
    Do        //  MAIN LOOP
    // ------------------------------------------------

        Cls 0
        
        angle#=wrapangle(angle#+2)


        if RefreshScene =false
            cleararray Row_list(),0
            
            FreeItem = GetBankptr(ObjectBank)
    
            //  Make a bunch of things and add them to the list 
            for lp =getscreenheight()-1 to 0 step -1
        
                //  create the data required for this object 
                
                //  Compute some X position by adding a bunch of cos()/Sin() waves
                //  together
                x            =getscreenwidth()/2
                x            +=(sin( Angle#+lp)*100)
                x            +=(cos(((Angle#)+lp)*2)*80)
                x            +=(sin((Angle#+(lp*2))*3)*40)

                Y            =lp
                size        =10+(lp*0.34)
                Colour    =lp*123465 
            

                //  Let the user control one of the items during the update
                if lp=mousey()
                        x=mousex()-(Size/2)
                        y+=Size/-2
                        colour = $ff0000
                        if y<0 then continue
                endif    



                //  Get the address where this should be written 
                ThisObject =  FreeItem 

                //  Write this object onto the heap
                ThisObject.x            =x
                ThisObject.y            =y
                ThisObject.size        =size
                ThisObject.colour    =colour
                    
                // Set the link of this new object to the old object (if any)
                // along this ROw
            
                // So a row stoes all of the objects on it, by linking them
                // in reverse order.  So we're inserting to the head of the 
                // list, pushing any existing items down the list 
                
                ThisObject.link        = Row_List(y)  

                // insert this newly added object to the head of
                // the list of items upon this row.
                Row_List(y)    = ThisObject      

            
                //  move the free pointer past the data we just
                //  wrote into memory. 
                FreeItem += sizeof(tobject) 
            next

        endif



Login required to view complete source code