Split uniform, 3D, orthogonal grid into "bubbles"

#1

I need to decompose a uniform 3D orthogoanl grid into subdomains such that 1) each subdomain has approximately the same number of vertices (inside) and 2) the subdomains, under that constraint, are as relaxed as possible.

In other words:

I need to decompose an arbitrary volume which is delimited by orthogonal faces into subvolumia of equal size and as relaxed as possible (the discrete “grid-based” solution is then the best approximation of this continuous decomposition).

Although this seems like a typical problem one would be faced with in, say, HPC, I cannot find any good resources on this. I have some ideas, but those are rather vague and given, that such a problem must have been solved thoroughly in the past, I was wondering where to find literature on the etablished algorithms. Do you have an idea?

#2

What are your boundaries? From a purely theoretical point of view, if distribution is uniform, you can reach excellent matches by just going down a grid discretisation until all cells have one point in them, but obviously this is not what you’ll want.

Are you memory or performance bound, or both, with your current solution?
It might help to know what problem you wish to solve.

At a guess, it sounds like an OCtree with leaf constraints and recompute neighbors on leaf differences would do what you want, but you seem to want to stick to a grid.
If the grid can’t be hierarchically partitioned or have differently sized cells, there’s little you can do about it other than subdividing it linearly until your lightest and heaviest leaves/cells are within an acceptable difference.

#3

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.