Skip to main content
GameDev.net gamedev.net
🔒 Locked

Question on Cohen-Sutherland Line Clipping Algorithm.

Started by Warren Sep 12, 2004 at 1:33 PM 6 replies 8.7k views
Original Post
Warren
Warren
Alright, so I am implementing this algorithm. I have a book, Tips and Tricks of the Windows Game Programming Guru's that has some source code. I don't like to just copy/paste. I like working through the math. Anyways, on with the question. The following code is basically copy/paste from the books source CD with name changes. I am working through the math before I recode it my way. 

switch(p1code)
{
	case CLIP_REGION_C:
	{
		break;
	}
	case CLIP_REGION_N:
	{
		clipStartY = clipRect->top;
		clipStartX = startX + tempVar+(clipRect->top-startY)*(endX-startX)/(endY-startY);
		break;
	}
	case CLIP_REGION_S:
	{
		clipStartY = clipRect->bottom;
		clipStartX = startX + tempVar+(clipRect->bottom-startY)*(endX-startX)/(endY-startY);
		break;
	}
	case CLIP_REGION_W:
	{
		clipStartX = clipRect->left;
		clipStartY = startY + tempVar+(clipRect->left-startX)*(endY-startY)/(endX-startX);
		break;
	}
	case CLIP_REGION_E:
	{
		clipStartX = clipRect->right;
		clipStartY = startY + tempVar+(clipRect->right-startX)*(endY-startY)/(endX-startX);
		break;
	}
// these cases are more complex, must compute 2 intersections
	case CLIP_REGION_NE:
	{
		// north hline intersection
		clipStartY = clipRect->top;
		clipStartX = startX + tempVar+(clipRect->top-startY)*(endX-startX)/(endY-startY);
		// test if intersection is valid, of so then done, else compute next
		if (clipStartX < clipRect->left || clipStartX > clipRect->right)
		{
			// east vline intersection
			clipStartX = clipRect->right;
			clipStartY = startY + tempVar+(clipRect->right-startX)*(endY-startY)/(endX-startX);
		} // end if
	break;
	}
	case CLIP_REGION_SE:
	{
		// south hline intersection
		clipStartY = clipRect->bottom;
		clipStartX = startX + tempVar+(clipRect->bottom-startY)*(endX-startX)/(endY-startY);	
		// test if intersection is valid, of so then done, else compute next
		if (clipStartX < clipRect->left || clipStartX > clipRect->right)
		{
			// east vline intersection
			clipStartX = clipRect->right;
			clipStartY = startY + tempVar+(clipRect->right-startX)*(endY-startY)/(endX-startX);
		} // end if
		break;
	}
	case CLIP_REGION_NW: 
	{
		// north hline intersection
		clipStartY = clipRect->top;
		clipStartX = startX + tempVar+(clipRect->top-startY)*(endX-startX)/(endY-startY);
		// test if intersection is valid, of so then done, else compute next
		if (clipStartX < clipRect->left || clipStartX > clipRect->right)
		{
			clipStartX = clipRect->left;
			clipStartY = startY + tempVar+(clipRect->left-startX)*(endY-startY)/(endX-startX);	
		} // end if
		break;
	}
	case CLIP_REGION_SW:
	{
		// south hline intersection
		clipStartY = clipRect->bottom;
		clipStartX = startX + tempVar+(clipRect->bottom-startY)*(endX-startX)/(endY-startY);	
		// test if intersection is valid, of so then done, else compute next
		if (clipStartX < clipRect->left || clipStartX > clipRect->right)
		{
			clipStartX = clipRect->left;
			clipStartY = startY + tempVar+(clipRect->left-startX)*(endY-startY)/(endX-startX);	
		} // end if
		break;
	}
	default:
	{
		break;
	}
} // end switch
// determine clip point for p2
switch(p2code)
{
	case CLIP_REGION_C:
	{
		break;
	}
	case CLIP_REGION_N:
	{
		clipEndY = clipRect->top;
		clipEndX = endX + (clipRect->top-endY)*(startX-endX)/(startY-endY);
		break;
	}
	case CLIP_REGION_S:
	{
		clipEndY = clipRect->bottom;
		clipEndX = endX + (clipRect->bottom-endY)*(startX-endX)/(startY-endY);
		break;
	}
	case CLIP_REGION_W:
	{
		clipEndX = clipRect->left;
		clipEndY = endY + (clipRect->left-endX)*(startY-endY)/(startX-endX);
		break;
	}
	case CLIP_REGION_E:
	{
		clipEndX = clipRect->right;
		clipEndY = endY + (clipRect->right-endX)*(startY-endY)/(startX-endX);
		break;
	}
	// these cases are more complex, must compute 2 intersections
	case CLIP_REGION_NE:
	{
		// north hline intersection
		clipEndY = clipRect->top;
		clipEndX = endX + tempVar+(clipRect->top-endY)*(startX-endX)/(startY-endY);
		// test if intersection is valid, of so then done, else compute next
		if (clipEndX < clipRect->left || clipEndX > clipRect->right)
		{
			// east vline intersection
			clipEndX = clipRect->right;
			clipEndY = endY + tempVar+(clipRect->right-endX)*(startY-endY)/(startX-endX);
		} // end if
		break;
	}
	case CLIP_REGION_SE:
	{
		// south hline intersection
		clipEndY = clipRect->bottom;
		clipEndX = endX + tempVar+(clipRect->bottom-endY)*(startX-endX)/(startY-endY);	
		// test if intersection is valid, of so then done, else compute next
		if (clipEndX < clipRect->left || clipEndX > clipRect->right)
		{
			// east vline intersection
			clipEndX = clipRect->right;
			clipEndY = endY + tempVar+(clipRect->right-endX)*(startY-endY)/(startX-endX);
		} // end if
		break;
	}
	case CLIP_REGION_NW: 
	{
		// north hline intersection
		clipEndY = clipRect->top;
		clipEndX = endX + tempVar+(clipRect->top-endY)*(startX-endX)/(startY-endY);
		// test if intersection is valid, of so then done, else compute next
		if (clipEndX < clipRect->left || clipEndX > clipRect->right)
		{
			clipEndX = clipRect->left;
			clipEndY = endY + tempVar+(clipRect->left-endX)*(startY-endY)/(startX-endX);	
		} // end if
		break;
	}
	case CLIP_REGION_SW:
	{
		// south hline intersection
		clipEndY = clipRect->bottom;
		clipEndX = endX + tempVar+(clipRect->bottom-endY)*(startX-endX)/(startY-endY);	
		// test if intersection is valid, of so then done, else compute next
		if (clipEndX < clipRect->left || clipEndX > clipRect->right)
		{
			clipEndX = clipRect->left;
			clipEndY = endY + tempVar+(clipRect->left-endX)*(startY-endY)/(startX-endX);	
		} // end if
		break;
	}
	default:
	{
		break;
	}
}
Neways, in some of the calculations where we multiply by the slope (startY-endY)/(startX-endX) or the inverse slope, (StartX-EndX)/(StartY-endY) he is adding 0.5. In the code above, all 0.5's are replaced by tempVar. I am assuming 0.5 is added when we are rounding from a double to an int and the 0.5 makes the rounding more accurate. In C++ double to int just loses the decimal information. The + 0.5 essentially rounds for us. Neways, why is it not there for ALL of the places where there is going to be a decimal value? It would make sense to always add 0.5 before casting to integer would it not? I've set tempVar to both 0.5 and 0.0 and run the code, drawing 16 clipped lines every time. I haven't saved the results and done a pixel to pixel comparasin but the images look identical. Any thoughts on the issue would be appreciated. Do you figure his source code is just missing a couple 0.5's?
wyrzy
wyrzy
Well, I'm not trying to be smart, but the line-clipping code would probably depend on how you are drawing the lines in the first place.
Also, if you don't want to worry about the rounding in the first place, then just convert floats to ints using assembly, which will do the rounding for you. I've found it helpful (some people may think confusing) to add an Int() function to my projects that converts floats to ints using assembly. It also avoids overhead associated with _ftol.
Warren
Warren
Hmm, maybe i need to explain the question better. My line drawing code works. My line clipping code works. So if I specify a RECT of 10,10,1014, 758 and try to draw lines in it, they will be clipped to the above RECT with my code.

It works.

The only question I had was why is he using +0.5 for some of the floating point rounding and not using it for others. As far as I can tell, its a typo in his code or he is making some assumptions about which end point he is receiving first. IE, a line from p1 to p2, where p1.x < p2.x is always true. Either way, its dumb cause I don't like code that requires that depends on proper input to be correct.

Too much time making end user software at work...

Neways, I'll be changing the code to suit myself later. Right now I need to figure out the +0.5 discrepancy.

Any thoughts?
lubby
lubby
I would say its because the pixel is a point not a square, so a start point 0,0 would reference the left top corner or left bottom corner of the pixel, depending on your coord system. By Adding 0.5 the start point is being set to the center of the pixel as it should be. If it were not doing this you would find slight inacuracies with clipping coords, these would be more exagerated as the clipping area increased in size.

edit:
You should always ensure your line is running from top->bottom or bottom->top (keep same for all lines) when passed to the clip algo, I am guessing you are also using Bresenhams midpoint line as well, you should treat this the same way.
Skizz
Skizz
That's not a particularly good implementation of the S-C line clipping algorithm. There's no need for any floating point operations at all, if you really want to do rounding, the following can be used:
clipped_x = (dx * 2 * dist_y / dy + 1) / 2
although I've never needed to use the rounding (you'll be out by, at most, one pixel).
The version I have uses bit codes to identify the location of the end points of the line to clip and only clips one edge at a time. The clipping is done in a loop until the line is totally within the clip region or the line is totally outside the clip region. The bit codes used are:
0011 | 0010 | 0110------------------0001 | 0000 | 0100------------------1001 | 1000 | 1100

where the 0000 section represents the area the line is clipped to. Note that if the end point is above the clip region the clip code has bit 1 set, if it's to the right, bit 2 is set and so on.
Once you've got the bit codes for the two end points, then you can do a trivial rejection:
if the end point bit codes, when or'd together, is 0 then the line doesn't need clipping;
if the end point bit codes, when and'd together, is not zero then the line is totally clipped.
You then clip against any one line segment that the line crosses (so, if bit code & 1000 != 0 then clip against bottom edge), and then repeat the process.

Skizz

Edit: I might post my code if I can find it.
Warren
Warren
Skizz, thanks I am using the bit codes you listed already. Basically I send the clipping part both end points via reference, and it clips them against the bounding RECT I pass in.

The code I cut is the part that checks the endpoints against the bounding RECT.

After coming up with the codes for the endpoints, I run em through to see where they intersect with the bounding RECT and use the given math to compute the new (X,Y) values after clipping.

So if I have a clipping RECT from (10,10) to (100,100)

and a line from (5,45) to (50,45)i'd end up with clipped endpoints of (10,45) to (50,45).

It works with tempVar as both 0.5 and as 0.0.

I just can't figure out why this code sample is missing the 0.5 in some of the calculations?

Is it a typo or does it have something to do with the way the rasterization is done???

Lubby, I don't understand what you were trying to say...

last time I checked, the screen of a computer was divided into a finite number of pixels. Each pixel could be either ON or OFF so to speak. How does adding 0.5 move the pixel to the right place?

Thanks guys.
lubby
lubby
Quote:

last time I checked, the screen of a computer was divided into a finite number of pixels. Each pixel could be either ON or OFF so to speak. How does adding 0.5 move the pixel to the right place?



You are exactly right, literally, but not acording to the midpoint algorithm. Its a little hard to explain in another way than I have but I shall give it a try.

Imagine the midpoint (m) between two adjacent pixels. where the pixel is is treated without the 0.5 (x) being the left top. Draw it on graph paper to see this more clearly.
+------+------+|x     |      ||      |      ||o     |      |+------+------+|x     |      ||      |      ||      |      |+------+------+Now will do it again with the 0.5+------+------+|      |      ||  x   |      ||      |      |+--m---+------+|      |      ||  x   |      ||      |      |+------+------+

In the midpoint algorithm, when it comes to decision time to select which pixel to fill next. The first case will select the top pixel, but in the second case the midpoint will slect (depending on your implementation) the top or bottom pixel. This would be the same when any decisions variables are tied. The decision var being the distance from the midpoint to the nearest pixel.

I would hesitant a guess that you have this in your clipping algorithm to coincide with a drawing algorithm probably supplied in an earlier chapter. I have not read that book, but the reason I state the above, is to my knowledge the only reason why you would have those offsets in the clipping algorithm.
Warren
Warren
Yeah, I've built a version of the Bresenham line drawing algorithm.

The midpoint one you describe. With the E, and NE pixel choices.

Before that algorithm is called, I call this clipping algorithm to clip the endpoints of my line. After the endpoints are clipped, I call my Brenenham implementation to actually draw the line between the new, clipped endpoints.

Like I say, the code works fairly well and handles all lines, regardless of slope, or order of endpoints, and it clips properly.

What I can't figure out is why he has that 0.5 on some of the calculations and not others.

Maybe this will help:

What is different about the cases where there is a +0.5 -vs- the cases where there is no +0.5.

Remember I replaced the 0.5's with tempVar so I could vary the floating point number.

Anyone?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.