From de2b90e18e8fb5aecc67af2e8be7326151c27298 Mon Sep 17 00:00:00 2001 From: Hermet Park Date: Fri, 14 Apr 2023 13:32:20 +0900 Subject: [PATCH] sw_engine rle: fix RLE intersect. IntersectSpansRegion() wasn't working correctly, as it didn't take care of some corner cases. This fix makes the algorithm more accurate. Change-Id: I7405676290951f6f7ee7ac29f6cbc19473cda84d --- src/lib/sw_engine/tvgSwRle.cpp | 173 ++++++++++++++++++++++++++++++++--------- 1 file changed, 135 insertions(+), 38 deletions(-) diff --git a/src/lib/sw_engine/tvgSwRle.cpp b/src/lib/sw_engine/tvgSwRle.cpp index 6651e4e..d95d009 100644 --- a/src/lib/sw_engine/tvgSwRle.cpp +++ b/src/lib/sw_engine/tvgSwRle.cpp @@ -773,60 +773,58 @@ static int _genRle(RleWorker& rw) } -SwSpan* _intersectSpansRegion(const SwRleData *clip, const SwRleData *targetRle, SwSpan *outSpans, uint32_t spanCnt) +static SwSpan* _intersectSpansRegion(const SwRleData *clip, const SwRleData *target, SwSpan *outSpans) { auto out = outSpans; - auto spans = targetRle->spans; - auto end = targetRle->spans + targetRle->size; + auto spans = target->spans; + auto end = target->spans + target->size; auto clipSpans = clip->spans; auto clipEnd = clip->spans + clip->size; - while (spanCnt > 0 && spans < end) { - if (clipSpans == clipEnd) { - spans = end; - break; - } + while (spans < end && clipSpans < clipEnd) { + //align y cooridnates. if (clipSpans->y > spans->y) { ++spans; continue; } - if (spans->y != clipSpans->y) { + if (spans->y > clipSpans->y) { ++clipSpans; continue; } - auto sx1 = spans->x; - auto sx2 = sx1 + spans->len; - auto cx1 = clipSpans->x; - auto cx2 = cx1 + clipSpans->len; - if (cx1 < sx1 && cx2 < sx1) { - ++clipSpans; - continue; - } - else if (sx1 < cx1 && sx2 < cx1) { - ++spans; - continue; - } - auto x = sx1 > cx1 ? sx1 : cx1; - auto len = (sx2 < cx2 ? sx2 : cx2) - x; - if (len) { - auto spansCorverage = spans->coverage; - auto clipSpansCoverage = clipSpans->coverage; - out->x = sx1 > cx1 ? sx1 : cx1; - out->len = (sx2 < cx2 ? sx2 : cx2) - out->x; - out->y = spans->y; - out->coverage = (uint8_t)(((spansCorverage * clipSpansCoverage) + 0xff) >> 8); - ++out; - --spanCnt; + //Try clipping with all clip spans which have a same y coordinate. + auto temp = clipSpans; + while(temp->y == clipSpans->y) { + auto sx1 = spans->x; + auto sx2 = sx1 + spans->len; + auto cx1 = temp->x; + auto cx2 = cx1 + temp->len; + + //The span must be left(x1) to right(x2) direction. Not intersected. + if (cx2 < sx1 || sx2 < cx1) { + ++temp; + continue; + } + + //clip span region. + auto x = sx1 > cx1 ? sx1 : cx1; + auto len = (sx2 < cx2 ? sx2 : cx2) - x; + if (len > 0) { + out->x = x; + out->y = temp->y; + out->len = len; + out->coverage = (uint8_t)(((spans->coverage * temp->coverage) + 0xff) >> 8); + ++out; + } + ++temp; } - if (sx2 < cx2) ++spans; - else ++clipSpans; + ++spans; } return out; } -SwSpan* _intersectSpansRect(const SwBBox *bbox, const SwRleData *targetRle, SwSpan *outSpans, uint32_t spanCnt) +static SwSpan* _intersectSpansRect(const SwBBox *bbox, const SwRleData *targetRle, SwSpan *outSpans, uint32_t spanCnt) { auto out = outSpans; auto spans = targetRle->spans; @@ -865,6 +863,46 @@ SwSpan* _intersectSpansRect(const SwBBox *bbox, const SwRleData *targetRle, SwSp } +static SwSpan* _mergeSpansRegion(const SwRleData *clip1, const SwRleData *clip2, SwSpan *outSpans) +{ + auto out = outSpans; + auto spans1 = clip1->spans; + auto end1 = clip1->spans + clip1->size; + auto spans2 = clip2->spans; + auto end2 = clip2->spans + clip2->size; + + //list two spans up in y order + //TODO: Remove duplicated regions? + while (spans1 < end1 && spans2 < end2) { + while (spans1 < end1 && spans1->y <= spans2->y) { + *out = *spans1; + ++spans1; + ++out; + } + if (spans1 >= end1) break; + while (spans2 < end2 && spans2->y <= spans1->y) { + *out = *spans2; + ++spans2; + ++out; + } + } + + //Leftovers + while (spans1 < end1) { + *out = *spans1; + ++spans1; + ++out; + } + while (spans2 < end2) { + *out = *spans2; + ++spans2; + ++out; + } + + return out; +} + + void _replaceClipSpan(SwRleData *rle, SwSpan* clippedSpans, uint32_t size) { free(rle->spans); @@ -1001,6 +1039,28 @@ error: } +SwRleData* rleRender(const SwBBox* bbox) +{ + auto width = static_cast(bbox->max.x - bbox->min.x); + auto height = static_cast(bbox->max.y - bbox->min.y); + + auto rle = static_cast(malloc(sizeof(SwRleData))); + rle->spans = static_cast(malloc(sizeof(SwSpan) * height)); + rle->size = height; + rle->alloc = height; + + auto span = rle->spans; + for (uint16_t i = 0; i < height; ++i, ++span) { + span->x = bbox->min.x; + span->y = bbox->min.y + i; + span->len = width; + span->coverage = 255; + } + + return rle; +} + + void rleReset(SwRleData* rle) { if (!rle) return; @@ -1016,13 +1076,51 @@ void rleFree(SwRleData* rle) } +void rleMerge(SwRleData* rle, SwRleData* clip1, SwRleData* clip2) +{ + if (!rle || (!clip1 && !clip2)) return; + if (clip1 && clip1->size == 0 && clip2 && clip2->size == 0) return; + + TVGLOG("SW_ENGINE", "Unifying Rle!"); + + //clip1 is empty, just copy clip2 + if (!clip1 || clip1->size == 0) { + if (clip2) { + auto spans = static_cast(malloc(sizeof(SwSpan) * (clip2->size))); + memcpy(spans, clip2->spans, clip2->size); + _replaceClipSpan(rle, spans, clip2->size); + } else { + _replaceClipSpan(rle, nullptr, 0); + } + return; + } + + //clip2 is empty, just copy clip1 + if (!clip2 || clip2->size == 0) { + if (clip1) { + auto spans = static_cast(malloc(sizeof(SwSpan) * (clip1->size))); + memcpy(spans, clip1->spans, clip1->size); + _replaceClipSpan(rle, spans, clip1->size); + } else { + _replaceClipSpan(rle, nullptr, 0); + } + return; + } + + auto spanCnt = clip1->size + clip2->size; + auto spans = static_cast(malloc(sizeof(SwSpan) * spanCnt)); + auto spansEnd = _mergeSpansRegion(clip1, clip2, spans); + + _replaceClipSpan(rle, spans, spansEnd - spans); +} + + void rleClipPath(SwRleData *rle, const SwRleData *clip) { if (rle->size == 0 || clip->size == 0) return; auto spanCnt = rle->size > clip->size ? rle->size : clip->size; auto spans = static_cast(malloc(sizeof(SwSpan) * (spanCnt))); - if (!spans) return; - auto spansEnd = _intersectSpansRegion(clip, rle, spans, spanCnt); + auto spansEnd = _intersectSpansRegion(clip, rle, spans); _replaceClipSpan(rle, spans, spansEnd - spans); @@ -1034,7 +1132,6 @@ void rleClipRect(SwRleData *rle, const SwBBox* clip) { if (rle->size == 0) return; auto spans = static_cast(malloc(sizeof(SwSpan) * (rle->size))); - if (!spans) return; auto spansEnd = _intersectSpansRect(clip, rle, spans, rle->size); _replaceClipSpan(rle, spans, spansEnd - spans); -- 2.7.4