Ansel 0.0
A darktable fork - bloat + design vision
Loading...
Searching...
No Matches
masks_solid.c
Go to the documentation of this file.
1/*
2 This file is part of Ansel,
3 Copyright (C) 2026 Guillaume Stutin.
4
5 Ansel is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
9
10 Ansel is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with Ansel. If not, see <http://www.gnu.org/licenses/>.
17*/
18
19/* The edge of a stroke's solid part.
20 *
21 * A brush is painted as spokes, each solid from its spine sample to its edge sample, on the envelope
22 * of the stroke's solid discs. That envelope folds back where the stroke turns, and where the solid
23 * radius changes faster than the spine runs the discs nest and the spokes lie along the spine, so
24 * the line through the edge samples is not the union's edge. The union is filled instead and its
25 * edge traced: a boundary pass over the edge samples costs as much and keeps folds inside.
26 *
27 * The bands (c_k, f_k, f_k+1, c_k+1) between neighbouring spokes are grouped into runs of one
28 * orientation, each run a polygon -- spine forward, contour back -- wound positively, so the
29 * union is where the winding is not zero. It is filled a few sub-scanlines per cell row with exact
30 * crossings, the cells the spine crosses are set full, and its edge followed loop by loop by
31 * marching squares at half coverage. */
32
34#include "develop/masks_gui.h"
36#include "system/mem_alloc.h"
37#include "common/logging.h"
38#include "common/times.h"
39
40#include <float.h>
41#include <math.h>
42#include <stdint.h>
43#include <stdlib.h>
44#include <string.h>
45
46// Sub-scanlines per cell row: the half-coverage level lands within an eighth of a cell.
47#define SOLID_SUBLINES 4
48// The most cells the grid holds and crossings the fill stores; past either, the cells grow.
49#define SOLID_MAX_CELLS ((size_t)8 << 20)
50#define SOLID_MAX_CROSSINGS ((size_t)32 << 20)
51// How far, in cells, a run's bands sweep back before the run turns over.
52#define SOLID_DRIFT 0.1f
53// Up to this many crossings, a sub-scanline is sorted by insertion.
54#define SOLID_INSERTION 32
55
56enum { SOLID_TOP = 0, SOLID_RIGHT = 1, SOLID_BOTTOM = 2, SOLID_LEFT = 3 };
57
58typedef struct _solid_edge_t
59{
60 float x; // upper end, image pixels
61 float y;
62 float y_end; // lower end
63 float slope; // dx / dy
64 int dir; // winding, +1 or -1
66
67typedef struct _solid_crossing_t
68{
69 float x; // cells
70 int dir;
72
73typedef struct _solid_bands_t
74{
75 const float *spine; // samples, the header skipped
76 const float *contour; // index-aligned with spine
77 int n; // samples
78 int count; // bands: n when the walk closes, n - 1 otherwise
79 float cell; // image pixels
81
82typedef struct _solid_grid_t
83{
84 float x0; // image position of the grid's corner
85 float y0;
86 float cell; // a cell's side, image pixels
87 int w;
88 int h;
90
91/* Where band k's two spokes cross, if they do, as the fraction @p t of the first: such a band is a
92 * bow tie, its two lobes wound opposite ways. */
93static inline gboolean _solid_spokes_cross(const _solid_bands_t *const b, const int k, const int l, float *const t)
94{
95 const float *const c0 = b->spine + 2 * k;
96 const float *const c1 = b->spine + 2 * l;
97 const float ax = b->contour[2 * k] - c0[0];
98 const float ay = b->contour[2 * k + 1] - c0[1];
99 const float bx = b->contour[2 * l] - c1[0];
100 const float by = b->contour[2 * l + 1] - c1[1];
101 const float wx = c1[0] - c0[0];
102 const float wy = c1[1] - c0[1];
103 const float den = ax * by - ay * bx;
104 if(den == 0.0f) return FALSE;
105 *t = (wx * by - wy * bx) / den;
106 const float u = (wx * ay - wy * ax) / den;
107 return *t > 0.0f && *t < 1.0f && u > 0.0f && u < 1.0f;
108}
109
110/* Each band's orientation, +1 or -1, or 0 for a band skipped -- one with a vertex that is not
111 * finite, which cuts the run. The sign is the area's, taken about the band's own spine sample: about
112 * the origin, thousands of pixels out, float cancellation decides it. A run begins once its bands
113 * have swept SOLID_DRIFT of a cell one way, as width, area over perimeter, summed over them all:
114 * where the border moves fast the spine is sampled a fiftieth of a pixel apart, and no one band is
115 * wide enough to tell. It turns over only once its bands have swept back as far: a long spoke
116 * trembling by a hundredth of a pixel would turn it at every band, and every turn adds that spoke to
117 * the fill. Extends @p bbox by every band kept and counts the bow ties among them into @p twisted;
118 * returns how many runs. */
119static int _solid_band_signs(const _solid_bands_t *const b, int8_t *const sign, float bbox[4], int *const twisted)
120{
121 const float *const spine = b->spine;
122 const float *const contour = b->contour;
123 const int n = b->n;
124 const float drift_max = SOLID_DRIFT * b->cell;
125 int runs = 0;
126 int8_t current = 0;
127 float drift = 0.0f;
128 float swept = 0.0f; // before a run begins, how far its bands have swept
129 int pending = 0; // and the first of them
130 for(int k = 0; k < b->count; k++)
131 {
132 const int l = (k + 1) % n;
133 const float cx = spine[2 * k];
134 const float cy = spine[2 * k + 1];
135 const float f0x = contour[2 * k] - cx;
136 const float f0y = contour[2 * k + 1] - cy;
137 const float f1x = contour[2 * l] - cx;
138 const float f1y = contour[2 * l + 1] - cy;
139 const float c1x = spine[2 * l] - cx;
140 const float c1y = spine[2 * l + 1] - cy;
141 const float area2 = (f0x * f1y - f1x * f0y) + (f1x * c1y - c1x * f1y);
142 const float perimeter = fabsf(f0x) + fabsf(f0y) + fabsf(f1x - f0x) + fabsf(f1y - f0y) + fabsf(f1x - c1x)
143 + fabsf(f1y - c1y) + fabsf(c1x) + fabsf(c1y);
144 const float width = area2 / fmaxf(perimeter, FLT_MIN);
145 if(!isfinite(width))
146 {
147 current = 0;
148 swept = 0.0f;
149 pending = k + 1;
150 }
151 else if(current == 0)
152 {
153 swept += width;
154 if(fabsf(swept) > drift_max)
155 {
156 // the run takes the bands that swept it in
157 current = (swept > 0.0f) ? 1 : -1;
158 drift = 0.0f;
159 runs++;
160 for(int j = pending; j < k; j++) sign[j] = current;
161 }
162 }
163 else
164 {
165 // only a band against the run sweeps it back, so it turns to that band's way
166 drift = fmaxf(0.0f, drift - current * width);
167 if(drift > drift_max)
168 {
169 current = -current;
170 drift = 0.0f;
171 runs++;
172 }
173 }
174 sign[k] = current;
175 }
176
177 *twisted = 0;
178 for(int k = 0; k < b->count; k++)
179 {
180 if(sign[k] == 0) continue;
181 const int l = (k + 1) % n;
182 float t = 0.0f;
183 *twisted += _solid_spokes_cross(b, k, l, &t);
184 const int ends[2] = { k, l };
185 for(int q = 0; q < 2; q++)
186 {
187 const int s = ends[q];
188 bbox[0] = fminf(bbox[0], fminf(spine[2 * s], contour[2 * s]));
189 bbox[1] = fmaxf(bbox[1], fmaxf(spine[2 * s], contour[2 * s]));
190 bbox[2] = fminf(bbox[2], fminf(spine[2 * s + 1], contour[2 * s + 1]));
191 bbox[3] = fmaxf(bbox[3], fmaxf(spine[2 * s + 1], contour[2 * s + 1]));
192 }
193 }
194 return runs;
195}
196
197static int _solid_add_edge(_solid_edge_t *const e, const float xa, const float ya, const float xb,
198 const float yb, const int winding)
199{
200 if(ya == yb) return 0;
201 const gboolean down = ya < yb;
202 e->x = down ? xa : xb;
203 e->y = down ? ya : yb;
204 e->y_end = down ? yb : ya;
205 e->slope = (xb - xa) / (yb - ya);
206 e->dir = down ? winding : -winding;
207 return 1;
208}
209
210/* A bow tie's lobe wound against its run counts -1 where the run counts +1, and cancels a band it
211 * lies on: a hole in the solid part. That lobe is added again the other way, twice. A run walks a
212 * band c0, c1, f1, f0; its lobes are (c0, c1, X) and (X, f1, f0), X where the spokes cross.
213 * Returns how many edges. */
214static int _solid_untwist(const _solid_bands_t *const b, const int k, const int l, const float t, const int s,
215 _solid_edge_t *const edges)
216{
217 const float *const c0 = b->spine + 2 * k;
218 const float *const c1 = b->spine + 2 * l;
219 const float *const f0 = b->contour + 2 * k;
220 const float *const f1 = b->contour + 2 * l;
221 const float x = c0[0] + t * (f0[0] - c0[0]);
222 const float y = c0[1] + t * (f0[1] - c0[1]);
223 // The spine's lobe as the band's own area counts it (c0, X, c1): against the run when its sign is
224 // not s. Either lobe is then walked v1, v2, X.
225 const float spine_lobe = (x - c0[0]) * (c1[1] - c0[1]) - (y - c0[1]) * (c1[0] - c0[0]);
226 const gboolean spine_side = (spine_lobe > 0.0f) != (s > 0);
227 const float *const v1 = spine_side ? c0 : f1;
228 const float *const v2 = spine_side ? c1 : f0;
229 int count = _solid_add_edge(edges, v1[0], v1[1], v2[0], v2[1], -2 * s);
230 count += _solid_add_edge(edges + count, v2[0], v2[1], x, y, -2 * s);
231 count += _solid_add_edge(edges + count, x, y, v1[0], v1[1], -2 * s);
232 return count;
233}
234
235/* The runs' polygons as one edge list: the order of the edges is irrelevant to a winding count,
236 * so each band adds its spine and contour edges as it comes, each run its two end spokes.
237 * Returns how many edges; horizontal ones cross no scanline and are not kept. */
238static int _solid_edges(const _solid_bands_t *const bands, const int8_t *const sign, _solid_edge_t *const edges)
239{
240 const float *const spine = bands->spine;
241 const float *const contour = bands->contour;
242 const int n = bands->n;
243 int count = 0;
244 int a = 0;
245 gboolean joined = FALSE; // this run's first spoke ended the run before, and is already in
246 while(a < bands->count)
247 {
248 const int s = sign[a];
249 int b = a;
250 for(; b < bands->count && sign[b] == s; b++)
251 {
252 if(s == 0) continue;
253 const int l = (b + 1 == n) ? 0 : b + 1;
254 count += _solid_add_edge(edges + count, spine[2 * b], spine[2 * b + 1], spine[2 * l], spine[2 * l + 1], s);
255 count += _solid_add_edge(edges + count, contour[2 * l], contour[2 * l + 1], contour[2 * b],
256 contour[2 * b + 1], s);
257 float t = 0.0f;
258 if(_solid_spokes_cross(bands, b, l, &t)) count += _solid_untwist(bands, b, l, t, s, edges + count);
259 }
260 // Two runs that meet share a spoke, which each walks its own way under its own sign: the same
261 // edge twice, added once with both windings.
262 const gboolean next = (s != 0) && b < bands->count && sign[b] != 0;
263 if(s != 0)
264 {
265 const int e = (b == n) ? 0 : b;
266 count += _solid_add_edge(edges + count, spine[2 * e], spine[2 * e + 1], contour[2 * e], contour[2 * e + 1],
267 next ? 2 * s : s);
268 if(!joined)
269 count += _solid_add_edge(edges + count, contour[2 * a], contour[2 * a + 1], spine[2 * a], spine[2 * a + 1], s);
270 }
271 joined = next;
272 a = b;
273 }
274 return count;
275}
276
277/* Two empty cells round the box, so no sample on the grid's rim is ever inside and the walk never
278 * leaves the grid. */
279static void _solid_grid_fit(_solid_grid_t *const g, const float bbox[4], float cell)
280{
281 double w = 0.0;
282 double h = 0.0;
283 for(;;)
284 {
285 w = ceil((bbox[1] - bbox[0]) / cell) + 4.0;
286 h = ceil((bbox[3] - bbox[2]) / cell) + 4.0;
287 if(w * h <= (double)SOLID_MAX_CELLS) break;
288 cell *= 1.01f * (float)sqrt(w * h / (double)SOLID_MAX_CELLS);
289 }
290 g->cell = cell;
291 g->x0 = bbox[0] - 2.0f * cell;
292 g->y0 = bbox[2] - 2.0f * cell;
293 g->w = (int)w;
294 g->h = (int)h;
295}
296
297/* The sub-scanlines [t0, t1) an edge crosses, sub-scanline t lying at (t + 0.5) / SOLID_SUBLINES
298 * cells: half-open, so a vertex two edges share is crossed once. */
299static inline void _solid_lines(const _solid_edge_t *const e, const _solid_grid_t *const g, int *t0, int *t1)
300{
301 const float scale = SOLID_SUBLINES / g->cell;
302 *t0 = (int)ceilf((e->y - g->y0) * scale - 0.5f);
303 *t1 = (int)ceilf((e->y_end - g->y0) * scale - 0.5f);
304}
305
306/* How many crossings each sub-scanline holds, as offsets into one array, @p offset holding
307 * lines + 1 entries. Returns the total; past SOLID_MAX_CROSSINGS the offsets are not written. */
308static size_t _solid_count(const _solid_edge_t *const edges, const int count, const _solid_grid_t *const g,
309 int *const offset)
310{
311 const int lines = g->h * SOLID_SUBLINES;
312 memset(offset, 0, sizeof(int) * (lines + 1));
313 size_t total = 0;
314 for(int k = 0; k < count; k++)
315 {
316 int t0 = 0;
317 int t1 = 0;
318 _solid_lines(edges + k, g, &t0, &t1);
319 if(t1 <= t0) continue;
320 offset[t0]++;
321 offset[t1]--;
322 total += (size_t)(t1 - t0);
323 }
324 if(total > SOLID_MAX_CROSSINGS) return total;
325 int run = 0;
326 int at = 0;
327 for(int t = 0; t <= lines; t++)
328 {
329 run += offset[t];
330 offset[t] = at;
331 at += run;
332 }
333 return total;
334}
335
336static inline uint32_t _solid_key(const _solid_crossing_t *const c)
337{
338 uint32_t key = 0;
339 memcpy(&key, &c->x, sizeof(key));
340 return key;
341}
342
343/* One sub-scanline's crossings in order of x. Every x is positive -- the grid starts two cells
344 * before the box -- and a positive float's bits sort as its value, so a long line is sorted on
345 * them a byte at a time, through @p scratch, as long; a byte all the crossings share is skipped. */
346static void _solid_sort(_solid_crossing_t *const c, _solid_crossing_t *const scratch, const int m)
347{
348 if(m <= SOLID_INSERTION)
349 {
350 for(int q = 1; q < m; q++)
351 {
352 const _solid_crossing_t v = c[q];
353 int r = q;
354 for(; r > 0 && c[r - 1].x > v.x; r--) c[r] = c[r - 1];
355 c[r] = v;
356 }
357 return;
358 }
359 _solid_crossing_t *from = c;
360 _solid_crossing_t *to = scratch;
361 for(int shift = 0; shift < 32; shift += 8)
362 {
363 int start[257] = { 0 };
364 for(int q = 0; q < m; q++) start[((_solid_key(from + q) >> shift) & 0xff) + 1]++;
365 if(start[((_solid_key(from) >> shift) & 0xff) + 1] == m) continue;
366 for(int d = 0; d < 256; d++) start[d + 1] += start[d];
367 for(int q = 0; q < m; q++) to[start[(_solid_key(from + q) >> shift) & 0xff]++] = from[q];
368 _solid_crossing_t *const was = from;
369 from = to;
370 to = was;
371 }
372 if(from != c) memcpy(c, from, sizeof(_solid_crossing_t) * m);
373}
374
375/* One span of one sub-scanline into the row: the cells it covers whole through a running step,
376 * the two it ends in by the fraction it covers. */
377static inline void _solid_span(float *const partial, float *const step, const float xa, const float xb,
378 int *const lo, int *const hi)
379{
380 const float k = 1.0f / SOLID_SUBLINES;
381 const int ia = (int)xa;
382 const int ib = (int)xb;
383 *lo = MIN(*lo, ia);
384 *hi = MAX(*hi, ib);
385 if(ia == ib)
386 {
387 partial[ia] += (xb - xa) * k;
388 return;
389 }
390 partial[ia] += ((float)(ia + 1) - xa) * k;
391 partial[ib] += (xb - (float)ib) * k;
392 step[ia + 1] += k;
393 step[ib] -= k;
394}
395
396/* Non-zero coverage of the edges' polygons, 0 to 255 per cell, into @p cover (zeroed, w * h), and
397 * the cells of each row it may have written, first and last, into @p range: none, w and -1.
398 * @p crossing holds every sub-scanline's crossings at @p offset. Returns 1 on allocation failure. */
399static int _solid_fill(const _solid_edge_t *const edges, const int count, const _solid_grid_t *const g,
400 const int *const offset, _solid_crossing_t *const crossing, uint8_t *const cover,
401 int *const range)
402{
403 const int lines = g->h * SOLID_SUBLINES;
404 int longest = 0;
405 for(int t = 0; t < lines; t++) longest = MAX(longest, offset[t + 1] - offset[t]);
406 int *cursor = dt_alloc_align(sizeof(int) * lines);
407 float *partial = dt_calloc_align_float((size_t)g->w + 1);
408 float *step = dt_calloc_align_float((size_t)g->w + 1);
409 _solid_crossing_t *scratch = dt_alloc_align(sizeof(_solid_crossing_t) * MAX(longest, 1));
410 if(IS_NULL_PTR(cursor) || IS_NULL_PTR(partial) || IS_NULL_PTR(step) || IS_NULL_PTR(scratch))
411 {
412 dt_free_align(cursor);
413 dt_free_align(partial);
414 dt_free_align(step);
415 dt_free_align(scratch);
416 return 1;
417 }
418 memcpy(cursor, offset, sizeof(int) * lines);
419
420 const float line_step = g->cell / SOLID_SUBLINES;
421 for(int k = 0; k < count; k++)
422 {
423 const _solid_edge_t *const e = edges + k;
424 int t0 = 0;
425 int t1 = 0;
426 _solid_lines(e, g, &t0, &t1);
427 for(int t = t0; t < t1; t++)
428 {
429 const float y = g->y0 + ((float)t + 0.5f) * line_step;
430 _solid_crossing_t *const c = crossing + cursor[t]++;
431 c->x = (e->x + (y - e->y) * e->slope - g->x0) / g->cell;
432 c->dir = e->dir;
433 }
434 }
435
436 for(int j = 0; j < g->h; j++)
437 {
438 int lo = g->w;
439 int hi = -1;
440 for(int t = j * SOLID_SUBLINES; t < (j + 1) * SOLID_SUBLINES; t++)
441 {
442 _solid_crossing_t *const c = crossing + offset[t];
443 const int m = offset[t + 1] - offset[t];
444 if(m < 2) continue;
445 _solid_sort(c, scratch, m);
446 int winding = 0;
447 float from = 0.0f;
448 for(int q = 0; q < m; q++)
449 {
450 const int was = winding;
451 winding += c[q].dir;
452 if(was == 0) from = c[q].x;
453 else if(winding == 0) _solid_span(partial, step, from, c[q].x, &lo, &hi);
454 }
455 }
456 float run = 0.0f;
457 uint8_t *const row = cover + (size_t)j * g->w;
458 for(int i = lo; i <= hi; i++)
459 {
460 run += step[i];
461 row[i] = (uint8_t)(fminf(fmaxf(partial[i] + run, 0.0f), 1.0f) * 255.0f + 0.5f);
462 partial[i] = 0.0f;
463 step[i] = 0.0f;
464 }
465 range[2 * j] = lo;
466 range[2 * j + 1] = hi;
467 }
468
469 dt_free_align(cursor);
470 dt_free_align(partial);
471 dt_free_align(step);
472 dt_free_align(scratch);
473 return 0;
474}
475
476/* The cells the spine of every kept band crosses, into the solid part. Its spokes start on it, so
477 * the solid part holds it; where the solid radius falls near nothing or its spokes lie along it,
478 * that part is a thread round it, and a thread thinner than half a cell is under half coverage:
479 * traced from the fill alone, it breaks into islands that float rounding makes or unmakes. Each
480 * segment is walked from cell to cell across their sides, so the cells it marks are joined by a
481 * side and the trace keeps one loop round them. */
482static void _solid_spine(const _solid_bands_t *const b, const int8_t *const sign, const _solid_grid_t *const g,
483 uint8_t *const cover, int *const range)
484{
485 for(int k = 0; k < b->count; k++)
486 {
487 if(sign[k] == 0) continue;
488 const int l = (k + 1 == b->n) ? 0 : k + 1;
489 const float xa = (b->spine[2 * k] - g->x0) / g->cell;
490 const float ya = (b->spine[2 * k + 1] - g->y0) / g->cell;
491 const float xb = (b->spine[2 * l] - g->x0) / g->cell;
492 const float yb = (b->spine[2 * l + 1] - g->y0) / g->cell;
493 int i = (int)xa;
494 int j = (int)ya;
495 const int i_end = (int)xb;
496 const int j_end = (int)yb;
497 const float dx = xb - xa;
498 const float dy = yb - ya;
499 const int si = (dx > 0.0f) - (dx < 0.0f);
500 const int sj = (dy > 0.0f) - (dy < 0.0f);
501 for(;;)
502 {
503 cover[(size_t)j * g->w + i] = 255;
504 range[2 * j] = MIN(range[2 * j], i);
505 range[2 * j + 1] = MAX(range[2 * j + 1], i);
506 if(i == i_end && j == j_end) break;
507 // The segment leaves the cell by the side it reaches first: its next side across x, at sx / dx
508 // of the segment, or its next side across y, at sy / dy.
509 const float sx = (float)(i + (si > 0)) - xa;
510 const float sy = (float)(j + (sj > 0)) - ya;
511 if(j == j_end || (i != i_end && fabsf(sx * dy) <= fabsf(sy * dx)))
512 i += si;
513 else
514 j += sj;
515 }
516 }
517}
518
519/* Square (i, j) has its corners at samples tl (i, j), tr, br and bl, numbered 0 to 3 clockwise,
520 * and edge e runs from corner e to corner e + 1. Its visit is recorded on one sample: a horizontal
521 * edge's on its left end (bit 1), a vertical edge's on its upper end (bit 2). */
522static const int _corner_i[4] = { 0, 1, 1, 0 };
523static const int _corner_j[4] = { 0, 0, 1, 1 };
524static const int _visit_corner[4] = { 0, 1, 3, 0 };
525static const int _step_i[4] = { 0, 1, 0, -1 };
526static const int _step_j[4] = { -1, 0, 1, 0 };
527
528static inline uint8_t *_solid_visit(uint8_t *const visited, const int w, const int i, const int j, const int e,
529 uint8_t *const bit)
530{
531 *bit = (e & 1) ? 2 : 1;
532 return visited + (size_t)(j + _corner_j[_visit_corner[e]]) * w + i + _corner_i[_visit_corner[e]];
533}
534
535/* The edge a contour entering square (i, j) through @p entry leaves it by. A saddle is resolved
536 * by its centre, the mean of its corners: the two corners on the centre's side are joined. */
537static int _solid_exit(const uint8_t *const cover, const int w, const int i, const int j, const int entry)
538{
539 const uint8_t *const top = cover + (size_t)j * w + i;
540 const int v[4] = { top[0], top[1], top[w + 1], top[w] };
541 gboolean crossed[4];
542 for(int e = 0; e < 4; e++) crossed[e] = (v[e] >= 128) != (v[(e + 1) & 3] >= 128);
543
544 if(crossed[0] && crossed[1] && crossed[2] && crossed[3])
545 {
546 static const int tl_joined[4] = { SOLID_RIGHT, SOLID_TOP, SOLID_LEFT, SOLID_BOTTOM };
547 static const int tl_alone[4] = { SOLID_LEFT, SOLID_BOTTOM, SOLID_RIGHT, SOLID_TOP };
548 const gboolean centre = (v[0] + v[1] + v[2] + v[3]) > 510;
549 return ((v[0] >= 128) == centre) ? tl_joined[entry] : tl_alone[entry];
550 }
551 for(int e = 0; e < 4; e++)
552 if(e != entry && crossed[e]) return e;
553 return entry; // a square entered through a crossed edge has another
554}
555
556/* Where the half-coverage level crosses edge e of square (i, j), in image pixels: a sample sits
557 * at its cell's centre. */
558static inline void _solid_point(const uint8_t *const cover, const _solid_grid_t *const g, const int i,
559 const int j, const int e, float *const out)
560{
561 const int a = e;
562 const int b = (e + 1) & 3;
563 const float va = cover[(size_t)(j + _corner_j[a]) * g->w + i + _corner_i[a]];
564 const float vb = cover[(size_t)(j + _corner_j[b]) * g->w + i + _corner_i[b]];
565 const float t = (127.5f - va) / (vb - va);
566 const float x = i + _corner_i[a] + t * (_corner_i[b] - _corner_i[a]);
567 const float y = j + _corner_j[a] + t * (_corner_j[b] - _corner_j[a]);
568 out[0] = g->x0 + (x + 0.5f) * g->cell;
569 out[1] = g->y0 + (y + 0.5f) * g->cell;
570}
571
572/* Follow the loop through the TOP edge of square (i, j), edge by edge, each crossed into the next
573 * square, until it reaches an edge already walked: in a consistent marching-squares field, that
574 * first one. Writes the loop's points, closed on the first, and returns how many. */
575static int _solid_follow(const uint8_t *const cover, uint8_t *const visited, const _solid_grid_t *const g,
576 int i, int j, float *const out)
577{
578 int count = 0;
579 int e = SOLID_TOP;
580 for(;;)
581 {
582 uint8_t bit = 0;
583 uint8_t *const visit = _solid_visit(visited, g->w, i, j, e, &bit);
584 if(*visit & bit) break;
585 *visit |= bit;
586 _solid_point(cover, g, i, j, e, out + 2 * count);
587 count++;
588 i += _step_i[e];
589 j += _step_j[e];
590 e = _solid_exit(cover, g->w, i, j, (e + 2) & 3);
591 }
592 out[2 * count] = out[0];
593 out[2 * count + 1] = out[1];
594 return count + 1;
595}
596
597/* Every loop of the half-coverage level. Every loop crosses at least four grid edges, the
598 * squares around a sample, so N crossed edges make at most N / 4 loops and N + N / 4 points.
599 * Only the cells the fill wrote, @p range, can be inside: a cell is from 128 up, its top bit. */
600static int _solid_trace(const uint8_t *const cover, const int *const range, const _solid_grid_t *const g,
602{
603 const int w = g->w;
604 const int h = g->h;
605 size_t crossed = 0;
606 for(int j = 0; j + 1 < h; j++)
607 {
608 const uint8_t *const row = cover + (size_t)j * w;
609 for(int i = range[2 * j] - 1; i <= range[2 * j + 1]; i++) crossed += (row[i] ^ row[i + 1]) >> 7;
610 const int last = MAX(range[2 * j + 1], range[2 * j + 3]);
611 for(int i = MIN(range[2 * j], range[2 * j + 2]); i <= last; i++) crossed += (row[i] ^ row[i + w]) >> 7;
612 }
613 if(crossed == 0) return 0;
614
615 const size_t max_loops = crossed / 4 + 1;
616 float *points = dt_pixelpipe_cache_alloc_align_float_cache(2 * (crossed + max_loops), 0);
619 uint8_t *visited = dt_calloc_align((size_t)w * h);
620 if(IS_NULL_PTR(points) || IS_NULL_PTR(breaks) || IS_NULL_PTR(visited))
621 {
624 dt_free_align(visited);
625 return 1;
626 }
627
628 int count = 0;
629 int loops = 0;
630 for(int j = 0; j + 1 < h; j++)
631 for(int i = range[2 * j] - 1; i <= range[2 * j + 1]; i++)
632 {
633 const uint8_t *const sample = cover + (size_t)j * w + i;
634 if(!((sample[0] ^ sample[1]) & 0x80) || (visited[(size_t)j * w + i] & 1)) continue;
635 if(loops > 0) breaks[loops - 1] = (dt_masks_skip_range_t){ .jump_from = count, .resume_at = count };
636 count += _solid_follow(cover, visited, g, i, j, points + 2 * count);
637 loops++;
638 }
639 dt_free_align(visited);
640
641 if(loops < 2) dt_pixelpipe_cache_free_align(breaks);
642 gp->fading = points;
643 gp->fading_count = count;
644 gp->fading_breaks = breaks;
645 gp->fading_break_count = (loops < 2) ? 0 : loops - 1;
646 return 0;
647}
648
649int dt_masks_solid_edge(dt_masks_form_gui_points_t *gui_points, const float *contour, const int header,
650 const float cell)
651{
652 const int n = gui_points->border_count - header;
653 if(n < 2) return 0;
654 const float *const spine = gui_points->points + 2 * header;
655 contour += 2 * header;
656 const double start = dt_get_wtime();
657
658 // The samples run round the stroke and back to its start: the band that closes the walk is
659 // only there when they do.
660 const gboolean closed = hypotf(spine[0] - spine[2 * n - 2], spine[1] - spine[2 * n - 1]) < cell;
661 const _solid_bands_t b = { .spine = spine, .contour = contour, .n = n, .count = closed ? n : n - 1, .cell = cell };
662 const int bands = b.count;
663
664 int8_t *sign = dt_alloc_align((size_t)bands);
665 if(IS_NULL_PTR(sign)) return 1;
666 float bbox[4] = { FLT_MAX, -FLT_MAX, FLT_MAX, -FLT_MAX };
667 int twisted = 0;
668 const int runs = _solid_band_signs(&b, sign, bbox, &twisted);
669 const size_t capacity = 2 * ((size_t)bands + runs) + 3 * (size_t)twisted;
670 _solid_edge_t *edges = (runs > 0) ? dt_alloc_align(sizeof(_solid_edge_t) * capacity) : NULL;
671 const int edge_count = IS_NULL_PTR(edges) ? 0 : _solid_edges(&b, sign, edges);
672 if(IS_NULL_PTR(edges))
673 {
675 return runs > 0;
676 }
677
678 _solid_grid_t g = { 0 };
679 int *offset = NULL;
680 size_t crossings = 0;
681 for(float c = cell;; c = g.cell * 2.0f)
682 {
683 _solid_grid_fit(&g, bbox, c);
684 dt_free_align(offset);
685 offset = dt_alloc_align(sizeof(int) * ((size_t)g.h * SOLID_SUBLINES + 1));
686 if(IS_NULL_PTR(offset)) break;
687 crossings = _solid_count(edges, edge_count, &g, offset);
688 if(crossings <= SOLID_MAX_CROSSINGS) break;
689 }
690
691 _solid_crossing_t *crossing = dt_alloc_align(sizeof(_solid_crossing_t) * MAX(crossings, 1));
692 uint8_t *cover = dt_calloc_align((size_t)g.w * g.h);
693 int *range = dt_alloc_align(sizeof(int) * 2 * (size_t)g.h);
694 int failed = IS_NULL_PTR(offset) || IS_NULL_PTR(crossing) || IS_NULL_PTR(cover) || IS_NULL_PTR(range);
695 if(!failed) failed = _solid_fill(edges, edge_count, &g, offset, crossing, cover, range);
696 if(!failed) _solid_spine(&b, sign, &g, cover, range);
698 dt_free_align(edges);
699 dt_free_align(offset);
700 dt_free_align(crossing);
701 const double filled = dt_get_wtime();
702
703 if(!failed) failed = _solid_trace(cover, range, &g, gui_points);
704 dt_free_align(cover);
705 dt_free_align(range);
706
709 "[masks] solid edge: %d bands in %d runs, %d of them bow ties, %d edges, %dx%d cells of %.1f px, %"
710 G_GSIZE_FORMAT " crossings, %d points in %d loops; filled in %.1f ms, traced in %.1f ms\n",
711 bands, runs, twisted, edge_count, g.w, g.h, g.cell, crossings, gui_points->fading_count,
712 gui_points->fading_break_count + (gui_points->fading_count > 0), 1000.0 * (filled - start),
713 1000.0 * (dt_get_wtime() - filled));
714 return failed;
715}
#define FALSE
Definition ashift_lsd.c:158
#define m
Definition basecurve.c:283
static const float x
const int t
const float v
const dt_colormatrix_t dt_aligned_pixel_t out
const float top
static const int row
void * dt_alloc_align(size_t size)
Allocate cacheline-aligned memory.
Definition darktable.c:511
memcpy(roundtrip, origin, sizeof(roundtrip))
dt_map_box_t bbox
Definition location.c:4
@ DT_DEBUG_PERF
Definition logging.h:55
@ DT_DEBUG_MASKS
Definition logging.h:62
int32_t dt_get_debug_flags(void)
Definition darktable.c:2094
void dt_print(dt_debug_thread_t thread, const char *msg,...) __attribute__((format(printf
Print to stdout when thread is enabled, prefixed with seconds since startup.
float *const restrict const size_t k
#define IS_NULL_PTR(p)
C is way too permissive with !=, == and if(var) checks, which can mean too many things depending on w...
Definition macros.h:96
The interactive half of the masks subsystem: the editing state (dt_masks_form_gui_t),...
static uint32_t _solid_key(const _solid_crossing_t *const c)
static const int _corner_i[4]
static void _solid_span(float *const partial, float *const step, const float xa, const float xb, int *const lo, int *const hi)
static void _solid_spine(const _solid_bands_t *const b, const int8_t *const sign, const _solid_grid_t *const g, uint8_t *const cover, int *const range)
#define SOLID_SUBLINES
Definition masks_solid.c:47
static size_t _solid_count(const _solid_edge_t *const edges, const int count, const _solid_grid_t *const g, int *const offset)
static uint8_t * _solid_visit(uint8_t *const visited, const int w, const int i, const int j, const int e, uint8_t *const bit)
static void _solid_grid_fit(_solid_grid_t *const g, const float bbox[4], float cell)
static int _solid_band_signs(const _solid_bands_t *const b, int8_t *const sign, float bbox[4], int *const twisted)
static const int _corner_j[4]
static void _solid_point(const uint8_t *const cover, const _solid_grid_t *const g, const int i, const int j, const int e, float *const out)
static void _solid_sort(_solid_crossing_t *const c, _solid_crossing_t *const scratch, const int m)
static int _solid_fill(const _solid_edge_t *const edges, const int count, const _solid_grid_t *const g, const int *const offset, _solid_crossing_t *const crossing, uint8_t *const cover, int *const range)
#define SOLID_DRIFT
Definition masks_solid.c:52
static const int _visit_corner[4]
static void _solid_lines(const _solid_edge_t *const e, const _solid_grid_t *const g, int *t0, int *t1)
static int _solid_add_edge(_solid_edge_t *const e, const float xa, const float ya, const float xb, const float yb, const int winding)
static int _solid_edges(const _solid_bands_t *const bands, const int8_t *const sign, _solid_edge_t *const edges)
static int _solid_untwist(const _solid_bands_t *const b, const int k, const int l, const float t, const int s, _solid_edge_t *const edges)
static const int _step_j[4]
#define SOLID_MAX_CROSSINGS
Definition masks_solid.c:50
static int _solid_trace(const uint8_t *const cover, const int *const range, const _solid_grid_t *const g, dt_masks_form_gui_points_t *const gp)
static const int _step_i[4]
int dt_masks_solid_edge(dt_masks_form_gui_points_t *gui_points, const float *contour, const int header, const float cell)
@ SOLID_BOTTOM
Definition masks_solid.c:56
@ SOLID_LEFT
Definition masks_solid.c:56
@ SOLID_TOP
Definition masks_solid.c:56
@ SOLID_RIGHT
Definition masks_solid.c:56
#define SOLID_INSERTION
Definition masks_solid.c:54
static int _solid_follow(const uint8_t *const cover, uint8_t *const visited, const _solid_grid_t *const g, int i, int j, float *const out)
#define SOLID_MAX_CELLS
Definition masks_solid.c:49
static int _solid_exit(const uint8_t *const cover, const int w, const int i, const int j, const int entry)
static gboolean _solid_spokes_cross(const _solid_bands_t *const b, const int k, const int l, float *const t)
Definition masks_solid.c:93
static float * dt_calloc_align_float(size_t pixels)
dt_alloc_align_float() followed by a zero fill.
Definition mem_alloc.h:241
#define dt_free_align(ptr)
Release memory from dt_alloc_align() and set ptr to NULL.
Definition mem_alloc.h:214
static void * dt_calloc_align(size_t size)
dt_alloc_align() followed by a zero fill.
Definition mem_alloc.h:225
char * key
uint32_t width
Definition mipmap_cache.c:0
#define dt_pixelpipe_cache_alloc_align_float_cache(pixels, id)
#define dt_pixelpipe_cache_alloc_align_cache(size, id)
#define dt_pixelpipe_cache_free_align(mem)
static const dt_aligned_pixel_simd_t sign
Definition simd.h:118
const float r
const float * contour
Definition masks_solid.c:76
const float * spine
Definition masks_solid.c:75
dt_masks_skip_range_t * fading_breaks
Definition masks_gui.h:77
One cut in a shape's border outline: while walking the border buffer forward, on reaching index jump_...
#define c1
#define MIN(a, b)
Definition thinplate.c:32
#define MAX(a, b)
Definition thinplate.c:29
static double dt_get_wtime(void)
Definition times.h:43