Another optimization for shadow calculation in xcompmgr.c
Michael Knorr
damage-list@freenet.de
Wed, 03 Dec 2003 01:27:11 +0100
This is a multi-part message in MIME format.
--------------050308090906070208000409
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
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
--------------050308090906070208000409
Content-Type: text/plain;
name="xcomp.diff"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="xcomp.diff"
--- ../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;
}
--------------050308090906070208000409--