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 🙂

mass-springs

..the pride of my dsp retinue :p

mass-springs, as they are known, are elementary to physics simulation and so to acoustic modeling. a simple manifestation of hooke’s law:

F = -kx

where F is restoring force, k is a spring constant, and x is displacement in the spring.

my first implementation was probably at the age of twelve, making simple games and simulations on a tandy coco. no physics, only a simple application of elementary mathematics for making things bounce on the screen. the first applications in audio dsp were for a reed model and for a simple oscillator i called ‘gravity’. the mass-spring also correlates to the helmholtz resonator, or resonant volume of air found inside the body of a guitar, violin, or bottle when you blow across the top.

i was proud that the implementation i had muddled together was better than other examples i was finding online, for instance i had managed to devise a brutal and tragic way of calculating the resonant frequency. in retrospect these adjectives do apply. i will not go to the trouble of resuscitating the algorithm i published in my EPM pdf in order to comparatively illustrate the merits of the presented form.

so, you’re reading this because you searched for mass-springs and dsp and c++, or because my dsp journey fascinates you, or because you are a stalker. i address the first circumstance.

if you nose around in audio dsp you are bound to encounter the concept of angular frequency, annotated as a little omega, or lower case w.

w = 2 * pi * Hz / fs

Hz is the resonant frequency, fs is one of several notations for sampling frequency. it’s really nice in dsp when people say what the symbols mean, that doesn’t always happen.

first, a note about efficiency if your application modulates the resonant frequency: you can factor the 2 * pi out by creating a constant used for calculations of angular frequency.

initialise:   fsw = fs / 6.283185307179586476925286766559

calculate:   w = Hz / fsw

wonderfully, the resonant frequency of a mass-spring, or k, is w * w. especially given the mess i had previously, it took a while to elicit that. isn’t sharing wonderful?

so.. the cause of this blog is a wonderful experience yesterday where i reexamined my preexistent algorithm (after years of implementations). if you have used it, you are aware that the dynamic response varied with frequency. i had cleverly (again, over duration) tailored my mess to decay at a uniform rate. higher frequencies had a higher dynamic response i hadn’t been able to tame. now we are past these tribulations.

also, lets get that negative out of hooke’s law, so our resonant frequency coefficient k = –w * w

i am neither physicist nor mathematician, and cannot profess the vernacular.. so my algorithm uses two variables. i am sure there are more informed choices. i use:

mp, or position of the mass-spring..

mv, or velocity of the mass-spring..

i’m sure position is an appropriate use of the term. people with an education may smile at the use of the term velocity. there are often different equations used by educated people to describe eg. force and velocity in modeling, to me it’s just making sounds with numbers, dude 🙂 so be aware of that when continuing with this topic.

i’m so excited. this code drops a multiply on what i was using. it also has uniform dynamic response.. if you initialise with a displacement of mp =1, you get the same amplitude contour at every frequency 🙂

mv = k * mp + gain * mv;
mp += mv;

a note about this – squaring angular frequency means bad things at high values. i haven’t got there yet but i think you’re okay below fs/4, so oversample a bit if you’re using high resonant frequencies.

one of my reads during revision was http://gafferongames.com/game-physics/spring-physics/ which will reveal a super useful way to add an offset to the oscillation, so that you can ensure your mass-spring doesn’t pass a certain point on one side. lovely! 🙂 and/or, if you prefer, a collision modification. both of these methods are more efficient and elegant than the separate concoctions i was using before (eg. a 1/n softlimiter).

but wait, there’s more!

one of the reasons why it is preferable not to share source (and i hardly ever share source.. i’ll happily have lengthy, unpaid discussions about method, but other peoples source is a pita, and i imagine mine is as well.. i like one or two character variable names..) is because there are real benefits to doing all the steps yourself.

one of my failures in acoustic modeling is the 2d mesh. i’ve addressed it at at least three discrete periods. i’m not julius smith (his policy of documentation, alongside his accomplishments, establishes him as a luminary in audio dsp and acoustic modeling.. his texts are challenging without a practiced knowledge of calculus).. i don’t think like him and despite his prolific notes, i’ve never managed to make a 2d mesh that didn’t explode.

..revision of my m-s algo is intended to optimise a snare model i’ve been working on. development is good when you aren’t on a clock.. after finding my optimisation was tamed, i modeled an acoustic string. this took some wrangling due to the bounds.. the way i had of computing the force acting on each segment produced a gradual dc build. after a while, i nailed it and thought, well, that’s 1d, let’s try 2d.

the 2d also worked wonderfully. the crucial thing here is that by using mass-springs i was able to observe the building dc by using low resonant frequencies and correct my implementation. explosion in the 2d mesh happens within a dozen samples or so instead of over several minutes..

so in one 24 hour period i’ve fixed my mass-springs for ideal calibration, increased its efficiency and derived a bounded plane solution. this is a really good day in dsp.

but wait.. there’s more.

(first, straggling notes on the above material. the gain for the mass-spring has to be _very_ close to 1.0 in order to see much happen at audio rates. and also, arranging mass-springs in a line or grid with an audio rate resonant frequency.. are simply expensive ways to produce a sine 🙂 the grid may make a great looking flag, but at audio rates, flags aren’t very exciting.

so, what was the “more”..

with a gain of 1.0 (and eliminating one multiply!) the mass-spring algorithm is an efficient pure cosine oscillator – one assign faster than the fastest ‘quick sine osc’ i’ve seen elsewhere. its limitation is that amplitude changes with frequency modulation, however it has an advantage that no scaling operation is necessary for gain beyond the initial offset of the mp coefficient. there’s an additive solution in there somewhere.. perhaps percussion.

neighbor, that’s a dsp gonga :p