225 lines
4.5 KiB
C
225 lines
4.5 KiB
C
#include <assert.h>
|
|
#include <stdbool.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdint.h>
|
|
#include <string.h>
|
|
#include <time.h>
|
|
#include <math.h>
|
|
|
|
#define max(x, y) ((x) > (y) ? (x) : (y))
|
|
#define min(x, y) ((x) < (y) ? (x) : (y))
|
|
|
|
typedef unsigned char byte;
|
|
|
|
struct pixel {
|
|
float r;
|
|
float g;
|
|
float b;
|
|
};
|
|
|
|
void
|
|
die(char *msg)
|
|
{
|
|
fprintf(stderr, "%s\n", msg);
|
|
exit(1);
|
|
}
|
|
|
|
void
|
|
usage()
|
|
{
|
|
die("usage: dither filename");
|
|
}
|
|
|
|
/*
|
|
* parsing input file
|
|
*/
|
|
|
|
/* we assume it's P3 format */
|
|
void
|
|
skip_format(FILE *in)
|
|
{
|
|
fgetc(in);
|
|
fgetc(in);
|
|
fgetc(in);
|
|
}
|
|
|
|
bool
|
|
isdelim(char c)
|
|
{
|
|
return (c == ' ' || c == '\n');
|
|
}
|
|
|
|
float
|
|
read_number(FILE *in)
|
|
{
|
|
char buf[10] = {0};
|
|
char *bufptr = buf;
|
|
for(;;) {
|
|
char c = fgetc(in);
|
|
if (isdelim(c)) {
|
|
do {
|
|
c = fgetc(in);
|
|
if (c == EOF) break;
|
|
} while (isdelim(c));
|
|
|
|
fseek(in, -1L, SEEK_CUR);
|
|
return atoi(buf);
|
|
}
|
|
else {
|
|
*(bufptr++) = c;
|
|
}
|
|
}
|
|
}
|
|
|
|
struct pixel
|
|
read_pixel(FILE *in)
|
|
{
|
|
struct pixel p;
|
|
p.r = read_number(in);
|
|
p.g = read_number(in);
|
|
p.b = read_number(in);
|
|
return p;
|
|
}
|
|
|
|
/*
|
|
* drawing pixels
|
|
*/
|
|
|
|
void
|
|
draw_pixel(struct pixel p)
|
|
{
|
|
printf("%.0f %.0f %.0f\n", p.r, p.g, p.b);
|
|
}
|
|
|
|
/*
|
|
* main algorithm
|
|
*/
|
|
|
|
struct pixel
|
|
pixel_from_scalar(float scalar)
|
|
{
|
|
return (struct pixel) {
|
|
.r = scalar,
|
|
.g = scalar,
|
|
.b = scalar,
|
|
};
|
|
}
|
|
|
|
float
|
|
greyscale(struct pixel p)
|
|
{
|
|
return (p.r + p.g + p.b) / 3;
|
|
}
|
|
|
|
float
|
|
closest_palette_colour(float c)
|
|
{
|
|
return round(c);
|
|
}
|
|
|
|
size_t
|
|
safe_index(int width, int height, int x, int y)
|
|
{
|
|
return min((max(y, 0)), height-1) * width
|
|
+ min((max(x, 0)), width-1);
|
|
}
|
|
|
|
void
|
|
floyd_steinberg(size_t width, size_t height, struct pixel *pixels)
|
|
{
|
|
/* first convert the pixels to greyscale */
|
|
float grey[width*height];
|
|
|
|
for (size_t y = 0; y < height; y++) {
|
|
for (size_t x = 0; x < width; x++) {
|
|
float g = greyscale(pixels[y*width+x]);
|
|
grey[y*width+x] = g / 255;
|
|
}
|
|
}
|
|
|
|
for (size_t y = 0; y < height; y++) {
|
|
for (size_t x = 0; x < width; x++) {
|
|
float old = grey[y*width+x];
|
|
float new = closest_palette_colour(old);
|
|
|
|
grey[y*width+x] = new;
|
|
float quant_error = old - new;
|
|
|
|
grey[safe_index(width, height, x+1, y)] =
|
|
grey[safe_index(width, height, x+1, y)] + (quant_error*7/16);
|
|
grey[safe_index(width, height, x-1, y+1)] =
|
|
grey[safe_index(width, height, x-1, y+1)] + (quant_error*3/16);
|
|
grey[safe_index(width, height, x, y+1)] =
|
|
grey[safe_index(width, height, x, y+1)] + (quant_error*5/16);
|
|
grey[safe_index(width, height, x+1, y+1)] =
|
|
grey[safe_index(width, height, x+1, y+1)] + (quant_error*1/16);
|
|
}
|
|
}
|
|
|
|
for (size_t y = 0; y < height; y++) {
|
|
for (size_t x = 0; x < width; x++) {
|
|
pixels[y*width+x] = pixel_from_scalar(grey[y*width+x] * 255);
|
|
}
|
|
}
|
|
}
|
|
|
|
/* void */
|
|
/* dad(size_t width, size_t height, struct pixel *pixels) */
|
|
/* { */
|
|
/* /\* first convert the pixels to greyscale *\/ */
|
|
/* for (size_t y = 0; y < height; y++) { */
|
|
/* for (size_t x = 0; x < width; x++) { */
|
|
/* pixels[y*width+x] = pixel_from_scalar(greyscale(pixels[y*width+x])); */
|
|
/* } */
|
|
/* } */
|
|
|
|
/* struct pixel white = {.r = 255, .g = 255, .b = 255}; */
|
|
/* struct pixel black = {.r = 0, .g = 0, .b = 0}; */
|
|
|
|
/* srand(time(NULL)); */
|
|
/* for (size_t y = 0; y < height; y++) { */
|
|
/* for (size_t x = 0; x < width; x++) { */
|
|
/* byte r = rand() % 255; */
|
|
|
|
/* pixels[y*width+x] = pixels[y*width+x].r <= r */
|
|
/* ? black */
|
|
/* : white; */
|
|
|
|
/* } */
|
|
/* } */
|
|
/* } */
|
|
|
|
int
|
|
main(void)
|
|
{
|
|
FILE *in = stdin;
|
|
|
|
skip_format(in);
|
|
size_t w = read_number(in), h = read_number(in);
|
|
|
|
/* this is P3 since we might want different colours than black/white */
|
|
printf("P3\n%zu %zu\n255\n", w, h);
|
|
|
|
struct pixel pixels[h*w];
|
|
|
|
/* read the max colour depth, discard it */
|
|
read_number(in);
|
|
|
|
for (size_t y = 0; y < h; y++) {
|
|
for (size_t x = 0; x < w; x++) {
|
|
struct pixel p = read_pixel(in);
|
|
pixels[y*w+x] = p;
|
|
}
|
|
}
|
|
|
|
floyd_steinberg(w, h, pixels);
|
|
/* dad(w, h, pixels); */
|
|
|
|
for (size_t y = 0; y < h; y++) {
|
|
for (size_t x = 0; x < w; x++) {
|
|
draw_pixel(pixels[y*w+x]);
|
|
}
|
|
}
|
|
}
|