2
\$\begingroup\$

I have a mesh like this (it's all a single mesh):

enter image description here

How I can figure out that the one floating piece is completely disconnected from the rest of the mesh?

\$\endgroup\$
3
  • \$\begingroup\$ With extreme difficulty. Also, I'm going to edit your question it make the goal more clear. \$\endgroup\$ – Draco18s no longer trusts SE Dec 18 '15 at 16:58
  • 1
    \$\begingroup\$ It's a lot easier to detect 'floating cubes' from the voxel data you have (assuming that you are generating the voxels dynamically). \$\endgroup\$ – user9790 Dec 18 '15 at 17:46
  • \$\begingroup\$ @JaakkoLipsanen That's a good idea, i will try it. Thanks. \$\endgroup\$ – S. Tarık Çetin Dec 18 '15 at 17:48
2
\$\begingroup\$

As Jaakko Lipsanen said above, it's likely much simpler to detect this elsewhere in your code (from raw voxel data, or from the code that mutates the world).

However, if you do decide to work from mesh data alone, as long as you're not trying to compute this on a per-frame basis, there are lots of ways to do this.

Normally you'd check for connectivity using breadth- or depth- first search. However in the case of a mesh, you typically do not have the data in a convenient form for that. I.e., to do a BFS/DFS you'd want to start at a vertex and traverse one or more of its edges, but given a vertex you don't directly know the edges. What you do know is the triangles.

To leverage this, I think instead of a normal graph connected-ness search, I think I would solve this using something similar to a flood fill. https://en.wikipedia.org/wiki/Flood_fill

(I believe there's a proper name for the algorithm below that is not 'flood fill', but I can't recall what it is right now, and Google's not helping.)

Approach overview:

  • Iterate over all triangles
    • Assign vertices to a "connected set" according to the following:
      • If the vertices are all unassigned, create a new set and assign them to it.
      • If only one vertex has been assigned, assign all of them to that set.
      • If there are two or three sets represented,
        • pick one to be the new merged set ID,
        • assign all the vertices to it,
        • do bookkeeping to merge all the vertices into that set.

Here's an unoptimized, uncompiled, untested partial implementation. Set merging can be made O(1), but for clarity using an O(n) merge. The HashSets aren't necessary in a tighter implementation, but again, clarity. Overall with the O(n) merge, this is O(n^2). That might be fine if the meshes are small-ish and you're not running it often.

O(1) merge is pretty straightforward - just stop overwriting setIDs every iteration, and instead maintain set ID equivalence hashsets. Then if you need, you can make one final pass to rewrite all the ids to one per "set set", which would still be O(n).

private void determineMeshConnectedness(Mesh mesh){
    // setIDs records which set each vertex belongs to
    // at the end of the algorithm
    // 0 means unassigned
    int[] tris = mesh.triangles;
    int[] setIDs = new int[mesh.vertexCount];
    int nextSetID = 1;
    HashSet<int> activeSetIDs = new HashSet<int>();
    HashSet<int> triSetIDs = new HashSet<int>();

    for(int i=0; i<(tris.Length-2); i+=3){
        triSetIDs.Clear();

        // get the sets this triangle touches
        triSetIDs.Add(setIDs[tris[i]]);
        triSetIDs.Add(setIDs[tris[i+1]]);
        triSetIDs.Add(setIDs[tris[i+2]]);

        // ignore 'unassigned' set
        triSetIDs.Remove(0);

        if(triSetIDs.Count == 0){
          // create new set, assign all vertices to it
          createNewSet()
          activeSetIDs.Add(nextSetID);
          setIDs[tris[i]] = setIDs[tris[i+1]] = setIDs[tris[i+2]] = nextSetID;
          nextSetID++;
        } else if(triSetIDs.Count == 1){
          // assign each vertex to the single set found
          IEnumerator<int> hse = triSetIDs.GetEnumator();
          hse.MoveNext();
          setIDs[tris[i]] = setIDs[tris[i+1]] = setIDs[tris[i+2]] = hse.Current;
        } else {
          // merge the sets, store set they were merged into
          int combinedSet = mergeSets(triSetIDs);
          setIDs[tris[i]] = setIDs[tris[i+1]] = setIDs[tris[i+2]] = combinedSet;
        }
    }

    // At this point, activeSetIDs should contain the list of connected mesh IDs
    // And setIDs marks which set each vertex belongs to

    // do whatever with this information
}

// lots of ways to do this
// this one is O(n) in the number of vertices
// returns the set ID everything was merged into
private int mergeSets(HashSet<int> triSetIDs){
    IEnumerator<int> hse = triSetIDs.GetEnumerator();
    hse.MoveNext();

    // choose to merge into first set ID, arbitrarily
    int finalSet = hse.Current;

    // update now-dead set IDs to new set
    for(int i=0; i<setIDs.Length; i++){
        if(hse.contains(setIDs[i])){
            setIDs[i] = finalSet;
        }
    }

    // remove dead sets from active list
    while(hse.MoveNext()){
        activeSetIDs.Remove(hse.Current);
    }

    return finalSet;
}

Hope this helps. Let me know if you find any bugs, or if it doesn't work at all!

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.