Archive for the ‘math’ Category


tesselation + travis’ b-day

February 23, 2009

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.

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

December 25, 2008

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

November 30, 2008

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



interwebs are back! new laptop arrived! CAMERAS!

November 27, 2008


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:



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



Okay, that’s about it.

But hey, webcam fun! 🙂  LOOOOKIIIT



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

October 21, 2008

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


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

October 18, 2008

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

October 9, 2008

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.