# HG changeset patch # User Thinker K.F. Li # Date 1292658105 -28800 # Node ID eca737d33a18f3dfa4219db03b330578e0611c3a # Parent b65ac686a7c5c891397ef48afc4c06486119d35e Improve performance of function to compute center of an arc. It is improved by using integer instead of floating point when computing. Some complicate computations are replaced by pre-computed table. diff -r b65ac686a7c5 -r eca737d33a18 configure.ac --- a/configure.ac Sat Dec 18 09:00:55 2010 +0800 +++ b/configure.ac Sat Dec 18 15:41:45 2010 +0800 @@ -32,6 +32,12 @@ # pkgconfig/pkg_check_modules.html PKG_PROG_PKG_CONFIG +# Checks for buuild time tools. +AC_PATH_PROG([PYTHON_PATH], [python]) +[if [ -z x"${PYTHON_PATH}" ]; then] +AC_MSG_ERROR([can not found Python script engine (install Python)]) +[fi] + # Checks for library functions. AC_FUNC_MALLOC AC_FUNC_REALLOC diff -r b65ac686a7c5 -r eca737d33a18 examples/svg2code_ex/svg2code_ex.svg --- a/examples/svg2code_ex/svg2code_ex.svg Sat Dec 18 09:00:55 2010 +0800 +++ b/examples/svg2code_ex/svg2code_ex.svg Sat Dec 18 15:41:45 2010 +0800 @@ -1,5 +1,6 @@ + diff -r b65ac686a7c5 -r eca737d33a18 src/Makefile.am --- a/src/Makefile.am Sat Dec 18 09:00:55 2010 +0800 +++ b/src/Makefile.am Sat Dec 18 15:41:45 2010 +0800 @@ -24,7 +24,7 @@ observer.c paint.c redraw_man.c rotate.c shape_path.c \ shape_rect.c shift.c subtree_free.c timer.c \ timertool.c tools.c visibility.c prop.c sprite.c \ - mouse.c shape_image.c $(MBAF_SOURCES) + mouse.c shape_image.c precomputed.c $(MBAF_SOURCES) libmbfly_la_CPPFLAGS = libmbfly_la_LDFLAGS = @@ -100,3 +100,7 @@ testcase_LDFLAGS = -lcunit -L/usr/local/lib/ @pangocairo_LIBS@ EXTRA_PROGRAMS = testcase + +precomputed.c precomputed.h: $(top_srcdir)/tools/gen_precomputed_tabs.py + $(PYTHON_PATH) $(top_srcdir)/tools/gen_precomputed_tabs.py \ + precomputed.c precomputed.h diff -r b65ac686a7c5 -r eca737d33a18 src/shape_path.c --- a/src/shape_path.c Sat Dec 18 09:00:55 2010 +0800 +++ b/src/shape_path.c Sat Dec 18 15:41:45 2010 +0800 @@ -4,6 +4,7 @@ #include #include #include +#include #include "mb_graph_engine.h" #include "mb_types.h" #include "mb_redraw_man.h" @@ -47,6 +48,12 @@ #define OK 0 #define ERR -1 #define PI 3.1415926535897931 +#define FRAC_PI 51472 + +#define SWAP(x, y) do { x ^= y; y ^= x; x ^= y; } while(0) +#define MAX(x, y) (((x) > (y))? (x): (y)) +#define MIN(x, y) (((x) > (y))? (y): (x)) +#define IS_NEGATIVE(x) ((x) & ~(-1 >> 1)) #ifdef UNITTEST #undef rdman_man_shape @@ -70,7 +77,284 @@ /* ============================================================ * Implement arc in path. */ -#include +#if 1 + +#include "precomputed.h" + +#define ABS(x) (((x) > 0)? (x): -(x)) + +/*! \brief Compute the small slope of a vector. + * + * A small slope is based on absolute value of x-axis and y-axis. + * And use smaller one of absolute values as divisor. + */ +static int +_small_slope(int x, int y) { + int _x, _y; + int r; + + _x = ABS(x); + _y = ABS(y); + if(_x > _y) + r = (_y << FRACTION_SHIFT) / _x; + else + r = (_x << FRACTION_SHIFT) / _y; + + return r; +} + +/*! \brief Index a given angle in slope table. + * + * Binary search. + */ +static int +_find_slope_index(int slope) { + int left, right, v; + + left = 0; + right = SLOPE_TAB_SZ - 1; + while(left <= right) { + v = (left + right) >> 1; + if(slope < slope_tab[v]) + right = v - 1; + else + left = v + 1; + } + + return v; +} + +static int +_vector_len(int x, int y) { + int _x, _y; + int slope; + int slope_index; + int radius; + + _x = ABS(x); + _y = ABS(y); + + if(_x > _y) { + slope = (_y << FRACTION_SHIFT) / _x; + slope_index = _find_slope_index(slope); + radius = _x * vector_len_factor_tab[slope_index]; + } else { + slope = (_x << FRACTION_SHIFT) / _y; + slope_index = _find_slope_index(slope); + radius = _y * vector_len_factor_tab[slope_index]; + } + + return radius; +} + +/*! \brief Find index of an arc-to-radius ratio in arc_radius_ratio_tab. + * + * Binary search. + */ +static int +_find_arc_radius(int arc_radius_ratio) { + int left, right, v; + + left = 0; + right = ARC_RADIUS_RATIO_TAB_SZ - 1; + while(left <= right) { + v = (left + right) >> 1; + if(arc_radius_ratio < arc_radius_ratio_tab[v]) + right = v - 1; + else + left = v + 1; + } + + return v; +} + +/* Compute shift factor for the ratio of arc to radius */ +static int +_get_arc_radius_shift_factor(int arc_x, int arc_y, int radius) { + int arc_len; + int radius_len; + int arc_radius_ratio; + int arc_radius_index; + int arc_radius_factor; + + arc_len = _vector_len(ABS(arc_x), ABS(arc_y)); + arc_radius_ratio = (arc_len << FRACTION_SHIFT) / radius; + arc_radius_index = _find_arc_radius(arc_radius_ratio); + + arc_radius_factor = arc_radius_factor_tab[arc_radius_index]; + + return arc_radius_factor; +} + +/* Return a unit vector in the extend direction. + * + * This function make a decision on the direction of extend to make + * radius of rx direction equivlant to ry direction. It extends the + * direction of short one. + */ +static void +_compute_extend_unit_vector(int rx, int ry, int x_rotate, + int *ext_unit_x, int *ext_unit_y) { + int extend_dir; + int extend_phase; + int extend_index; + int extend_sin, extend_cos; + /* Change sign of x, y values accroding phase of the vector. */ + static int sin_cos_signs_tab[4][2] = { + /* 0 for positive, 1 for negative */ + {0, 0}, {1, 0}, {1, 1}, {0, 1}}; + int *signs; + + if(rx > ry) + extend_dir = x_rotate + (FRAC_PI >> 1); + else + extend_dir = x_rotate; + extend_dir %= FRAC_PI * 2; + extend_phase = extend_dir / (FRAC_PI >> 1); + + extend_index = (extend_dir % (FRAC_PI >> 4)) * SIN_TAB_SZ / + (FRAC_PI >> 4); + if(extend_phase & 0x1) /* half-phases 1,3 */ + extend_index = SIN_TAB_SZ - extend_index - 1; + + extend_sin = sin_tab[extend_index]; + extend_cos = sin_tab[SIN_TAB_SZ - extend_index - 1]; + + signs = sin_cos_signs_tab[extend_phase]; + *ext_unit_x = signs[0]? -extend_cos: extend_cos; + *ext_unit_y = signs[1]? -extend_sin: extend_sin; +} + +static int +_calc_center_i(int x0, int y0, + int x, int y, + int rx, int ry, + int x_rotate, + int large, int sweep, + int *cx, int *cy) { + int radius; + int ext_unit_y, ext_unit_x; /* x and y value of unit vector on + * extend direction */ + int arc_x, arc_y; + int radius_ref_ratio; + int arc_radius_factor; + int stat = 0; + int slope, slope_index; + int shift_cx, shift_cy; + int center_shift_factor; + static int negatives[4] = {0, 1, 1, 0}; + /* Change sign of shift-x/y accroding sign of arc_x, arc_y, + * large and sweep. + */ + static int shift_signs_tab[16][2] = { + /* -x,-y +x,-y -x,+y +x,+y */ + {0, 0}, {0, 1}, {1, 0}, {1, 1}, /* small, negative-angle */ + {1, 1}, {1, 0}, {0, 1}, {0, 0}, /* large, negative-angle */ + {1, 1}, {1, 0}, {0, 1}, {0, 0}, /* small, positive-angle */ + {0, 0}, {0, 1}, {1, 0}, {1, 1} /* large, positive-angle */ + }; + int extend_len; + int extend_x, extend_y; + + arc_x = x - x0; + arc_y = y - y0; + + if(arc_x == 0 && arc_y == 0) { + *cx = x0; + *cy = y0; + return OK; + } + + /* Translate arc to the coordinate that extend rx or ry to the + * equivlant size as another. It translate the ellipse to a + * circle. + */ + radius = MAX(rx, ry); + _compute_extend_unit_vector(rx, ry, x_rotate, &ext_unit_x, &ext_unit_y); + + extend_len = (arc_x * ext_unit_x + arc_y * ext_unit_y) >> FRACTION_SHIFT; + extend_len = extend_len * MAX(rx, ry) / MIN(rx, ry) - + (1 << FRACTION_SHIFT); + extend_x = ext_unit_x * extend_len; + extend_y = ext_unit_y * extend_len; + + arc_x += extend_x; + arc_y += extend_y; + + /* Find range index of slope. */ + slope = _small_slope(arc_x, arc_y); + slope_index = _find_slope_index(slope); + + /* Compute shift factor for the ratio of arc to radius */ + arc_radius_factor = _get_arc_radius_shift_factor(arc_x, arc_y, radius); + + /* Compute ratio of radius to reference radius */ + radius_ref_ratio = radius >> REF_RADIUS_SHIFT; + + /* Compute x/y-shift of center range index according + * slope_index, radius_ref_ratio and arc_radius_factor. + */ + center_shift_factor = radius_ref_ratio * arc_radius_factor; + center_shift_factor = center_shift_factor >> FRACTION_SHIFT; + shift_cx = (center_shift_tab[slope_index][0] * center_shift_factor) >> + FRACTION_SHIFT; + shift_cy = (center_shift_tab[slope_index][1] * center_shift_factor) >> + FRACTION_SHIFT; + if(ABS(arc_x) <= ABS(arc_y)) + SWAP(shift_cx, shift_cy); + + if(IS_NEGATIVE(arc_x)) + stat |= 0x1; + if(IS_NEGATIVE(arc_y)) + stat |= 0x2; + if(large) + stat |= 0x4; + if(sweep) + stat |= 0x8; + if(shift_signs_tab[stat][0]) + shift_cx = -shift_cx; + if(shift_signs_tab[stat][1]) + shift_cy = -shift_cy; + + shift_cx += arc_x >> 2; + shift_cy += arc_y >> 2; + + /* translate shift_cx/cy back to original coordinate */ + extend_len = (shift_cx * ext_unit_x + shift_cy * ext_unit_y) + >> FRACTION_SHIFT; + extend_len = extend_len - extend_len * MIN(rx, ry) / MAX(rx, ry); + extend_x = (ext_unit_x * extend_len) >> FRACTION_SHIFT; + extend_y = (ext_unit_y * extend_len) >> FRACTION_SHIFT; + shift_cx = shift_cx - extend_x; + shift_cy = shift_cy - extend_y; + + /* get center */ + *cx = x0 + shift_cx; + *cy = y0 + shift_cy; + + return OK; +} + +static int _calc_center(co_aix x0, co_aix y0, + co_aix x, co_aix y, + co_aix rx, co_aix ry, + co_aix x_rotate, + int large, int sweep, + co_aix *cx, co_aix *cy) { + int cx_i, cy_i; + int r; + + r = _calc_center_i(x0 * (1 << FRACTION_SHIFT), y0 * (1 << FRACTION_SHIFT), + x * (1 << FRACTION_SHIFT), y * (1 << FRACTION_SHIFT), + rx * (1 << FRACTION_SHIFT), ry * (1 << FRACTION_SHIFT), + x_rotate * (1 << FRACTION_SHIFT), + large, sweep, &cx_i, &cy_i); + *cx = cx_i; + *cy = cy_i; + return r; +} + +#else /*! \brief Calculate center of the ellipse of an arc. * * Origin of our coordination is left-top corner, and y-axis are grown @@ -119,26 +403,33 @@ co_aix x_rotate, int large, int sweep, co_aix *cx, co_aix *cy) { - co_aix nrx, nry, nrx0, nry0; + co_aix br_x, br_y, br_x0, br_y0; /* before-rotated x, y, x0, y0 */ co_aix udx, udy, udx2, udy2; co_aix umx, umy; co_aix udcx, udcy; - co_aix nrcx, nrcy; + co_aix br_cx, br_cy; co_aix udl2; - float _sin = sinf(x_rotate); + co_aix rev_rx2, rev_ry2; + float _sin = -sinf(x_rotate); /* rotate to oposite direction */ float _cos = cosf(x_rotate); int reflect; - /* Compute center of the ellipse */ - nrx = x * _cos + y * _sin; - nry = x * -_sin + y * _cos; - nrx0 = x0 * _cos + y0 * _sin; - nry0 = x0 * -_sin + y0 * _cos; +#define X_AFTER_ROTATE(x, y, sin, cos) (x * cos - y * sin) +#define Y_AFTER_ROTATE(x, y, sin, cos) (x * sin + y * cos) - udx = (nrx - nrx0) / 2 / rx; /* ux - umx */ - udy = (nry - nry0) / 2 / ry; /* uy - umy */ - umx = (nrx + nrx0) / 2 / rx; - umy = (nry + nry0) / 2 / ry; + /* Restore positions to the value before rotation */ + br_x = X_AFTER_ROTATE(x, y, _sin, _cos); + br_y = Y_AFTER_ROTATE(x, y, _sin, _cos); + br_x0 = X_AFTER_ROTATE(x0, y0, _sin, _cos); + br_y0 = Y_AFTER_ROTATE(x0, y0, _sin, _cos); + + /* Resize to be an unit circle */ + rev_rx2 = 1.0 / (2 * rx); + rev_ry2 = 1.0 / (2 * ry); + udx = (br_x - br_x0) * rev_rx2; /* ux - umx */ + udy = (br_y - br_y0) * rev_ry2; /* uy - umy */ + umx = (br_x + br_x0) * rev_rx2; + umy = (br_y + br_y0) * rev_ry2; udx2 = udx * udx; udy2 = udy * udy; @@ -164,15 +455,15 @@ udcy = -udcy; } - nrcx = rx * (udcx + umx); - nrcy = ry * (udcy + umy); + br_cx = rx * (udcx + umx); + br_cy = ry * (udcy + umy); - *cx = nrcx * _cos - nrcy * _sin; - *cy = nrcx * _sin + nrcy * _cos; + *cx = X_AFTER_ROTATE(br_cx, br_cy, -_sin, _cos); + *cy = Y_AFTER_ROTATE(br_cx, br_cy, -_sin, _cos); return OK; } - +#endif static co_aix _angle_rotated_ellipse(co_aix x, co_aix y, co_aix rx, co_aix ry, @@ -1092,6 +1383,9 @@ sh_path_free((shape_t *)path); } +void test_calc_center(void) { +} + void test_spaces_head_tail(void) { sh_path_t *path; redraw_man_t rdman; @@ -1109,6 +1403,7 @@ suite = CU_add_suite("Suite_shape_path", NULL, NULL); CU_ADD_TEST(suite, test_rdman_shape_path_new); CU_ADD_TEST(suite, test_path_transform); + CU_ADD_TEST(suite, test_calc_center); return suite; } diff -r b65ac686a7c5 -r eca737d33a18 tools/gen_precomputed_tabs.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tools/gen_precomputed_tabs.py Sat Dec 18 15:41:45 2010 +0800 @@ -0,0 +1,263 @@ +#!/usr/bin/env python +from math import pi, sin, cos, sqrt + +# #define FRACTION_SHIFT 10 +# +# #define REF_RADIUS_SHIFT 10 +# #define SLOPE_TAB_SZ 128 +# #define ARC_RADIUS_RATIO_TAB_SZ 128 +# #define ARC_RADIUS_FACTOR_TAB_SZ ARC_RADIUS_RATIO_TAB_SZ +# #define SIN_TAB_SZ 256 +# static int slope_tab[SLOPE_TAB_SZ]; +# static int center_shift_tab[SLOPE_TAB_SZ][2]; +# static int vector_len_factor_tab[SLOPE_TAB_SZ]; +# static int arc_radius_ratio_tab[ARC_RADIUS_RATIO_TAB_SZ]; +# static int arc_radius_factor_tab[ARC_RADIUS_FACTOR_TAB_SZ]; +# static int sin_tab[SIN_TAB_SZ]; + +class tabs_generator(object): + _fraction_shift = 10 + _ref_radius_shift = 10 + _slope_tab_sz = 128 + _arc_radius_ratio_tab_sz = 128 + _arc_radius_factor_tab_sz = 128 + _sin_tab_sz = 256 + + def gen_slope_tab(self): + lines = [] + line = '''\ +/*! \\brief The table used to map a slope to an index. + * + * The index is used to be a key in other tables. + * The table is an array of slope values for vectors in 0~(PI/4) + * direction. + */\ +''' + lines.append(line) + line = 'int slope_tab[SLOPE_TAB_SZ] = {' + lines.append(line) + + factor = 1 << self._fraction_shift + + for i in range(self._slope_tab_sz): + angle = pi / 4 * i / (self._slope_tab_sz - 1) + slope = int(sin(angle) / cos(angle) * factor) + line = ' %d,' % (slope) + lines.append(line) + pass + + line = ' };' + lines.append(line) + return lines + + def gen_center_shift_tab(self): + lines = [] + line = '''\ +/*! \\brief The table maps the slope of an arc to the factors of shifting. + * + * Every mapped slope is associated with two factors for x and y + * axis respective. The are multiplied with length of the arc to + * get shifting value in x and y axis direction. + */\ +''' + lines.append(line) + line = 'int center_shift_tab[SLOPE_TAB_SZ][2] = {' + lines.append(line) + + radius = 1 << (self._ref_radius_shift + self._fraction_shift) + + for i in range(self._slope_tab_sz): + angle = pi / 4 * i / (self._slope_tab_sz - 1) + x = -int(cos(angle) * radius) + y = -int(sin(angle) * radius) + line = ' {%d, %d},' % (x, y) + lines.append(line) + pass + + line = ' };' + lines.append(line) + return lines + + def gen_vector_len_factor_tab(self): + lines = [] + line = '''\ +/*! \\brief The table maps a slope to a lenght factor for a vector. + * + * The factor is used to multipled with one of axis values + * to get the lenght of the vector. + * The range of mapped slopes are 0~(PI/4). + */\ +''' + lines.append(line) + line = 'int vector_len_factor_tab[SLOPE_TAB_SZ] = {' + lines.append(line) + + frac_factor = 1 << self._fraction_shift + + for i in range(self._slope_tab_sz): + angle = pi / 4 * i / (self._slope_tab_sz - 1) + factor = int((1 / cos(angle)) * frac_factor) + line = ' %d,' % (factor) + lines.append(line) + pass + + line = ' };' + lines.append(line) + return lines + + def gen_arc_radius_ratio_tab(self): + lines = [] + line = '''\ +/*! \\brief A table of ratio from an arc to its radius. + * + * It is to find an index for a given ratio value. + */\ +''' + lines.append(line) + line = 'int arc_radius_ratio_tab[ARC_RADIUS_RATIO_TAB_SZ] = {' + lines.append(line) + + frac_factor = 1 << self._fraction_shift + + for i in range(self._arc_radius_ratio_tab_sz): + arc_ratio = 2.0 * i / (self._arc_radius_ratio_tab_sz - 1) + arc_ratio = int(arc_ratio * frac_factor) + line = ' %d,' % (arc_ratio) + lines.append(line) + pass + + line = ' };' + lines.append(line) + return lines + + def gen_arc_radius_factor_tab(self): + lines = [] + line = '''\ +/*! \\brief The table maps an arc-radius ratio to a distance factor. + * + * The factor is multiplied with radius to get distance of arc and + * center. It is in the order of arc_radius_ratio_tab. + */\ +''' + lines.append(line) + line = 'int arc_radius_factor_tab[ARC_RADIUS_FACTOR_TAB_SZ] = {' + lines.append(line) + + frac_factor = 1 << self._fraction_shift + + for i in range(self._arc_radius_factor_tab_sz): + arc = 2.0 * i / (self._arc_radius_factor_tab_sz - 1) + factor = int(sqrt(1 - (arc / 2) ** 2) * frac_factor) + line = ' %d,' % (factor) + lines.append(line) + pass + + line = ' };' + lines.append(line) + return lines + + def gen_sin_tab(self): + lines = [] + line = '/*! \\brief A table of sin() values */' + lines.append(line) + line = 'int sin_tab[SIN_TAB_SZ] = {' + lines.append(line) + + frac_factor = 1 << self._fraction_shift + + for i in range(self._sin_tab_sz): + angle = i * pi / 2 / (self._sin_tab_sz - 1) + _sin = int(sin(angle) * frac_factor) + line = ' %d,' % (_sin) + lines.append(line) + pass + + line = ' };' + lines.append(line) + return lines + + def gen_definition(self, out): + line = '/* This file is generated by tools/gen_precomputed_tabs.py */' + print >> out, line + print >> out + lines = self.gen_slope_tab() + print >> out, '\n'.join(lines) + print >> out + print >> out + lines = self.gen_center_shift_tab() + print >> out, '\n'.join(lines) + print >> out + print >> out + lines = self.gen_vector_len_factor_tab() + print >> out, '\n'.join(lines) + print >> out + print >> out + lines = self.gen_arc_radius_ratio_tab() + print >> out, '\n'.join(lines) + print >> out + print >> out + lines = self.gen_arc_radius_factor_tab() + print >> out, '\n'.join(lines) + print >> out + print >> out + lines = self.gen_sin_tab() + print >> out, '\n'.join(lines) + print >> out + pass + + def gen_declaration(self, out): + line = '''\ +#define FRACTION_SHIFT %d + +#define REF_RADIUS_SHIFT %d +#define SLOPE_TAB_SZ %d +#define ARC_RADIUS_RATIO_TAB_SZ %d +#define ARC_RADIUS_FACTOR_TAB_SZ %d +#define SIN_TAB_SZ %d + +extern int slope_tab[SLOPE_TAB_SZ]; +extern int center_shift_tab[SLOPE_TAB_SZ][2]; +extern int vector_len_factor_tab[SLOPE_TAB_SZ]; +extern int arc_radius_ratio_tab[ARC_RADIUS_RATIO_TAB_SZ]; +extern int arc_radius_factor_tab[ARC_RADIUS_FACTOR_TAB_SZ]; +extern int sin_tab[SIN_TAB_SZ]; +''' + line = line % (self._fraction_shift, self._ref_radius_shift, + self._slope_tab_sz, self._arc_radius_ratio_tab_sz, + self._arc_radius_factor_tab_sz, self._sin_tab_sz) + print >> out, line + pass + pass + +if __name__ == '__main__': + import sys + + def usage(progname): + print >> sys.stderr, 'Usage: %s

' % (progname) + sys.exit(255) + pass + + if len(sys.argv) != 3: + usage(sys.argv[0]) + pass + + cfile = sys.argv[1] + hfile = sys.argv[2] + + gen = tabs_generator() + + cout = file(cfile, 'w+') + print >> cout, '#include "%s"' % (hfile) + print >> cout + gen.gen_definition(cout) + cout.close() + + hout = file(hfile, 'w+') + sentinel = '__' + hfile.upper().replace('.', '_') + '_' + print >> hout, '#ifndef %s' % (sentinel) + print >> hout, '#define %s' % (sentinel) + print >> hout + gen.gen_declaration(hout) + print >> hout, '#endif /* %s */' % (sentinel) + hout.close() + pass