oil-backend-cpu.def

#include "oil.h"
#include "oil-image-private.h"
#include "oil-backend-private.h"

#include <float.h>
#include <string.h>

/* this file is designed to be included (once!) in C files in order to create
   a CPU backend. This is because most backends share a lot of code, and
   differ only in details like how to add vectors.
   
   Unfortunately, as a result, there's a lot of C preprocessor. Sorry.
*/

#ifndef CPU_BACKEND_NAME
#error oil-backend-cpu.def included without CPU_BACKEND_NAME set
#endif

#ifdef SSE
#include <emmintrin.h>
#include <stdint.h>
#endif /* SSE */

typedef struct {
    unsigned short *depth_buffer;
} CPUPriv;

/* like (a * b + 127) / 255), but fast */
#define MULDIV255(a, b, tmp)                                \
	(tmp = (a) * (b) + 128, ((((tmp) >> 8) + (tmp)) >> 8))

/* used to compare floats
   determined by making the multiplier smaller and smaller until the holes
   between triangles went away. YMMV.
*/
#define SMALLFLOAT (20 * FLT_EPSILON)

static int oil_backend_cpu_initialize(void) {
    /* nothing to do */
    return 1;
}

static void oil_backend_cpu_new(OILImage *im) {
    /* add our data struct. FIXME fail if any of these are NULL */
    CPUPriv *priv;
    priv = im->backend_data = malloc(sizeof(CPUPriv));
    priv->depth_buffer = NULL;
}

static void oil_backend_cpu_free(OILImage *im) {
    /* free our data struct */
    CPUPriv *priv = im->backend_data;
    if (priv->depth_buffer)
        free(priv->depth_buffer);
    free(priv);
}

static void oil_backend_cpu_load(OILImage *im) {
    /* nothing to do */
}

static void oil_backend_cpu_save(OILImage *im) {
    /* nothing to do */
}

static inline void composite(OILPixel *out, OILPixel *in) {
    int tmp1, tmp2, tmp3;
    
    /* special cases */
    if ((in->a == 255 || (out->a == 0 && in->a > 0))) {
        /* straight-up copy */
        *out = *in;
    } else if (in->a == 0) {
        /* source is fully transparent, do nothing */
    } else {
        /* general case */
        int comp_alpha = in->a + MULDIV255(out->a, 255 - in->a, tmp1);
		
        out->r = MULDIV255(in->r, in->a, tmp1) + MULDIV255(MULDIV255(out->r, out->a, tmp2), 255 - in->a, tmp3);
        out->r = (out->r * 255) / comp_alpha;
                
        out->g = MULDIV255(in->g, in->a, tmp1) + MULDIV255(MULDIV255(out->g, out->a, tmp2), 255 - in->a, tmp3);
        out->g = (out->g * 255) / comp_alpha;
                
        out->b = MULDIV255(in->b, in->a, tmp1) + MULDIV255(MULDIV255(out->b, out->a, tmp2), 255 - in->a, tmp3);
        out->b = (out->b * 255) / comp_alpha;
		
        out->a = comp_alpha;
    }
}

static int oil_backend_cpu_composite(OILImage *im, OILImage *src, unsigned char alpha, int dx, int dy, unsigned int sx, unsigned int sy, unsigned int xsize, unsigned int ysize) {
    /* used by MULDIV255 */
    int tmp;
    unsigned int x, y;
    
    for (y = 0; y < ysize; y++) {
        OILPixel *out = &(im->data[dx + (dy + y) * im->width]);
        OILPixel *in = &(src->data[sx + (sy + y) * src->width]);
        
        for (x = 0; x < xsize; x++) {
            /* apply overall alpha */
            if (alpha != 255 && in->a != 0) {
                in->a = MULDIV255(in->a, alpha, tmp);
            }
            
            composite(out, in);
            
            /* move forward */
            out++;
            in++;
        }
    }
    
    return 1;
}

/* draws a triangle on the destination image, multiplicatively!
 * used for smooth lighting
 * (excuse the ridiculous number of parameters!)
 *
 * Algorithm adapted from _Fundamentals_of_Computer_Graphics_
 * by Peter Shirley, Michael Ashikhmin
 * (or at least, the version poorly reproduced here:
 *  http://www.gidforums.com/t-20838.html )
 */

static inline void draw_triangle(OILImage *im, OILImage *tex, OILVertex v0, OILVertex v1, OILVertex v2, OILTriangleFlags flags) {
    CPUPriv *priv = im->backend_data;
    /* ranges of pixels that are affected */
    int xmin, xmax, ymin, ymax;
    /* the (signed) area of the triangle in normalized 2d space */
    float area;
    /* constant coefficients for alpha, beta, gamma */
    float a12, a20, a01;
    float b12, b20, b01;
    float c12, c20, c01;
    /* constant normalizers for alpha, beta, gamma */
    float alpha_norm, beta_norm, gamma_norm;
    /* temporary variables */
    int tmp;
    /* iteration variables */
    int x, y;
    
    /* if we need to, initialize the depth buffer */
    if (OIL_EXPECT(flags & OIL_DEPTH_TEST, OIL_DEPTH_TEST) && OIL_UNLIKELY(priv->depth_buffer == NULL)) {
        priv->depth_buffer = calloc(im->width * im->height, sizeof(unsigned short));
    }
    
    /* set up draw ranges */
    xmin = (int)(OIL_MIN(v0.x, OIL_MIN(v1.x, v2.x)) - 0.5);
    ymin = (int)(OIL_MIN(v0.y, OIL_MIN(v1.y, v2.y)) - 0.5);
    xmax = (int)(OIL_MAX(v0.x, OIL_MAX(v1.x, v2.x)) - 0.5) + 1;
    ymax = (int)(OIL_MAX(v0.y, OIL_MAX(v1.y, v2.y)) - 0.5) + 1;
    
    xmin = OIL_CLAMP(xmin, 0, im->width);
    ymin = OIL_CLAMP(ymin, 0, im->height);
    xmax = OIL_CLAMP(xmax, 0, im->width);
    ymax = OIL_CLAMP(ymax, 0, im->height);
    
    /* bail early if the triangle is completely outside */
    if (OIL_LIKELY(ymin >= ymax || xmin >= xmax))
        return;
    
    /* figure out the triangle's area */
    area = 0.5 * ((v1.x - v0.x) * (v0.y - v2.y) - (v1.y - v0.y) * (v0.x - v2.x));
    /* back-face culling, and don't draw anything
       with area less than half a pixel */
    if (area < 0.5)
        return;
    
    /* setup coefficients */
    a12 = v1.y - v2.y; b12 = v2.x - v1.x; c12 = (v1.x * v2.y) - (v2.x * v1.y);
    a20 = v2.y - v0.y; b20 = v0.x - v2.x; c20 = (v2.x * v0.y) - (v0.x * v2.y);
    a01 = v0.y - v1.y; b01 = v1.x - v0.x; c01 = (v0.x * v1.y) - (v1.x * v0.y);
    
    /* setup normalizers */
    alpha_norm = 1.0f / ((a12 * v0.x) + (b12 * v0.y) + c12);
    beta_norm  = 1.0f / ((a20 * v1.x) + (b20 * v1.y) + c20);
    gamma_norm = 1.0f / ((a01 * v2.x) + (b01 * v2.y) + c01);
    
    /* apply normalizers */
    a12 *= alpha_norm; b12 *= alpha_norm; c12 *= alpha_norm;
    a20 *= beta_norm; b20 *= beta_norm; c20 *= beta_norm;
    a01 *= gamma_norm; b01 *= gamma_norm; c01 *= gamma_norm;
    
    /* iterate over the destination rect */
    for (y = ymin; y < ymax; y++) {
        OILPixel *out = &(im->data[y * im->width + xmin]);
        
        for (x = xmin; x < xmax; x++) {
            float fx, fy;
            float alpha, beta, gamma;
            float s, t;
            int si, ti;
            OILPixel p;
            fx = x + 0.5;
            fy = y + 0.5;
            alpha = (a12 * fx) + (b12 * fy) + c12;
            beta  = (a20 * fx) + (b20 * fy) + c20;
            gamma = (a01 * fx) + (b01 * fy) + c01;
            
            if (alpha >= -SMALLFLOAT && beta >= -SMALLFLOAT && gamma >= -SMALLFLOAT) {
                alpha = OIL_CLAMP(alpha, 0.0, 1.0);
                beta = OIL_CLAMP(beta, 0.0, 1.0);
                gamma = OIL_CLAMP(gamma, 0.0, 1.0);
                
                if (OIL_LIKELY(tex != NULL)) {
                    /* have to be more careful with texture coords, to
                       prevent bleeding */
                    float renorm = 1.0 / (alpha + beta + gamma);
                    s = renorm * (alpha * v0.s + beta * v1.s + gamma * v2.s);
                    t = renorm * (alpha * v0.t + beta * v1.t + gamma * v2.t);
                    
                    si = tex->width * s;
                    ti = tex->height * -t - 1;
                    
                    /* using % is too slow for the common case where
                       these are already inside the image */
                    while (OIL_UNLIKELY(si < 0))
                        si += tex->width;
                    while (OIL_UNLIKELY(si >= tex->width))
                        si -= tex->width;
                    while (ti < 0) /* this space intentionally ambiguous */
                        ti += tex->height;
                    while (OIL_UNLIKELY(ti >= tex->height))
                        ti -= tex->height;
                
                    p = tex->data[ti * tex->width + si];
                    if (OIL_UNLIKELY(p.a == 0)) {
                        /* skip this, nothing to draw
                           we want to bail before the depth test */
                        out++;
                        continue;
                    }
                } else {
                    p.r = 255;
                    p.g = 255;
                    p.b = 255;
                    p.a = 255;
                }
                
                if (OIL_EXPECT(flags & OIL_DEPTH_TEST, OIL_DEPTH_TEST)) {
                    int depth = alpha * v0.z + beta * v1.z + gamma * v2.z;
                    unsigned short *dbuffer = &(priv->depth_buffer[y * im->width + x]);
                    if (depth >= *dbuffer) {
                        /* write to our buffer */
                        *dbuffer = depth;
                    } else {
                        /* skip this, it's behind something */
                        out++;
                        continue;
                    }
                }
                
                if (v0.color.r != 255 || v1.color.r != 255 || v2.color.r != 255)
                    p.r = MULDIV255(p.r, alpha * v0.color.r + beta * v1.color.r + gamma * v2.color.r, tmp);
                if (v0.color.g != 255 || v1.color.g != 255 || v2.color.g != 255)
                    p.g = MULDIV255(p.g, alpha * v0.color.g + beta * v1.color.g + gamma * v2.color.g, tmp);
                if (v0.color.b != 255 || v1.color.b != 255 || v2.color.b != 255)
                    p.b = MULDIV255(p.b, alpha * v0.color.b + beta * v1.color.b + gamma * v2.color.b, tmp);
                if (v0.color.a != 255 || v1.color.a != 255 || v2.color.a != 255)
                    p.a = MULDIV255(p.a, alpha * v0.color.a + beta * v1.color.a + gamma * v2.color.a, tmp);
                
                composite(out, &p);
            }
            
            out++;
        }
    }
}

static void oil_backend_cpu_draw_triangles(OILImage *im, OILMatrix *matrix, OILImage *tex, OILVertex *vertices, unsigned int vertices_length, unsigned int *indices, unsigned int indices_length, OILTriangleFlags flags) {
    OILMatrix realmat;
    unsigned int i;
    
    /* first we need to take the given matrix which yields [-1, 1] coordinates
       to something that gives pixel x/y coordinates
       also, invert Y because we want +Y to be up in 3D.
       finally, we need [-1, 1] Z to map to [0, 2^16 - 1] for depth buffer */
    oil_matrix_set_identity(&realmat);
    oil_matrix_scale(&realmat, im->width/2.0f, -(im->height/2.0f), (0xffff/2.0));
    oil_matrix_translate(&realmat, 1.0f, -1.0f, 1.0f);
    oil_matrix_multiply(&realmat, &realmat, matrix);
    
    
    for (i = 0; i < indices_length; i += 3) {
        OILVertex v0, v1, v2;
        v0 = vertices[indices[i]];
        v1 = vertices[indices[i + 1]];
        v2 = vertices[indices[i + 2]];
        
        oil_matrix_transform(&realmat, &(v0.x), &(v0.y), &(v0.z));
        oil_matrix_transform(&realmat, &(v1.x), &(v1.y), &(v1.z));
        oil_matrix_transform(&realmat, &(v2.x), &(v2.y), &(v2.z));
                
        draw_triangle(im, tex, v0, v1, v2, flags);
    }
}

static int oil_backend_resize_half(OILImage *im, OILImage *src) {
    unsigned int x, y;
	unsigned int r, g, b, a;
    
    for (y = 0; y < im->height; y++) {
        OILPixel *out = &(im->data[y * im->width]);
        OILPixel *in1 = &(src->data[(y * 2) * src->width]);
        OILPixel *in2 = &(src->data[(y * 2 + 1) * src->width]);
        
        for (x = 0; x < im->width; x++) {
			r = g = b = a = 0;
			
			/* read first column */
			r += in1->r + in2->r;
			g += in1->g + in2->g;
			b += in1->b + in2->b;
			a += in1->a + in2->a;
			in1++;
			in2++;
			
			/* read second column */
			r += in1->r + in2->r;
			g += in1->g + in2->g;
			b += in1->b + in2->b;
			a += in1->a + in2->a;
			in1++;
			in2++;
			
			/* write out average */
			out->r = (r >> 2);
			out->g = (g >> 2);
			out->b = (b >> 2);
			out->a = (a >> 2);
			out++;
        }
    }
    
    return 1;
}

static void oil_backend_cpu_clear(OILImage *im) {
	memset(im->data, 0, im->width * im->height * sizeof(OILPixel));
}

OILBackend CPU_BACKEND_NAME = {
    oil_backend_cpu_initialize,
    oil_backend_cpu_new,
    oil_backend_cpu_free,
    oil_backend_cpu_load,
    oil_backend_cpu_save,
    oil_backend_cpu_composite,
    oil_backend_cpu_draw_triangles,
	oil_backend_resize_half,
	oil_backend_cpu_clear,
};