Highly Optimized scanline filing algorithm inspired by c way of writing algorithms

OptimizedScanline.kt

package scanlineFilling

/* each edge consists of 4 values: the yMin, yMax, xOfYMin and the slopeInverse thus the total number is 4*/
const val SizeOfVariablesPerEdge = 4

/**
 * the values we need to store are recorded in an array, and these are their indices.
 * Essentially something like this
 ```
Index:      0     1     2     3     4     5     6     7     8     9    10    11
of elements
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
Field:   │yMin │yMax │xMin │slope│yMin │yMax │xMin │slope│yMin │yMax │xMin │slope│
Value:   │10.0 │20.0 │5.0  │0.5  │15.0 │25.0 │7.0  │0.33 │ 5.0 │12.0 │2.0  │-0.2 │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
Record:     [ Edge 0 ]         [ Edge 1 ]         [ Edge 2 ]
 base:          0                4                    8
Logical i
(index of edge 0                 1                   2
record)
```
 * whereby the base is the offset in the flat array where the record for logical index i starts.
 * The logical i is the index of the edge record — like saying "this is edge #0", "edge #1", "edge #2",
 * Each record has at least 4 elements: yMin, yMax, xMin and slope. Thus record size is 4
 * Each 4-float block is a "virtual struct" representing an edge.
 * You access the N-th edge's field with:
 * ```
val iBase = i * 4 [recordSize]
val yMin = data[iBase + 0]
val yMax = data[iBase + 1]
val xMin = data[iBase + 2]
val slope = data[iBase + 3]
 * ```
**/

const val YMinimum = 0
const val YMaximum = 1
const val XOfyMinimum = 2
const val SlopeInverse = 3

fun createEdgeTable(polygonVertices: LongArray): FloatArray {
    val numberOfVertices = polygonVertices.size
    val edgeData = FloatArray(numberOfVertices * SizeOfVariablesPerEdge)
    var count =0 // actual number of edges we will actually store
    for (i in 0 until numberOfVertices){
        /* the two edges meeting or going from this vertex: pre-decessor & sucessor
        for each edge, we pack the two coordinates into the 64 bits i.e, for x we store in the upper 32 bits
        * by simply shifting the x coordinate to the left by 32 bits, then we combine with y bits which occupy
        * the remaining lower 32 bits
        * val packed = (x.toLong() shl 32) or (y.toLong() and 0xFFFFFFFFL) */
        val firstEdge = polygonVertices[i]
        val secondEdge = polygonVertices[ (i+1) % numberOfVertices]
        // extract the packed x, and y coordinates
        val x1 = (firstEdge shr 32).toInt() // extract the first 32 bits of the long bits making up the first-edge
        val y1 = firstEdge.toInt() // access the lower 32 bits directly since they are already in place
        val x2 =(secondEdge shr 32).toInt()
        val y2 = secondEdge.toInt() // in jvm if you call long.toInt(), it will only keep the lower 32 bits, so we are accessing the lower 32 bits directly

        if (y1==y2) continue // discard horizontal edges because they are not intersection points
        val yMin = minOf(y1, y2).toFloat()
        val yMax = maxOf(y1,y2).toFloat()
        val xOfyMin = if (y1<y2) x1.toFloat() else x2.toFloat()
        val inverseOfSlope = (((x2 - x1).toFloat()) / (y2 - y1).toFloat())
        val base = count * SizeOfVariablesPerEdge
        edgeData[base + YMinimum] = yMin
        edgeData[base +YMaximum] = yMax
        edgeData[base +XOfyMinimum] =xOfyMin
        edgeData[base + SlopeInverse] = inverseOfSlope
        count++
    }

    /* count* edgeSize gives us the number of allocated floats in our array, or rather the cut off point,
    * since we might have pre-allocated a lot of space to store the unknown the floats, we trim our array to the known
    * number of edges we will store */
    val finalEdges=edgeData.copyOf(count * SizeOfVariablesPerEdge)
    stableSortByYThenX(finalEdges)
    return finalEdges
}
fun FloatArray.getFieldOfAnEdge(fieldIndex:Int, currentNumberOfEdges: Int): Float{
    val cutOffPoint=currentNumberOfEdges*SizeOfVariablesPerEdge
    return this[cutOffPoint+fieldIndex]
}

/**
 * Uses a heap sort to sort the edges using yMinimum as the primary-key then fall back to the secondary key: x-of-y-minimum
 * if two edges start at the same y-coordinate, we will use the secondary key: x-of-y-minimum
 */
private fun stableSortByYThenX(unsortedEdges: FloatArray){

    val edgeCount = unsortedEdges.size/SizeOfVariablesPerEdge
    // heap-sort by default does not ensure stability because equal keys may switch,
    // thus we introduce a third-key which is original index for the edges, so if you have 3 edges, we will have
    // 0,1,2
    val edgeIndices = IntArray(edgeCount){it}

    // create the heap
    for (i in edgeCount/2 -1 downTo 0){
        buildHeap(unsortedEdges,edgeIndices,
            edgeCount,i,SizeOfVariablesPerEdge)
    }
    // sort by moving the maximum to the end
    for (end in edgeCount-1 downTo 1){
        edgeIndices.swap(0,end)
        buildHeap(unsortedEdges,edgeIndices,
            end,0, SizeOfVariablesPerEdge)
    }
    /* when starting, the edge indices might be [0,2,1] however after the heap-sort
    * they might be [2,0,1] whereby index 2 represents the smallest edge and so on.
    * so we re-order the edge records in our float-array on the basis of the sorted edges in the edge-indices. To understand this
    * assume our unsorted edges array looks like this
    * 10.0f, 20.0f, 5.0f, 0.5f,     // Edge 0 base/offset =4
    * 15.0f, 25.0f, 7.0f, 0.33f,    // Edge 1 base/offset = 8
    * 5.0f, 12.0f, 2.0f, -0.2f      // Edge 2 base/offset =12 .. and so on
    * Now in the first loop assuming i =0, to get the particular edge
    * we will indices[0]=2 * 4 = 8 [this gives us the offset of the edge 2 we are copying from]
    * thus take the second edge record then copy it to, indices[1] =0 *4=0, the first edge's position
    * This wil result in something like this
    * 5.0f, 12.0f, 2.0f, -0.2f,   // Edge 2 (first)
    * 10.0f, 20.0f, 5.0f, 0.5f,   // Edge 0
    * 15.0f, 25.0f, 7.0f, 0.33f   // Edge 1 (last)
    * */
    val sorted = FloatArray(unsortedEdges.size)
    for (i in edgeIndices.indices){
        val from = edgeIndices[i] * SizeOfVariablesPerEdge
        val to = i * SizeOfVariablesPerEdge
        for (j in 0 until SizeOfVariablesPerEdge){
            sorted[to + j] = unsortedEdges[from+j]
        }
    }
    // copy the sorted indices back to the now sorted edges
    for (i in unsortedEdges.indices){
        unsortedEdges[i] = sorted[i]
    }
}

/**
 * builds the heap from bottom to top: from the parent of the last node
 * assuming you have indices [0,1,2] which represents the indices of the edges
 * so start will be 0 (3/2 -1), hence using index 0, left and right of its children wil be
 * 1,2. Now compare the edge at index[0] with that of index[1] and index[2]
 * if yMin[0] < yMin[1] then the largest will be 1 and
 * yMin[1] > yMin[2] then in such case no change
 * so swap index 0 with 1 [0,1,2] -> [1,0,2]
 * our max heap built will therefore be: [1,0,2]
 * Generally to understand this, think of this as an array-based binary heap. We have i which is an index of item in the arra,
 * now the next two items will be regarded as parents of the first i such that:
 * ```
 * Parent index = i
 * Left child = 2*i+1
 * Right child = 2*i+2
 *         15 (i=0)
 *         /   \
 *     10(i=1)  5(i=2)
 * ```
 * where the 2 represents the children of the node
 * We're checking if node at i=0 is greater than its children.
 * If not, we swap and recursively buildHeap() the affected child.
 * The recordSize here is count of the consecutive floats in one row
 * | yMin | yMax | xOfYmin | slopeInverse |
 * for element at i=0, then record starts at 0 *4=0
 * for element at i=1 then record starts at 1*4=4 and so on
 */
private fun buildHeap(edges: FloatArray,
                      originalEdgesIndices:IntArray,
                      size:Int,
                      indexOfCurrentNode: Int,
                      recordSize:Int){
    var largest = indexOfCurrentNode
    val left = (2*indexOfCurrentNode) +1
    val right =(2* indexOfCurrentNode) +2
    if (left < size && compare(edges,originalEdgesIndices[left],
        originalEdgesIndices[largest],recordSize)>0){
        largest=left
    }
    if (right< size && compare(edges, originalEdgesIndices[right],
        originalEdgesIndices[largest],recordSize)>0){
        largest=right
    }
    if (largest!=indexOfCurrentNode){
        originalEdgesIndices.swap(indexOfCurrentNode,
            largest)
        buildHeap(edges,originalEdgesIndices,size,largest,
            recordSize)
    }
}
private fun compare(
    edges: FloatArray,
    index1: Int,
    index2: Int,
    recordSize: Int
): Int {
    val base1 = index1 * recordSize
    val base2 = index2 * recordSize
    val yMinimum1 = edges[base1 + YMinimum]
    val yMinimum2 = edges[base2 + YMinimum]

    if (yMinimum1 != yMinimum2) {
        return yMinimum1.compareTo(yMinimum2)
    }

    val xOfYMinimum1 = edges[base1 + XOfyMinimum]
    val xOfYMinimum2 = edges[base2 + XOfyMinimum]

    if (xOfYMinimum1 != xOfYMinimum2) {
        return xOfYMinimum1.compareTo(xOfYMinimum2)
    }

    // If yMin and xOfYMin are equal, maintain original order
    return index1.compareTo(index2)
}
private fun IntArray.swap(i:Int, j:Int){
    val tmp = this[i]
    this[i] = this[j]
    this[j] =tmp
}
typealias drawPixels = (x:Int, y:Int)-> Unit

/**
 * This is the scanline fill algorithm. It takes in an edge table data structure, and drawPixels function for drawing
 * the filled pixels on the screen or terminal or whatever medium you use.
 * The first step is to add new edges starting at the first scan line, and then once it hits a ```yMin``` that is after
 * the current scan line we stop. For each matching edge, we create a copy of its record in a float array
 *  then add it to the current active edges
 *  The second step is removing edges whose yMaximum are equal to the current scan line, because in such a case,
 *  the scan line is at the top of the edge so it is not active or it is not currently being processed
 *  Third step is sorting the active edges using the xOfYminimum key to ensure the edges appear in left - right order on
 *  the scan line
 *  The fourth step is filling in between the pairs, we use the even-odd rule: odd is when the scan line enters an edge,
 *  even is when the scan line exits an edge, and so on. Thus, we draw pixels between the x1 and x2
 *  on the current scan line, and then we increment by 2 because we are using two edges, so we need to go to the next edge
 *  edges come in pair: pre-decessor and sucessor, hence why we are stepping by 2
 *  Fifth step is incrementing the scan line to move up one row in the scan line and process the next y-cordinate
 *  The last step is updting the xOfYmin using the slope  inverse to stimulate the scan line moving up
 *  the inter seciton point xOfYminimum is made to move along the edge using the precomputed slope Inverse value
 *  visualization
 *  ```
 *  Active edges:
 * - Edge A: yMin = 5, yMax = 10, x = 3.0, slopeInv = 0.5
 * - Edge B: yMin = 5, yMax = 9,  x = 7.0, slopeInv = -0.3
 *  // We fill between x = 3.0 and x = 7.0 on y = 5.
 *  // On next scanline (y = 6): Edge A's x becomes 3.5, Edge B's x becomes 6.7, We fill between 3.5 and 6.7
 *  Scanline 2: [========]
 *  Scanline 3:  [======]
 *  Scanline 4:   [====]
 *  Scanline 5:    [==]
 *  ```
 *  for more info check:http://www.cs.sjsu.edu/faculty/pollett/116a.1.04f/Lec04102004.pdf
 *  https://www.khoury.northeastern.edu/home/fell/CS4300/Lectures/CS4300F2012-9-ScanLineFill.pdf
 */
fun scanlineFillAlgorithm(edgeTable: FloatArray, drawPixels: drawPixels){
    val edgeCount = edgeTable.size / SizeOfVariablesPerEdge
    if (edgeCount < 2) throw IllegalStateException("This is not a valid polygon!")

    var scanlineYMinimum = edgeTable[0 + YMinimum].toInt()
    val yMaximum = edgeTable[(edgeCount - 1) * SizeOfVariablesPerEdge + YMaximum].toInt()
    val activeEdges = mutableListOf<FloatArray>()
    var edgeIndex = 0

    while (scanlineYMinimum < yMaximum) {
        // 1. add the new edges starting at this scan line
        while (edgeIndex < edgeCount) {
            val base = edgeIndex * SizeOfVariablesPerEdge
            val yMinimum = edgeTable[base + YMinimum]
            if (yMinimum.toInt() > scanlineYMinimum) break

            val edge = FloatArray(SizeOfVariablesPerEdge)
            for (j in 0 until SizeOfVariablesPerEdge) {
                edge[j] = edgeTable[base + j]
            }
            activeEdges.add(edge)
            edgeIndex++
        }

        // 2. remove the edges where yMaximum == current scanline
        activeEdges.removeAll { edge ->
            edge[YMaximum].toInt() == scanlineYMinimum
        }



        // 3. sort active edges by current x of Y minimum (Stable sort)
        activeEdges.sortWith(compareBy { it[XOfyMinimum] })



        // 4. fill spans between pairs of edges
        var i = 0
        while (i < activeEdges.size - 1) {
            val x1 = activeEdges[i][XOfyMinimum].toInt()
            val x2 = activeEdges[i + 1][XOfyMinimum].toInt()
            for (x in x1 until x2){
                drawPixels(x, scanlineYMinimum)
            }

            i += 2
        }

        // 6. update the x of y minimum using the slope inverse
        for (edge in activeEdges) {
            edge[XOfyMinimum] += edge[SlopeInverse]
        }
        // 5. increment the scan line
        scanlineYMinimum++
    }
}

fun pack(x: Int, y: Int): Long = (x.toLong() shl 32) or (y.toLong() and 0xFFFFFFFFL)
private const val CanvasFillValue =1

private fun renderPixelsOnTerminal(canvas:Array<IntArray>){
    for (row in canvas.reversed()){ // very important
        println(row.joinToString("") { if (it == FillValue) "#" else "." })
    }
}
fun main(){
    val width = 20
    val height =10
    val canvas = Array(height) { IntArray(width) }

    val polygonVertices = longArrayOf(
        pack(10, 2),    // top middle
        pack(15, 5),    // top right
        pack(15, 10),   // bottom right
        pack(5, 10),    // bottom left
        pack(5, 5)      // top left
    )

    val edgeTable = createEdgeTable(polygonVertices)

    scanlineFillAlgorithm(edgeTable, drawPixels = { x,y->
        // on row y which is our scan line, fill a particular color between this x and x
        // we need to check bounds to ensure we don't fill sth outside our buffer height. Scan lines outside the height
        // ought to be ignored
        if (y in canvas.indices && x in canvas[0].indices){
            canvas[y][x] = CanvasFillValue
        }

    })
    renderPixelsOnTerminal(canvas)
}