Enter the third dimension

While attending university in the mid-1980s, I studied computer graphics from both two-dimensional and three-dimensional perspectives. Although I enjoyed playing with 2D graphics, I became fascinated with 3D graphics. This fascination led me to write this installment of Java Fun and Games, which provides an introduction to 3D graphics from the Java perspective. I’ll eventually apply this and future 3D graphics articles to a 3D-based Java game.

This article first introduces you to a Swing component, whose API lets you load/display a 3D model and adjust a 3D model’s viewability. Next, the article introduces you to a Swing applet, whose user interface lets you play with this component. This article concludes by presenting you with a component-based 3D graphics tutorial, which introduces you to 3D graphics fundamentals—starting with coordinate systems and transformations.

A component for 3D graphics

A custom Swing component with a simple API is probably the most convenient tool for introducing 3D graphics to Swing-based applets and applications. To this end, I’ve created a Panel3D class that subclasses javax.swing.JPanel. This 3D panel component provides a four-method API that creates the component, loads a 3D model into the component, displays the model, and adjusts the model’s viewability:

• public Panel3D(int width): creates a 3D panel. Parameter width identifies the number of pixels on each side of the component. The value passed to this parameter establishes the component’s preferred and minimum sizes. I set the component’s minimum size so that the component is never shown smaller than its preferred size.
• public void load(String filename): loads a 3D model from the text file identified by parameter filename, parses the model, stores parsed vertices and edges in the component, and repaints the component to present the model. A java.io.IOException object is thrown if an I/O problem occurs. If a parsing problem occurs, a java.text.ParseException object is thrown.
• public void lookFrom(double x, double y, double z): establishes the viewpoint, or the position from which the 3D model is viewed. The viewpoint’s x, y, and z coordinates are specified by the positive/negative values passed to parameters x, y, and z. The viewpoint always looks toward the model’s (0, 0, 0) origin. This method does not repaint the component.
• public void perspective(double ds): establishes the amount of perspective when viewing the 3D model. Parameter ds represents my textbook’s D/S zoom ratio. A large ratio zooms into the model (a telephoto view). In contrast, a small ratio zooms out of the model (a wide-angle view). This method must be called after lookFrom(); it repaints the component.

To get comfortable with Panel3D‘s methods, consider an example that creates a 3D panel for use in an applet context. This component occupies 60 percent of the applet’s width, loads the contents of a cube.3d model file (included with this article’s code), lets an observer view the model from viewpoint (6.0, 8.0, 7.0), and sets the perspective to halfway between telephoto and wide-angle:

 Panel3D p3d = new Panel3D (getWidth ()*3/5);
p3d.load ("cube.3d");
p3d.lookFrom (6.0, 8.0, 7.0);
p3d.perspective (1.0 / Math.tan (Math.toRadians (45.0)));

Note: You can download this article’s source code from Resources.

The load() method’s parser requires cube.3d‘s contents to agree with my custom model file format. This format recognizes C++ // comments, requires vertex definitions to appear first (one definition per line), and requires edge definitions to appear last (also one definition per line). At least one blank line must separate the last vertex definition from the first edge definition.

Each vertex definition must begin with a label that names the vertex and continue with three space-separated real numbers that (left to right) identify the vertex’s x, y, and z coordinates. Each edge definition must consist of two space-separated vertex names—the name on the left identifies the start vertex. These definitions and the rest of the model file format are illustrated in Listing 1.

Listing 1. cube.3d

 
// cube.3d
A -1  1 -1
B  1  1 -1
C  1 -1 -1
D -1 -1 -1
E -1  1  1
F  1  1  1
G  1 -1  1
H -1 -1  1
A B
B C
C D
D A
E F
F G
G H
H E
A E
B F
C G
D H

Let there be 3D graphics

Before playing with the 3D panel, you must add this component to a Swing-based applet’s or application’s GUI. To save you the bother, I’ve created a Demo3D applet. This applet’s GUI presents the 3D panel, three slider controls for specifying x, y, and z viewpoint values (each value ranges from -50 to 50), another slider control for specifying the perspective, and three buttons for loading prebuilt 3D models. See Figure 1.

Figure 1 reveals that the 3D panel component renders a 3D model as a wire-frame image to simplify the code (including the model file format illustrated in Listing 1) and shorten the article. As a result, the world doesn’t look solid and (depending on the viewpoint’s current setting), optical illusions can arise—I’ll rectify these problems in a future article.

The GUI also reveals that each of the x, y, and z coordinate axes—drawn by Panel3D‘s public void paintComponent(Graphics g) method—has its own color: the x axis is red, the y axis is green, and the z axis is blue. The tiny black dash that appears on one side of each axis identifies the negative half of the axis.

A third GUI item of interest: “Field Of View.” This angle determines how much of a model is viewable and ranges from 0 to 180 degrees. A small angle zooms into the model: you see less model but more detail. In contrast, a large angle zooms out of the model: you see more model but less detail. The field-of-view angle is mapped to ratio D/S, which passes to the perspective() method—I discuss this mapping later.

The Demo3D class’s public void init() method constructs this applet’s GUI. It first invokes the private JPanel buildGUI() method and then adds the returned JPanel to the applet’s content pane. The buildGUI() method, whose code appears below, requires that the applet’s width match its height; otherwise null returns:

 
private JPanel buildGUI ()
{
   // Although I'm ignoring the computer screen's aspect ratio (I don't care
   // if individual pixels aren't square), I want the applet's dimensions to
   // be square.
   int width = getWidth ();
   if (width != getHeight ())
       return null;
   // Create a 3D panel where each side is 60 percent of the applet's width. Set
   // the default viewpoint from which an observer views the scene. Also,
   // set the default perspective to halfway between extreme telephoto and
   // extreme wide-angle.
   final Panel3D p3d = new Panel3D (width*3/5);
   p3d.lookFrom (posX, posY, posZ);
   p3d.perspective (ds);
   // GUI components are stored in the following panel.
   JPanel panel = new JPanel ();
   panel.setLayout (new BorderLayout ());
   // The top panel contains the X and Y slider controls; it also contains
   // the 3D panel.
   JPanel panelTop = new JPanel ();
   // Build the top panel.
   JPanel panelTemp = new JPanel ();
   panelTemp.add (new JLabel ("X"));
   final JSlider sliderX = new JSlider (JSlider.VERTICAL, MINX, MAXX, DEFX);
   sliderX.setMinorTickSpacing (5);
   sliderX.setMajorTickSpacing (10);
   sliderX.setPaintTicks (true);
   sliderX.setPaintLabels (true);
   sliderX.setLabelTable (sliderX.createStandardLabels (10));
   ChangeListener cl;
   cl = new ChangeListener ()
        {
            public void stateChanged (ChangeEvent e)
            {
               posX = sliderX.getValue ();
               p3d.lookFrom (posX, posY, posZ);
               p3d.perspective (ds);
            }
        };
   sliderX.addChangeListener (cl);
   panelTemp.add (sliderX);
   panelTop.add (panelTemp);
   panelTemp = new JPanel ();
   panelTemp.add (p3d);
   panelTop.add (panelTemp);
   panelTemp = new JPanel ();
   panelTemp.add (new JLabel ("Y"));
   final JSlider sliderY = new JSlider (JSlider.VERTICAL, MINY, MAXY, DEFY);
   sliderY.setMinorTickSpacing (5);
   sliderY.setMajorTickSpacing (10);
   sliderY.setPaintTicks (true);
   sliderY.setPaintLabels (true);
   sliderY.setLabelTable (sliderY.createStandardLabels (10));
   cl = new ChangeListener ()
        {
            public void stateChanged (ChangeEvent e)
            {
               posY = sliderY.getValue ();
               p3d.lookFrom (posX, posY, posZ);
               p3d.perspective (ds);
            }
        };
   sliderY.addChangeListener (cl);
   panelTemp.add (sliderY);
   panelTop.add (panelTemp);
   // Place the top panel in the top area of the overall panel.
   panel.add (panelTop, BorderLayout.NORTH);
   // The bottom panel contains the Z slider control; it also contains the
   // field of view slider and a panel of buttons.
   JPanel panelBottom = new JPanel ();
   panelBottom.setLayout (new BorderLayout ());
   // Build the bottom panel.
   panelTemp = new JPanel ();
   panelTemp.add (new JLabel ("Z"));
   final JSlider sliderZ = new JSlider (JSlider.HORIZONTAL, MINZ, MAXZ, 
DEFZ);
   sliderZ.setMinorTickSpacing (5);
   sliderZ.setMajorTickSpacing (10);
   sliderZ.setPaintTicks (true);
   sliderZ.setPaintLabels (true);
   sliderZ.setLabelTable (sliderZ.createStandardLabels (10));
   cl = new ChangeListener ()
        {
            public void stateChanged (ChangeEvent e)
            {
               posZ = sliderZ.getValue ();
               p3d.lookFrom (posX, posY, posZ);
               p3d.perspective (ds);
            }
        };
   sliderZ.addChangeListener (cl);
   panelTemp.add (sliderZ);
   panelBottom.add (panelTemp, BorderLayout.NORTH);
   JPanel panelFOV = new JPanel ();
   panelFOV.setLayout (new BorderLayout ());
   panelFOV.add (new JLabel ("Field Of View", JLabel.CENTER),
                 BorderLayout.CENTER);
   final JSlider sliderFOV = new JSlider (JSlider.HORIZONTAL, 0, 180, 90);
   sliderFOV.setMinorTickSpacing (5);
   sliderFOV.setMajorTickSpacing (10);
   sliderFOV.setPaintTicks (true);
   sliderFOV.setPaintLabels (true);
   sliderFOV.setLabelTable (sliderFOV.createStandardLabels (10));
   cl = new ChangeListener ()
        {
            public void stateChanged (ChangeEvent e)
            {
               int angle = sliderFOV.getValue ();
               if (angle == 0)
                   ds = Double.MAX_VALUE;
               else
               if (angle == 180)
                   ds = 0.0;
               else
               {
                   double rads;
                   rads = Math.toRadians (angle / 2.0);
                   ds = 1.0 / Math.tan (rads);
               }
               p3d.lookFrom (posX, posY, posZ);
               p3d.perspective (ds);
            }
        };
   sliderFOV.addChangeListener (cl);
   panelFOV.add (sliderFOV, BorderLayout.SOUTH);
   panelBottom.add (panelFOV, BorderLayout.CENTER);
   JButton btnCube = new JButton ("Cube");
   ActionListener al;
   al = new ActionListener ()
        {
            public void actionPerformed (ActionEvent e)
            {
               try
               {
                   p3d.load ("cube.3d");
               }
               catch (Exception e2)
               {
                   JOptionPane.showMessageDialog (Demo3D.this,
                                                  e2.getMessage ());
               }
            }
        };
   btnCube.addActionListener (al);
   JButton btnPyramid = new JButton ("Pyramid");
   al = new ActionListener ()
        {
            public void actionPerformed (ActionEvent e)
            {
               try
               {
                   p3d.load ("pyramid.3d");
               }
               catch (Exception e2)
               {
                   JOptionPane.showMessageDialog (Demo3D.this,
                                                  e2.getMessage ());
               }
            }
        };
   btnPyramid.addActionListener (al);
   btnCube.setPreferredSize (btnPyramid.getPreferredSize ());
   JButton btnTower = new JButton ("Tower");
   al = new ActionListener ()
        {
            public void actionPerformed (ActionEvent e)
            {
               try
               {
                   p3d.load ("tower.3d");
               }
               catch (Exception e2)
               {
                   JOptionPane.showMessageDialog (Demo3D.this,
                                                  e2.getMessage ());
               }
            }
        };
   btnTower.addActionListener (al);
   btnTower.setPreferredSize (btnPyramid.getPreferredSize ());
   panelTemp = new JPanel ();
   panelTemp.setLayout (new FlowLayout (FlowLayout.CENTER, 15, 15));
   panelTemp.add (btnCube);
   panelTemp.add (btnPyramid);
   panelTemp.add (btnTower);
   panelBottom.add (panelTemp, BorderLayout.SOUTH);
   // Place the bottom panel in the center area of the overall panel to
   // occupy empty space below the top area of the overall panel.
   panel.add (panelBottom, BorderLayout.CENTER);
   return panel;
}

In addition to Listing 1’s cube.3d, this article’s source code contains source files Demo3D.java and Panel3D.java, model files pyramid.3d and tower.3d, and Listing 2’s Demo3D.html. After compiling both source files via javac Demo3D.java, run this applet by invoking appletviewer Demo3D.html.

Listing 2. Demo3D.html

 <applet code=Demo3D.class width=550 height=550>
</applet>

The fundamentals of 3D graphics

Many people find 3D graphics difficult to understand. In this section, I attempt to overcome this difficulty by presenting 3D graphics fundamentals in the context of the 3D panel component. I discuss coordinate systems and transformations, basic transformations, world modeling, world viewing, perspective, clipping, and projection onto a 2D screen. Panel3D.java excerpts illustrate these fundamentals.

Coordinate systems and transformations

Transforming a 3D model into the wire-frame image that appears on the screen involves coordinate systems and transformations. A coordinate system provides positional information for a model’s objects (model components: a vehicle model’s body and tire components, for example). Transformations position objects, map a coordinate system to another coordinate system, and more. Coordinate systems include:

• Object coordinate system: Although not used by Panel3D, the object coordinate system is a convenience for defining objects, via object coordinates, independently of where they are located in a 3D model’s world. Multiple instances of an object can then appear (via suitable transformations) in the world, which saves space. A transformation maps this coordinate system to the world coordinate system.
• World coordinate system: A 3D model describes a world of objects. The world coordinate system locates objects within this world via world coordinates. Unlike object coordinates, these coordinates connect all of the world’s objects together. A transformation maps this coordinate system to the eye coordinate system.
• Eye coordinate system: A world is viewed similarly to how a person sees the world through a camera: the eye coordinate system’s viewpoint origin represents the person’s eye; the positive z axis represents the camera’s direction of view. The world’s objects are located relative to the viewpoint via eye coordinates. A transformation maps this coordinate system to the clipping coordinate system.
• Clipping coordinate system: Because perspective can increase the sizes of a world’s objects, invisible lines could wrap around the screen. To prevent this from happening, each line must be clipped to exclude the invisible portion of the line (or the entire line). If the line is visible, as determined by the clipping coordinates of its endpoints, a transformation maps it to the screen coordinate system.
• Screen coordinate system: Because the screen coordinate system is a 2D coordinate system, converting the endpoints of a line’s clipping coordinates to this coordinate system’s (x, y) screen coordinates requires that each endpoint’s x and y coordinates be divided by its z coordinate. Following a multiplication and addition to each transformed endpoint’s x and y values, the line appears on the screen.

Although it’s helpful to think of a transformation in terms of simple math equations (x' = x + tx, which adds a translation offset to old x, to achieve new x', for example), equations aren’t practical from a performance perspective. Evaluating the same series of equations for thousands of, or more, points is time-consuming. It’s cheaper performance-wise to use a matrix.

A matrix contains numbers in a grid of rows and columns; a transformation can be represented as a 4-row by 4-column matrix. Thanks to matrix multiplication, transformation matrices can be multiplied together before evaluating points. This results in fewer calculations per point—a significant time savings. Because matrices are so useful, I’ve nested the following Matrix class in the Panel3D class:

 
private class Matrix
{
   private double [][] matrix;
   Matrix (int nrows, int ncols)
   {
      matrix = new double [nrows][];
      for (int row = 0; row < ncols; row++)
           matrix [row] = new double [ncols];
   }
   int getCols ()
   {
       return matrix [0].length;
   }
   int getRows ()
   {
       return matrix.length;
   }
   double getValue (int row, int col)
   {
      return matrix [row] [col];
   }
   void setValue (int row, int col, double value)
   {
      matrix [row] [col] = value;
   }
   Matrix multiply (Matrix m)
   {
      Matrix result = new Matrix (matrix.length, matrix [0].length);
      for (int i = 0; i < getRows (); i++)
           for (int j = 0; j < m.getCols (); j++)
                for (int k = 0; k < m.getRows (); k++)
                     result.setValue (i, j, result.getValue (i, j) +
                                      matrix [i][k] * m.getValue (k, j));
      return result;
   }
}

Basic transformations

The translation, rotation, and scaling transformations are used in modeling and viewing. Translation changes an object’s or coordinate system’s position. To change an object’s position, add positive offsets to each point’s x, y, and z values via equations:

• x' = x + Tx
• y' = y + Ty
• z' = z + Tz

The old position is (x, y, z), the new position is (x', y', z'), and Tx, Ty, and Tz are offsets. The equivalent matrix operation:

 [x' y' z' 1] = [x y z 1] [1    0    0    0]
                         [0    1    0    0]
                         [0    0    1    0]
                         [Tx   Ty   Tz   1]

To move the coordinate system, add negative offsets to each point’s x, y, and z values. This transformation is represented by equations:

• x' = x - Tx
• y' = y - Ty
• z' = z - Tz

The old coordinate system’s (0, 0, 0) origin becomes (-Tx, -Ty, -Tz) in the new coordinate system; (Tx, Ty, Tz) in the old coordinate system becomes origin (0, 0, 0) in the new coordinate system—or the following matrix operation:

 [x y z 1] = [x' y' z' 1] [1    0    0    0]
                         [0    1    0    0]
                         [0    0    1    0]
                         [-Tx  -Ty  -Tz  1]

The Panel3D class provides a private void translate(double tx, double ty, double tz) method that handles translation. After creating a 4-row by 4-column translation Matrix object, and populating this object’s rows and columns with the values in tx, ty, and tz, this method multiplies the current transformation matrix by the translation matrix:

 
private void translate (double tx, double ty, double tz)
{
   Matrix t = new Matrix (4, 4);
   t.setValue (0, 0, 1.0);
   t.setValue (3, 0, tx);
   t.setValue (1, 1, 1.0);
   t.setValue (3, 1, ty);
   t.setValue (2, 2, 1.0);
   t.setValue (3, 2, tz);
   t.setValue (3, 3, 1.0);
   transform = transform.multiply (t);
}

Rotation transformations change an object’s orientation (via a positive angle) with respect to the x, y, and z axes. Each transformation has an inverse that changes the orientation of the coordinate system (via a negative angle) with respect to an axis. When an object is rotated, the angle of rotation around a given axis is measured in a clockwise direction when you look down the rotation axis to the origin—see Figure 2.

Rotation around the z coordinate axis is represented by equations

• x' = x * cos a + y * sin a
• y' = x * -sin a + y * cos a
• z' = 1

Angle a is measured in radians. Alternatively, this rotation can be represented by the following matrix operation:

 [x' y' z' 1] = [x y z 1] [cos a   -sin a  0       0]
                         [sin a   cos a   0       0]
                         [0       0       1       0]
                         [0       0       0       1]

Rotation around the y coordinate axis is represented by equations:

• x' = x * cos a + z * -sin a
• y' = 1
• z' = x * sin a + z * cos a

This rotation is also represented by the matrix operation specified below:

 [x' y' z' 1] = [x y z 1] [cos a   0       sin a   0]
                         [0       1       0       0]
                         [-sin a  0       cos a   0]
                         [0       0       0       1]

Rotation around the x coordinate axis is represented by equations:

• x' = 1
• y' = y * cos a + z * sin a
• z' = y * -sin a + z * cos a

In matrix form, this operation becomes:

 [x' y' z' 1] = [x y z 1] [1       0       0       0]
                         [0       cos a   -sin a  0]
                         [0       sin a   cos a   0]
                         [0       0       0       1]

The Panel3D class provides methods private void rotateX(double angle), private void rotateY(double angle), and private void rotateZ(double angle) to rotate angle degrees around x, y, and z, respectively. Each method converts from degrees to radians, creates/sets up a rotation Matrix object, and multiplies the current transformation matrix by the rotation matrix:

 
private void rotateX (double angle)
{
   angle = Math.toRadians (angle);
   Matrix r = new Matrix (4, 4);
   r.setValue (0, 0, 1.0);
   r.setValue (1, 1, Math.cos (angle));
   r.setValue (2, 1, Math.sin (angle));
   r.setValue (1, 2, -Math.sin (angle));
   r.setValue (2, 2, Math.cos (angle));
   r.setValue (3, 3, 1.0);
   transform = transform.multiply (r);
}
private void rotateY (double angle)
{
   angle = Math.toRadians (angle);
   Matrix r = new Matrix (4, 4);
   r.setValue (0, 0, Math.cos (angle));
   r.setValue (2, 0, -Math.sin (angle));
   r.setValue (1, 1, 1.0);
   r.setValue (0, 2, Math.sin (angle));
   r.setValue (2, 2, Math.cos (angle));
   r.setValue (3, 3, 1.0);
   transform = transform.multiply (r);
}
private void rotateZ (double angle)
{
   angle = Math.toRadians (angle);
   Matrix r = new Matrix (4, 4);
   r.setValue (0, 0, Math.cos (angle));
   r.setValue (1, 0, Math.sin (angle));
   r.setValue (0, 1, -Math.sin (angle));
   r.setValue (1, 1, Math.cos (angle));
   r.setValue (2, 2, 1.0);
   r.setValue (3, 3, 1.0);
   transform = transform.multiply (r);
}

Scaling is a transformation that changes an object’s size, converts from the right-handed representation of the world coordinate system to the left-handed representation of the eye coordinate system, and more. When working with objects, this transformation is represented by equations:

• x' = x * Sx
• y' = y * Sy
• z' = z * Sz

The Sx, Sy, Sz are scaling multipliers. The matrix operation appears below:

 [x' y' z' 1] = [x y z 1] [Sx   0    0    0]
                         [0    Sy   0    0]
                         [0    0    Sz   0]
                         [0    0    0    1]

The world coordinate system’s right-handed representation appears in Figure 2. To convert to the eye coordinate system’s left-handed representation (the right-handed representation with the positive z axis pointed in the opposite direction), multiply each z coordinate by -1. This transformation is represented by equations:

• x' = x * Sx
• y' = y * Sy
• z' = z * -Sz

Or by the following matrix operation:

 [x' y' z' 1] = [x y z 1] [Sx   0    0    0]
                         [0    Sy   0    0]
                         [0    0    -Sz  0]
                         [0    0    0    1]

The Panel3D class provides a private void scale(double sx, double sy, double sz) method that handles scaling. After creating a 4-row by 4-column scaling Matrix object, and populating this object’s rows and columns with the values in sx, sy, and sz, this method multiplies the current transformation matrix by the scaling matrix:

 
private void scale (double sx, double sy, double sz)
{
   Matrix s = new Matrix (4, 4);
   s.setValue (0, 0, sx);
   s.setValue (1, 1, sy);
   s.setValue (2, 2, sz);
   s.setValue (3, 3, 1.0);
   transform = transform.multiply (s);
}

World modeling

A world begins as a model. Models typically present geometric information, such as point locations or object dimensions; topological information, such as how points form polygons, how polygons form objects, and how objects form a world; and shading information. As Listing 1 illustrates, the 3D panel’s simple model consists of a vertices (points) list for its geometry and a list of edges connecting vertices for its topology. Shading isn’t present.

The Panel3D class’s load() method stores a model as follows: Each vertex’s x, y, and z values are placed into a Panel3D.Vertex object, which is mapped to the vertex name via an entry in a java.util.Hashmap; each edge’s start and end vertex names are placed into a Panel3D.Edge object, which is stored in a java.util.Vector.

The stored model is drawn by Panel3D‘s paintComponent() method. After drawing the x, y, and z axes, paintComponent() enumerates the Vector‘s Edges. For each Edge, the start and end Vertex objects are obtained, and their x, y, and z world coordinate values are used in drawing the world:

 
public void paintComponent (Graphics g)
{
   super.paintComponent (g);
   // Paint panel background.
   g.setColor (PANEL_COLOR);
   g.fillRect (0, 0, getWidth (), getHeight ());
   // Draw x axis.
   g.setColor (XAXIS_COLOR);
   moveto (-2.0, 0.0, 0.0);
   lineto (g, 2.0, 0.0, 0.0);
   // Draw dash to identify negative x axis.
   g.setColor (Color.black);
   moveto (-2.1, 0.0, 0.0);
   lineto (g, -2.2, 0.0, 0.0);
   // Draw y axis.
   g.setColor (YAXIS_COLOR);
   moveto (0.0, -2.0, 0.0);
   lineto (g, 0.0, 2.0, 0.0);
   // Draw dash to identify negative y axis.
   g.setColor (Color.black);
   moveto (0.0, -2.1, 0.0);
   lineto (g, 0.0, -2.2, 0.0);
   // Draw z axis.
   g.setColor (ZAXIS_COLOR);
   moveto (0.0, 0.0, -2.0);
   lineto (g, 0.0, 0.0, 2.0);
   // Draw dash to identify negative z axis.
   g.setColor (Color.black);
   moveto (0.0, 0.0, -2.1);
   lineto (g, 0.0, 0.0, -2.2);
   // Draw model.
   g.setColor (Color.black);
   Enumeration e = edges.elements ();
   while (e.hasMoreElements ())
   {
      Edge edge = (Edge) e.nextElement ();
      Vertex v1 = (Vertex) vertices.get (edge.startVertex);
      moveto (v1.x, v1.y, v1.z);
      Vertex v2 = (Vertex) vertices.get (edge.endVertex);
      lineto (g, v2.x, v2.y, v2.z);
   }
}

World modeling could be simplified by modifying the model file format and the 3D panel’s load() method to read the modeling transformation—a sequence of translations, rotations, and scalings that map object coordinates to world coordinates—from the model file and apply this transformation to the object coordinates of each object’s vertices. Perhaps you might be interested in this advanced exercise.

World viewing

After you finish modeling a world, you’ll want to view this world on the 2D display screen. The first step in viewing this world is to locate the world’s objects in the eye coordinate system via the viewing transformation, a sequence of translations, rotations, and scalings that map world coordinates to eye coordinates.

An example is the best way to understand the viewing transformation. The example I’ve chosen places the eye coordinate system’s viewpoint at world point (6, 8, 7) and points the eye coordinate system’s positive z axis at the (0, 0, 0) origin of the world coordinate system. Achieving this objective requires five steps that progressively establish this eye coordinate system. The first step is illustrated in Figure 3.

The first step translates the world coordinate system’s (0, 0, 0) origin to point (6, 8, 7). Because the coordinate system—not a point—is being moved, the translation requires negative x, y, and z values. translate (-6, -7, -8); is what this operation looks like from a source code perspective. The second step is shown in Figure 4.

The second step rotates the world coordinate system -90 degrees about the x’ axis so that the z axis parallels the y axis and points towards the xz plane. Because we are rotating a coordinate system (not a point), the rotation requires a positive angle. This operation is represented as rotateX (90.0); in source code. The third step appears in Figure 5.

The third step rotates the world coordinate system 216.8 degrees about the y’ axis so that world point (0, 0, 7) lies on the z’ axis. The negative version of this angle is used because we are rotating a coordinate system; this operation is represented as rotateY (-216.8); at the source code level. The fourth step is revealed in Figure 6.

The fourth step rotates the world coordinate system (approximately) 35 degrees about the x’ axis so that the world’s (0, 0, 0) origin lies on the z’ axis. The negative version of this angle is passed to rotateX() at the source code level. This step sets the stage for the final step, which changes the direction of the z’ axis so that positive z’ points towards the world’s origin. Check out Figure 7.

Figure 7 labels the axes Xe, Ye, and Ze. This labeling reminds you that the previous five steps established the eye coordinate system. Although the text indicated otherwise, these steps didn’t change the existing world coordinate system: all they did was establish a transformation pipeline. This pipeline’s input consists of a world point; the output consists of the equivalent eye point.

The lookFrom(double x, double y, double z) method sets up the viewing transformation. After initializing the current transformation matrix to the identity matrix so that the initial matrix multiplication is the same as multiplying a number by 1, a translation, three rotations, and a scaling are performed:

 
public void lookFrom (double x, double y, double z)
{
   identity ();
   translate (-x, -y, -z);
   rotateX (90.0);
   double angle;
   if (x >= 0 && y >= 0)
       angle = Math.toDegrees (Math.atan (x/y)) + 180.0;
   else
   if (x < 0 && y >= 0)
       angle = Math.toDegrees (Math.atan (x/y)) - 180.0;
   else
   if (x >= 0 && y <; 0)
       angle = Math.toDegrees (Math.atan (x/y));
   else
       angle = Math.toDegrees (Math.atan (x/y));
   rotateY (-angle);
   angle = Math.toDegrees (Math.atan (z/Math.sqrt (x*x+y*y)));
   rotateX (-angle);
   scale (1.0, 1.0, -1.0);
}

The values passed to x, y, and z can be positive or negative. This fact affects the third step in the formation of the viewing transformation. If both values are positive, angle = Math.toDegrees (Math.atan (x/y)) + 180.0; executes. Using (6, 8, 7) as the viewpoint, angle = Math.toDegrees (Math.atan (6.0/8.0)) + 180.0; yields 216.8, as expected.

For each of the -x/+y, +x/-y, and -x/-y quadrants, the first step orients the x’, y’, and z’ axes in the same way as shown in Figure 3. Similarly, the second step rotates the x’/y’/z’ coordinate system in the same direction as shown in Figure 4. In Step 3, the size of the rotation angle or its direction (or both) changes. Figure 8 reveals these steps for viewpoint (-6, 8, 7)—in the -x/y quadrant.

Perspective

The previous step in viewing the world established an eye coordinate system with an origin located at the viewpoint and with a direction of view pointed at the world’s origin. This step doesn’t take into account how much of the world is to be seen—the field of view. Because field of view relates to perspective, let’s first examine this concept. Take a look at Figure 9.

Perspective is a way to picture objects on a flat surface so as to give the appearance of distance. This is accomplished, in the real world, via a camera’s lens, which determines the amount of perspective shown in the picture. In the computer world, this is accomplished by dividing the distance from the viewpoint to the screen (D) by half the screen size (S), which results in a zoom ratio.

The perspective(double ds) method concatenates the perspective transformation to the viewing transformation so that perspective will be taken into account. After creating and initializing (to the D/S zoom ratio) a 4-row by 4-column perspective Matrix object, this method multiplies the current transformation matrix by the perspective matrix and repaints the 3D panel:

 
public void perspective (double ds)
{
   Matrix p = new Matrix (4, 4);
   p.setValue (0, 0, ds);
   p.setValue (1, 1, ds);
   p.setValue (2, 2, 1.0);
   p.setValue (3, 3, 1.0);
   transform = transform.multiply (p);
   repaint ();
}

It’s more convenient to think in terms of field of view, an angle that determines how much of the world is viewable, than the D/S zoom ratio. This angle ranges from 0 degrees to 180 degrees. As the angle increases, you observe more of the world—a smaller D/S zoom ratio. Figure 10 shows how the field-of-view angle relates to D/S.

Clipping

After applying perspective to a world (in terms of the eye coordinate system), the portion of the world that should not be seen when projected onto a 2D display screen must be clipped. This is accomplished in Panel3D‘s private void lineto(Graphics g, double x, double y, double z) method, after it and private void moveto(double x, double y, double z) transform the line’s endpoints:

 
private void lineto (Graphics g, double x, double y, double z)
{
   double xc = x*transform.getValue (0, 0)+
               y*transform.getValue (1, 0)+
               z*transform.getValue (2, 0)+
               transform.getValue (3, 0);
   double yc = x*transform.getValue (0, 1)+
               y*transform.getValue (1, 1)+
               z*transform.getValue (2, 1)+
               transform.getValue (3, 1);
   double zc = x*transform.getValue (0, 2)+
               y*transform.getValue (1, 2)+
               z*transform.getValue (2, 2)+
               transform.getValue (3, 2);
   clip (g, cx, cy, cz, xc, yc, zc);
   cx = xc;
   cy = yc;
   cz = zc;
}
private void moveto (double x, double y, double z)
{
   cx = x*transform.getValue (0, 0)+
        y*transform.getValue (1, 0)+
        z*transform.getValue (2, 0)+
        transform.getValue (3, 0);
   cy = x*transform.getValue (0, 1)+
        y*transform.getValue (1, 1)+
        z*transform.getValue (2, 1)+
        transform.getValue (3, 1);
   cz = x*transform.getValue (0, 2)+
        y*transform.getValue (1, 2)+
        z*transform.getValue (2, 2)+
        transform.getValue (3, 2);
}

Clipping is best understood in terms of points. If point (xe, ye, ze) lies within the viewing pyramid (that portion of the eye coordinate system in which objects can be seen by the viewer)—see Figure 11—the point is displayed; otherwise, the point is rejected. To be displayed, the point must satisfy conditions -ze <= (D/S)xe <= +ze and -ze <= (D/S)ye <= +ze.

Although it’s trivial to test points, it’s also time-consuming. It’s much faster to test each line’s endpoints rather than all of a line’s points. Through a repeated search that involves endpoint testing, a line is clipped against a viewing pyramid’s limits and the visible portion’s endpoints are found. To facilitate this task, a clipping coordinate system is introduced in terms of the eye coordinate system, via the matrix operation below:

 [xc yc zc 1] = [xe ye ze 1] [D/S  0    0    0]
                            [0    D/S  0    0]
                            [0    0    1    0]
                            [0    0    0    1]

My textbook’s 3D-clipping algorithm refers to a line’s endpoints in terms of the clipping coordinate system. Essentially, it locates the visible portion of a line such that conditions -zc <= xc <= +zc and -zc <= yc <= +zc are satisfied for each of the line’s two endpoints. To perform this task, the algorithm first classifies each endpoint according to a 4-bit code:

• First bit: xc is to the pyramid’s left: xc < -zc
• Second bit: xc is to the pyramid’s right: xc > zc
• Third bit: yc is below the pyramid: yc < -zc
• Fourth bit: yc is above the pyramid: yc > zc

The line lies entirely within the viewing pyramid (and is displayed) if both codes are zero. If the logical intersection of these codes is not zero, the line locates outside the pyramid and is rejected. Otherwise, the line crosses one or more pyramid planes, its intersection with each plane is calculated, and the clipping algorithm repeats.

The Panel3D class provides the private void clip(Graphics g, double x1, double y1, double z1, double x2, double y2, double z2) method, along with the private int code(double x, double y, double z) helper method, to handle clipping:

 
private void clip (Graphics g, double x1, double y1, double z1, double x2,
                   double y2, double z2)
{
   int c, c1, c2;
   double t, x = 0.0, y = 0.0, z = 0.0;
   c1 = code (x1, y1, z1);
   c2 = code (x2, y2, z2);
   while (c1 != 0 || c2 != 0)
   {
      if ((c1 & c2) != 0)
          return;
      c = c1;
      if (c == 0)
          c = c2;
      if ((c & LEFT) != 0)
      {
          t = (z1 + x1) / ((x1 - x2) - (z2 - z1));
          z = t * (z2 - z1) + z1;
          x = -z;
          y = t * (y2 - y1) + y1;
      }
      else
      if ((c & RIGHT) != 0)
      {
          t = (z1 - x1) / ((x2 - x1) - (z2 - z1));
          z = t * (z2 - z1) + z1;
          x = z;
          y = t * (y2 - y1) + y1;
      }
      else
      if ((c & BOTTOM) != 0)
      {
          t = (z1 + y1) / ((y1 - y2) - (z2 - z1));
          z = t * (z2 - z1) + z1;
          x = t * (x2 - x1) + x1;
          y = -z;
      }
      else
      if ((c & TOP) != 0)
      {
          t = (z1 - y1) / ((y2 - y1) - (z2 - z1));
          z = t * (z2 - z1) + z1;
          x = t * (x2 - x1) + x1;
          y = z;
      }
      if (c == c1)
      {
          x1 = x;
          y1 = y;
          z1 = z;
          c1 = code (x, y, z);
      }
      else
      {
          x2 = x;
          y2 = y;
          z2 = z;
          c2 = code (x, y, z);
      }
   }
   showLine (g, x1, y1, z1, x2, y2, z2);
}
private int code (double x, double y, double z)
{
   int result = 0;
   if (x < -z)
       result = LEFT;
   if (x > z)
       result |= RIGHT;
   if (y < -z)
       result |= BOTTOM;
   if (y > z)
       result |= TOP;
   return result;
}

Projection onto a 2D screen

Subsequent to the clipping algorithm calculating the endpoints of the visible portion of a line, this line can be projected onto the 2D display screen—the final step in viewing a world. Although Panel3D‘s projection code requires clipping coordinates, it’s helpful to think about projection in terms of eye coordinates. The following matrix operation converts clipping coordinates back to eye coordinates:

 [xe ye ze 1] = [xc yc zc 1] [S/D  0    0    0]
                            [0    S/D  0    0]
                            [0    0    1    0]
                            [0    0    0    1]

Projecting eye points—world points located in the eye coordinate system—onto the 2D display screen is accomplished by dividing each point’s x and y values by its z value. For example, assume that the clipping algorithm has accepted eye point P, one of a line’s endpoints. After dividing its x and y values by its z value, the projection of P—point P’—appears on the screen, as illustrated in Figure 12.

The screen coordinates of the projected point, P’, are obtained from observing a pair of similar triangles. In Figure 13’s Ye/Ze plane, these similar triangles are OQ’P’ and OQP, establishing the ys/D = ye/ze relation. For the Xe/Ze plane, similar triangles would establish xs/D = xe/ze. Rewriting these relations and dividing by half the screen size yields xs = Dxe/Sze and ys = Dye/Sze.

The xs and ys values are fractions of displacement across the screen. Each value is useless until it is converted to a screen coordinate. This conversion is accomplished by multiplying the value by half the screen’s size (in the appropriate direction) and adding the result to the appropriate screen center value.

In keeping with textbook conventions, I’ve introduced the concept of a view-port (which defaults to the entire screen) into Panel3D via a private void setViewport(int x1, int y1, int x2, int y2) method, variables vsx and vsy (which contain half the size of the view-port), and variables vcx and vcy (which contain the center of the view-port):

 
private void setViewport (int x1, int y1, int x2, int y2)
{
   height = y2-y1+1;
   double vxl = x1;
   double vyb = y1;
   double vxr = x2;
   double vyt = y2;
   vcx = (vxl+vxr)/2;
   vcy = (vyb+vyt)/2;
   vsx = (vxr-vxl)/2;
   vsy = (vyt-vyb)/2;
}

Taking these variables into consideration, xs = (Dxe/Sze)vsx+vcx and ys = (Dye/Sze)vsy+vcy return the appropriate view-port coordinates, which are basically the 3D panel’s coordinates. For the equivalent clipping coordinates, these relations are expressed as xs = (xc/zc)vsx+vcx and ys = (yc/zc)vsy+vcy.

Because Panel3D‘s perspective() method is called to establish the D/S ratio prior to lineto() calling clip(), the latter clipping coordinates are used by the following private void showLine(Graphics g, double xc1, double yc1, double zc1, double xc2, double yc2, double zc2) method to carry out the projection:

 
private void showLine (Graphics g, double xc1, double yc1, double zc1,
                       double xc2, double yc2, double zc2)
{
   int xs1 = (int) ((xc1/zc1)*vsx+vcx);
   int ys1 = (int) ((yc1/zc1)*vsy+vcy);
   int xs2 = (int) ((xc2/zc2)*vsx+vcx);
   int ys2 = (int) ((yc2/zc2)*vsy+vcy);
   g.drawLine (xs1, height-ys1, xs2, height-ys2);
}

The showLine() method subtracts each of the values in the ys1 and ys2 variables from the view-port’s height variable because the values in ys1 and ys2 assume a screen where the (0, 0) origin locates in the lower-left corner. In contrast, a Java component places this origin in the upper-left corner.

Conclusion

Because 3D computer graphics theory can be hard to grasp, I hope this article’s Panel3D component, Demo3D applet, and component-based 3D graphics tutorial have helped to simplify this fascinating topic. In the future, I’ll expand the component and the applet to illustrate additional 3D graphics concepts.

For now, however, I have some homework for you: Create additional model files and make them accessible to Demo3D via appropriate buttons. Also, implement a checkbox for hiding/showing the coordinate axes.