Mercurial > MadButterfly

comparison tools/gen_precomputed_tabs.py @ 1129:eca737d33a18

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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.
author Thinker K.F. Li <thinker@codemud.net>
date Sat, 18 Dec 2010 15:41:45 +0800
parents
children bd0cfb8666b8
comparison
equal deleted inserted replaced
1128:b65ac686a7c5 1129:eca737d33a18
1 #!/usr/bin/env python
2 from math import pi, sin, cos, sqrt
3
4 # #define FRACTION_SHIFT 10
5 #
6 # #define REF_RADIUS_SHIFT 10
7 # #define SLOPE_TAB_SZ 128
8 # #define ARC_RADIUS_RATIO_TAB_SZ 128
9 # #define ARC_RADIUS_FACTOR_TAB_SZ ARC_RADIUS_RATIO_TAB_SZ
10 # #define SIN_TAB_SZ 256
11 # static int slope_tab[SLOPE_TAB_SZ];
12 # static int center_shift_tab[SLOPE_TAB_SZ][2];
13 # static int vector_len_factor_tab[SLOPE_TAB_SZ];
14 # static int arc_radius_ratio_tab[ARC_RADIUS_RATIO_TAB_SZ];
15 # static int arc_radius_factor_tab[ARC_RADIUS_FACTOR_TAB_SZ];
16 # static int sin_tab[SIN_TAB_SZ];
17
18 class tabs_generator(object):
19 _fraction_shift = 10
20 _ref_radius_shift = 10
21 _slope_tab_sz = 128
22 _arc_radius_ratio_tab_sz = 128
23 _arc_radius_factor_tab_sz = 128
24 _sin_tab_sz = 256
25
26 def gen_slope_tab(self):
27 lines = []
28 line = '''\
29 /*! \\brief The table used to map a slope to an index.
30 *
31 * The index is used to be a key in other tables.
32 * The table is an array of slope values for vectors in 0~(PI/4)
33 * direction.
34 */\
35 '''
36 lines.append(line)
37 line = 'int slope_tab[SLOPE_TAB_SZ] = {'
38 lines.append(line)
39
40 factor = 1 << self._fraction_shift
41
42 for i in range(self._slope_tab_sz):
43 angle = pi / 4 * i / (self._slope_tab_sz - 1)
44 slope = int(sin(angle) / cos(angle) * factor)
45 line = ' %d,' % (slope)
46 lines.append(line)
47 pass
48
49 line = ' };'
50 lines.append(line)
51 return lines
52
53 def gen_center_shift_tab(self):
54 lines = []
55 line = '''\
56 /*! \\brief The table maps the slope of an arc to the factors of shifting.
57 *
58 * Every mapped slope is associated with two factors for x and y
59 * axis respective. The are multiplied with length of the arc to
60 * get shifting value in x and y axis direction.
61 */\
62 '''
63 lines.append(line)
64 line = 'int center_shift_tab[SLOPE_TAB_SZ][2] = {'
65 lines.append(line)
66
67 radius = 1 << (self._ref_radius_shift + self._fraction_shift)
68
69 for i in range(self._slope_tab_sz):
70 angle = pi / 4 * i / (self._slope_tab_sz - 1)
71 x = -int(cos(angle) * radius)
72 y = -int(sin(angle) * radius)
73 line = ' {%d, %d},' % (x, y)
74 lines.append(line)
75 pass
76
77 line = ' };'
78 lines.append(line)
79 return lines
80
81 def gen_vector_len_factor_tab(self):
82 lines = []
83 line = '''\
84 /*! \\brief The table maps a slope to a lenght factor for a vector.
85 *
86 * The factor is used to multipled with one of axis values
87 * to get the lenght of the vector.
88 * The range of mapped slopes are 0~(PI/4).
89 */\
90 '''
91 lines.append(line)
92 line = 'int vector_len_factor_tab[SLOPE_TAB_SZ] = {'
93 lines.append(line)
94
95 frac_factor = 1 << self._fraction_shift
96
97 for i in range(self._slope_tab_sz):
98 angle = pi / 4 * i / (self._slope_tab_sz - 1)
99 factor = int((1 / cos(angle)) * frac_factor)
100 line = ' %d,' % (factor)
101 lines.append(line)
102 pass
103
104 line = ' };'
105 lines.append(line)
106 return lines
107
108 def gen_arc_radius_ratio_tab(self):
109 lines = []
110 line = '''\
111 /*! \\brief A table of ratio from an arc to its radius.
112 *
113 * It is to find an index for a given ratio value.
114 */\
115 '''
116 lines.append(line)
117 line = 'int arc_radius_ratio_tab[ARC_RADIUS_RATIO_TAB_SZ] = {'
118 lines.append(line)
119
120 frac_factor = 1 << self._fraction_shift
121
122 for i in range(self._arc_radius_ratio_tab_sz):
123 arc_ratio = 2.0 * i / (self._arc_radius_ratio_tab_sz - 1)
124 arc_ratio = int(arc_ratio * frac_factor)
125 line = ' %d,' % (arc_ratio)
126 lines.append(line)
127 pass
128
129 line = ' };'
130 lines.append(line)
131 return lines
132
133 def gen_arc_radius_factor_tab(self):
134 lines = []
135 line = '''\
136 /*! \\brief The table maps an arc-radius ratio to a distance factor.
137 *
138 * The factor is multiplied with radius to get distance of arc and
139 * center. It is in the order of arc_radius_ratio_tab.
140 */\
141 '''
142 lines.append(line)
143 line = 'int arc_radius_factor_tab[ARC_RADIUS_FACTOR_TAB_SZ] = {'
144 lines.append(line)
145
146 frac_factor = 1 << self._fraction_shift
147
148 for i in range(self._arc_radius_factor_tab_sz):
149 arc = 2.0 * i / (self._arc_radius_factor_tab_sz - 1)
150 factor = int(sqrt(1 - (arc / 2) ** 2) * frac_factor)
151 line = ' %d,' % (factor)
152 lines.append(line)
153 pass
154
155 line = ' };'
156 lines.append(line)
157 return lines
158
159 def gen_sin_tab(self):
160 lines = []
161 line = '/*! \\brief A table of sin() values */'
162 lines.append(line)
163 line = 'int sin_tab[SIN_TAB_SZ] = {'
164 lines.append(line)
165
166 frac_factor = 1 << self._fraction_shift
167
168 for i in range(self._sin_tab_sz):
169 angle = i * pi / 2 / (self._sin_tab_sz - 1)
170 _sin = int(sin(angle) * frac_factor)
171 line = ' %d,' % (_sin)
172 lines.append(line)
173 pass
174
175 line = ' };'
176 lines.append(line)
177 return lines
178
179 def gen_definition(self, out):
180 line = '/* This file is generated by tools/gen_precomputed_tabs.py */'
181 print >> out, line
182 print >> out
183 lines = self.gen_slope_tab()
184 print >> out, '\n'.join(lines)
185 print >> out
186 print >> out
187 lines = self.gen_center_shift_tab()
188 print >> out, '\n'.join(lines)
189 print >> out
190 print >> out
191 lines = self.gen_vector_len_factor_tab()
192 print >> out, '\n'.join(lines)
193 print >> out
194 print >> out
195 lines = self.gen_arc_radius_ratio_tab()
196 print >> out, '\n'.join(lines)
197 print >> out
198 print >> out
199 lines = self.gen_arc_radius_factor_tab()
200 print >> out, '\n'.join(lines)
201 print >> out
202 print >> out
203 lines = self.gen_sin_tab()
204 print >> out, '\n'.join(lines)
205 print >> out
206 pass
207
208 def gen_declaration(self, out):
209 line = '''\
210 #define FRACTION_SHIFT %d
211
212 #define REF_RADIUS_SHIFT %d
213 #define SLOPE_TAB_SZ %d
214 #define ARC_RADIUS_RATIO_TAB_SZ %d
215 #define ARC_RADIUS_FACTOR_TAB_SZ %d
216 #define SIN_TAB_SZ %d
217
218 extern int slope_tab[SLOPE_TAB_SZ];
219 extern int center_shift_tab[SLOPE_TAB_SZ][2];
220 extern int vector_len_factor_tab[SLOPE_TAB_SZ];
221 extern int arc_radius_ratio_tab[ARC_RADIUS_RATIO_TAB_SZ];
222 extern int arc_radius_factor_tab[ARC_RADIUS_FACTOR_TAB_SZ];
223 extern int sin_tab[SIN_TAB_SZ];
224 '''
225 line = line % (self._fraction_shift, self._ref_radius_shift,
226 self._slope_tab_sz, self._arc_radius_ratio_tab_sz,
227 self._arc_radius_factor_tab_sz, self._sin_tab_sz)
228 print >> out, line
229 pass
230 pass
231
232 if __name__ == '__main__':
233 import sys
234
235 def usage(progname):
236 print >> sys.stderr, 'Usage: %s <C file> <header file>' % (progname)
237 sys.exit(255)
238 pass
239
240 if len(sys.argv) != 3:
241 usage(sys.argv[0])
242 pass
243
244 cfile = sys.argv[1]
245 hfile = sys.argv[2]
246
247 gen = tabs_generator()
248
249 cout = file(cfile, 'w+')
250 print >> cout, '#include "%s"' % (hfile)
251 print >> cout
252 gen.gen_definition(cout)
253 cout.close()
254
255 hout = file(hfile, 'w+')
256 sentinel = '__' + hfile.upper().replace('.', '_') + '_'
257 print >> hout, '#ifndef %s' % (sentinel)
258 print >> hout, '#define %s' % (sentinel)
259 print >> hout
260 gen.gen_declaration(hout)
261 print >> hout, '#endif /* %s */' % (sentinel)
262 hout.close()
263 pass