[sdf] Add '8-point sequential Euclidean distance mapping' algorithm. * src/sdf/ftbsdf.c (compare_neighbor, first_pass, second_pass, edt8): New functions.
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 276 277 278 279 280 281 282 283 284
diff --git a/ChangeLog b/ChangeLog
index 318f9d9..70d4dfe 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
2020-08-20 Anuj Verma <anujv@iitbhilai.ac.in>
+ [sdf] Add '8-point sequential Euclidean distance mapping' algorithm.
+
+ * src/sdf/ftbsdf.c (compare_neighbor, first_pass, second_pass,
+ edt8): New functions.
+
+2020-08-20 Anuj Verma <anujv@iitbhilai.ac.in>
+
[sdf] Add function to copy source bitmap to distance map.
* src/sdf/ftbsdf.c (bsdf_init_distance_map): New function.
diff --git a/src/sdf/ftbsdf.c b/src/sdf/ftbsdf.c
index da4d9f9..aee9987 100644
--- a/src/sdf/ftbsdf.c
+++ b/src/sdf/ftbsdf.c
@@ -303,7 +303,7 @@
* non-axis-aligned edges.
*
* (3) The only remaining piece of information that we cannot
- * approximate directly from the alpha is the direction of the edge.
+ * approximate directly from the alpha is the direction of the edge.
* This is where we use Sobel's operator to compute the gradient of
* the pixel. The gradient give us a pretty good approximation of
* the edge direction. We use a 3x3 kernel filter to compute the
@@ -695,4 +695,253 @@
}
+ /**************************************************************************
+ *
+ * @Function:
+ * compare_neighbor
+ *
+ * @Description:
+ * Compare neighbor pixel (which is defined by the offset) and update
+ * `current` distance if the new distance is shorter than the original.
+ *
+ * @Input:
+ * x_offset ::
+ * X offset of the neighbor to be checked. The offset is relative to
+ * the `current`.
+ *
+ * y_offset ::
+ * Y offset of the neighbor to be checked. The offset is relative to
+ * the `current`.
+ *
+ * width ::
+ * Width of the `current` array.
+ *
+ * @InOut:
+ * current ::
+ * Pointer into array of distances. This parameter must point to the
+ * position whose neighbor is to be checked. The array is treated as
+ * a two-dimensional array.
+ *
+ */
+ static void
+ compare_neighbor( ED* current,
+ FT_Int x_offset,
+ FT_Int y_offset,
+ FT_Int width )
+ {
+ ED* to_check;
+ FT_16D16 dist;
+ FT_16D16_Vec dist_vec;
+
+
+ to_check = current + ( y_offset * width ) + x_offset;
+
+ /*
+ * While checking for the nearest point we first approximate the
+ * distance of `current` by adding the deviation (which is sqrt(2) at
+ * most). Only if the new value is less than the current value we
+ * calculate the actual distances using `FT_Vector_Length`. This last
+ * step can be omitted by using squared distances.
+ */
+
+ /*
+ * Approximate the distance. We subtract 1 to avoid precision errors,
+ * which could happen because the two directions can be opposite.
+ */
+ dist = to_check->dist - ONE;
+
+ if ( dist < current->dist )
+ {
+ dist_vec = to_check->near;
+
+ dist_vec.x += x_offset * ONE;
+ dist_vec.y += y_offset * ONE;
+ dist = VECTOR_LENGTH_16D16( dist_vec );
+
+ if ( dist < current->dist )
+ {
+ current->dist = dist;
+ current->near = dist_vec;
+ }
+ }
+ }
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * first_pass
+ *
+ * @Description:
+ * First pass of the 8SED algorithm. Loop over the bitmap from top to
+ * bottom and scan each row left to right, updating the distances in
+ * `worker->distance_map`.
+ *
+ * @InOut:
+ * worker::
+ * Contains all the relevant parameters.
+ *
+ */
+ static void
+ first_pass( BSDF_Worker* worker )
+ {
+ FT_Int i, j; /* iterators */
+ FT_Int w, r; /* width, rows */
+ ED* dm; /* distance map */
+
+
+ dm = worker->distance_map;
+ w = worker->width;
+ r = worker->rows;
+
+ /* Start scanning from top to bottom and sweep each */
+ /* row back and forth comparing the distances of the */
+ /* neighborhood. Leave the first row as it has no top */
+ /* neighbor; it will be covered in the second scan of */
+ /* the image (from bottom to top). */
+ for ( j = 1; j < r; j++ )
+ {
+ FT_Int index;
+ ED* current;
+
+
+ /* Forward pass of rows (left -> right). Leave the first */
+ /* column, which gets covered in the backward pass. */
+ for ( i = 1; i < w; i++ )
+ {
+ index = j * w + i;
+ current = dm + index;
+
+ /* left-up */
+ compare_neighbor( current, -1, -1, w );
+ /* up */
+ compare_neighbor( current, 0, -1, w );
+ /* up-right */
+ compare_neighbor( current, 1, -1, w );
+ /* left */
+ compare_neighbor( current, -1, 0, w );
+ }
+
+ /* Backward pass of rows (right -> left). Leave the last */
+ /* column, which was already covered in the forward pass. */
+ for ( i = w - 2; i >= 0; i-- )
+ {
+ index = j * w + i;
+ current = dm + index;
+
+ /* right */
+ compare_neighbor( current, 1, 0, w );
+ }
+ }
+ }
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * second_pass
+ *
+ * @Description:
+ * Second pass of the 8SED algorithm. Loop over the bitmap from bottom
+ * to top and scan each row left to right, updating the distances in
+ * `worker->distance_map`.
+ *
+ * @InOut:
+ * worker::
+ * Contains all the relevant parameters.
+ *
+ */
+ static void
+ second_pass( BSDF_Worker* worker )
+ {
+ FT_Int i, j; /* iterators */
+ FT_Int w, r; /* width, rows */
+ ED* dm; /* distance map */
+
+
+ dm = worker->distance_map;
+ w = worker->width;
+ r = worker->rows;
+
+ /* Start scanning from bottom to top and sweep each */
+ /* row back and forth comparing the distances of the */
+ /* neighborhood. Leave the last row as it has no down */
+ /* neighbor; it is already covered in the first scan */
+ /* of the image (from top to bottom). */
+ for ( j = r - 2; j >= 0; j-- )
+ {
+ FT_Int index;
+ ED* current;
+
+
+ /* Forward pass of rows (left -> right). Leave the first */
+ /* column, which gets covered in the backward pass. */
+ for ( i = 1; i < w; i++ )
+ {
+ index = j * w + i;
+ current = dm + index;
+
+ /* left-up */
+ compare_neighbor( current, -1, 1, w );
+ /* up */
+ compare_neighbor( current, 0, 1, w );
+ /* up-right */
+ compare_neighbor( current, 1, 1, w );
+ /* left */
+ compare_neighbor( current, -1, 0, w );
+ }
+
+ /* Backward pass of rows (right -> left). Leave the last */
+ /* column, which was already covered in the forward pass. */
+ for ( i = w - 2; i >= 0; i-- )
+ {
+ index = j * w + i;
+ current = dm + index;
+
+ /* right */
+ compare_neighbor( current, 1, 0, w );
+ }
+ }
+ }
+
+
+ /**************************************************************************
+ *
+ * @Function:
+ * edt8
+ *
+ * @Description:
+ * Compute the distance map of the a bitmap. Execute both first and
+ * second pass of the 8SED algorithm.
+ *
+ * @InOut:
+ * worker::
+ * Contains all the relevant parameters.
+ *
+ * @Return:
+ * FreeType error, 0 means success.
+ *
+ */
+ static FT_Error
+ edt8( BSDF_Worker* worker )
+ {
+ FT_Error error = FT_Err_Ok;
+
+
+ if ( !worker || !worker->distance_map )
+ {
+ error = FT_THROW( Invalid_Argument );
+ goto Exit;
+ }
+
+ /* first scan of the image */
+ first_pass( worker );
+
+ /* second scan of the image */
+ second_pass( worker );
+
+ Exit:
+ return error;
+ }
+
/* END */