c++ check if 2d line segments cross

very simple, posting it here is more or less needless. you can check which side of an infinite line a point is on using the cross product. so check to see if the points of segment A are on different sides of the line defined by segment B. if they are, check to see if the points of segment B are on different sides of the line defined by segment A.

this alg isn’t particularly concerned about if the segments are on the same line 🙂

bool segmentscross(point2 point00, point2 point01, point2 point10, point2 point11) {
 bool check0 = 0;
 bool check1 = 0;
 point2 param00 = point00 – point10; point2 param01 = point01 – point10; point2 param11 = point11 – point10;
 if (param00.cross(param11) > 0) check0 = 1;
 if (param01.cross(param11) > 0) check1 = 1;
 if (check0 == check1) return 0;
 check0 = check1 = 0;
 param00 = point10 – point00; param01 = point11 – point00; param11 = point01 – point00;
 if (param00.cross(param11) > 0) check0 = 1;
 if (param01.cross(param11) > 0) check1 = 1;
 if (check0 == check1) return 0;
 return 1;
}

c++ concise win32 game source

wordpress isn’t playing friendly right now so this will be a paste dump, soz if the formatting isn’t perfect.

i haven’t seen much open source game/multimedia for win32 that i consider readable, so even though this is new ground for me, i thought i’d share what i’ve got. don’t consider this material authoritative, but it does actually work.

the source is a few short documents – i’m used to c-based, one document programming, with one character variable names – stuff you can read quickly. the intent here is to provide a minimal framework to help other people turn their ideas into applications. apart from the main document which has the win32 stuff, there are five short headers – one for global variables, one for audio (which can be de-commented to produce a 440hz sine), one with a few basic vector algorithms (2d point class, point to line check), 2d vector graphics (aa line and circle/filled circle), and one that does the “game turn”. it’s not optimised because eg. the triangle rotation calcs are performed on each frame regardless of if anything’s moved, but you should be able to skim over them to get an idea of where everything is pretty quickly so you know at least one way to do things.

the app draws an asteroids style ship which can be rotated and thrusted with the arrow keys, and colours each background pixel red and green to indicate which side of the ship it’s on. you’ll probably fly it off the edge of the screen, hit escape to quit.

as said, this is new for me, hopefully it’s solid enough to help others get a foothold and improve on it. you can stop reading unless you want the particulars of the line algorithm.

http://xoxos.net/software/vector.zip

the first aa code i wrote was for a line algorithm. i intended to expand the code for variable thickness, but endpoints are a hassle, so it’s a “1 pixel width only” alg now (you can expand the ‘softness’ of the aa by dropping the ‘margin’ coefficient to give the graphics a different feel and make thicker lines). anyway – my alg has two major differences from Wu – atan() is used to calculate the thickness of the line based on it’s angle (it can be more than the 2 pixels Wu uses) – and a nonlinearity is used to boost the line pigment which reduces stepping. i was pretty happy with it and call it the pothead line algorithm.

yesterday i noticed that there was a bug in one of the endpoint routines that was drawing over pixels in another location so i rewrote it instead of trying to fix it, because i’d used round-down INT conversion. it’s now quite concise and the “line” is drawn from the start to end pixels (endpoints are fractional), which means that the pixels at the ends aren’t aa’ed for their “perpendicular” distance from the line. they’re more intensive the way i do it (fully calculating the distance to each pixel around the ends) and i noticed it was working pretty good without endpoints anyway. i intend to use my aa lines for wireframe/vector style stuff, where lines will often be drawn end to end, so spending all that effort is hardly worth it.

here’s what i can tell you about writing aa line algorithms –

as said, the first one i wrote lazily and passed floats to ints by rounding down. i tested the alg by rotating a radial line around a fixed point. when it passed WNW to WNN there was a slight jump because of this. i figured that wouldn’t be too overt, but it was, kinda, when i put the triangle ship together.

when i wrote the new pothead line algorithm i was prudent about handling the 0.5f “center” of each pixel, but still, this is the pothead line algorithm, so i didn’t want to get too involved with it and did it off head. i have yet to perform the spinning line test with it, having switched to the spinning spaceship triangle. in this case, when the triangle points SE, the front edges kind of get wider for a few degrees. it’s a much smaller artifact, you need to make the ship bigger (say 40 pixels instead of 10) to really see it. given the method i wouldn’t be surprised if it’s due to the floating point. or maybe i need to draw some diagrams or something.

at least you can turn this app quickly into something like pong, where aa isn’t an issue 🙂