Advanced Computer Graphics 2 Taught by [[Xin Li]] ## Syllabus ![[CS350_Syllabus-Spring-2026.pdf]] What is this class *not* about: - Surface Details - Graphics API - GPU Programming - Physically Based Modelling ## Course Overciew ### Learning Objectives - Theory & Practices on Data Structures & Operations to represent & process geometric data for Intersection & Collision Detection in Area Search, occlusion, culling, overlapping, - Applications: - Games - Simulation - Robotics - CAD - VLSI - *etc* ### Topics - [[Geometric Primitive|Geometric Primitives]] - [[Bounding Volume|Bounding Volumes]] - [[Spatial Partitioning]] - [[Data Structure]] - Casting / Culling / Searching / Queries (Basic Operations) - Intersections / Collision Detection ### Emphasis 1. Efficiency (speed) 2. Efficiency (memory use) 3. Efficiency (design, implementation, debugging, something else idk) ### Examples - Collision Detection - [[Euler Characteristic]] >[!info] the worm used to be an Oiler Character >![[Pasted image 20260107165723.png]] $\huge \begin{align} F&=E-N+2 \\ F &= \underbrace{f(n)}_{\text{Linear}} \\ E &: \text{Linearly bounded by } n \\ \frac{3}{2} n &\leq E \leq 3n-6 \\ 🏒 & 🥅 \end{align} $ If all [[Triangular Mesh|triangular faces]], $\huge E = 3n-6 $ $\huge \begin{align} F &= 3n-6 -n + 2 \\ &= 2n-4 \end{align} $ - Naive Aproach to collision detection : $\mathcal O(n^{2})$ - Can we do $\mathcal O(n \ln n )$? $\mathcal O(n)$? $\mathcal O(0)$? >[!tip]- > poker doesnt need collision this class is useless - Area Search: $\mathcal O(n), \mathcal O(\ln n)$, K-d Tree ### Combined Approaches - Space Subdivisions -> BoundingVolumes -> Geometric Level - Quick Culling >95% ## Tentative Topics 1. Simple Geometric Primitives - [[Point]], [[Planes|Plane]], [[Triangle]], [[Axis Aligned Bounding Box|AABB]], [[Sphere]], [[Ray]], [[Frustum]] - Data Structures & Operations 2. Basic [[Bounding Volume]] 3. Simple [[Spatial Partitioning]] - [[Uniform Grids]], [[H-Grids]], Hybrid Aproach - Operations (casting / queries) 4. [[AABB Tree|AABB Trees]] - Static & Dynamic - Construction, maintenance 5. BSP Trees - Construction (partition, storage, poly_split) - operations...; - Constructive Solid Geometry (*CSG*) 6. Other Spatial Partition Trees - K-d Trees, Quad Tree, Oct Tree 7. GJK Algorithm - Preliminaries (polytopes, voronoi regions, simplices, [[Barycentric Coordinates]], ...) - Voronoi Test - GJK + Minkowski Diff 8. Maybe: - SAT - NPR - EPA ## Notation ### Point / Vector [[Point]] / [[Vector]] will be represented as a triplet of numbers $(x,y,z)$. A [[Point]] will always be a capitilized letter ($\vec P$) In C++ we will represent as if it is defined: ```cpp struct vector { float x, y, z; }; ``` ### [[Plane]] #### Explicit Form $\huge \begin{align} \hat n \cdot \pa{\vec p - \vec p_{0}} &= 0\\ \hat{n} \cdot \vec p - \hat{n} \cdot \vec p_{0} &= 0\\ \hat{n} \cdot \vec p = \hat{n} \cdot \vec p_{0} \end{align} $ Where $\hat{n}=\braket{a,b,c}$,$|\hat n|=1$, $\vec p_{0}$ is the 'origin' of the plane, and $\vec p$ is any point on the plane #### Implicit Form $\huge \begin{align} ax+by+cz - d &= 0 \\ \end{align}$ $d$ is the [[Geodesic]] of the plane. $\huge d = \vec n \cdot \vec p_{0} $ #### [[Parametric Function|Parametric Form]] $\huge \begin{align} \vec p &= \vec p_{0} + s\vec q + t \vec r \end{align}$ Where: $\huge \begin{align} s,r &\in \R \\ \vec q, \vec r &\in \R^{3} \\ \vec q \times \vec r &\parallel \vec n \end{align} $ $\vec q, \vec r$ are vectors that [[Span|span]] the plane. #### Structure ```cpp struct plane { vector4 mData; }; ``` or ```cpp struct plane { vector3 mNormal; // \vec n vector3 mPoint; // \vec p_0 }; ``` ### [[Triangle]] #### Structure ```cpp struct Triangle { vector3 mP0, mP1, mP2; }; ``` ### [[Axis Aligned Bounding Box|AABB]] $\huge \vec \min, \vec \max $ ```cpp struct AABB { vector3 mMin, mMax; }; ``` or ```cpp struct AABB { vector3 mCenter, mExt; // center & extents/size }; ``` ### [[Sphere]] $\huge \begin{align} (x-x_{0})^{2} + (y-y_{0})^{2} + (z-z_{0})^{2} = r^{2}\\ \end{align} $ Where $\vec c_{S} = (x_{0},y_{0},z_{0})$ is the center of the sphere. $\huge (\vec c_{s} - \vec p) \cdot (\vec c_{s}-\vec p) = r^{2} $ ```cpp struct Sphere { vector3 mCenter; float radius; }; ``` $\huge \op{sphere} = \ba{ \vec c_{s}, r } $ ### [[Ray]] $\huge \vec p = \vec S_{r} + t\hat d $ Where $\vec p$ is any point in the ray. ```cpp struct Ray { vector3 mStart, mDirection; }; ``` $\huge \op{Ray} = [\vec s_{r}, \vec d] $ ### [[Frustum]] ```cpp struct Frustum { Plane mPlane[6]; }; ``` ```cpp struct Frustum { vector3 vertex[8]; }; ``` Assume all [[Normal Vector|Normal]] of the planes are facing inwards into the frustum.w