Monday, March 15, 2010

Real-Time Destruction/Fractures

in the last two weekends i'v been working on real time destruction/fractures on 3d models, i always amazed by havok destruction demonstration and even more by red fraction guerrilla.
unlike havok physics/animation, havok destruction isn't free, but i really wanted something like that in my engine.
after few days of thinking and googling, i got few options on how to implement it:
1) get into some really nasty physics using fem model, build tetrahedrons that fit to the model and use it to know which part do i need to break.
2) voxelize the model and use the voxels to know which part do i need to break.
3) clip the model by a plane.
every option need to take care two things:
1) the render model which is the model that you render and contain valid tnb vectors, mapping, position etc.
2) the physics model which you use to do collision with.

the option i implement is 3, because it is very fast to implement, doesn't need to preprocess the mesh like option 1 and does not restrict you with same fracture size like option 2.
also it doesn't take extra memory to store data per model, everything is computed in real time, so if you are not breaking the model it is just like any other model in the scene.
if you break it, it will take the memory needed to store fractures data and that's it.
as you all know (or don't), nothing comes for free, more memory means less cpu work and less memory means more cpu work.
this is always the dilemma when implementing an algorithm, but in this case its not because you can't really preprocess the fractures because you don't really know where the player is going to shot the model.
some games generating fractures in advance and when you shot on the model, the closest fractures is detached from the parent model, in my opinion its doesn't do the work like the real thing and again, memory could be huge if you split the model into small fractures.
another thing to take into account is how many time do you have to implement it, if you don't really have a limit i think you can find some cool idea...
anyway, option 3 can be simplified in few steps:
1. determine the model that you hit, call it M (your physics engine should do the job)
2. split M by a plane into two parts, negative and positive, call them N and P
3. close the holes of N, P using triangulation algorithm (ear cutting or something similar), if you assume convex shapes you can simply build a fan to close those holes very fast.
4. apply uv mapping for the faces that closed N,P holes.
5. build physic shapes for N and P.
thats it, the catch is to do those steps fast!
here is a video to show what i'v done so far, note that in the video step 4 is disabled and you see the same color (all vertices map into 0,0) that's because i need to add option to give faces from step 3 different material so it will look good and not using #1 texture i used in the video


Doron said...

That looks cool :)

Ido Lavy said...

Very impressive.

max said...

Awesome. Any chance for source or tutorial using this technique?

orenk2k said...

10x max
sorry, for now no source code will be released...
as for tutorial, i wrote the main steps and i really don't have a lot of free time to write a complete tutorial.
if you have specific question feel free to ask and i try to help.