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...

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?

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.

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.

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]

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]

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.