Sign in to follow this  

Floodfilling polygons - weird I know.

This topic is 4839 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
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
I agree with Dmytry. Thinking about my method, I realized that it was probably just going to add almost all polygons to the stack before really popping many off. The problem was that the algorithm only popped one face off the stack at a time. The two array method I believe would basically be like popping all faces off the stack, then going through eaching of them, pushing new connected faces onto the stack.

Here's an altered version, using two stacks, pretty much just like Dmytry's. (You could easily get rid of one of the nearly identical loops by having pointers to the two stacks, pSrcStack and pDestStack, and just swap them at the end of the loop.)


Push the initial true face onto Stack1.
Stack2 starts off empty.
While Stack1 is not empty Or Stack2 is not empty
While Stack1 is not empty
Pop a single face off of the top of Stack1.
For each edge of that face, find the connected face.
If the connected face is false
Set that face to true.
Push that face onto Stack2.
End If
End For
End While
While Stack2 is not empty
Pop a single face off of the top of Stack2.
For each edge of that face, find the connected face.
If the connected face is false
Set that face to true.
Push that face onto Stack1.
End If
End For
End While
End While

Share this post


Link to post
Share on other sites
Sounds kinda similar to the A* algorithm...

Pick a polygon from your 'desired' part of the mesh to seed the open list, and have it search for a polygon that does not exist (or is not connected to anything). The algorithm will run, moving polygons you want to keep to the closed list. When the open list runs out of entries, delete any polygon that is not in the closed list. Voila.

Share this post


Link to post
Share on other sites
In my version i just had both stacks storen in array with only 2 elements. edit: and it's not exactly stacks in sence it's better to read array in forward direction in ram while writing into second array also in forward direction...

Share this post


Link to post
Share on other sites
Thanks for all the ideas and pseudo code... Much appreciated.

I'll use arrays instead of lists then. Possibly an STL vector and call array.reserve(n) first to avoid the arrays being resized during filling and deleting. Or is there a better way of having a dynamic array without memory allocation all the time?

Share this post


Link to post
Share on other sites
I think I'm missing something. Why can't the mesh be partitioned in a preprocess? Is the face connectivity changing per frame?

Just to be clear, here is what I have in mind:
1) Partition all faces (into n partitions). Label each face with a partition ID (ranging from 1..n).
3) At run-time, to propogate a value from one face to all connected faces, just loop through the entire list of faces and look for faces with a matching partition ID.

Or, to eliminate the search through the entire list of faces:
1) Partition all faces (into n partitions).
2) Add a "next_in_partition" pointer in your face data structure. Circularly link all faces within each partition.
3) At run-time, to propogate a value from one face to all connected faces, just traverse the circular linked list, stopping when you get back to the initial face.

Share this post


Link to post
Share on other sites
Quote:
Original post by Eric
I think I'm missing something. Why can't the mesh be partitioned in a preprocess? Is the face connectivity changing per frame?

Yes it is. This is primarily for detecting floating geometry after a real-time CSG subtraction has taken place e.g. a hole blown in a wall - detect any floating geometry left behind.

Share this post


Link to post
Share on other sites
Ok, I see... and you must be updating your edge data as you're performing the subtraction.

Alrighty, I have another suggestion. The gist of my approach is this: instead of propagating from the ground and through the entire (grounded) mesh, you propagate out from all the CSG-op-affected and CSG-op-created faces (and you'll typically not propagate out very far).

For each face, you maintain a path from the face to the ground. Specifically, each face has a pointer to its "parent" face, which is just the next face on the path. For actual ground-touching faces, the pointer field holds some special key value. (To initialize these paths, you set all pointers to null or the key value, then you run the "re-parent orphans" step described below.)

During your CSG operation, when the operation affects a face, you make the face an orphan (set the parent pointer to null). You also add it to a list of orphans. Any newly-created faces are also created as orphans and added to the orphan list.

Next, you propagate the orphans: For each orphan in the list, check if it is a parent of any of its neighbors. If so, make them orphans and add them to the orphan list. Repeatedly process the entire orphan list, stopping when the most recent pass failed to add any new orphans.

Finally, you re-parent the orphans: For each orphan face in the list, check if any one of its neighbors is not an orphan. If so, have the non-orphan neighbor "adopt" the face, and remove the face from the orphan list. Repeatedly process the orphan list, stopping when (A) it is empty, or (B) the most recent pass failed to remove any orphans. At this point, the orphan list is your "floater" list.

Hmmm, looking back on this lengthy treatise I've just written, I'd say my approach lacks some of the elegance and simplicity of your original 4-line solution [smile]. On the other hand, if your mesh has a million faces and you only want to process a few hundred or thousand faces near your CSG op, then maybe this is something to consider.

[Edited by - Eric on September 18, 2004 2:35:05 AM]

Share this post


Link to post
Share on other sites
Neat idea. I like the approach and like you said it could be faster for meshes with large numbers of faces.

But what happens when you split a ground/attached face? If you make them both orphans then you may lose the fact they are ground faces. Also if you set them to both ground faces after the split, then there is the problem that you may have split it in a way that only one face is a ground face, e.g. a wall split horizontally halfway up.

EDIT: Just thought of another problem with this. I am using n-sided convex faces, so for example I may have a face with 8 edges meaning 8 neighbours too. Now some of those 8 neighbours' parents may be this face. Now if I split this face, then those parent pointers in the neighbouring faces need to be updated incase they point to the newly created face instead of the original one. This is because it could end up screwing up this test: "For each orphan in the list, check if it is a parent of any of its neighbors". As it may be a parent, but that face is no longer a neighbour. Updating all those pointers, checking each edge and neighbour face will be too slow in real-time I imagine.

Dunno if I explained that well enough, let me try an example.

Draw two squares next to each other horizontally. Call the left one 'square 1' and the right one 'square 2'. Now square 2's parent is square 1 and points to it. Now split square 1 vertically down the middle, and say that the new face is the one on the right, square 3. You'll now see that square 1 is a parent to square 2, yet square 2's neighbour is square 3 not 1.

[Edited by - Hybrid on September 18, 2004 6:51:25 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Hybrid
Thanks for all the ideas and pseudo code... Much appreciated.

I'll use arrays instead of lists then. Possibly an STL vector and call array.reserve(n) first to avoid the arrays being resized during filling and deleting. Or is there a better way of having a dynamic array without memory allocation all the time?

ii'd make my own counters that contains how many face indices you have in array. And not resize your arrays(c++ vectors) down till the end, when array will be automatically freed (leaving the scope). And of course reserve much enough before entering loop - i think something near to 10*sqrt(numberoffaces) should be almost always enough. (if you have million faces it's 10k)
Check your vector's implementation. If it's bad(will call new too many times), you may need to write yourself struct that holds how many vertices do you use, and when it exceeds array size, simply double array size using reserve. So resizing will be rare enough and not a problem. Or write your own vector class that works good for that specific situation.

Make a variable "MeshFloodfillMaxArraySize" in your logger class(or global), and in loop
MeshFloodfillMaxArraySize=min(MeshFloodfillMaxArraySize, arrays[current].size)
("arrays" have 2 elements, each is your array/vector/something )

At the termination of program, display your MeshFloodfillMaxArraySize. So you'll know how much you typically need, double it, and use.

As about Eric 's suggestion, he is right, you should use frame-to-frame coherency, so you'll not need to re-check everything.

It's all is kinda similar to different GC schemes(that is, garbage collection(memory management)). You may read about different GC algorithms.

Share this post


Link to post
Share on other sites

This topic is 4839 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this