Search code examples
matlabcomputational-geometrytriangulationsurfacedelaunay

How to get freeBoundary to respect initial triangulation vertex order. (2017a+)

This might be an x, y problem, so here is the situation I'm in. I'm creating a sphere, generating the x, y, z points using the method defined here. But for my project, I need to be able to generate hemispheres and limit the azimuth and elevation and still have uniform point generation defined by N (total number of points to generate over a given spherical surface area). I've found out how to do this, but I also needed the connectivity (roughly what were the "neighbors" of each x y z, or az, el, r=1 position).

Matlab provides something called delaunayTriangulation which won't give me the actual surface connections, but the tetrahedron connections. I found a method of getting the surface from the triangulation object returned by the delaunayTriangulation function, called freeBoundary which returns two things in the form [FBtri, FBpoints]. FBtri is a n x 3 matrix of integers where each row contains a set of three integers that correspond to the rows inside the FBpoints (thus creating a triangle). FBpoints is a n x 3 matrix, where each row corresponds to the x,y,and z coordinates of a point on the surface.

The issue with freeBoundary is that I don't just wan't a triangle for just any point on the semisphere surface, only those within my azimuth elevation range. For example, if I limit the elevation on the top of the sphere to not be above pi/4, then there should be a big hole on the top of the sphere. Here are some visual examples of what I did.

Sphere with Bad points

enter image description here

Sphere with removed points

enter image description here

To "solve" this issue I have a series of convoluted steps to generate "bad points" which are appending to the points used in generating the initial delaunay triangulation, and then search for in the connectivity list in the output of freeBoundary to remove them. This could be done via simply removing all connections that exist after a certain index (as I append the "bad points" after the ones I actually need to use), however to my horror freeBoundary does not actually keep the order of points the same as the input coming from triangulation objects (and likes to scramble it, but only for the bad points I've added) so I can't easily remove invalid connections, and the indices in the connections do not actually correspond 1:1 to my original true set of points. Here is an example of the ordering issue

the actual order

enter image description here

the ruined order

enter image description here

If I cannot force freeBoundary to be nice, then I'm going to have to programmically reorder the points myself, which I don't see being a fast operation in time complexity (though I may be wrong). I believe in order to manually do this, I would have to find the new updated positions, and manually update them for each connection in the connectivity list, which is (O(triangleCount)*changedIdxCount) which doesn't look good for me, I'm generating thousands of points.

Here is an example of what I'm doing so far:

goodPoints = generateSphere(...);
badPoints = generateBadSpherePoints(...);
points = vertcat(goodPoints, badPoints);
triObj = delaunayTriangulation(points(:,1), points(:,2), points(:,3));
[FBtri, FBpoints] = freeBoundary(triObj);
...
%remove the bad points and get only good connections!
Solution

  • If you want the facets in FBtri to reference the points you use to make the initial triangulation instead of the vertices in FBpoints, all you have to do is omit capturing FBpoints as a second output:

    FBtri = freeBoundary(triObj);

    As per the freeBoundary documentation:

    The vertex IDs in FBtri reference a specific matrix, depending on the syntax you choose:

    • If you call freeBoundary with one output argument, then the elements of FBtri are row numbers of TR.Points.

    • If you call freeBoundary with two output arguments, then the elements of FBtri are row numbers of FBpoints.