Jumlah maksimum simpul setelah memotong segitiga melawan AABB

Saya klip segitiga 3D terhadap 3D Axis-Aligned Bounding Box (AABB) untuk mendapatkan poligon planar terbesar dari segitiga yang terkandung dalam AABB. Algoritme kliping saya adalah versi (sedikit dimodifikasi) dari robust (mis. Pesawat clipping memiliki ketebalan terbatas) Algoritma Sutherland-Hodgman seperti yang dijelaskan dalam Deteksi Tabrakan Real-Time C. Ericson. Saya klip segitiga terhadap masing-masing dari 6 pesawat yang merupakan AABB.

Untuk menghindari alokasi heap (de), saya mengalokasikan buffer titik ukuran tetap pada stack terlebih dahulu untuk semua simpul poligon planar yang diperoleh. Pertanyaan saya sekarang adalah: berapakah jumlah simpul maksimum yang dapat diperoleh setelah memotong segitiga melawan AABB?

Berdasarkan aliran kontrol, setiap simpul yang diperiksa dapat menghasilkan dua simpul selama kliping bidang poligon. Jadi$3*2^6$sudut. Karena simetri, ini menjadi$3*2^3=24$sudut. Namun, saya selalu mendapatkan lebih sedikit simpul dalam praktik.

Lucunya, saya menanyakan pertanyaan persis ini pada Math.SE beberapa tahun yang lalu: Jumlah maksimum simpul di persimpangan segitiga dengan kotak .

Jawabannya adalah 9 simpul, karena masing-masing dari 6 bidang kotak dapat memotong satu sudut poligon, mengganti satu simpul dengan dua. Jadi 3 simpul + 6 simpul ditambahkan karena kliping = 9 total.