4
$\begingroup$

Suppose I have a set of points in 3D which are all co-planar, and which describe the vertices of a convex polygon. I know the coordinates of all of these vertices, I know the unit normal to the plane of the polygon, and I know the order (in a right-hand sense with respect to the normal) in which the vertices go around the polygon.

I also have a polyhedron, which is in general non-convex, and the surface of which is made of triangles. It is a triangle mesh like the one shown here. It describes a completely enclosed volume (no holes in the surface). I know the coordinates of all the vertices of all the triangles that make up the polyhedron. For a given vertex, I know the list of which triangles it is a vertex of.

One other thing I know, which may or may not be useful, is that the polygon lies "in the vicinity of" a particular pair of vertices of the polyhedron, say the ones with indices $i$ and $j$. So if there were to be some kind of a search of the surface of the polyhedron, that would be the place to start.

My task is to find the area of the intersection between the polygon and the polyhedron. I believe this is a well-defined quantity. I need an algorithm to calculate this, hopefully efficiently but at this point I'll take anything.

My thoughts:

I can classify each polygon vertex as either inside or outside the polyhedron. I've written a ray-casting algorithm that computes this fairly accurately and efficiently. That means that each edge of the polygon can be classified as either "both vertices inside", "both vertices outside", or "one in, one out." I can calculate the point of intersection between a given polygon edge and the polyhedron by checking a bunch of nearby triangles.

But that's not enough. For instance, just because both vertices of an edge are inside doesn't mean the whole edge is inside. A "finger" of the polyhedron might intersect an edge without touching either of its endpoints. Furthermore, the polyhedron might intersect the polygon in such a way that it doesn't touch any of the edges at all. Clearly, one must also calculate the intersections between the triangles' edges and the polygon as well.

It gets a bit too complicated for me at that point, and I'm wondering if there is some established algorithm for this?

Perhaps something like: Project the polyhedron onto the plane containing the polygon and then... I don't know.

Improve this question
$\endgroup$
5
  • $\begingroup$ Welcome to CS.SE! It seems like this reduces to computing the intersection between a triangle (from the polyhedron) and a line or face (of the polygon). Does that sound right? Am I missing something? Both of those should be doable. Perhaps I'm not exactly sure what the "area of intersection" indicates; is that the area of the intersection of their perimeters; or the volume of the intersection of their interiors? $\endgroup$
    – D.W. ♦
    Jun 2, 2017 at 18:47
  • $\begingroup$ @D.W. The polygon is a 2D object, embedded in a 3D space. It has no volume, only area. It is intersecting the volume of a 3D polyhedron. I need to compute the total area of the part of the polygon which is inside the polyhedron. It comes down to computing intersections between polygon edges and the triangles, as well as between triangles and the polygon. And then there needs to be some kind of topological calculation that determines the correct ordering of all of these points. I'm wondering if there's some standard algorithm for all of that. $\endgroup$
    – John Barber
    Jun 2, 2017 at 20:04
  • $\begingroup$ If you have a vicinity of points (starting point), then instead of projecting the polyhedron onto the plane you may find the slice of the polyhedron at the plane where your polygon is and then you only need to calculate polygon-polygon intersection. It might seem like overkill but taking the Weiler-Atherton intersection will cover all cases and return the intersection. Is it really a mesh, or have you got some better representation? Like a patch? $\endgroup$
    – Evil
    Jun 2, 2017 at 23:30
  • $\begingroup$ @Evil Now this seems like a very promising idea to me. I'm not sure of the precise definitions of "mesh" and "patch" in the context of computer graphics. My polyhedron consists of of a list of vertices, and a list of triangles defined by triplets of vertices. Is there some algorithm for finding the slice of the polyhedron? I can check all nearby triangles to find the set of line segments due to plane-polyhedron intersections, but how do I order them? $\endgroup$
    – John Barber
    Jun 3, 2017 at 1:11
  • $\begingroup$ Afaik, the mesh is what you have, and the patch is some kind of parametric tensor product of splines (like Bézier, or NURBS). In the mesh, you have already calculated normals, I have assumed that you store your triangles(faces) in some connected or localized manner, if not then it is a heavy task. The order of resulting "walk" around the polyhedron gathering line segments should give one polygon as the result since it was closed. The order comes from moving on the "cutting" plane $\endgroup$
    – Evil
    Jun 3, 2017 at 1:37

1 Answer 1

Reset to default
3
$\begingroup$

You have a 2D convex polygon $G$, and a 3D polyhedron $H$. Let $P_G$ denote the plane that the polygon is contained in. The following should work:

Their intersection is a 2D polygon. You can find the edges of the intersection as follows:

  • For each triangle of $H$:

    • If the triangle intersects $G$, output this intersection.

This procedure outputs the edges of a 2D polygon, and now you want to compute its area. To do this, compute a triangulation of it (which apparently can be done in linear time), then sum up the area of the resulting triangles.

You can test whether a triangle intersects $G$ as follows: compute the intersection of the triangle with $P_G$; call the result $R$. Typically, $R$ will be a point or line. $R$ can be computed efficiently. Then, compute the intersection of $R$ with $G$. This is purely a 2D problem. There are standard algorithms for solving this; see, e.g., https://en.wikipedia.org/wiki/Line_clipping or http://geomalgorithms.com/a13-_intersect-4.html.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your response. I think I understand what you're saying, but I think it leaves out a solution to the most difficult part of the problem. Note that the intersection, while a polygon, will not in general be a convex polygon. Just having a list of line segments where triangles intersect the polygon is therefore not enough to compute the area of the intersection. You also need to know how the new set of edges is connected, i.e. what order they're in. Deducing this from the topology of the polyhedron sounds difficult to me, unless I'm missing something obvious. $\endgroup$
    – John Barber
    Jun 2, 2017 at 21:55
  • $\begingroup$ @JohnBarber, OK. You may well be right. I am not an expert in this area. I think you know the edges of that polygon, and the order in which they occur, which might help. I edited the question to add a link to resources about polygon triangulation. I'd suggest checking them out, then if you can't find anything relevant, ask a new question specifically about how to compute the area of a polygon gives its edges and the order they occur, as that sounds like something that might be generally useful beyond this particular application and might be of use to others in the future as well. $\endgroup$
    – D.W. ♦
    Jun 2, 2017 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.