Archived

This topic is now archived and is closed to further replies.

intersections and clipping

This topic is 4997 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites