Cohen-Sutherland 2D line clipping algorithm

Question

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.

Answer 1

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

• user3804: 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?