This project has moved and is read-only. For the latest updates, please go here.

Dynamic updating of geometries

Aug 21, 2009 at 12:48 PM
Edited Aug 21, 2009 at 3:20 PM


I've recently found out about Farseer, and so far I like everything about it, got a simple 2d sandbox up & running in just a few minutes!

But I've run in some troubles while updating geom's at runtime; I use the texture to polygon functionality to vectorize some bitmap tiles. I construct an environment using these tiles which can be blown up much like in Worms. Now when I re-apply the texture to polygon function after altering an tile's pixeldata, I get new vertice data which also has a new centroid. This causes the geometry's position to jump from it's previous centroid depending the difference with the new centroid.

Because the tiles are only used for collision detection (they're set static), the centroid doesn't matter that much for moi etc. I've looked at the source but it doesnt seem to be possible to manually set the centroid for the geom. I tried translating the vertices, and just updating them for the geom. But that way the old geom vertices are still remembered somewhere... maybe the collision grid isnt updated; because the simulation still does collision detection on vertices that are removed (the physicssimulatorview doesnt draw them neither). The only way I got it to work is to remove the altered geom from the simulation, and recreate a new geom using the updated vertices, but this causes the "jump" in position and setting / translating the vertices again after the creation doesnt sound like an efficient solution..

How can I force the updated vertices to be used for collision detection?



Aug 21, 2009 at 3:29 PM

If you are using the Distance Grid narrow phase collider (it is default) you are right. The old grid is kept and that can cause ghost collisions. Since we support multiple narrow phase algorithms it is hard to make an easy interface to recalculate the grid. You will have to do this manually for the time being.

The narrow phase algorithms are in singleton based form, so only one instance is defined. You can call DistanceGrid.Instance at any point in time and you will have access to all the previously created distance grids. You can also create new grids and remove old onces. I suggest you do the following:

1. You have the original geometry, you blow up a chunk of it and end up with a new vertices set.

2. Remove the old distance grid (cleanup to minimize memory usage) using DistanceGrid.Instance.RemoveDistanceGrid(Geom)

3. Create a new one using DistanceGrid.Instance.CreateDistanceGrid(Geom)

Then you should have a new distance grid defined for the old geometry. Distance grids can take some time to calculate, this can be minimized by adjusting the geom.GridCellSize property. Normally the GridCellSize is calculated automatically (and thus it can be wrong) unless you define something yourself.

An alternative is to use the SAT narrow phase algorithm. It does not have to pre-calculate anything and is really more suited for worms-like games. We have had some bugs with the algorithm tho and a new one is in the works (bugs fixed and better performance). Try it out and see if it works for you.

Aug 23, 2009 at 12:21 PM
Edited Aug 23, 2009 at 9:57 PM

Thanks for the detailed reply genbox!

SAT does indeed sound more suitable than a distance grid. I haven't tested this yet, but it sounds like the recalculation of the distancegrid could potentially cause a small hickup when lots of new geometry is created. However, if the newly created geometry is concave, I'd need convex decomposition for SAT to work. I haven't looked thoroughly at the source yet, but convex decomposition is not yet supported out of the box right? And even if it was, it would be a matter of convex decomposition (when using SAT) vs calcuting a new distance field, I'd guess they'd be equally calculation intensive?


Edit: I just noticed in this thread ( that convex decomposition is supported... still the decomposition vs recalculation of the distance grid stands

PS: And just out of interest; What algorithm is implemented for the texture-to-polygon? Marching squares?

Aug 28, 2009 at 11:43 AM

I was testing what approach is better suited (decomposition vs grid), but I'm getting weird behavior with the SAT narrow pahse collider... When an collision accurs using SAT, the object "jumps"; it's positions seems to be reset to a position above the vertice it collided with... (im colliding a sphere against an triangulated texture's vertices/edges), using an distance grid it all works fine.

Also I wondered, with convex decomposition it shows in the debug view that all decomposed polygons have their own aabb. For big environments it is adviced to chunk up everything into tiles, does this still hold when using SAT? (As there seems to be enough AABB's created)

Aug 28, 2009 at 9:05 PM

SAT is still experimental. Matthew is working on a new version but I can't say when it will be out. I'm focusing mainly on 3.0 and it has a robust SAT implementation.

The texture-to-polygon algorithm is marching squares. (I think) - It is a user contribution and that user has retreated to his personal life, so the algorithm contains some bugs for now. Nothing major tho.

The distance grid calculation vs. SAT decomposition really depends on the data and precision defined. You will have to test it for your game only. The distance grid calculation is O(n^2) - I can't remember what the Earclip is, but I think it is O(n log n). If you time both on the same dataset (polygons) I would like to see what the results are.