[Numerical Analysis] 6. Rendering

Rendering

 

Rendering Curves

- Evaluate $p(u)$ for serveral values of $u$, and draw line segments between these points.

- The finer the divisions of the curve (the more values of $u$), the better the rendering will look.

- For efficiency : $p(u) = c_0 + uc_1 + u^2 c_2 + u^3c_3 = c_0 + u(c_1 + u(c_2 uc_3))$

- Smaller number of point in flat curve

 

Subdivision of ezier Curves

- Divide a curve into 2 halves ($l(u)$ & $r(u)$)

- Find $l_0, l_1, l_2, l_3$ and $r_0, r_1,r_2,r_3$ -> points

- Recursively draw $l(u)$ and $r(u)$

 

- When to Stop?

    - Divide until the curve is flat or close to flat

        - Measure how far $l_1$ and $l_2$ are from the line between $l_0$ and $l_3$. When this is below a threshold, stop dividing.

 

- Compute new control points for each half curve :

    - $p_0 = l_0$, $p_3 = r_3$, $p(\frac{1}{2}) = l_3 = r_0$

    - $l_1$, $r_2$ : magnitude of derivative is half, and direction is same.

    - $l(0) = l_0 = p_0 = p(0)$

    - $l(1) = l_3 = p(\frac{1}{2})$

    - $l'(0) = 3(l_1 - l_0) = \frac{1}{2}p'(0)$

    - $l'(1) = 3(l_3 - l_2) = \frac{1}{2}p'(\frac{1}{2})$

    - Solve algebraically for $l_0, l_1, l_2, l_3$

    - Similarly solve for $r_0, r_1, r_2, r_3$

 

- Geometric method

    - $p_0=l_0$

    - $p_3 = r_3$

    - $l_1 = \frac{1}{2}(p_0 + p_1)$

    - $l_2 = \frac{1}{2} ( l_1 + \frac{p_1+p_2}{2})$

    - $l_3 = r_0 = \frac{1}{2}(l_2 + r_1)

    - $r_2 = \frac{1}{2}(p_2 + p_3)$

    - $r_1 = \frac{1}{2}(r_2 + \frac{p_1 + p_2}{2})$

 

Subdividing Other Curves

    - Calculations more complex

    - Transform control points to obtain identical curve as Bezier curve

    - Use the Bezier recursive subdivision algorithm

 

- Converting to a Bezier curve : Suppose the curve is given by : $p(u) = u^TMp$

- We can find Bezier control points, $q$ : $p(u) = u^TM_B q$

- it follows that : $q = M_B^{-1}Mp$

 

Subdividing Other Curves : Example

- Interpolation to Bezier 

$$M_B^{-1}M_I = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -\frac{5}{6} & 3 & -\frac{3}{2} & \frac{1}{3} \\ \frac{1}{3} & -\frac{3}{2} & 3 & \frac{5}{6} \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$$

- B-Spline to Bezier

$$M_B^{-1}M_S =  \frac{1}{6}\begin{bmatrix} 1 & 4 & 1 & 0 \\ 0 & 4 & 2 & 0 \\ 0 & 2 & 4 & 0 \\ 0 & 1 & 4 & 1 \\ \end{bmatrix}$$

 

Subdivision of Surfaces

1. Hold $u$ constant at $u = 0, 1/3, 2/3, 1$ subdivide the 4 curves in the $v$ direction.

2. Holde $v$ constant at $v=0,1/3,2/3,1$  for each of 8 half curves generated in 1. Subdivide the 8 curves in the $u$ direction.

3. Divide the surface into 4 patches (one of each quadrant) and repeat for each of the 4 patches.

4. When done dividing, render with GL_QUADS