splash/SplashScreen.cc

//========================================================================
//
// SplashScreen.cc
//
//========================================================================

//========================================================================
//
// Modified under the Poppler project - http://poppler.freedesktop.org
//
// All changes made under the Poppler project to this file are licensed
// under GPL version 2 or later
//
// Copyright (C) 2009, 2016, 2018, 2020, 2021 Albert Astals Cid <aacid@kde.org>
// Copyright (C) 2012 Fabio D'Urso <fabiodurso@hotmail.it>
//
// To see a description of the changes please see the Changelog file that
// came with your tarball or type make ChangeLog if you are building from git
//
//========================================================================

#include <config.h>

#include <cstdlib>
#include <cstring>
#include <algorithm>
#include "goo/gmem.h"
#include "goo/grandom.h"
#include "goo/GooLikely.h"
#include "SplashMath.h"
#include "SplashScreen.h"

static const SplashScreenParams defaultParams = {
    splashScreenDispersed, // type
    2, // size
    2, // dotRadius
    1.0, // gamma
    0.0, // blackThreshold
    1.0 // whiteThreshold
};

//------------------------------------------------------------------------

struct SplashScreenPoint
{
    int x, y;
    int dist;
};

struct cmpDistancesFunctor
{
    bool operator()(const SplashScreenPoint p0, const SplashScreenPoint p1) { return p0.dist < p1.dist; }
};

//------------------------------------------------------------------------
// SplashScreen
//------------------------------------------------------------------------

// If <clustered> is true, this generates a 45 degree screen using a
// circular dot spot function.  DPI = resolution / ((size / 2) *
// sqrt(2)).  If <clustered> is false, this generates an optimal
// threshold matrix using recursive tesselation.  Gamma correction
// (gamma = 1 / 1.33) is also computed here.
SplashScreen::SplashScreen(const SplashScreenParams *params)
{

    if (!params) {
        params = &defaultParams;
    }

    screenParams = params;
    mat = nullptr;
    size = 0;
    maxVal = 0;
    minVal = 0;
}

void SplashScreen::createMatrix()
{
    unsigned char u;
    int black, white, i;

    const SplashScreenParams *params = screenParams;

    // size must be a power of 2, and at least 2
    for (size = 2, log2Size = 1; size < params->size; size <<= 1, ++log2Size) {
        ;
    }

    switch (params->type) {

    case splashScreenDispersed:
        mat = (unsigned char *)gmallocn(size * size, sizeof(unsigned char));
        buildDispersedMatrix(size / 2, size / 2, 1, size / 2, 1);
        break;

    case splashScreenClustered:
        mat = (unsigned char *)gmallocn(size * size, sizeof(unsigned char));
        buildClusteredMatrix();
        break;

    case splashScreenStochasticClustered:
        // size must be at least 2*r
        while (size < (params->dotRadius << 1)) {
            size <<= 1;
            ++log2Size;
        }
        mat = (unsigned char *)gmallocn(size * size, sizeof(unsigned char));
        buildSCDMatrix(params->dotRadius);
        break;
    }

    sizeM1 = size - 1;

    // do gamma correction and compute minVal/maxVal
    minVal = 255;
    maxVal = 0;
    black = splashRound((SplashCoord)255.0 * params->blackThreshold);
    if (black < 1) {
        black = 1;
    }
    int whiteAux = splashRound((SplashCoord)255.0 * params->whiteThreshold);
    if (whiteAux > 255) {
        white = 255;
    } else {
        white = whiteAux;
    }
    for (i = 0; i < size * size; ++i) {
        u = splashRound((SplashCoord)255.0 * splashPow((SplashCoord)mat[i] / 255.0, params->gamma));
        if (u < black) {
            u = (unsigned char)black;
        } else if (u >= white) {
            u = (unsigned char)white;
        }
        mat[i] = u;
        if (u < minVal) {
            minVal = u;
        } else if (u > maxVal) {
            maxVal = u;
        }
    }
}

void SplashScreen::buildDispersedMatrix(int i, int j, int val, int delta, int offset)
{
    if (delta == 0) {
        // map values in [1, size^2] --> [1, 255]
        mat[(i << log2Size) + j] = 1 + (254 * (val - 1)) / (size * size - 1);
    } else {
        buildDispersedMatrix(i, j, val, delta / 2, 4 * offset);
        buildDispersedMatrix((i + delta) % size, (j + delta) % size, val + offset, delta / 2, 4 * offset);
        buildDispersedMatrix((i + delta) % size, j, val + 2 * offset, delta / 2, 4 * offset);
        buildDispersedMatrix((i + 2 * delta) % size, (j + delta) % size, val + 3 * offset, delta / 2, 4 * offset);
    }
}

void SplashScreen::buildClusteredMatrix()
{
    SplashCoord *dist;
    SplashCoord u, v, d;
    unsigned char val;
    int size2, x, y, x1, y1, i;

    size2 = size >> 1;

    // initialize the threshold matrix
    for (y = 0; y < size; ++y) {
        for (x = 0; x < size; ++x) {
            mat[(y << log2Size) + x] = 0;
        }
    }

    // build the distance matrix
    dist = (SplashCoord *)gmallocn(size * size2, sizeof(SplashCoord));
    for (y = 0; y < size2; ++y) {
        for (x = 0; x < size2; ++x) {
            if (x + y < size2 - 1) {
                u = (SplashCoord)x + 0.5 - 0;
                v = (SplashCoord)y + 0.5 - 0;
            } else {
                u = (SplashCoord)x + 0.5 - (SplashCoord)size2;
                v = (SplashCoord)y + 0.5 - (SplashCoord)size2;
            }
            dist[y * size2 + x] = u * u + v * v;
        }
    }
    for (y = 0; y < size2; ++y) {
        for (x = 0; x < size2; ++x) {
            if (x < y) {
                u = (SplashCoord)x + 0.5 - 0;
                v = (SplashCoord)y + 0.5 - (SplashCoord)size2;
            } else {
                u = (SplashCoord)x + 0.5 - (SplashCoord)size2;
                v = (SplashCoord)y + 0.5 - 0;
            }
            dist[(size2 + y) * size2 + x] = u * u + v * v;
        }
    }

    // build the threshold matrix
    x1 = y1 = 0; // make gcc happy
    for (i = 0; i < size * size2; ++i) {
        d = -1;
        for (y = 0; y < size; ++y) {
            for (x = 0; x < size2; ++x) {
                if (mat[(y << log2Size) + x] == 0 && dist[y * size2 + x] > d) {
                    x1 = x;
                    y1 = y;
                    d = dist[y1 * size2 + x1];
                }
            }
        }
        // map values in [0, 2*size*size2-1] --> [1, 255]
        val = 1 + (254 * (2 * i)) / (2 * size * size2 - 1);
        mat[(y1 << log2Size) + x1] = val;
        val = 1 + (254 * (2 * i + 1)) / (2 * size * size2 - 1);
        if (y1 < size2) {
            mat[((y1 + size2) << log2Size) + x1 + size2] = val;
        } else {
            mat[((y1 - size2) << log2Size) + x1 + size2] = val;
        }
    }

    gfree(dist);
}

// Compute the distance between two points on a toroid.
int SplashScreen::distance(int x0, int y0, int x1, int y1)
{
    int dx0, dx1, dx, dy0, dy1, dy;

    dx0 = abs(x0 - x1);
    dx1 = size - dx0;
    dx = dx0 < dx1 ? dx0 : dx1;
    dy0 = abs(y0 - y1);
    dy1 = size - dy0;
    dy = dy0 < dy1 ? dy0 : dy1;
    return dx * dx + dy * dy;
}

// Algorithm taken from:
// Victor Ostromoukhov and Roger D. Hersch, "Stochastic Clustered-Dot
// Dithering" in Color Imaging: Device-Independent Color, Color
// Hardcopy, and Graphic Arts IV, SPIE Vol. 3648, pp. 496-505, 1999.
void SplashScreen::buildSCDMatrix(int r)
{
    SplashScreenPoint *dots, *pts;
    int dotsLen, dotsSize;
    char *tmpl;
    char *grid;
    int *region, *dist;
    int x, y, xx, yy, x0, x1, y0, y1, i, j, d, iMin, dMin, n;

    // generate the random space-filling curve
    pts = (SplashScreenPoint *)gmallocn(size * size, sizeof(SplashScreenPoint));
    i = 0;
    for (y = 0; y < size; ++y) {
        for (x = 0; x < size; ++x) {
            pts[i].x = x;
            pts[i].y = y;
            ++i;
        }
    }
    for (i = 0; i < size * size; ++i) {
        j = i + (int)((double)(size * size - i) * grandom_double());
        x = pts[i].x;
        y = pts[i].y;
        pts[i].x = pts[j].x;
        pts[i].y = pts[j].y;
        pts[j].x = x;
        pts[j].y = y;
    }

    // construct the circle template
    tmpl = (char *)gmallocn((r + 1) * (r + 1), sizeof(char));
    for (y = 0; y <= r; ++y) {
        for (x = 0; x <= r; ++x) {
            tmpl[y * (r + 1) + x] = (x * y <= r * r) ? 1 : 0;
        }
    }

    // mark all grid cells as free
    grid = (char *)gmallocn(size * size, sizeof(char));
    for (y = 0; y < size; ++y) {
        for (x = 0; x < size; ++x) {
            grid[(y << log2Size) + x] = 0;
        }
    }

    // walk the space-filling curve, adding dots
    dotsLen = 0;
    dotsSize = 32;
    dots = (SplashScreenPoint *)gmallocn(dotsSize, sizeof(SplashScreenPoint));
    for (i = 0; i < size * size; ++i) {
        x = pts[i].x;
        y = pts[i].y;
        if (!grid[(y << log2Size) + x]) {
            if (dotsLen == dotsSize) {
                dotsSize *= 2;
                dots = (SplashScreenPoint *)greallocn(dots, dotsSize, sizeof(SplashScreenPoint));
            }
            dots[dotsLen++] = pts[i];
            for (yy = 0; yy <= r; ++yy) {
                y0 = (y + yy) % size;
                y1 = (y - yy + size) % size;
                for (xx = 0; xx <= r; ++xx) {
                    if (tmpl[yy * (r + 1) + xx]) {
                        x0 = (x + xx) % size;
                        x1 = (x - xx + size) % size;
                        grid[(y0 << log2Size) + x0] = 1;
                        grid[(y0 << log2Size) + x1] = 1;
                        grid[(y1 << log2Size) + x0] = 1;
                        grid[(y1 << log2Size) + x1] = 1;
                    }
                }
            }
        }
    }

    gfree(tmpl);
    gfree(grid);

    // assign each cell to a dot, compute distance to center of dot
    region = (int *)gmallocn(size * size, sizeof(int));
    dist = (int *)gmallocn(size * size, sizeof(int));
    for (y = 0; y < size; ++y) {
        for (x = 0; x < size; ++x) {
            iMin = 0;
            dMin = distance(dots[0].x, dots[0].y, x, y);
            for (i = 1; i < dotsLen; ++i) {
                d = distance(dots[i].x, dots[i].y, x, y);
                if (d < dMin) {
                    iMin = i;
                    dMin = d;
                }
            }
            region[(y << log2Size) + x] = iMin;
            dist[(y << log2Size) + x] = dMin;
        }
    }

    // compute threshold values
    for (i = 0; i < dotsLen; ++i) {
        n = 0;
        for (y = 0; y < size; ++y) {
            for (x = 0; x < size; ++x) {
                if (region[(y << log2Size) + x] == i) {
                    pts[n].x = x;
                    pts[n].y = y;
                    pts[n].dist = distance(dots[i].x, dots[i].y, x, y);
                    ++n;
                }
            }
        }
        std::sort(pts, pts + n, cmpDistancesFunctor());
        for (j = 0; j < n; ++j) {
            // map values in [0 .. n-1] --> [255 .. 1]
            mat[(pts[j].y << log2Size) + pts[j].x] = 255 - (254 * j) / (n - 1);
        }
    }

    gfree(pts);
    gfree(region);
    gfree(dist);

    gfree(dots);
}

SplashScreen::SplashScreen(const SplashScreen *screen)
{
    screenParams = screen->screenParams;
    size = screen->size;
    sizeM1 = screen->sizeM1;
    log2Size = screen->log2Size;
    mat = (unsigned char *)gmallocn(size * size, sizeof(unsigned char));
    if (likely(mat != nullptr)) {
        memcpy(mat, screen->mat, size * size * sizeof(unsigned char));
    }
    minVal = screen->minVal;
    maxVal = screen->maxVal;
}

SplashScreen::~SplashScreen()
{
    gfree(mat);
}