1
$\begingroup$

Let us say you have a polyotpe define as the intersection of halfplanes. That is you are given N half-spaces. The polytope is the volume defined by all points which lie on the positive side of all N half-spaces.

I want to make a mesh of the surface of the polytope. I.e. find the positions of the vertices plus their connectivity.

A possible way to go about it is to do dual contouring on the SDF generated by this polytope, but that generates a mesh with a lot of superfluous vertices and edges with are not necessarily the same as the vertices of the polytope.

$\endgroup$

1 Answer 1

3
$\begingroup$

Hints:

If efficiency is not your first concern, you can implement a simple solution.

Assume you have solved the problem for the first $k$ halfplanes and obtained a polyhedric representation, made of vertices, edges and faces. The next step is to cut that polyhedron with the next plane.

By means of the implicit equation of the plane, determine on which side lie every vertex and discard the ones on the wrong side. For all edges, discard those joining two vertices on the wrong side. Keep those with the vertices on the good side, and for the mixed ones, intersect with the plane and trim. Finally, some of the faces will be left untouched, some discarded, some trimmed, and a new one, joining all the edge intersections will be created.

Note that at any stage the poyhedron is convex, as are its faces. This eases the topological operations. It can be convenient to use a change of basis such that the cutting plane becomes $OXY$, making the intersection computations and reconstruction of the section an easier 2D problem.

$\endgroup$
3
  • 2
    $\begingroup$ If efficiency is a concern, the polyhedron/plane intersection problem can be implemented much faster. sciencedirect.com/science/article/pii/0304397582901207 Also worth noting that the simplex algorithm is called that for a reason: you can traverse the edges of a polytope using pivot operations. $\endgroup$
    – Pseudonym
    Jun 15, 2023 at 1:58
  • $\begingroup$ @Pseudonym: if I am right, this only solves the detection problem. Computation of the intersection points and topology updates take more effort. $\endgroup$
    – user16034
    Jun 15, 2023 at 7:50
  • $\begingroup$ IIRC, finding which polygons intersect the new plane is the more expensive problem as you add more planes. $\endgroup$
    – Pseudonym
    Jun 15, 2023 at 11:17

Your Answer

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

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