source: libpipi/trunk/pipi/paint/line.c @ 2844

/*
 *  libpipi       Pathetic image processing interface library
 *  Copyright (c) 2004-2008 Sam Hocevar <sam@zoy.org>
 *                2008 Jean-Yves Lamoureux <jylam@lnxscene.org>
 *                All Rights Reserved
 *
 *  $Id$
 *
 *  This library is free software. It comes without any warranty, to
 *  the extent permitted by applicable law. You can redistribute it
 *  and/or modify it under the terms of the Do What The Fuck You Want
 *  To Public License, Version 2, as published by Sam Hocevar. See
 *  http://sam.zoy.org/wtfpl/COPYING for more details.
 */

/*
 * line.c: line rendering functions
 */

#include "config.h"
#include "common.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#undef __USE_MISC  /* THAT sucks */
#undef __USE_XOPEN /* THAT sucks, too (avoid declaring y1 in math.h) */
#include <math.h>

#include "pipi.h"
#include "pipi_internals.h"

/* math.h doesn't like y1 (sucker) */
float floorf(float x);
float truncf(float x);
float fabsf(float x);

#if !defined TEMPLATE_FILE /* This file uses the template system */

static float fractf(float d) { return (d - floorf(d)); }
static float fractinvf(float d) { return (1 - (d - floorf(d))); }

struct line
{
    int x1, y1;
    int x2, y2;
    void (*draw) (pipi_image_t*, struct line*);
    union {
        uint32_t color32;
        float    colorf[3];
    };

    union {
        uint32_t *buf_u32;
        float    *buf_f;
    };

};

#define TEMPLATE_FLAGS SET_FLAG_GRAY | SET_FLAG_8BIT
#define TEMPLATE_FILE "paint/line.c"
#include "pipi_template.h"

static void clip_line(pipi_image_t*, struct line*);
static uint8_t clip_bits(pipi_image_t*, int, int);

int pipi_draw_line(pipi_image_t *img , int x1, int y1, int x2, int y2, uint32_t c, int aa)
{
    struct line s;
    s.x1 = x1;
    s.y1 = y1;
    s.x2 = x2;
    s.y2 = y2;


    /* No Transparency routine for u32 yet, fallback to float version */
    if(img->last_modified == PIPI_PIXELS_RGBA_C)
    {
        if(!aa)
        {
            uint32_t  *dstdata;
            dstdata = (uint32_t *)pipi_getpixels(img, PIPI_PIXELS_RGBA_C)->pixels;
            s.color32 = c;
            s.buf_u32 = dstdata;
            s.draw = line_8bit;
        }
        else
        {
            float  *dstdata;
            dstdata = (float *)pipi_getpixels(img, PIPI_PIXELS_RGBA_F)->pixels;
            s.colorf[2] = ((c&0x00FF0000)>>16)/255.0f; /* XXX FIXME */
            s.colorf[1] = ((c&0x0000FF00)>>8)/255.0f;  /* XXX FIXME */
            s.colorf[0] = (c&0x000000FF)/255.0f;       /* XXX FIXME */
            s.buf_f = dstdata;
            s.draw = aaline;
        }
    }
    else if(img->last_modified == PIPI_PIXELS_Y_F)
    {
        float  *dstdata;
        dstdata = (float *)pipi_getpixels(img, PIPI_PIXELS_Y_F)->pixels;
        s.colorf[0] = (c & 0xff) / 255.0f; /* XXX FIXME */
        s.buf_f = dstdata;
        s.draw = aa ? aaline_gray : line_gray;
    }
    else
    {
        float  *dstdata;
        dstdata = (float *)pipi_getpixels(img, PIPI_PIXELS_RGBA_F)->pixels;
        s.colorf[2] = ((c&0x00FF0000)>>16)/255.0f; /* XXX FIXME */
        s.colorf[1] = ((c&0x0000FF00)>>8)/255.0f;  /* XXX FIXME */
        s.colorf[0] = (c&0x000000FF)/255.0f;       /* XXX FIXME */
        s.buf_f = dstdata;
        s.draw = aa ? aaline : line;
    }

    clip_line(img, &s);
    return 0;
}

int pipi_draw_polyline(pipi_image_t *img, int const x[], int const y[],
                       int n, uint32_t c, int aa)
{
    int i;

    for(i = 0; i < n; i++)
        pipi_draw_line(img, x[i], y[i], x[i + 1], y[i + 1], c, aa);

    return 0;
}

/*
 * XXX: The following functions are local.
 */

/* Generic Cohen-Sutherland line clipping function. */
static void clip_line(pipi_image_t *img, struct line* s)
{
    uint8_t bits1, bits2;

    bits1 = clip_bits(img, s->x1, s->y1);
    bits2 = clip_bits(img, s->x2, s->y2);

    if(bits1 & bits2)
        return;

    if(bits1 == 0)
    {
        if(bits2 == 0)
            s->draw(img, s);
        else
        {
            int tmp;
            tmp = s->x1; s->x1 = s->x2; s->x2 = tmp;
            tmp = s->y1; s->y1 = s->y2; s->y2 = tmp;
            clip_line(img, s);
        }
        return;
    }

    if(bits1 & (1<<0))
    {
        s->y1 = s->y2 - (s->x2 - 0) * (s->y2 - s->y1) / (s->x2 - s->x1);
        s->x1 = 0;
    }
    else if(bits1 & (1<<1))
    {
        int xmax = img->w - 1;
        s->y1 = s->y2 - (s->x2 - xmax) * (s->y2 - s->y1) / (s->x2 - s->x1);
        s->x1 = xmax;
    }
    else if(bits1 & (1<<2))
    {
        s->x1 = s->x2 - (s->y2 - 0) * (s->x2 - s->x1) / (s->y2 - s->y1);
        s->y1 = 0;
    }
    else if(bits1 & (1<<3))
    {
        int ymax = img->h - 1;
        s->x1 = s->x2 - (s->y2 - ymax) * (s->x2 - s->x1) / (s->y2 - s->y1);
        s->y1 = ymax;
    }

    clip_line(img, s);
}

/* Helper function for clip_line(). */
static uint8_t clip_bits(pipi_image_t *img, int x, int y)
{
    uint8_t b = 0;

    if(x < 0)
        b |= (1<<0);
    else if(x >= (int)img->w)
        b |= (1<<1);

    if(y < 0)
        b |= (1<<2);
    else if(y >= (int)img->h)
        b |= (1<<3);

    return b;
}

#else /* XXX: the following functions use the template system */

/* Xiaolin Wu's line algorithm, as seen at http://portal.acm.org/citation.cfm?id=122734 */

#define PLOT(x, y, c) \
    if(FLAG_8BIT) \
    { \
        /* TODO */ \
    } \
    else \
    { \
        if(FLAG_GRAY) \
        { \
            s->buf_f[((int)(x))+((int)(y))*img->w] =  \
            (c*s->colorf[0]) + (1-c) * s->buf_f[((int)(x))+((int)(y))*img->w]; \
            if(s->buf_f[((int)(x))+((int)(y))*img->w] > 1.0f) \
                s->buf_f[((int)(x))+((int)(y))*img->w] = 1.0f; \
            if(s->buf_f[((int)(x))+((int)(y))*img->w] < 0.0f) \
                s->buf_f[((int)(x))+((int)(y))*img->w] = 0.0f; \
        } \
        else \
        { \
            int qwer = (((int)(x)*4))+((int)(y))*(img->w*4);\
            int qweg = (1+((int)(x)*4))+((int)(y))*(img->w*4); \
            int qweb = (2+((int)(x)*4))+((int)(y))*(img->w*4); \
            s->buf_f[qwer] = (c*s->colorf[0]) + (1-c) * s->buf_f[qwer]; \
            s->buf_f[qweg] = (c*s->colorf[1]) + (1-c) * s->buf_f[qweg]; \
            s->buf_f[qweb] = (c*s->colorf[2]) + (1-c) * s->buf_f[qweb]; \
            if(s->buf_f[qwer] > 1.0f) s->buf_f[qwer] = 1.0f; \
            if(s->buf_f[qwer] < 0.0f) s->buf_f[qwer] = 0.0f; \
            if(s->buf_f[qweg] > 1.0f) s->buf_f[qweg] = 1.0f; \
            if(s->buf_f[qweg] < 0.0f) s->buf_f[qweg] = 0.0f; \
            if(s->buf_f[qweb] > 1.0f) s->buf_f[qweb] = 1.0f; \
            if(s->buf_f[qweb] < 0.0f) s->buf_f[qweb] = 0.0f; \
        } \
    }

static void T(aaline)(pipi_image_t *img, struct line* s)
{
    float x1 = s->x1, y1 = s->y1, x2 = s->x2, y2 = s->y2;
    float g, xd, yd, xgap, xend, yend, xf, yf, val1, val2;
    int x, y, ix1, ix2, iy1, iy2;

    xd = x2 - x1;
    yd = y2 - y1;

    /* "Horizontal" line (X greater than Y)*/
    if (fabsf(xd) > fabsf(yd))
    {
        if (x1 > x2)
        {
            float tmp;
            tmp = x1; x1 = x2; x2 = tmp;
            tmp = y1; y1 = y2; y2 = tmp;
            xd = (x2-x1);
            yd = (y2-y1);
        }
        g = yd/xd;

        xend = truncf(x1+0.5);
        yend = y1 + g*(xend-x1);
        xgap = fractinvf(x1+0.5);
        ix1 = (int)xend;
        iy1 = (int)yend;
        val1 = fractinvf(yend)*xgap;
        val2 = fractf(yend)*xgap;

        PLOT(ix1, iy1,   val1);
        PLOT(ix1, (iy1+1)<y1?(iy1+1):iy1, val2);

        yf = yend+g;
        xend = truncf(x2+0.5);
        yend = y2 + g*(xend-x2);
        xgap = fractinvf(x2-0.5);
        ix2 = (int)xend;
        iy2 = (int)yend;
        val1 = fractinvf(yend)*xgap;
        val2 = fractf(yend)*xgap;

        PLOT(ix2, iy2,   val1);
        PLOT(ix2, iy2+1<y2?iy2+1:iy2, val2);

        for (x = (ix1+1); x < ix2; x++)
        {
            float focus;

            val1 = fractinvf(yf);
            val2 = fractf(yf);
            focus = (1.0 - fabsf(val1-val2));
            val1 += 0.3*focus;
            val2 += 0.3*focus;

            PLOT(x, yf, val1);
            PLOT(x, (yf+1)<y1?(yf+1):yf, val2);

            yf = yf + g;
        }
    }
    /* "Vertical" line (Y greater than X)*/
    else
    {
        if (x1 > x2)
        {
            float tmp;
            tmp = x1; x1 = x2; x2 = tmp;
            tmp = y1; y1 = y2; y2 = tmp;
            xd = (x2-x1);
            yd = (y2-y1);
        }

        g = xd/yd;

        xend = truncf(x1+0.5);
        yend = y1 + g*(xend-x1);
        xgap = fractf(x1+0.5);
        ix1 = (int)xend;
        iy1 = (int)yend;
        val1 = fractinvf(yend)*xgap;
        val2 = fractf(yend)*xgap;

        PLOT(ix1, iy1, val1);
        PLOT(ix1, (iy1+1)<y1?(iy1+1):iy1, val2);

        xf = xend + g;

        xend = truncf(x2+0.5);
        yend = y2 + g*(xend-x2);
        xgap = fractinvf(x2-0.5);
        ix2 = (int)xend;
        iy2 = (int)yend;
        val1 = fractinvf(yend)*xgap;
        val2 = fractf(yend)*xgap;

        PLOT(ix2, iy2,   val1);
        PLOT(ix2, (iy2+1)<y2?(iy2+1):iy2, val2);


        for (y = (iy1+1); y < iy2; y++)
        {
            float focus;
            int   vx = xf;
            val1 = fractinvf(xf);
            val2 = fractf(xf);
            focus = (1.0 - fabsf(val1-val2));
            val1 += 0.3*focus;
            val2 += 0.3*focus;
            PLOT(vx, y, val1);
            vx++;
            PLOT(vx, y, val2);
            xf = xf + g;
        }
    }
}

#undef PLOT

/* Solid line drawing function, using Bresenham's mid-point line
 * scan-conversion algorithm. */
static void T(line)(pipi_image_t *img, struct line* s)
{
    int x1, y1, x2, y2;
    int dx, dy;
    int xinc, yinc;

    x1 = s->x1; y1 = s->y1; x2 = s->x2; y2 = s->y2;

    dx = abs(x2 - x1);
    dy = abs(y2 - y1);

    xinc = (x1 > x2) ? -1 : 1;
    yinc = (y1 > y2) ? -1 : 1;

    if(dx >= dy)
    {
        int dpr = dy << 1;
        int dpru = dpr - (dx << 1);
        int delta = dpr - dx;

        for(; dx >= 0; dx--)
        {
            if(FLAG_GRAY)
            {
                if(FLAG_8BIT)
                    /* TODO */;
                else
                    s->buf_f[x1 + y1 * img->w] = s->colorf[0];
            }
            else
            {
                if(FLAG_8BIT)
                    s->buf_u32[x1 + y1 * img->w] = s->color32;
                else
                {
                    s->buf_f[4 * (y1 * img->w + x1)] = s->colorf[0];
                    s->buf_f[4 * (y1 * img->w + x1) + 1] = s->colorf[1];
                    s->buf_f[4 * (y1 * img->w + x1) + 2] = s->colorf[2];
                }
            }

            if(delta > 0)
            {
                x1 += xinc;
                y1 += yinc;
                delta += dpru;
            }
            else
            {
                x1 += xinc;
                delta += dpr;
            }
        }
    }
    else
    {
        int dpr = dx << 1;
        int dpru = dpr - (dy << 1);
        int delta = dpr - dy;

        for(; dy >= 0; dy--)
        {
            if(FLAG_GRAY)
            {
                if(FLAG_8BIT)
                    /* TODO */;
                else
                    s->buf_f[x1 + y1 * img->w] = s->colorf[0];
            }
            else
            {
                if(FLAG_8BIT)
                    s->buf_u32[x1 + y1 * img->w] = s->color32;
                else
                {
                    s->buf_f[4 * (y1 * img->w + x1)] = s->colorf[0];
                    s->buf_f[4 * (y1 * img->w + x1) + 1] = s->colorf[1];
                    s->buf_f[4 * (y1 * img->w + x1) + 2] = s->colorf[2];
                }
            }

            if(delta > 0)
            {
                x1 += xinc;
                y1 += yinc;
                delta += dpru;
            }
            else
            {
                y1 += yinc;
                delta += dpr;
            }
        }
    }
}

#endif