tesselation + travis’ b-day

Both are filled with good times.  My good man Travis turned 17 on Thursday.  Yesterday we had had a b-day party at Ian’s place, and it was a fucking good time is what it was.  I can’t handle big parties, I hate ’em, but it was really just a few close friends just hanging out.  Which is my favorite.  I can’t handle too many people, or else I do an Asperger’s freakout.  I played some guitar, explained some autonoma theory, talked about stuff, then got blitzed and turned in to a sentemental cartoon of a wino.  I’d say my +20 liver of steel diety level holy liquor containment was definitely called upon.  I rarely drink so much.  But anyway.  I also recorded some hilarious footage, but I was told posting it would be in bad taste, so no drunken antics for you.

But here are two pictures:

Travis recites a random Lord of the Rings passage to Cat in the spirit of awesome.

You know what else totally shreds?  Tesselation algorithms!  Check this shit out:

1. Walk around loop and record all x and y values in respective lists.  O(n) [iterate through nodes and copy values to lists]
2. Remove duplicate x and y values, treating the lists independently.  O(n) [iterate through lists, remove and continue only]
3. Divide the space in to tiles using the x and y values from the nodes as seperate lists.  O(1) [create tile array]
4. Scan the tiles left to right, top to bottom.  Anywhere possible: Grow a rectangle right and down for each iteration until as much space as possible is full.  Repeat until all scanned.  O(amortize(n))

Conclusion: this is a good-ass algorithm!  BAM!

physics talk abstract and slides

So now that my talk is done and over with, I guess I promised earlier to post my abstract/slides. SO IM POSTING THEM JESUS DONT KILL ME OKAY KAYTHX.

They’re here, and you must use the video signal analysis in your brain to interpret the pictures. No one ever gets that and they’re all like ROFLMAO I CANT SEE WTF. silly silly people.

download: physics_talk_08_ccis.7z

That takes care of that.

shadow town, it’s where shading of unlit areas goes down, doo de doo

I’m trying to implement them!  So, shadow volumes are kinda slow with any graphics hardware, because they have to be calculated on the CPU, then passed to a shader/fixed-pipeline.  Also, doing per light occlusion shadowing (the accurate per light shadow method) must be done in multiple passes.  This is why I want to do shadow maps.  Shadow samplers can be easily accessed from GLSL fragment programs.  I can do it in one rendering pass, as the shader can receive the information for each light and it’s shadow map all at once and simply add/clamp the results easy as pie.  Ultraaaa banananana creeeeeam piiiie!  Right.

Anyway, I have been looking for a good sample for quite some time now, and Imma like “whaaat, they nothin’ heah!”  I found some good ones on directional and spotlight mapping, but that’s easy because it fits in one simple perspective projection.  I really need an example for point lights: omnidirectional shadow mapping using cube maps specifically.  I’d like to use shadowCube samplers if possible, but it’s fine to pack depth info in some advanced way and do the comparisons manually in the shader.

Sooo, I’m a little frustrated right now, ’cause I can’t find the poop on it.  But I’m still looking, and I’ve ordered the OpenGL Orange Book, it should be arriving shortly.

Siiiiggghhhhh.  You should check out the Inhuman comic.  It’s made of awesome.  No, they’re not furries, they’re aliens.  And stop calling me gay already.  That was only for those of you who look at this and say “that’s gay.”  I’ve been informed that the supreme Overmind known as “Common Sense” wants you all lined up and shot.  If I only I could order someone to do that.  Oh well.

So, shadow maps anyone?  pleeezzz halp omg ur mom.

t3h b4lling3st f0h3v4r bitches

Bye.

interwebs are back! new laptop arrived! CAMERAS!

YYYAAAAAAAaHHHHHHHHH!  I’M FREE!  AFK FTW BBQ ROLFMAOCOPTERSAUCE

afk is a fairly disgusting statement.  It was coined by a friend who thought there should be texting abbreviation for anally fucking kittens.  He came up with it.  Not me.  Though it does make a great expletive.  gggrrrraaAAAHHH!  ANALLY FUCKING KITTENS, THIS SUCKS!  Packs a punch.

Now that I have full access to ye olde intarwebz0rz again, allow me to fill you in: my new laptop is here.  Yes here.  Not almost here, ACTUALLY HERE!  It runs Ubuntu 8.10 Intrepid perfectly, and Windows Vista because if I take it off I’ll lose the software license.  Microsoft bitches.

I have tested my stuff under Vista though, and I was pleasantly surprised that it ran!  My code has always been very raw and portable, something I am very proud of.  It also runs on Ubuntu Intrepid just fine.  Actually, better than anywhere else, because this is an AMD64 (Athlon64X2) machine.  It came with 32-bit Windows, which makes no sense to me, it’s like putting two toilets in an apartment with only one ass.  But the Ubuntu half is full on 64-bit, and I have to say it’s a big improvement, especially since this baby is dual core.  Multitasking!  Also, the physics engine has a build now just for 64-bit GNU/Linux, available through both GNU Make and C::B projects.  It’s really fast on this machine, and this build is always double precision too, because of the 64 bittage!

Here’s a screenshot of the pyramid example running on the laptop:

yoink!

Yeah.  Now look at the zooming in on the frame rate:

WHOA!  FFFFAAAASSSSSSSTTTTTT.

Okay, that’s about it.

But hey, webcam fun! 🙂  LOOOOKIIIT

T3H BAANNGGING OF T3H HEDZ P0R M3TUHLZ!!!111!!1!1!!

Yes, the laptop has a webcam to.  Camgasm that’s awesome.

Oh, wait!  I’ve also just been messing around with shaders, because my laptop can actually handle this shit!  This is my phong lighting shader.  I have it split in to ambient and diffuse/specular passes, so that luminance occlusion multipass shadows can be easily integrated.  I’m working on a shadow mapper right now.  But anyway, last picture:

See all y’alls!

CCD stuff

Aaah, the many ways of doing continuous collision.  After looking at conservative advancement in Box2D, I realized it just wasn’t what I needed.  I wanted a process that could finish in one iteration.  So I started looking at sweep tests, and my first was circle-circle sweeps.

Basically circle-circle sweeps are a quadratic equation, where A is the relative velocity squared, B is two times the relative velocity dotted with their relative position, and C is their relative position squared minus the sum of their radii squared.  BLARGH!  So, here’s the math:

v is a vector describing their relative velocity
p is a vector describing their relative position

A=v^2
B=2*v*p,
C=p^2-radii^2

Then you just crunch that with the good ol’ quadratic formula and the smallest of your two roots is the time of impact.  The larger root would be the time they separate after passing through eachother, but who the fuck needs that?  Not me.  Here’s a picture.  Joooocy peeectoooor.  Yaaaaah.

Aaaaw yeeeaaaah.  It’s an exact answer too, no dicking around with approximations.

Polygons might be trickier though.  I CAN get an exact answer using extended separating axis, (where each axis’ interval is extended by the velocity component dotted with said axis,) but it is only a result given linear velocity.  When you have screw motion, it becomes approximate, because a lot can change between now and projected time of impact when they rotate.  You may wind up hitting totally wrong, or worse, missing just as badly.  So, I may need conservative advancement for this one, or else I’ll have to dig for papers on Google about more advanced methods my feeble brain can barely comprehend.

More on this later.  For now, I will headbang.  To Dream Theater.

continuous collision detection

Do you people think it’s about time?  HUH?  Well, I do.  So, several things are planned for addition soon.  This will involve a lot of lists:

• 0 degrees of freedom constraint: pivot constraints (the anchor point on each object are forced to share a common point in global space.)  Basically a bar constraint, but with a length of zero.  This is needed because a length of zero creates a singularity in bar constraints.
• 2 degrees of freedom constraint: groove constraints (probably.)
• Continuous Collision Detection by means of sweep test + a time of impact advancement method.

In the future, I will probably add force fields, but not just yet, all we have is the global gravity constant for now.  My current collision algorithm is completely discrete, and is as follows:

1. Update positions by delta time.
2. Cache AABBs and world transforms.
3. Check for intersections.
4. Generate collision contacts and update arbiters.
5. Do response.

Continuous collision detection is trickier:

1. Cache swept AABBs and swept world transforms using the Minkowski Sum method or gift wrap method.  With the Minkowski Sum you could do an iterative deformation for orientation movement, but only if you wanted to handle potentially concave hulls.
2. Check for sweep intersections.
3. For each sweep intersection calculate the time of impact of the two hulls.  The best method in my opinion is a convex cast, but there are more accurate ways out there.  The time of impact should have a slight slop to it.
4. Then take each of those and update positions by time of impact and accumulate lost time as delta time minus time of impact, and update the rest by delta time plus time lost in any previous TOI (time of impact) collisions.
5. Cache world transforms.
6. Check for intersections.
7. Generate collision contacts and update arbiters.
8. Do response.

As you can clearly see, the only complex part is updating of the position based on advanced timing.  After that, it’s just like the discrete method, as none of the actual collision handling is different.  We’re just making sure there is no tunneling, that is, nothing can pass through anything else.  This is a huge undertaking.  As such, this is a big milestone.  I’ll keep people in the loop about progress as much as I feel like it.

Peace  🙂

physics stuff

Well, I’m back to work on physics.  I’m basically cleaning up all memory problems, and there are a few.  I’ll post again when I have some results for you.  🙂

Also, sorry for not doing any programming lately.  I’ve been kinda wrapped up in mental health issues, not to mention the presidential election.  Mental health issues here are mostly caused by it being the fucking end of civilization.  I mean, we’ve had a depression before, but the flood of doom is impending from melting ice caps.  The air is unbreathable and McSame wants to drill in a fragile tundra wildlife reserve, not to mention if he croaks we have Sarah “I’m a mavrick you betcha wowzers alrighty bimbo pants” Palin to contend with.  The Dan Quayle of our time, but even dumber.

If we keep damaging the planet, it will die, and we will too.  We grow our crops, breathe our air, and live our lives right here on this planet.  It’s like we’re burning our own house.

I haven’t forgotten about posting my guitar tabs for Unified System either, I just don’t know how on WordPress.

quaternions page is finished!

Well, there you have it!  It’s got the functions and everything!  😉

quaternions page is up + good times

Let me get this out of the way – there is a new article about quaternion rotations up.  Yes, I know I haven’t showed you how to convert to/from them, so it’s useless except as a theoretical paper.  This will soon change, but TOMORROW.  GOD IM TIRED BLARG.

Also to get out of the way, 2D Boy is almost about to release World of Goo, which I’m really geeking about right now.  If you order before they release it, you get a profanity sound effects pack.  FUCK!  😀

So I’ve had some good times this past week, which is interesting, seeing as how it literally started out with me on suicide watch.  I made a full recovery on Tuesday, ironically because of a Dream Theater song I was listening to.  A Change of Seasons, and there’s this part that’s like “I’m sick of all you hypocrites!  I don’t need your sympathy to get me through the day! Seasons change, and so can I!…” and it was really inspiring.  My main problem, I suddenly realized, was in expecting sympathy for my problems.  Whereas in a perfect world I would certainly get some sympathy for the kind of shit I deal with, I realized expecting it from everyone will only make me feel let down.

Then I went skating on Thursday with James, Colleen, and Phillip on 80’s night, and we listened to music from the past (i.e. real music) the whole time while skating.  On Friday I saw James again, and we basically played Destroy All Humans and such the whole time, but after that we went back to the rink on Saturday and enjoyed a roller derby match!  Go RoCo!  That was actually a really good time.  Then the next morning I went to YRUU (that’s youth religious unitarian universalists) again and didn’t get picked on really by that girl, so it was actually pretty cool.  I had a long conversation afterwards with cool people who like Transformers, Spore, D&D, and other incredibly geeky stuff, making me feel at home.  Tomorrow Chuck and Life are on network television, followed by a Tuesday at programming club, where I really just can’t feel better.  I’m on a roll of engaging in non-suckage!  😀

But my point is, I really forget just how much I can do when I’m in good spirits.  I wrote that whole fucking quaternions article in about an hour!  I mean, that is just crazy fast.  Of course it’s not quite finished, but I could have easily just slapped all the functions up there, and didn’t.  In fact, it was like a mini paper on quaternions before it even gets to rotation, and then there’s an extensive discussion on that.

When I get up tomorrow, I’ll get straight to work on the menus and hopefully have a usable thing soon.  And then I really will get to work on the game.  I’m still deciding if it should be pure 2D (aside from the menus obviously) or if I should go all slick and shiny 3D interface on you people, with bells, whistles, and cabbage.  All puppies need cabbage to slaughter freemasons!  Ahhh, I’m like, intoxicated with not feeling awful.  I almost forgot what that was like, you know?  ❤

quaternions, I can make them work!

Now that I have arc ball working, I will show you what a quaternion is.  I have a couple of screenshots too, and they are here:

It looks like this initially.

Now we have a white circle showing us the grabable sphere of the arcball. The red point is where we've grabbed it.

As we've dragged the red dot, notice how what we've really done is simply dragged that point over on the arcball, and as the point is dragged, so rotates the sphere, and as the sphere rotates, so does the model.

Basically what a quaternion is is a 4 dimensional vector that exists in space over the real numbers.  For the purposes I use it for (rotation) it’s basically is superior, because it can do perfect great circle rotation easily.  The reason is that it isn’t constrained by the Euler representation’s axes (pitch, yaw, roll) which make the question of arbitrary axis smooth rotation much harder.  You have to do something like 3 different space transforms in order to do the rotation, and then you have to go back.  Whereas a quaternion essentially produces an imaginary axis that can rotate as though there were no space transform, because the other elements of the vector are relativistic.  It is very hard to imagine what this looks like, because it’s, you know, hyperspace.  Once the rotation operation has been derived through all that complex imaginary number crap, though, all the imaginary elements are gone, so nothing special is needed for the algorithm.  This wiki page has info on quaternions, and this NeHeGL example is a good demo of how it works.