A from-scratch implementation of the assignments of USTC "Computer Graphics" (计算机图形学) by Prof. Ligang Liu (刘利刚), covering digital image processing, discrete geometry processing, and physically-based rendering — part of a csdiy.wiki full-catalog build.
The course walks from 2D image editing through the core of discrete differential
geometry to rendering. Every algorithm here is implemented from scratch in
Python (numpy/scipy/PIL) — no graphics libraries, no OpenGL, no mesh toolkits.
All inputs (test images and meshes) are generated procedurally so the repo is
fully self-contained and reproducible, and every assignment writes a real
result image / mesh into results/.
Everything runs on the CPU (this machine has no GPU): the rasterizer, the path tracer and all the sparse-linear-system solves are software. The one inherently interactive/GPU part of the original course — the real-time OpenGL handle-dragging UI — is realized here as verified offline solves that produce the same deformation/parameterization results as static renders (see Partials).
| # | Assignment | What it does | Measured result |
|---|---|---|---|
| a1 | Image Warping (IDW / RBF) | smooth planar deformation from control points | anchor interpolation error 0 (IDW) / 2e-11 px (RBF thin-plate) |
| a2 | Poisson Image Editing | seamless cloning via a sparse Poisson solve | seam gradient energy 13.12 → 0.12 (≈100× smoother) |
| a3 | Minimal Surface | zero-mean-curvature soap film, fixed boundary | area 20.60 → 5.40 (−73.8%), monotone |
| a4 | Tutte / Harmonic Parameterization | flatten a disk to the plane | 0 flips; cotan distortion 0.652 < uniform 0.694 |
| a5 | ARAP Parameterization (Liu 2008) | local/global low-distortion flattening | ARAP energy 1.48 → 0.15; isometric distortion −89.7% vs harmonic |
| a6 | ARAP Surface Deformation (Sorkine-Alexa) | handle-driven rigid deformation | edge-length error 6.3% (ARAP) vs 16.0% (naive Laplacian) |
| a7 | Mesh Simplification (QEM) | Garland-Heckbert quadric edge collapse | 5120 → 408 faces at 1.9% mean-vertex error |
| a8 | Software Rasterizer | z-buffer + Blinn-Phong scene | 5458 triangles, correct depth occlusion |
| a9 | Path Tracer (final) | Monte-Carlo Cornell box, global illumination | 256×256, 400 spp — colour bleeding + soft shadows + mirror |
Path tracing — Cornell box (final project). Global illumination with next-event estimation: soft shadows, colour bleeding from the red/green walls, and a mirror sphere reflecting the scene.
ARAP surface deformation. Rest tube → naive Laplacian (collapses, middle) → ARAP (preserves the circular cross-section, right).
Poisson image editing. Naive paste (visible seam, left) → seamless clone (middle) → mixed gradients (right).
Image warping. Input with control points → IDW → RBF thin-plate.
Minimal surface. Noisy input patch → discrete minimal surface spanning a non-planar boundary.
Mesh simplification (QEM). 5120 → 1280 → 408 faces, shape preserved.
Tutte / ARAP parameterization (checkerboard pulled back onto the surface):
| Tutte (harmonic) | ARAP (low distortion) |
|---|---|
 |
 |
Software rasterizer — shaded scene and its z-buffer (depth):
- a1 — Image Warping: IDW (per-anchor local affine, weighted LS) and RBF thin-plate splines, exact anchor interpolation, backward-mapped resampling.
- a2 — Poisson Image Editing: seamless cloning + mixed gradients as one sparse linear system per colour channel.
- a3 — Minimal Surface: iterated cotangent-Laplace solve (fixed boundary) to a discrete zero-mean-curvature surface; plus explicit umbrella flow.
- a4 — Tutte / Harmonic Parameterization: convex boundary + uniform (Tutte, bijective) and cotangent (harmonic) interior solves.
- a5 — ARAP Parameterization: Liu et al. 2008 local/global block descent (per-triangle SVD rotation + cotangent-Laplace global step).
- a6 — ARAP Surface Deformation: Sorkine & Alexa 2007 handle-constrained as-rigid-as-possible modeling, compared to naive Laplacian editing.
- a7 — Mesh Simplification: Garland-Heckbert quadric error metrics with a lazy min-heap of edge collapses.
- a8 — Software Rasterizer: full CPU pipeline — matrices, clipping, barycentric scan conversion, z-buffer, Blinn-Phong.
- a9 — Path Tracer (final): vectorised Monte-Carlo path tracing of a Cornell box with Lambertian + mirror materials, area light, NEE, Russian roulette, Reinhard tone-mapping.
ustc-cg/
├── src/ustc_cg/
│ ├── mesh.py # OBJ IO, procedural mesh generators, cotangent Laplacian,
│ │ # boundary loops, adjacency, normals
│ └── render.py # CPU software rasterizer (z-buffer, Blinn-Phong, UV, depth)
├── assignments/
│ ├── a1_image_warping.py a6_arap_deformation.py
│ ├── a2_poisson_editing.py a7_mesh_simplification.py
│ ├── a3_minimal_surface.py a8_rasterizer.py
│ ├── a4_tutte_parameterization.py a9_path_tracer.py
│ └── a5_arap_parameterization.py
├── tests/test_smoke.py # pytest correctness checks (bijectivity, area decrease, …)
├── results/ # committed figures + .obj outputs (the evidence)
├── run_all.py # regenerate every figure
└── requirements.txt
# Python 3.11 with numpy, scipy, Pillow, matplotlib
pip install -r requirements.txt
# regenerate every figure in results/ (path tracer at 200 spp)
python run_all.py
# quick pass (path tracer 64 spp, smaller image)
python run_all.py --fast
# or run one assignment:
python assignments/a2_poisson_editing.py
python assignments/a9_path_tracer.py 256 400 # <resolution> <samples-per-pixel>
# correctness tests (~14 s):
python -m pytest tests/ -q- Unit tests (
tests/test_smoke.py, 7 passing): Tutte embedding has 0 flipped triangles (bijectivity), the cotangent Laplacian has the constant null-space, the icosphere satisfies Euler's formula V−E+F=2, warps interpolate their anchors, QEM reduces face count while keeping valid triangles, and the minimal-surface area decreases monotonically. - Measured evidence: every assignment prints and commits real numbers (table
above) and writes its output image/mesh to
results/. Key checks: Poisson seam energy drops ~100×; ARAP parameterization cuts isometric distortion 89.7%; ARAP deformation preserves edge lengths 2.5× better than naive Laplacian; QEM holds error under 2% of the bounding-box diagonal at 8% of the faces. - Renders are real: the rasterizer depth buffer (
a8_raster_depth.png) confirms correct hidden-surface removal; the path traced Cornell box shows the physically-correct colour bleeding and soft shadows that only a converged GI solver produces.
The original course ships a Qt/OpenGL application (MiniMesh/MiniDraw) for
interactive handle dragging and real-time shading. This machine is CPU-only
with no display/GPU, so the interactive real-time harness is not reproduced;
instead every underlying algorithm is implemented and verified as an offline
solve that produces the identical result (the deformation/parameterization
maths is the same — only the UI event loop differs). All numerical cores,
images and meshes above are genuine, not mocked.
Python 3.11 · numpy · scipy (sparse, sparse.linalg, spatial.cKDTree) ·
Pillow · matplotlib. No GPU, no OpenGL, no external mesh/geometry libraries.
- The Laplacian is everywhere. The same cotangent-Laplace operator drives minimal surfaces, harmonic parameterization, and the global step of both ARAP algorithms — geometry processing is largely "assemble the right sparse system".
- Local/global (ARAP) optimization: alternating per-element SVD rotations with a single global linear solve is a remarkably effective, monotone way to minimize non-linear as-rigid-as-possible energies.
- Quadric error metrics turn "how much does this edge collapse cost?" into a 4×4 quadratic form, giving near-optimal, curvature-adaptive simplification.
- Poisson editing reframes compositing as "match gradients, fix the boundary" — a Dirichlet problem solved with one sparse system.
- Path tracing is the rendering equation as a recursive Monte-Carlo integral; next-event estimation and importance sampling are what make it converge on a CPU.
Based on the assignments of "Computer Graphics" (计算机图形学) by Prof. Ligang Liu (刘利刚), University of Science and Technology of China — course page, official framework. This repository is an independent educational reimplementation; all course materials and specifications belong to their original authors. Original code here is released under the MIT License.