Span Grid

Span Grid is a modification of the classic span buffer that uses a static buffer instead of dynamic lists. The purpose of any span buffer is to speed up the rasterization of polygons in software 3D rendering.

How it works

The principle of the algorithm is that triangles are divided into horizontal segments — spans. Instead of immediate rasterization, they are added to a special structure — span buffer.

When adding a new span, it can modify existing spans or modify itself, depending on the type of interaction: full overlap, partial overlap, or intersection.

Rasterization only occurs after all polygons have been spanned. This prevents the same pixels from being calculated multiple times — a key optimization used in early 3D games.

Advantages and disadvantages of implementation

Advantages

1. No memory allocations during rendering
2. No need to sort spans
3. Very fast adding span to buffer — at best O(1)

Disadvantages

1. Requires a significant amount of memory (but the size is constant throughout the program)
2. SIMD vectorization is more difficult to implement

Example

In examples/ I left a primitive program that demonstrates how my library works. It draws two triangles in the console:

#                                             
 ####                                         
  ######                                      
   #########                                  
    ############                              
     ##############                     :     
      #################          ::::::       
       ################### :::::::::          
        ######################::::            
         #########################            
       :::###########################         
:::::::::::##############################     
::::::::::::###########################       
:::::::::::::#########################        
::::::::::::::######################          
:::::::::::::::###################            
::::::::::::::: #################             
:::::::::::::    ##############               
::::::::::        ############                
::::::::           #########                  
::::::              ######                    
:::                  ####                     
:                     #