Destructible ground and Farseer

Topics: Developer Forum
Jan 21, 2011 at 10:59 AM

Hey.

I've been thinking about how destructible ground could be accomplised for some time now and not really gotten to any real solutions.

Most of my ideas so far have all been modifications of this idea:

Create a Texture2D with black for ground and transparency for air.
As the ground changes i add or subtract black area to the texture.
Everytime the ground changes start a separate thread that decomposes the texture into a set of polygons using one of the methods available with Farseer, once decompositions is done replace the current ground polygons in the engine with the new ones.

One of many problems with this (aside from that polygon decomposition is slow and unstable) is that the ground texture could be divided into multiple polygons with air between them. I would then first need to cut out all the individual polygons from the main texture.. Something i havent even started to think about yet.

So, im hoping for some tips or general ideas.. is there a way to do this, has anyone done anything like this before?

What i would really like to accomplish in the end is a ground that behaves similairly to this:
http://www.youtube.com/watch?v=56QoKI85P6c

It is constantly reformed and behaves with the physics objects.

Thanks

 

Developer
Jan 21, 2011 at 4:06 PM

Marching Squares is the proper algorithm for this problem. An alpha version of the algorithm has been added to the source control. I am currently working on a demo of destructible terrain, but you'll have to wait until it's done!

Jan 22, 2011 at 2:58 PM

Hey.

Thats great news.

Do you have any sort of estimated date for when it will be ready for use?

 

Thanks!

Developer
Jan 22, 2011 at 10:28 PM

It's being worked on right now and should hopefully be ready be the end of the month.

Jan 23, 2011 at 12:06 AM

Another way to do it, which I think Little Big Planet probably uses, is polygon boolean operations. (YuPeng Clipper in Farseer)

So you'll have a single rectangle for the ground, and then each time an explosion happens you'll create a circle shape and subtract it from the ground.

You'll need to triangulate the shape and creating a vertexbuffer each time it changes, for drawing.

I have done this in my game and it works well.

Jan 23, 2011 at 9:16 AM

@mattbettcher: Thats great, looking forward to it :)

@robertdodd: This also sounds very interesting. Was trying to find some examples of this but my googling skills seem a bit off today, coulden't find any examples of this and Farseer, got any links?

 

Jan 24, 2011 at 8:50 AM

I created a patch which demonstrates it. Go here to find it: http://farseerphysics.codeplex.com/SourceControl/list/patches

Its a bit messy but works well. Some other things to add, especially in a game, are:

  • Destroying items when the explosion consumes them
  • Explosion forces (Farseer can do this)
  • Using an AABB to check if items are affected by the explosion before clipping them (this is actually important, but i didnt have time to put it in. its easy though)

Polygon Clipping might be a better solution for separate, smaller items, while Marching Squares might be better for large terrain.

Running a boolean operation on an item that has lots and lots of vertices (like Worms terrain) will be really slow. You'll have to see which method suits better when mattbetcher is done.

You can also probably speed up both methods for terrain by by using tiled partitions.

Developer
Jan 24, 2011 at 9:32 PM

Robert- The marching squares demo will use tiled partitions, but it's actually quite fast. I haven't compared it to doing boolean operations on polygons yet.

Coordinator
Jan 24, 2011 at 9:38 PM

@Robert: I've added the patch to the Testbed. Do you think you could create a real terrain inside the test instead of just a couple of boxes?

Jan 25, 2011 at 2:09 AM

@genbox: Sure thing I'll see what I can put together.

@mattbetcher: That marching squares sample works really great, well done! a comparison would be interesting, I'll try write one up. Are there any areas which you think MarchingSquares would perform badly, like boolean operations are slow with complex shapes?.

Also, does anyone know how to handle holes with the YuPengClipper? I haven't looked too deeply at the code but was wondering if it knows which shapes are holes inside, so they can be flagged or something?

Developer
Jan 25, 2011 at 9:11 AM

@robertdodd: I wrote the YuPeng Clipper and still have some optimizations flying around, i'll try to add them in the next few days... unfortunately im quite busy at the moment :/

Holes have (as far as i remember) a different winding order. So output "vertices" which are holes should be clockwise instead of counterclockwise. I think triangulation already supports holes somehow and distinguishes also via the winding order... correct genbox?

Coordinator
Jan 25, 2011 at 11:39 AM

@Robert: Sounds great.

@Elsch: Correct. The CDT algorithm already support holes, the API just need to be exposed in FPE 3.3. I've also asked David to improve on his texture to polygon algorithm by returning holes with a clockwise winding.

Jan 29, 2011 at 2:49 AM

I'm a bit busy, so just letting you know that it might be a while before I finish a comparison between the 2 methods.

Here's what Im trying to do:

  • There will be three tests
  • Each will use the same terrain and clip-shape both loaded from textures
  • Each test will perform a series of operations on the terrain and time it
  • The tests will be: Marching Squares, Yu Peng on Marching Squares terrain(lots of small bodies), and Yu Peng on a normal Texture-To-Vertices terrain(as few bodies/fixtures as possible, but with many vertices)

I haven't started yet, it might be a while till I get time. If someone wants to do part of it, or has any ideas or suggestions or something just let me know.

Developer
Jan 30, 2011 at 9:28 PM

rob - hold off on starting that comparison until I get the Marching Squares implementation finished. I now have a version that is combining the squares, but there is still a few small bugs to fix.

Developer
Jan 31, 2011 at 11:57 AM

I also have some optimizations for the clipper. Won't make such a big difference though i guess. I'll try to upload them in the next few days. There is still a bug somewhere, which gives me headaches at the moment :/

Coordinator
Jan 31, 2011 at 8:14 PM

@Elsch: How are polygons that are completely enclosed in the clipping shape handled in the clipper? Just wondering if it would remove polygons that are fully contained inside the clipping polygon or just clip along the edge.

Developer
Jan 31, 2011 at 9:06 PM

Marching Squares is almost done...

TODO list-

  • Fix up API.
  • Write helper functions.
  • Write new demos.
  • Change internal CxFastList to be a singly linked list.
  • Hide CxFastList from external API.
  • Do thorough testing of entire API.

Honestly, that's not very much. I'm hoping to have it completely finished by the end of the weekend.

For those of you who are interested the speeds are pretty much limited by the decomposition algorithm. But in the terrain demo I will demonstrate how to use the simple API to create groups of smaller polygons so that the decomposition algorithm can run fast.

Also I'm hoping to get a multi-threaded version in the works once this version is finished.

Developer
Feb 1, 2011 at 11:52 AM

@Genbox: completely enclosed polygons are handled correctly. E.g. on add you get the outer polygon and on substract you get a polygon with a hole.

Coordinator
Feb 1, 2011 at 5:28 PM

I was wondering about the other way around: When you subtract a shape that is bigger than the polygon you are clipping on. Example: You have a circle that you subtract from a polygon, the polygon is fully enclosed inside the circle. I guess the expectations would be that the polygon completely disappear.

Developer
Feb 1, 2011 at 6:46 PM
Edited Feb 1, 2011 at 6:49 PM

And that is exactly what happens, i.e. YuPengClipper returns an empty List<Vertices> in that case.

I just uploaded the "fixes" for the YuPengClipper. I always wanted to optimize the PointInPolygon check further before submitting, but never got around to it. It is fully functional however so I'd rather have it in source control and revisit that later.

There was an issue with the union operation when two polygons only touched. That works now and combines the two polys in that case (before nothing happend).

The only remaining "issue" is that it can produce polygon output with colinear vertices. So before using the output with the clipper again, a check for colinear points should be performed on each polygon (which is needed for correct results). This happens only in some special cases though and one might ignore that to gain some performance so I'm undecided whether to integrate a non-colinear check at the end of the clipper or not.

...especially as it could be obsolete if i want to decompose the output of the clipper anyway. *puzzled* :)

Coordinator
Feb 1, 2011 at 7:41 PM

Excellent news Elsch.

As for the collinear points; I think you should implement the collinear check and remove all collinear points. They cause trouble and are redundant in 95% of all cases. If someone decides to use them, they can always use SubDivideEdges() (Going to implement it again in 3.3) to create collinear points (for whatever reason - seen it before for more random triangulation results).

Developer
Feb 2, 2011 at 9:15 AM

For the sake of completeness: Collinear simplify of the output is now part of the clipper. Depending on the input source you still have to take care to not supply polys containing collinear points. Removing them before and after each operation would overdo things a bit I think.

I also learned that you actually write collinear with two 'l'. 

Last but not least I added asserts to all factory methods that hinder you from creating anything that is bigger than 15 units whatsoever. They throw "Consider converting your stuff to MKS" warnings now ;)