Octreezing the world

posted in owl's Blog
Published May 04, 2011
Advertisement
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]
0 likes 8 comments

Comments

Bow_vernon
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
May 05, 2011 12:29 AM
owl
[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]
May 05, 2011 12:38 AM
Bow_vernon
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 :)
May 05, 2011 01:21 AM
owl
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.
May 05, 2011 01:59 AM
owl
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 :)
May 05, 2011 02:45 AM
Bow_vernon
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?
May 05, 2011 03:40 AM
owl
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.
May 05, 2011 03:44 AM
Aardvajk
[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.
May 05, 2011 07:01 AM
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!
Advertisement