← Back to branch summary

~valavanisalex/ubuntu/oneiric/inkscape/inkscape_0.48.1-2ubuntu5

« back to all changes in this revision

Viewing changes to src/helper/bezier-utils-test.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Wolfram Quester
  • Date: 2004-06-02 10:35:45 UTC
  • Revision ID: james.westby@ubuntu.com-20040602103545-q3x0q6xd2k1yj0fr
Tags: upstream-0.38.1
Import upstream version 0.38.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/helper/bezier-utils-test.cpp
 
1
#include "../utest/utest.h"
 
2
#include <glib.h>
 
3
#include <libnr/nr-macros.h> /* NR_DF_TEST_CLOSE */
 
4
 
 
5
/* mental disclaims all responsibility for this evil idea for testing
 
6
   static functions.  The main disadvantages are that we retain the
 
7
   #define's and `using' directives of the included file. */
 
8
#include "bezier-utils.cpp"
 
9
 
 
10
using NR::Point;
 
11
 
 
12
static bool range_approx_equal(double const a[], double const b[], unsigned len);
 
13
 
 
14
/* (Returns false if NaN encountered.) */
 
15
template<class T>
 
16
static bool range_equal(T const a[], T const b[], unsigned len) {
 
17
    for (unsigned i = 0; i < len; ++i) {
 
18
        if ( a[i] != b[i] ) {
 
19
            return false;
 
20
        }
 
21
    }
 
22
    return true;
 
23
}
 
24
 
 
25
inline bool point_approx_equal(NR::Point const &a, NR::Point const &b, double const eps)
 
26
{
 
27
    using NR::X; using NR::Y;
 
28
    return ( NR_DF_TEST_CLOSE(a[X], b[X], eps) &&
 
29
             NR_DF_TEST_CLOSE(a[Y], b[Y], eps) );
 
30
}
 
31
 
 
32
static inline double square(double const x) {
 
33
    return x * x;
 
34
}
 
35
 
 
36
/** Determine whether the found control points are the same as previously found on some developer's
 
37
    machine.  Doesn't call utest__fail, just writes a message to stdout for diagnostic purposes:
 
38
    the most important test is that the root-mean-square of errors in the estimation are low rather
 
39
    than that the control points found are the same.
 
40
**/
 
41
static void compare_ctlpts(Point const est_b[], Point const exp_est_b[])
 
42
{
 
43
    unsigned diff_mask = 0;
 
44
    for (unsigned i = 0; i < 4; ++i) {
 
45
        for (unsigned d = 0; d < 2; ++d) {
 
46
            if ( fabs( est_b[i][d] - exp_est_b[i][d] ) > 1.1e-5 ) {
 
47
                diff_mask |= 1 << ( i * 2 + d );
 
48
            }
 
49
        }
 
50
    }
 
51
    if ( diff_mask != 0 ) {
 
52
        printf("Warning: got different control points from previously-coded (diffs=0x%x).\n",
 
53
               diff_mask);
 
54
        printf(" Previous:");
 
55
        for (unsigned i = 0; i < 4; ++i) {
 
56
            printf(" (%g, %g)", exp_est_b[i][0], exp_est_b[i][1]);
 
57
        }
 
58
        putchar('\n');
 
59
        printf(" Found:   ");
 
60
        for (unsigned i = 0; i < 4; ++i) {
 
61
            printf(" (%g, %g)", est_b[i][0], est_b[i][1]);
 
62
        }
 
63
        putchar('\n');
 
64
    }
 
65
}
 
66
 
 
67
static void compare_rms(Point const est_b[], double const t[], Point const d[], unsigned const n,
 
68
                        double const exp_rms_error)
 
69
{
 
70
    double sum_errsq = 0.0;
 
71
    for (unsigned i = 0; i < n; ++i) {
 
72
        Point const fit_pt = bezier_pt(3, est_b, t[i]);
 
73
        Point const diff = fit_pt - d[i];
 
74
        sum_errsq += dot(diff, diff);
 
75
    }
 
76
    double const rms_error = sqrt( sum_errsq / n );
 
77
    UTEST_ASSERT( rms_error <= exp_rms_error + 1.1e-6 );
 
78
    if ( rms_error < exp_rms_error - 1.1e-6 ) {
 
79
        /* The fitter code appears to have improved [or the floating point calculations differ
 
80
           on this machine from the machine where exp_rms_error was calculated]. */
 
81
        printf("N.B. rms_error regression requirement can be decreased: have rms_error=%g.\n",
 
82
               rms_error);
 
83
    }
 
84
}
 
85
 
 
86
int main(int argc, char *argv[]) {
 
87
    utest_start("bezier-utils.cpp");
 
88
 
 
89
    UTEST_TEST("copy_without_nans_or_adjacent_duplicates") {
 
90
        NR::Point const src[] = {
 
91
            Point(2., 3.),
 
92
            Point(2., 3.),
 
93
            Point(0., 0.),
 
94
            Point(2., 3.),
 
95
            Point(2., 3.),
 
96
            Point(1., 9.),
 
97
            Point(1., 9.)
 
98
        };
 
99
        Point const exp_dest[] = {
 
100
            Point(2., 3.),
 
101
            Point(0., 0.),
 
102
            Point(2., 3.),
 
103
            Point(1., 9.)
 
104
        };
 
105
        g_assert( G_N_ELEMENTS(src) == 7 );
 
106
        Point dest[7];
 
107
        struct tst {
 
108
            unsigned src_ix0;
 
109
            unsigned src_len;
 
110
            unsigned exp_dest_ix0;
 
111
            unsigned exp_dest_len;
 
112
        } const test_data[] = {
 
113
            /* src start ix, src len, exp_dest start ix, exp dest len */
 
114
            {0, 0, 0, 0},
 
115
            {2, 1, 1, 1},
 
116
            {0, 1, 0, 1},
 
117
            {0, 2, 0, 1},
 
118
            {0, 3, 0, 2},
 
119
            {1, 3, 0, 3},
 
120
            {0, 5, 0, 3},
 
121
            {0, 6, 0, 4},
 
122
            {0, 7, 0, 4}
 
123
        };
 
124
        for (unsigned i = 0 ; i < G_N_ELEMENTS(test_data) ; ++i) {
 
125
            tst const &t = test_data[i];
 
126
            UTEST_ASSERT( t.exp_dest_len
 
127
                          == copy_without_nans_or_adjacent_duplicates(src + t.src_ix0,
 
128
                                                                      t.src_len,
 
129
                                                                      dest) );
 
130
            UTEST_ASSERT(range_equal(dest,
 
131
                                     exp_dest + t.exp_dest_ix0,
 
132
                                     t.exp_dest_len));
 
133
        }
 
134
    }
 
135
 
 
136
    UTEST_TEST("bezier_pt(1)") {
 
137
        Point const a[] = {Point(2.0, 4.0),
 
138
                           Point(1.0, 8.0)};
 
139
        UTEST_ASSERT( bezier_pt(1, a, 0.0) == a[0] );
 
140
        UTEST_ASSERT( bezier_pt(1, a, 1.0) == a[1] );
 
141
        UTEST_ASSERT( bezier_pt(1, a, 0.5) == Point(1.5, 6.0) );
 
142
        double const t[] = {0.5, 0.25, 0.3, 0.6};
 
143
        for (unsigned i = 0; i < G_N_ELEMENTS(t); ++i) {
 
144
            double const ti = t[i], si = 1.0 - ti;
 
145
            UTEST_ASSERT( bezier_pt(1, a, ti) == si * a[0] + ti * a[1] );
 
146
        }
 
147
    }
 
148
 
 
149
    UTEST_TEST("bezier_pt(2)") {
 
150
        Point const b[] = {Point(1.0, 2.0),
 
151
                           Point(8.0, 4.0),
 
152
                           Point(3.0, 1.0)};
 
153
        UTEST_ASSERT( bezier_pt(2, b, 0.0) == b[0] );
 
154
        UTEST_ASSERT( bezier_pt(2, b, 1.0) == b[2] );
 
155
        UTEST_ASSERT( bezier_pt(2, b, 0.5) == Point(5.0, 2.75) );
 
156
        double const t[] = {0.5, 0.25, 0.3, 0.6};
 
157
        for (unsigned i = 0; i < G_N_ELEMENTS(t); ++i) {
 
158
            double const ti = t[i], si = 1.0 - ti;
 
159
            Point const exp_pt( si*si * b[0] + 2*si*ti * b[1] + ti*ti * b[2] );
 
160
            Point const pt(bezier_pt(2, b, ti));
 
161
            UTEST_ASSERT(point_approx_equal(pt, exp_pt, 1e-11));
 
162
        }
 
163
    }
 
164
 
 
165
    Point const c[] = {Point(1.0, 2.0),
 
166
                       Point(8.0, 4.0),
 
167
                       Point(3.0, 1.0),
 
168
                       Point(-2.0, -4.0)};
 
169
    UTEST_TEST("bezier_pt(3)") {
 
170
        UTEST_ASSERT( bezier_pt(3, c, 0.0) == c[0] );
 
171
        UTEST_ASSERT( bezier_pt(3, c, 1.0) == c[3] );
 
172
        UTEST_ASSERT( bezier_pt(3, c, 0.5) == Point(4.0, 13.0/8.0) );
 
173
        double const t[] = {0.5, 0.25, 0.3, 0.6};
 
174
        for (unsigned i = 0; i < G_N_ELEMENTS(t); ++i) {
 
175
            double const ti = t[i], si = 1.0 - ti;
 
176
            UTEST_ASSERT( LInfty( bezier_pt(3, c, ti)
 
177
                                  - ( si*si*si * c[0] +
 
178
                                      3*si*si*ti * c[1] +
 
179
                                      3*si*ti*ti * c[2] +
 
180
                                      ti*ti*ti * c[3] ) )
 
181
                          < 1e-4 );
 
182
        }
 
183
    }
 
184
 
 
185
    struct Err_tst {
 
186
        Point pt;
 
187
        double u;
 
188
        double err;
 
189
    } const err_tst[] = {
 
190
        {c[0], 0.0, 0.0},
 
191
        {Point(4.0, 13.0/8.0), 0.5, 0.0},
 
192
        {Point(4.0, 2.0), 0.5, 9.0/64.0},
 
193
        {Point(3.0, 2.0), 0.5, 1.0 + 9.0/64.0},
 
194
        {Point(6.0, 2.0), 0.5, 4.0 + 9.0/64.0},
 
195
        {c[3], 1.0, 0.0},
 
196
    };
 
197
    UTEST_TEST("compute_error") {
 
198
        for (unsigned i = 0; i < G_N_ELEMENTS(err_tst); ++i) {
 
199
            Err_tst const &t = err_tst[i];
 
200
            UTEST_ASSERT( compute_error(t.pt, t.u, c) == t.err );
 
201
        }
 
202
    }
 
203
 
 
204
    UTEST_TEST("compute_max_error") {
 
205
        Point d[G_N_ELEMENTS(err_tst)];
 
206
        double u[G_N_ELEMENTS(err_tst)];
 
207
        for (unsigned i = 0; i < G_N_ELEMENTS(err_tst); ++i) {
 
208
            Err_tst const &t = err_tst[i];
 
209
            d[i] = t.pt;
 
210
            u[i] = t.u;
 
211
        }
 
212
        g_assert( G_N_ELEMENTS(u) == G_N_ELEMENTS(d) );
 
213
        unsigned max_ix = ~0u;
 
214
 
 
215
        UTEST_ASSERT( err_tst[4].err == compute_max_error(d, u, G_N_ELEMENTS(d), c, &max_ix) );
 
216
        UTEST_ASSERT( max_ix == 4 );
 
217
    }
 
218
 
 
219
    UTEST_TEST("chord_length_parameterize") {
 
220
        /* n == 2 */
 
221
        {
 
222
            Point const d[] = {Point(2.9415, -5.8149),
 
223
                               Point(23.021, 4.9814)};
 
224
            double u[G_N_ELEMENTS(d)];
 
225
            double const exp_u[] = {0.0, 1.0};
 
226
            g_assert( G_N_ELEMENTS(u) == G_N_ELEMENTS(exp_u) );
 
227
            chord_length_parameterize(d, u, G_N_ELEMENTS(d));
 
228
            UTEST_ASSERT(range_equal(u, exp_u, G_N_ELEMENTS(exp_u)));
 
229
        }
 
230
 
 
231
        /* Straight line. */
 
232
        {
 
233
            double const exp_u[] = {0.0, 0.1829, 0.2105, 0.2105, 0.619, 0.815, 0.999, 1.0};
 
234
            unsigned const n = G_N_ELEMENTS(exp_u);
 
235
            Point d[n];
 
236
            double u[n];
 
237
            Point const a(-23.985, 4.915), b(4.9127, 5.203);
 
238
            for (unsigned i = 0; i < n; ++i) {
 
239
                double bi = exp_u[i], ai = 1.0 - bi;
 
240
                d[i] = ai * a  +  bi * b;
 
241
            }
 
242
            chord_length_parameterize(d, u, n);
 
243
            UTEST_ASSERT(range_approx_equal(u, exp_u, n));
 
244
        }
 
245
    }
 
246
 
 
247
    /* Feed it some points that can be fit exactly with a single bezier segment, and see how
 
248
       well it manages. */
 
249
    Point const src_b[4] = {Point(5., -3.),
 
250
                            Point(8., 0.),
 
251
                            Point(4., 2.),
 
252
                            Point(3., 3.)};
 
253
    double const t[] = {0.0, .001, .03, .05, .09, .13, .18, .25, .29, .33, .39, .44,
 
254
                        .51, .57, .62, .69, .75, .81, .91, .93, .97, .98, .999, 1.0};
 
255
    unsigned const n = G_N_ELEMENTS(t);
 
256
    Point d[n];
 
257
    for (unsigned i = 0; i < n; ++i) {
 
258
        d[i] = bezier_pt(3, src_b, t[i]);
 
259
    }
 
260
    Point const tHat1(unit_vector( src_b[1] - src_b[0] ));
 
261
    Point const tHat2(unit_vector( src_b[2] - src_b[3] ));
 
262
 
 
263
    UTEST_TEST("generate_bezier") {
 
264
        Point est_b[4];
 
265
        generate_bezier(est_b, d, t, n, tHat1, tHat2);
 
266
 
 
267
        compare_ctlpts(est_b, src_b);
 
268
 
 
269
        /* We're being unfair here in using our t[] rather than best t[] for est_b: we
 
270
           over-estimate RMS of errors. */
 
271
        compare_rms(est_b, t, d, n, 1e-8);
 
272
    }
 
273
 
 
274
    UTEST_TEST("sp_bezier_fit_cubic_full") {
 
275
        Point est_b[4];
 
276
        gint const succ = sp_bezier_fit_cubic_full(est_b, d, n, tHat1, tHat2, square(1.2), 1);
 
277
        UTEST_ASSERT( succ == 1 );
 
278
 
 
279
        Point const exp_est_b[4] = {
 
280
            Point(5.000000, -3.000000),
 
281
            Point(7.5753, -0.4247),
 
282
            Point(4.77533, 1.22467),
 
283
            Point(3, 3)
 
284
        };
 
285
        compare_ctlpts(est_b, exp_est_b);
 
286
 
 
287
        /* We're being unfair here in using our t[] rather than best t[] for est_b: we
 
288
           over-estimate RMS of errors. */
 
289
        compare_rms(est_b, t, d, n, .307911);
 
290
    }
 
291
 
 
292
    UTEST_TEST("sp_bezier_fit_cubic") {
 
293
        Point est_b[4];
 
294
        gint const succ = sp_bezier_fit_cubic(est_b, d, n, square(1.2));
 
295
        UTEST_ASSERT( succ == 1 );
 
296
 
 
297
        Point const exp_est_b[4] = {
 
298
            Point(5.000000, -3.000000),
 
299
            Point(7.57134, -0.423509),
 
300
            Point(4.77929, 1.22426),
 
301
            Point(3, 3)
 
302
        };
 
303
        compare_ctlpts(est_b, exp_est_b);
 
304
 
 
305
        /* We're being unfair here in using our t[] rather than best t[] for est_b: we
 
306
           over-estimate RMS of errors. */
 
307
        compare_rms(est_b, t, d, n, .307983);
 
308
    }
 
309
 
 
310
    return !utest_end();
 
311
}
 
312
 
 
313
/* (Returns false if NaN encountered.) */
 
314
static bool range_approx_equal(double const a[], double const b[], unsigned const len) {
 
315
    for (unsigned i = 0; i < len; ++i) {
 
316
        if (!( fabs( a[i] - b[i] ) < 1e-4 )) {
 
317
            return false;
 
318
        }
 
319
    }
 
320
    return true;
 
321
}
 
322
 
 
323
/*
 
324
  Local Variables:
 
325
  mode:c++
 
326
  c-file-style:"stroustrup"
 
327
  c-file-offsets:((innamespace . 0)(inline-open . 0))
 
328
  indent-tabs-mode:nil
 
329
  fill-column:99
 
330
  End:
 
331
*/
 
332
// vim: filetype=c++:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :