Mercurial > MadButterfly

changeset 1132:3de972a43d46

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge
author wycc
date Sat, 18 Dec 2010 23:51:22 +0800
parents 3ec0ad89e443 (current diff) eca737d33a18 (diff)
children bc619172bd2c
files
diffstat 5 files changed, 727 insertions(+), 145 deletions(-) [+]
line wrap: on
line diff
--- 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
--- 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 @@
 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
 <!-- Created with Inkscape (http://www.inkscape.org/) -->
+
 <svg
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:cc="http://creativecommons.org/ns#"
@@ -13,9 +14,8 @@
    height="600"
    id="svg2"
    sodipodi:version="0.32"
-   inkscape:version="0.46"
+   inkscape:version="0.47 r22583"
    version="1.0"
-   sodipodi:docbase="/usr/home/thinker/progm/MadButterfly/examples/svg2code_ex"
    sodipodi:docname="svg2code_ex.svg"
    inkscape:output_extension="org.inkscape.output.svg.inkscape">
   <defs
@@ -322,7 +322,7 @@
      inkscape:pageshadow="2"
      inkscape:zoom="0.63166667"
      inkscape:cx="400"
-     inkscape:cy="176.10388"
+     inkscape:cy="239.42842"
      inkscape:document-units="px"
      inkscape:current-layer="layer1"
      width="800px"
@@ -331,7 +331,8 @@
      inkscape:window-width="822"
      inkscape:window-height="721"
      inkscape:window-x="130"
-     inkscape:window-y="120" />
+     inkscape:window-y="120"
+     inkscape:window-maximized="0" />
   <metadata
      id="metadata7">
     <rdf:RDF>
@@ -347,127 +348,140 @@
      inkscape:label="Layer 1"
      inkscape:groupmode="layer"
      id="layer1"
-     style="display:inline">
-    <rect
-       style="opacity:1;fill:url(#linearGradient5140);fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;display:none"
-       id="rect5132"
-       width="802.63855"
-       height="601.58313"
-       x="0"
-       y="0" />
-    <rect
-       style="opacity:0.5;fill:url(#radialGradient4155);fill-opacity:1.0;stroke:#000000;stroke-width:0.81232697;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
-       id="rect3174"
-       width="801.2431"
-       height="39.687672"
-       x="-0.093836516"
-       y="-0.093836516" />
-    <rect
-       style="opacity:1;fill:#f9f9f9;fill-opacity:1;stroke:#000000;stroke-width:1.2880522;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
-       id="rect5128"
-       width="458.71194"
-       height="418.71198"
-       x="20.644026"
-       y="60.644024"
-       rx="4.0216751"
-       ry="5.0559778" />
-    <rect
-       style="opacity:1;fill:#f9f9f9;fill-opacity:1;stroke:#000000;stroke-width:0.93608844;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
-       id="rect5130"
-       width="259.5639"
-       height="419.56393"
-       x="519.96802"
-       y="59.96804"
-       rx="5.0424933" />
-    <rect
-       style="opacity:1;fill:#ffffff;fill-opacity:1;stroke:#000000;stroke-width:0.97354287;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
-       id="rect5144"
-       width="459.52646"
-       height="79.526451"
-       x="19.986771"
-       y="499.98679" />
-    <path
-       style="fill:#00ffff;fill-rule:evenodd;stroke:url(#linearGradient6123);stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;stroke-miterlimit:4;stroke-dasharray:none;fill-opacity:1.0"
-       d="M 20.580475,489.18206 L 471.76781,490.76517"
-       id="path5146" />
-    <g
-       id="file_button"
-       transform="translate(6.3324538,1.5831135)">
-      <rect
-         ry="3.0364513"
-         rx="1.1221098"
-         y="1.3907586"
-         x="18.805006"
-         height="32.046982"
-         width="81.123505"
-         id="rect6129"
-         style="opacity:0.9;fill:url(#radialGradient8096);fill-opacity:1;stroke:#000000;stroke-width:0.61528957;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
-      <text
-         id="text8071"
-         y="22.163589"
-         x="44.327179"
-         style="font-size:16px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans Mono"
-         xml:space="preserve"><tspan
-           y="22.163589"
-           x="44.327179"
-           id="tspan8073"
-           sodipodi:role="line">檔案</tspan></text>
-    </g>
-    <g
-       id="file_menu"
-       display="none"
-       style="display:none">
-      <rect
-         y="41.991447"
-         x="20.458471"
-         height="237.55008"
-         width="232.80074"
-         id="rect3157"
-         style="opacity:0.5;fill:url(#radialGradient7686);fill-opacity:1;stroke:#000000;stroke-width:0.91694379;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
-      <rect
-         y="46.864952"
-         x="26.915098"
-         height="219.88747"
-         width="215.13812"
-         id="rect2160"
-         style="opacity:0.5;fill:url(#linearGradient7683);fill-opacity:1;stroke:#000000;stroke-width:1.16530466;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
-      <text
-         sodipodi:linespacing="125%"
-         style="font-size:16px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-opacity:1;font-family:Bitstream Vera Sans"
-         id="text3134"
-         y="86.360161"
-         x="52.16227"
-         xml:space="preserve"><tspan
-           y="86.360161"
-           x="52.16227"
-           id="tspan3136"
-           sodipodi:role="line">test</tspan><tspan
-           id="tspan3138"
-           y="118.32115"
-           x="52.16227"
-           sodipodi:role="line"
-           style="font-size:28px">test</tspan></text>
-    </g>
-    <path
-       sodipodi:type="arc"
-       style="opacity:1;fill:none;fill-opacity:1;stroke:#000000;stroke-width:2.39700007;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
-       id="path2451"
-       sodipodi:cx="648.28497"
-       sodipodi:cy="541.4248"
-       sodipodi:rx="98.944588"
-       sodipodi:ry="37.994728"
-       d="M 723.62808,516.79651 A 98.944588,37.994728 0 1 1 549.36227,542.22385"
-       sodipodi:start="5.5779634"
-       sodipodi:end="9.4037459"
-       sodipodi:open="true"/>
-    <image
-       y="87.316605"
-       x="605.409"
-       id="image2497"
-       height="130.90765"
-       width="100"
-       sodipodi:absref="/usr/home/thinker/progm/MadButterfly/examples/svg2code_ex/dsc_3241.png"
-       xlink:href="dsc_3241.png" />
-        transform="translate(0,-17.414248)" />
+     style="display:inline"><rect
+   style="fill:#ffffff;fill-opacity:1;stroke:#000000;stroke-width:4"
+   id="rect2885"
+   width="804.22162"
+   height="606.33246"
+   x="-1.5831134"
+   y="-1.5831103"
+   inkscape:transform-center-x="0"
+   inkscape:transform-center-y="0"
+   inkscape:bbox-x="-3.5831134"
+   inkscape:bbox-y="-6.7493482"
+   inkscape:bbox-width="808.22162"
+   inkscape:bbox-height="610.33246" />
+<rect
+   style="opacity:1;fill:url(#linearGradient5140);fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;display:none"
+   id="rect5132"
+   width="802.63855"
+   height="601.58313"
+   x="0"
+   y="0" />
+<rect
+   style="opacity:0.5;fill:url(#radialGradient4155);fill-opacity:1.0;stroke:#000000;stroke-width:0.81232697;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
+   id="rect3174"
+   width="801.2431"
+   height="39.687672"
+   x="-0.093836516"
+   y="-0.093836516" />
+<rect
+   style="opacity:1;fill:#f9f9f9;fill-opacity:1;stroke:#000000;stroke-width:1.2880522;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
+   id="rect5128"
+   width="458.71194"
+   height="418.71198"
+   x="20.644026"
+   y="60.644024"
+   rx="4.0216751"
+   ry="5.0559778" />
+<rect
+   style="opacity:1;fill:#f9f9f9;fill-opacity:1;stroke:#000000;stroke-width:0.93608844;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
+   id="rect5130"
+   width="259.5639"
+   height="419.56393"
+   x="519.96802"
+   y="59.96804"
+   rx="5.0424933" />
+<rect
+   style="opacity:1;fill:#ffffff;fill-opacity:1;stroke:#000000;stroke-width:0.97354287;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
+   id="rect5144"
+   width="459.52646"
+   height="79.526451"
+   x="19.986771"
+   y="499.98679" />
+<path
+   style="fill:#00ffff;fill-rule:evenodd;stroke:url(#linearGradient6123);stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;stroke-miterlimit:4;stroke-dasharray:none;fill-opacity:1.0"
+   d="M 20.580475,489.18206 L 471.76781,490.76517"
+   id="path5146" />
+<g
+   id="file_button"
+   transform="translate(6.3324538,1.5831135)">
+  <rect
+     ry="3.0364513"
+     rx="1.1221098"
+     y="1.3907586"
+     x="18.805006"
+     height="32.046982"
+     width="81.123505"
+     id="rect6129"
+     style="opacity:0.9;fill:url(#radialGradient8096);fill-opacity:1;stroke:#000000;stroke-width:0.61528957;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
+  <text
+     id="text8071"
+     y="22.163589"
+     x="44.327179"
+     style="font-size:16px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans Mono"
+     xml:space="preserve"><tspan
+       y="22.163589"
+       x="44.327179"
+       id="tspan8073"
+       sodipodi:role="line">檔案</tspan></text>
+</g>
+<g
+   id="file_menu"
+   display="none"
+   style="display:none">
+  <rect
+     y="41.991447"
+     x="20.458471"
+     height="237.55008"
+     width="232.80074"
+     id="rect3157"
+     style="opacity:0.5;fill:url(#radialGradient7686);fill-opacity:1;stroke:#000000;stroke-width:0.91694379;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
+  <rect
+     y="46.864952"
+     x="26.915098"
+     height="219.88747"
+     width="215.13812"
+     id="rect2160"
+     style="opacity:0.5;fill:url(#linearGradient7683);fill-opacity:1;stroke:#000000;stroke-width:1.16530466;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
+  <text
+     sodipodi:linespacing="125%"
+     style="font-size:16px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;stroke-opacity:1;font-family:Bitstream Vera Sans"
+     id="text3134"
+     y="86.360161"
+     x="52.16227"
+     xml:space="preserve"><tspan
+       y="86.360161"
+       x="52.16227"
+       id="tspan3136"
+       sodipodi:role="line">test</tspan><tspan
+       id="tspan3138"
+       y="118.32115"
+       x="52.16227"
+       sodipodi:role="line"
+       style="font-size:28px">test</tspan></text>
+</g>
+<path
+   sodipodi:type="arc"
+   style="opacity:1;fill:none;fill-opacity:1;stroke:#000000;stroke-width:2.39700007;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
+   id="path2451"
+   sodipodi:cx="648.28497"
+   sodipodi:cy="541.4248"
+   sodipodi:rx="98.944588"
+   sodipodi:ry="37.994728"
+   d="M 723.62808,516.79651 A 98.944588,37.994728 0 1 1 549.36227,542.22385"
+   sodipodi:start="5.5779634"
+   sodipodi:end="9.4037459"
+   sodipodi:open="true" />
+<image
+   sodipodi:absref="/usr/home/thinker/progm/MadButterfly/examples/svg2code_ex/dsc_3241.png"
+   xlink:href="dsc_3241.png"
+   width="100"
+   height="130.90765"
+   id="image2497"
+   x="605.409"
+   y="87.316605" />
+
+        transform=&quot;translate(0,-17.414248)&quot; /&gt;
   </g>
 </svg>
--- 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
--- 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 <stdlib.h>
 #include <ctype.h>
 #include <string.h>
+#include <math.h>
 #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 <math.h>
+#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;
 }
--- /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 <C file> <header file>' % (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