How to extract region inside a loop on sphere

Question

The input is a sphere(defined by radius and center) and a loop defined by a set of points(unordered, illustrated in cyan in the image above) that satisfy the implicit function of the sphere. How can I get the region enclosed by it?

I've thought of using simple BFS(breadth first search) on sphere.

1. first create a sphere mesh with specified center and radius
2. inflate the boundary points several times to form a closed loop(if the points are ordered, then it's better to perform a shortest path algorithm to make sure the loop is closed)
3. pick a random seed to extract the patch

there are several drawbacks of this algorithm: 1.because the seed is random, I might end up getting the outer region of the boundary 2.even if I get the right region, the boundary is not perfect(ie. the extracted triangles are not clipped to fit the shape of the boundary)

I'm wondering if there are alternatives to solve this kind of problem?

Answer 1

Given the low curvature of the curve, I guess that a simple nearest-neighbor strategy will allow you to reconstruct it. Start at an arbitrary point, link to the nearest neighbor, then link the nearest neighbor to its nearest neighbor in the opposite direction (disregard the points in the incoming half-plane). You can do this in the projected view or in spherical coordinates.

Now unwrapping the mesh in spherical coordinates the problem becomes a planar one and you have to build the intersection of the triangles and the inside of the curve. An interesting option is to resample the curve on the parallels, meridians and the tile diagonals: this directly gives you the intersection points with the facets of the mesh.

A final, uneasy step, is to determine which triangles are wholly contained inside the curve (those that carry no intersection on their sides and have a vertex inside it), and the remaining portions of those intersected by the curve. You will have to reconstruct the intersection polygons, and possibly triangulate them to keep triangular facets.

Answer 2

If the loop is convex then one solution is to use a simple polyhedron clipping algorithm.

First, Generate a non-planar polygon from the path of the loop, it sounds like this is already available. Then for each segment of the polygon define a plane that is perpendicular to the surface of the sphere and passes through the polygon segment. The normal for the plane is tangent to the sphere at that point and contains a point on the line..

Using the plane, iterate over every triangle in the sphere and classify the triangles as being on the negative side of the plane (distance to plane for all vertices of the triangle are negative), the positive side of the plane (all distances are positive) or crossing the plane (some combination of positive and negative).

With the plane normal computed to point inside the polygon: Discard triangles on the negative side, keep triangles on the positive side, and clip triangles to fit that cross.

Repeat this process for every segment of the polygon.

At least 1 more plane should be created that clips away the back side of the sphere. (usually just choose 3 points on the polygon then form a plane from them, and offset it by a small amount so it doesn't intersect the polygon). Create another plane offset in the opposite direction could be done to complete a convex polyhedron surrounding the region to be clipped.

This is similar to how decals are generated for a polygon mesh in some algorithms.

Another way to compute the planes normal is to compute the vector from the center of the sphere to a point on the polygon segment in question. Then compute a vector for the polygon segment take the cross product and normalize. This will give you a new vector that is perpendicular to the other two. Just make sure the ordering is done correctly so that new vector point to the inside of the loop. The plane distance becomes a point on the segment being clipped.

---

computing a normal to the plane using the two line segments: If the sphere center is $r$, the line has end points $a,b$. Then the equation becomes $pN = normalize( cross( a-r, a-b))$ and the point for the plane becomes $a$. To put the plane into the implicit form compute d with $d= dot(-pN, a)$ and the final plane becomes $[pN | d]$. To compute the distance to this plane take the 4d dot product of the point and the plane which will result in a signed distance to the plane. Where the homogenous points is of the form $(x,y,z,1)$

---

If the loop is not convex then a non-convex, non-planar (for polygon's that do not self intersect) polygon triangulation algorithm could be used. In this method triangulate the polygon, then align all vertices with the surface of the sphere (using a line formed between the center of the sphere and the generated point). Then tesselate to get triangle area near some preset value.