# HG changeset patch # User wycc # Date 1292687482 -28800 # Node ID 3de972a43d46469bc24b8f0ee4ff183d1339da0b # Parent 3ec0ad89e443e8ceb0f6c415d397b5ca3203ff15# Parent eca737d33a18f3dfa4219db03b330578e0611c3a Merge diff -r 3ec0ad89e443 -r 3de972a43d46 configure.ac --- a/configure.ac Sat Dec 18 23:50:43 2010 +0800 +++ b/configure.ac Sat Dec 18 23:51:22 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 3ec0ad89e443 -r 3de972a43d46 examples/svg2code_ex/svg2code_ex.svg --- a/examples/svg2code_ex/svg2code_ex.svg Sat Dec 18 23:50:43 2010 +0800 +++ b/examples/svg2code_ex/svg2code_ex.svg Sat Dec 18 23:51:22 2010 +0800 @@ -1,5 +1,6 @@ + + inkscape:window-y="120" + inkscape:window-maximized="0" /> @@ -347,127 +348,140 @@ inkscape:label="Layer 1" inkscape:groupmode="layer" id="layer1" - style="display:inline"> - - - - - - - - - 檔案 - - - - - transform="translate(0,-17.414248)" /> + style="display:inline"> + + + + + + + + + 檔案 + + + + + + transform="translate(0,-17.414248)" /> diff -r 3ec0ad89e443 -r 3de972a43d46 src/Makefile.am --- a/src/Makefile.am Sat Dec 18 23:50:43 2010 +0800 +++ b/src/Makefile.am Sat Dec 18 23:51:22 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 3ec0ad89e443 -r 3de972a43d46 src/shape_path.c --- a/src/shape_path.c Sat Dec 18 23:50:43 2010 +0800 +++ b/src/shape_path.c Sat Dec 18 23:51:22 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 3ec0ad89e443 -r 3de972a43d46 tools/gen_precomputed_tabs.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tools/gen_precomputed_tabs.py Sat Dec 18 23:51:22 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