Computer Graphics (old course)

The classes that implement the Shape interface (such as Line2D, Rectangle2D, Ellipse2D, Arc2D) are defined in the package java.awt.geom. The Shape interface itself is in java.awt.

A normalized device coordinate (NDC) space, typically $[0,1]\times[0,1]$, is used as an intermediate step so that the window-to-viewport mapping becomes device independent. The same picture is first mapped to the normalized space and then to the specific device coordinates, so the application does not depend on the resolution or size of each device, and only one mapping per device is needed.

Scaling by $s_x, s_y, s_z$ about an arbitrary point $(x_f, y_f, z_f)$ is: translate the point to the origin, scale, then translate back.

$M = T(x_f,y_f,z_f)\cdot S(s_x,s_y,s_z)\cdot T(-x_f,-y_f,-z_f)$

$M=\begin{bmatrix} s_x & 0 & 0 & x_f(1-s_x)\\ 0 & s_y & 0 & y_f(1-s_y)\\ 0 & 0 & s_z & z_f(1-s_z)\\ 0&0&0&1\end{bmatrix}$

Graphics2D g2 = (Graphics2D) g;
g2.setStroke(new BasicStroke(2));   // line thickness = 2
g2.drawLine(50, 50, 200, 100);

BasicStroke(2) sets the line width to 2 pixels, and it is placed in the paint/paintComponent method.

A machine-independent graphical language (such as OpenGL, GKS or PHIGS) provides a standard set of commands for drawing, independent of the hardware. It helps programmers because:

• the same program runs on different devices and platforms without rewriting (portability);
• they need not know the details of the display hardware or drivers;
• development is faster, with a simpler and higher-level programming interface;
• programs are easier to maintain and to upgrade to new hardware.

Simulation is the modelling of a real or imagined system's behaviour over time on a computer, and virtual reality (VR) is an immersive, interactive 3D environment. VR is built on simulation: the simulated model supplies the behaviour, physics and responses of the virtual world, and VR provides the immersive interface (head-mounted display, sensors) through which the user experiences and interacts with it in real time. Examples are flight simulators and surgery training.

Intensity attenuation is the decrease in the intensity of light as it travels from the light source to a surface. For a point source it is commonly modelled as $f(d)=\dfrac{1}{a_0+a_1 d+a_2 d^2}$, where $d$ is the distance from the source, so the farther an object is from the source, the dimmer it appears. It gives depth cues to the rendered scene.

Number of frames:

$15\ \text{fps}\times 4\times 60\ \text{s} = 3600\ \text{frames}$

Size:

$3600\times 64 = 230400\ \text{bits} = 28800\ \text{bytes} \approx 28.1\ \text{KB}$

The A-buffer (accumulation buffer, an extension of the Z-buffer) is used when transparent or translucent surfaces, or anti-aliasing of edges, must be handled. The Z-buffer stores only one depth and colour per pixel, so it handles only opaque surfaces, while the A-buffer keeps a linked list of surface data for each pixel and can combine the colours of several overlapping surfaces.

Midpoint circle algorithm (radius $r=8$, centre $(x_c,y_c)=(4,2)$)

Start at $(0,r)=(0,8)$ with decision parameter $p_0 = 1 - r = -7$. For each step $x_{k+1}=x_k+1$ and:

• if $p_k<0$: next point $(x_k+1,\,y_k)$ and $p_{k+1}=p_k+2x_{k+1}+1$
• else: next point $(x_k+1,\,y_k-1)$ and $p_{k+1}=p_k+2x_{k+1}+1-2y_{k+1}$

Stop when $x\ge y$. The remaining octants come from symmetry: each computed $(x,y)$ gives $(\pm x,\pm y)$ and $(\pm y,\pm x)$, which are then shifted by $(4,2)$.

Java program

import javax.swing.*;
import java.awt.*;

public class MidpointCircle extends JPanel {
    int xc = 4, yc = 2, r = 8;
    int scale = 20;                       // magnify so pixels are visible

    void plot(Graphics g, int x, int y) {
        // origin shifted to the middle of the panel, y axis pointing up
        int px = 200 + x * scale, py = 200 - y * scale;
        g.fillRect(px, py, scale / 2, scale / 2);
    }

    void plot8(Graphics g, int x, int y) {
        plot(g, xc + x, yc + y); plot(g, xc - x, yc + y);
        plot(g, xc + x, yc - y); plot(g, xc - x, yc - y);
        plot(g, xc + y, yc + x); plot(g, xc - y, yc + x);
        plot(g, xc + y, yc - x); plot(g, xc - y, yc - x);
    }

    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        g.setColor(Color.BLUE);
        int x = 0, y = r, p = 1 - r;
        plot8(g, x, y);
        while (x < y) {
            x++;
            if (p < 0) {
                p += 2 * x + 1;
            } else {
                y--;
                p += 2 * x + 1 - 2 * y;
            }
            plot8(g, x, y);
        }
    }

    public static void main(String[] args) {
        JFrame f = new JFrame("Midpoint Circle");
        f.add(new MidpointCircle());
        f.setSize(420, 440);
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.setVisible(true);
    }
}

Using homogeneous coordinates, the combined matrix is $M = R\cdot S_{(2,3)}\cdot F$ (applied right to left).

(a) Reflection about $y=5$. Translate down by 5, reflect about the x-axis, translate back:

$F = T(0,5)\,\text{Ref}_x\,T(0,-5)=\begin{bmatrix}1&0&0\\0&-1&10\\0&0&1\end{bmatrix}$

so $(x,y)\to(x,\,10-y)$:

$P(1,2)\to(1,8)$, $Q(1,6)\to(1,4)$, $R(9,6)\to(9,4)$, $S(9,2)\to(9,8)$.

(b) Scaling by $(s_x,s_y)=(4,2)$ about $(2,3)$:

$S=T(2,3)\,\text{Scale}(4,2)\,T(-2,-3)=\begin{bmatrix}4&0&-6\\0&2&-3\\0&0&1\end{bmatrix}$

i.e. $x'=4x-6,\; y'=2y-3$:

$P\to(-2,13)$, $Q\to(-2,5)$, $R\to(30,5)$, $S\to(30,13)$.

(c) Rotation by $+45^\circ$ about the origin:

$R=\begin{bmatrix}\cos45^\circ&-\sin45^\circ&0\\ \sin45^\circ&\cos45^\circ&0\\0&0&1\end{bmatrix}=\begin{bmatrix}0.7071&-0.7071&0\\0.7071&0.7071&0\\0&0&1\end{bmatrix}$

with $x''=0.7071(x'-y')$ and $y''=0.7071(x'+y')$.

• $P'(-2,13)$: $x''=0.7071(-15)=-10.61$, $y''=0.7071(11)=7.78$
• $Q'(-2,5)$: $x''=0.7071(-7)=-4.95$, $y''=0.7071(3)=2.12$
• $R'(30,5)$: $x''=0.7071(25)=17.68$, $y''=0.7071(35)=24.75$
• $S'(30,13)$: $x''=0.7071(17)=12.02$, $y''=0.7071(43)=30.41$

Combined matrix

$M=R\,S\,F=\begin{bmatrix}2.828&1.414&-16.263\\2.828&-1.414&7.778\\0&0&1\end{bmatrix}$

Transformed rectangle: $P''(-10.61,\,7.78)$, $Q''(-4.95,\,2.12)$, $R''(17.68,\,24.75)$, $S''(12.02,\,30.41)$.

Projection maps 3D points onto a 2D view plane.

Parallel (orthographic) projection

Projectors are parallel to each other. For projection onto the plane $z=0$ along the z-axis, a point $(x,y,z)$ goes to $(x_p,y_p)=(x,y)$, and the z coordinate is dropped:

$\begin{bmatrix}x_p\\y_p\\z_p\\1\end{bmatrix}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&0\\0&0&0&1\end{bmatrix}\begin{bmatrix}x\\y\\z\\1\end{bmatrix}$

For an oblique parallel projection with projector direction making angle $\alpha$ and length factor $L$ with the plane, $x_p=x+zL\cos\alpha$, $y_p=y+zL\sin\alpha$:

$M_{oblique}=\begin{bmatrix}1&0&L\cos\alpha&0\\0&1&L\sin\alpha&0\\0&0&0&0\\0&0&0&1\end{bmatrix}$

Parallel projection preserves relative dimensions and parallel lines, so it is used in engineering drawings.

Perspective projection

Projectors meet at the centre of projection. Put the centre at the origin and the view plane at $z=d$. By similar triangles:

$\frac{x_p}{d}=\frac{x}{z},\qquad \frac{y_p}{d}=\frac{y}{z}\;\Rightarrow\; x_p=\frac{x\,d}{z}=\frac{x}{z/d},\quad y_p=\frac{y\,d}{z}=\frac{y}{z/d}$

In homogeneous form with $h=z/d$:

$\begin{bmatrix}x_h\\y_h\\z_h\\h\end{bmatrix}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&1/d&0\end{bmatrix}\begin{bmatrix}x\\y\\z\\1\end{bmatrix}$

Dividing by $h$ gives $(x_p,y_p,z_p)=\left(\dfrac{x d}{z},\dfrac{y d}{z},d\right)$.

Distant objects appear smaller (perspective foreshortening), so the result looks realistic but does not preserve sizes or parallelism.

Endpoints $A(1,9)$ and $B(6,1)$.

$\Delta x = 5$, $\Delta y = |1-9| = 8$. Since $\Delta y>\Delta x$ the line is steep (slope $-8/5$, negative), so we step in $y$ (decreasing by 1 each time) and decide whether to increment $x$.

Initial decision parameter: $p_0 = 2\Delta x-\Delta y = 10-8 = 2$.

Rule at each step ($y$ decreases by 1):

• if $p_k<0$: $x$ unchanged, $p_{k+1}=p_k+2\Delta x = p_k+10$
• if $p_k\ge0$: $x$ increases by 1, $p_{k+1}=p_k+2\Delta x-2\Delta y=p_k-6$

Digitized pixels: (1,9), (2,8), (2,7), (3,6), (4,5), (4,4), (5,3), (5,2), (6,1). The last pixel equals $B$, confirming the result.

Clip window: $x_{min}=10,\;x_{max}=20,\;y_{min}=10,\;y_{max}=20$. Polygon vertices in order: $P(-10,-20)$, $Q(10,60)$, $R(0,10)$, $S(10,10)$.

Sutherland-Hodgeman clips the polygon against each window edge in turn (left, right, bottom, top). A point is inside the left edge if $x\ge10$. For each polygon edge $(V_1\to V_2)$: in-in outputs $V_2$; in-out outputs the intersection; out-out outputs nothing; out-in outputs the intersection and $V_2$.

1. Left edge ($x=10$)

• $P\to Q$ (out to in): intersection with $x=10$ is $(10,60)$; output $(10,60)$, $Q(10,60)$
• $Q\to R$ (in to out): intersection $(10,60)$
• $R\to S$ (out to in): intersection $(10,10)$; output $(10,10)$, $S(10,10)$
• $S\to P$ (in to out): intersection $(10,10)$

After removing duplicates the list is $(10,60),(10,10)$.

2. Right edge ($x=20$): both points have $x=10\le20$, so both are inside and the list is unchanged.

3. Bottom edge ($y=10$): $y=60$ and $y=10$ are both $\ge10$, so the list is unchanged.

4. Top edge ($y=20$): $(10,60)$ is outside and $(10,10)$ is inside.

• $(10,60)\to(10,10)$ (out to in): intersection $(10,20)$, then $(10,10)$
• $(10,10)\to(10,60)$ (in to out): intersection $(10,20)$

Result: the polygon lies entirely on or outside the left boundary, so only a degenerate (zero-area) portion remains: the vertices $(10,20)$ and $(10,10)$, i.e. the line segment along the left window edge $x=10$ from $(10,10)$ to $(10,20)$. No area of the polygon is visible inside the window.

Visible surface detection (hidden surface removal) is the process of deciding which surfaces or parts of surfaces of 3D objects are visible from a given viewpoint, so that only those are displayed and hidden ones are removed. It gives a realistic image in which nearer objects block farther ones. Methods are of two kinds: object-space (e.g. back-face detection, painter's algorithm) and image-space (e.g. z-buffer, scan-line).

Comparison of scan-line and painter's algorithm

A lighting (illumination) model is a mathematical model that calculates the intensity (colour) of light at a point on a surface from the light sources, surface properties (reflectivity, texture, orientation) and the viewer's position. Typical components are ambient light, diffuse reflection, $I_d=k_dI_l\cos\theta=k_dI_l(\mathbf N\cdot\mathbf L)$, and specular reflection, $I_s=k_sI_l(\mathbf R\cdot\mathbf V)^{n}$ (Phong model). A surface-rendering (shading) method then applies the model to polygon surfaces.

Constant (flat) shading procedure

1. Take each polygon of the object and find its surface normal $\mathbf N$ from the vertex coordinates (cross product of two edges).
2. Evaluate the lighting model once for the polygon, using $\mathbf N$, the light direction $\mathbf L$ and view direction $\mathbf V$, to get one intensity value.
3. Fill the entire polygon (all its pixels) with that single intensity.
4. Repeat for every polygon.

It assumes the light source and viewer are far away, so $\mathbf N\cdot\mathbf L$ and $\mathbf V\cdot\mathbf R$ are constant over the polygon.

Applications

• Fast preview and wireframe/solid rendering where speed matters more than quality
• Rendering flat-faced objects such as buildings and boxes
• Real-time systems and games with low-polygon models
• Approximating curved surfaces coarsely (visible facets and Mach bands are the drawback)