Concav Hull

[ranska]

Problem statement

It will be nice if sverchok have the possibility to create the "concav hull" of a group of vertices.

Expected result

For example by using the Alpha shape algorithm The node can have on input:

• vertices
• alpha And on output
• edges

Actual result

So far I have search some all ready made version in python to see if there is something that we can use, or easily port, to sverchok with a minimum of dependency. Here is what I have found so far.

on pypi using delaunay with ggal a good blog post

using knn with cython with c cpp python wrapper

Has said by @randum in blenderartists Blender have delaunay already made.

What do you think about?

[portnov]

Blender has Delaunay in 2D only. For 3D, scipy will be needed (so it is possible in sverchok-extra).

[portnov]

Adapted from your link...

"""
in vertices_in v
in alpha_in s
out vertices_out v
out edges_out s
out faces_out s
"""

from scipy.spatial import Delaunay
import numpy as np
from collections import defaultdict

from sverchok.data_structure import zip_long_repeat

def alpha_shape_3D(pos, alpha):
    """
    Compute the alpha shape (concave hull) of a set of 3D points.
    Parameters:
        pos - np.array of shape (n,3) points.
        alpha - alpha value.
    return
        outer surface vertex indices, edge indices, and triangle indices
    """

    tetra = Delaunay(pos)
    # Find radius of the circumsphere.
    # By definition, radius of the sphere fitting inside the tetrahedral needs 
    # to be smaller than alpha value
    # http://mathworld.wolfram.com/Circumsphere.html
    tetrapos = np.take(pos,tetra.vertices,axis=0)
    normsq = np.sum(tetrapos**2,axis=2)[:,:,None]
    ones = np.ones((tetrapos.shape[0],tetrapos.shape[1],1))
    a = np.linalg.det(np.concatenate((tetrapos,ones),axis=2))
    Dx = np.linalg.det(np.concatenate((normsq,tetrapos[:,:,[1,2]],ones),axis=2))
    Dy = -np.linalg.det(np.concatenate((normsq,tetrapos[:,:,[0,2]],ones),axis=2))
    Dz = np.linalg.det(np.concatenate((normsq,tetrapos[:,:,[0,1]],ones),axis=2))
    c = np.linalg.det(np.concatenate((normsq,tetrapos),axis=2))
    r = np.sqrt(Dx**2+Dy**2+Dz**2-4*a*c)/(2*np.abs(a))

    # Find tetrahedrals
    tetras = tetra.simplices[r<alpha,:]
    # triangles
    TriComb = np.array([(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)])
    Triangles = tetras[:,TriComb].reshape(-1,3)
    Triangles = np.sort(Triangles,axis=1)
    # Remove triangles that occurs twice, because they are within shapes
    TrianglesDict = defaultdict(int)
    for tri in Triangles:TrianglesDict[tuple(tri)] += 1
    Triangles=np.array([tri for tri in TrianglesDict if TrianglesDict[tri] ==1])
    #edges
    EdgeComb=np.array([(0, 1), (0, 2), (1, 2)])
    Edges=Triangles[:,EdgeComb].reshape(-1,2)
    Edges=np.sort(Edges,axis=1)
    Edges=np.unique(Edges,axis=0)

    Vertices = np.unique(Edges)
    return Vertices,Edges,Triangles

vertices_out = []
edges_out = []
faces_out = []

for vertices, alpha in zip_long_repeat(vertices_in, alpha_in):
    if isinstance(alpha, (list, tuple)):
        alpha = alpha[0]

    _, new_edges, new_faces = alpha_shape_3D(vertices, alpha)
    #print(new_vertices)
    new_vertices = vertices

    vertices_out.append(new_vertices)
    edges_out.append(new_edges.tolist())
    faces_out.append(new_faces.tolist())

[Durman]

API documentation delaunay triangulation 2d: https://docs.blender.org/api/current/mathutils.geometry.html#mathutils.geometry.delaunay_2d_cdt

And example of usage: https://github.com/nortikin/sverchok/blob/385d5c4ab1547c1f595daef3cc3f5841c5d3517f/nodes/modifier_make/delaunay_2d_cdt.py#L24-L46

But if you intend to solve the problem in 3D space then yes it will be easy to do in sverchok-extra addon as Portnov suggesting.

[ranska]

Woooo! Just go outside for a little walk and you already made it !! You're amazing. Bravo !

[ranska]

@Durman 3D version is very good for creat manifold object from cloud of vertices. 2D version can be usefull for create outlines edges of surface and then make a volum like extrusion of surface.

[zeffii]

i assume this is resolved. reopen if not :)