utils/surfaces.py

import numpy as np
import scipy as sp
import scipy.linalg as spLA
import scipy.sparse.linalg as sla
import os
import logging
import copy
import potpourri3d as pp3d
from sklearn.cluster import KMeans#, DBSCAN, SpectralClustering
from scipy.spatial import cKDTree
import trimesh as tm


try:
    from vtk import *
    import vtk.util.numpy_support as v2n

    gotVTK = True
except ImportError:
    print('could not import VTK functions')
    gotVTK = False

eps = 1e-8
# import kernelFunctions as kfun

class vtkFields:
    def __init__(self):
        self.scalars = []
        self.vectors = []
        self.normals = []
        self.tensors = []


# General surface class, fibers possible. The fiber is a vector field of norm 1, defined on each vertex.
# It must be an array of the same size (number of vertices)x3.

class Surface:

    # Fibers: a list of vectors, with i-th element corresponding to the value of the vector field at vertex i
    # Contains as object:
    # vertices : all the vertices
    # centers: the centers of each face
    # faces: faces along with the id of the faces
    # surfel: surface element of each face (area*normal)
    # List of methods:
    # read : from filename type, call readFILENAME and set all surface attributes
    # updateVertices: update the whole surface after a modification of the vertices
    # computeVertexArea and Normals
    # getEdges
    # LocalSignedDistance distance function in the neighborhood of a shape
    # toPolyData: convert the surface to a polydata vtk object
    # fromPolyDate: guess what
    # Simplify : simplify the meshes
    # flipfaces: invert the indices of faces from [a, b, c] to [a, c, b]
    # smooth: get a smoother surface
    # Isosurface: compute isosurface
    # edgeRecove: ensure that orientation is correct
    # remove isolated: if isolated vertice, remove it
    # laplacianMatrix: compute Laplacian Matrix of the surface graph
    # graphLaplacianMatrix: ???
    # laplacianSegmentation: segment the surface using laplacian properties
    # surfVolume: compute volume inscribed in the surface (+ inscribed infinitesimal volume for each face)
    # surfCenter: compute surface Center
    # surfMoments: compute surface second order moments
    # surfU: compute the informations for surface rigid alignement
    # surfEllipsoid: compute ellipsoid representing the surface
    # savebyu of vitk or vtk2: save the surface in a file
    # concatenate: concatenate to another surface

    def __init__(self, surf=None, filename=None, FV=None):
        if surf == None:
            if FV == None:
                if filename == None:
                    self.vertices = np.empty(0)
                    self.centers = np.empty(0)
                    self.faces = np.empty(0)
                    self.surfel = np.empty(0)
                else:
                    if type(filename) is list:
                        fvl = []
                        for name in filename:
                            fvl.append(Surface(filename=name))
                        self.concatenate(fvl)
                    else:
                        self.read(filename)
            else:
                self.vertices = np.copy(FV[1])
                self.faces = np.int_(FV[0])
                self.computeCentersAreas()

        else:
            self.vertices = np.copy(surf.vertices)
            self.faces = np.copy(surf.faces)
            self.surfel = np.copy(surf.surfel)
            self.centers = np.copy(surf.centers)
            self.computeCentersAreas()
        self.volume, self.vols = self.surfVolume()
        self.center = self.surfCenter()
        self.cotanLaplacian()

    def read(self, filename):
        (mainPart, ext) = os.path.splitext(filename)
        if ext == '.byu':
            self.readbyu(filename)
        elif ext == '.off':
            self.readOFF(filename)
        elif ext == '.vtk':
            self.readVTK(filename)
        elif ext == '.obj':
            self.readOBJ(filename)
        elif ext == '.ply':
            self.readPLY(filename)
        elif ext == '.tri' or ext == ".ntri":
            self.readTRI(filename)
        else:
            print('Unknown Surface Extension:', ext)
            self.vertices = np.empty(0)
            self.centers = np.empty(0)
            self.faces = np.empty(0)
            self.surfel = np.empty(0)

    # face centers and area weighted normal
    def computeCentersAreas(self):
        xDef1 = self.vertices[self.faces[:, 0], :]
        xDef2 = self.vertices[self.faces[:, 1], :]
        xDef3 = self.vertices[self.faces[:, 2], :]
        self.centers = (xDef1 + xDef2 + xDef3) / 3
        self.surfel = np.cross(xDef2 - xDef1, xDef3 - xDef1)

    # modify vertices without toplogical change
    def updateVertices(self, x0):
        self.vertices = np.copy(x0)
        xDef1 = self.vertices[self.faces[:, 0], :]
        xDef2 = self.vertices[self.faces[:, 1], :]
        xDef3 = self.vertices[self.faces[:, 2], :]
        self.centers = (xDef1 + xDef2 + xDef3) / 3
        self.surfel = np.cross(xDef2 - xDef1, xDef3 - xDef1)
        self.volume, self.vols = self.surfVolume()

    def computeVertexArea(self):
        # compute areas of faces and vertices
        V = self.vertices
        F = self.faces
        nv = V.shape[0]
        nf = F.shape[0]
        AF = np.zeros([nf, 1])
        AV = np.zeros([nv, 1])
        for k in range(nf):
            # determining if face is obtuse
            x12 = V[F[k, 1], :] - V[F[k, 0], :]
            x13 = V[F[k, 2], :] - V[F[k, 0], :]
            n12 = np.sqrt((x12 ** 2).sum())
            n13 = np.sqrt((x13 ** 2).sum())
            c1 = (x12 * x13).sum() / (n12 * n13)
            x23 = V[F[k, 2], :] - V[F[k, 1], :]
            n23 = np.sqrt((x23 ** 2).sum())
            # n23 = norm(x23) ;
            c2 = -(x12 * x23).sum() / (n12 * n23)
            c3 = (x13 * x23).sum() / (n13 * n23)
            AF[k] = np.sqrt((np.cross(x12, x13) ** 2).sum()) / 2
            if (c1 < 0):
                # face obtuse at vertex 1
                AV[F[k, 0]] += AF[k] / 2
                AV[F[k, 1]] += AF[k] / 4
                AV[F[k, 2]] += AF[k] / 4
            elif (c2 < 0):
                # face obuse at vertex 2
                AV[F[k, 0]] += AF[k] / 4
                AV[F[k, 1]] += AF[k] / 2
                AV[F[k, 2]] += AF[k] / 4
            elif (c3 < 0):
                # face obtuse at vertex 3
                AV[F[k, 0]] += AF[k] / 4
                AV[F[k, 1]] += AF[k] / 4
                AV[F[k, 2]] += AF[k] / 2
            else:
                # non obtuse face
                cot1 = c1 / np.sqrt(1 - c1 ** 2)
                cot2 = c2 / np.sqrt(1 - c2 ** 2)
                cot3 = c3 / np.sqrt(1 - c3 ** 2)
                AV[F[k, 0]] += ((x12 ** 2).sum() * cot3 + (x13 ** 2).sum() * cot2) / 8
                AV[F[k, 1]] += ((x12 ** 2).sum() * cot3 + (x23 ** 2).sum() * cot1) / 8
                AV[F[k, 2]] += ((x13 ** 2).sum() * cot2 + (x23 ** 2).sum() * cot1) / 8

        for k in range(nv):
            if (np.fabs(AV[k]) < 1e-10):
                print('Warning: vertex ', k, 'has no face; use removeIsolated')
        # print('sum check area:', AF.sum(), AV.sum()
        return AV, AF

    def computeVertexNormals(self):
        self.computeCentersAreas()
        normals = np.zeros(self.vertices.shape)
        F = self.faces
        for k in range(F.shape[0]):
            normals[F[k, 0]] += self.surfel[k]
            normals[F[k, 1]] += self.surfel[k]
            normals[F[k, 2]] += self.surfel[k]
        af = np.sqrt((normals ** 2).sum(axis=1))
        # logging.info('min area = %.4f'%(af.min()))
        normals /= (af.reshape([self.vertices.shape[0], 1]) + eps)

        return normals

    # Computes edges from vertices/faces
    def getEdges(self):
        self.edges = []

        for k in range(self.faces.shape[0]):
            for kj in (0, 1, 2):
                u = [self.faces[k, kj], self.faces[k, (kj + 1) % 3]]

                if (u not in self.edges) & (u.reverse() not in self.edges):
                    self.edges.append(u)

        self.edgeFaces = []

        for u in self.edges:
            self.edgeFaces.append([])

        for k in range(self.faces.shape[0]):
            for kj in (0, 1, 2):
                u = [self.faces[k, kj], self.faces[k, (kj + 1) % 3]]

                if u in self.edges:
                    kk = self.edges.index(u)
                else:
                    u.reverse()
                    kk = self.edges.index(u)

                self.edgeFaces[kk].append(k)

        self.edges = np.int_(np.array(self.edges))
        self.bdry = np.int_(np.zeros(self.edges.shape[0]))

        for k in range(self.edges.shape[0]):
            if len(self.edgeFaces[k]) < 2:
                self.bdry[k] = 1

    # computes the signed distance function in a small neighborhood of a shape
    def LocalSignedDistance(self, data, value):
        d2 = 2 * np.array(data >= value) - 1
        c2 = np.cumsum(d2, axis=0)
        for j in range(2):
            c2 = np.cumsum(c2, axis=j + 1)
        (n0, n1, n2) = c2.shape

        rad = 3
        diam = 2 * rad + 1
        (x, y, z) = np.mgrid[-rad:rad + 1, -rad:rad + 1, -rad:rad + 1]
        cube = (x ** 2 + y ** 2 + z ** 2)
        maxval = (diam) ** 3
        s = 3.0 * rad ** 2
        res = d2 * s
        u = maxval * np.ones(c2.shape)
        u[rad + 1:n0 - rad, rad + 1:n1 - rad, rad + 1:n2 - rad] = (c2[diam:n0, diam:n1, diam:n2]
                                                                   - c2[0:n0 - diam, diam:n1, diam:n2] - c2[diam:n0,
                                                                                                         0:n1 - diam,
                                                                                                         diam:n2] - c2[
                                                                                                                    diam:n0,
                                                                                                                    diam:n1,
                                                                                                                    0:n2 - diam]
                                                                   + c2[0:n0 - diam, 0:n1 - diam, diam:n2] + c2[diam:n0,
                                                                                                             0:n1 - diam,
                                                                                                             0:n2 - diam] + c2[
                                                                                                                            0:n0 - diam,
                                                                                                                            diam:n1,
                                                                                                                            0:n2 - diam]
                                                                   - c2[0:n0 - diam, 0:n1 - diam, 0:n2 - diam])

        I = np.nonzero(np.fabs(u) < maxval)
        # print(len(I[0]))

        for k in range(len(I[0])):
            p = np.array((I[0][k], I[1][k], I[2][k]))
            bmin = p - rad
            bmax = p + rad + 1
            # print(p, bmin, bmax)
            if (d2[p[0], p[1], p[2]] > 0):
                # print(u[p[0],p[1], p[2]])
                # print(d2[bmin[0]:bmax[0], bmin[1]:bmax[1], bmin[2]:bmax[2]].sum())
                res[p[0], p[1], p[2]] = min(
                    cube[np.nonzero(d2[bmin[0]:bmax[0], bmin[1]:bmax[1], bmin[2]:bmax[2]] < 0)]) - .25
            else:
                res[p[0], p[1], p[2]] = - min(
                    cube[np.nonzero(d2[bmin[0]:bmax[0], bmin[1]:bmax[1], bmin[2]:bmax[2]] > 0)]) - .25

        return res

    def toPolyData(self):
        if gotVTK:
            points = vtkPoints()
            for k in range(self.vertices.shape[0]):
                points.InsertNextPoint(self.vertices[k, 0], self.vertices[k, 1], self.vertices[k, 2])
            polys = vtkCellArray()
            for k in range(self.faces.shape[0]):
                polys.InsertNextCell(3)
                for kk in range(3):
                    polys.InsertCellPoint(self.faces[k, kk])
            polydata = vtkPolyData()
            polydata.SetPoints(points)
            polydata.SetPolys(polys)
            return polydata
        else:
            raise Exception('Cannot run toPolyData without VTK')

    def fromPolyData(self, g, scales=[1., 1., 1.]):
        npoints = int(g.GetNumberOfPoints())
        nfaces = int(g.GetNumberOfPolys())
        logging.info('Dimensions: %d %d %d' % (npoints, nfaces, g.GetNumberOfCells()))
        V = np.zeros([npoints, 3])
        for kk in range(npoints):
            V[kk, :] = np.array(g.GetPoint(kk))
            # print(kk, V[kk])
            # print(kk, np.array(g.GetPoint(kk)))
        F = np.zeros([nfaces, 3])
        gf = 0
        for kk in range(g.GetNumberOfCells()):
            c = g.GetCell(kk)
            if (c.GetNumberOfPoints() == 3):
                for ll in range(3):
                    F[gf, ll] = c.GetPointId(ll)
                    # print(kk, gf, F[gf])
                gf += 1

                # self.vertices = np.multiply(data.shape-V-1, scales)
        self.vertices = np.multiply(V, scales)
        self.faces = np.int_(F[0:gf, :])
        self.computeCentersAreas()

    def Simplify(self, target=1000.0):
        if gotVTK:
            polydata = self.toPolyData()
            dc = vtkQuadricDecimation()
            red = 1 - min(np.float(target) / polydata.GetNumberOfPoints(), 1)
            dc.SetTargetReduction(red)
            dc.SetInput(polydata)
            dc.Update()
            g = dc.GetOutput()
            self.fromPolyData(g)
            z = self.surfVolume()
            if (z > 0):
                self.flipFaces()
                print('flipping volume', z, self.surfVolume())
        else:
            raise Exception('Cannot run Simplify without VTK')

    def flipFaces(self):
        self.faces = self.faces[:, [0, 2, 1]]
        self.computeCentersAreas()

    def smooth(self, n=30, smooth=0.1):
        if gotVTK:
            g = self.toPolyData()
            print(g)
            smoother = vtkWindowedSincPolyDataFilter()
            smoother.SetInput(g)
            smoother.SetNumberOfIterations(n)
            smoother.SetPassBand(smooth)
            smoother.NonManifoldSmoothingOn()
            smoother.NormalizeCoordinatesOn()
            smoother.GenerateErrorScalarsOn()
            # smoother.GenerateErrorVectorsOn()
            smoother.Update()
            g = smoother.GetOutput()
            self.fromPolyData(g)
        else:
            raise Exception('Cannot run smooth without VTK')

    # Computes isosurfaces using vtk
    def Isosurface(self, data, value=0.5, target=1000.0, scales=[1., 1., 1.], smooth=0.1, fill_holes=1.):
        if gotVTK:
            # data = self.LocalSignedDistance(data0, value)
            if isinstance(data, vtkImageData):
                img = data
            else:
                img = vtkImageData()
                img.SetDimensions(data.shape)
                img.SetOrigin(0, 0, 0)
                if vtkVersion.GetVTKMajorVersion() >= 6:
                    img.AllocateScalars(VTK_FLOAT, 1)
                else:
                    img.SetNumberOfScalarComponents(1)
                v = vtkDoubleArray()
                v.SetNumberOfValues(data.size)
                v.SetNumberOfComponents(1)
                for ii, tmp in enumerate(np.ravel(data, order='F')):
                    v.SetValue(ii, tmp)
                    img.GetPointData().SetScalars(v)

            cf = vtkContourFilter()
            if vtkVersion.GetVTKMajorVersion() >= 6:
                cf.SetInputData(img)
            else:
                cf.SetInput(img)
            cf.SetValue(0, value)
            cf.SetNumberOfContours(1)
            cf.Update()
            # print(cf
            connectivity = vtkPolyDataConnectivityFilter()
            connectivity.ScalarConnectivityOff()
            connectivity.SetExtractionModeToLargestRegion()
            if vtkVersion.GetVTKMajorVersion() >= 6:
                connectivity.SetInputData(cf.GetOutput())
            else:
                connectivity.SetInput(cf.GetOutput())
            connectivity.Update()
            g = connectivity.GetOutput()

            if smooth > 0:
                smoother = vtkWindowedSincPolyDataFilter()
                if vtkVersion.GetVTKMajorVersion() >= 6:
                    smoother.SetInputData(g)
                else:
                    smoother.SetInput(g)
                #     else:
                # smoother.SetInputConnection(contour.GetOutputPort())
                smoother.SetNumberOfIterations(30)
                # this has little effect on the error!
                # smoother.BoundarySmoothingOff()
                # smoother.FeatureEdgeSmoothingOff()
                # smoother.SetFeatureAngle(120.0)
                smoother.SetPassBand(smooth)  # this increases the error a lot!
                smoother.NonManifoldSmoothingOn()
                # smoother.NormalizeCoordinatesOn()
                # smoother.GenerateErrorScalarsOn()
                # smoother.GenerateErrorVectorsOn()
                smoother.Update()
                g = smoother.GetOutput()

            # dc = vtkDecimatePro()
            red = 1 - min(np.float(target) / g.GetNumberOfPoints(), 1)
            # print('Reduction: ', red)
            dc = vtkQuadricDecimation()
            dc.SetTargetReduction(red)
            # dc.AttributeErrorMetricOn()
            # dc.SetDegree(10)
            # dc.SetSplitting(0)
            if vtkVersion.GetVTKMajorVersion() >= 6:
                dc.SetInputData(g)
            else:
                dc.SetInput(g)
                # dc.SetInput(g)
            # print(dc)
            dc.Update()
            g = dc.GetOutput()
            # print('points:', g.GetNumberOfPoints())
            cp = vtkCleanPolyData()
            if vtkVersion.GetVTKMajorVersion() >= 6:
                cp.SetInputData(dc.GetOutput())
            else:
                cp.SetInput(dc.GetOutput())
                #        cp.SetInput(dc.GetOutput())
            # cp.SetPointMerging(1)
            cp.ConvertPolysToLinesOn()
            cp.SetAbsoluteTolerance(1e-5)
            cp.Update()
            g = cp.GetOutput()
            self.fromPolyData(g, scales)
            z = self.surfVolume()
            if (z > 0):
                self.flipFaces()
                # print('flipping volume', z, self.surfVolume())
                logging.info('flipping volume %.2f %.2f' % (z, self.surfVolume()))

            # print(g)
            # npoints = int(g.GetNumberOfPoints())
            # nfaces = int(g.GetNumberOfPolys())
            # print('Dimensions:', npoints, nfaces, g.GetNumberOfCells())
            # V = np.zeros([npoints, 3])
            # for kk in range(npoints):
            #     V[kk, :] = np.array(g.GetPoint(kk))
            #     #print(kk, V[kk])
            #     #print(kk, np.array(g.GetPoint(kk)))
            # F = np.zeros([nfaces, 3])
            # gf = 0
            # for kk in range(g.GetNumberOfCells()):
            #     c = g.GetCell(kk)
            #     if(c.GetNumberOfPoints() == 3):
            #         for ll in range(3):
            #             F[gf,ll] = c.GetPointId(ll)
            #             #print(kk, gf, F[gf])
            #         gf += 1

            #         #self.vertices = np.multiply(data.shape-V-1, scales)
            # self.vertices = np.multiply(V, scales)
            # self.faces = np.int_(F[0:gf, :])
            # self.computeCentersAreas()
        else:
            raise Exception('Cannot run Isosurface without VTK')

    # Ensures that orientation is correct
    def edgeRecover(self):
        v = self.vertices
        f = self.faces
        nv = v.shape[0]
        nf = f.shape[0]
        # faces containing each oriented edge
        edg0 = np.int_(np.zeros((nv, nv)))
        # number of edges between each vertex
        edg = np.int_(np.zeros((nv, nv)))
        # contiguous faces
        edgF = np.int_(np.zeros((nf, nf)))
        for (kf, c) in enumerate(f):
            if (edg0[c[0], c[1]] > 0):
                edg0[c[1], c[0]] = kf + 1
            else:
                edg0[c[0], c[1]] = kf + 1

            if (edg0[c[1], c[2]] > 0):
                edg0[c[2], c[1]] = kf + 1
            else:
                edg0[c[1], c[2]] = kf + 1

            if (edg0[c[2], c[0]] > 0):
                edg0[c[0], c[2]] = kf + 1
            else:
                edg0[c[2], c[0]] = kf + 1

            edg[c[0], c[1]] += 1
            edg[c[1], c[2]] += 1
            edg[c[2], c[0]] += 1

        for kv in range(nv):
            I2 = np.nonzero(edg0[kv, :])
            for kkv in I2[0].tolist():
                edgF[edg0[kkv, kv] - 1, edg0[kv, kkv] - 1] = kv + 1

        isOriented = np.int_(np.zeros(f.shape[0]))
        isActive = np.int_(np.zeros(f.shape[0]))
        I = np.nonzero(np.squeeze(edgF[0, :]))
        # list of faces to be oriented
        activeList = [0] + I[0].tolist()
        lastOriented = 0
        isOriented[0] = True
        for k in activeList:
            isActive[k] = True

        while lastOriented < len(activeList) - 1:
            i = activeList[lastOriented]
            j = activeList[lastOriented + 1]
            I = np.nonzero(edgF[j, :])
            foundOne = False
            for kk in I[0].tolist():
                if (foundOne == False) & (isOriented[kk]):
                    foundOne = True
                    u1 = edgF[j, kk] - 1
                    u2 = edgF[kk, j] - 1
                    if not ((edg[u1, u2] == 1) & (edg[u2, u1] == 1)):
                        # reorient face j
                        edg[f[j, 0], f[j, 1]] -= 1
                        edg[f[j, 1], f[j, 2]] -= 1
                        edg[f[j, 2], f[j, 0]] -= 1
                        a = f[j, 1]
                        f[j, 1] = f[j, 2]
                        f[j, 2] = a
                        edg[f[j, 0], f[j, 1]] += 1
                        edg[f[j, 1], f[j, 2]] += 1
                        edg[f[j, 2], f[j, 0]] += 1
                elif (not isActive[kk]):
                    activeList.append(kk)
                    isActive[kk] = True
            if foundOne:
                lastOriented = lastOriented + 1
                isOriented[j] = True
                # print('oriented face', j, lastOriented,  'out of',  nf,  ';  total active', len(activeList))
            else:
                print('Unable to orient face', j)
                return
        self.vertices = v;
        self.faces = f;

        z, _ = self.surfVolume()
        if (z > 0):
            self.flipFaces()

    def removeIsolated(self):
        N = self.vertices.shape[0]
        inFace = np.int_(np.zeros(N))
        for k in range(3):
            inFace[self.faces[:, k]] = 1
        J = np.nonzero(inFace)
        self.vertices = self.vertices[J[0], :]
        logging.info('Found %d isolated vertices' % (J[0].shape[0]))
        Q = -np.ones(N)
        for k, j in enumerate(J[0]):
            Q[j] = k
        self.faces = np.int_(Q[self.faces])

    def laplacianMatrix(self):
        F = self.faces
        V = self.vertices;
        nf = F.shape[0]
        nv = V.shape[0]

        AV, AF = self.computeVertexArea()

        # compute edges and detect boundary
        # edm = sp.lil_matrix((nv,nv))
        edm = -np.ones([nv, nv]).astype(np.int32)
        E = np.zeros([3 * nf, 2]).astype(np.int32)
        j = 0
        for k in range(nf):
            if (edm[F[k, 0], F[k, 1]] == -1):
                edm[F[k, 0], F[k, 1]] = j
                edm[F[k, 1], F[k, 0]] = j
                E[j, :] = [F[k, 0], F[k, 1]]
                j = j + 1
            if (edm[F[k, 1], F[k, 2]] == -1):
                edm[F[k, 1], F[k, 2]] = j
                edm[F[k, 2], F[k, 1]] = j
                E[j, :] = [F[k, 1], F[k, 2]]
                j = j + 1
            if (edm[F[k, 0], F[k, 2]] == -1):
                edm[F[k, 2], F[k, 0]] = j
                edm[F[k, 0], F[k, 2]] = j
                E[j, :] = [F[k, 2], F[k, 0]]
                j = j + 1
        E = E[0:j, :]

        edgeFace = np.zeros([j, nf])
        ne = j
        # print(E)
        for k in range(nf):
            edgeFace[edm[F[k, 0], F[k, 1]], k] = 1
            edgeFace[edm[F[k, 1], F[k, 2]], k] = 1
            edgeFace[edm[F[k, 2], F[k, 0]], k] = 1

        bEdge = np.zeros([ne, 1])
        bVert = np.zeros([nv, 1])
        edgeAngles = np.zeros([ne, 2])
        for k in range(ne):
            I = np.flatnonzero(edgeFace[k, :])
            # print('I=', I, F[I, :], E.shape)
            # print('E[k, :]=', k, E[k, :])
            # print(k, edgeFace[k, :])
            for u in range(len(I)):
                f = I[u]
                i1l = np.flatnonzero(F[f, :] == E[k, 0])
                i2l = np.flatnonzero(F[f, :] == E[k, 1])
                # print(f, F[f, :])
                # print(i1l, i2l)
                i1 = i1l[0]
                i2 = i2l[0]
                s = i1 + i2
                if s == 1:
                    i3 = 2
                elif s == 2:
                    i3 = 1
                elif s == 3:
                    i3 = 0
                x1 = V[F[f, i1], :] - V[F[f, i3], :]
                x2 = V[F[f, i2], :] - V[F[f, i3], :]
                a = (np.cross(x1, x2) * np.cross(V[F[f, 1], :] - V[F[f, 0], :], V[F[f, 2], :] - V[F[f, 0], :])).sum()
                b = (x1 * x2).sum()
                if (a > 0):
                    edgeAngles[k, u] = b / np.sqrt(a)
                else:
                    edgeAngles[k, u] = b / np.sqrt(-a)
            if (len(I) == 1):
                # boundary edge
                bEdge[k] = 1
                bVert[E[k, 0]] = 1
                bVert[E[k, 1]] = 1
                edgeAngles[k, 1] = 0

                # Compute Laplacian matrix
        L = np.zeros([nv, nv])

        for k in range(ne):
            L[E[k, 0], E[k, 1]] = (edgeAngles[k, 0] + edgeAngles[k, 1]) / 2
            L[E[k, 1], E[k, 0]] = L[E[k, 0], E[k, 1]]

        for k in range(nv):
            L[k, k] = - L[k, :].sum()

        A = np.zeros([nv, nv])
        for k in range(nv):
            A[k, k] = AV[k]

        return L, A

    def graphLaplacianMatrix(self):
        F = self.faces
        V = self.vertices
        nf = F.shape[0]
        nv = V.shape[0]

        # compute edges and detect boundary
        # edm = sp.lil_matrix((nv,nv))
        edm = -np.ones([nv, nv])
        E = np.zeros([3 * nf, 2])
        j = 0
        for k in range(nf):
            if (edm[F[k, 0], F[k, 1]] == -1):
                edm[F[k, 0], F[k, 1]] = j
                edm[F[k, 1], F[k, 0]] = j
                E[j, :] = [F[k, 0], F[k, 1]]
                j = j + 1
            if (edm[F[k, 1], F[k, 2]] == -1):
                edm[F[k, 1], F[k, 2]] = j
                edm[F[k, 2], F[k, 1]] = j
                E[j, :] = [F[k, 1], F[k, 2]]
                j = j + 1
            if (edm[F[k, 0], F[k, 2]] == -1):
                edm[F[k, 2], F[k, 0]] = j
                edm[F[k, 0], F[k, 2]] = j
                E[j, :] = [F[k, 2], F[k, 0]]
                j = j + 1
        E = E[0:j, :]

        edgeFace = np.zeros([j, nf])
        ne = j
        # print(E)

        # Compute Laplacian matrix
        L = np.zeros([nv, nv])

        for k in range(ne):
            L[E[k, 0], E[k, 1]] = 1
            L[E[k, 1], E[k, 0]] = 1

        for k in range(nv):
            L[k, k] = - L[k, :].sum()

        return L

    def cotanLaplacian(self, eps=1e-8):
        L = pp3d.cotan_laplacian(self.vertices, self.faces, denom_eps=1e-10)
        massvec_np = pp3d.vertex_areas(self.vertices, self.faces)
        massvec_np += eps * np.mean(massvec_np)

        if (np.isnan(L.data).any()):
            raise RuntimeError("NaN Laplace matrix")
        if (np.isnan(massvec_np).any()):
            raise RuntimeError("NaN mass matrix")
        self.L = L 
        self.massvec_np = massvec_np
        return L, massvec_np

    def lapEigen(self, n_eig=10, eps=1e-8):
        L_eigsh = (self.L + sp.sparse.identity(self.L.shape[0]) * eps).tocsc()
        massvec_eigsh = self.massvec_np
        Mmat = sp.sparse.diags(massvec_eigsh)
        eigs_sigma = eps#-0.01
        evals, evecs = sla.eigsh(L_eigsh, k=n_eig, M=Mmat, sigma=eigs_sigma)
        return evals, evecs

    def laplacianSegmentation(self, k, verbose=False):
        # (L, AA) = self.laplacianMatrix()
        # # print((L.shape[0]-k-1, L.shape[0]-2))
        # (D, y) = spLA.eigh(L, AA, eigvals=(L.shape[0] - k, L.shape[0] - 1))
        evals, evecs = self.lapEigen(k*2)
        y = evecs[:, 1:] * np.exp(-2*0.1 * evals[1:]) #**2
        # N = y.shape[0]
        # d = y.shape[1]
        # I = np.argsort(y.sum(axis=1))
        # I0 = np.floor((N - 1) * sp.linspace(0, 1, num=k)).astype(int)
        # # print(y.shape, L.shape, N, k, d)
        # C = y[I0, :].copy()
        #
        # eps = 1e-20
        # Cold = C.copy()
        # u = ((C.reshape([k, 1, d]) - y.reshape([1, N, d])) ** 2).sum(axis=2)
        # T = u.min(axis=0).sum() / (N)
        # # print(T)
        # j = 0
        # while j < 5000:
        #     u0 = u - u.min(axis=0).reshape([1, N])
        #     w = np.exp(-u0 / T);
        #     w = w / (eps + w.sum(axis=0).reshape([1, N]))
        #     # print(w.min(), w.max())
        #     cost = (u * w).sum() + T * (w * np.log(w + eps)).sum()
        #     C = np.dot(w, y) / (eps + w.sum(axis=1).reshape([k, 1]))
        #     # print(j, 'cost0 ', cost)
        #
        #     u = ((C.reshape([k, 1, d]) - y.reshape([1, N, d])) ** 2).sum(axis=2)
        #     cost = (u * w).sum() + T * (w * np.log(w + eps)).sum()
        #     err = np.sqrt(((C - Cold) ** 2).sum(axis=1)).sum()
        #     # print(j, 'cost ', cost, err, T)
        #     if (j > 100) & (err < 1e-4):
        #         break
        #     j = j + 1
        #     Cold = C.copy()
        #     T = T * 0.99
        #
        #     # print(k, d, C.shape)
        # dst = ((C.reshape([k, 1, d]) - y.reshape([1, N, d])) ** 2).sum(axis=2)
        # md = dst.min(axis=0)
        # idx = np.zeros(N).astype(int)
        # for j in range(N):
        #     I = np.flatnonzero(dst[:, j] < md[j] + 1e-10)
        #     idx[j] = I[0]
        # I = -np.ones(k).astype(int)
        # kk = 0
        # for j in range(k):
        #     if True in (idx == j):
        #         I[j] = kk
        #         kk += 1
        # idx = I[idx]
        # if idx.max() < (k - 1):
        #     print('Warning: kmeans convergence with %d clusters instead of %d' % (idx.max(), k))
        #     # ml = w.sum(axis=1)/N
        kmeans = KMeans(n_clusters=k, random_state=0, n_init="auto").fit(y)
        # kmeans = DBSCAN().fit(y)
        idx = kmeans.labels_
        nc = idx.max() + 1
        C = np.zeros([nc, self.vertices.shape[1]])
        a, foo = self.computeVertexArea()
        for k in range(nc):
            I = np.flatnonzero(idx == k)
            nI = len(I)
            # print(a.shape, nI)
            aI = a[I]
            ak = aI.sum()
            C[k, :] = (self.vertices[I, :] * aI).sum(axis=0) / ak;
        mean_eigen = (y*a).sum(axis=0)/a
        tree = cKDTree(y)
        _, indices = tree.query(mean_eigen, k=1)
        index_center = indices[0]
        _, indices = tree.query(C, k=1)
        index_C = indices[0]

        mesh = tm.Trimesh(vertices=self.vertices, faces=self.faces)
        nv = self.computeVertexNormals()
        rori = self.vertices[index] + 0.001 * (-nv[index, :])
        rdir = -nv[index, :]

        locations, index_ray, index_tri = mesh.ray.intersects_location(ray_origins=rori[None, :], ray_directions=rdir[None, :])
        if verbose:
            print(locations, index_ray, index_tri)
            print(index_center, index_C)
        return idx, C, index_center, locations[0]

    def get_keypoints(self, n_eig=30, n_points=5, sym=False):
        evals, evecs = self.lapEigen(n_eig+1)
        pts_evecs = evecs[:, 1:] * np.exp(-2*0.1 * evals[1:]) # approximate geod distance
        tree = cKDTree(pts_evecs)
        _, center_index = tree.query(np.zeros(pts_evecs.shape[-1]), k=1)
        indices = fps_gpt_geod(self.vertices, self.faces, 10, center_index)[1:]
        areas = np.linalg.norm(self.surfel, axis=-1, keepdims=True)
        area = np.sqrt(areas.sum()/2)
        print(area)
        ## Looking for center + provide distances to the center
        
        print(center_index)
        solver = pp3d.MeshHeatMethodDistanceSolver(self.vertices, self.faces)
        norm_center = solver.compute_distance(center_index)
    
        ## Dist matrix just between selected points
        dist_mat_indices = np.zeros((len(indices), len(indices)))
        all_ii = np.arange(len(indices)) # just to easy code
        for ii, index in enumerate(indices):
            dist_mat_indices[ii, ii!=all_ii] = solver.compute_distance(index)[indices[indices != index]]
    
        ## Select points which : farthest from the center, delete their neighbors with dist < 0.5*area
        keep = []
        max_norm = norm_center.max()
        for ii, index in enumerate(indices[:n_points]):
            # distances_compar = (dist_mat_indices[ii, ii!=all_ii] + norm_center[ii]) / norm_center[indices[ii!=all_ii]]
            # min_dist = np.amin(np.abs(distances_compar - 1))
            # print(min_dist/norm_center[ii], min_dist)
            # if min_dist > 0.3:
            #     #print(ii, min_dist/norm_center[ii], norm_center[ii], dist_mat_indices[ii, ii!=all_ii], norm_center[indices[indices != index]], indices[7])
            keep.append(index)
        ## Add the index of the center
        ## Add the index of the center 
        if sym:
            mesh = tm.base.Trimesh(self.vertices, self.faces, process=False)  # Load your mesh
            # Given data
            index = 123  # Your starting point index
            direction = -mesh.vertex_normals[center_index]
            
            # Get the starting vertex position
            start_point = mesh.vertices[center_index]
            
            # Perform ray intersection
            locations, index_ray, index_tri = mesh.ray.intersects_location(
                ray_origins=start_point[None, :],  # Starting point
                ray_directions=direction[None, :]  # Direction of travel
            )
            
            # If intersections exist
            if len(locations) > 0:
                # Sort intersections by distance from start_point
                distances = np.linalg.norm(locations - start_point, axis=1)
                sorted_indices = np.argsort(distances)
            
                # Get the first valid intersection point beyond the start point
                #next_intersection = locations[sorted_indices]
                #print(f"Next intersection at: {next_intersection}")
                intersected_triangle = index_tri[sorted_indices[1]]
                print(f"Intersected Triangle Index: {mesh.faces[intersected_triangle]}")
                center_index = mesh.faces[intersected_triangle][0]
            else:
                print("No intersection found in the given direction.")
        keep.append(center_index)
        return keep


    # Computes surface volume
    def surfVolume(self):
        f = self.faces
        v = self.vertices
        t = v[f, :]
        vols = np.linalg.det(t) / 6
        return vols.sum(), vols

    def surfCenter(self):
        f = self.faces
        v = self.vertices
        center_infs = (v[f, :].sum(axis=1) / 4) * self.vols[:, np.newaxis]
        center = center_infs.sum(axis=0)
        return center

    def surfMoments(self):
        f = self.faces
        v = self.vertices
        vec_0 = v[f[:, 0], :] + v[f[:, 1], :]
        s_0 = vec_0[:, :, np.newaxis] * vec_0[:, np.newaxis, :]
        vec_1 = v[f[:, 0], :] + v[f[:, 2], :]
        s_1 = vec_1[:, :, np.newaxis] * vec_1[:, np.newaxis, :]
        vec_2 = v[f[:, 1], :] + v[f[:, 2], :]
        s_2 = vec_2[:, :, np.newaxis] * vec_2[:, np.newaxis, :]
        moments_inf = self.vols[:, np.newaxis, np.newaxis] * (1. / 20) * (s_0 + s_1 + s_2)
        return moments_inf.sum(axis=0)

    def surfF(self):
        f = self.faces
        v = self.vertices
        cent = (v[f, :].sum(axis=1)) / 4.
        F = self.vols[:, np.newaxis] * np.sign(cent) * (cent ** 2)
        return F.sum(axis=0)

    def surfU(self):
        vol = self.volume
        vertices = self.vertices / pow(vol, 1. / 3)
        vertices -= self.center
        self.updateVertices(vertices)
        moments = self.surfMoments()
        u, s, vh = np.linalg.svd(moments)
        F = self.surfF()
        return np.diag(np.sign(F)) @ u, s

    def surfEllipsoid(self, u, s, moments):
        coeff = pow(4 * np.pi / 15, 1. / 5) * pow(np.linalg.det(moments), -1. / 10)
        A = coeff * ((u * np.sqrt(s)) @ u.T)
        return u, A

    # Reads from .off file
    def readOFF(self, offfile):
        with open(offfile, 'r') as f:
            all_lines = f.readlines()
    
    
        n_vertices = int(all_lines[1].split()[0])
        n_faces = int(all_lines[1].split()[1])

        vertices_list = []
        for i in range(n_vertices):
            vertices_list.append([float(x) for x in all_lines[2+i].split()[:3]])

        faces_list = []
        for i in range(n_faces):
            # Be careful to convert to int. Otherwise, you can use np.array(faces_list).astype(np.int32)
            faces_list.append([int(x) for x in all_lines[2+i+n_vertices].split()[1:4]])
        self.faces = np.array(faces_list)
        self.vertices = np.array(vertices_list)
        self.computeCentersAreas()    # Reads from .byu file
    def readbyu(self, byufile):
        with open(byufile, 'r') as fbyu:
            ln0 = fbyu.readline()
            ln = ln0.split()
            # read header
            ncomponents = int(ln[0])  # number of components
            npoints = int(ln[1])  # number of vertices
            nfaces = int(ln[2])  # number of faces
            # fscanf(fbyu,'%d',1);		% number of edges
            # %ntest = fscanf(fbyu,'%d',1);		% number of edges
            for k in range(ncomponents):
                fbyu.readline()  # components (ignored)
            # read data
            self.vertices = np.empty([npoints, 3])
            k = -1
            while k < npoints - 1:
                ln = fbyu.readline().split()
                k = k + 1;
                self.vertices[k, 0] = float(ln[0])
                self.vertices[k, 1] = float(ln[1])
                self.vertices[k, 2] = float(ln[2])
                if len(ln) > 3:
                    k = k + 1;
                    self.vertices[k, 0] = float(ln[3])
                    self.vertices[k, 1] = float(ln[4])
                    self.vertices[k, 2] = float(ln[5])

            self.faces = np.empty([nfaces, 3])
            ln = fbyu.readline().split()
            kf = 0
            j = 0
            while ln:
                if kf >= nfaces:
                    break
                    # print(nfaces, kf, ln)
                for s in ln:
                    self.faces[kf, j] = int(sp.fabs(int(s)))
                    j = j + 1
                    if j == 3:
                        kf = kf + 1
                        j = 0
                ln = fbyu.readline().split()
        self.faces = np.int_(self.faces) - 1
        xDef1 = self.vertices[self.faces[:, 0], :]
        xDef2 = self.vertices[self.faces[:, 1], :]
        xDef3 = self.vertices[self.faces[:, 2], :]
        self.centers = (xDef1 + xDef2 + xDef3) / 3
        self.surfel = np.cross(xDef2 - xDef1, xDef3 - xDef1)

    # Saves in .byu format
    def savebyu(self, byufile):
        # FV = readbyu(byufile)
        # reads from a .byu file into matlab's face vertex structure FV

        with open(byufile, 'w') as fbyu:
            # copy header
            ncomponents = 1  # number of components
            npoints = self.vertices.shape[0]  # number of vertices
            nfaces = self.faces.shape[0]  # number of faces
            nedges = 3 * nfaces  # number of edges

            str = '{0: d} {1: d} {2: d} {3: d} 0\n'.format(ncomponents, npoints, nfaces, nedges)
            fbyu.write(str)
            str = '1 {0: d}\n'.format(nfaces)
            fbyu.write(str)

            k = -1
            while k < (npoints - 1):
                k = k + 1
                str = '{0: f} {1: f} {2: f} '.format(self.vertices[k, 0], self.vertices[k, 1], self.vertices[k, 2])
                fbyu.write(str)
                if k < (npoints - 1):
                    k = k + 1
                    str = '{0: f} {1: f} {2: f}\n'.format(self.vertices[k, 0], self.vertices[k, 1], self.vertices[k, 2])
                    fbyu.write(str)
                else:
                    fbyu.write('\n')

            j = 0
            for k in range(nfaces):
                for kk in (0, 1):
                    fbyu.write('{0: d} '.format(self.faces[k, kk] + 1))
                    j = j + 1
                    if j == 16:
                        fbyu.write('\n')
                        j = 0

                fbyu.write('{0: d} '.format(-self.faces[k, 2] - 1))
                j = j + 1
                if j == 16:
                    fbyu.write('\n')
                    j = 0

    def saveVTK(self, fileName, scalars=None, normals=None, tensors=None, scal_name='scalars', vectors=None,
                vect_name='vectors'):
        vf = vtkFields()
        # print(scalars)
        if not (scalars == None):
            vf.scalars.append(scal_name)
            vf.scalars.append(scalars)
        if not (vectors == None):
            vf.vectors.append(vect_name)
            vf.vectors.append(vectors)
        if not (normals == None):
            vf.normals.append('normals')
            vf.normals.append(normals)
        if not (tensors == None):
            vf.tensors.append('tensors')
            vf.tensors.append(tensors)
        self.saveVTK2(fileName, vf)

    # Saves in .vtk format
    def saveVTK2(self, fileName, vtkFields=None):
        F = self.faces;
        V = self.vertices;

        with open(fileName, 'w') as fvtkout:
            fvtkout.write('# vtk DataFile Version 3.0\nSurface Data\nASCII\nDATASET POLYDATA\n')
            fvtkout.write('\nPOINTS {0: d} float'.format(V.shape[0]))
            for ll in range(V.shape[0]):
                fvtkout.write('\n{0: f} {1: f} {2: f}'.format(V[ll, 0], V[ll, 1], V[ll, 2]))
            fvtkout.write('\nPOLYGONS {0:d} {1:d}'.format(F.shape[0], 4 * F.shape[0]))
            for ll in range(F.shape[0]):
                fvtkout.write('\n3 {0: d} {1: d} {2: d}'.format(F[ll, 0], F[ll, 1], F[ll, 2]))
            if not (vtkFields == None):
                wrote_pd_hdr = False
                if len(vtkFields.scalars) > 0:
                    if not wrote_pd_hdr:
                        fvtkout.write(('\nPOINT_DATA {0: d}').format(V.shape[0]))
                        wrote_pd_hdr = True
                    nf = len(vtkFields.scalars) / 2
                    for k in range(nf):
                        fvtkout.write('\nSCALARS ' + vtkFields.scalars[2 * k] + ' float 1\nLOOKUP_TABLE default')
                        for ll in range(V.shape[0]):
                            # print(scalars[ll])
                            fvtkout.write('\n {0: .5f}'.format(vtkFields.scalars[2 * k + 1][ll]))
                if len(vtkFields.vectors) > 0:
                    if not wrote_pd_hdr:
                        fvtkout.write(('\nPOINT_DATA {0: d}').format(V.shape[0]))
                        wrote_pd_hdr = True
                    nf = len(vtkFields.vectors) / 2
                    for k in range(nf):
                        fvtkout.write('\nVECTORS ' + vtkFields.vectors[2 * k] + ' float')
                        vectors = vtkFields.vectors[2 * k + 1]
                        for ll in range(V.shape[0]):
                            fvtkout.write(
                                '\n {0: .5f} {1: .5f} {2: .5f}'.format(vectors[ll, 0], vectors[ll, 1], vectors[ll, 2]))
                if len(vtkFields.normals) > 0:
                    if not wrote_pd_hdr:
                        fvtkout.write(('\nPOINT_DATA {0: d}').format(V.shape[0]))
                        wrote_pd_hdr = True
                    nf = len(vtkFields.normals) / 2
                    for k in range(nf):
                        fvtkout.write('\nNORMALS ' + vtkFields.normals[2 * k] + ' float')
                        vectors = vtkFields.normals[2 * k + 1]
                        for ll in range(V.shape[0]):
                            fvtkout.write(
                                '\n {0: .5f} {1: .5f} {2: .5f}'.format(vectors[ll, 0], vectors[ll, 1], vectors[ll, 2]))
                if len(vtkFields.tensors) > 0:
                    if not wrote_pd_hdr:
                        fvtkout.write(('\nPOINT_DATA {0: d}').format(V.shape[0]))
                        wrote_pd_hdr = True
                    nf = len(vtkFields.tensors) / 2
                    for k in range(nf):
                        fvtkout.write('\nTENSORS ' + vtkFields.tensors[2 * k] + ' float')
                        tensors = vtkFields.tensors[2 * k + 1]
                        for ll in range(V.shape[0]):
                            for kk in range(2):
                                fvtkout.write(
                                    '\n {0: .5f} {1: .5f} {2: .5f}'.format(tensors[ll, kk, 0], tensors[ll, kk, 1],
                                                                           tensors[ll, kk, 2]))
                fvtkout.write('\n')

    # Reads .vtk file
    def readVTK(self, fileName):
        if gotVTK:
            u = vtkPolyDataReader()
            u.SetFileName(fileName)
            u.Update()
            v = u.GetOutput()
            # print(v)
            npoints = int(v.GetNumberOfPoints())
            nfaces = int(v.GetNumberOfPolys())
            V = np.zeros([npoints, 3])
            for kk in range(npoints):
                V[kk, :] = np.array(v.GetPoint(kk))

            F = np.zeros([nfaces, 3])
            for kk in range(nfaces):
                c = v.GetCell(kk)
                for ll in range(3):
                    F[kk, ll] = c.GetPointId(ll)

            self.vertices = V
            self.faces = np.int_(F)
            xDef1 = self.vertices[self.faces[:, 0], :]
            xDef2 = self.vertices[self.faces[:, 1], :]
            xDef3 = self.vertices[self.faces[:, 2], :]
            self.centers = (xDef1 + xDef2 + xDef3) / 3
            self.surfel = np.cross(xDef2 - xDef1, xDef3 - xDef1)
        else:
            raise Exception('Cannot run readVTK without VTK')

    # Reads .obj file
    def readOBJ(self, fileName):
        if gotVTK:
            u = vtkOBJReader()
            u.SetFileName(fileName)
            u.Update()
            v = u.GetOutput()
            # print(v)
            npoints = int(v.GetNumberOfPoints())
            nfaces = int(v.GetNumberOfPolys())
            V = np.zeros([npoints, 3])
            for kk in range(npoints):
                V[kk, :] = np.array(v.GetPoint(kk))

            F = np.zeros([nfaces, 3])
            for kk in range(nfaces):
                c = v.GetCell(kk)
                for ll in range(3):
                    F[kk, ll] = c.GetPointId(ll)

            self.vertices = V
            self.faces = np.int_(F)
            xDef1 = self.vertices[self.faces[:, 0], :]
            xDef2 = self.vertices[self.faces[:, 1], :]
            xDef3 = self.vertices[self.faces[:, 2], :]
            self.centers = (xDef1 + xDef2 + xDef3) / 3
            self.surfel = np.cross(xDef2 - xDef1, xDef3 - xDef1)
        else:
            raise Exception('Cannot run readOBJ without VTK')

    def readPLY(self, fileName):
        if gotVTK:
            u = vtkPLYReader()
            u.SetFileName(fileName)
            u.Update()
            v = u.GetOutput()
            # print(v)
            npoints = int(v.GetNumberOfPoints())
            nfaces = int(v.GetNumberOfPolys())
            V = np.zeros([npoints, 3])
            for kk in range(npoints):
                V[kk, :] = np.array(v.GetPoint(kk))

            F = np.zeros([nfaces, 3])
            for kk in range(nfaces):
                c = v.GetCell(kk)
                for ll in range(3):
                    F[kk, ll] = c.GetPointId(ll)

            self.vertices = V
            self.faces = np.int_(F)
            xDef1 = self.vertices[self.faces[:, 0], :]
            xDef2 = self.vertices[self.faces[:, 1], :]
            xDef3 = self.vertices[self.faces[:, 2], :]
            self.centers = (xDef1 + xDef2 + xDef3) / 3
            self.surfel = np.cross(xDef2 - xDef1, xDef3 - xDef1)
        else:
            raise Exception('Cannot run readPLY without VTK')

    def readTRI(self, fileName):
        vertices = []
        faces = []
        with open(fileName, "r") as f:
            pithc = f.readlines()
            line_1 = pithc[0]
            n_pts, n_tri = line_1.split(' ')
            for i, line in enumerate(pithc[1:]):
                pouetage = line.split(' ')
                if i <= int(n_pts):
                    vertices.append([float(poupout) for poupout in pouetage[:3]])
                    # vertices.append([float(poupout) for poupout in pouetage[4:7]])
                else:
                    faces.append([int(poupout.split("\n")[0]) for poupout in pouetage[1:]])
        self.vertices = np.array(vertices)
        self.faces = np.array(faces)
        xDef1 = self.vertices[self.faces[:, 0], :]
        xDef2 = self.vertices[self.faces[:, 1], :]
        xDef3 = self.vertices[self.faces[:, 2], :]
        self.centers = (xDef1 + xDef2 + xDef3) / 3
        self.surfel = np.cross(xDef2 - xDef1, xDef3 - xDef1)

    def concatenate(self, fvl):
        nv = 0
        nf = 0
        for fv in fvl:
            nv += fv.vertices.shape[0]
            nf += fv.faces.shape[0]
        self.vertices = np.zeros([nv, 3])
        self.faces = np.zeros([nf, 3], dtype='int')

        nv0 = 0
        nf0 = 0
        for fv in fvl:
            nv = nv0 + fv.vertices.shape[0]
            nf = nf0 + fv.faces.shape[0]
            self.vertices[nv0:nv, :] = fv.vertices
            self.faces[nf0:nf, :] = fv.faces + nv0
            nv0 = nv
            nf0 = nf
        self.computeCentersAreas()

def get_surf_area(surf):
    areas = np.linalg.norm(surf.surfel, axis=-1)
    return areas.sum()/2

def centroid(surf):
    areas = np.linalg.norm(surf.surfel, axis=-1, keepdims=True)
    center = (surf.centers * areas).sum(axis=0) / areas.sum()
    return center, np.sqrt(areas.sum()/2)


def do_bbox_vertices(vertices):
    new_verts = np.zeros(vertices.shape)
    new_verts[:, 0] = (vertices[:, 0] - np.amin(vertices[:, 0]))/(np.amax(vertices[:, 0]) - np.amin(vertices[:, 0]))
    new_verts[:, 1] = (vertices[:, 1] - np.amin(vertices[:, 1]))/(np.amax(vertices[:, 1]) - np.amin(vertices[:, 1]))
    new_verts[:, 2] = (vertices[:, 2] - np.amin(vertices[:, 2]))/(np.amax(vertices[:, 1]) - np.amin(vertices[:, 2]))*0.5
    return new_verts

def opt_rot_surf(surf_1, surf_2, areas_c):
    center_1, _ = centroid(surf_1)
    pts_c1 = surf_1.centers - center_1
    center_2, _ = centroid(surf_2)
    pts_c2 = surf_2.centers - center_2 
    to_sum = pts_c1[:, :, np.newaxis] * pts_c2[:, np.newaxis, :]
    A = (to_sum * areas_c[:, :, np.newaxis]).sum(axis=0)
    #A = to_sum.sum(axis=0)
    u, _, v = np.linalg.svd(A)
    a = np.array([[1, 0, 0], [0, 1, 0], [0, 0, np.sign(np.linalg.det(A))]])
    O = u @ a @ v
    return O.T

def srnf(surf):
    areas = np.linalg.norm(surf.surfel, axis=-1, keepdims=True) + 1e-8
    return surf.surfel/np.sqrt(areas)

def fps_gpt(points, num_samples):
    """
    Selects a subset of points using the Farthest Point Sampling algorithm.

    :param points: numpy array of shape (N, D), where N is the number of points and D is the dimension of each point
    :param num_samples: number of points to select
    :return: numpy array of indices of the selected points
    """
    if num_samples > len(points):
        raise ValueError("num_samples must be less than or equal to the number of points")

    # Initialize an array to hold the indices of the selected points
    selected_indices = np.zeros(num_samples, dtype=int)

    center = np.mean(points, axis=0)

    # Array to store the shortest distance of each point to a selected poin
    shortest_distances = np.full(len(points), np.inf)
    last_selected_point = center
    for i in range(1, num_samples):
        

        # Update the shortest distance of each point to the selected points
        for j, point in enumerate(points):
            distance = np.linalg.norm(point - last_selected_point)
            shortest_distances[j] = min(shortest_distances[j], distance)

        # Select the point that is farthest from all selected points
        selected_indices[i] = np.argmax(shortest_distances)
        last_selected_point = points[selected_indices[i]]
    return selected_indices


def fps_gpt_geod(points, faces, num_samples, index_start):
    """
    Selects a subset of points using the Farthest Point Sampling algorithm.

    :param points: numpy array of shape (N, D), where N is the number of points and D is the dimension of each point
    :param num_samples: number of points to select
    :return: numpy array of indices of the selected points
    """
    if num_samples > len(points):
        raise ValueError("num_samples must be less than or equal to the number of points")

    # Initialize an array to hold the indices of the selected points
    selected_indices = np.zeros(num_samples, dtype=int)

    # Array to store the shortest distance of each point to a selected poin
    shortest_distances = np.full(len(points), np.inf)
    selected_indices[0] = index_start
    distances = np.zeros((num_samples, len(points)))
    solver = pp3d.MeshHeatMethodDistanceSolver(points, faces)
    for i in range(1, num_samples):
        distances[i] = (solver.compute_distance(selected_indices[i-1]))

        # Update the shortest distance of each point to the selected points
        for j, point in enumerate(points):
            distance = distances[i][j]
            shortest_distances[j] = min(shortest_distances[j], distance)

        # Select the point that is farthest from all selected points
        selected_indices[i] = np.argmax(shortest_distances)
    return selected_indices

# class MultiSurface:
#     def __init__(self, pattern):
#         self.surf = []
#         files = glob.glob(pattern)
#         for f in files:
#             self.surf.append(Surface(filename=f))