
/*From: http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland */

#include "gfd.h"

#ifndef __cplusplus
#define bool int
#define true 1
#define false 0
#endif

#define outcode int

const int RIGHT = 8;  //1000
const int TOP = 4;    //0100
const int LEFT = 2;   //0010
const int BOTTOM = 1; //0001

//Compute the bit code for a point (x, y) using the clip rectangle
//bounded diagonally by (xmin, ymin), and (xmax, ymax)
static __inline outcode ComputeOutCode (double x, double y, double xmin, double xmax, double ymin, double ymax)
{
    outcode code = 0;
    if (y > ymax)              //above the clip window
        code |= TOP;
    else if (y < ymin)         //below the clip window
        code |= BOTTOM;
    if (x > xmax)              //to the right of clip window
        code |= RIGHT;
    else if (x < xmin)         //to the left of clip window
        code |= LEFT;
    return code;
}

//Cohen–Sutherland clipping algorithm clips a line from
//P0 = (x0, y0) to P1 = (x1, y1) against a rectangle with
//diagonal from (xmin, ymin) to (xmax, ymax).
int gfd_fb_cohen_sutherland_line_clip(gfd_framebuffer_t* const fb, int* const ix0, int* const iy0, int* const ix1, int* const iy1)
{
    double x0=*ix0;
    double y0=*iy0;
    double x1=*ix1;
    double y1=*iy1;
    double xmin=fb->ox;
    double xmax=fb->ex;
    double ymin=fb->oy;
    double ymax=fb->ey;

    //Outcodes for P0, P1, and whatever point lies outside the clip rectangle
    outcode outcode0, outcode1, outcodeOut;
    bool accept = false, done = false;

    //compute outcodes
    outcode0 = ComputeOutCode (x0, y0, xmin, xmax, ymin, ymax);
    outcode1 = ComputeOutCode (x1, y1, xmin, xmax, ymin, ymax);

    do{
        if (!(outcode0 | outcode1))      //logical or is 0. Trivially accept and get out of loop
        {
            accept = true;
            done = true;
        }
        else if (outcode0 & outcode1)//logical and is not 0. Trivially reject and get out of loop
                {
            done = true;
                }

        else
        {
            //failed both tests, so calculate the line segment to clip
            //from an outside point to an intersection with clip edge
            double x=0, y=0;
            //At least one endpoint is outside the clip rectangle; pick it.
            outcodeOut = outcode0? outcode0: outcode1;
            //Now find the intersection point;
            //use formulas y = y0 + slope * (x - x0), x = x0 + (1/slope)* (y - y0)
            if (outcodeOut & TOP)          //point is above the clip rectangle
            {
                x = x0 + (x1 - x0) * (ymax - y0)/(y1 - y0);
                y = ymax;
            }
            else if (outcodeOut & BOTTOM)  //point is below the clip rectangle
            {
                x = x0 + (x1 - x0) * (ymin - y0)/(y1 - y0);
                y = ymin;
            }
            else if (outcodeOut & RIGHT)   //point is to the right of clip rectangle
            {
                y = y0 + (y1 - y0) * (xmax - x0)/(x1 - x0);
                x = xmax;
            }
            else if (outcodeOut & LEFT)                         //point is to the left of clip rectangle
            {
                y = y0 + (y1 - y0) * (xmin - x0)/(x1 - x0);
                x = xmin;
            }
            //Now we move outside point to intersection point to clip
            //and get ready for next pass.
            if (outcodeOut == outcode0)
            {
                x0 = x;
                y0 = y;
                outcode0 = ComputeOutCode (x0, y0, xmin, xmax, ymin, ymax);
            }
            else
            {
                x1 = x;
                y1 = y;
                outcode1 = ComputeOutCode (x1, y1, xmin, xmax, ymin, ymax);
            }
        }
    }while (!done);

    if (accept)
    {
      *ix0=gfd_nint(x0);
      *ix1=gfd_nint(x1);
      *iy0=gfd_nint(y0);
      *iy1=gfd_nint(y1);
      return 1;
    }
    return 0;
}
