0
\$\begingroup\$

I am writing a software renderer for the Kotlin port of Dear ImGui. In order to be feature complete, I needed to add barycentric coloring to some triangles for things such as color pickers. I have implemented barycentric rendering as below, but it takes 75-95 percent of the time spent on the CPU to compute it. Are there any better methods I could use?

Some information on the performance numbers (in ns):

Startup 12 Barycentric triangles: 40% time. This appears to be because the rest of the pipeline is warming up.
total time 2673419, bary time 1204929 which is 45.1% bary time. Bary draws 12 Tex Draws 311 Normal Times 443 Normal Draws 365

Long-running 12 Barycentric triangles: 75% time
total time 1384237, bary time 1034258 which is 74.7% bary time. Bary draws 12 Tex Draws 311 Normal Times 443 Normal Draws 365

Long-running 28 Barycentric triangles: 95% time
total time 18795482, bary time 17941069 which is 95.5% bary time. Bary draws 28 Tex Draws 351 Normal Times 673 Normal Draws 575


gc is a GraphicsContext.
vtx1, vtx, vtx3 are the vertices of this triangle.
vt1, vt2, vt3 are the vertices ordered such that vt1.y >= vt2.y >= vt3.y

//set up so that vt1.y >= vt2.y >= vt3.y
val vt3 = if (vtx1.pos.y > vtx2.pos.y) if (vtx1.pos.y > vtx3.pos.y) vtx1 else vtx3 else if (vtx2.pos.y > vtx3.pos.y) vtx2 else vtx3
val vt1 = if (vtx1.pos.y < vtx2.pos.y) if (vtx1.pos.y < vtx3.pos.y) vtx1 else vtx3 else if (vtx2.pos.y < vtx3.pos.y) vtx2 else vtx3

//process of elimination
val vt2 = if (vt1 == vtx1)
    if (vt3 == vtx2)
        vtx3
    else
        vtx2
else
    if (vt1 == vtx2)
        if (vt3 == vtx3)
            vtx1
        else
            vtx3
    else
        if (vt3 == vtx2)
            vtx1
        else
            vtx2

//set up all the constant barycentric coords for this triangle
val v0 = vt2.pos - vt1.pos
val v1 = vt3.pos - vt1.pos

val d00 = dotProd(v0, v0)
val d01 = dotProd(v0, v1)
val d11 = dotProd(v1, v1)

val denom = d00 * d11 - d01 * d01
//end setup

/**
 * Draw the color at point [p] based on the currently set up barycentric triangle
 */
fun baryColor(p: Vec2) {
    //get the rest of barycentric information
    val v2 = p - vt1.pos
    val d20 = dotProd(v2, v0)
    val d21 = dotProd(v2, v1)
    val v = (d11 * d20 - d01 * d21) / denom
    val w = (d00 * d21 - d01 * d20) / denom
    val u = 1.0 - v - w
    //turn the colors into usable colors
    val c1 = vt1.col.toJFXColor()
    val c2 = vt2.col.toJFXColor()
    val c3 = vt3.col.toJFXColor()
    //mix colors based on their involvement, and clamp to [0.0,1.0]
    //u,v,w can be negative
    gc.fill = JFXColor(
            ((c1.red * u) + (c2.red * v) + (c3.red * w)).coerceIn(0.0, 1.0),
            ((c1.green * u) + (c2.green * v) + (c3.green * w)).coerceIn(0.0, 1.0),
            ((c1.blue * u) + (c2.blue * v) + (c3.blue * w)).coerceIn(0.0, 1.0),
            ((c1.opacity * u) + (c2.opacity * v) + (c3.opacity * w)).coerceIn(0.0, 1.0)
    )
    //draw a 1x1 rectangle at `p`
    gc.fillRect(p.x.d, p.y.d, 1.0, 1.0)
}

/**
 * Draws a bottom flat triangle with barycentric color coord mixing
 */
fun fillBottomFlatTriangle(vs1: Vec2, vs2: Vec2, vs3: Vec2) {
    //get the inverse slopes of the lines since we will be multiplying by y and need x offset
    val invslope1p = (vs2.x - vs1.x) / (vs2.y - vs1.y)
    val invslope2p = (vs3.x - vs1.x) / (vs3.y - vs1.y)

    //order them properly so that invslope1 < invslope2
    val (invslope1, invslope2) = if (invslope1p > invslope2p) Pair(invslope2p, invslope1p) else Pair(invslope1p, invslope2p)

    //on the first line start at just a point
    var curx1 = vs1.x
    var curx2 = vs1.x

    //get the min and max values
    val minY = vs1.y
    val maxY = vs3.y

    //we have them ordered by y but nothing by x, so we get the max and min x by comparing all values
    val minX = vs3.x min vs2.x min vs1.x
    val maxX = vs3.x max vs2.x max vs1.y

    //if it's a line, needs to be drawn specially so that only 1 pixel isn't drawn
    if (maxY - minY > 1.0f) {
        //for each y value in the triangle
        for (scanlineY in Math.round(minY).i..Math.round(maxY).i) {
            //for each x value on the line
            for (x in Math.round(curx1).i..Math.round(curx2).i) {
                //draw the color at the given point
                baryColor(Vec2(x, scanlineY))
            }
            curx1 += invslope1
            curx2 += invslope2
            curx1 = curx1.coerceAtLeast(minX) //if the difference in y's is less than 1, this will properly clamp the x
            curx2 = curx2.coerceAtMost(maxX)  //if the difference in y's is less than 1, this will properly clamp the x
        }
    } else {
        //average where the line goes
        val scanlineY = (maxY + minY) / 2.0f
        for (x in Math.round(minX).i..Math.round(maxX).i) {
            //draw the color at each point on the line
            baryColor(Vec2(x, scanlineY))
        }
    }
}

/**
 * Draws a top flat triangle with barycentric color coord mixing
 *
 * For more information on the steps, similar to fillBottomFlatTriangle
 */
fun fillTopFlatTriangle(vs1: Vec2, vs2: Vec2, vs3: Vec2) {
    val invslope1p = (vs3.x - vs1.x) / (vs3.y - vs1.y)
    val invslope2p = (vs3.x - vs2.x) / (vs3.y - vs2.y)

    val (invslope1, invslope2) = if (invslope1p > invslope2p) Pair(invslope1p, invslope2p) else Pair(invslope2p, invslope1p)

    var curx1 = vs3.x
    var curx2 = vs3.x

    val maxY = vs3.y
    val minY = vs1.y

    val minX = vs3.x min vs2.x min vs1.x
    val maxX = vs3.x max vs2.x max vs1.y

    if (maxY - minY > 1.0f) {
        for (scanlineY in Math.round(maxY).i downTo Math.round(minY).i) {
            for (x in Math.round(curx1).i..Math.round(curx2).i) {
                baryColor(Vec2(x, scanlineY))
            }
            curx1 -= invslope1
            curx2 -= invslope2
            curx1 = curx1.coerceAtLeast(minX)
            curx2 = curx2.coerceAtMost(maxX)
        }
    } else {
        val scanlineY = (maxY + minY) / 2.0f
        for (x in Math.round(minX).i..Math.round(maxX).i) {
            baryColor(Vec2(x, scanlineY))
        }
    }
}

//check if this is a top flat, bottom flat, or general triangle
when {
    vt2.pos.y == vt3.pos.y -> {
        fillBottomFlatTriangle(vt1.pos, vt2.pos, vt3.pos)
    }
    vt1.pos.y == vt2.pos.y -> {
        fillTopFlatTriangle(vt1.pos, vt2.pos, vt3.pos)
    }
    else -> {
        /* general case - split the triangle in a topflat and bottom-flat one */
        val v4 = Vec2((vt1.pos.x + (vt2.pos.y - vt1.pos.y) / (vt3.pos.y - vt1.pos.y) * (vt3.pos.x - vt1.pos.x)), vt2.pos.y)
        fillBottomFlatTriangle(vt1.pos, vt2.pos, v4)
        fillTopFlatTriangle(vt2.pos, v4, vt3.pos)
    }
}

On a side note, removing the general case renders does not significantly impact performance.

If you could benefit from any other information, please comment and I'll add it for you. Thank you in advance!

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! That is a lot of per cents: of wall clock time on a multi-core CPU? If there are alternative algorithms to handle barycentric colouring/rendering (I don't know the first thing about it), you may want to tag algorithm. (Just noticed the very same numbers of operations reported for Startup and Long-running: that OK?) \$\endgroup\$ – greybeard Mar 21 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.