Computer Graphics

Geometry and Intersection

Representing surfaces and finding where a ray meets them.

Colour is the family; a dashed line is the second member of it.

Drag to pan · scroll to zoom · click a node to open it
G bump-mapping Bump Mapping displacement-mapping Displacement Mapping bump-mapping->displacement-mapping perturbs normals only; silhouettes stay flat bvh Bounding Volume Hierarchy whitted-ray-tracing Whitted Ray Tracing bvh->whitted-ray-tracing testing every primitive per ray is linear in scene size catmull-clark Catmull-Clark Subdivision subdivision-surfaces Subdivision Surfaces catmull-clark->subdivision-surfaces bicubic B-splines extended to arbitrary quad meshes texture-mapping Texture Mapping displacement-mapping->texture-mapping the texture moves geometry rather than shading it dual-contouring Dual Contouring marching-cubes Marching Cubes dual-contouring->marching-cubes corner sign tables cannot reproduce sharp edges kd-tree kd-Tree kd-tree->bvh splits space, not objects, so nodes never overlap lbvh Linear BVH surface-area-heuristic Surface Area Heuristic lbvh->surface-area-heuristic Morton order instead of a cost-driven split search level-of-detail Level of Detail rasterization Rasterization level-of-detail->rasterization distant meshes otherwise cost far more than they show loop-subdivision Loop Subdivision loop-subdivision->subdivision-surfaces box splines over triangles rather than quads sphere-tracing Sphere Tracing marching-cubes->sphere-tracing converts the field to triangles instead of tracing it meshlets Meshlets and Mesh Shaders meshlets->rasterization culls per cluster instead of per triangle or per object simt SIMT meshlets->simt a cluster is sized to one workgroup's registers moller-trumbore Moller-Trumbore Intersection ray-triangle-intersection Ray-Triangle Intersection moller-trumbore->ray-triangle-intersection barycentric solve with nothing precomputed normal-mapping Normal Mapping normal-mapping->bump-mapping stores the normal itself rather than a height parallax-occlusion-mapping Parallax Occlusion Mapping parallax-occlusion-mapping->normal-mapping perturbed normals give no parallax or self-occlusion polygon-mesh Polygon Mesh surface-representation Surface Representation polygon-mesh->surface-representation rasterization->polygon-mesh it fills projected primitives, not implicit surfaces z-buffer Z-Buffer rasterization->z-buffer per-pixel depth is what makes visibility local ray-triangle-intersection->polygon-mesh the primitive being intersected signed-distance-field Signed Distance Field signed-distance-field->surface-representation sphere-tracing->signed-distance-field the step length is the distance value itself subdivision-surfaces->surface-representation surface-area-heuristic->bvh median splits ignore the actual cost of traversal texture-mapping->polygon-mesh needs a surface parameterization to index into virtual-geometry Virtualized Geometry virtual-geometry->level-of-detail discrete per-object LOD pops and cannot stream virtual-geometry->meshlets the cut through the hierarchy is expressed as clusters watertight-ray-triangle Watertight Ray- Triangle Intersection watertight-ray-triangle->moller-trumbore rounding lets rays leak through shared edges

25 nodes

Texture Mapping

Assigns surface parameters from an image indexed by per-vertex coordinates, decoupling material detail from geometric density. · 1974

Bump Mapping

Perturbs the shading normal from a height texture without moving any geometry. Almost free, and its limits are visible the moment a silhouette or a s… · 1978

Catmull-Clark Subdivision

Generalizes bicubic B-spline refinement to meshes of arbitrary topology. The standard modelling surface in film, and the reason quad topology is the… · 1978

Displacement Mapping

Moves surface points along the normal by a stored height, producing detail that occludes itself and changes the silhouette because the geometry reall… · 1984

Loop Subdivision

The triangle counterpart of Catmull-Clark, built on box splines, for pipelines whose base meshes are triangular rather than quad. · 1987

Marching Cubes

Extracts a triangle mesh from a scalar field by table lookup on the sign pattern at each cell's corners. The reason volume data can be handed to ordi… · 1987

Surface Area Heuristic

Chooses each split by estimating traversal cost from the probability a random ray hits each child, which is proportional to its surface area. Still t… · 1990

Sphere Tracing

Marches along a ray by exactly the distance value at each point, which can never overshoot the surface. Renders implicit geometry without ever tessel… · 1996

Moller-Trumbore Intersection

Solves for barycentric coordinates directly with a scalar triple product, needing no precomputed plane equation and therefore no per- triangle storag… · 1997

Dual Contouring

Places one vertex per cell by solving a least-squares fit to the surface normals it intersects, which lets it reproduce sharp creases that corner-sig… · 2002

Parallax Occlusion Mapping

Ray-marches the height field in tangent space so texture features shift with view angle and occlude each other, recovering the parallax that normals… · 2006

Linear BVH

Sorts primitives along a Morton curve and builds the hierarchy from the resulting bit patterns, which parallelizes perfectly and rebuilds in millisec… · 2012

Watertight Ray-Triangle Intersection

Reorders the arithmetic so that a ray crossing an edge shared by two triangles is guaranteed to hit exactly one of them, closing the pinhole leaks th… · 2013

Virtualized Geometry

Builds a hierarchy of pre-simplified clusters and chooses the cut through it per frame, so level of detail changes per cluster and streams from disk… · 2021

Bounding Volume Hierarchy

A tree of nested bounding boxes over primitives. Handles unevenly distributed geometry gracefully, refits cheaply under animation, and is what ray tr…

kd-Tree

Recursively splits space rather than objects with axis-aligned planes. Nodes never overlap, which makes traversal tight, but primitives straddling a…

Level of Detail

Swaps in coarser geometry as an object shrinks on screen, keeping triangle density roughly constant in screen space.

Meshlets and Mesh Shaders

Splits a mesh into small vertex-and-triangle clusters that can be culled and dispatched independently, replacing the fixed vertex-fetch pipeline with…

Normal Mapping

Stores the perturbed normal directly in a tangent-space texture instead of deriving it from height differences, which removes the derivative computat…

Polygon Mesh

Vertices, edges and faces. Explicit, cheap to rasterize and to intersect, and the representation essentially all hardware is built around.

Rasterization

Projects primitives to the screen and fills the pixels they cover. Cost scales with primitives times coverage, and visibility comes free from a depth…

Ray-Triangle Intersection

The innermost operation of every ray tracer, so constant factors and numerical robustness here dominate both performance and correctness.

Signed Distance Field

Stores distance to the nearest surface, negative inside. Booleans, offsets and blends become arithmetic on the field, and the distance value itself i…

Subdivision Surfaces

Defines a smooth limit surface as the result of infinitely refining a control mesh, giving a single representation that is both editable at low resol…

Surface Representation

How a surface is stored before anything is rendered: explicitly as primitives, or implicitly as a function whose zero set is the surface.