GP32 Bounded Line Segment

[pea]

Hi all,

Though it is a relatively simple task, to save me coding it from scratch, does anybody have a function that crops a line segment to fit a bounding area? Pref. floating point (I will convert it to fixed point).

Example.
I have the line p1 = -50,-50; p2 = 400,300;
This line obviously is longer than the screen, and starts and ends out of the screen.

The slow way would be to simply calculate each pixel, then test whether it is on the screen, and then draw it if it is.

The faster way would be to calculate new endpoints based on a bounding rect (the screen) and then draw the line with no testing to see if it is on the screen.

There is the overhead of recalculating the end points, but this will hopefully be faster than calculating the position of all the pixels that aren't actually drawn, and the checking of each and every pixel to be within the bounds.

I already have a half-pie implementation which I wrote that draws antialised lines based on the wu principle (very fast antialiasing), but it currently only crops the x axis. I am sure someone has come up with a fast crop routine in the past.

 

[mrsnature]

try a google search for "cohen and sutherland 2d clipping algorithm", if you can't find what you need i'll get some books out and take a look..

it works for clipping straight lines to a rectangular clipping boundry

 

[mrsnature]

try http://www.cse.ohio-state.edu/~hwshen/681/0118.pdf

got some clear descriptions of clipping algorythms, you should be able to code them up without too much trouble

 

[pea]

Nice and Nice! The Barsky algorthm looks good too. Thanks for that.

 

[pea]

To all interested.

I now have a fast antialised line routine (based on the Wu algorithm - just shifts and adds/subtracts) - however I then use full alpha to render it, so if the line crosses different colours on the screen, it all looks nice and pretty

The function also includes clipping to keep the line within a boundary (uses Liang-Barsky algorithm) - useful when keeping lines within the framebuffer, or within a sprite. And it all uses fixed point math.

Example output:
I drew a filled rectangle to the screen first so you can see where the clipping rect is, and then drew two sets of lines in different colours to show the antialiasing/alpha working:

 

[Drag]

I feel kinda weird because I sometimes get excited over big mathy things like this.

Those are some very nice looking lines. Right now, I'm working out way to 'interpolate' between 4 2d points, like if I wanted to get a value in between 4 points in an array, like if I were looking for the height of a specific point in between 4 2d points making up a plate or a tile or something. I think I figured it out though.

Well anyway, I'm a bit curious, what will you use those lines for?

Edit: Actually, what's kinda boggling me, line related, is how to drow them without anti-aliasing...

like if I draw the line horizontally, the slope can't be any larger than 1, or else the line will break apart into just dots. I think I can overcome this by checking the slope of the line, and then using that to determine whether I should draw this line horizontally or vertically (inversing the slope, so the line reaches the points correctly)

 

[pea]

re: 4 2d point interpolation
What you mean is that you have 4 points that indicate the corners of the tile? To interpolate here, break it down into x and y, and interpolate each of those seperatly to get your new point.

For example: Find 70% along and 80% down into the tile bounded by 30,40 and 70,80
- NOTE: If the tile is rectangular, you only need two points to define it, not 4
Next:
ny = interpolate between y1 and y2 by 80% (40 and 80)
nx = interpolate between x1 and x2 by 70% (30 and 70)

There is some interpolation code on my website:
snippet: Pea - Linear interpolation
snippet: Pea - Linear interpolation using fixed point math.

But you can use a simpler case whereby:

float interpolate( float a, float b, float amount ){
	return a + (b-a) * amount;
}

To use that exact code, this is what you would do:

// Top left
p1.x = 30;
p1.y = 40;
// Bottom right
p2.x = 70;
p2.y = 80;

// Interpolate for X
p3.x = interpolate( p1.x, p2.x, 0.7 ); // 70% accross tile
p3.y = interpolate( p1.y, p2.y, 0.8 ); // 80% down

re: Use of lines
At the moment they are only used to draw the borders, shadows, highlights etc on windows in GPDesktop.

re: Slope greater or equal to 1
Exactly how I do it! The code to use is something like this:

// Slope
dx = x2-x1; adx = (dx < 0 ? -dx : dx); // delta x, and abs(delta x) 
dy = y2-y1; ady = (dy < 0 ? -dy : dy); // delta y, and abs(delta y)

if (adx>ady){
	// line horizontal based

	if (ady==0){
  // line exactly horizontal
	}
}else{
	// line vertical based

	if (adx==0){
  // line exactly vertical
	}
}