In those day I'm creating my very first 3d game and I've ran into couple of problems.
I read about AABB intersectioning and the idea of building trees from it, but
the one thing that I couldn't understand is, if my "character" rotates during the game, the concept of the Axis-aligned isn't preserved!
I've checked a couple of libraries (like oz-collide, OPCODE, and more), and I've seen that the implementations were made for static objects, because it uses the boxes without an origin (for non static, all the nodes in the tree should be updated after each movement).
Those libraries supposed to be SUPER-FAST, and I had probably mistaken somewhere.
Can somebody please help me with shedding some light on this topic?
Sadly yes, if your character rotates you need to recalculate your AABB, and it will not necessarily be a snug fit either. If you have a rectangle and rotate it so it's no longer rectiliniear the AABB will be bigger than the object.
The AABB is fast because the intersection test is very simple but as you've already discovered it becomes problematic when accurate intersections are needed on objects not aligned to the AABBs axes.
The AABB is still useful for quick tests, which I suspect those trees are made for. With a AABB tree you can quickly eliminate large swathes of objects from a more accurate testing phase. If the query returns a couple of extra objects it doesn't matter much. In your rotated character case this might mean that your character is regarded as in a region when he/she really isn't.
The AABB-tree lends itself to this with ease since each time you pass a test you go deeper into the tree and into more detail.
You can use a Oriented Bounding Box (OBB) when you need really accurate intersections. It can be implemented with the separating axis theorem. I see oz-collide has support for OBBs already.
There are alot of resources on OBBs, this one helped me:
GPWiki on separating axis theorem
Here's an implementation.
You can calculate an AABB from an OBB if you need to.
OZCollide works for moveable entities and is time independent (you just have to give a velocity vector).
It also works for OBB (not only AABB).
Check the online documentation:
http://www.tsarevitch.org/ozcollide/docs/ link broken
