Android中点椭圆算法在大尺寸Bitmap上绘制椭圆边缘裁切问题

我正在开发一款面向Android平台的像素画编辑器，近期基于中点椭圆算法实现了椭圆绘制工具。
需要特别强调的是，该工具在常规场景下的运行效果完全正常！
唯一的问题是：当我在尺寸约为1000x1000及以上的大尺寸Bitmap上绘制大规格椭圆时，椭圆的边缘会被裁切，同时出现异常绘制行为：

中点椭圆算法实现代码 #

package com.therealbluepandabear.pixapencil.algorithms

import com.therealbluepandabear.pixapencil.activities.canvas.canvascommands.overrideSetPixel
import com.therealbluepandabear.pixapencil.models.Coordinates

class MidpointEllipseAlgorithm(private val algorithmInfo: AlgorithmInfoParameter, private val xDEC: Boolean = false, private val yDEC: Boolean = false, private val filledMode: Boolean = false) {
    private val shouldLineIgnoreBrush = true

    private fun putPixel(p1: Coordinates, p2: Coordinates) {
        val xc = p1.x
        val yc = p1.y

        val x = p2.x
        val y = p2.y

        if (!xDEC && !yDEC) {
            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc + x, yc + y),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc + x, yc - y),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc - x, yc - y),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc - x, yc + y),
                algorithmInfo.color
            )

            if (filledMode) {
                val lineAlgorithmInstance = LineAlgorithm(algorithmInfo, shouldLineIgnoreBrush)

                lineAlgorithmInstance.compute(
                    Coordinates(xc + x, yc + y),
                    Coordinates(xc + x, yc - y),
                )

                lineAlgorithmInstance.compute(
                    Coordinates(xc - x, yc - y),
                    Coordinates(xc - x, yc + y),
                )
            }
        } else if (xDEC && !yDEC) {
            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates((xc + x) + 1, yc + y),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates((xc + x) + 1, yc - y),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc - x, yc - y),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc - x, yc + y),
                algorithmInfo.color
            )

            if (filledMode) {
                val lineAlgorithmInstance = LineAlgorithm(algorithmInfo, shouldLineIgnoreBrush)

                lineAlgorithmInstance.compute(
                    Coordinates((xc + x) + 1, yc + y),
                    Coordinates((xc + x) + 1, yc - y),
                )

                lineAlgorithmInstance.compute(
                    Coordinates(xc - x, yc - y),
                    Coordinates(xc - x, yc + y),
                )
            }
        } else if (!xDEC && yDEC) {
            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc + x, (yc + y) + 1),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc + x, yc - y),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc - x, yc - y),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc - x, (yc + y) + 1),
                algorithmInfo.color
            )

            if (filledMode) {
                val lineAlgorithmInstance = LineAlgorithm(algorithmInfo, shouldLineIgnoreBrush)

                lineAlgorithmInstance.compute(
                    Coordinates(xc + x, (yc + y) + 1),
                    Coordinates(xc + x, yc - y),
                )

                lineAlgorithmInstance.compute(
                    Coordinates(xc - x, yc - y),
                    Coordinates(xc - x, (yc + y) + 1),
                )
            }
        } else {
            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates((xc + x) + 1, (yc + y) + 1),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates((xc + x) + 1, yc - y),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc - x, yc - y),
                algorithmInfo.color
            )

            algorithmInfo.canvasCommandsHelperInstance.overrideSetPixel(
                Coordinates(xc - x, (yc + y) + 1),
                algorithmInfo.color
            )

            if (filledMode) {
                val lineAlgorithmInstance = LineAlgorithm(algorithmInfo, shouldLineIgnoreBrush)

                lineAlgorithmInstance.compute(
                    Coordinates((xc + x) + 1, (yc + y) + 1),
                    Coordinates((xc + x) + 1, yc - y),
                )

                lineAlgorithmInstance.compute(
                    Coordinates(xc - x, yc - y),
                    Coordinates(xc - x, (yc + y) + 1),
                )
            }
        }
    }

    fun compute(p1: Coordinates, rx: Int, ry: Int) {
        val idp = Coordinates(0, ry)

        var xkp1 = idp.x
        var ykp1 = idp.y

        var lxkp1: Int
        var lykp1: Int

        var p1k = (ry * ry) + ((rx * rx) / 4) - (ry * (rx * rx))

        val incy = p1.y
        val incx = p1.x

        putPixel(Coordinates(incx, incy), Coordinates(xkp1, ykp1))

        while (
            (2 * (xkp1 + 1) * (ry * ry))
            <
            (2 * ykp1 * (rx * rx))
        ) {
            p1k += if (p1k >= 0) {
                xkp1++
                ykp1--

                lxkp1 = xkp1 - 1
                lykp1 = ykp1 + 1

                (ry * ry) + (2 * (lxkp1 + 1)) * (ry * ry) + (rx * rx) * ((ykp1 * ykp1) - (lykp1 * lykp1)) - (rx * rx) * (ykp1 - lykp1)
            } else {
                xkp1++

                lxkp1 = xkp1 - 1
                lykp1 = ykp1

                (ry * ry) + (2 * (lxkp1 + 1)) * (ry * ry) + (rx * rx) * ((ykp1 * ykp1) - (lykp1 * lykp1))
            }

            putPixel(Coordinates(incx, incy), Coordinates(xkp1, ykp1))
        }

        var p2k = (ry * ry) * ((xkp1 + 0.5) * (xkp1 + 0.5)) + (rx * rx) * ((ykp1 - 1) * (ykp1 - 1)) - ((rx * rx) * (ry * ry))

        while (
            ykp1 > 0
        ) {
            if (p2k >= 0) {
                ykp1--
                lykp1 = ykp1 + 1
                lxkp1 = xkp1

                p2k += (rx * rx) - 2 * (rx * rx) * (lykp1 - 1) + (ry * ry) * ((xkp1 * xkp1) - (lxkp1 * lxkp1))
            } else {
                xkp1++
                lxkp1 = xkp1 - 1
                ykp1--
                lykp1 = ykp1 + 1

                p2k += (rx * rx) - 2 * (rx * rx) * (lykp1 - 1) + (ry * ry) * ((xkp1 * xkp1) - (lxkp1 * lxkp1)) + (ry * ry) * (xkp1 - lxkp1)
            }

            putPixel(Coordinates(incx, incy), Coordinates(xkp1, ykp1))
        }
    }
}

已排查确认信息 #

• 异常仅存在于MidpointEllipseAlgorithm实现中：overrideSetPixel函数并非问题诱因，即便替换为原生Bitmap.setPixel方法，异常仍然存在。
• 小尺寸画布上绘制椭圆无任何问题，仅在1000x1000及以上大尺寸Bitmap上绘制大规格椭圆时才会触发异常。
• 已尝试调整变量取值、循环判断条件，参考公开同算法实现替换原有代码，问题仍未解决。

问题根因 #

异常由32位Int整数溢出导致：
Kotlin/JVM中基础Int类型为32位有符号整数，最大可存储值为2^31 - 1 = 2147483647。算法中存在大量半径平方、多参数连续乘法计算：

• 椭圆半径小于463时，所有中间计算结果均在Int取值范围内，逻辑判断正常，绘制结果正确
• 半径达到500以上时，类似2 * ykp1 * (rx * rx)的连续乘法结果会超过Int最大值，溢出后变为无意义的负数，直接导致循环终止条件判断失效、决策参数p1k/p2k计算错误，最终出现坐标偏移、边缘裁切的异常绘制行为。
  小尺寸画布上椭圆半径不可能达到溢出阈值，因此无法复现问题。

修复方案 #

将算法中所有参与乘法计算的变量、中间计算值统一转为Long类型存储即可解决：

• 决策参数p1k、p2k声明为Long类型
• 半径平方等中间值计算时，第一步就转为Long运算，例如写为rx.toLong() * rx，不要写(rx * rx).toLong()（后者会先完成Int乘法溢出后再转类型，没有修复效果）
• 循环判断条件两侧的计算也统一使用Long值运算，避免比较逻辑出错。

内容的提问来源于stack exchange，提问作者thebluepandabear