summaryrefslogtreecommitdiff
path: root/src/lib/evas/common/evas_draw_main.c
diff options
context:
space:
mode:
authorCarsten Haitzler (Rasterman) <raster@rasterman.com>2016-12-30 18:55:55 +0900
committerCarsten Haitzler (Rasterman) <raster@rasterman.com>2017-01-02 18:53:56 +0900
commitb0530aba4f777352cc3ae9772fb1d22f598679a5 (patch)
tree38537cbffe97e5fd1fc2b94209fcc8c66a0d1167 /src/lib/evas/common/evas_draw_main.c
parent5a9c6d393aeda99d2691953dc978ec8b5f905fa7 (diff)
evas cutouts - quickly avoid huge per issues with large nos of cutouts
i found evas_common_draw_context_apply_cutouts() was procsessing 300+ cutouts and as it's O(n^2)/2 to try and merge adjacent rects for cutouts this really performs like complete junk. we apply cutout rects a LOT. this is not the best solution, but it's quick and much faster than doing the clipouts which drop framerate to like 1-2fps or so in the nasty case i say (tyls -m of photos in a dir with a 2160 high terminal). this figures out the target area to limit the count of rects significantly so O(n^2) is far far better when n is now < 10 most of the time. and for the few operations where it's a high value this now uses qsort to speed up merges etc. etc. @optimize
Diffstat (limited to 'src/lib/evas/common/evas_draw_main.c')
-rw-r--r--src/lib/evas/common/evas_draw_main.c182
1 files changed, 134 insertions, 48 deletions
diff --git a/src/lib/evas/common/evas_draw_main.c b/src/lib/evas/common/evas_draw_main.c
index b87c473..60ab694 100644
--- a/src/lib/evas/common/evas_draw_main.c
+++ b/src/lib/evas/common/evas_draw_main.c
@@ -590,39 +590,66 @@ evas_common_draw_context_cutout_split(Cutout_Rects *res, int idx, Cutout_Rect *s
590#undef R_NEW 590#undef R_NEW
591} 591}
592 592
593EAPI void
594evas_common_draw_context_target_set(RGBA_Draw_Context *dc, int x, int y, int w, int h)
595{
596 dc->cutout_target.x = x;
597 dc->cutout_target.y = y;
598 dc->cutout_target.w = w;
599 dc->cutout_target.h = h;
600}
601
602static int
603_srt_y(const void *d1, const void *d2)
604{
605 const Cutout_Rect *r1 = d1, *r2 = d2;
606 if (r1->y == r2->y) return r1->x - r2->x;
607 return r1->y - r2->y;
608}
609
610static int
611_srt_x(const void *d1, const void *d2)
612{
613 const Cutout_Rect *r1 = d1, *r2 = d2;
614 if (r1->x == r2->x) return r1->y - r2->y;
615 return r1->x - r2->x;
616}
617
593EAPI Cutout_Rects * 618EAPI Cutout_Rects *
594evas_common_draw_context_apply_cutouts(RGBA_Draw_Context *dc, Cutout_Rects *reuse) 619evas_common_draw_context_apply_cutouts(RGBA_Draw_Context *dc, Cutout_Rects *reuse)
595{ 620{
596 Cutout_Rects *res = NULL; 621 Cutout_Rects *res = NULL;
597 int i; 622 int i, j, active, found = 0;
598 int j;
599 623
600 if (!dc->clip.use) return NULL; 624 if (!dc->clip.use) return NULL;
601 if ((dc->clip.w <= 0) || (dc->clip.h <= 0)) return NULL; 625 if ((dc->clip.w <= 0) || (dc->clip.h <= 0)) return NULL;
602 626
603 627 if (!reuse) res = evas_common_draw_context_cutouts_new();
604 if (!reuse)
605 {
606 res = evas_common_draw_context_cutouts_new();
607 }
608 else 628 else
609 { 629 {
610 evas_common_draw_context_cutouts_free(reuse); 630 evas_common_draw_context_cutouts_free(reuse);
611 res = reuse; 631 res = reuse;
612 } 632 }
633 // this avoids a nasty case of O(n^2)/2 below with lots of rectangles
634 // to merge so only do this merging if the number of rects is small enough
635 // not to blow out into insanity
613 evas_common_draw_context_cutouts_add(res, dc->clip.x, dc->clip.y, dc->clip.w, dc->clip.h); 636 evas_common_draw_context_cutouts_add(res, dc->clip.x, dc->clip.y, dc->clip.w, dc->clip.h);
614 637 for (i = 0; i < dc->cutout.active; i++)
615 for (i = 0; i < dc->cutout.active; ++i)
616 { 638 {
617 /* Don't loop on the element just added to the list as they are already correctly clipped. */ 639 if ((dc->cutout_target.w != 0) &&
618 int active = res->active; 640 (!RECTS_INTERSECT(dc->cutout.rects[i].x, dc->cutout.rects[i].y,
619 641 dc->cutout.rects[i].w, dc->cutout.rects[i].h,
642 dc->cutout_target.x, dc->cutout_target.y,
643 dc->cutout_target.w, dc->cutout_target.h)))
644 continue;
645 // Don't loop on the element just added to the list as they are
646 // already correctly clipped.
647 active = res->active;
620 for (j = 0; j < active; ) 648 for (j = 0; j < active; )
621 { 649 {
622 if (evas_common_draw_context_cutout_split(res, j, dc->cutout.rects + i)) 650 if (evas_common_draw_context_cutout_split
623 ++j; 651 (res, j, dc->cutout.rects + i)) j++;
624 else 652 else active--;
625 active--;
626 } 653 }
627 } 654 }
628 /* merge rects */ 655 /* merge rects */
@@ -630,66 +657,125 @@ evas_common_draw_context_apply_cutouts(RGBA_Draw_Context *dc, Cutout_Rects *reus
630#define RJ res->rects[j] 657#define RJ res->rects[j]
631 if (res->active > 1) 658 if (res->active > 1)
632 { 659 {
633 int found = 1; 660 if (res->active > 5)
634
635 while (found)
636 { 661 {
637 found = 0; 662 // fast path for larger numbers of rects to merge by using
663 // qsort to sort by y and x to limit the number of rects
664 // we have to walk as rects that have a different y cannot
665 // be merged anyway (or x).
666 qsort(res->rects, res->active, sizeof(res->rects[0]), _srt_y);
638 for (i = 0; i < res->active; i++) 667 for (i = 0; i < res->active; i++)
639 { 668 {
669 if (RI.w == 0) continue; // skip empty rect
640 for (j = i + 1; j < res->active; j++) 670 for (j = i + 1; j < res->active; j++)
641 { 671 {
642 /* skip empty rects we are removing */ 672 if (RJ.y != RI.y) break; // new line, sorted thus skip
643 if (RJ.w == 0) continue; 673 if (RJ.w == 0) continue; // skip empty rect
644 /* check if its same width, immediately above or below */ 674 // if J is the same height (could be merged)
645 if ((RJ.w == RI.w) && (RJ.x == RI.x)) 675 if (RJ.h == RI.h)
646 { 676 {
647 if ((RJ.y + RJ.h) == RI.y) /* above */ 677 // if J is immediately to the right of I
678 if (RJ.x == (RI.x + RI.w))
648 { 679 {
649 RI.y = RJ.y; 680 RI.w = (RJ.x + RJ.w) - RI.x; // expand RI
650 RI.h += RJ.h; 681 RJ.w = 0; // invalidate
651 RJ.w = 0; 682 found++;
652 found = 1;
653 } 683 }
654 else if ((RI.y + RI.h) == RJ.y) /* below */ 684 // since we sort y and THEN x, if height matches
685 // but it's not immediately adjacent, no more
686 // rects exists that can be merged
687 else break;
688 }
689 }
690 }
691 qsort(res->rects, res->active, sizeof(res->rects[0]), _srt_x);
692 for (i = 0; i < res->active; i++)
693 {
694 if (RI.w == 0) continue; // skip empty rect
695 for (j = i + 1; j < res->active; j++)
696 {
697 if (RJ.x != RI.x) break; // new line, sorted thus skip
698 if (RJ.w == 0) continue; // skip empty rect
699 // if J is the same height (could be merged)
700 if (RJ.w == RI.w)
701 {
702 // if J is immediately to the right of I
703 if (RJ.y == (RI.y + RI.h))
655 { 704 {
656 RI.h += RJ.h; 705 RI.h = (RJ.y + RJ.h) - RI.y; // expand RI
657 RJ.w = 0; 706 RJ.w = 0; // invalidate
658 found = 1; 707 found++;
659 } 708 }
709 // since we sort y and THEN x, if height matches
710 // but it's not immediately adjacent, no more
711 // rects exists that can be merged
712 else break;
660 } 713 }
661 /* check if its same height, immediately left or right */ 714 }
662 else if ((RJ.h == RI.h) && (RJ.y == RI.y)) 715 }
716 }
717 else
718 {
719 // for a small number of rects, keep things simple as the count
720 // is small and big-o complexity isnt a problem yet
721 found = 1;
722 while (found)
723 {
724 found = 0;
725 for (i = 0; i < res->active; i++)
726 {
727 for (j = i + 1; j < res->active; j++)
663 { 728 {
664 if ((RJ.x + RJ.w) == RI.x) /* left */ 729 // skip empty rects we are removing
730 if (RJ.w == 0) continue;
731 // check if its same width, immediately above or below
732 if ((RJ.w == RI.w) && (RJ.x == RI.x))
665 { 733 {
666 RI.x = RJ.x; 734 if ((RJ.y + RJ.h) == RI.y) // above
667 RI.w += RJ.w; 735 {
668 RJ.w = 0; 736 RI.y = RJ.y;
669 found = 1; 737 RI.h += RJ.h;
738 RJ.w = 0;
739 found++;
740 }
741 else if ((RI.y + RI.h) == RJ.y) // below
742 {
743 RI.h += RJ.h;
744 RJ.w = 0;
745 found++;
746 }
670 } 747 }
671 else if ((RI.x + RI.w) == RJ.x) /* right */ 748 // check if its same height, immediately left or right
749 else if ((RJ.h == RI.h) && (RJ.y == RI.y))
672 { 750 {
673 RI.w += RJ.w; 751 if ((RJ.x + RJ.w) == RI.x) // left
674 RJ.w = 0; 752 {
675 found = 1; 753 RI.x = RJ.x;
754 RI.w += RJ.w;
755 RJ.w = 0;
756 found++;
757 }
758 else if ((RI.x + RI.w) == RJ.x) // right
759 {
760 RI.w += RJ.w;
761 RJ.w = 0;
762 found++;
763 }
676 } 764 }
677 } 765 }
678 } 766 }
679 } 767 }
680 } 768 }
681 769
682 /* Repack the cutout */ 770 // Repack the cutout
683 j = 0; 771 j = 0;
684 for (i = 0; i < res->active; i++) 772 for (i = 0; i < res->active; i++)
685 { 773 {
686 if (RI.w == 0) continue; 774 if (RI.w == 0) continue;
687 if (i != j) 775 if (i != j) RJ = RI;
688 RJ = RI;
689 j++; 776 j++;
690 } 777 }
691 res->active = j; 778 res->active = j;
692 return res;
693 } 779 }
694 return res; 780 return res;
695} 781}