8

I clip a 3D triangle against a 3D Axis-Aligned Bounding Box (AABB) to obtain the largest planar polygon of the triangle contained in the AABB. My clipping algorithm is a (slightly modified) version of the robust (e.g. clipping planes have a small finite thickness) Sutherland-Hodgman algorithm as described in C. Ericson's Real-Time Collision Detection. I clip the triangle against each of the 6 planes constituting the AABB.

In order to avoid heap (de)allocation, I allocated a fixed size point buffer on the stack in advance for all the vertices of the obtained planar polygon. My question now is: what is the maximum number of vertices possible one can obtain after clipping a triangle against an AABB?

Based on the control flow, every examined vertex can result in two vertices during a polygon plane clipping. Thus $3*2^6$ vertices. Due to symmetry this becomes $3*2^3=24$ vertices. However, I always obtain less vertices in practice.

Nero
  • 1,310
  • 3
  • 15
  • 31
Matthias
  • 1,044
  • 9
  • 25

1 Answers1

9

Funnily enough, I asked this exact question on Math.SE a couple years ago: Maximum number of vertices in intersection of triangle with box.

The answer is 9 vertices, because each of the 6 planes of the box can cut off one corner of the polygon, replacing one vertex with two. So 3 vertices + 6 added vertices due to clipping = 9 total.

Community
  • 1
Nathan Reed
  • 24,302
  • 2
  • 63
  • 103