1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
/* This file is part of the GNU plotutils package. Copyright (C) 1995,
1996, 1997, 1998, 1999, 2000, 2005, 2008, Free Software Foundation, Inc.
The GNU plotutils package is free software. You may redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software foundation; either version 2, or (at your
option) any later version.
The GNU plotutils package is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License along
with the GNU plotutils package; see the file COPYING. If not, write to
the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor,
Boston, MA 02110-1301, USA. */
/* Lookup table listing relative chordal deviation, i.e. the factor
(chordal deviation)/(chord length), for binary subdivisions of the arc
sizes we support.
The symbolic names for these arc sizes, e.g. QUARTER_ARC and
THREE_QUARTER_ARC, are defined in extern.h. The constant
MAX_ARC_SUBDIVISIONS, which can in principle be device dependent, is
also defined there. It should be no greater than
TABULATED_ARC_SUBDIVISIONS, the length of each entry in the lookup
table.
The formula
relative_deviation = (1 - cos (theta/2)) / (2 * sin (theta/2)),
where theta = subtended angle, was used to compute the numbers in the
lookup tables. The formula is justified as follows. Let
s = chordal deviation / radius (so that 0 <= s <= 2)
h = half chord length / radius.
Then by elementary trigonometry, s = 1 - cos(theta/2) and
h = sin(theta/2), where theta = angle subtended by the chord. Since
the relative chordal deviation is s/2h, this justifies the formula.
Incidentally, h = sqrt(s * (2-s))), irrespective of theta.
There is an alternative derivation of the numbers in these tables,
tail-recursive and elegant, which uses only sqrt(). Let s' and h' be
the values of s and h when the arc is bisected, i.e. theta is divided by
two. Using half-angle formulae it is easy to check that
s' = 1 - sqrt (1 - s / 2)
h' = h / 2 (1 - s')
(The first of these formulae is well-known; see the article of Ken
Turkowski <turk@apple.com> in Graphics Gems V, where he approximates the
right-hand side by s/4.) So the pair (s',h') may be computed from the
pair (s,h). By updating (s,h) with every bisection, one can generate a
table of successive values of the quotient s/2h, i.e. the relative
chordal deviation.
*/
/* Maximum number of times a circular or elliptic arc is recursively
subdivided, when it is being approximated by an inscribed polyline. The
polyline will contain no more than 2**MAX_ARC_SUBDIVISIONS line
segments. MAX_ARC_SUBDIVISIONS must be no larger than
TABULATED_ARC_SUBDIVISIONS below (the size of the tables in g_arc.h). */
#define MAX_ARC_SUBDIVISIONS 5 /* to avoid buffer overflow on HP7550[A|B] */
#define TABULATED_ARC_SUBDIVISIONS 15 /* length of each table entry */
/* Types of circular/elliptic arc. These index into the doubly indexed
table of `relative chordal deviations' below. */
#define NUM_ARC_TYPES 3
#define QUARTER_ARC 0
#define HALF_ARC 1
#define THREE_QUARTER_ARC 2
#define USER_DEFINED_ARC -1 /* does not index into table */
static const double _chord_table[NUM_ARC_TYPES][TABULATED_ARC_SUBDIVISIONS] =
{
{ /* Quarter Arc */
0.20710678, /* for arc subtending 90 degrees */
0.099456184, /* for arc subtending 45 degrees */
0.049245702, /* for arc subtending 22.5 degrees */
0.024563425, /* for arc subtending 11.25 degrees */
0.012274311, /* etc. */
0.0061362312,
0.0030680001,
0.0015339856,
0.000766991,
0.00038349527,
0.00019174761,
9.58738e-05,
4.79369e-05,
2.396845e-05,
1.1984225e-05
},
{ /* Half Arc */
0.5, /* for arc subtending 180 degrees */
0.20710678, /* for arc subtending 90 degrees */
0.099456184, /* for arc subtending 45 degrees */
0.049245702, /* for arc subtending 22.5 degrees */
0.024563425, /* for arc subtending 11.25 degrees */
0.012274311, /* etc. */
0.0061362312,
0.0030680001,
0.0015339856,
0.000766991,
0.00038349527,
0.00019174761,
9.58738e-05,
4.79369e-05,
2.396845e-05
},
{ /* Three Quarter Arc */
1.2071068, /* for arc subtending 270 degrees */
0.33408932, /* for arc subtending 135 degrees */
0.15167334, /* for arc subtending 67.5 degrees */
0.074167994, /* for arc subtending 33.75 degrees */
0.036882216, /* etc. */
0.01841609,
0.0092049244,
0.0046020723,
0.0023009874,
0.0011504876,
0.00057524305,
0.00028762143,
0.0001438107,
7.190535e-05,
3.5952675e-05
}
};
|
