Aoi is an applet/application written in Java. Version 0.04 is able to display three-dimensional objects made up of polygons, by projecting the polygons onto the screen. It also allows the user to change the viewing position and orientation. Definitions of the polygons to be displayed are read from a file. For each polygon, coordinates of its vertices, and optionally its color, should be defined.
The program can be run both as an applet or an application.
To run it as an application, type
java Aoi file
where file is the name of the file containing the
description of the world to be displayed.
To run the program as an applet, first embed the applet into an
HTML document. Then to view the applet, you can use e.g. JDK's
appletviewer, by typing
appletviewer HTML_document
Alternately, you can use a Java-enabled browser, which will not only
show you the applet in the document, but also the rest of the
document. Recent versions of Netscape, for example, are able to
display applets. To use Netscape to do this, you can choose Open
File from the File menu, and enter or select the
file name of the HTML document. Or, you can choose Open
Location from the same menu, and type in the URL for the HTML
document.
To embed the applet into an HTML document, you must use an
APPLET tag. In its most basic form, it looks like this:
<APPLET CODE="Aoi.class" WIDTH=301
HEIGHT=301></APPLET>
You may also use other tags, such as ALIGN, within the
APPLET tag, but you must specify CODE,
WIDTH and HEIGHT, and they must be given the values
shown above.
Between <APPLET> and </APPLET> you will
need to give the parameter required by the applet, the name of the
file containing the world description. You do it like this:
<PARAM NAME="file" VALUE=filename>
The program reads the description of the world to be displayed, i.e. a list of all the polygons in the world, from a text file. Each polygon must be defined on a separate line, and the definition must fit on one line. For each polygon, at least three vertices must be defined. There may be more, but if so, all of them must be on the same plane. Also, if it is possible to split a polygon into more than two parts with one plane, the polygon may not always be displayed correctly. When in doubt, only use triangles.
To specify a vertex, write (x,y,z), where x, y and z are floating point values specifying the coordinates of the vertex. Specify all vertices of the polygon like this, in either clockwise or counterclockwise order along the edges of the polygon.
Optionally you may also specify the color of the polygon by writing [r,g,b], where r, g and b are integer values between 0 and 255. When divided by 255, the values give a position within the RGB color model unit cube. Alternately, you may specify a color by writing [color], where color is one of black, blue, cyan, darkGray, gray, green, lightGray, magenta, orange, pink, red, white, and yellow. The color names are case insensitive. If the chosen color is not available, the closest one of the available colors will be used instead.Lines beginning with '%' or containing no '(' are considered to be comments.
Example:
% Roof. (-3,3,1.5) (-3,0,3) (3,0,3) (3,3,1.5) [black] (-3,0,3) (-3,-3,1.5) (3,-3,1.5) (3,0,3) [0,0,0]
The commands understood by the program are given in the table below. All commands are given by pressing a key, either a cursor key or some letter. Make sure that the window, or, if using a browser, the applet, is active before attempting to give any commands.
| List of commands | |
|---|---|
| Key | Function |
| Left | Move Left |
| Right | Move Right |
| Up | Move Up |
| Down | Move Down |
| Shift-Up | Move In |
| Shift-Down | Move Out |
| j | Rotate Counterclockwise about y-axis |
| k | Rotate Clockwise about y-axis |
| i | Rotate Counterclockwise about x-axis |
| m | Rotate Clockwise about x-axis |
| z | Zoom In |
| Z | Zoom Out |
Moving moves the viewing point into the specified direction, and the objects displayed therefore appear to move into the opposite direction. Possible directions of movement are along the yellow lines, or straight into or out of the screen. Step of movement is set to 0.25, regardless of how many pixels it corresponds into. At present, moving in or out doesn't produce any visible effect (except for a redraw), because of the simple orthographic parallel projection used.
Rotations cause all of the objects to be rotated around either x-axis (the horizontal yellow line) or y-axis (the vertical yellow line). Step or rotation is set to 30 degrees. As far as the user is concerned, the right half of the horizontal line is the positive x-axis, and the top half of the vertical one is the positive y-axis. This is good to keep in mind when figuring out which rotation is a clockwise one and which is not.
Initially, 40.0 pixels correspond to value 1. You can change this by zooming. Zoom factor is set to 0.9, and the number of pixels per 1 will be either divided or multiplied by the zoom factor, depending on whether you zoom in or out, respectively.
The software was programmed mostly under the Linux operating system, but some of the work was done under Windows 95, and some under the Hewlett Packard flavour of UNIX (HPUX). The Java Developer's Kit (JDK) was always used, regardless of the platform.
The class library used to display graphics is the Alternative Window Toolkit (AWT). Some other standard Java libraries, such as java.io and java.net, were also used. Excluding those libraries, and the class BaseAppletFrame, all of the classes used by the applet were written by the author.
The source code for the program can be found from the address
http://www.iki.fi/hasu/Aoi/src/
To compile, you should have the JDK, or some other suitable
development kit installed. If using JDK, you may get the makefile from
the above address, and just type
make
Or, without Makefile, you can type
javac AppletFrame.java Exceptions.java
SinglyLinkedList.java Aoi.java
As a result, you should get over twenty or so class files, each of
which contains a bytecode description of property and methods of one of the
classes of the application.
The object descriptions read from a file by the program are expressed in world coordinates. The world coordinates of the objects are never changed after reading them in. Instead, when wanting to display a particular view into the world, copies of all of the polygons are made, and the coordinates of those polygons are expressed in view coordinates.
View coordinate system is such that its x-axis is the horizontal yellow line on the screen, and the y-axis is the vertical one, so that origo is in the middle. Positive x-axis is on the right of origo, and positive y-axis below origo (because in AWT, y-coordinates grow from the top of the screen to the bottom). Positive z-axis reaches directly out at the viewer. x and y -values are expressed in pixels.
Initially, the origos of both of the coordinate systems are in the
same place. When moving, the value of the vector that points from
view coordinate system origo into the world origo is changed.
When rotating, the base vectors of the world coordinate system are
rotated. The rotation about x-axis is calculated as follows:
[ x' ] [ 1 0 0 0 ] [ x ]
[ y' ] = [ 0 cos(a) -sin(a) 0 ] * [ y ]
[ z' ] [ 0 sin(a) cos(a) 0 ] [ z ]
[ 1 ] [ 0 0 0 1 ] [ 1 ]
and about y-axis:
[ x' ] [ cos(a) 0 sin(a) 0 ] [ x ]
[ y' ] = [ 0 1 0 0 ] * [ y ]
[ z' ] [ -sin(a) 0 cos(a) 0 ] [ z ]
[ 1 ] [ 0 0 0 1 ] [ 1 ]
where [x, y, z] is the old base vector and [x', y',
z'] is the new one, and a is the angle of rotation.
Initial values of the base vectors are [1,0,0],
[0,-1,0], [0,0,1] for x, y, and z -axes, respectively.
After any operation that changes the view, view transformation matrix is
recalculated. This matrix, be it V, is such that
V * [x, y, z, 1] = [x', y', z', 1], where (x,y,z)
is in world coordinates, and (x',y',z') is the same point
expressed in view coordinates.
To determine the view transformation matrix V,
we perform the following calculation:
[ ppu 0 0 ppu/2 ] [ bxx bxy bxz 0 ] T [ 1 0 0 ox ]
V = [ 0 ppu 0 ppu/2 ] * [ byx byy byz 0 ] * [ 0 1 0 oy ]
[ 0 0 1 0 ] [ bzx bzy bzz 0 ] [ 0 0 1 oz ]
[ 0 0 0 1 ] [ 0 0 0 1 ] [ 0 0 0 1 ]
where ppu is pixels per unit, [bxx, bxy, bxz],
[byx, byy, byz], [bzx, bzy, bzz] are the base
vectors of the world coordinate system, and [ox, oy, oz] is
the position of the world coordinate system origo in view coordinates.
The binary space-partitioning (BSP) tree method is used to determine
the order in which to draw the polygons onto the screen. Every time
after the viewing point or angle has changed, the plane equation of each
polygon is recalculated. This is done so that two non-parallel edges
of the polygon are first selected, and then three vertices of those
edges (x1,y1,z1), (x2,y2,z2), and
(x3,y3,z3), and the following calculations are made
to determine the constants of the plane equation
ax + by + cz + d = 0:
| 1 y1 z1 | | x1 1 z1 | | x1 y1 1 | | x1 y1 z1 |
a = | 1 y2 z2 | b = | x2 1 z2 | c = | x2 y2 1 | d = -| x2 y2 z2 |
| 1 y3 z3 | | x3 1 z3 | | x3 y3 1 | | x3 y3 z3 |
Optimization could be done here by excluding those polygons
that do not fit, even in part, within the borders of the
window. It also seems unnecessary to recalculate the equation after
altering the zoom factor.
The plane of each polygon, even if some of them are the same,
is used to check if the plane goes through any of the polygons. If a
part of some polygon is on the other side of the plane, and a part on
the other side, the polygon is split into two. No splitting is done if
a point or edge of the polygon (or even the whole polygon) only touches the
partitioning plane, but does not go through it.
If some edge of a polygon to be split is cut by the partitioning
plane, it is of course necessary to determine the point of the edge
that is on the plane.
If the position vectors of the endpoints of the edge are E0
and E1, then the position of any point on the edge can be
expressed as E0 + q * (E1 - E0), just by changing the value
of the scalar q. For any point on the plane, in turn, it is true that
[a b c] P = -d, where P is the position vector of
the point. Now, if E0 = [e0x, e0y, e0z] and
E1 = [e1x, e1y, e1z], we can write the group of equations:
e0x = q * (e1x - e0x) = x
e0y = q * (e1y - e0y) = y
e0z = q * (e1z - e0z) = z
a * x + b * y + c * z = -d
from which we can solve the unknown variables q, x,
y, and z, where (x,y,z) are the coordinates
of the point we wanted to know.
Rounding errors can be severe if the denominator is small. The
denominator might even be zero. In these cases, iteration is used
until the we have such (x,y,z) that
a * x + b * y + c * z + d is close enough to zero. As initial
values, we choose the endpoints of the edge, and start splitting the
edge in half recursively, always selecting the half which might
contain the solution for the next iteration.
When the partitioning is started, all of the polygons are placed into the root node of the BSP tree. For each of the partitioning planes, all of the leaf nodes in the tree are examined. Unless all of the polygons in a leaf node are in the same side of the partitioning plane, the leaf node is changed into an interior node and given two leaf nodes as children. Those polygons in front of the plane are placed into other one of the children, and those behind are placed into the other one. When all of the partitioning planes have been used, we can draw the polygons in correct order by traversing the tree depth-first by always selecting the "behind" child first and after that the "front" child.
To determine the position of a polygon in comparison to a plane,
the following calculation is made for each vertex of the polygon:
zp = (a * x + b * y + d) / -c
where a, b, c, and d are constants
of the plane equation ax + by + cz + d = 0, and x
and y are the x and y -coordinates of the vertex. After this,
the z-coordinate of the vertex is compared against zp, to
determine the position of the vertex in comparison to the plane. View
direction is along the positive z-axis, so the point that has a bigger
z-value is in the front of the other. If c is zero, the plane
is parallel to the line of view, and the vertex under examination is
either on the plane or its side.
The world to be displayed is built of polygons, so for this purpose a class called PolygonSurface was created (the name Polygon would have been used, if there already wasn't such a class in AWT). The polygon consists of edges, so a class called Edge was created to represent them. Edges consist of two points and a line between them, so class Vertex was created to represent the points. Since polygons have a list of edges, and the world has a list of polygons, and the leaf nodes in a BSP tree contain lists of polygons, some kind of a list class was obviously required. It was one of the first things written for the program, and got a very descriptive name, SinglyLinkedList. Other data structures used include points with various dimensions, such as Point3 and Point4, and a 4 by 4 matrix class called Matrix4x4.
Then to the larger data structures. The world description is kept in a class called World. One particular view into the world is kept in the class WorldView. Then there is a BSP tree class called BSPTree, which contains the root of the tree, which may have children. Both the root and possible children are of type BSPTreeNode.
The events caused by the user (keypresses) cause the keyDown method of Applet (Aoi's superclass) to be called. The events are processed there by calling the appropriate methods of other objects, which are the property of Aoi. File I/O is handled by creating a DataInputStream on top of either a FileInputStream or an InputStream opened by an URL object. Then it is a simple matter to read the stream one line at a time. Parsing the lines, however, seemed less convenient without the use of pointers (like in C or C++).
If the program is run as an application, the class AppletFrame is instantiated first by the static main method of Aoi. If the program is run as an applet, Aoi is the class that is instantiated first, and no instance of AppletFrame is created. Aoi then creates a World, and an initial view into it, and finally a Display for the view. Then it just sits around and responds to user input.
No global variables are used by the program.
The author enjoyed writing the software, since he was well motivated to do so. As someone who plays games that employ great looking polygon graphics, he wanted to familiarize himself with at least the most basic 3D-polygon handling routines, by writing them himself.
Although this is only the second Java application the author has written, he was already comfortable with the language, which says something positive about the language. With the extra overhead of interpreting bytecode and checking for security exceptions, a Java applet may not be the best of choices for displaying fast and smooth polygon animation, at least without specialized hardware. But speed was not the main concern when writing the software. If it were that important, the code itself could surely be further still optimized for speed, or it could perhaps be compiled into native code if one would be willing to sacrifice portability.
The hardest part in writing the software was the detection of visible surfaces, and avoiding severe rounding errors in the calculations involved.