Generate 2D cross-section polygon from 3D mesh

Question

I'm writing a game which uses 3D models to draw a scene (top-down orthographic projection), but a 2D physics engine to calculate response to collisions, etc. I have a few 3D assets for which I'd like to be able to automatically generate a hitbox by 'slicing' the 3D mesh with the X-Y plane and creating a polygon from the resultant edges.

Google is failing me on this one (and not much helpful material on SO either). Suggestions?

The meshes I'm dealing with will be simplified versions of the displayed models, which are connected, closed, non-convex and have zero genus.

Considering your description, might it also be acceptable to project the 3D mesh onto a 2D plane? The projection part is easy, and reduces the question to "creating a polygon from a bunch of overlapping triangles", which may be easier to solve, especially if your projection is convex. — Thomas
Maybe you can tell us more about your mesh. Is it convex? Is it connected? Is it closed? Does it have zero genus? How is it represented in memory? — Thomas
The meshes are not convex, but they will be connected and closed, and have zero genus. — nornagon
@Thomas, could you provide any more detail about the "create a poly from overlapping triangles" method? (or should I start a new question?) — nornagon
I think a new question would be appropriate. Post the link here once you've opened it! — Thomas

Thomas Thomas · Accepted Answer · 2010-05-09T11:46:09

Since your meshes are not convex, the resulting cross-section may be disconnected, so actually consist of multiple polygons. This means that every triangle must be checked, so you'll need at least O(n) operations for n triangles.

Here's one way to do it:

T <- the set of all triangles
P <- {}
while T is not empty:
  t <- some element from T
  remove t from T
  if t intersects the plane:
    l <- the line segment that is the intersection between t and the plane
    p <- [l]
    s <- l.start
    while l.end is not s:
      t <- the triangle neighbouring t on the edge that generated l.end
      remove t from T
      l <- the line segment that is the intersection between t and the plane
      append l to p
    add p to P

This will run in O(n) time for n triangles, provided that your triangles have pointers to their three neighbours, and that T supports constant-time removals (e.g. a hash set).

As with all geometric algorithms, the devil is in the details. Think carefully about cases where a triangle's vertex is exactly in the plane, for example.

Generate 2D cross-section polygon from 3D mesh

2 Answers