9. Correction Filters

9.1. Correcting a Square

The function kuf_correct_square will correct an input square and return it as a new square. This is a consistent function.

uint16_t kuf_correct_square(uint16_t s);

uint16_t kuf_correct_square(uint16_t s)
{
    uint8_t tmp;

<<correct_B>>
<<correct_BD_S>>
<<correct_D_S>>
<<correct_ABCD_W>>
<<correct_AC_W>>
<<correct_AB_NW>>
<<correct_CD_SW>>
<<correct_A_NW>>
<<correct_C_SW>>

    return s;
}

The eastern wall is first checked to be correct: B, BD:S,D:S. With any luck, nothing will need to be changed, reducing modifications down the line.

Checking the B quad is a matter of seeing if it is a correct quad or not. If it is not, it will increment to the next correct quad.

tmp = kuf_square_quad_get(s, KUF_QUAD_B);
while (!kuf_quad_check(tmp)) {
    tmp++;
    tmp &= 0xf;
}
s = kuf_square_quad_set(s, KUF_QUAD_B, tmp);

The southern side of BD (BD:S) is corrected next. The northern half is already been decided because B has been corrected.

tmp = kuf_square_quad_get(s, KUF_QUAD_BD);
tmp = kuf_correct_side(tmp, KUF_SOUTH);
s = kuf_square_quad_set(s, KUF_QUAD_BD, tmp);

The southern side of D (D:S) comes after (BD:S), which follows a similar process.

tmp = kuf_square_quad_get(s, KUF_QUAD_D);
tmp = kuf_correct_side(tmp, KUF_SOUTH);
s = kuf_square_quad_set(s, KUF_QUAD_D, tmp);

The western side of of ABCD (ABCD:W) gets solved next. ABCD:E has been provided by BD:W.

tmp = kuf_square_quad_get(s, KUF_QUAD_ABCD);
tmp = kuf_correct_side(tmp, KUF_WEST);
s = kuf_square_quad_set(s, KUF_QUAD_ABCD, tmp);

The western side of AC (AC:W) is corrected. This is the last side to correct.

tmp = kuf_square_quad_get(s, KUF_QUAD_AC);
tmp = kuf_correct_side(tmp, KUF_WEST);
s = kuf_square_quad_set(s, KUF_QUAD_AC, tmp);

The remaining tiles need to be corrected. First, the Northwest tile of AB (AB:NW) and the southwest tile of CD (CD:SW).

tmp = kuf_square_quad_get(s, KUF_QUAD_AB);
tmp = kuf_correct_tile(tmp, KUF_NORTHWEST);
s = kuf_square_quad_set(s, KUF_QUAD_AB, tmp);

tmp = kuf_square_quad_get(s, KUF_QUAD_CD);
tmp = kuf_correct_tile(tmp, KUF_SOUTHWEST);
s = kuf_square_quad_set(s, KUF_QUAD_CD, tmp);

Correcting AB:NW and CD:SW allows for correcting the final pair of tiles: the Northwest tile of A (A:NW), and the southwest tile of C (C:SW).

tmp = kuf_square_quad_get(s, KUF_QUAD_A);
tmp = kuf_correct_tile(tmp, KUF_NORTHWEST);
s = kuf_square_quad_set(s, KUF_QUAD_A, tmp);

tmp = kuf_square_quad_get(s, KUF_QUAD_C);
tmp = kuf_correct_tile(tmp, KUF_SOUTHWEST);
s = kuf_square_quad_set(s, KUF_QUAD_C, tmp);

9.2. Correcting a Side

The function kuf_correct_side will perform correction to a quad, constrained to a particular side. Options are North, South, East, West.

uint8_t kuf_correct_side(uint8_t q, int side);

uint8_t kuf_correct_side(uint8_t q, int side)
{
    if (kuf_quad_check(q)) return q;
    switch (side) {
        case KUF_NORTH:
<<correct_north_side>>
            break;
        case KUF_EAST:
<<correct_east_side>>
            break;
        case KUF_SOUTH:
<<correct_south_side>>
            break;
        case KUF_WEST:
<<correct_west_side>>
            break;
    }
    return q;
}

{
    int i;

    for (i = 0; i < 4; i++) {
        uint8_t s;

        s = kuf_quad_side_get(q, KUF_NORTH);
        s++;
        s &= 0x3;
        q = kuf_quad_side_set(q, KUF_NORTH, s);
        if (kuf_quad_check(q)) break;
    }
}

{
    int i;

    for (i = 0; i < 4; i++) {
        uint8_t s;

        s = kuf_quad_side_get(q, KUF_EAST);
        s++;
        s &= 0x3;
        q = kuf_quad_side_set(q, KUF_EAST, s);
        if (kuf_quad_check(q)) break;
    }
}

{
    int i;

    for (i = 0; i < 4; i++) {
        uint8_t s;

        s = kuf_quad_side_get(q, KUF_WEST);
        s++;
        s &= 0x3;
        q = kuf_quad_side_set(q, KUF_WEST, s);
        if (kuf_quad_check(q)) break;
    }
}

{
    int i;

    for (i = 0; i < 4; i++) {
        uint8_t s;

        s = kuf_quad_side_get(q, KUF_SOUTH);
        s++;
        s &= 0x3;
        q = kuf_quad_side_set(q, KUF_SOUTH, s);
        if (kuf_quad_check(q)) break;
    }
}

9.3. Correcting a Tile

kuf_correct_tile will correct a specific tile inside of a quad. This may at some point return a blank quad if no suitable candidates are found. Suitable positions are KUF_NORTHWEST, KUF_NORTHEAST, KUF_SOUTHEAST, and KUF_SOUTHWEST.

uint8_t kuf_correct_tile(uint8_t q, int pos);

uint8_t kuf_correct_tile(uint8_t q, int pos)
{
    uint8_t tile;

    if (kuf_quad_check(q)) return q;

    tile = kuf_quad_tile_get(q, pos);
    tile = tile ? 0 : 1;

    q = kuf_quad_tile_set(q, pos, tile);

    if (!kuf_quad_check(q)) {
        fprintf(stderr, "Oops. Could not correct tile!\n");
    }

    return q;
}

9.4. Correcting the D + C Quad of a squares

9.4.1. D Quad Correction

The local function correct_dquad will correct quad D in a square. This is needed for the larger function kuf_correct.

static uint16_t correct_dquad(uint16_t s);

Corrects tiles in the following order: ABCD:SE, CD:SE, BD:SE, D:SE. If for whatever reason, no solution is found, whitespace (0) will be returned.

static uint16_t correct_dquad(uint16_t s)
{
    uint8_t q;

    q = kuf_square_quad_get(s, KUF_QUAD_ABCD);
    q = kuf_correct_tile(q, KUF_SOUTHEAST);
    s = kuf_square_quad_set(s, KUF_QUAD_ABCD, q);

    q = kuf_square_quad_get(s, KUF_QUAD_CD);
    q = kuf_correct_tile(q, KUF_SOUTHEAST);
    s = kuf_square_quad_set(s, KUF_QUAD_CD, q);

    q = kuf_square_quad_get(s, KUF_QUAD_BD);
    q = kuf_correct_tile(q, KUF_SOUTHEAST);
    s = kuf_square_quad_set(s, KUF_QUAD_BD, q);

    q = kuf_square_quad_get(s, KUF_QUAD_D);
    q = kuf_correct_tile(q, KUF_SOUTHEAST);
    s = kuf_square_quad_set(s, KUF_QUAD_D, q);

    if (!kuf_quad_check(q)) {
        fprintf(stderr, "Oops. Could not correct D quad!\n");
    }

    return s;
}

9.4.2. C Quad Correction

correct_cquad works similarly to correct_dquad, only with the C quad. However, in this scenario it is assumed that only A has been corrected, and that the remaining C, B, and D quads remain to be corrected.

static uint16_t correct_cquad(uint16_t s);

Compared to the D quad corrector, this is has less constraints, as it is assumed at this point only the A quad has been corrected and locked in place.

Motions here are: AC:S and C:S.

static uint16_t correct_cquad(uint16_t s)
{
    uint8_t q;

    q = kuf_square_quad_get(s, KUF_QUAD_AC);
    q = kuf_correct_side(q, KUF_SOUTH);
    s = kuf_square_quad_set(s, KUF_QUAD_AC, q);

    q = kuf_square_quad_get(s, KUF_QUAD_C);
    q = kuf_correct_side(q, KUF_SOUTH);
    s = kuf_square_quad_set(s, KUF_QUAD_C, q);

    if (!kuf_quad_check(q)) {
        fprintf(stderr, "Oops. Could not correct D quad!\n");
    }

    return s;
}

9.5. Correcting the Eastern Wall of a Square

static uint16_t correct_eastwall(uint16_t s);

The eastern wall consists of the B + D quads, with A and C as known inputs assumed to be corrected already.

Correction moves in the following order: AB:E, B:E, ABCD:SE, BD:SE, CD:SE, D:SE.

static uint16_t correct_eastwall(uint16_t s)
{
    uint8_t q;

    q = kuf_square_quad_get(s, KUF_QUAD_AB);
    q = kuf_correct_side(q, KUF_EAST);
    s = kuf_square_quad_set(s, KUF_QUAD_AB, q);

    q = kuf_square_quad_get(s, KUF_QUAD_B);
    q = kuf_correct_side(q, KUF_EAST);
    s = kuf_square_quad_set(s, KUF_QUAD_B, q);

    q = kuf_square_quad_get(s, KUF_QUAD_ABCD);
    q = kuf_correct_tile(q, KUF_SOUTHEAST);
    s = kuf_square_quad_set(s, KUF_QUAD_ABCD, q);

    q = kuf_square_quad_get(s, KUF_QUAD_BD);
    q = kuf_correct_tile(q, KUF_SOUTHEAST);
    s = kuf_square_quad_set(s, KUF_QUAD_BD, q);

    q = kuf_square_quad_get(s, KUF_QUAD_CD);
    q = kuf_correct_tile(q, KUF_SOUTHEAST);
    s = kuf_square_quad_set(s, KUF_QUAD_CD, q);

    q = kuf_square_quad_get(s, KUF_QUAD_D);
    q = kuf_correct_tile(q, KUF_SOUTHEAST);
    s = kuf_square_quad_set(s, KUF_QUAD_D, q);

    return s;
}

9.6. Correcting a large pattern

The function kuf_correct is used apply a kufic correction filter on an existing pattern of squares configured in an NxM configuration. An optional bitmask bm can be supplied as a way to skip over particular squares in the matrix. NULL can be supplied here to disable it.

The input expects to be a sequence of squares, represented as 16-bit integers, lined up one row at a time.

The correction filter will write to the squares in-place.

The size of the array should be n*m.

void kuf_correct(int n, int m, uint16_t *squares, uint8_t *bm);

void kuf_correct(int n, int m, uint16_t *squares, uint8_t *bm)
{
    int x, y;
    int movesx;
    int movesy;
    uint8_t a, b, c, d;

    movesx = (n * 2) - 1;
    movesy = (m * 2) - 1;

    a = b = c = d = 0;

    for (y = 0; y < movesy; y++) {
        int yodd;
        yodd = y % 2;
<<update_abcd>>
        for (x = 0; x < movesx; x++) {
<<correct_and_update>>
        }
    }
}

Iterating through the loop is a matter of finding and updating 4 quads of the current square ABCD.

At the start of the row, the leftmost square is broken down into components A, B, C, and D. If y is odd, it is in between two squares: A + B are C + D of the current square, and C + D are A + B of the next square. An even Y value breaks up a square more regularly.

if (yodd) {
    uint16_t q[2];

    q[0] = squares[(y/2) * n];
    q[1] = squares[((y/2) + 1) * n];

    a = kuf_square_quad_get(q[0], KUF_QUAD_C);
    b = kuf_square_quad_get(q[0], KUF_QUAD_D);
    c = kuf_square_quad_get(q[1], KUF_QUAD_A);
    d = kuf_square_quad_get(q[1], KUF_QUAD_B);
} else {
    kuf_break_square(squares[(y/2)*n], &a, &b, &c, &d);
}

The correction will proceed to work on the row, moving left-to-right one half-square at at time.

uint16_t cur;
int xodd;
/* find new b + d based on position */

xodd = x % 2;

<<find_bd>>

/* construct current square */
cur = kuf_glue_square(a, b, c, d);

<<check_bitmask>>

if (y == 0) {
    if (x == 0) {
<<top_left_square>>
    } else {
<<correct_eastern_wall>>
    }
} else {
    if (x == 0) {
<<correct_cquad>>
    }

<<correct_dquad>>
}

<<break_and_update>>
<<set_AC_quads>>

Before any operations happen, the bitmask is checked. A bitmask is only checked on whole squares. If checking is disabled in the bitmask, the program moves forward and skips the current iteration.

Squares surrounding an ignored square will need to be corrected, otherwise there's a chance that they will yield invalid quads. Specifically, the leftmost quads of neighboring squares. Any square in the top row must have A and C of the right neighbor (the eastern wall of what would have been the next square), otherwise only C is solved (D quad of the next square).

Y-axis movement may not need any adjustment and will naturally solve itself. Hang on.

if (!xodd && !yodd) {
    if (!kuf_bitmask_get(bm, n, x/2, y/2)) {

        if (kuf_bitmask_get(bm, n, (x/2) + 1, y/2)) {
            uint16_t *ts;
            uint8_t ta, tb, tc, td;
            uint16_t nxt;

            nxt = squares[(y/2)*n + ((x/2) + 1)];
            nxt =
                kuf_glue_square(b,
                                kuf_square_quad_get(nxt,
                                                    KUF_QUAD_A),
                                d,
                                kuf_square_quad_get(nxt,
                                                    KUF_QUAD_C));
            if (y == 0) {
                /* correct eastern wall */
                nxt = correct_eastwall(nxt);
            } else {
                /* correct just the D quad */
                nxt = correct_dquad(nxt);
            }

            /* write back into squares */
            kuf_break_square(nxt, &ta, &tb, &tc, &td);

            ts = &squares[(y/2)*n + ((x/2) + 1)];

            *ts = kuf_square_quad_set(*ts, KUF_QUAD_A, tb);
            *ts = kuf_square_quad_set(*ts, KUF_QUAD_C, td);
        }

        kuf_break_square(squares[(y/2)*n + (x/2) + 1], &a, &b, &c, &d);
        x+=1;
        continue;
    }
}

Inside the loop, the B + D quads of the current square are found. x and y odd values indicate fractional boundaries.

if (xodd) {
    if (yodd) {
        uint16_t ts[2];

        ts[0] = squares[(y / 2) * n + ((x / 2) + 1)];
        ts[1] = squares[((y / 2) + 1) * n + ((x / 2) + 1)];

        b = kuf_square_quad_get(ts[0], KUF_QUAD_C);
        d = kuf_square_quad_get(ts[1], KUF_QUAD_A);
    } else {
        uint16_t ts;

        ts = squares[(y / 2) * n + ((x / 2) + 1)];

        b = kuf_square_quad_get(ts, KUF_QUAD_A);
        d = kuf_square_quad_get(ts, KUF_QUAD_C);
    }
} else {
    if (yodd) {
        uint16_t ts[2];

        ts[0] = squares[(y / 2) * n + (x / 2)];
        ts[1] = squares[((y / 2) + 1) * n + (x / 2)];

        b = kuf_square_quad_get(ts[0], KUF_QUAD_D);
        d = kuf_square_quad_get(ts[1], KUF_QUAD_B);
    } else {
        uint16_t ts;

        ts = squares[(y / 2) * n + (x / 2)];
        b = kuf_square_quad_get(ts, KUF_QUAD_B);
        d = kuf_square_quad_get(ts, KUF_QUAD_D);
    }
}

Depending on position, different corrections will happen.

The top-left square is the first to be corrected. Since it is the initial seed, the whole square needs to be correct.

cur = kuf_correct_square(cur);

Squares in the first row have the whole eastern side corrected (quads B and D).

cur = correct_eastwall(cur);

Squares that aren't in the first row only need to have their D quad corrected so that it is contextually correct.

cur = correct_dquad(cur);

At the beginning of each row (following the first row), the leftmost square must have the C quad corrected.

cur = correct_cquad(cur);

The currently selected square broken up into quad components, and are then written back into the buffer.

Similar to finding B + D at the beginning of the loop, writing the quads back to the correct squares is dependent on the oddness of the x and y positions, which break up the quads across multiple squares.

kuf_break_square(cur, &a, &b, &c, &d);
if (xodd) {
    if (yodd) {
        /* TODO: may not need the array anymore */
        /* Re-use variable instead */
        uint16_t *ts[4];

        ts[0] = &squares[(y / 2) * n + (x / 2)];
        *ts[0] = kuf_square_quad_set(*ts[0], KUF_QUAD_D, a);

        if (kuf_bitmask_get(bm, n, (x/2) + 1, (y/2))) {
            ts[1] = &squares[(y / 2) * n + ((x / 2) + 1)];
            *ts[1] = kuf_square_quad_set(*ts[1], KUF_QUAD_C, b);
        }

        if (kuf_bitmask_get(bm, n, (x/2), (y/2) + 1)) {
            ts[2] = &squares[((y / 2) + 1) * n + (x / 2)];
            *ts[2] = kuf_square_quad_set(*ts[2], KUF_QUAD_B, c);
        }

        if (kuf_bitmask_get(bm, n, (x/2) + 1, (y/2) + 1)) {
            ts[3] = &squares[((y / 2) + 1) * n + ((x / 2) + 1)];
            *ts[3] = kuf_square_quad_set(*ts[3], KUF_QUAD_A, d);
        }
    } else {
        /* TODO: may not need the array anymore */
        /* Re-use variable instead */
        uint16_t *ts[2];

        ts[0] = &squares[(y / 2) * n + (x / 2)];
        *ts[0] = kuf_square_quad_set(*ts[0], KUF_QUAD_B, a);
        *ts[0] = kuf_square_quad_set(*ts[0], KUF_QUAD_D, c);

        if (kuf_bitmask_get(bm, n, (x/2) + 1, (y/2))) {
            ts[1] = &squares[(y / 2) * n + ((x / 2) + 1)];
            *ts[1] = kuf_square_quad_set(*ts[1], KUF_QUAD_A, b);
            *ts[1] = kuf_square_quad_set(*ts[1], KUF_QUAD_C, d);
        }
    }
} else {
    if (yodd) {
        uint16_t *ts[2];

        ts[0] = &squares[(y / 2) * n + (x / 2)];

        *ts[0] = kuf_square_quad_set(*ts[0], KUF_QUAD_C, a);
        *ts[0] = kuf_square_quad_set(*ts[0], KUF_QUAD_D, b);

        if (kuf_bitmask_get(bm, n, (x/2), (y/2) + 1)) {
            ts[1] = &squares[((y / 2) + 1) * n + (x / 2)];
            *ts[1] = kuf_square_quad_set(*ts[1], KUF_QUAD_A, c);
            *ts[1] = kuf_square_quad_set(*ts[1], KUF_QUAD_B, d);
        }
    } else {
        uint16_t *ts;
        ts = &squares[((y / 2) * n) + (x / 2)];

        *ts = kuf_square_quad_set(*ts, KUF_QUAD_A, a);
        *ts = kuf_square_quad_set(*ts, KUF_QUAD_B, b);
        *ts = kuf_square_quad_set(*ts, KUF_QUAD_C, c);
        *ts = kuf_square_quad_set(*ts, KUF_QUAD_D, d);
    }
}

The B + D quads of are set to be the A + C quads.

a = b;
c = d;

9.7. Bitmasks

A correction filter can be used with a bitmask as a way to explicitely ignore and skip particular squares.

A bitmask in kuf is represented as an array of unsigned 8-bit values. Each bit represents the state of a square. If it is in the particular position, it will be subjected to correction. If it 0, it is skipped.

The number of bits must be at least the NxM dimension of the square tessellation pattern, rounded to the nearest byte boundary. This number can be calculated using kuf_bitmask_nbytes.

int kuf_bitmask_nbytes(int n, int m);

int kuf_bitmask_nbytes(int n, int m)
{
    int nbits;
    int nbytes;

    nbits = n * m;

    nbytes = nbits / 8;

    if ((nbytes * 8) < nbits) nbytes++;

    return nbytes;
}

Setting a bit in a bitmask can be done with kuf_bitmask_set. The n dimension must be supplied.

void kuf_bitmask_set(uint8_t *bm, int n, int x, int y, int s);

void kuf_bitmask_set(uint8_t *bm, int n, int x, int y, int s)
{
    int bitpos;
    int bytepos;
    int localpos;

    bitpos = y * n + x;
    bytepos = bitpos / 8;
    localpos = bitpos - (bytepos * 8);

    if (s) {
        bm[bytepos] |= (1 << localpos);
    } else {
        bm[bytepos] &= ~(1 << localpos);
    }
}

Getting a bit in a bitmask can be done with kuf_bitmask_get. The N dimension in the NxM square matrix must be supplied.

int kuf_bitmask_get(uint8_t *bm, int n, int x, int y);

If bm is NULL, this will return 1 by default. This behavior has been added to make integration into kuf_correct more straight forward.

int kuf_bitmask_get(uint8_t *bm, int n, int x, int y)
{
    int s;
    int bitpos;
    int bytepos;
    int localpos;

    if (bm == NULL) return 1;

    s = 0;

    bitpos = y * n + x;
    bytepos = bitpos / 8;
    localpos = bitpos - (bytepos * 8);

    s = (bm[bytepos] & (1 << localpos)) > 0;

    return s;
}

---

prev | home | next