Line data    Source code

       1             : """
       2             :     maycollapse(mesh, h::HHnd) :: Bool
       3             : 
       4             : Determine whether half-edge `h` can be collapsed, i.e., its source
       5             : vertex is "moved into" its destination vertex.
       6             : 
       7             : !!! warning "Precondition"
       8             :     This method **requires a triangle mesh**!
       9             : 
      10             : See also [`collapse!`](@ref)
      11             : """ maycollapse
      12             : 
      13          14 : function maycollapse(mesh::Mesh, h::HHnd)
      14          14 :     @massert isused(mesh, h)
      15             : 
      16          14 :     v0v1 = h
      17          14 :     v1v0 = opposite(mesh, h)
      18             : 
      19             :     # the edges v1-vl and vl-v0 must not be both boundary edges,
      20             :     # the edges v0-vr and vr-v1 must not be both boundary edges
      21             : 
      22          14 :     success, vl = _maycollpase_check_boundary(mesh, v0v1)
      23          19 :     success || return false
      24             : 
      25           9 :     success, vr = _maycollpase_check_boundary(mesh, v1v0)
      26          12 :     success || return false
      27             : 
      28           6 :     (vl != vr) || return false # equal and used or both NoV
      29             : 
      30           6 :     v0 = destination(mesh, v1v0)
      31           6 :     v1 = destination(mesh, v0v1)
      32             : 
      33             :     # edge between two boundary vertices should be a boundary edge
      34           6 :     isboundary(mesh, v0) && isboundary(mesh, v1) &&
      35             :         !isboundary(mesh, v0v1) && !isboundary(mesh, v1v0) && return false
      36             : 
      37             :     # test intersection of the one-rings of v0 and v1
      38          12 :     for v in ring(mesh, v0)
      39          21 :         if (v != v1) && (v != vl) && (v != vr)
      40           7 :             (halfedge(mesh, v, v1) == NoH) || return false
      41             :         end
      42          21 :     end
      43             : 
      44           0 :     true
      45             : end
      46             : 
      47          23 : function _maycollpase_check_boundary(mesh::Mesh, h::HHnd)
      48          23 :     isboundary(mesh, h) && return (true, NoV)
      49             : 
      50          18 :     h1 = next(mesh, h)
      51          18 :     h2 = next(mesh, h1)
      52          18 :     @massert next(mesh, h2) == h "require triangulation"
      53             : 
      54          18 :     isboundary(mesh, opposite(mesh, h1)) &&
      55             :         isboundary(mesh, opposite(mesh, h2)) && return (false, NoV)
      56             : 
      57          10 :     (true, destination(mesh, h1))
      58             : end
      59             : 
      60             : """
      61             :     collapse!(mesh, h::HHnd)
      62             : 
      63             : Apply half-edge collapse such that the [`source`](@ref) vertex of `h`
      64             : is "collapsed into" the [`destination`](@ref) vertex. This way, the
      65             : source vertex and one (`h` [`isboundary`](@ref)) or two triangles
      66             : incident to `h` and associated edges are removed from `mesh` (i.e,
      67             : [`isused`](@ref) yields `false`).
      68             : 
      69             : !!! warning "Precondition"
      70             :     This method **requires a triangle mesh**!
      71             : 
      72             : !!! warning "Precondition"
      73             :     Requires `maycollapse(mesh, h) == true` immediately before
      74             :     `collapse!(mesh, h)`!
      75             : 
      76             : See also [`maycollapse`](@ref)
      77             : 
      78             : """
      79           3 : function collapse!(mesh::Mesh, h::HHnd)
      80           3 :     @massert isused(mesh, h)
      81             : 
      82           3 :     h0 = h
      83           3 :     h1 = prev(mesh, h0)
      84           3 :     o0 = opposite(mesh, h0)
      85           3 :     o1 = next(mesh, o0)
      86             : 
      87           3 :     _collapse_remove_edge(mesh, h0)
      88             : 
      89           6 :     (next(mesh, next(mesh, h1)) != h1) || _collapse_remove_loop(mesh, h1)
      90           3 :     (next(mesh, next(mesh, o1)) != o1) || _collapse_remove_loop(mesh, o1)
      91             : end
      92             : 
      93           3 : function _collapse_remove_edge(mesh::Mesh, h::HHnd)
      94           3 :     @massert isused(mesh, h)
      95             : 
      96           3 :     hn = next(mesh, h)
      97           3 :     hp = prev(mesh, h)
      98             : 
      99           3 :     o = opposite(mesh, h)
     100           3 :     on = next(mesh, o)
     101           3 :     op = prev(mesh, o)
     102             : 
     103           3 :     fh = face(mesh, h)
     104           3 :     fo = face(mesh, o)
     105             : 
     106           3 :     vh = destination(mesh, h)
     107           3 :     vo = destination(mesh, o)
     108             : 
     109             :     # half-edge -> vertex
     110           6 :     for hc in star(mesh, vo)
     111          12 :         _setvertex!(mesh, opposite(mesh, hc), vh)
     112          21 :     end
     113             : 
     114             :     # half-edge -> half-edge
     115           3 :     _setnexthalfedge!(mesh, hp, hn)
     116           3 :     _setnexthalfedge!(mesh, op, on)
     117             : 
     118             :     # face -> half-edge
     119           6 :     (fh == NoF) || _sethalfedge!(mesh, fh, hn)
     120           5 :     (fo == NoF) || _sethalfedge!(mesh, fo, on)
     121             : 
     122             :     # vertex -> half-edge
     123           4 :     (halfedge(mesh, vh) != o) || _sethalfedge!(mesh, vh, hn)
     124           3 :     _adjustoutgoinghalfedge!(mesh, vh)
     125           3 :     _sethalfedge!(mesh, vo, NoH)
     126             : 
     127           3 :     _setunused!(mesh, vo)
     128           3 :     _setunused!(mesh, edge(mesh, h))
     129             : end
     130             : 
     131           5 : function _collapse_remove_loop(mesh::Mesh, h::HHnd)
     132           5 :     @massert isused(mesh, h)
     133             : 
     134           5 :     h0 = h
     135           5 :     h1 = next(mesh, h0)
     136             : 
     137           5 :     o0 = opposite(mesh, h0)
     138           5 :     o1 = opposite(mesh, h1)
     139             : 
     140           5 :     v0 = destination(mesh, h0)
     141           5 :     v1 = destination(mesh, h1)
     142             : 
     143           5 :     fh = face(mesh, h0)
     144           5 :     fo = face(mesh, o0)
     145             : 
     146           5 :     @massert (next(mesh, h1) == h0) && (h1!= h0) "loop"
     147             : 
     148             :     # half-edge -> half-edge
     149           5 :     _setnexthalfedge!(mesh, h1, next(mesh, o0))
     150           5 :     _setnexthalfedge!(mesh, prev(mesh, o0), h1)
     151             : 
     152             :     # half-edge -> face
     153           5 :     _setface!(mesh, h1, fo)
     154             : 
     155             :     # vertex -> half-edge
     156           5 :     _sethalfedge!(mesh, v0, h1)
     157           5 :     _adjustoutgoinghalfedge!(mesh, v0)
     158           5 :     _sethalfedge!(mesh, v1, o1)
     159           5 :     _adjustoutgoinghalfedge!(mesh, v1)
     160             : 
     161             :     # face -> half-edge
     162           5 :     (fo != NoF) && (halfedge(mesh, fo) == o0) && _sethalfedge!(mesh, fo, h1)
     163             : 
     164           5 :     (fh != NoF) && _setunused!(mesh, fh)
     165           5 :     _setunused!(mesh, edge(mesh, h))
     166             : end