Line data Source code
1 : #
2 : # TODO: filter/clean-up todos !!!
3 : #
4 :
5 : # TODO: add_edge! (assert v1 in face && v in face -> intersection of fans)
6 : # TODO: split face
7 : # TODO: test with 2 triangles -> 1 quad -> 4 triangles
8 : # TODO: test with 2 sandwiched triangles
9 : # TODO: test with tetrahedron
10 : # TODO: interop (shared vertex table, MeshIO)
11 : # TODO: small test data sets
12 : # TODO: remove_loop! ?
13 : # TODO: remove_isolated_vertices!
14 : # TODO: compact, compact! (in-place)
15 : # TODO: clear
16 : # TODO: collapse, split_edge
17 : # TODO: boundary loops, connected components
18 : # TODO: union
19 :
20 : # TODO: (full) edges (property)
21 : # TODO: full edges imply no flags on half edges?!, new iterator, ...
22 :
23 : # TODO: split file, cleanup
24 : # TODO: micro-benchmarks (regression)
25 :
26 : # TODO: consider using sizehint! for temp arrays (common size of vectors of handles; "reuse"/"reallocate")
27 :
28 : # TODO: any trick to "bind" mesh?!
29 :
30 : # TODO:: unlink...! vs remov...! (unlink_face!) does not remove vertices
31 :
32 : # TODO:: full edges
33 :
34 : # TODO:: split file (mesh, core, addface, ...)
35 :
36 : # TODO:: degree, hasboundary, boundaryloops, components, ...
37 :
38 : # TODO:: try bind mesh (macro!?!)
39 :
40 : # TODO:: compact, compact!
41 :
42 : # TODO:: similar, copy, caching
43 :
44 : # TODO:: copy between different types
45 :
46 : # TODO:: isisolated, isboundary (implies not isolated), ismanifold (implies not isolated), isregular (implies manifold and not boundary)
47 :
48 :
49 :
50 : """
51 : n = nv(mesh)
52 :
53 : Get number of vertices in `mesh`.
54 : """
55 100 : nv(mesh::Mesh) = n_used(vattr(mesh))
56 :
57 : """
58 : n = nf(mesh)
59 :
60 : Get number of faces in `mesh`.
61 : """
62 71 : nf(mesh::Mesh) = n_used(fattr(mesh))
63 :
64 : """
65 : n = nh(mesh)
66 :
67 : Get number of half-edges in `mesh`.
68 : """
69 23 : nh(mesh::Mesh) = 2ne(mesh)
70 :
71 : """
72 : n = ne(mesh)
73 :
74 : Get number of edges in `mesh`.
75 : """
76 39 : ne(mesh::Mesh) = n_used(eattr(mesh))
77 :
78 228909 : isused(mesh::Mesh, v::VHnd) = isused(vattr(mesh), v)
79 212026 : isused(mesh::Mesh, f::FHnd) = isused(fattr(mesh), f)
80 3614661 : isused(mesh::Mesh, h::HHnd) = isused(mesh, edge(mesh, h))
81 3614664 : isused(mesh::Mesh, e::EHnd) = isused(eattr(mesh), e)
82 :
83 : """
84 : isused(mesh, v::VHnd)
85 : isused(mesh, f::FHnd)
86 : isused(mesh, h::HHnd)
87 : isused(mesh, e::EHnd)
88 :
89 : Determine if mesh element is used.
90 : """ isused
91 :
92 24 : iscontiguous(mesh::Mesh, ::Type{VHnd}) = iscontiguous(vattr(mesh))
93 21 : iscontiguous(mesh::Mesh, ::Type{FHnd}) = iscontiguous(fattr(mesh))
94 17 : iscontiguous(mesh::Mesh, ::Type{EHnd}) = iscontiguous(eattr(mesh))
95 :
96 16 : iscontiguous(mesh::Mesh) =
97 : iscontiguous(mesh, VHnd) &&
98 : iscontiguous(mesh, FHnd) &&
99 : iscontiguous(mesh, EHnd)
100 :
101 : """
102 : iscontiguous(mesh, VHnd)
103 : iscontiguous(mesh, FHnd)
104 : iscontiguous(mesh, EHnd)
105 : iscontiguous(mesh)
106 :
107 : Are elements stored contiguously (i.e., number if used elements equals
108 : their total number)? The handle type restricts query to vertices,
109 : faces, edges or all elements. (Half-edges are stored contiguously iff
110 : edges are stored contiguously.)
111 :
112 : See also [Compact Storage](@ref page_compact)
113 : """ iscontiguous
114 :
115 : """
116 : for v in vertices(mesh)
117 : ...
118 : end
119 :
120 : Generate sequence of all used vertices.
121 : """
122 121 : vertices(mesh::Mesh) = used(vattr(mesh))
123 :
124 : """
125 : for f in faces(mesh)
126 : ...
127 : end
128 :
129 : Generate sequence of all used faces.
130 : """
131 107 : faces(mesh::Mesh) = used(fattr(mesh))
132 :
133 : """
134 : for (h1, h2) in halfedges(mesh)
135 : ...
136 : end
137 :
138 : Generate sequence all *pairs* of used half-edges.
139 : """
140 12 : halfedges(mesh::Mesh) = (halfedges(e) for e in used(eattr(mesh)))
141 :
142 : """
143 : for e in edges(mesh)
144 : ...
145 : end
146 :
147 : Generate sequence of all edges.
148 : """
149 32 : edges(mesh::Mesh) = used(eattr(mesh))
150 :
151 : """
152 : [v for v in vhnds(mesh)]
153 :
154 : Generate sequence of all -- including unused -- vertex handles.
155 : """
156 0 : vhnds(mesh::Mesh) = handles(vattr(mesh))
157 :
158 : """
159 : [f for f in fhnds(mesh)]
160 :
161 : Generate sequence of all --including unused -- face handles.
162 : """
163 0 : fhnds(mesh::Mesh) = handles(fattr(mesh))
164 :
165 : """
166 : [h for h in hhnds(mesh)]
167 :
168 : Generate sequence of all --including unused -- half-edge handles.
169 : """
170 0 : hhnds(mesh::Mesh) = handles(hattr(mesh))
171 :
172 : """
173 : [e for e in ehnds(mesh)]
174 :
175 : Generate sequence of all --including unused -- edge handles.
176 : """
177 0 : ehnds(mesh::Mesh) = handles(eattr(mesh))
178 :
179 :
180 0 : Base.sizehint!(mesh::Mesh, nv::Int) = sizehint!(mesh, (nv, 2nv))
181 18 : Base.sizehint!(mesh::Mesh, nv, nf) = sizehint!(mesh, (Int(nv), Int(nf)))
182 :
183 20 : function Base.sizehint!(mesh::Mesh, n::Tuple{Int, Int})
184 20 : nv , nf = n
185 20 : sizehint!(attrs(vattr(mesh)), nv)
186 20 : sizehint!(attrs(fattr(mesh)), nf)
187 20 : sizehint!(attrs(hattr(mesh)), 6nf)
188 20 : sizehint!(attrs(eattr(mesh)), 3nf)
189 : end
190 :
191 : """
192 : sizehint!(mesh, nv[, nf=2nv])
193 :
194 : Provide a hint on the total number of vertices `nv` and `faces `nf` for
195 : preallocation of storage.
196 :
197 : !!! tip
198 : Estimate and consider expected dynamic manipulation, i.e., adding
199 : elements.
200 : """ sizehint!
201 :
202 : """
203 : shrinkdisabled!(mesh)
204 :
205 : Shrink arrary for disabled attributes to zero size.
206 : """
207 1 : function shrinkdisabled!(mesh::Mesh)
208 1 : shrinkdisabled!(attrs(vattr(mesh)))
209 1 : shrinkdisabled!(attrs(fattr(mesh)))
210 2 : shrinkdisabled!(attrs(hattr(mesh)))
211 1 : shrinkdisabled!(attrs(eattr(mesh)))
212 : end
213 :
214 : """
215 : Synonym for [`shrinkdisabled!`](@ref)
216 :
217 : !!! note
218 : In the future, fhis function may be extended to support "shrink to
219 : fit" for enabled attributes.
220 : """
221 1 : shrink!(mesh::Mesh) = shrinkdisabled!(mesh)
222 :
223 : struct ShowDetails{T}
224 : item::T
225 : end
226 :
227 : """
228 : @show details(mesh)
229 : @show mesh # prints only nv, nf
230 :
231 : Print detailed overview of `mesh` with its attributes.
232 : """
233 0 : details(mesh::Mesh) = ShowDetails{Mesh}(mesh)
234 :
235 0 : function Base.show(io::IO, data::ShowDetails{Mesh})
236 0 : mesh = data.item
237 0 : print(io, "Mesh #v=$(nv(mesh)), #f=$(nf(mesh))\n")
238 0 : print(io, "- vertices: ")
239 0 : show(io, vattr(mesh))
240 0 : print(io, "- faces: ")
241 0 : show(io, fattr(mesh))
242 0 : print(io, "- half-edges: ")
243 0 : show(io, hattr(mesh))
244 0 : print(io, "- edges: ")
245 0 : show(io, eattr(mesh))
246 : end
247 :
248 2 : function Base.show(io::IO, mesh::Mesh)
249 2 : print(io, "Mesh[#v=$(nv(mesh)), #f=$(nf(mesh))]")
250 : end
251 :
252 : """
253 : e = edge([mesh,] h::HHnd)
254 :
255 : Get edge handle from half-edge handle.
256 : """
257 3614720 : edge(::Mesh, h::HHnd) = edge(h)
258 3615386 : edge(h::HHnd) = h != NoH ? EHnd((Int(h) - 1) ÷ 2 + 1) : NoE
259 :
260 0 : halfedgeoffset(::Mesh, h::HHnd) = halfedgeoffset(h)
261 572 : halfedgeoffset(h::HHnd) = (Int(h) - 1) % 2 + 1
262 :
263 : """
264 : i = halfedgeoffset(mesh, h)
265 : i = halfedgeoffset(h)
266 :
267 : Get offset `i ∈ {1,2}` of half-edge `h` in its edge. The inverse is
268 :
269 : h = halfedge([mesh,] egde([mesh, ]h), i)
270 :
271 : which get the half-edge from [`edge`](@ref) and offset `i`.
272 :
273 : See also [`halfegde`](@ref).
274 : """
275 :
276 : """
277 : h = halfedge([mesh,] e::EHnd, i)
278 :
279 : Get first (`i==1`) or second (`i==2`) half-edge of edge `e`.
280 : """
281 322 : halfedge(::Mesh, e::EHnd, i::Int = 1) = halfedge(e, i)
282 32949 : function halfedge(e::EHnd, i::Int = 1)
283 33282 : @massert i == 1 || i == 2
284 32949 : HHnd(2(Int(e) - 1) + i)
285 : end
286 :
287 779 : halfedges(::Mesh, e::EHnd) = halfedges(e)
288 16024 : halfedges(e::EHnd) = ((halfedge(e, i) for i in 1:2)...,)
289 :
290 : """
291 : h = halfedge(mesh, v::VHnd)
292 :
293 : Get some outgoing half-edge of vertex `v`.
294 :
295 : Returns `h == NoH` if there is such half-edge. In this case `v`
296 : is an **isolated vertex**.
297 :
298 : If `v` is a **boundary vertex**, `h` is guaranteed to be a boundary
299 : half-egde, i.e., its [`opposite`](@ref) half-edge equals `NoH`.
300 :
301 : !!! note
302 : If `v` is a boundary vertex, there may exist multiple outgoing
303 : boundary half-edges. If so, `v` is not a manifold vertex.
304 :
305 : See also [`isisolated`](@ref), [`isboundary`](@ref), [`ismanifold`](@ref)
306 : """
307 169216 : function halfedge(mesh::Mesh, v::VHnd)
308 169216 : @massert isused(mesh::Mesh, v)
309 169216 : link(vattr(mesh))[v] :: HHnd
310 : end
311 :
312 : """
313 : h = halfedge(mesh, f::FHnd)
314 :
315 : Get some half-edge in the sequence of half-edges that span the face `f`.
316 :
317 : !!! note
318 : This method always returns a valid half-edge (and *never* `NoH`).
319 : """
320 211865 : function halfedge(mesh::Mesh, f::FHnd)
321 211865 : @massert isused(mesh::Mesh, f)
322 211865 : link(fattr(mesh))[f] :: HHnd
323 : end
324 :
325 68 : function halfedges(h::HHnd)
326 68 : i = (Int(h) - 1) & ~Int(1)
327 68 : HHnd(i+1), HHnd(i+2)
328 : end
329 :
330 68 : halfedges(::Mesh, h::HHnd) = halfedges(h)
331 :
332 : """
333 : h0, h1 = halfedges([mesh,] e::EHnd)
334 :
335 : Get ordered pair of half-edges `h0, h1` such that `Int(h0) + 1 == Int(h1)`.
336 :
337 : h0, h1 = halfedges([mesh,] h::HHnd)
338 :
339 : Get ordered pair of half-edges `h0, h1` such that additionally
340 : `h0 == h || h1 == h` and
341 :
342 : !!! warning "Precondition"
343 : Requires `h != NoE`!
344 : """
345 : halfedges
346 :
347 0 : isfirsthalfedge(::Mesh, h::HHnd) = isfirsthalfedge(h)
348 :
349 1 : function isfirsthalfedge(h::HHnd)
350 1 : @massert h != NoH
351 1 : (Int(h) & Int(1)) == 1
352 : end
353 :
354 : """
355 : isfirsthalfedge([mesh,] h)
356 :
357 : Helper to decide if
358 :
359 : h == edge(h, 1)
360 :
361 : or equivalently
362 :
363 : h == first(halfedges(h))
364 :
365 : !!! warning "Precondition"
366 : Requires `h != NoE`!
367 :
368 : See also [`halfedges`](@ref), [`edge`](@ref)
369 : """ isfirsthalfedge
370 :
371 : """
372 : isisolated(mesh, v)
373 :
374 : Is vertex `v` an isolated vertex, i.e., `degree(mesh, v) == 0` or
375 : equivalently `halfedge(mesh, v) == NoH`.
376 :
377 : See also [`degree`](@ref)
378 : """
379 49174 : isisolated(mesh::Mesh, v::VHnd) = halfedge(mesh, v) == NoH
380 :
381 : # TODO:: option allowisolated ??? semantics of isboundary(vtx) ?!?
382 :
383 290733 : isboundary(mesh::Mesh, h::HHnd) = (face(mesh, h) == NoF)
384 :
385 54 : isboundary(mesh::Mesh, e::EHnd) =
386 : any(isboundary(mesh, h) for h in halfedges(e))
387 :
388 36 : function isboundary(mesh::Mesh, v::VHnd)
389 : # !isisolated(mesh, v) && isboundary(link(vattr(mesh)[v]))
390 36 : h = halfedge(mesh, v)
391 36 : h != NoH && isboundary(mesh, h)
392 : end
393 :
394 0 : isboundary(mesh::Mesh, f::FHnd) =
395 : any(isboundary(mesh, h) for h in halfedges(mesh, f))
396 :
397 : """
398 : isboundary(mesh, v::VHnd)
399 : isboundary(mesh, f::FHnd)
400 : isboundary(mesh, h::HHnd)
401 : isboundary(mesh, e::EHnd)
402 :
403 : Is element a boundary element? (A face is a boundary face if any of
404 : its edges is boundary.)
405 : """ isboundary
406 :
407 : """
408 : h = boundaryhalfedge(mesh, e)
409 :
410 : If `e` is a boundary edge, return the boundary half-edge `h`, i.e.,
411 : `isboundary(mesh, h) == true`. Return `NoH` if `e` is not boundary.
412 :
413 : See also [`isboundary`](@ref)
414 : """
415 706 : function boundaryhalfedge(mesh::Mesh, e::EHnd)
416 706 : h0, h1 = halfedges(mesh, e)
417 :
418 706 : isboundary(mesh, h0) && return h0
419 702 : isboundary(mesh, h1) && return h1
420 :
421 0 : NoH
422 : end
423 :
424 : # TODO: collect helpers
425 : # _countlength is slightly faster than Base.count as of v1.8
426 204 : function _countlength(r)
427 204 : n = 0
428 213 : for _ in r
429 744 : n += 1
430 775 : end
431 204 : n
432 : end
433 :
434 195 : degree(mesh::Mesh, f::FHnd) = _countlength(halfedges(mesh, f))
435 9 : degree(mesh::Mesh, v::VHnd) = _countlength(star(mesh, v))
436 :
437 : """
438 : n = degree(mesh, f::FHnd)
439 : n = degree(mesh, v::VHnd)
440 :
441 : Get face degree, i.e., number of vertices spanning `f`, or vertex
442 : degree, i.e., number of edges incident to `v`.
443 :
444 : !!! note
445 : The vertex degree is alternatively called *valence* (e.g., in the
446 : [PMP library](http://www.pmp-library.org/)).
447 : """ degree
448 :
449 : """
450 : vs = face(mesh, f)
451 :
452 : Collect [`vertices`](@ref) spanning face `f`.
453 :
454 : !!! note
455 : This method returns the collected `Vector{VHnd}` from the *generator*
456 : `vertices(mesh, f)`.
457 :
458 : See also [`vertices`](@ref).
459 : """
460 11 : face(mesh::Mesh, f::FHnd) = collect(vertices(mesh, f))
461 :
462 : """
463 : isempty(mesh)
464 :
465 : Is mesh empty, i.e., it does not contain any vertices or edges.
466 : """
467 4 : Base.isempty(mesh::Mesh) = nv(mesh) == 0
468 :
469 : """
470 : istrianglemesh(mesh)
471 :
472 : Is the polygonal `mesh` a triangle mesh, i.e., all faces have degree 3?
473 :
474 : See also [`degree`](@ref)
475 : """
476 16 : istrianglemesh(mesh::Mesh) = all(bind(istriangle, mesh), faces(mesh))
477 : # istrianglemesh(mesh::Mesh) = all(degree(mesh, f) == 3 for f in faces(mesh))
478 :
479 : """
480 : isquadmesh(mesh)
481 :
482 : Is the polygonal `mesh` a quad mesh, i.e., all faces have degree 4?
483 :
484 : See also [`degree`](@ref)
485 : """
486 12 : isquadmesh(mesh::Mesh) = all(bind(isquad, mesh), faces(mesh))
487 : # isquadmesh(mesh::Mesh) = all(degree(mesh, f) == 4 for f in faces(mesh))
488 :
489 : # TODO:: want triangles or quads ... ismaxfacedegree(4, ...) -> all instead of maximum
490 :
491 : """
492 : n = maxfacedegree(mesh)
493 :
494 : Get maximum face degree, e.g., for `n=4` the mesh consists of
495 : triangles and quads.
496 :
497 : See also [`degree`](@ref), [`istrianglemesh`](@ref), [`isquadmesh`](@ref)
498 : """
499 0 : maxfacedegree(mesh::Mesh) = maximum(degree(mesh, f) for f in faces(mesh))
500 :
501 :
502 : """
503 : isclosed(mesh; [allowisolated=false])
504 :
505 : Is `mesh` a closed surface without boundary loops or isolated vertices?
506 : Optionally ignore isolated vertices.
507 :
508 : See also [`isboundary`](@ref), [`isisolated`](@ref)
509 : """
510 36 : isclosed(mesh::Mesh; allowisolated = false) =
511 : all(isinner(mesh, v; allowisolated) for v in vertices(mesh))
512 :
513 : """
514 : hasisolatedvertices(mesh)
515 :
516 : Does `mesh` conatin any isolated vertices?
517 :
518 : See also [`isisolated`](@ref)
519 : """
520 4 : hasisolatedvertices(mesh::Mesh) =
521 : any(isisolated(mesh, v) for v in vertices(mesh))
522 :
523 221 : vertices(mesh::Mesh, h::HHnd) = (source(mesh, h), destination(mesh, h))
524 161 : vertices(mesh::Mesh, e::EHnd) = vertices(mesh, halfedge(mesh, e))
525 :
526 : """
527 : vsource, vdestination = vertices(mesh, h::HHnd)
528 : vsource, vdestination = vertices(mesh, e::EHnd)
529 :
530 : Get vertices spanning half-edge `h` or `h=halfedge(e)` for edge `e`.
531 : """
532 :
533 1454 : function ismanifold(mesh::Mesh, v::VHnd; allowisolated::Bool = false)
534 727 : isisolated(mesh,v) && return allowisolated
535 724 : isinner(mesh, v) && return true
536 :
537 120 : count(isboundary(mesh, h) for h in star(mesh, v)) < 2
538 : end
539 :
540 34 : ismanifold(mesh::Mesh; allowisolated::Bool = false) =
541 : all(ismanifold(mesh, v; allowisolated) for v in vertices(mesh))
542 :
543 : """
544 : ismanifold(mesh, v::VHnd)
545 : ismanifold(mesh[; allowisolated=false)
546 :
547 : Is `mesh` locally manifold near vertex `v` or globally a manifold
548 : surface mesh? Optionally ignore isolated vertices.
549 :
550 : !!! note
551 : An isolated vertex is non-manifold. Meshes that contain isolated vertices
552 : are non-manifold. -- The option `allowisolated==true` ignores any
553 : manifold vertices.
554 :
555 : !!! warning
556 : These semantics differ from [PMP](http://www.pmp-library.org/)!
557 :
558 : See also [`hasisolatedvertices`](@ref)
559 : """ ismanifold
560 :
561 : # function isinner(mesh::Mesh, v::VHnd)
562 : # # !isisolated(mesh, v) && !isboundary(mesh, v)
563 : # h = halfedge(mesh, v)
564 : # (h != NoH) && !isboundary(mesh, h)
565 : # end
566 :
567 : """
568 : isinner(mesh, v::VHnd[; allowisolated=false)
569 :
570 : Is `v` an interior vertex, i.e., neither an isolated vertex nor a
571 : boundary vertex. Optionally return `true` also for isolated vertices.
572 :
573 : !!! note
574 : `isinner` implies `ismanifold` because non-manifold vertices
575 : require a boundary.
576 :
577 : See also [`isboundary`](@ref), [`isisolated`](@ref), [`ismanifold`](@ref)
578 : """
579 61838 : function isinner(mesh::Mesh, v::VHnd; allowisolated::Bool = false)
580 : # !isisolated(mesh, v) && !isboundary(mesh, v)
581 30919 : h = halfedge(mesh, v)
582 :
583 30919 : (h == NoH) && return allowisolated
584 :
585 25644 : !isboundary(mesh, h)
586 : end
|
