i know theres been a lot of intersection questions on the boards lately, and i thought i had seen this one, but i looked through the last 30 days (manually..."search" wasnt much use) and no dice. basically i have to clip a 2d line to the screen. the brute force method is obvious and simple, but i just implemented bresenham''s algorithm and it seems like such a waste. any one have really fast clipping suggestions? i figure i need to quickly determine if the line is in or out, as most of them will be either. only then will i clip. i googled it and mostly got big-o studies on an n number of intersections on the screen...while i only need really really fast clipping on one line segment. i did pick up on a method using a determinant of some matrix...but i couldnt find anything more than a mention. so yeah...any ideas?

as a quick first test just check if both ends of the line are to the left of the left-hand edge of the screen, to the right of the right-hand edge of the screen, etc... if they are, they are outside...

then i guess the next test you wanna do is if both vertices are contained within the screen area, and then finally do the intersection between the line and the edges of the screen...

depends what your trying to do really, but if you have a lot of stationary lines spread over a large area... the fastest would probably be to build a quadtree...

quote:Original post by SpaceDude
as a quick first test just check if both ends of the line are to the left of the left-hand edge of the screen, to the right of the right-hand edge of the screen, etc... if they are, they are outside...

then i guess the next test you wanna do is if both vertices are contained within the screen area, and then finally do the intersection between the line and the edges of the screen...

depends what your trying to do really, but if you have a lot of stationary lines spread over a large area... the fastest would probably be to build a quadtree...

right, thats all pretty much as i figured. this is a single line drawing algorithm though...i just want to avoid wrap around and accessing non existant array indeces. i guess ill just code the version you basically outlined. any one have any super fast intersection methods? (divides = bleh)

quote:Original post by oliii
the search brought up

Clipping algorithms

yeah, thats perfect, thanks. im a bit of a basic-rendering-algorithms-optimization whore so i was just working on my lines...i thought someone had come up with a sneaky way of doing this.

Looks like oliii has solved this problem, but I thought I''d mention something to anyone (esp beginners) who may trip across this thread:

Bresenham''s algorithm is a line _drawing_ algorithm and not designed for (and thus not very good at) line _clipping_. While the two are related, clipping and drawing are not the same thing. Morale of the story: make sure you''re selecting the right tool for the task at hand.