Creating AlphaShape from triangulation dataset

Is there any way to directly generate an 3D alpha shape from the triangulation dataset ( points and connectivity list matrices)? I don’t want to fit an alpha shape to the 3D points without using the connectivity list matrix as this leads to the loss of accuracy. The method I am looking for should incorporate both matrices (Points and ConnectivityList) to recreate the AlphaShape. I would appreciate any help you can provide.

Answer 1

[John D'Errico]

Is there any way? Trivially, yes. Ok, maybe trivial is in the eyes of the writer. I can say this because I have written both 2d and 3d alpha shape codes from scratch, and they both start from a triangulation/tessellation.

You just look at the surface facets of the triangulation. Then any tetrahedron that would allow the alpha ball to penetrate into the shape so that an alpha sphere of radius alpha would touch the interior vertex, that tetrahedron gets deleted. Now just test every surface facet. Whenever you delete a tetrahedron from the list, just update the list of surface facets.

There is some bookkeeping in this of course, and you will need to figure out the test to determine if an alpha ball can penetrate the shape through that facet. Without looking at any of my code, the test would seem to take two parts, first by looking at the radius of the in-circle that fits inside the triangular facet.

So, is there a way to do this? Yes, as I said, it is straightforward. You will need to write some code, since I won't provide the code I wrote myself (many years ago, before MATLAB even had a 2-d alpha shape. Geez, roughly 23 years ago, since I've been retired almost that long. Time flies.)

[Memo Remo]

Dear John,

I appreciate your help. That is definitely part of my plan to learn about the AlphaShape algorithm, but my ultimate goal is to use MATLAB inShape command to determine if an arbitrary point in 3D space is located inside a 3D point cloud geomtery. I was able to develop a ray casting algorithm for this purpose and it works great, but it is slow. I have datasets with 4M vertices and really need a fast algorithm like MATLAB's inShape to perform this analysis. To use inShape I must store my triangulated surface in an AlphaShape variable.

Assume that I was able to learn how to generate an AlphaShape algorithm from scratch, the the problem would be how to create a MATLAB AlphaShape variable from the AlphaShape I obtained.

[Memo Remo]

Or any inputs regarding how to develop MATLAB's inShape command that can work with triangulated surfaces would be highly appreciated.

[John D'Errico]

In my own case, I just wrote my own tools to test if a point was inside an alpha shape. My suite of tools was quite extensive, allowing things like a slice through a simplicial complex, mappings form one space to another, an adaptive numerical integration over a domain, surface modeling in multiple dimensions, adaptive surface modeling, intersections and unions of simplicial complexes, etc.

As far as the alphaShape tool, you cannot supply a triangulation as a basis for the alphaShape utility. Of that I am pretty sure.

X = alphaShape(rand(20,3))

X = 
  alphaShape with properties:

             Points: [20×3 double]
              Alpha: 0.3426
      HoleThreshold: 0
    RegionThreshold: 0

struct(X)

Warning: Calling STRUCT on an object prevents the object from hiding its implementation details and should thus be avoided. Use DISP or DISPLAY to see the visible public details of an object. See 'help struct' for more information.

ans = struct with fields:
             Points: [20×3 double]
              Alpha: 0.3426
      HoleThreshold: 0
    RegionThreshold: 0
      UnderlyingObj: []

So there are no hidden fields we can access to contain the simplicial dissection.

And that means we cannot create a tessellation, then stuff it into an object we can use inShape on. Sorry. At most you can create a feature request directly to tech support to allow that capability for the future.

[Memo Remo]

Dear John,

Thank you very much for your attention to my question. I appreciate that.

I try to use GPU parallel processing to run my ray casting algorithm instead.