Cohen-Sutherland 2D line clipping algorithm

Please, review the following implementation of Cohen-Sutherland line clipping algorithm (p-91):

Bits.cpp

class Bits
{
public:
int bit1;
int bit2;
int bit3;
int bit4;
public:
Bits()
{
bit1 = bit2 = bit3 = bit4 = 0;
}
Bits(Bits & b)
{
*this = b;
}
Bits & operator & (Bits & b)
{
bit1 = bit1 & b.bit1;
bit2 = bit2 & b.bit2;
bit3 = bit3 & b.bit3;
bit4 = bit4 & b.bit4;
return *this;
}
Bits & operator | (Bits & b)
{
bit1 = bit1 | b.bit1;
bit2 = bit2 | b.bit2;
bit3 = bit3 | b.bit3;
bit4 = bit4 | b.bit4;
return *this;
}
Bits & operator = (Bits & b)
{
bit1 = b.bit1;
bit2 = b.bit2;
bit3 = b.bit3;
bit4 = b.bit4;
return *this;
}
bool operator == (Bits & b)
{
if(bit1 == b.bit1 && bit2 == b.bit2 && bit3 == b.bit3 && bit4 == b.bit4) return true;
else return false;
}
private:
int Sign(double a)
{
if(a>0.01f) return 1;
else return 0;
}
int GetBit1(double y, double yMax)
{
return Sign(y - yMax);
}
int GetBit2(double y, double yMin)
{
return Sign(yMin - y);
}
int GetBit3(double x, double xMax)
{
return Sign(x - xMax);
}
int GetBit4(double x, double xMin)
{
return Sign(xMin - x);
}
public:
void PointToBits(Point2d & clipMax, Point2d & clipMin, Point2d & pnt)
{
bit1 = GetBit1(pnt.y, clipMax.y);
bit2 = GetBit2(pnt.y, clipMin.y);
bit3 = GetBit3(pnt.x, clipMax.x);
bit4 = GetBit4(pnt.x, clipMin.x);
}
bool IsClippingCandidate(Bits & bits)
{
Bits zeroBits;
Bits andedBits = *this | bits;

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


ClippingLine2d.cpp

#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);
}

return tempLine;
}
};

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

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

ClippingLine2d clip(rect, ln);

Line2d clippedLine = clip.GetClippedLine();

Coordinates2d::Draw(clippedLine, Yellow);

Coordinates2d::Wait();

return 0;
}


The whole Visual C++ 2008 Express source code can be found here.

Extra Copying

ClippingLine2d(Rectangle2d rect, Line2d line)
{
this->rectangle = rect;
this->line = line;
}


This will default-initialize rectangle and line, copy the input parameters into rect and line, and then copy them again into your member variables. You can save a copy and an extra initialization by direct initializing them from references to const:

ClippingLine2d(Rectangle2d const& rect, Line2d const& line)
: rectangle(rect)
, line(line)
{ }


The same is true of GetClippedLine. This:

Line2d GetClippedLine(std::vector<Line2d> clippingRegionLines, Line2d ln)


does an extra copy of the vector and the Line2d. This:

Line2d GetClippedLine(std::vector<Line2d> const& clippingRegionLines, Line2d const& ln)


does not.

Is this copy even necessary?

Bits start = startPointBits;
Bits end = endPointsBits;


Bits

Now that you posted the code, lots to say here. First, there is a standard C++ container to use for storing bits: std::bitset. Use it:

class Bits {
std::bitset<4> bits;
...
};


That way you don't need to write the copy constructor/assignment operators. For the other other operators, they're wrong in two ways:

Bits & operator & (Bits & b)


That actually implements &=. It'd be pretty surprising to users if they did Bits c = a & b; and found out that a had changed too! Also there's no reason to restrict the input to non-const references. This should become:

Bits& operator&=(const Bits& b) {
bits &= b.bits;
return *this;
}

Bits operator&(const Bits& b) const {
Bits lhs(*this);
lhs &= b;
return lhs;
}


And similarly for operator|.

For operator==, writing if (expr) return true else return false is an antipattern. It should just be return expr. Also, comparison should be const:

bool operator==(const Bits& rhs) const {
return bits == rhs.bits;
}


Next the main methods. PointToBits makes zero sense as a member function. It should be a free function. Also you have 4 one-line functions that are all only used in one place. That makes it harder to read without adding any value. Just write them all inline:

Bits PointToBits(Point2d const& clipMax, Point2d const& clipMin, Point2d const& pnt)
{
Bits b;
static const double epsilon = 0.01;

b[0] = pnt.y - clipMax.y > epsilon;
b[1] = clipMin.y - pnt.y > epsilon;
b[2] = pnt.x - clipMax.x > epsilon;
b[3] = clipMin.x - pnt.x > epsilon;

return b;
}


You'll have to add operator[] on Bits. It'll be easy.

Lastly, IsClippingCandidate(). We're not modifying this (or at least we wouldn't be if operator| was correct), so the function should be const. The variable is named andedBits - so presumably you meant to use & and not |. The argument should be taken by const reference. And we have the same antipattern about returning true or false. The whole thing can be reduced to:

bool IsClippingCandidate(Bits const& b) const {
return (bits & b.bits).any(); // check if any of the bits specified
// by 'b' are set
}


Repetition

In the overload of GetClippedLine that takes a vector, you have the same block twice. You can refactor that:

size_t bitsToIndex(Bits const& bits) {
if (bits.bit4 == 1) {
return 3; // DA
}
else if ( ... ) { ... }
else {
return -1;
}
}

Point2d getIntersectionPoint(std::vector<line2d> const& clippingRegionLines,
Line2d const& ln, bool isStart)
{
Bits& bits = isStart ? startPointBits : endPointBits;
size_t idx = bitsToIndex(bits);

if (idx != -1) {
return ln.GetIntersection(clippingRegionLines[idx]);
}
else {
return isStart ? ln.GetStart() : ln.GetEnd();
}
}

Line2d GetClippedLine(std::vector<Line2d> const& clippingRegionLines, Line2d const& ln) {
return Line2d(
getIntersectionPoint(clippingRegionLines, ln, true).Round(),
getIntersectionPoint(clippingRegionLines, ln, false).Round()
);
}


That's a lot easier to grok. Could even avoid the awkward bool in there by introducing:

struct Start { };
struct End { };

Point2d get(Rectangle2d const& rect, Start ) { return rect.GetStart(); }
Point2d get(Rectangle2d const& rect, End ) { return rect.GetEnd(); }
// likewise for other cases


Then:

template <typename SIDE>
Point2d getIntersectionPoint(std::vector<line2d> const& clippingRegionLines,
Line2d const& ln, SIDE side)
{
size_t idx = bitsToIndex(getBits(side));

if (idx != -1) {
return ln.GetIntersection(clippingRegionLines[idx]);
}
else {
return get(ln, side);
}
}

Line2d GetClippedLine(std::vector<Line2d> const& clippingRegionLines, Line2d const& ln) {
return Line2d(
getIntersectionPoint(clippingRegionLines, ln, Start()).Round(),
getIntersectionPoint(clippingRegionLines, ln, End()).Round()
);
}

• OK. It works, but, the question is, Is the algorithm implemented correctly? I suspect that the while loop is actually not needed at all to implement the algorithm. What do you think?
– user3804
Commented Jul 14, 2015 at 18:37