Line data Source code
1 : """
2 : newmesh, map = compact(mesh)
3 :
4 : Create a contiguous copy `newmesh` of `mesh` by stable rearrangement
5 : of elements.
6 :
7 : !!! note
8 : Use [`clone`](@ref) if you need a copy with identical handles to
9 : elements (but lacking "compact", contigiuous storage).
10 :
11 : See also [`compact!`](@ref), [`iscontiguous`](@ref), [`clone`](@ref)
12 : """
13 2 : function compact(mesh::Mesh{V, F, H, E}) where {V, F, H, E}
14 2 : vplan = compactplan(vattr(mesh), CompactStable())
15 2 : fplan = compactplan(fattr(mesh), CompactStable())
16 2 : eplan = compactplan(eattr(mesh), CompactStable())
17 :
18 2 : va, vidx = compactapply(vattr(mesh), vplan)
19 2 : fa, fidx = compactapply(fattr(mesh), fplan)
20 2 : ha, _ = compactapply(hattr(mesh), eplan)
21 2 : ea, eidx = compactapply(eattr(mesh), eplan)
22 :
23 2 : newmesh = Mesh{V, F, H, E}(va, fa, ha, ea)
24 :
25 4 : rvidx = iscontiguous(mesh, VHnd) ? Int[] : compactinverse(vidx)
26 3 : rfidx = iscontiguous(mesh, FHnd) ? Int[] : compactinverse(fidx)
27 3 : reidx = iscontiguous(mesh, EHnd) ? Int[] : compactinverse(eidx)
28 :
29 2 : _compactupdatevertices!(newmesh, reidx)
30 2 : _compactupdatefaces!(newmesh, reidx)
31 :
32 2 : _compactupdatehalfedges!(newmesh, rvidx, rfidx, reidx)
33 :
34 2 : newmesh, (vmap=(vidx, rvidx), fmap=(fidx, rfidx), emap=(eidx, reidx))
35 : end
36 :
37 : using PMeshAttributes: CompactStrategy
38 :
39 6 : function compact!(mesh::Mesh;
40 : strategy::CompactStrategy=CompactStable())
41 3 : iscontiguous(mesh) && return nothing
42 :
43 5 : vidx, rvidx = _compactvertices!(mesh, strategy)
44 5 : fidx, rfidx = _compactfaces!(mesh, strategy)
45 3 : eidx, reidx = _compactedges!(mesh, strategy)
46 :
47 3 : _compactupdatevertices!(mesh, reidx)
48 3 : _compactupdatefaces!(mesh, reidx)
49 :
50 3 : _compactupdatehalfedges!(mesh, rvidx, rfidx, reidx)
51 :
52 3 : (vmap=(vidx, rvidx), fmap=(fidx, rfidx), emap=(eidx, reidx))
53 : end
54 :
55 : """
56 : map = compact!(mesh[, CompactStable()])
57 : map = compact!(mesh, CompactFast()])
58 :
59 : Rearrange element in place such that element storage (and handle
60 : ranges) become contiguous.
61 :
62 : The `CompactStable()` rearrangement moves elements
63 : forward such that their relative order is preserved.
64 :
65 : For `CompactFast()`, elements are moved to unused indices from back to
66 : front. This typically requires fewer moves than stable rearrangement,
67 : but relative order is not preserved.
68 :
69 : [`iscontiguous`](@ref) yields `true` immediately after calling
70 : `compact!`.
71 :
72 : See also [`compact`](@ref), [`iscontiguous`](@ref)
73 : """ compact!
74 :
75 : const _CompactMap = Tuple{Vector{Int}, Vector{Int}}
76 :
77 3 : function _compactvertices!(mesh::Mesh, strategy::CompactStrategy) :: _CompactMap
78 3 : iscontiguous(mesh, VHnd) && return (Int[], Int[])
79 2 : _compactelts(vattr(mesh), strategy)
80 : end
81 :
82 3 : function _compactfaces!(mesh::Mesh, strategy::CompactStrategy) :: _CompactMap
83 3 : iscontiguous(mesh, FHnd) && return (Int[], Int[])
84 2 : _compactelts(fattr(mesh), strategy)
85 : end
86 :
87 3 : function _compactedges!(mesh::Mesh, strategy::CompactStrategy) :: _CompactMap
88 3 : iscontiguous(mesh, EHnd) && return (Int[], Int[])
89 :
90 2 : ma = eattr(mesh)
91 2 : plan = compactplan(ma, strategy)
92 :
93 2 : idx = compactapply!(ma, plan)
94 :
95 2 : compactapply!(hattr(mesh), plan)
96 :
97 4 : ridx = compactinverse(idx) # TODO: emax old n_total
98 :
99 2 : (idx, ridx)
100 : end
101 :
102 4 : function _compactelts(ma::ManagedAttributes, strategy::CompactStrategy) :: _CompactMap
103 4 : plan = compactplan(ma, strategy)
104 4 : idx = compactapply!(ma, plan)
105 :
106 8 : ridx = compactinverse(idx) # TODO: emax old n_total
107 :
108 4 : (idx, ridx)
109 : end
110 :
111 573 : function _compactmaphalfedge(reidx, h)
112 574 : (h != NoH) || return NoH
113 572 : isempty(reidx) && return h
114 :
115 572 : e = edge(h)
116 572 : k = halfedgeoffset(h)
117 572 : halfedge(EHnd(reidx[Int(e)]), k)
118 : end
119 :
120 5 : function _compactupdatevertices!(mesh::Mesh, reidx)
121 5 : isempty(reidx) && return
122 3 : @massert iscontiguous(mesh, VHnd)
123 :
124 3 : vlink = link(vattr(mesh))
125 :
126 3 : for i in 1:nv(mesh)
127 65 : h = vlink[VHnd(i)]
128 65 : vlink[VHnd(i)] = _compactmaphalfedge(reidx, h)
129 65 : end
130 : end
131 :
132 5 : function _compactupdatefaces!(mesh::Mesh, reidx)
133 5 : isempty(reidx) && return
134 3 : @massert iscontiguous(mesh, FHnd)
135 :
136 3 : flink = link(fattr(mesh))
137 :
138 3 : for i in 1:nf(mesh)
139 52 : h = flink[FHnd(i)]
140 52 : flink[FHnd(i)] = _compactmaphalfedge(reidx, h)
141 52 : end
142 : end
143 :
144 5 : function _compactupdatehalfedges!(mesh::Mesh, rvidx, rfidx, reidx)
145 5 : @massert iscontiguous(mesh)
146 :
147 5 : hlink = link(hattr(mesh))
148 :
149 5 : for i in 1:ne(mesh)
150 114 : e = EHnd(i)
151 114 : for h in halfedges(e)
152 228 : hl = hlink[h]
153 :
154 446 : v = isempty(rvidx) ? hl.v : VHnd(rvidx[Int(hl.v)])
155 :
156 432 : f =
157 : if hl.f == NoF || isempty(rfidx)
158 24 : hl.f
159 : else
160 432 : FHnd(rfidx[Int(hl.f)])
161 : end
162 :
163 228 : hlink[h] = HalfEdge(v,
164 : f,
165 : _compactmaphalfedge(reidx, hl.next),
166 : _compactmaphalfedge(reidx, hl.prev))
167 342 : end
168 114 : end
169 : end
170 :
171 : # The following methods implement compactapply!(...) for HHnd which
172 : # appear in pairs but use the plan from edges. Both return nothing:
173 : # the map is provided only for edges.
174 :
175 : # TODO: must change after changing PMeshAttributes (avoid dynamic dispatch in inner loop)
176 :
177 2 : function compactapply!(ma::ManagedAttributes{HHnd},
178 : plan::CompactPlanForward)
179 2 : n, idx = plan
180 2 : @assert n == length(idx)
181 :
182 4 : for (name, a) in attrdict(attrs(ma))
183 2 : isenabled(a) || continue
184 :
185 2 : b = attrs(ma, name)
186 :
187 2 : for (i, r) in enumerate(idx)
188 10 : i = 2i - 1
189 10 : r = 2r - 1
190 :
191 10 : b[HHnd(i)] = b[HHnd(r)]
192 10 : b[HHnd(i + 1)] = b[HHnd(r + 1)]
193 18 : end
194 2 : end
195 :
196 2 : resizeattr!(attrs(ma), 2n)
197 :
198 0 : nothing
199 : end
200 :
201 2 : function compactapply(ma::ManagedAttributes{HHnd},
202 : plan::CompactPlanForward)
203 2 : n, idx = plan
204 2 : @assert n == length(idx)
205 :
206 3 : manew = similar(ma)
207 3 : resizeattr!(attrs(manew), 2n)
208 :
209 4 : for (name, a) in attrdict(attrs(ma))
210 3 : isenabled(a) || continue
211 :
212 3 : b = attrs(ma, name)
213 3 : bnew = attrs(manew, name)
214 :
215 3 : for (i, r) in enumerate(idx)
216 104 : i = 2i - 1
217 104 : r = 2r - 1
218 :
219 104 : bnew[HHnd(i)] = b[HHnd(r)]
220 104 : bnew[HHnd(i + 1)] = b[HHnd(r + 1)]
221 207 : end
222 4 : end
223 :
224 2 : manew, idx
225 : end
226 :
227 0 : function compactapply!(ma::ManagedAttributes{HHnd},
228 : plan::CompactPlanBackward)
229 0 : n, moves = plan
230 :
231 0 : for (name, a) in attrdict(attrs(ma))
232 0 : isenabled(a) || continue
233 :
234 0 : b = attrs(ma, name)
235 :
236 0 : _cp(moves, b.a)
237 0 : end
238 :
239 0 : resizeattr!(attrs(ma), 2n)
240 :
241 0 : nothing
242 : end
243 :
244 0 : function _cp(moves, b::Vector{T}) where {T}
245 0 : for (i, j) in moves
246 :
247 0 : i = 2i - 1
248 0 : j = 2j - 1
249 :
250 0 : b[i] = b[j]
251 0 : b[i + 1] = b[j + 1]
252 0 : end
253 : end
|
