Jump to content
  • Advertisement
Sign in to follow this  
Hybrid

Floodfilling polygons - weird I know.

This topic is 5144 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Okay, so I have a mesh made out of n-sided polygons. Let's say we have 100 of these faces with 3 or more edges. Each edge points to the two polygons it is part of. Now, say I set a flag in one of these faces to 'true'. All the other faces currently have 'false' as default. What I need to do is pass that 'true' value to all the other faces touching this face (by getting the opposite face pointer from each edge), and in turn those faces will then pass the value onto the faces they touch etc.. etc.. until all the connecting faces have had the value set where possible. I can't just set all the faces in the face list to true, as it's important that they are connected. Specifically this is for detecting floating (unattached) geometry in a mesh. So if I know I have a face that is attached to the ground, I need to propogate this 'attached' value to all the connected faces. Hence this will leave me with the faces that are not connected, and I can deal with them. So basically I need to floodfill the mesh's polygons in a way, propagating a value to all connected, adjacent faces. Is there a better way than:
For every face
    For every edge
        Get opposite face and pass in value
        Tell this opposite face to then pass the value along to its connected faces.
Did that make sense? :-)

Share this post


Link to post
Share on other sites
Advertisement
You could build a winged edge structure, that would improve the speed considerably. The winged edge structure defines for every edge which two polygons use it. That way you can hop from one polygon to it's neighbour using a single lookup.

You can efficiently build a winged edge structure by first making a list of polygons that use a vertex. Build a linked list of polygons per vertex and process all polygons, adding them to the linked list of each of their vertices. After that, you can quickly build the winged edge structure: You only have to check polygons that share one of the vertices of the edge you are processing.

Hope that makes sense. :)

Share this post


Link to post
Share on other sites
Don't forget the stopping criterium:


For every face

For every edge

Get opposite face and pass in value

If (flag not set)
Set flag

Tell this opposite face to then pass the value along to its connected faces.

Share this post


Link to post
Share on other sites
There are two ways that I can think to do this, one would be recursively, and the other would be to use a stack data type (which the recursive method does implicitly). They're both basically identical, but the former does a lot for you (but has limitations such as stack space, and a lot of function calls).

Recursive:

1) Start with the initial "true" face.
2) For each edge of that face, find the connected face.
3) If the connected face is false
4) Set that face to true
5) Call the function (starting at (2)), but with this new face.
6) End If
7) End For



Stack:

1) Push the initial true face onto the stack.
2) Loop the following while the stack is not empty:
3) Pop a single face off of the top of the stack.
4) For each edge of that face, find the connected face.
5) If the connected face is false
6) Set that face to true.
7) Push that face onto the stack.
8) End If
9) End For
A) End Loop


I think those should be correct.

And I bet someone(s) else has already responded before me... Oh well.

Share this post


Link to post
Share on other sites
If its just to detect unconnected Faces, why don't you simply check for each Face if its connected to at least one Other ?
You could simply do:

foreach Triangles
foreach point
foreach Triangle except current
foreach point
does point equal previous currentPoint ?

And if thats true, at least one triangle is connected to this.

I maybe wrong .. that happens :)

Share this post


Link to post
Share on other sites
phantomus - yes, I use a similar edge structure. I use pairs of half-edges to represent an edge. Edges are always in the same direction (clockwise or anti-clockwise)

rick_appleton - Ah yes. I forgot to add that little bit though I did notice it.

Thanks for the replies. So it looks like I'm stuck with doing it this way though. The recursive way decribed that is. I was just hoping for some ultra clever way of doing it.

This should be fast enough though - I hope :-)

Share this post


Link to post
Share on other sites
Quote:
Original post by Wintermute2004
If its just to detect unconnected Faces, why don't you simply check for each Face if its connected to at least one Other ?

It's not as simple as that unfortunately, because there could be a whole group of faces that make up say a brick floating in space. They are attached to each other. But as a whole they are floating in space and I need to detect that group of faces.

Share this post


Link to post
Share on other sites
Long ago i did floodfilling of 2d images.... it was very efficient, worked w/o recursion (my recursive version causes stack overflow on certain images [hahaha, what a security hole.]), used very little ram, and i was very proud of it :)

Generalized version of algo i used (works with any graph, i.e. with faces, and can be also somehow used for pathfinding, i guess):

Make 2 arrays of face indices, both big enough (even in worst case them will not need to store more than all nodes,err.,faces you have), or resizeable (c++ vectors). Also you'll need to have 2 counters that stores how many things you have in array.

Initially, array 1 contains your starting face. array 2 is empty.
array1 is current array,
outer_loop:{
inner_loop:{for each face storen in current array , check all neighbouring faces if their flags is set. If for some neighbouring face it's not set, set the flag and push that face to non-current array (store it on top, and increment number_of_indices storen in non-current array).
}
set number_of_indices storen in current array to zero. Select non-current array to be current. If it's empty, leave the loop.
}

(With 2d images, i've used horisontal scanning strips to search for neighbour "nodes" )

Ops.
Agony's second approach seems to be similar and quite simpler, but requirs more ram (i think,in almost all "normal" cases , all faces will be pushed into array). I think it's nothing bad for meshes. (it was not good for images, but for meshes doesn't matter)

Share this post


Link to post
Share on other sites
That 2 array version sounds interesting. I'd probably use a list though. Whether all that list manipulation is acceptable in real-time, I just don't know? This has to be real-time, so this entire value propagation phase has to be fast, and I'm not sure if the recursive version would be faster or slower than the non-recursive, 2 list version.

Thanks for the idea though, it's got me thinking.

Share this post


Link to post
Share on other sites
It's in fact not good to use lists, unless you wrote your own list class that works good. Lists is better only when you need to delete from center.... it's exactly example where array is alot better.

Main reason why i used 2 arrays, was that as result we have "wave" propagating and it greatly reduces typical number of indices to store (and it's important for image floodfill, where if on image we have dots where (x&1)&&(y&1) is true, one-array approach will store really many things, and recursive approach will store even more due to return adresses and local variables(and may crash) . But it's not *that* important for typical meshes as for especially bad images.
And certanly any non-recursive version is faster than recursive.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!