Past exam question: 2082 Kartik (Back), Q4
Open in the Padhaiko appIllustrate space partitioning representation in brief. How polygon meshes support to represent 3D object? Explain with relevant figures.
Solution
Space Partitioning Representation: Space partitioning schemes model 3D solid objects by subdividing continuous 3D space containing the object into a collection of contiguous, non-overlapping spatial cells (volumes):
- Spatial-Occupancy Enumeration (Voxel Grids): Space is divided into a regular 3D grid of identical cubes called voxels. Each voxel stores a binary flag (inside or outside the solid) or material density (e.g. in medical CT/MRI imaging).
- Octrees: A hierarchical tree data structure that recursively subdivides 3D bounding cubes into eight octants. A node is classified as:
- Full / Black: Entirely inside the object (leaf node).
- Empty / White: Entirely outside the object (leaf node).
- Partially Full / Gray: Intersects the object boundary; recursively divided into 8 sub-octants.
- Binary Space Partitioning (BSP) Trees: Recursively bisects 3D space using arbitrary planes, organizing polygons into front and back subtrees for fast hidden surface determination and ray tracing.
Polygon Mesh Representation of 3D Objects: A polygon mesh represents the boundary surface of a 3D object using a collection of planar polygonal faces (typically triangles or quadrilaterals) that share edges and vertices:
- Tessellation: Curved surfaces (spheres, cylinders, character models) are approximated as piece-wise planar facets. Finer meshes yield smoother appearances.
- Hardware Compatibility: Modern GPU rasterizers are architected specifically to process and rasterize triangle meshes in parallel.
- Surface Normal and Lighting Support: Normals computed at mesh vertices or face planes enable flat, Gouraud, and Phong shading and texture mapping.
Standard Geometric Data Structure Tables for Polygon Meshes: To avoid redundant storage and maintain topological connectivity, polygon meshes are organized into three linked tables:
- Vertex Table: Stores spatial coordinates for each distinct vertex.
- Edge Table: Stores pointers to the two endpoint vertices of each edge, along with pointers to adjacent faces.
- Polygon (Face) Table: Stores an ordered list of edge (or vertex) pointers bounding each polygonal face.
Example: Triangular Pyramid Mesh (4 Vertices V1..V4, 4 Faces F1..F4)
V1 (Apex)
/\
/ \
/ F1 \
/ \
V2 /________\ V3
\ /
\ F4 /
\ /
\ /
\/ V4
Vertex Table:
V1: (0, 10, 0)
V2: (-5, 0, 5)
V3: (5, 0, 5)
V4: (0, 0, -5)
Edge Table:
E1: V1, V2
E2: V2, V3
E3: V3, V1
E4: V1, V4
E5: V2, V4
E6: V3, V4
Polygon Table:
F1: E1, E2, E3 (Front face)
F2: E1, E5, E4 (Left face)
F3: E3, E4, E6 (Right face)
F4: E2, E6, E5 (Bottom base)Evaluating Plane Equations and Surface Normals: For each planar facet in the polygon table, its plane equation is:
Given three non-collinear vertices in counter-clockwise order when viewed from the outside:
The outward unit normal determines whether the face is front-facing or back-facing, supports back-face culling, and drives illumination equations.
Space partitioning divides 3D space into discrete spatial cells (voxels, octrees, BSP trees) to represent volumetric occupancy. Polygon meshes represent 3D object surfaces via collections of connected planar polygons, organized into vertex, edge, and polygon tables for compact storage, efficient topological traversal, GPU rasterization, and illumination calculations.
All past exam questions for Computer Graphics and Visualization