Repository navigation
Expand file tree
/
Copy path11-fitting.html
More file actions
275 lines (262 loc) · 18.2 KB
/
Copy path11-fitting.html
File metadata and controls
275 lines (262 loc) · 18.2 KB
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Curve fitting — inkvec</title>
<link rel="stylesheet" href="assets/doc.css">
</head>
<body>
<div class="wrap">
<header class="masthead">
<p class="eyebrow">Stage 11 of 16</p>
<h1>Choosing the fewest shapes that still tell the truth</h1>
<p class="standfirst">A boundary arrives as hundreds of measured points, each with its
own honest uncertainty. This stage decides how to draw it — straight lines, curves, or
arcs — using as few of them as the measurement allows, and not one fewer.</p>
<p class="pairlink">Technical reference: <a href="11-fitting.md">11-fitting.md</a></p>
</header>
<main>
<section>
<h2>The problem with "trace every point"</h2>
<p>The most literal way to redraw a boundary is to visit every point the earlier
stages measured and connect them with straight lines. That produces a shape made of
hundreds of tiny segments — technically accurate, and useless. Every jitter in the
original measurement becomes a visible kink. A circle drawn this way is not a circle;
it is a many-sided polygon wearing a circle's outline.</p>
<p>The opposite mistake is just as real. Describe the same boundary with too few
shapes — one long curve standing in for what was actually three — and the drawing
drifts visibly away from the true edge. Too many shapes wastes effort recording noise.
Too few loses the picture. This stage finds the point in between: the fewest shapes
that still explain what was actually measured.</p>
<figure>
<svg viewBox="0 0 640 260" role="img" aria-label="The same curved boundary described three ways: too many segments, too few, and the optimum">
<text x="20" y="22" class="fig-label-strong">The same edge, described three ways</text>
<g transform="translate(20,40)">
<text x="0" y="0" class="fig-label">Too many shapes — chases every wobble</text>
<polyline points="0,60 8,52 15,49 24,44 34,42 45,40 58,39 70,41 82,45 92,50 100,57 106,64 108,72 106,80 100,87 90,92 78,95 64,96 50,95 38,92 26,87 16,80 8,72 3,63 0,60"
fill="none" class="fig-accent-stroke" stroke-width="1.5"/>
<text x="130" y="65" class="fig-label">every jitter becomes a corner</text>
</g>
<g transform="translate(220,40)">
<text x="0" y="0" class="fig-label">Too few shapes — misses the shape</text>
<ellipse cx="55" cy="68" rx="30" ry="20" fill="none" class="fig-accent-stroke" stroke-width="1.5"/>
<path d="M 25,55 Q 55,20 90,55" fill="none" stroke="var(--ink-faint)" stroke-width="1.2" stroke-dasharray="3 3"/>
<text x="130" y="65" class="fig-label">the true bulge is gone</text>
</g>
<g transform="translate(420,40)">
<text x="0" y="0" class="fig-label">The optimum — as few as it can afford</text>
<path d="M 25,68 C 25,48 40,38 55,38 C 70,38 85,48 85,68 C 85,88 70,98 55,98 C 40,98 25,88 25,68 Z"
fill="none" class="fig-accent-stroke" stroke-width="1.8"/>
<circle cx="25" cy="68" r="2.5" class="fig-accent"/>
<circle cx="55" cy="38" r="2.5" class="fig-accent"/>
<circle cx="85" cy="68" r="2.5" class="fig-accent"/>
<circle cx="55" cy="98" r="2.5" class="fig-accent"/>
<text x="130" y="65" class="fig-label">four points, smooth curves</text>
</g>
<text x="20" y="230" class="fig-label" fill="var(--ink-soft)">Each dot in the third panel is a
deliberate decision. Nothing is left to the shape of the noise.</text>
</svg>
<figcaption>The first panel is faithful to the noise. The second is faithful to
nothing. The third is faithful to the boundary, at the smallest cost in numbers.
</figcaption>
</figure>
</section>
<section>
<h2>A single rule that trades honesty for economy</h2>
<p>Every candidate description — a line here, a curve there, a break at this point or
that one — is priced by one rule: how well it matches what was measured, plus a fixed
charge for every number it takes to write down. A description that matches slightly
worse but needs six fewer numbers can still win, if the six numbers cost more than the
small mismatch is worth. A description that matches almost perfectly but needs twenty
extra numbers to do it usually loses.</p>
<p>This is the same idea as writing a good summary of a long report. A summary that
keeps every sentence is not a summary. A summary that drops the argument to save a
paragraph is not faithful. The useful summary sits between the two, and the test for
where to stop is whether the next sentence you could add is worth the space it takes.
This stage runs that test formally, on every possible boundary and every possible
shape, rather than by feel.</p>
<div class="aside">The charge per number is not picked by taste. It comes from how big
the picture is and how precisely coordinates will eventually be written — a
calculation the code does once, honestly, rather than a knob someone tunes until the
picture looks right.</div>
</section>
<section>
<h2>The most surprising fact in this stage</h2>
<p>It would be reasonable to expect that charge-per-number to be a sensitive knob —
turn it up, get a much simpler drawing; turn it down, get a much more detailed one.
It is not. The charge enters the trade-off under a square root, and the charge itself
is a logarithm of image size divided by output precision. Two dampening effects,
stacked.</p>
<p>Concretely: doubling the charge per number widens how far a curve is allowed to
drift from the measured points by only about 41%, not 100%. And getting the charge to
double in the first place needs the image to become ten times bigger, or the output
precision to become ten times finer. Put together, changing the output precision by a
factor of ten moves the actual shape of the drawing by only about 13%.</p>
<p>That is the opposite of what a "quality knob" is supposed to do, and it is
deliberate rather than accidental — a genuine measurement of how flat this trade-off
is was made on the real corpus, and it stayed flat across a wide range of settings
that looked, on paper, very different. The two real levers this stage has are how
precisely each point was actually measured — inherited from earlier stages, not set
here — and the fixed price of each kind of shape in the alphabet. Turning the
headline knob is close to turning nothing at all.</p>
<figure>
<svg viewBox="0 0 640 190" role="img" aria-label="A square root dampens how much the number-charge affects the curve; a tenfold change in precision moves the shape by about thirteen percent">
<text x="20" y="22" class="fig-label-strong">Why the knob barely turns anything</text>
<g transform="translate(30,50)">
<text x="0" y="0" class="fig-label">precision changes 10x</text>
<rect x="0" y="10" width="140" height="14" fill="var(--copper-soft)"/>
<rect x="0" y="10" width="140" height="14" fill="none" stroke="var(--rule)"/>
<text x="150" y="21" class="fig-label">full swing</text>
</g>
<g transform="translate(30,90)">
<text x="0" y="0" class="fig-label">-> the charge per number changes ~2.3x (a logarithm)</text>
<rect x="0" y="10" width="60" height="14" fill="var(--copper-soft)"/>
<rect x="0" y="10" width="140" height="14" fill="none" stroke="var(--rule)" stroke-dasharray="2 2"/>
<text x="150" y="21" class="fig-label">already much less</text>
</g>
<g transform="translate(30,130)">
<text x="0" y="0" class="fig-label">-> the drawing itself changes ~13% (a square root on top)</text>
<rect x="0" y="10" width="18" height="14" class="fig-accent"/>
<rect x="0" y="10" width="140" height="14" fill="none" stroke="var(--rule)" stroke-dasharray="2 2"/>
<text x="150" y="21" class="fig-label" fill="var(--copper)">what you actually see</text>
</g>
</svg>
<figcaption>Two separate dampening effects — a logarithm, then a square root — sit
between the setting a person turns and the shape they see change.</figcaption>
</figure>
</section>
<section>
<h2>Searching every possible place to break the line</h2>
<p>Deciding where to put the joins between shapes is not a matter of eyeballing corners.
The method considers every possible split of the boundary into pieces, and for every
piece, every shape in the alphabet that could describe it, and finds the single
combination that adds up to the lowest total price. This sounds like it should be
catastrophically slow — checking every combination of every split — but the trick is
that the best way to reach any given point on the boundary only ever depends on the
best way to reach some earlier point, never on guessing the whole path at once. That
lets the search build its answer forward, point by point, keeping only the best route
to each point rather than re-exploring the world from the start every time.</p>
<p>This is checked, not just argued: an independent brute-force search that genuinely
tries every combination is run on hundreds of small test shapes, and its answer is
required to match the fast method's answer, on the nose, every time.</p>
</section>
<section>
<h2>What the alphabet contains, and what each letter costs</h2>
<p>A straight line is the cheapest shape — two numbers, an endpoint. A smooth curve
costs six numbers — two control handles plus an endpoint — because it can bend in
ways a line cannot. A circular arc sits in between at five numbers, and it earns its
place honestly: many real logos and icons are drawn from actual circles, and an arc
describes that shape exactly, at less cost than the curve that would otherwise be
needed to approximate it.</p>
<p>Five is a judgement, not a count: the file itself spells an arc out in seven numbers
(two radii, a rotation, two yes-or-no flags and an endpoint), and the benchmark counts
seven. Charging the seven was tried. About half the arcs then become curves or lines,
and the test icons needed about 1.4 % fewer numbers at 512 px with the colour unchanged
on average, provided a single curve is not allowed to stand in for more than a quarter
of a circle (past that it visibly misses it) and each number is spent a little more
freely. But on a second, held-back set of icons the colour got worse, and a few corners
came back as spikes, so the tracer still charges five; the experiment is kept in the
code, switched off.</p>
<p>Lines alone hit a wall no amount of clever placement can fix. Approximating a circle
with straight chords needs dozens of short segments to stay accurate; four well-placed
curves do the same job to a fraction of a percent of error. So the alphabet has to
include curves and arcs, not because lines are wrong, but because some shapes simply
cannot be told cheaply in a language that only has straight lines.</p>
<div class="aside">One curious refinement: when a stretch of straight-seeming boundary
turns out to fit a circle four times better than it fits a line, that consistent bulge
is itself treated as evidence against the line — even before the circle wins outright.
A boundary that leans the same way, point after point, is not behaving like noise.</div>
</section>
<section>
<h2>Corners are not where the measurement puts them</h2>
<p>A camera, or a rendering engine, cannot draw an infinitely sharp corner — it always
rounds the very tip off by a pixel or so, the same way a photograph of a sharp table
edge shows a hint of blur right at the point. Trusting the measured point at a corner
literally would draw every corner very slightly rounded, and would waste an extra
shape bridging the rounding on the way there.</p>
<p>The fix is to find where the two straight edges either side of a corner actually
meet, algebraically, rather than trust the rounded sample sitting between them — but
only where there is genuinely a corner to find. Trying this on a smooth curve, where
two neighbouring pieces are nearly parallel, is like trying to find where two nearly
parallel roads on a map cross: the answer exists on paper but can be miles from
either road. So the correction only fires where two pieces meet at a real angle, and
even then, only up to a distance the measurement's own honesty allows — never further
than the corner could plausibly have been rounded by the rendering process that
produced it in the first place.</p>
</section>
<section>
<h2>Passes that clean up afterwards, on by default and off by default</h2>
<p>Two small tidy-up passes run automatically after every fit: rejoining a short run of
segments into one smooth curve when a corner's rigid geometry made it look artificially
expensive, and replacing a curve that is really just the camera's rounding of a corner
with the sharp corner it stands in for.</p>
<p>The first of these is where most of the fitting time used to go. For each short run it
searches for the single curve that fits best: about two thousand rough candidates
first, then a fine search from the most promising one, each candidate measured against
every point of the run. Almost all of those candidates lose, so since October 2026 a
candidate is first checked with a cheaper quantity that is provably never larger than
its real misfit, and only a candidate that survives that check is measured exactly.
The rough candidates also share most of their arithmetic, which is now done once and
reused. Neither change alters a single number in the output; the drawing is the same
to the last bit, it just arrives sooner.</p>
<p>A third pass moves the joins between curves to where a designer would put them. Type
designers and icon artists place a curve's points at its top, bottom, left and right,
where the curve runs exactly horizontal or vertical, so that every handle an editor
shows there points straight along an axis; Adobe's specification for its fonts has
asked for this since 1990. The fitter had no reason to: it puts a join wherever a
measured point happens to lie, and moving a join along a smooth curve hardly changes
the drawing. The pass offers, for every smooth stretch, the same stretch with its joins
at those extreme points and every join smooth, and keeps it only where the fitter's
own measure of fit and economy prefers it. A join at an extreme point is credited for
the one number it no longer has to write: its direction. On the 246 test icons this
moved the trace closer to the artists' files on the gate's own measures (see the
reference document), without writing a single number more or fewer.</p>
<p>Two more exist in the code but are built only into research versions of the program,
never into a release. One would snap a line to be perfectly horizontal or vertical
when the measurement genuinely cannot tell it apart from one — real drawings do this
constantly, and the evidence for it is strong, but turning it on made almost no
measurable difference to the finished picture. The other would rewrite two
neighbouring curves to share a handle exactly, the shorthand professional design
tools write automatically — again, well-supported by how real artwork looks, and
again, not worth it on the measurements.</p>
</section>
<section>
<h2>A whole circle, or a run of curves?</h2>
<p>Every boundary is also offered as one whole shape: a circle, an ellipse, a rectangle
with or without rounded corners, or a run of circular arcs. Both descriptions are
priced by the same rule, and the cheaper one is written. A boundary that really is a
circle comes back as three numbers rather than four curves; one that only looks
roughly round keeps its curves. This choice is worth a lot: taking the whole-shape
option away makes the traced files carry about 30% more numbers.</p>
<p>The image's own border is the commonest whole shape of all — on most icons the
background touches every edge, and its boundary is the frame of the picture. The
rectangle won that contest every single time it was measured, so the frame is now
tried as a rectangle first, and when the rectangle is cheaper than any curve could
possibly be, the curve search is not run at all. On every other boundary the curve
search and the whole-shape search run at the same time on different processor cores.
Both shortcuts give exactly the answer the full comparison would have.</p>
</section>
</main>
<nav class="stages">
<a href="00-overview.html">Overview</a>
<a href="01-intake.html">1 Intake</a>
<a href="02-coverage.html">2 Coverage</a>
<a href="03-palette.html">3 Palette</a>
<a href="04-regions.html">4 Regions</a>
<a href="05-gradients.html">5 Gradients</a>
<a href="06-planar-map.html">6 Planar map</a>
<a href="07-subpixel.html">7 Sub-pixel</a>
<a href="08-boundary-solve.html">8 Boundary solve</a>
<a href="09-decode.html">9 Decode</a>
<a href="10-symmetry.html">10 Symmetry</a>
<a href="11-fitting.html" aria-current="page">11 Curve fitting</a>
<a href="12-repair.html">12 Repair</a>
<a href="13-emit.html">13 Emit</a>
<a href="14-fast-mode.html">14 Fast mode</a>
<a href="15-strokes.html">15 Strokes</a>
<a href="constants.md">Constants</a>
</nav>
</div>
</body>
</html>