Archived

This topic is now archived and is closed to further replies.

Hybrid

Detecting floating geometry

Recommended Posts

I''ve always wondered how you go about detecting floating geometry in a mesh. Floating geometry being an unconnected piece of geometry that has not been dealt with. Take the game Red Faction as a perfect example - if you were to fire a load of rockets in a big circle on a big wall to create a solid bit of wall left floating in the middle of the circle - how could that floating piece be found/detected in the mesh? Given that you''re only likely to have a list of triangles, edges and vertices in the object mesh. It seems complicated to me, but I thought that it would have to be some kind of recursive function that starts at ground vertices (lowest y value) and then goes through all the connecting triangles and say they are not floating. What you are then left with is all the floating geometry I guess. Sounds slow though. Any clever ideas?

Share this post


Link to post
Share on other sites
Hmm. You''d need to specify which piece you wanted and which piece you didn''t... otherwise you risk culling your entire world and leaving the piece of brick wall there

Perhaps this could be done with an adjacency table - do an A* search through it or something, starting at a triangle you know needs to be removed. A little like a flood fill.

Share this post


Link to post
Share on other sites
Well I need to detect which bit is floating so it can be dealt with - made into a separate rigid body or destroyed.

You just kind of solved the problem for me. You mention that you could do an A* search from a triangle that you know needs to be removed. However I don''t know which ones could potentially be floating or not. But then it clicked - since the rocket fire would take a hole out of the wall every time, you could perform the A* search on all the triangles/vertices that touch that hole.

I guess that would be the fastest way anyway.

Share this post


Link to post
Share on other sites
If I remember correctly, the world of Red Faction was not entirely destructible. Only certain areas suffered from fire. Everything else would reduce playability too far, as it would be possible to block your own way.

So this leaves you with weak and strong areas. Strong areas always exist and cannot be destroyed. Floors are candidates for such areas. Weak areas can be destroyed. At this point you decide if you do a FES for the deformable, weak areas or just assume that as long as it is connected to a strong point it''s ok, otherwise it evaporates.

---------------------------
I may be getting older, but I refuse to grow up

Share this post


Link to post
Share on other sites
quote:
Original post by Dreamforger
If I remember correctly, the world of Red Faction was not entirely destructible. Only certain areas suffered from fire. Everything else would reduce playability too far, as it would be possible to block your own way.


More of a problem is that it would allow the player to actually leave the world - if they just point in one direction and keep firing, eventually you''d run out of geometry for them (unless you''re doing something crazy like procedurally generating the world).

Flagging polygons as destructible/indestructible, and simply factoring that into a more general search technique (maybe like the one I mentioned) would probably be the best approach.

Still, as far as a destructible world goes, the floating geometry probably isn''t much of a problem. Assuming that you''re using something like CSG to construct the world (and I think you''d have to) then the bigger problem would be arranging things so that the triangles you''re removing reflect the impact correctly; building your wall out of a single quad isn''t going to look great if you just fire an RPG blast into the middle of it

You could just subdivide the wall beforehand - use 16 quads instead of 1 - which would certainly give better results, but means that you''ll be pushing many more polys for something which, if the player *doesn''t* try to blow it up, only needs 2 to achieve the same result. Plus, we''ve not thought about the fact that usually, in-game solids have depth; removing polys from the point of impact will create a hole in the wall as it faces you, but you want to create a corresponding hole in the other side and connect the two (so that they can''t see ''inside'' the solid).

Perhaps some form of realtime CSG - or at least, dealing with brush volumes - is what''s required. Using halfspaces or clipping planes to divide the brush volume up into destroyed and non-destroyed pieces, and then regenerating the mesh for it using them... of course, quite how you perform that division will depend upon (a) the material the wall is made from, and (b) the object impacting with it.

Richard "Superpig" Fine
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4 | Enginuity5
ry. .ibu cy. .y''ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu
"Don''t document your code; code your documentation." -me
"I''m not a complete idiot; parts of me are missing." -}}i{{

Share this post


Link to post
Share on other sites