Cohen–Sutherland Algorithm Modification

Hi,
My question is regarding a modification I was considering making to the Cohen-Sutherland algorithm to remove the need for a loop, specifically I want to know if the performance benefits of such a modification would outweigh the downside of the extra calculations. The modification I am making is this:
In the original algorithm, lines are clipped first against the vertical and then against the horizontal edges, so in worst case a line may need to be clipped 4 times, twice on each end. I modified the algorithm to use two slopes -- the slope of the line itself, and the line between the outer endpoint and the corner of the clipping region, to determine whether to clip the line against the vertical or the horizontal boundary. The code (in Java) looks like this:
...

double x = p1.getX();
double y = p1.getY();
double cornerSlope = (y - ymax)/(x - xmax);
double lineSlope = (y - p2.getY()) / (x - p2.getX());
if(cornerSlope < lineSlope) {
// chop against top edge
double yClipped = ymax;
double xClipped = (y - ymax) / lineSlope;
return new Point2D.Double(xClipped, yClipped);
} else {
// chop against left edge
....
}
...
Above is just a snippet of a function that is part of the algorithm, it is called after trivial accept/reject cases have been handled and returns the intersect point given p1 as the outer point and p2 as either the inner or the outer point (outer/inner with respect to the clipping region). It's called twice with parameters flipped if the line sticks out on both ends.

So I was wondering whether it is better to clip twice on each end as in original algorithm or use this modification, calculate the slopes, and clip only once on each end? Also, is this something that maybe is well-known/has been done/documented/has a name/etc.? Please forgive /correct any mistakes as I'm a bit new to this and I just coded this tonight/this morning. Thanks for any replies.

To clarify my question here's the code, I finished it today and it seems to work, so if someone can please take a look at it and tell me if my approach to line clipping makes sense I'd really appreciate it. It's difficult to know if you're on the right track without feedback, this is part of my first big project and I've been working on it for a while and I was hoping someone here might know something about line clipping and whether it makes sense to get rid of the loop in the algorithm or not. So here's the code:

Code:

---


import java.awt.geom.*;

public class ClippingWindow {
        private double xmin;
        private double xmax;
        private double ymin;
        private double ymax;

        public ClippingWindow(double xmin, double xmax, double ymin, double ymax) {
                this.xmin = xmin;
                this.xmax = xmax;
                this.ymin = ymin;
                this.ymax = ymax;
        }

        /**
        * Clips the line against the window. If the line is outside the window,
        * rejects it by returning a null. If part of it is inside the window,
        * returns the clipped part.
        *
        * Implements the Cohen-Sutherlad Clipping Algorithm with a modification
        * to eliminate the loop. As with Cohen-Sutherland, first it is determined
        * whether p1 or p2 is outside. However instead of chopping right away
        * four additional cases are discriminated first. In the original,
        * the procedure is:
        *        if(p is to the left) chop against the left edge
        *        else if(p is to the right) chop against the right edge
        *        else if(p is below) chop against the bottom edge
        *        else if(p is above) chop against the top edge
        * However this opens up the possibility that in each of those four cases,
        * a combination, i.e. a corner case, might occur. E.g. p might be
        * both to the left and above, and in that case if the slope of the line
        * is greater than the slope connecting p to the corner another iteration
        * will be required before the line is fully trimmed.
        *        To avoid the need to repeat the procedure, the area outside the window
        * is divided into 8 zones, further subdivided into two categories - corner
        * zones and side zones. Corner zones are upper left, upper right, lower left,
        * and lower right. Side zones are left, upper, right, and lower.
        *        By testing if the outside point is in a corner or a side zone the
        * method can determine how to chop the line. The procedure is this:
        *        if(p is in a side zone)
        *                follow the procedure as before once and return, one pass is sufficient.
        *        if(p is in a corner zone)
        *                calculate slope between p and corner (corner slope)
        *                and compare it to the slope of the line (line slope).
        *                if(p is in upper left)
        *                        if(corner slope is less)
        *                                chop against top edge
        *                        else
        *                                chop against left edge
        *                if(p is in upper right)
        *                        if(corner slope is less)
        *                                chop against top edge
        *                        else
        *                                chop against right edge
        *                if(p is in lower left)
        *                        if(corner slope is less)
        *                                chop against bottom edge
        *                        else
        *                                chop against left edge
        *                if(p is in the lower right)
        *                        if(corner slope is less)
        *                                chop against bottom edge
        *                        else
        *                                chop against right edge
        *                The above procedure completes the clipping in one pass.
        * @param line
        * @return
        */
        public Line2D clip(Line2D line) {
                Point2D p1 = line.getP1();
                Point2D p2 = line.getP2();

                byte p1code = code(p1);
                byte p2code = code(p2);

                if((p1code | p2code) == 0) { // trivial accept
                        return new Line2D.Double(p1, p2);
                }
                if((p1code & p2code) != 0) { // trivial reject
                        return null;
                }
                Point2D p1clipped = p1;
                Point2D p2clipped = p2;
                if(p1code != 0) { // p1 is outside
                        p1clipped = clipEnd(p1, p2, p1code);
                        if(p2code != 0) { // p2 is outside as well
                                p2clipped = clipEnd(p2, p1, p2code);
                        }
                        return new Line2D.Double(p1clipped, p2clipped);
                } else { // p2 must be outside and p1 must be inside
                        assert p2code != 0; // check to make sure p2 is indeed outside
                        assert p1code == 0; // check that p1 is actually inside
                        p2clipped = clipEnd(p2, p1, p2code); // clip on p2 side
                        return new Line2D.Double(p1clipped, p2clipped);
                }
        }

        private enum Edge {TOP, BOTTOM, LEFT, RIGHT};

        /**
        * This procedure clips the line with respect to p1, by assuming that
        * p1 is outside, and p2 is either inside or outside. It clips
        * the p1 end of the line to its intersection with the window boundary
        * and returns that point of intersection.
        * @param p1
        * @param p2
        * @param pcode
        * @return
        */
        private Point2D clipEnd(Point2D p1, Point2D p2, byte pcode) {
        /*        if(p is in a side zone)
        *                if(p is to the left) chop against the left edge
        *                else if(p is to the right) chop against the right edge
        *                else if(p is below) chop against the bottom edge
        *                else if(p is above) chop against the top edge
        *        if(p is in a corner zone)
        *                calculate slope between p and corner (corner slope)
        *                and compare it to the slope of the line (line slope).
        *                if(p is in upper left)
        *                        if(corner slope is less)
        *                                chop against top edge
        *                        else
        *                                chop against left edge
        *                if(p is in upper right)
        *                        if(corner slope is less)
        *                                chop against top edge
        *                        else
        *                                chop against right edge
        *                if(p is in lower left)
        *                        if(corner slope is less)
        *                                chop against bottom edge
        *                        else
        *                                chop against left edge
        *                if(p is in the lower right)
        *                        if(corner slope is less)
        *                                chop against bottom edge
        *                        else
        *                                chop against right edge
        */
                double p1x = p1.getX();
                double p1y = p1.getY();
                double p2x = p2.getX();
                double p2y = p2.getY();

                double delx = p2x - p1x;
                double dely = p2y - p1y;
               
                if((pcode & 0xF0) == 0) { // p1 is in a side zone
                        if((pcode & 8) != 0) { // p1 is to the left
                                // chop against the left edge
                                return chop(delx, dely, p1x, p1y, Edge.LEFT);
                        } else if((pcode & 2) != 0) { // p1 is to the right
                                // chop against the right edge
                                return chop(delx, dely, p1x, p1y, Edge.RIGHT);
                        } else if ((pcode & 1) != 0) { // p1 is below
                                // chop against the bottom edge
                                return chop(delx, dely, p1x, p1y, Edge.BOTTOM);
                        } else { // (pcode & 4) != 0, p1 is above
                                assert((pcode & 4) != 0);
                                // chop against the top edge
                                return chop(delx, dely, p1x, p1y, Edge.TOP);
                        }
                } else { // p1 is in a corner zone
                        assert (p1x < xmin || p1x > xmax) && (p1y < ymin || p1y > ymax);
                        // because p1x has to be outside [xmin, xmax] and
                        // p1y has to be outside [ymin, ymax], the line is neither
                        // horizontal nor vertical, so we don't have to worry about / by 0
                        // when finding slopes.

                        double lineSlope = dely / delx;
                        double cornerSlope;
                        if((pcode & 16) != 0) { // p1 is in the upper left
                                cornerSlope = (ymax - p1y) / (xmin - p1x);
                                if(cornerSlope < lineSlope) {
                                        // chop against top edge
                                        return chop(delx, dely, p1x, p1y, Edge.TOP);
                                } else {
                                        // chop against left edge
                                        return chop(delx, dely, p1x, p1y, Edge.LEFT);
                                }
                        } else if((pcode & 32) != 0) { // p1 is in the upper right
                                cornerSlope = (ymax - p1y) / (xmax - p1x);
                                if(cornerSlope < lineSlope) {
                                        // chop against top edge
                                        return chop(delx, dely, p1x, p1y, Edge.TOP);
                                } else {
                                        // chop against right edge
                                        return chop(delx, dely, p1x, p1y, Edge.RIGHT);
                                }

                        } else if((pcode & 64) != 0) { // p1 is in the lower left
                                cornerSlope = (ymin - p1y) / (xmin - p1x);
                                if(cornerSlope < lineSlope) {
                                        // chop against bottom edge
                                        return chop(delx, dely, p1x, p1y, Edge.BOTTOM);
                                } else {
                                        // chop against left edge
                                        return chop(delx, dely, p1x, p1y, Edge.LEFT);
                                }

                        } else { // (pcode & 128) != 0, p1 is in the lower right
                                assert((pcode & 128) != 0);
                                cornerSlope = (ymin - p1y) / (xmax - p1x);
                                if(cornerSlope < lineSlope) {
                                        // chop against bottom edge
                                        return chop(delx, dely, p1x, p1y, Edge.BOTTOM);
                                } else {
                                        // chop against right edge
                                        return chop(delx, dely, p1x, p1y, Edge.RIGHT);
                                }

                        }
                }
        }

        /**
        * Finds the intersection of the line and the given edge, i.e. chops
        * the line against the given edge, which is either LEFT, RIGHT, TOP, or
        * BOTTOM.
        * @param delx Quantity (p1x - p2x), delta x
        * @param dely Quantity (p1y - p2y), delta y
        * @param p1x
        * @param p1y
        * @param edge
        * @return
        */
        private Point2D chop(double delx, double dely, double p1x, double p1y, Edge edge) {
                double xClipped;
                double yClipped;
                switch(edge) {
                        case LEFT:
                                // chop against the left edge
                                xClipped = xmin;
                                yClipped = p1y + dely / delx * (xmin - p1x);
                                break;
                        case RIGHT:
                                // chop against the right edge
                                xClipped = xmax;
                                yClipped = p1y + dely / delx * (xmax - p1x);
                                break;
                        case BOTTOM:
                                // chop against the bottom edge
                                xClipped = p1x + delx / dely * (ymin - p1y);
                                yClipped = ymin;
                                break;
                        case TOP:
                                // chop against the top edge
                                xClipped = p1x + delx / dely * (ymax - p1y);
                                yClipped = ymax;
                                break;
                        default:
                                throw new IllegalArgumentException("Unknown Edge type encountered.");
                }
                return new Point2D.Double(xClipped, yClipped);
        }

        /*
        *    Forms a byte code word that represents the location of the end
        * point relative to the window.
        *    The 4 lower bits represent are used to code the position.
        *          In these 4 bits, 1 means yes, 0 means no.
        *    The sequence of 4 questions from left to right, i.e. lower to upper
        * bits is:
        *          bit 0: Is p below window?
        *    bit 1: Is p to the right of window?
        *    bit 2: Is p above window?
        *    bit 3: Is p to the left of window?
        *    In order to help identify points that fall into corner positions,
        * bits 5 through 8 are used to indicate which corner the point is in.
        * Either one of the upper bits is on, or they are all off indicating
        * the point is in a side zone. Corner zones are numbered 1 through 4
        * left to right, up to down:
        *          bit 4: Zone 1, upper left.
        *          bit 5: Zone 2, upper right.
        *      bit 6: Zone 3, lower left.
        *      bit 7: Zone 4, lower right.
        */
        private byte code(Point2D point) {
                byte code = 0;
                double x = point.getX();
                double y = point.getY();
                if(y < ymin) {
                        code |= 1 | 64 | 128;
                } else if (y > ymax) {
                        code |= 4 | 16 | 32;
                }
                if(x < xmin) {
                        code &= 16 | 64 | 0x0F;
                        code |= 8;
                } else if(x > xmax) {
                        code &= 32 | 128 | 0x0F;
                        code |= 2;
                } else {
                        code &= 0x0F; // clear upper bits
                }
               
                return code;
        }
}

---

Here's a JUnit test to go with it, I know it's lacking test cases but I didn't have time to add more:

Code:

---

import java.awt.geom.*;

import org.junit.*;
import static org.junit.Assert.*;

public class ClippingWindowTest {
        private static final boolean DEBUG = true;

        private static class TestCase {
                private ClippingWindow window;
                private Line2D line;
                private Line2D expected;

                public TestCase(ClippingWindow window, Line2D line, Line2D expected) {
                        this.window = window;
                        this.line = line;
                        this.expected = expected;
                }

                public void clipTest() {
                        Line2D clipped = window.clip(line);
                        if(DEBUG) {
                                printLine(line);
                                printLine(clipped);
                        }
                        assertLineEquals(expected, clipped, 0.001);
                }

                private void printLine(Line2D line) {
                        System.out.println("(" + line.getX1() + "," + line.getY1()
                                        + "),(" + line.getX2() + "," + line.getY2() + ")" );
                }

                private void assertLineEquals(Line2D expected, Line2D actual, double epsilon) {
                        Point2D ep1 = expected.getP1();
                        Point2D ep2 = expected.getP2();
                        Point2D ap1 = actual.getP1();
                        Point2D ap2 = actual.getP2();

                        double ep1x = ep1.getX();
                        double ep1y = ep1.getY();
                        double ep2x = ep2.getX();
                        double ep2y = ep2.getY();

                        double ap1x = ap1.getX();
                        double ap1y = ap1.getY();
                        double ap2x = ap2.getX();
                        double ap2y = ap2.getY();

                        assertEquals(ep1x, ap1x, epsilon);
                        assertEquals(ep1y, ap1y, epsilon);
                        assertEquals(ep2x, ap2x, epsilon);
                        assertEquals(ep2y, ap2y, epsilon);
                }
        }

        private TestCase[] testCases = {
                new TestCase(
                        new ClippingWindow(0,10,0,10),
                        new Line2D.Double(11,5,5,-1),
                        new Line2D.Double(10,4,6,0)),
                new TestCase(
                        new ClippingWindow(0,10,0,10),
                        new Line2D.Double(5,-1,-1,5),
                        new Line2D.Double(4,0,0,4)),
                new TestCase(
                        new ClippingWindow(0,10,0,10),
                        new Line2D.Double(-1,5,5,11),
                        new Line2D.Double(0,6,4,10)),
                new TestCase(
                        new ClippingWindow(0,10,0,10),
                        new Line2D.Double(5,11,11,5),
                        new Line2D.Double(6,10,10,6))
        };

        @Test
        public void clipTest() {
                for(TestCase testCase : testCases)
                        testCase.clipTest();       
        }       
}

---

If I put code lines which does the majority of the computation in your example code, it would be the following lines:

Code:

---


  cornerSlope = (ymax - p1y) / (xmin - p1x); //in clipEnd()
  ...
  if(cornerSlope < lineSlope) {  //in clipEnd()
  ...
  xClipped = p1x + delx / dely * (ymin - p1y); //in chop()

---

The Cohen-Sutherland algorithm has a max of 4 passes, where on each pass it mainly calculates

Code:

---

x = x0 + delx * (ymax - y0) / dely;

---

But since there is no consequence to the selection of which point goes first, it can be done in max of 2 parallel passes.
Since this algorithm is usually implemented in hardware pipeline, the loop is implemented in parallel, and you get better latency.

On the other hand, I think your code may not be parallelized very well since the decision where to clip is based on the slope check branch.

Regards,
Zachm