47#define SOLID_SUBLINES 4
49#define SOLID_MAX_CELLS ((size_t)8 << 20)
50#define SOLID_MAX_CROSSINGS ((size_t)32 << 20)
52#define SOLID_DRIFT 0.1f
54#define SOLID_INSERTION 32
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;
121 const float *
const spine = b->spine;
122 const float *
const contour = b->contour;
130 for(
int k = 0;
k < b->count;
k++)
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);
151 else if(current == 0)
154 if(fabsf(swept) > drift_max)
157 current = (swept > 0.0f) ? 1 : -1;
160 for(
int j = pending; j <
k; j++)
sign[j] = current;
166 drift = fmaxf(0.0f, drift - current *
width);
167 if(drift > drift_max)
178 for(
int k = 0;
k < b->count;
k++)
180 if(
sign[
k] == 0)
continue;
181 const int l = (
k + 1) %
n;
184 const int ends[2] = {
k, l };
185 for(
int q = 0; q < 2; q++)
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]));
198 const float yb,
const int winding)
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;
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]);
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);
240 const float *
const spine = bands->
spine;
241 const float *
const contour = bands->
contour;
242 const int n = bands->
n;
245 gboolean joined =
FALSE;
246 while(a < bands->count)
248 const int s =
sign[a];
250 for(; b < bands->
count &&
sign[b] == s; b++)
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);
262 const gboolean next = (s != 0) && b < bands->count &&
sign[b] != 0;
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],
269 count +=
_solid_add_edge(edges + count, contour[2 * a], contour[2 * a + 1], spine[2 * a], spine[2 * a + 1], s);
285 w = ceil((
bbox[1] -
bbox[0]) / cell) + 4.0;
286 h = ceil((
bbox[3] -
bbox[2]) / cell) + 4.0;
291 g->x0 =
bbox[0] - 2.0f * cell;
292 g->y0 =
bbox[2] - 2.0f * cell;
302 *t0 = (int)ceilf((e->
y -
g->y0) * scale - 0.5f);
303 *t1 = (int)ceilf((e->
y_end -
g->y0) * scale - 0.5f);
312 memset(offset, 0,
sizeof(
int) * (lines + 1));
314 for(
int k = 0;
k < count;
k++)
319 if(t1 <= t0)
continue;
322 total += (size_t)(t1 - t0);
327 for(
int t = 0;
t <= lines;
t++)
350 for(
int q = 1; q <
m; q++)
354 for(;
r > 0 && c[
r - 1].x >
v.x;
r--) c[
r] = c[
r - 1];
361 for(
int shift = 0; shift < 32; shift += 8)
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];
377static inline void _solid_span(
float *
const partial,
float *
const step,
const float xa,
const float xb,
378 int *
const lo,
int *
const hi)
381 const int ia = (int)xa;
382 const int ib = (int)xb;
387 partial[ia] += (xb - xa) *
k;
390 partial[ia] += ((float)(ia + 1) - xa) *
k;
391 partial[ib] += (xb - (float)ib) *
k;
400 const int *
const offset,
_solid_crossing_t *
const crossing, uint8_t *
const cover,
405 for(
int t = 0;
t < lines;
t++) longest =
MAX(longest, offset[
t + 1] - offset[
t]);
418 memcpy(cursor, offset,
sizeof(
int) * lines);
421 for(
int k = 0;
k < count;
k++)
427 for(
int t = t0;
t < t1;
t++)
429 const float y =
g->y0 + ((float)
t + 0.5f) * line_step;
431 c->x = (e->
x + (y - e->
y) * e->
slope -
g->x0) /
g->cell;
436 for(
int j = 0; j <
g->h; j++)
443 const int m = offset[
t + 1] - offset[
t];
448 for(
int q = 0; q <
m; q++)
450 const int was = winding;
452 if(was == 0) from = c[q].x;
453 else if(winding == 0)
_solid_span(partial, step, from, c[q].
x, &lo, &hi);
457 uint8_t *
const row = cover + (size_t)j *
g->w;
458 for(
int i = lo;
i <= hi;
i++)
461 row[
i] = (uint8_t)(fminf(fmaxf(partial[
i] + run, 0.0f), 1.0f) * 255.0f + 0.5f);
466 range[2 * j + 1] = hi;
483 uint8_t *
const cover,
int *
const range)
485 for(
int k = 0;
k < b->count;
k++)
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;
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);
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;
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)))
528static inline uint8_t *
_solid_visit(uint8_t *
const visited,
const int w,
const int i,
const int j,
const int e,
531 *bit = (e & 1) ? 2 : 1;
537static int _solid_exit(
const uint8_t *
const cover,
const int w,
const int i,
const int j,
const int entry)
539 const uint8_t *
const top = cover + (size_t)j * w +
i;
542 for(
int e = 0; e < 4; e++) crossed[e] = (
v[e] >= 128) != (
v[(e + 1) & 3] >= 128);
544 if(crossed[0] && crossed[1] && crossed[2] && crossed[3])
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];
551 for(
int e = 0; e < 4; e++)
552 if(e != entry && crossed[e])
return e;
559 const int j,
const int e,
float *
const out)
562 const int b = (e + 1) & 3;
565 const float t = (127.5f - va) / (vb - va);
568 out[0] =
g->x0 + (
x + 0.5f) *
g->cell;
569 out[1] =
g->y0 + (y + 0.5f) *
g->cell;
576 int i,
int j,
float *
const out)
583 uint8_t *
const visit =
_solid_visit(visited,
g->w,
i, j, e, &bit);
584 if(*visit & bit)
break;
593 out[2 * count + 1] =
out[1];
606 for(
int j = 0; j + 1 < h; j++)
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;
613 if(crossed == 0)
return 0;
615 const size_t max_loops = crossed / 4 + 1;
630 for(
int j = 0; j + 1 < h; j++)
631 for(
int i = range[2 * j] - 1;
i <= range[2 * j + 1];
i++)
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;
654 const float *
const spine = gui_points->
points + 2 * header;
655 contour += 2 * header;
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;
666 float bbox[4] = { FLT_MAX, -FLT_MAX, FLT_MAX, -FLT_MAX };
669 const size_t capacity = 2 * ((size_t)bands + runs) + 3 * (
size_t)twisted;
680 size_t crossings = 0;
681 for(
float c = cell;; c =
g.cell * 2.0f)
695 if(!failed) failed =
_solid_fill(edges, edge_count, &
g, offset, crossing, cover, range);
703 if(!failed) failed =
_solid_trace(cover, range, &
g, gui_points);
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,
const dt_colormatrix_t dt_aligned_pixel_t out
void * dt_alloc_align(size_t size)
Allocate cacheline-aligned memory.
memcpy(roundtrip, origin, sizeof(roundtrip))
int32_t dt_get_debug_flags(void)
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...
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)
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)
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
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)
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)
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)
static float * dt_calloc_align_float(size_t pixels)
dt_alloc_align_float() followed by a zero fill.
#define dt_free_align(ptr)
Release memory from dt_alloc_align() and set ptr to NULL.
static void * dt_calloc_align(size_t size)
dt_alloc_align() followed by a zero fill.
#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
One cut in a shape's border outline: while walking the border buffer forward, on reaching index jump_...
static double dt_get_wtime(void)