<p>If the loop is convex then one solution is to use a simple polyhedron clipping algorithm.</p>
<p>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..</p>
<p>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).</p>
<p>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.</p>
<p>Repeat this process for every segment of the polygon.</p>
<p>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.</p>
<p>This is similar to how decals are generated for a polygon mesh in some algorithms.</p>
<p>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.</p>
<hr />
<p>computing a normal to the plane using the two line segments:
If the sphere center is <span class="math-container">$r$</span>, the line has end points <span class="math-container">$a,b$</span>. Then the equation becomes <span class="math-container">$pN = normalize( cross( a-r, a-b))$</span> and the point for the plane becomes <span class="math-container">$a$</span>. To put the plane into the implicit form compute d with <span class="math-container">$d= dot(-pN, a)$</span> and the final plane becomes <span class="math-container">$[pN | d]$</span>. 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 <span class="math-container">$(x,y,z,1)$</span></p>
<hr />
<p>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.</p>

CC BY-SA 4.0
2023-05-03T14:20:03.933Z
thanks for the detailed explanation. It's really helpful.
veggieg
CC BY-SA 4.0
2023-05-03T15:51:41.637Z
Sorry if this sounds too dumb but I have trouble understanding the normal of the plane in convex case. If the plane is perpendicular to the sphere then its normal would be vector3d(sphereCenter- planeCenter) where planeCenter is one of the points of a segment(edge), and then you said the normal is tangent to the sphere at the point, isn't the tangent line perpendicular to  vector3d(sphereCenter- planeCenter)?
veggieg
CC BY-SA 4.0
2023-05-04T01:50:31.857Z
"The plane and the normal of the plane are perpendicular to each other. " yeah I get this. What I'm confused about is that if the plane is perpendicular to the sphere then the plane is a tangent plane of sphere, then the normal would be the radius vector, how can it be tangent to the sphere? Or I misunderstood the meaning of "perperdicular to the sphere"?
veggieg
CC BY-SA 4.0
2023-05-04T12:25:53.830Z
I added a small section for computing the plane near the bottom of the answer hopefully this will help clear things up. BTW, this method to clipping polyhedrons is a powerful technique and is worth the trouble of learning since it can be applied in several other useful situations.
pmw1234
CC BY-SA 4.0
2023-05-05T03:23:42.037Z
thanks that's detailed enough! It just occurs to me, is the convex case a 3d case for Sutherland–Hodgman algorithm?
veggieg
CC BY-SA 4.0
2023-05-05T10:28:53.050Z
This is very similar to Sutherland-Hodgeman but I'm not sure this is the same since it works with polyhedron instead of polygons.
pmw1234
CC BY-SA 4.0
2023-05-03T13:51:37.343Z
2023-05-04T13:40:41.333Z
2023-05-04T13:40:41.333Z
pmw1234
<p><a href="https://i.sstatic.net/0W2FL.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/0W2FL.png" alt="loop illustrated in cyan" /></a></p>
<p>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?</p>
<p>I've thought of using simple BFS(breadth first search) on sphere.</p>
<ol>
<li>first create a sphere mesh with specified center and radius</li>
<li>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)</li>
<li>pick a random seed to extract the patch</li>
</ol>
<p>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)</p>
<p>I'm wondering if there are alternatives to solve this kind of problem?</p>

<mesh><geometry>
How to extract region inside a loop on sphere
veggieg
# How to extract region inside a loop on sphere

(Asked by: username_0 on 2023-05-03)

[![loop illustrated in cyan](https://i.sstatic.net/0W2FL.png)](https://i.sstatic.net/0W2FL.png)

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?

**Tags:** mesh, geometry


---

## 1 answers

### Answer by username_1 on 2023-05-03. Score: 1

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.

> **Comments:**
> **username_0**: thanks for the detailed explanation. It's really helpful.  
> **username_0**: Sorry if this sounds too dumb but I have trouble understanding the normal of the plane in convex case. If the plane is perpendicular to the sphere then its normal would be vector3d(sphereCenter- planeCenter) where planeCenter is one of the points of a segment(edge), and then you said the normal is tangent to the sphere at the point, isn't the tangent line perpendicular to  vector3d(sphereCenter- planeCenter)?  
> **username_0**: "The plane and the normal of the plane are perpendicular to each other. " yeah I get this. What I'm confused about is that if the plane is perpendicular to the sphere then the plane is a tangent plane of sphere, then the normal would be the radius vector, how can it be tangent to the sphere? Or I misunderstood the meaning of "perperdicular to the sphere"?  
> **username_1**: I added a small section for computing the plane near the bottom of the answer hopefully this will help clear things up. BTW, this method to clipping polyhedrons is a powerful technique and is worth the trouble of learning since it can be applied in several other useful situations.  
> **username_0**: thanks that's detailed enough! It just occurs to me, is the convex case a 3d case for Sutherland–Hodgman algorithm?  
> **username_1**: This is very similar to Sutherland-Hodgeman but I'm not sure this is the same since it works with polyhedron instead of polygons.  

---

