3D Computational Geometry

Doom (1993) ran on a 486 CPU with no GPU and rendered a 3D world in real time. The secret: a prebuilt BSP-tree that determined drawing order in O(n). 3D geometry is not just mathematics - it is the foundation of computer graphics, physics simulations, and robotics.

• **Game engines** (Unreal, Unity) - convex hulls and BSP for collision detection
• **CAD systems** - halfspace intersection for CSG (Constructive Solid Geometry)
• **Robotics** - motion planning through obstacles in 3D configuration space
• **Physics simulations** - GJK and EPA use convex hulls for collision detection

Convex Hull in 3D: Quickhull Algorithm

The convex hull of a point set in 3D is the smallest convex polyhedron containing all points. In 2D it is a closed contour. In 3D it is a set of triangular faces. Quickhull is the most practical algorithm: O(n log n) average case, O(n^2) worst case, but excellent on random data.

**Lower bound:** building the convex hull of n points in 3D requires Omega(n log n) - proved by reduction from sorting. Quickhull matches this bound on random data.

Halfspace Intersection

A convex polyhedron can be described in two ways: as the convex hull of a set of points (V-representation) or as the intersection of halfspaces (H-representation). Converting between them is a duality that underlies linear programming and many geometric algorithms.

**Point-plane duality:** a point (a, b, c) in the primal space corresponds to the plane z = ax + by - c in the dual. This makes convex hull and halfspace intersection mirror-symmetric problems - an algorithm for one automatically solves the other.

Polyhedra and Euler's Formula

Euler's formula is one of the fundamental theorems of geometry: V - E + F = 2 for any convex polyhedron, where V = vertices, E = edges, F = faces. Leonhard Euler proved it in 1758. The formula constrains the possible shapes of polyhedra and has consequences for algorithms.

**Upper Bound Theorem:** the convex hull of n points in d-dimensional space has O(n^floor(d/2)) faces. In 3D this is O(n) - practically linear. In 4D it is already O(n^2) - this is why 4D convex hulls appear in linear programming algorithms.

BSP-Trees in 3D

Binary Space Partitioning (BSP) is a technique for recursively partitioning 3D space with planes. A BSP-tree allows geometry to be sorted from back to front in O(n) - without explicit sorting. In the 1990s every 3D game (Doom, Quake) used BSP as the foundation of its rendering pipeline.

**Splitting plane selection** is the key heuristic: minimizing polygon splits keeps the tree balanced and small. In practice the SAH (Surface Area Heuristic) is used - selecting the plane that minimizes expected ray traversal cost. Modern games moved from BSP to BVH (Bounding Volume Hierarchy), but BSP remains relevant for visibility determination and CSG (Constructive Solid Geometry).

3D Computational Geometry

• Quickhull 3D: O(n log n) average - builds initial tetrahedron, adds farthest points via horizon ridge
• H-representation: convex polyhedron as halfspace intersection Ax <= b, dual to V-representation
• Euler's formula V - E + F = 2 for convex polyhedra; Euler characteristic generalizes to topological surfaces
• Convex hull of n points in 3D has O(n) faces on average (Upper Bound Theorem: O(n^floor(d/2)))
• BSP-tree: recursive space partitioning with planes, O(n) traversal for Painter's Algorithm
• Splitting plane selection uses SAH heuristic; modern alternative is BVH

Related Topics

3D geometry extends 2D algorithms and introduces structures specific to three dimensions.

• Convex Hull in 2D — 2D analog - Graham Scan and Jarvis March
• Delaunay Triangulation — 3D Delaunay triangulation with tetrahedra
• Polygon Triangulation — 2D polygon decomposition as the basis for 3D meshing

Вопросы для размышления

• Why does the convex hull in 4D have O(n^2) faces while in 3D it has only O(n)? What does this imply for linear programming algorithms?
• BSP-trees are prebuilt for static geometry. Why are they unsuitable for dynamic objects, and what replaced them?
• Euler's formula V - E + F = 2 holds for a sphere but gives chi = 0 for a torus. Why are the sphere and torus fundamentally different from a geometric perspective?

Связанные уроки

• la-06-transformations