2
$\begingroup$

I have a mesh already partitioned into disjoint groups of cells. What I want to achieve is the following.

  1. Obtain the adjacency graph for the cell groups.
  2. Partition the mesh, i.e. generate submeshes from the cell groups in such a way that cells among the interfaces (boundaries of the cell groups) are no longer connected. This leads to new node numbers.

Notes:

  1. I do not need to know to adjacency graph of the mesh cells, rather the adjacency of the cell groups.
  2. Ideally, I am looking for ready software solutions, so that I don't need to reinvent the wheel.
  3. Python solutions are preferred.
  4. I work in two spatial dimensions with a single cell type (either fully triangular or fully quadrilateral).
  5. Efficiency is not my primary concern.
  6. Typically, in my application, the number of cells is at most 100k, while the number of cell groups is about 250.
Improve this question
$\endgroup$
11
  • $\begingroup$ Have you tried Metis? $\endgroup$ – Alone Programmer Dec 21 '20 at 18:34
  • $\begingroup$ @AloneProgrammer I considered METIS but, as far as I know, it will partition the mesh automatically or based on some hints, while I want the exact partitions given by the groups of cells. $\endgroup$ – Zoltán Csáti Dec 21 '20 at 18:37
  • $\begingroup$ So just for clarity: you mean you have the cuts and you want to just extract the partitioned mesh based on your given cuts (i.e. given groups of cells)? $\endgroup$ – Alone Programmer Dec 21 '20 at 18:38
  • $\begingroup$ Yes, that's what I want (2nd requirement in my post). But I would also like to establish the connectivity of the groups (1st requirement in my post) if possible. $\endgroup$ – Zoltán Csáti Dec 21 '20 at 19:51
  • $\begingroup$ The hard part (the mesh partitioning) is already done. Frankly, you're asking for help on the easy part, although this type of bookkeeping coding can be tedious. I wouldn't consider it "reinventing the wheel" as much as just another part of the day-to-day unglamorous work that many of us do. What you're trying to do looks rather mundane, but custom enough that it seems unlikely to me that you would find that exact functionality in an existing library. Even if you did find what you needed, it might take longer to port your data structures to the library's data structures than to just implement $\endgroup$ – LedHead Dec 21 '20 at 21:47
3
$\begingroup$

For your first question, constructing the adjacency graph of the "partitions" (what you call "cell groups"): Let's say you have an array $p_K$ in which you store for each cell $K$ which partition $p$ it belongs to. Also assume that you have a (sparse) array $a_{KL}$ whose entries are true if cells $K$ and $L$ are neighbors ("adjacent"). Then partition $s$ is "adjacent" to partition $t$ if $t$ is in the set $$ \left( \bigcup_{K, p_K=s} \; \bigcup_{L, a_{KL}=\text{true}} \left\{p_L\right\} \right)\setminus \{s\}. $$ (In other words, we loop over all cells $K$ in partition $s$, then over all neighbors $L$ of these $K$, and collect their partition indices. This union contains all partition indices that partition $s$ is adjacent to, but will likely include $s$ itself -- so we throw away $s$ at the end.

For your second question, visualization -- this is typically done in the following way:

  • For each partition $s$, compute its center of mass $\mathbf x_s$, for example by taking the average of the centers of the cells in this partition.
  • Compute the center of mass of the entire domain $\mathbf {\hat x}$, for example by taking the average of the centers of all cells.
  • When visualizing the mesh, you draw each triangle with an offset $\alpha (\mathbf x_s - \mathbf {\hat x})$ with a small $\alpha$ -- say, $\alpha=0.05$. In essence, what this does is move each partition outward from the global center of mass by a distance that is proportional to how far that partition already is from the center of mass. Some visualization programs can already do that for you -- the option is typically called "explode".
Improve this answer
$\endgroup$
7
  • $\begingroup$ I don't think the second question is about visualization, it's just about renumbering the tri/quad connectivity information. $\endgroup$ – LedHead Dec 22 '20 at 16:40
  • $\begingroup$ I'm really not trying to start a fight here, but I don't think this answers the question any better than my answer. OP is asking for help with some mesh processing, and simply expressing the problem in math formalism seems unlikely to help. $\endgroup$ – LedHead Dec 22 '20 at 16:49
  • $\begingroup$ As for my second question: I am not concerned about visualization (sorry for the misnomer "explode", which is used in the context of visualization), but -- as LedHead noted -- I would simply like the renumbering of the nodes. I edited my question accordingly. Nevertheless, thank you for the mesh "explode" algorithm. $\endgroup$ – Zoltán Csáti Dec 22 '20 at 17:43
  • $\begingroup$ I understood your algorithm. However, in order to obtain the sparse connectivity matrix $a_{KL}$, one has to create the connectivity graph of the whole mesh (in my case, the mesh is given by the cell-vertex matrix and the vertex-coordinate matrix). I think, this will be the costly part of the algorithm. At least third-party libraries can perform this task. $\endgroup$ – Zoltán Csáti Dec 22 '20 at 18:36
  • $\begingroup$ @ZoltánCsáti Ah, I see now how I misunderstood the "explode" part. As for $a_{KL}$: The cell-vertex matrix is what you need for that, along with its transpose. In fact, if $b_{Kv}$ is a 1-0 matrix that corresponds to which vertices $v$ are parts of cells $K$, then I believe that $a_{KL} = \sum_v b_{Kv} b_{Lv}$, i.e., you have that $A=BB^T$. If you think about this a bit, you'll realize that you don't actually need the connectivity matrix for the whole mesh, but that it is enough if every process (=owner of one partition) knows about its cells plus one layer of ghost cells. $\endgroup$ – Wolfgang Bangerth Dec 22 '20 at 19:09

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.