Can you tell me what's wrong with this implementation of Cohen-Sutherland Algorithm?

Question

Please, help me to fix the code of this implementation of Cohen-Sutherland Algorithm.

The theory is here at Page-91.

Here is the entire project.

#include "Line2d.h"
#include "Rectangle2d.h"
#include "Coordinates2d.h"

class ClippingLine2d
{
private:
    Rectangle2d rectangle;//clipping rectangle
    Line2d line;//line to be clipped
private:
    Bits startPointBits;//bits for start point of line
    Bits endPointsBits;//bits for end point of line
public:
    ClippingLine2d(Rectangle2d rect, Line2d line)
    {
        this->rectangle = rect;
        this->line = line;      
    }       
private:        
    Line2d GetClippedLine(std::vector<Line2d> clippingRegionLines, Line2d ln)
    {
        Point2d start = ln.GetStart();
        Point2d end = ln.GetEnd();

        if(startPointBits.bit4 == 1)
        {
            start = ln.GetIntersection(clippingRegionLines[3]);//DA
        }
        else if(startPointBits.bit3 == 1)
        {
            start = ln.GetIntersection(clippingRegionLines[1]);//BC
        }
        else if(startPointBits.bit2 == 1)
        {
            start = ln.GetIntersection(clippingRegionLines[0]);//AB
        }
        else if(startPointBits.bit1 == 1)
        {
            start = ln.GetIntersection(clippingRegionLines[2]);//CD
        }


        if(endPointsBits.bit4 == 1)
        {
            end = ln.GetIntersection(clippingRegionLines[3]);//DA
        }
        else if(endPointsBits.bit3 == 1)
        {
            end = ln.GetIntersection(clippingRegionLines[1]);//BC
        }
        else if(endPointsBits.bit2 == 1)
        {
            end = ln.GetIntersection(clippingRegionLines[0]);//AB
        }
        else if(endPointsBits.bit1 == 1)
        {
            end = ln.GetIntersection(clippingRegionLines[2]);//CD
        }

        return Line2d(start.Round(), end.Round());
    }
public:
    Line2d GetClippedLine()
    {
        Point2d min = rectangle.GetStart();
        Point2d max = rectangle.GetEnd();

        startPointBits.PointToBits(max, min, line.GetStart());
        endPointsBits.PointToBits(max, min, line.GetEnd());

        std::vector<Line2d> clippingRegionLines = rectangle.GetLines();

        Line2d tempLine = this->line;
        Bits start = startPointBits;
        Bits end = endPointsBits;

        while(start.IsClippingCandidate(end))
        {
            tempLine = GetClippedLine(clippingRegionLines, tempLine);

            Point2d startP = tempLine.GetStart();
            Point2d endP = tempLine.GetEnd();

            start.PointToBits(max, min, startP);
            end.PointToBits(max, min, endP);

            Coordinates2d::Draw(tempLine);
        }

        return tempLine;
    }
};

#define LINENUM 3

int main()
{
    Line2d ln(Point2d(-120, -40), Point2d(270, 160)); 
    Rectangle2d rect(Point2d(0, 0), Point2d(170, 120)); 

    Coordinates2d::ShowWindow("Cohen-Sutherland Line Clipping");
    Coordinates2d::Draw(ln);
    Coordinates2d::Draw(rect);  

    ClippingLine2d clip(rect, ln);

    Line2d clippedLine = clip.GetClippedLine();

    Coordinates2d::Draw(clippedLine);

    Coordinates2d::Wait();

    return 0;
}

The GetClippedLine() is stuck in an infinite loop. Coz, Bit3 of end-point of line always remains 1..

---

Down-voters and close-voters, please care to leave a comment.

Answer 1

The == operator in your Bits class contains a bug:

bool operator == (Bits & b)
{
    bool b1 = bit1 == b.bit1;
    bool b2 = bit2 == b.bit2; // <-- change bit1 to bit2
    bool b3 = bit3 == b.bit3; // <-- change bit1 to bit3
    bool b4 = bit4 == b.bit4; // <-- change bit1 to bit4

    if(b1==true && b2==true && b3==true && b4==true) return true;
    else return false;
}

The operator function is called from IsClippingCandidate() inside GetClippedLine()

Also, your clipping test is comparing to zero, and returning 1 (needs to be clipped) if the end-point of the line is grater than or equal to the clipping line, which means that if it gets clipped exactly to the line it will always be 1. So, change the comparison to be greater than instead of greater than or equal.

int Sign(int a)
{
    if(a>0) return 1;
    else return 0;
}

Also, if you are getting inaccurate results you can try doing the clipping in floating point instead of integer, in which case you should change the type of a to float or double and add a small tolerance to the comparison e.g. if(a > 0.0001f)

The clipping function should execute as long as there are bits set in start or end, so change IsClippingCandidate to OR the two together and return false when the result is zero (no bits are set in either) and true otherwise:

bool IsClippingCandidate(Bits & bits)
{
    Bits zeroBits;
    Bits orredBits = *this | bits;

    if(orredBits == zeroBits) return false;
    else return true;
}

You can also test whether the line is completely outside the clipping region and can be discarded like this:

bool IsInvisible(Bits & bits)
{
    Bits zeroBits;
    Bits andedBits = *this & bits;

    if(andedBits == zeroBits) return false;
    else return true;
}

If both points are outside a given clipping line then the line is invisible.