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.
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 anInt
vector of lengthn
withidx[i]
storing the "old" index/handle of elementi
before rearrangement,- the inverse
ridx
is anInt
vector that stores the "new" indexridx[j]
for an "old" indexj
.
Thus ridx[idx[i]] == i
and idx[ridx[j]] == j
.
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
.
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!
— Functionmap = 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
PMesh.compact
— Methodnewmesh, map = compact(mesh)
Create a contiguous copy newmesh
of mesh
by stable rearrangement of elements.
Use clone
if you need a copy with identical handles to elements (but lacking "compact", contigiuous storage).
See also compact!
, iscontiguous
, clone