Compact storage

Removing mesh elements marks them as "unused". This is efficient (constant time) and minimizes side-effects: the handles of remaining elements don't change. However, this is not storage efficient as there are "gaps" of unused elements in the vectors storing attributes.

A storage efficient representation of a mesh does not show such "gaps", i.e., the sequence of elements is contiguous (see iscontiguous).

The compact! and compact methods rearrange the mesh elements such that all data is stored contiguously. compact! provides an in-place rearrangement, i.e., it does not allocate new storage, while compact generates new contiguous "copies" of the mesh elements' attributes.

Note

This is sometimes called garbage collection, e.g., in the PMP library. We avoid this term.

Stability

The in-place compact! can be executed such that the rearrangement is stable – i.e., the relative order of elements is preserved – or non-stable. The stable rearrangement is the default choice. The non-stable is generally faster.

The compact method always yields a stable rearrangement.

Mapping

You may require mapping old handles/indices to new handles/indices after rearrangement. compact! and compact return index maps for vertices, faces and edges as a named tuple (vmap=vm, fmap=fm, emap=em), where each map vm, fm, em is represented as a tuple of vectors (idx, ridx). If n is the number of used elements,

  • idx is an Int vector of length n with idx[i] storing the "old" index/handle of element i before rearrangement,
  • the inverse ridx is an Int vector that stores the "new" index ridx[j] for an "old" index j.

Thus ridx[idx[i]] == i and idx[ridx[j]] == j.

precondition

ridx is a partial map, it provides valid indices inew only for previously valid iold!

If iold was not valid, it is is either out of bounds for ridx or ridx[iold] == 0.

Note

There is no explicit map for half-edges because it is implicitly defined by the edge mapping emap: for every edge index/handle e the associated half-edges are determined by

h0, h1 = halfedges(e::EHnd)

See also PMeshAttributes.

Examples

mesh2, maps = compact(mesh)
@assert iscontiguous(mesh2)
vidx, rvidx = map.vmap
fidx, rfidx = map.fmap
eidx, reidx = map.emap
PMesh.compact!Function
map = compact!(mesh[, CompactStable()])
map = compact!(mesh, CompactFast()])

Rearrange element in place such that element storage (and handle ranges) become contiguous.

The CompactStable() rearrangement moves elements forward such that their relative order is preserved.

For CompactFast(), elements are moved to unused indices from back to front. This typically requires fewer moves than stable rearrangement, but relative order is not preserved.

iscontiguous yields true immediately after calling compact!.

See also compact, iscontiguous

source
PMesh.compactMethod
newmesh, map = compact(mesh)

Create a contiguous copy newmesh of mesh by stable rearrangement of elements.

Note

Use clone if you need a copy with identical handles to elements (but lacking "compact", contigiuous storage).

See also compact!, iscontiguous, clone

source