using a custom octree with bepu

Discuss any questions about BEPUphysics or problems encountered.
sueds
Posts: 43
Joined: Tue Feb 05, 2008 10:40 am

using a custom octree with bepu

Post by sueds »

Hi I was wondering if I could use bepu with my octree. I'm not good at programming but I was wondering if it could or if would have to create a class into your code.

cheers
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: using a custom octree with bepu

Post by Norbo »

If you mean using an octree as a broad phase/space partitioning method (first step of detection, finding possible collision pairs), you could create a child class of the BroadPhase class and implement its required functionality (updateControllers method and so on) using the octree. You could then just tell the space to use it (space.setBroadPhase()). The already in place PersistentUniformGrid broad phase is pretty quick though; I'm not sure under which circumstances an octree would be superior. I don't currently plan on implementing an octree based broadphase myself at this time (a sweep and prune implementation is possible later).

If you were talking about something else besides broad phases, sorry :D

I should also mention that if this is for a static triangle group or level geometry, the upcoming v0.5.0 has a StaticTriangleGroup class which is nice n' fast (a demo of it is shown in the latest video posted in the general forum).
sueds
Posts: 43
Joined: Tue Feb 05, 2008 10:40 am

Re: using a custom octree with bepu

Post by sueds »

I've just seen the video of the mesh collision really nice. The technique triangle static mesh is not using an sort of space partitioning ? I mean I've ask some guy on other physics engine and I've told me that they were using octree to detect the level geometry.

Can I use your physic engine in a game contest ?

cheers
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: using a custom octree with bepu

Post by Norbo »

v0.5.0's StaticTriangleGroup internally uses a bounding volume hierarchy, I believe similar to Bullet's scheme (though I haven't checked their implementation or details, so I might be wrong). This structure is based on the bounding volumes of triangles themselves, not by subdividing space and handing out the bounding volumes accordingly. The hierarchy method has a couple of benefits, but isn't dramatically different.

You're free to use the engine in a game contest, and if you get to the point where you can sell your game (publishing deal from Dream Build Play, etc), you can contact me for a commercial contract. You don't need the commercial contract until you are ready to sell it, though. One of the available pricing plans is free upfront and free for the first 1,000 sold copies and a small amount per copy afterwards so you need not worry about getting stuck with a game you can't afford to license. If you want all the details, send me an e-mail.

Of course, you would also have to check to make sure the contest permits third party libraries without source. Not sure about DBP's stance on that since they don't have the main challenge's rules up yet. I'd assume it would be fine :d
sueds
Posts: 43
Joined: Tue Feb 05, 2008 10:40 am

Re: using a custom octree with bepu

Post by sueds »

I don't think I'll sell my game,the first prize is just money, I'm not sure Indies games are really suited for video game industry. Anyway I'm glad to hear that I can use your physic library in my game.

I'm really curious about the triangle bounding hierarchy thing. I mean you stored the indices and then you applied an custom bounding shape ? how is it working ? you check for example every triangle with the same normal and then you create a wall ? or is it something really different. I'm just trying to learn more thing about physic, so I hope you don't mind all my questions.

Do you have an idea about when the v.5 will be released ? Is your physic engine run on low end computer ?

cheers
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: using a custom octree with bepu

Post by Norbo »

Basically, the structure just splits the mesh into continually subdivided groups of triangles until a minimum number of triangles is reached, at which point there if a leaf node with a list of its children triangles (some implementations might choose to continue subdividing until there is only one triangle per leaf). Each child node's bounding box is entirely contained within its parent's bounding box, all the way up to the root. This structure allows for O(logn) time for creating new triangles for collision at the appropriate locations, since you just need to compare the bounding box against the root, then against the children, then against the children of the node(s) that were intersected by the entity's bounding box, and so on until the bottom.

During initialization, the tree must be created. It starts with a mess of unorganized triangles. You can compute the axis aligned bounding box of the whole mess from the points of the triangles. Then, a fairly intuitive method for setting up its children is to find the greatest length of the bounding box (along X, Y, or Z axis), and sort the triangles along that axis. You can then split the sorted triangle list in two (for a binary tree). Those two lists are the triangles of the children, whose bounding boxes can then be computed. This process continues recursively until all the leaf nodes are created.

A normal octree implementation would be somewhat similar, though I view it as slightly less intuitive for this application since you have to consider the space being divided into traditionally equal size parts. This doesn't fit the data as closely as something built directly off the data like the bounding volume hierarchy. Additionally, the octree could store duplicates in multiple leaf nodes (assuming no precaution was taken to prevent such a thing), making it a little more difficult to deal with.

Another fancy benefit of the hierarchy is that if you deform the mesh (as you can do in v0.5.0), you need not rebuild the entire hierarchy/tree. The bounding volumes can be refit bottom-up by recomputing leaf node bounding boxes, then the parents, then the grandparents, and so on. This is significantly faster than reinitializing the entire structure, which I believe you would end up doing in some form with an octree. Note that if the deformation is extremely severe, like the mesh being torn and twisted into an entirely new shape, the new refit tree will be far from optimal. It will still function, but it works very well when the triangles' relative positions and connections are kept somewhat stable.

There's still a few big features in v0.5.0 left to do, but I should be able to finish it up and get everything ready within a matter of weeks. Possibly mid-April, hopefully sooner.

The engine runs pretty quickly on lower end computers, but some care will have to be taken. Toy situations such as the pyramid run fairly acceptably in the demos because the application is allowed to take as much time as necessary per frame (this is common in pretty much all physics engine demos). For a game, you don't have this luxury and must pump out the updates in time. To maintain comfortable FPS under this context, keeping the iteration count low (or using the dynamic iteration count), and avoiding large, heavily interacting groups of physics objects during normal gameplay is advisable. For a physics load in a normal game, perhaps on the same order of magnitude as your average Half Life 2 map, there should be no performance problems even on low-end hardware.

I also continually optimize the engine of course, including v0.5.0's massive reduction in memory allocation (almost zero now). These sort of changes, and the inclusion of multithreading in a future version, will keep performance very high.

Personally, I develop on a bit of a beast computationally speaking, so I try to check performance on the Xbox360 and on older computers when I can to keep it in perspective.
sueds
Posts: 43
Joined: Tue Feb 05, 2008 10:40 am

Re: using a custom octree with bepu

Post by sueds »

you are right about octree it subdivide the space instead of the mesh. So basically it would be a better idea to wait mi April instead of trying something too tricky as I was thinking. I wasn't sure to succeed anyway...but your technique looks very interesting, I might take a look on this method ( just for curiosity)
I haven't look at your code yet (I've just test the performance) so I don't know how hard it to implement in the game.
I'm planning to make a 3d walkthrough with a 3d interactions, but my programming skills are low. I'm a test to see how to build a project on xna.

So there is my question what kind of entity should I use for a player class ? I'm planning to make two view 3rd and 1st. So the collision will also made with a character. I'm looking for the most basic way to avoid the character going through wall, being able to jump with gravity.

Do you have any kind of ray collision for the camera ?


Image

the first published picture of my little project just to show you some passionate people are following your project !

cheers
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: using a custom octree with bepu

Post by Norbo »

Neat screenshot, looking good :D

Raycasting and character controller support are two of the new features I'm finishing up now for v0.5.0. There are some stability issues with the ray-entity test in v0.4.0 unfortunately, but v0.5.0 fixes them and provides an easy method for testing intersection against meshes and other entity groups, as well as a space.rayCast function which tests all candidates in an efficient manner. Firing a ray out from the character to the desired camera position would give you an appropriate location (and normal/time parameter if you need it). I should mention that there is a ray-triangle intersection test special case in the Toolbox as well, and it has no known stability issues. If you need to compare a ray against a triangle prior to v0.5.0, this would work.

Character controllers will provide a pretty powerful basis for moving players around. Currently, the DynamicCharacter type supports friction, jumping, air control, maximum self-propelled speed in both air and ground, and interaction with the environment (pushing stuff around, rolling barrels by running on top of them), amongst some other things I'm forgetting as I don't have the code in front of me. This character type is based on a physically simulated body (whose inertia tensor can be set so that it cannot rotate, or you can use a constraint to keep it upright), which can be of any shape (including compound bodies). There may also be a non-dynamic character, which is based on a nondynamic entity (Currently called static in v0.4.0, though that is changing with a new entity organization in v0.5.0). A nondynamic character might not make it in if the dynamic character turns out to be superior in essentially every case.

The easiest method that doesn't involve the character controller in v0.5.0 would be a physically simulated sphere that your camera follows around- not exactly a great solution, but it is easy and is pretty simple to add input controls (simply modify momentum towards the given movement direction). Jumping would be simply checking to see if you're touching anything first (number of contacts in the entity's controllers > 0, perhaps checking to make sure the contact is on the bottom of the sphere), then applying an upward impulse.
sueds
Posts: 43
Joined: Tue Feb 05, 2008 10:40 am

Re: using a custom octree with bepu

Post by sueds »

Ok I'm going to try out your physics engine and wait for the next release. Is the physic API changing in the .5 version ? The character controller seems really interesting I hope I'll understand everything in your code to be able to use it properly.

cheers
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: using a custom octree with bepu

Post by Norbo »

Basically v0.4.0's organization of entities, which branched into Box, Capsule, and other types and THEN to a Phys(type) or Static(type) has been reworked. In v0.5.0, there are no longer Phys or Static prefixes, you can create the type directly. As a side effect, you can now convert an entity from dynamic (operating on momentum) to nondynamic (operating on velocity only, or static) and vice versa without having to recreate the entity since the only differentation is whether or not some properties are set up.

The rest of the API changes are basically the expansion of an Updateable framework (an open ended setup that allows you to create classes which are updated by the space directly), but that isn't much of a change as it is an addition.

The demos source upon v0.5.0 release will also include a heavily commented Character class, showing a way to use the character controller with input and the demos camera.

And by the way, if you do happen to find something that is unclear or you can't understand, go ahead and ask or tell me- it will help me improve documentation and make things more intuitive.
sueds
Posts: 43
Joined: Tue Feb 05, 2008 10:40 am

Re: using a custom octree with bepu

Post by sueds »

hello ! its me again ! I've managed to make a sphere fall on a plane but the problem is the plane is only a mesh. I don't understand why it collides with the sphere.
the problem I have is that the sphere is not rolling or anything. What value do I have to set up ? when it touch the plane, the game seem to slow down. Maybe I did something wrong.

I didn't understand how I could add a static meshes as a plane. I need to use the Static Convex Polyhedron entities but I didn't understand the way I can use the toolbox.
Anyway I trying to start simple collision detection and it's pretty simple. The code could be confusing if you haven't any experience of programming for list and all the thing you are using but I did understand almost everything. You did a really great job, it's seem easy to implement and to use. If you create some user page ( a sort of wiki) I'll wrote a small tutorial !

I found a way to set up the camera with a ray or with the collision itself. when I create the 3rd person camera I set a position for the camera using an offset with a vector3. I just have to check for a collision from anywhere and if the collision is made the camera will substrate 1for example 1 to offset.z and the matrix will handle the movement and make it move. I'm not sure that I'm really clear but if I manage to understand everything in the way to use bepu, I'll make a example. maybe it's help

I'm really enthusiast about your next features ! keep it up
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: using a custom octree with bepu

Post by Norbo »

I'm not sure I understand the first part; it sounds like you've created a very large convex polyhedron and dropped a ball on it. The ball then doesn't move properly and things slow down after collision occurs. If this is the case, its likely that the 'ground' you've created is too large for the collision detection to handle effectively. The system likes shapes of fairly similar magnitude, staying away from the extremes when possible. This sort of problem might appear if your 'ground' was many thousands of units across. Shrinking it should solve the problem in this case (I haven't seen any problems with a 100x100 static box, for example).

If you have the sphere setup but you can't get it moving around, it can be pushed around in a few different ways, easiest of which being directly modifying its linear momentum. Other methods are angular momentum, the applyImpulse function, or Forces.

If you're actually talking about a loaded in mesh made of triangles composing a ground plane, or even an airplane (I'm pretty sure this wasn't what you meant, but just making sure :D), you could be encountering a similar issue to above (in the ground plane case) or a slowdown associated with many triangles in the airplane case.

Quite a while ago, I actually had a wiki up and running for BEPUphysics. Unfortunately, the moderation time required to keep it clean of spam bots was excessive, and I was forced to take it down. There's a good chance that I'll try to get another sort of community documentation/sharing system up in the future, though.
sueds
Posts: 43
Joined: Tue Feb 05, 2008 10:40 am

Re: using a custom octree with bepu

Post by sueds »

the plane I used wasn't a convex polyhedron, it was a single mesh created in maya. Maybe it's a bug because in the same scene there was a box and it didn't collide with the sphere.

anyway I have few questions;

how can I set up the force with a world coordinate value, to avoid my box from rolling?
I set up a linear momentum with a vector.Y = -20 and the box was floating in the air. what's wrong ?
is there a sort of matrixCreateTranslation stuff ?

anyway everything is going smoothly maybe I'll be able to finish the camera collision stuff before the end of the week, if someone need it I'll publish it.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: using a custom octree with bepu

Post by Norbo »

I'm still not quite sure of the situation, is it a series of triangles based on the loaded in mesh composing a large plane? It still might cause the mentioned problem if the triangles are huge.

You can create continuous forces by creating instances of Force and using the (Entity).applyForce method. These forces are in world space, though you can choose to have them 'track' the entity and follow its position (and rotation if you'd like) relative to its original location.

If you actually want a method to keep a box upright at all times, like a constraint, that isn't explicitly supported in v0.4.0- you'd have to make it externally. A functionality like this will be available in v0.5.0 (and you will be able to modify the inertia tensors of objects, which offers an easy way to keep objects from rotating along given axes).

I'm not sure exactly why changing the linear momentum would have no visible effect. Are all of the entities you're using added to the same space (space.add)? And if so, are you calling space.update in your update method?

Entities can be translated by using the move and moveTo methods, there isn't a "apply matrix transformation" operation available, if that was what you were talking about. The best method for rotating is using the applyQuaternion method.
sueds
Posts: 43
Joined: Tue Feb 05, 2008 10:40 am

Re: using a custom octree with bepu

Post by sueds »

if I understand well using force for a box is not recommended because the box will keep rolling.

Linear momentum is not working and all my entities are set up correctly ( gravity is working for all of them). So I don't know... I'm going to make few test to see what's going on.


cheers
Post Reply