win32 solution to WM_NCLBUTTONUP

this stupid thing! a “convenient API for detecting mouse button release outside of client area”, only works when the window is maximised (and thus literally pointless). reason because once outside client, mouse is captured for dragging the window so the message is *never sent*. really good.

instead of messing with button messages, use this in your process to detect the button state:
if((GetKeyState(VK_LBUTTON) & 0x100) != 0)

contours

for some reason i always think i wrote these down somewhere i didn’t, so i write them here:

from 0 to 1, we may make a cheesy curve as x * x

instead of (1-x) * (1-x) to produce the inverse, we can write x * (2-x)

and as an interesting expansion of this form imo, we can produce an s-curve in this range,

x * x * (3 – 2x)

 

easy stuff, been a while :p

 

 

3d rotation advice

regarding the pitfalls i encountered implementing 3d rotation..

probably all of them. setting off comfortably from 2d geometry i did not foresee spending over a month on rotation..

the error explained: if you use sine and cosine and radians then you use what game coding people call euler angles. some will say they are correctly called tait-bryan angles, but this is mentioned for reference. i no care.

you may think as i did that you can easily do 3d with what you know but you are horribly WRONG. to illustrate:

here we are in 3d land. we gaze at the back of a tetrahedron. we turn left.. which is accomplished by rotating the world, so that objects on the screen are conveniently aligned with our coordinate system for translating to screen position..

..then, in the 3rd frame, we roll onto our left side some.. if you’re used to the same coordinate system as i, you’d think, “simple, we rotate on the z axis..”

..once we have done this, if we want to turn the camera left or right, what do we do? or to be explicit, incrementing the y angle rotation produces frame 4…

with some consideration it becomes obvious that to accomplish the desired left or right turn once we are rolled, it is going to take some very involved math.

at first i thought, i’ll rotate a unit vector, and decompose that.. then i decided i was being silly and ought to investigate what humans do.

gratifyingly, this turns out to be a classic and charming problem of mathematics. the conventional solutions involve matrix multiplication, or quaternion (specialised matrix) multiplication.

being fundamentally opposed to the introduction of new knowledge, i decided to implement 3 x 3 matrices. they have a floating point problem at the poles of the y axis due to tangency/infinity when translating the matrix back to radian values, but quaternions, for some reason, do not take radian derived arguments..

a matrix takes eg. sin(x) and a quaternion takes sin(x/2). as an audio based coder, if i wanted to do something daft with sin(x), i’d need to take the transcendental twice if i used quaternions. q’s do sound nifty, like a 3d form of the 2d sine oscillator (eg. previous posts), which is something i’d previously wanted to use.

also, everyone tells you to use quaternions, so i used 3 x 3 matrices. there has to be less multiplication as quaternion matrices are 4×4, and that pole error is kinda fun (met it in games).

and here began problem after problem.

there are numerous ways to roll a coordinate system, eg. if x is right and y is up, is z toward you or away from you. do you rotate clockwise or anticlockwise around the axis.. both of these degrees of variation (coordinate system and rotation on axis) have left handed or right handed representations (worth looking up for the visual reference), and the euler-to-matrix composition and decomposition must be structured accordingly.

NASA, the colorado school of mines, et c. et c. have online documentation of 3×3 matrices used with rotation. it’s everywhere, been done for years. however, i’ve been using POVray for 3d modelling for 15 years and am very comfortable with their left hand coordinate system left hand rotation, whereas most of the world use RH/RH.

my desired LH/LH solution was difficult to find online. i direct you to the euler angle pdf at geometrictools.com

ultimately, the solution for “3d rotation from a given orientation” is simple, but the various discrepancies can make it tortuous to implement. especially if you are pig-headed, like me, about keeping things in radian form.. i’m told most 3d games keep orientation in matrix form …ah-soo.. but radians = good for me.

it will not be helpful to list all the problems i had, because others may actually avoid them altogether.. eg. when translating matrix to euler, one axis is returned with pi range instead of 2pi, where rotations are reflected back into the hemisphere by compound effect of the other axes.. if you want a “full spherical response” this can be fixed by checking to see if z is significantly (pi, but not pi*2 of course) different.. when it crosses the y hemisphere, add pi to x and z and do y = pi – y..

my advice – to start, rotate an object, not the camera. it is very difficult to observe a bug from errors. incorrect order of rotations, for instance, wasn’t immediately intuitive.. g’head and implement the whole thing, carefully.. radians to matrix, matrix to radians.. rotate your object using the matrix or a euler angle function.

if you pick an xyz order matrix, you must rotate in zyx order if you use euler rotation. or it will act normal, act normal, woah spin all over the place.

so you have one rotation for object orientation, and another that represents the slight amount of incrementation.. you convert them both to matrices and multiply them together.. i found that the incrementation matrix had to be first, otherwise you get the same result as in the illustration. no one ever told me that! it’s just one of those things that you finally discover needs to be that way.

i wish someone would have told me that.

i wish i’d known things like, “that matrix conversion is right, mess around with that other thing to fix the bug”, but you never have that facility when outsourcing.

looking back at the last five weeks, there were stages where it took time to find the correct search terms to meet my solution, but the greater share of time lost is due to my determination to retain euler angles. or something. i don’t know what i could say or show a past self to make the process easier, it seems like a travesty of getting hung up on things. i’m glad i got through it managing to keep things left handed and in radians, i’m stunned by how painful the process was.

i guess, i hope you’re comfortable using RH/RH.

gimbal lock

when throwing my “3d soft” rendering engine together i’d gotten to the point where i could place an opaque aa triangle on the screen.. i then set up some rotation functions and watched my triangle spin around the y axis.

as i added rotation to more than one axis, i noticed that multiaxis rotation resulted in a locked orbit, though the rotation coefficients did tilt the orbit between poles in relation to the rate of rotation. i’d read about gimbal lock a few days previously but it took someone more experienced to point out that this is what was occuring, as at that point in development i was thinking that perhaps i’d misconceived it.. and a few other possibilities.

i had added rotation to each axis as a sine cosine pair instead of using quaternions. my friend recommended i switch to quaternions.

as i was developing casually, often in less than optimal states of consciousness it was probably around 2am half asleep that, from years of audio dsp (and a few simple 3d graphics, like global terrain generation) that my method was fine without quaternions, what i lacked was a state vector..

so i added the state vector (eg. instead of rotating the triangle by a degree, increment a variable for the rotation amount) and that resumed the anticipated rotation behaviour.

so that’s what gimbal lock looks like, and that’s one way to defeat it without quaternions.

aa triangle caveat

recently conceived of making the step to opaque 3d over wireframing. found a popular resource that helpfully defined two cases of triangles (an arbitrary definition but any case of two for triangles applied to a cartesian grid is okay) – when y for points is arranged low to high, the median point is to the left or to the right…

equipped with such a definition one is presented with two cases for procedurally approaching the triangle.. now the left and right borders can be easily defined and intermediate pixels rendered.

to aa my triangles i took the slope from each side and computed the number of pixels width that a 1 pixel aa border would occupy (as a float) so that rendering each aa’ed side is not intensive.

the tutorial i followed, after presenting the case for left pointing and right pointing triangles, rendered them in two stages – top corner to middle corner, middle corner to lowest.. seems a sensible approach, one side on the left, one side on the right…

following this topology, one is then presented with four special considerations – rows containing corners overshot the aa from the opposite side. so i had to rewrite my triangle prodecure, and here’s what i did differently:

there are still two cases, for left pointing and right pointing triangles going by the intermediate y coordinate. however, the entire triangle is rendered in one for loop, which uses the float border value at pixel + 0.5 and uses the slope with the current pixel’s x + 0.5 to determine an aa value for each side..

if the aa value is lower than 0, the point is outside of that side.. if it’s greater than 1, it’s inside that side. then clip them all at [0,1]. instead of attempting to save cycles with sneaky crap like dividing the process at the median y point, do the whole thing, compute all three sides, then go aaa * aab * aac

this will work much better than “efficient procedures” that will fuck up if triangle sides et c. are subpixel, or slopes are almost horizontal et c.

about developing

two patterns

recently upgraded my personal assessment to include the ability to create opaque 3d objects. i realised that conceptually, this stage is often reached about a minute after the ability to wireframe, but for me it took about five years.

sdks infuriate me. generally documentation is terse as effort goes towards the resource itself. i have continually been confronted with some barrier of data that prevented me from some ability. often these barriers are installed for years, eg. the three year wait to install the synthedit sdk with fclt. how was i supposed to know it just goes in the folder.. many requests for assistance ignored. that’s pattern number one – i work merrily when i don’t need someone else’s shit. i’ve now had several compounded multi-year breaches due to lack of transmission of very simple basics.. putting an sdk in a folder makes a lot of sense to anyone used to programming applications that use resources, but that’s never been my style. to save myself additional trauma, i have a very low threshold for shortcomings in documentation, and have no difficulty absolving myself of the responsibility for not being able to parse poor documentation due to the scope of my pursuits.

around 2009 i realised that 3d coordinates could easily be placed on a screen if one simply defines an angle of vision (eg. 180 degrees becomes 1024 pixels, and after that i messed with transforms for better perspective) allowing me to wireframe. i assessed that calculating the angle of reflection would be very intensive using transcendentals, so i decided to adjourn from 3d solids given the madness of attempting it using rudimentary angle calculations with lots of transcendental functions. i didn’t know about dot and cross products. (anyway that’s pattern #2.. creation is much easier once a precedent element is created with which to synthesize relation.. take a step forward.. petition the equation.. the dao of motion and creation. without a frustrum it’s difficult to conceive of how to wireframe).

perhaps if i’d messed with 3d coordinates for some years i would have discovered them. dunno, haven’t tried it. it took me five years because to learn about normals i had to start handling points with classes. before doing this, material was impenetrable due to the class simplifications – 3d can be done without them, and i’ve now seen a few examples of it beyond my own..

of course it is immensely better to use classes, it makes the syntax so much easier. so of course i can’t blame the public for failing to clarify opaque triangles to those who have avoided using classes, and similarly in many cases i can understand why people don’t take time away from their pursuits to facilitate absent informations for aspirants. and of course i can still permit myself to resent obscured resources for Things That Affect People, like windows. it’s kind of socially irresponsible how western forum users demote people for their english and culturally limit the resource, seen it in several fields, but things are getting cooler. (like in audio dsp at kvr there used to be a strong sense of exclusory snobbery, eg. it was considered impolite to give code to programmers who displayed deficiencies in some/other areas.. “if you let them know how, they’ll make some buggy as fuck version and it will affect us all”. here again, the persistence of public contributions has pretty much eliminated any public statements to this effect).

things are getting cooler. i upgraded the 2d vector classes i wrote last year to 3d yesterday, reviewed resources and found several that were “approachable” to me.. most of them created in the last four years.

point of all this.. hope the future is better.. my experience, saying a lot about me, maybe so maybe not.. i have one kind unusual hybrid erudition..

treasure your resources, or appreciate them, when they work for you. the folks who help out. i’ve seen a lot of snakes in the grass, people who trip others up to keep them uncompetitive. it’s been a tough slog, i’ve spent a lot of time staring at very puzzling things (julius o. smith) and it’s been a fight for people to establish cooperative, helpful venues and paradigms.

doing shaded 3d triangles is pretty easy, conceptually approachable by an algebra student. i’m 44, which makes it just over 3 decades of coding for me, and i just got here. many people have made it there before me, but all those fuckers had money, or friends, or someone or something they could understand. i spent years waiting to pay $60 for petzold, and i’m going to get a good 60 years screaming about how the world would be a different place if MS had intended for that text to dispense information easily.

bug in vector.zip source

one of the soundcard callback messages uses WM_SYSCOMMAND. in another app i found this method wasn’t passing other things through WM_SYSCOMMAND (perhaps i had added a break; in the wrong place..?) so that when i added a frame to the window, i was not able to move or maximise it as these were being dumped at WM_SYSCOMMAND.

the few things done in that statement were moved into the next thing that would have been called for them and window could be moved again 🙂 hazards of source..

(laying on back, don’t feel like messing with compiler to fix source, hopefully soon.. itm here’s a note)

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 🙂

c++ antialiased circle algorithm

i released a very minimal c++ win32 graphics&audio source on the software page at xoxos.net a few days ago with an antialiased line algorithm. i’d read about the wu line and seen the results and decided to do it my way first.. i use more than 2 pixels and a nonlinearity for the edge which is smoother than wu. it looks keen and it’s homemade.. only “feature” is a slight shift when switching from NWN to NWW directions, likely because i didn’t add 0.5 when converting to INT, which is a task for another day as it looks nice otherwise.

got to circles, my method inherits some of the methods i used for lines. this is pretty much a/the brute force algorithm as a sqrt() is performed for every pixel, and an additional sqrt() for every row. the benefit of this is that subpixel centers may be assigned so it can’t be optimised by symmetry.

my antialiasing uses a margin scaling coefficient, eg. once the distance between a pixel and a circle/line is resolved, this distance is then scaled before antialiasing is conducted.. which softens the boundary, or makes it more steppy if the coefficient increases the relative distance… 0.75 looks real nice to me along with the nonlinearity. the distance this affects in pixels is of course the inverse 1/margin, or 1.33 pixels if using 0.75.

circle basics:
radius = sqrt(x*x + y*y)   and so   y = sqrt(radius*radius – x*x) 

my technique is pretty simple – compute an outside circle and an inside circle which are larger/smaller by the inverse margin coefficient (eg. radius +/- 1.33), thereby reducing the amount of pixels that need to be run.

much of the length of this script is actually reading the preexistent pixel colour. once you get the idea, it’s probably easier to write it yourself than untangle my code.

as you may guess, reducing margin to 0.25 fades/blurs graphics by 4 pixels.. 0.001 by 1000 pixels and so forth.. and, once you get the idea, you can easily modify this technique to give the circle thickness. like the line algorithm, i am suggesting that this method be known as the pothead antialiased circle algorithm.

soz for the mess, i am not 1337 wordpresser, code tags put the whole lot on one line..

void circleaa(point2 param, float radius, int bgrr, int bgrg, int bgrb) {
 if (radius <= 0.f) return;
 short int bgb, bgg, bgr;
 float radiuso = radius + margini; // outside radius
 float radiusi = radius – margini;
 float radiusi2 = radiusi * radiusi;
 float radiuso2 = radiuso * radiuso;
 int cxi = floor(param.x); // center int
 int cyi = floor(param.y);
 float cxd = param.x – cxi;
 float cyd = param.y – cyi;
 o = radiuso + margini;
 int lowm = floor(-o); int highm = o;
 for (int dox = lowm; dox <= highm; dox++) {
  int pixx = cxi + dox;
  if (pixx > -1 && pixx < dispx) {
   float dx = dox – cxd; dx *= dx;
   float boy = radiuso2 – dx;
   if (boy > 0) {
    boy = sqrt(boy);
    int lowy = floor(-boy); int highy = boy; highy += 2;
    float biy = radiusi2 – dx;
    if (biy > 0) {
     biy = sqrt(biy);
     int lowi = floor(-biy); int highi = biy; lowi += 2;
     for (int doy = lowy; doy < lowi; doy++) {
      int pixy = cyi + doy;
      if (pixy > -1 && pixy < dispy) {
       float dy = doy – cyd;
       dy = sqrt(dx + dy * dy);
       dy -= radius; if (dy < 0) dy = -dy; dy = 1.f – dy * margin;
       if (dy > 0) {
        dy *= pih; dy = dy – dy * dy * dy * 0.1472725f; float dy0 = 1.f – dy;
        int dopix = (doy + cyi) * dispx + dox + cxi;
        bgb = (byte)framebuf[dopix];
        bgg = (byte)(framebuf[dopix]>>8);
        bgr = (byte)(framebuf[dopix]>>16);
        o = bgrb * dy + bgb * dy0; o < 255.f ? bgb = (int)o : bgb = 255;
        o = bgrg * dy + bgg * dy0; o < 255.f ? bgg = (int)o : bgg = 255;
        o = bgrr * dy + bgr * dy0; o < 255.f ? bgr = (int)o : bgr = 255;
        *(framebuf + dopix) = RGB(bgb,bgg,bgr);
     } } }
     for (int doy = highi; doy < highy; doy++) {
      int pixy = cyi + doy;
      if (pixy > -1 && pixy < dispy) {
       float dy = doy – cyd;
       dy = sqrt(dx + dy * dy);
       dy -= radius; if (dy < 0) dy = -dy; dy = 1.f – dy * margin;
       if (dy > 0) {
        dy *= pih; dy = dy – dy * dy * dy * 0.1472725f; float dy0 = 1.f – dy;
        int dopix = (doy + cyi) * dispx + dox + cxi;
        bgb = (byte)framebuf[dopix];
        bgg = (byte)(framebuf[dopix]>>8);
        bgr = (byte)(framebuf[dopix]>>16);
        o = bgrb * dy + bgb * dy0; o < 255.f ? bgb = (int)o : bgb = 255;
        o = bgrg * dy + bgg * dy0; o < 255.f ? bgg = (int)o : bgg = 255;
        o = bgrr * dy + bgr * dy0; o < 255.f ? bgr = (int)o : bgr = 255;
        *(framebuf + dopix) = RGB(bgb,bgg,bgr);
    } } } }
    else {
     for (int doy = lowy; doy < highy; doy++) {
      int pixy = cyi + doy;
      if (pixy > -1 && pixy < dispy) {
       float dy = doy – cyd;
       dy = sqrt(dx + dy * dy);
       dy -= radius; if (dy < 0) dy = -dy; dy = 1.f – dy * margin;
       if (dy > 0) {
        dy *= pih; dy = dy – dy * dy * dy * 0.1472725f; float dy0 = 1.f – dy;
        int dopix = (doy + cyi) * dispx + dox + cxi;
        bgb = (byte)framebuf[dopix];
        bgg = (byte)(framebuf[dopix]>>8);
        bgr = (byte)(framebuf[dopix]>>16);
        o = bgrb * dy + bgb * dy0; o < 255.f ? bgb = (int)o : bgb = 255;
        o = bgrg * dy + bgg * dy0; o < 255.f ? bgg = (int)o : bgg = 255;
        o = bgrr * dy + bgr * dy0; o < 255.f ? bgr = (int)o : bgr = 255;
        *(framebuf + dopix) = RGB(bgb,bgg,bgr);
} } } } } } } }