Sign in to follow this  
b34r

Polymesh and... boxes :) (demo inside)

Recommended Posts

Finally got around implementing polymesh/OBB in my coldet library. It's far from perfect especially on the culling side (KDtree/AABB does not work that well here). Compound objects (such as chairs) do not work yet, for some reason (errr, okay bug). The boat mesh is more of a crash test than anything meaningful but it works fairly well. while we are at it I'm interested in how people usually determine the contact set in a poly/OBB collision. I'm clipping the polygon to the OBB but it's nasty because it tends to allow the box to sink or stop in non-equilibrium state. There's not much else to say on the technical side. Maybe that it's SAT polygon/OBB not triangle/OBB so, for example, the floor of the large scene is a single polygon with 16 side... Ah, and yes, the tests are not swept so in the large scene boxes occasionally miss the ground when falling from high enough, of course the lower the frequency the worse it gets. Contacts are processed sequencially because I don't have the per contact depth in the poly/OBB test. That's something I'm thinking about lately, swept test are not especially complicated using the SAT but what to do when a completely missed collision is found? Obviously a penetration correction does not make much sense anymore... or does it? Well, anyway, here it is. Comment and speed report welcome.

Share this post


Link to post
Share on other sites
Quote:
Original post by glSmurf
great work =)

Its realy fun to play with and it makes me want to finish my own demo right away.


Thanks and go on :). I want to see it! As well as Oliie's one :)

Share this post


Link to post
Share on other sites
putting boxes in the SUV creates lots of contacts and it runs real slow

also, sometimes you have a box jitter on the uneven ground with like 6 contacts changing every iteration....

usually however it runs very well

[your wireframe draw mode is pretty slow though, at least on my ati radeon 9600se]

Share this post


Link to post
Share on other sites
Quote:
Original post by b34r
Quote:
Original post by glSmurf
great work =)

Its realy fun to play with and it makes me want to finish my own demo right away.


Thanks and go on :). I want to see it! As well as Oliie's one :)


You will see it soon ...its just that it has a few bugs in the app framework (view looks skewed) and it won't be much to look at compared to your demo =)
It is not optimized at all, using only brute force collision detection without bounding volumes (aabb or similar).

I code using the simple principle:
1. just make it work
2. make it work better
3. goto step 2
4. sleep/rest/eat =p

currently I'm at step 1 =)

Share this post


Link to post
Share on other sites
Quote:
Original post by sit
putting boxes in the SUV creates lots of contacts and it runs real slow

also, sometimes you have a box jitter on the uneven ground with like 6 contacts changing every iteration....

usually however it runs very well

[your wireframe draw mode is pretty slow though, at least on my ati radeon 9600se]


Yes, well the mesh is a bit too dense for a collision mesh (not to mention dirty) but you are right, I need some sort of contact reduction... The wireframe on polymesh is really debug code so every polygon is CPU transformed before being send one primitive (line) at a time to D3D :) I guess I could use some specific code for rendering wireframe meshes.

Quote:

I code using the simple principle:
1. just make it work
2. make it work better
3. goto step 2
4. sleep/rest/eat =p

currently I'm at step 1 =)


Quite a good way to go :). It's hardly ever possible to make a complex system working perfectly at once. That's what I'm doing, adding things one after the other. But the more you add the longer the TODO list gets :(.

Share this post


Link to post
Share on other sites
Yes - very nice :) You definitely need swept tests though - the crates very easily get stuck (e.g. go inside the ship cabin and throw some around) - and the problem will get much worse if you use smaller (i.e. normal) size objects. Maybe that's the problem with your chairs?

Share this post


Link to post
Share on other sites
Quote:
Original post by b34r
Quite a good way to go :). It's hardly ever possible to make a complex system working perfectly at once. That's what I'm doing, adding things one after the other. But the more you add the longer the TODO list gets :(.


I started off with the idea of making a realy complex system... but shortly I noticed that the more complex the system became the harder it was to make even smaller changes without causing a huge amount of bugs.
Now I try to keep everything as simple and straight forwards as possible. I believe its alot easier to improve already written code than to write perfect code at once. Actually I love optimizing/improving code, so I guess I have saved the best for last =)

Share this post


Link to post
Share on other sites
Quote:
Original post by MrRowl
Yes - very nice :) You definitely need swept tests though - the crates very easily get stuck (e.g. go inside the ship cabin and throw some around) - and the problem will get much worse if you use smaller (i.e. normal) size objects. Maybe that's the problem with your chairs?


Thanks :)

Stuck in the cabin? I manage that on the safety nets around the deck (sorry my vocabulary is seriously lacking in the boat department :)). Polygons are double sided collision-wise so if you don't take care the camera could be sitting on a wall and the crate might get pushed and caught inside a wall.

Swept tests should help a lot indeed but the mesh is seriously bad anyway. Small objects work good, well at least as good as they did before :). The chair problem is that some compounds of the chair simply miss collision (none detected at all) I don't think the lack of swept test could cause that.

My problem with swept tests is that I don't really have a feeling on how I should proceed with correcting largely missed collisions... I don't think that penetration correction only will work as there could be a large number of invalid collisions. That would mean backstepping the physics solver and retesting overlaps all over the place... errg. :( I don't like this idea. Moving the object directly could be acceptable since it ought to be moving fairly fast so it's not like everything was quietly sitting and stacking around it :).

Quote:
Original post by glSmurf
Actually I love optimizing/improving code, so I guess I have saved the best for last =)


Well, if you are like me you will never get there! There's always something new to start :)...

Share this post


Link to post
Share on other sites
Quote:
Original post by b34r
Well, if you are like me you will never get there! There's always something new to start :)...


hehe thats true. maybe I'll start optimizing if(when) the fps get too low. at moment there aren't more than just a few objects in each schene, just to test a new constraint or collisions primitive.

Share this post


Link to post
Share on other sites
Quote:
Original post by b34r
Stuck in the cabin?


Yes - I noticed this in the big cabin (not the one where the captain would stand :). Not really quite worked out when it happens... but it can happen when you're just shooting at a big patch of wall (i.e. not towards a hole etc).

I also noticed that you can get bad collision directions - fire a box at an angle against the side of the ship, and in some cases it comes bouncing back towards you, presumably because it hits a polygon edge. If you sort the collisions by depth (at least between pairs of objects) this problem can be reduced.

Possibly the problem with swept tests and your implementation is that you only respond to the collision after moving the object (I think... may be muddled :) so the algorithm allows penetration to happen, and that is bad with triangle meshes. Processing the collisions before the position update generally results in no (or little - can get bad results in corners) penetration at the end of the step, which is a Good Thing, because collisions are effectively predicted. The bad thing is that objects stop before they hit, which can look odd, especially for supposedly inelastic collisions.

I mentioned before that I had a solution to that. The idea is that the collision detection does a swept test and records (a) the contacts (as offsets relative to each object but in world space) and (b) the estimated penetration depth at that contact at the _start_ of the sweep, not the end. Then:

1. If you have two objects that are really overlapping, the penetration resolution code kicks in and applies impulses to separate them - it constrains the separating velocity to be >= (penetrationDepth * N * dt) where N is maybe 4 or 5.

2. If you have an object sitting "at rest" on a plane, whilst you detect collisions with the plane the penetration depth is 0, so no extra penetration-resolution gets done

3. Lets say all collisions are inelastic. Now, when a collision is detected, rather than constraining the separating velocity at each contact to be >= 0, you constrain it to be >= (penetrationDepth * dt), bearing in mind penetrationDepth is -ve. So, when a object (e.g. ball) is fired straight at a wall and about to hit it: (1) A collision is predicted, and the code calculates an impulse that will result in a normal velocity that places the ball _just_ touching the wall at the next time step (2) At the next timestep, normal inelastic collision occurs, and the ball stops dead, just touching the wall.

One nice thing about this is that exactly the same code is used for this predictive-collision impulse as is used for the penetration resolution, so there's not any extra cost. Oh, and the other nice thing is that it works :)

Share this post


Link to post
Share on other sites
Quote:
Original post by MrRowl
Yes - I noticed this in the big cabin (not the one where the captain would stand :). Not really quite worked out when it happens... but it can happen when you're just shooting at a big patch of wall (i.e. not towards a hole etc).


Okay, I was indeed testing in the captain's one :).

Quote:

I also noticed that you can get bad collision directions - fire a box at an angle against the side of the ship, and in some cases it comes bouncing back towards you, presumably because it hits a polygon edge. If you sort the collisions by depth (at least between pairs of objects) this problem can be reduced.


Yes, it is still a draft implementation and I planned to flag edges in order to exclude them from the axis selection when they belong to a quasi-plane or slightly convex curve. I'm not sure how it will work though...

Quote:

Possibly the problem with swept tests and your implementation is that you only respond to the collision after moving the object (I think... may be muddled :) so the algorithm allows penetration to happen, and that is bad with triangle meshes. Processing the collisions before the position update generally results in no (or little - can get bad results in corners) penetration at the end of the step, which is a Good Thing, because collisions are effectively predicted. The bad thing is that objects stop before they hit, which can look odd, especially for supposedly inelastic collisions.


Correct :) the good might outweight the bad on this one. (edit: I put back the timewarping scheme in and I can't seem to get crates stuck in the wall anymore.)

Quote:

I mentioned before that I had a solution to that. The idea is that the collision detection does a swept test and records (a) the contacts (as offsets relative to each object but in world space) and (b) the estimated penetration depth at that contact at the _start_ of the sweep, not the end. Then:

1. If you have two objects that are really overlapping, the penetration resolution code kicks in and applies impulses to separate them - it constrains the separating velocity to be >= (penetrationDepth * N * dt) where N is maybe 4 or 5.

2. If you have an object sitting "at rest" on a plane, whilst you detect collisions with the plane the penetration depth is 0, so no extra penetration-resolution gets done

3. Lets say all collisions are inelastic. Now, when a collision is detected, rather than constraining the separating velocity at each contact to be >= 0, you constrain it to be >= (penetrationDepth * dt), bearing in mind penetrationDepth is -ve. So, when a object (e.g. ball) is fired straight at a wall and about to hit it: (1) A collision is predicted, and the code calculates an impulse that will result in a normal velocity that places the ball _just_ touching the wall at the next time step (2) At the next timestep, normal inelastic collision occurs, and the ball stops dead, just touching the wall.

One nice thing about this is that exactly the same code is used for this predictive-collision impulse as is used for the penetration resolution, so there's not any extra cost. Oh, and the other nice thing is that it works :)


Sounds very good and clever! :) Makes sense. There's a bit of work to implement your system though... I'm not sure I'll undertake a remodeling of my solver until your next demo ;).

Share this post


Link to post
Share on other sites

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

Sign in to follow this