I’ve gotten stuck on the optimization of a project and hope to receive some pointers for where to look to learn about a solution. The project is a brush engine plugin. I have the functionality figured out, but adding anti-aliasing makes the brush noticeably laggy. Now I’m trying to figure where I should optimize it.
The brush engine is meant to emulate a broad edge calligraphy pen. I found the existing brush engines insufficient to create the angled brush strokes with very sharp corners. As an example, the letters BE drawn with it:
Without anti-aliasing and fully opaque, the code is simple:
void KisBroadEdgeOp::paintLine(const KisPaintInformation &pi1, const KisPaintInformation &pi2, KisDistanceInformation *currentDistance)
{
Q_UNUSED(currentDistance);
if (!painter()) return;
if (!m_segmentBufferDevice)
m_segmentBufferDevice = source()->createCompositionSourceDevice();
else
m_segmentBufferDevice->clear();
if (!m_painter) {
m_painter = new KisPainter(m_segmentBufferDevice);
m_painter->setPaintColor(painter()->paintColor());
}
KisPaintDeviceSP bufferDevice = m_painter->device();
if (!bufferDevice) return;
const qreal radius1 = 0.5 * additionalScale * m_sizeOption.apply(pi1) * m_broadEdgeOpOption.diameter;
const qreal radius2 = 0.5 * additionalScale * m_sizeOption.apply(pi2) * m_broadEdgeOpOption.diameter;
const qreal angle1 = m_broadEdgeOpOption.angle + m_rotationOption.apply(pi1);
const qreal angle2 = m_broadEdgeOpOption.angle + m_rotationOption.apply(pi2);
const QPointF penWidth1 = QPointF(cos(angle1), -sin(angle1)) * radius1;
const QPointF penWidth2 = QPointF(cos(angle2), -sin(angle2)) * radius2;
const QPointF pos1 = pi1.pos();
const QPointF pos2 = pi2.pos();
QPainterPath path;
path.moveTo(pos1 + penWidth1);
path.lineTo(pos2 + penWidth2);
path.lineTo(pos2 - penWidth2);
path.lineTo(pos1 - penWidth1);
path.setFillRule(Qt::WindingFill);
const QRect alignedRect= kisGrowRect(path.boundingRect(), 1).toAlignedRect();
m_painter->setAntiAliasPolygonFill(false);
m_painter->setFillStyle(KisPainter::FillStyleForegroundColor);
m_painter->fillPainterPath(path, alignedRect);
painter()->bitBlt(alignedRect.topLeft(), m_segmentBufferDevice, alignedRect);
painter()->renderMirrorMask(alignedRect, m_segmentBufferDevice);
}
To handle dynamic opacity, I unfortunately can’t use fillPainterPath and instead loop over the alignedRect with a KisSequentialIterator. On a 45° brush angle, this square contains a majority of pixels outisde of the painted quad. I could skip with some simple math to calculate the per line offset of the painted pixels, but I worry that such memory windows shifting at an inconsistent rate would mess with CPU caching and create a memory accessing bottleneck.
The algorithm for testing if a pixel is inside of the quad on the other hand should be more efficient than the generic polygon path test. The trick is to treat this as an interpolation of two lines by t, with two distinct approaches depending on if the lines are parallel or not:
qreal intersectionScalar(QPointF p0, QPointF v0, QPointF p1, QPointF v1) {
//p0.x + t0 * v0.x = p1.x + t1 * v1.x
//p0.y + t0 * v0.y = p1.y + t1 * v1.y
//t0 * (v0.x * v1.y - v1.x * v0.y) = p1.x * v1.y - p0.x * v1.y - p1.y * v1.x + p0.y * v1.x
// If v0 and v1 are parallel or either is 0, then this divides by 0 and returns positive or negative infinity.
qreal t = (p1.x() * v1.y() - p0.x() * v1.y() - p1.y() * v1.x() + p0.y() * v1.x())
/ (v0.x() * v1.y() - v1.x() * v0.y());
return t;
}
bool parallelAngles;
QPointF helperPoint;
if (penWidth1.x() * penWidth2.y() - penWidth2.x() * penWidth1.y()) {
// The brush angles are parallel.
parallelAngles = true;
helperPoint = penWidth1;
} else {
// The brush angles intersect.
parallelAngles = false;
qreal scalar = intersectionScalar(pos1, penWidth1, pos2, penWidth2);
helperPoint = pos1 + scalar * penWidth1;
}
KoColor currentColor(painter()->paintColor());
KisSequentialIterator it(bufferDevice, alignedRect);
while (it.nextPixel()) {
const QPointF pixelPoint = QPointF(it.x(), it.y());
qreal t;
if (parallelAngles)
t = intersectionScalar(pos1, pos2 - pos1, pixelPoint, helperPoint);
else
t = intersectionScalar(pos1, pos2 - pos1, pixelPoint, pixelPoint - helperPoint);
const QPointF localCenter = pos1 + t * (pos2 - pos1);
const QPointF localWidth = penWidth1 + t * (penWidth2 - penWidth1);
const qreal distance = (abs(pixelPoint.x() - localCenter.x()) + abs(pixelPoint.y() - localCenter.y()))
/ (abs(localWidth .x()) + abs(localWidth .y()));
const QPointF localOpacity = penOpacity1 + t * (penOpacity2 - penOpacity1);
if (t > 0 && t <= 1 && distance <= 1) {
currentColor.setOpacity(localOpacity);
memcpy(it.rawData(), currentColor.data(), pixelSize);
}
}
For anti-aliasing, nothing feels as straight forward.
Anti-aliasing the first quad like this is straight forward. Each pixel receives an alpha value matching the percentage of it’s surface, which is inside of the quad. The blue pixels are neither entirely covered or uncovered. The problem arises with subsequent quads. There are three scenarios that need to be handled.
- A straight line split into multiple
paintLinecalls. Each quad shares one edge with the previous quad, but no quad areas overlap. The anti-aliasing of both quads should cancel each other out along that edge. With conventional blending, that’snewAlpha = 1 - lastAlphawhich meansblendedAlpha = newAlpha + (1 - newAlpha) * (1 - newAlpha). It should be 1 instead. - After one quad, the paint stroke reverses in direction. The quads fully overlap and should be blended in the conventional way.
- The pen position changes only slightly for the second quad, but the pen angle changes significantly. This causes the pen edges of the two positions to intersect within their widths. One one side of the intersection, blending should be done conventionally, while on the other the anti-aliasing should cancel each other out.
One idea I had was to redraw the entire brush stroke with every paintLine. The Shape brush engine seems to work similarly, but I assume redrawing the whole buffer is unnecessary here. Only pixels that are at least partially covered by the quad need to be changed. And of those, any pixels fully covered can be blended with the conventional method. Pixels containing an edge however, would need to be rendered from scratch by using supersampling anti-aliasing to count the number of quad intersections for each subpixel.
The next idea was to hold pixels intersected by the leading edge in limbo. For each of those pixels I iterate an individual counter. Then for all other pixels I check if that counter is greater than 0. The counter determines how many quads in the stored quad history need to be processed together with the current one, to determine the coverage of the current pixel. Once processed, the counter is reset to 0. This makes brush strokes parallel to the pen angle especially laggy.
At this point it started to feel like I’m just adding more and more complexity to the algorithm, to handle all those edge cases. Surely someone else must have already gone through all of this and I’m just reinventing the wheel over here. Though, there are still some avenues I consider pursuing.
Instead of checking every pixel for a non zero counter, I can check only pixels intersected by the trailing edge. That alone would have no benefit, but it would allow for swapping between two buffers that scale proportional to pen width, instead of canvas size.
The other idea is to remove the need for a quad history by considering their directionality. When subsequent quads are on opposite sides of an edge, their coverage can be added together. When they’re on the same side of an edge, the the previous sum can be blended with the output and a new sum can be started. But there’s the unfortunate third case, where two edges intersect within one pixel. I’m not sure how to handle the case, where the quads are both, on the same side and opposite sides.
But at some point, all the flow control will create more overhead than it optimizes the code and I’m not sure how to tell when that happens. Either way, if anyone did read through all of this, I want to thank you for having interest in my problem. Nobody has an obligation to read all this and I truly appreciate that Krita has a community of people willing to help out others!