owl's Blog

Sign in to follow this  
  • entries
    26
  • comments
    30
  • views
    33720

Octreezing the world

Sign in to follow this  
owl

583 views

Got it. I made the octree class and I'm able to push the meshes geometry into it. The algorithm for character collision against the world is something like this:

  • Get character's AABB.
  • Set's character's AABB position to current character's position.
  • Add velocity vector to character's AABB position.
  • Pass the character's AABB and an empty std::set to the octree.
  • Collide the character's AABB with the octree nodes, when in a leaf, collide the meshes's AABB there with the character's AABB again and get those that overlap.
  • Iterate the std::set we got from the octree and collide the character's ellipsoid with each mesh geometry.
    This added quite a lot of complexity to per-frame processing but framerate increased notoriously because the data to be processed (mesh geometry) got reduced A LOT.

    Now I need to do the same for drawing only what's visible which will increase framerate quite a bit as well.

    The following video shows a level composed of 54 meshes with 54 faces each. At all time, I'm colliding only with +-1.6 meshes per frame. At the top right you can see the number of tiles that are subject to collision. The wireframe represents the octree's nodes.

    [media]
    [/media]
Sign in to follow this  


8 Comments


Recommended Comments

Hi owl, great project! Im curious at how you handle collision. are you using continuous or discrete collision detection? and how do you keep character attached on ground when going downhill? Thanks

Share this comment


Link to comment
[color=#1C2837][size=2]Hi! Thanks. For collision I'm using the algorithms described in Kasper Fauerby's paper which is easily obtainable through google (in html or pdf form). To avoid the ellipsoid (the character) sliding on slopes I added a boolean variable to the collision packet that is true when the aforementioned algorithm calculates the sliding vector.[/size][/color]

Share this comment


Link to comment
so you change the sliding vector to up(?) when the char is stopping? or what? can you please elaborate more on this? Im doing the same project and I think I could learn from yours. Thanks :)

Share this comment


Link to comment
No problem.

The collision algorithm, among other values, takes a velocity vector to predict where the ellipsoid will be the next step of the simulation and to calculate the sliding vector. The x value of this vector is used to move the ellipsoid to the left and to the right. The y value is the sum of the force exerted by gravity (negative) and jumping (positive). As falling is an accelerated movement (you add the value of gravity each frame) if you keep adding gravity after you collided with a slope, the algorithm will make the ellipsoid slide downwards.

What you need to do is, after performing the collision, detect which part of the ellipsoid collided. If it collided with it's lower part that means it collided with the floor, then you reset the y velocity to zero. That way, the next frame, the velocity downwards will be small and the sliding vector will not make the ellipsoid slide.

I hope that makes sense.

Share this comment


Link to comment
Hello! Because I'm using the octree also for culling at the time of rendering. Also because I'm not actually sure there won't be displacement on the z-axis someday :)

Share this comment


Link to comment
okh I got it. Glad to know Im doing the right thing. Oh and by the way, when will you add object-object collision. Do you plan to add monster or any kind of object?

Share this comment


Link to comment
yap, I'm afraid the little ragdoll will feel too lonely if I don't! I'm still pondering whether to shoot them or to slice them.

Share this comment


Link to comment
[quote name='owl' timestamp='1304567077']
I'm still pondering whether to shoot them or to slice them.
[/quote]

Hug them, man, and give them kisses. There's too much violence in this world.

Well done on getting all this working BTW. I know from experience it's a damn sight harder than it looks.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now