Another optimization for shadow calculation in xcompmgr.c
Michael Knorr <[email protected]>
| Newsgroups | gmane.comp.freedesktop.xserver |
|---|---|
| Message-ID | <[email protected]> |
Hello, I added a function that does some precalculations for the sums that are calculated several thousand times for big windows at every resize. There's no loop needed anymore. This should speed thing up quite a bit. Besides that I removed the unnecessary second "center" section in make_shadow that was left in there during the last code update. Greetings Michael Knorr
xcomp.diff
(text/plain, 6.3 KB)
--- ../xcompmgr/xcompmgr.c 2003-12-02 10:51:12.000000000 +0100
+++ ./xcompmgr.c 2003-12-03 01:05:49.000000000 +0100
@@ -67,6 +67,7 @@
typedef struct _conv {
int size;
double *data;
+ double *precalc_sums;
} conv;
win *list;
@@ -114,6 +115,70 @@
}
+/* precalculate some gaussian sums
+ gdata:
+ x0y0 x1y0 x2y0 ...
+ x0y1 x1y1 x2y1 ...
+ x0y2 x1y2 x2y2 ...
+ ...
+
+ gsums:
+ a1=x0y0 a2=x1y0+a1 a3=x2y0+a2 ...
+ a4=x0y1+a1 a5=x1y1+a2+a4-a1 a6=x2y1+a3+a5-a2 ...
+ a7=x0y2+a4 a8=x1y2+a5+a7-a4 a9=x2y2+a6+a8-a5 ...
+ ...
+ */
+static double *
+make_gaussian_sums(conv *map)
+{
+ int gsize = map->size;
+ double * gdata = map->data;
+ double * gsums = map->precalc_sums;
+ int x, y;
+ double v;
+ for (y = 0; y < gsize; y++)
+ {
+ for (x = 0; x < gsize; x++)
+ {
+ if (x > 0 && y > 0)
+ {
+ v = gdata[y * gsize + x]
+ + gsums[(y - 1) * gsize + x]
+ + gsums[y * gsize + x - 1]
+ - gsums[(y - 1) * gsize + x - 1];
+ }
+ else if (y > 0) /* we are on the top of the grid ( x == 0 ) */
+ {
+ v = gdata[y * gsize]
+ + gsums[(y - 1) * gsize];
+ }
+ else if (x > 0) /* we are on the left of the grid ( y == 0 ) */
+ {
+ v = gdata[x]
+ + gsums[x - 1];
+ }
+ else /* top left position ( x == 0 && y == 0 ) */
+ {
+ v = gdata[0];
+ }
+
+ if (v > 1.0)
+ {
+ v = 1.0;
+ }
+ else if (v < 0.0)
+ {
+ v = 0.0;
+ }
+
+ gsums[y * gsize + x] = v;
+
+ // printf("x: %d, y: %d, v: %f\n", x, y, v);
+ }
+ }
+}
+
+
static conv *
make_gaussian_map (Display *dpy, double r)
{
@@ -123,10 +188,12 @@
int x, y;
double t;
double g;
+ int data_size = size * size;
- c = malloc (sizeof (conv) + size * size * sizeof (double));
+ c = malloc (sizeof(conv) + sizeof(double) * data_size * 2);
c->size = size;
c->data = (double *) (c + 1);
+ c->precalc_sums = c->data + data_size;
for (y = 0; y < size; y++)
for (x = 0; x < size; x++)
{
@@ -140,6 +207,9 @@
{
c->data[y*size + x] /= t;
}
+
+ make_gaussian_sums(c);
+
return c;
}
@@ -164,6 +234,101 @@
sum_gaussian (conv *map, double opacity, int x, int y, int width, int height)
{
int fx, fy;
+ double *gsums = map->precalc_sums;
+ int gsize = map->size;
+ int center = gsize / 2;
+ int fx_start, fx_end;
+ int fy_start, fy_end;
+ double v;
+
+ /*
+ * Compute set of filter values which are "in range",
+ * that's the set with:
+ * 0 <= x + (fx-center) && x + (fx-center) < width &&
+ * 0 <= y + (fy-center) && y + (fy-center) < height
+ *
+ * 0 <= x + (fx - center) x + fx - center < width
+ * center - x <= fx fx < width + center - x
+ */
+
+ fx_start = center - x;
+ if (fx_start < 0)
+ fx_start = 0;
+ else if (fx_start > gsize - 1)
+ fx_start = gsize - 1;
+ fx_end = width + center - x - 1;
+ if (fx_end > gsize - 1)
+ fx_end = gsize - 1;
+ if(fx_end < fx_start)
+ fx_end = fx_start;
+
+ fy_start = center - y;
+ if (fy_start < 0)
+ fy_start = 0;
+ else if (fy_start > gsize - 1)
+ fy_start = gsize - 1;
+ fy_end = height + center - y - 1;
+ if (fy_end > gsize - 1)
+ fy_end = gsize - 1;
+ if(fy_end < fy_start)
+ fy_end = fy_start;
+
+ if (fx_start > 0 && fy_start > 0)
+ {
+ /* fx_start fx_end
+ +-------+---+---+---+---+---+---+---+
+ |(--)+ D|(-)|(-)|(-)|(-)|- B| | |
+ +-------+---+---+---+---+---+---+---+
+ fy_start |(-)|(+)|(+)|(+)|(+)|(+)| | |
+ +---+---+---+---+---+---+---+---+
+ |(-)|(+)|(+)|(+)|(+)|(+)| | |
+ +---+---+---+---+---+---+---+---+
+ |(-)|(+)|(+)|(+)|(+)|(+)| | |
+ +---+---+---+---+---+---+---+---+
+ fy_end |- C|(+)|(+)|(+)|(+)|+ A| | |
+ +---+---+---+---+---+---+---+---+
+ | | | | | | | | |
+ +---+---+---+---+---+---+---+---+
+ */
+ v = gsums[fy_end * gsize + fx_end] /* A */
+ - gsums[(fy_start - 1) * gsize + fx_end] /* B */
+ - gsums[fy_end * gsize + fx_start - 1] /* C */
+ + gsums[(fy_start - 1) * gsize + fx_start - 1]; /* D */
+ }
+ else if (fy_start > 0) /* fx_start == 0 */
+ {
+ v = gsums[fy_end * gsize + fx_end]
+ - gsums[(fy_start - 1) * gsize + fx_end]; /* B */
+ }
+ else if (fx_start > 0) /* fy_start == 0 */
+ {
+ v = gsums[fy_end * gsize + fx_end]
+ - gsums[fy_end * gsize + fx_start - 1];
+ }
+ else /* fx_start == 0 && fy_start == 0 */
+ {
+ v = gsums[fy_end * gsize + fx_end];
+ // printf("fx_start: %d, fx_end: %d, fy_start: %d, fy_end: %d, v: %f\n", fx_start, fx_end, fy_start, fy_end, v);
+ }
+
+ if (v > 1.0)
+ {
+ v = 1.0;
+ }
+ else if (v < 0.0)
+ {
+ v = 0.0;
+ }
+
+ return ((unsigned char) (v * opacity * 255.0));
+}
+
+
+#if 0
+static unsigned char
+sum_gaussian (conv *map, double opacity, int x, int y, int width, int height)
+{
+ int fx, fy;
double *g_data;
double *g_line = map->data;
int g_size = map->size;
@@ -212,6 +377,7 @@
return ((unsigned char) (v * opacity * 255.0));
}
+#endif
static XImage *
make_shadow (Display *dpy, double opacity, int width, int height)
@@ -239,22 +405,23 @@
* Build the gaussian in sections
*/
+ ylimit = gsize;
+ if (ylimit > sheight / 2)
+ ylimit = (sheight + 1) / 2;
+ xlimit = gsize;
+ if (xlimit > swidth / 2)
+ xlimit = (swidth + 1) / 2;
+
/*
- * center (fill the complete data array)
+ * center (fill the complete data array without top and bottom)
*/
d = sum_gaussian (gaussianMap, opacity, center, center, width, height);
- memset(data, d, sheight * swidth);
+ memset(&data[ylimit * swidth], d, (sheight - 2 * ylimit) * swidth);
/*
* corners
*/
- ylimit = gsize;
- if (ylimit > sheight / 2)
- ylimit = (sheight + 1) / 2;
- xlimit = gsize;
- if (xlimit > swidth / 2)
- xlimit = (swidth + 1) / 2;
for (y = 0; y < ylimit; y++)
for (x = 0; x < xlimit; x++)
@@ -301,15 +468,6 @@
}
}
- /*
- * center
- */
-
- d = sum_gaussian (gaussianMap, opacity, center, center, width, height);
- for (y = ylimit; y < sheight - ylimit; y++)
- for (x = xlimit; x < swidth - xlimit; x++)
- data[y * swidth + x] = d;
-
return ximage;
}