George Aroush, instructor
(Do at lest one of the following)
- Create your own three dimensional object as a set of polygons. Display the object, rotate it, move it and scale it in a 3D space.
- Modify "Dodecahedron.java" or your own three dimensional program and have the program display two or more objects moving and rotating in space all independent of each other or using a specific rule to interact with each other.
| Back to the top of this page. | Back to main Index |
Solid 3D Objects
Dodecahedron.java shows how to render a 12-faced solid object with colored faces, using the painter's algorithm. The object, made of pentagons, each polygon a different color, is drawn from back to front; faces/polygons that are closer to the viewer cover those farther away, just as a painter might paint a background first and then paint objects over it.
To describe a face that is a polyhedron, Dodecahedron.java uses a more complex kind of two-dimensional array than we have seen so far -- 10 values for each face describe 4 different kinds of things:
Array Index Sample Value Comment 1st 5 Number of vertices in face/polygon 2nd (the next 3 values/index) 0, 0, 0 Color of the Face/Polygon (R, G, B) 5th 0 Place holder for farthest Z value 6th (the next 5 values/index) 0, 1, 5, 6, 7 The Face's/Polygon's Vertices/Edges All the values are integers. The 1st value tells how many vertices make up the face. The next three values are for the polygon's color in RGB color space. The 5rd value is used to hold the most distant z-coordinate in the face which permits the faces to be sorted and put in order from back to front. The remaining values starting with the 6th are the index numbers of the vertices that make up the face:
int faces[][] = { {5, /* number of vertices in face */ 0, 0, 255, /* color of face */ 0, /* place for farthest z */ 0, 1, 5, 6, 7}, /* vertices */ {5, 0, 255, 255, 0, 1, 0, 4, 3, 2}, .... .... };The array elements are written this way for visual clarity and ease of editing.
The program runs very much like CubeFour.java, copying the vertices form oCoord[][] to coord[][], scaling, rotating, and translating them.
There is a change in the Project3D() method, and three new methods which are added: FarthestZ(), FDisplay(), and BubbleSort(), are used to display. BubbleSort() will sort any array of any kind into some kind of order. (See the second part of this handout for details on sorting.)
In Dodecahedron.java, we want the faces of the dodecahedron to be sorted in order form back (farthest from viewer) to front (closest to viewer.) Since the viewer is located at the origin, X, Y and Z are 0, farther faces will have larger Z-coordinates and closer faces will have smaller Z-coordinates/value. So we will use BubbleSort() to sort the faces by their farthest Z-coordinates.
The array of faces is sent to FarthestZ() method to determine the farthest Z-coordinate for each face. It begins by putting 0 in the FAR_Z position of a particular face array like this:
f[i][FAR_Z] = 0;
It uses the index numbers for each face to look up the current Z-coordinates for each vertex. The vertex numbers begin at the fourth position in the face array (starting at VERT.) The variable j is used to loop through the vertices; its value is added to VERT:
if (f[i][FAR_Z] < (int) v[ f[i][VERT + j] ][Z]) f[i][FAR_Z] = (int) v[ f[i][VERT + j] ][Z];If the current vertex's Z-coordinate is greater than the current farthest Z, the farthest Z is made equal to the new Z-coordinate. Note that after various rotations, the farthest Z of each face will probably be different, so this must be done for each display. Now the face arrays can be sent to BubbleSort() for sorting.
| Back to the top of this page. | Back to main Index |
Sorting: the Bubble sort Algorithm
One of the easiest sorting algorithm is called the Bubble Sort Algorithm. Bubble sort is simple but popular sorting algorithm. It is used frequently as a programming exercise because it is relatively easy to understand. It is not, however, particularly efficient. Other sorting algorithms, such as Heap sorts, Merge sorts and Quick sorts, are used more often in real applications.
The idea of Bubble sort is to repeatedly move the largest (or smallest depending on the order of sort we are doing: accenting or descending) element to the highest (or lowest; again depending on the sort order) index position of the array. Rather than search the entire effective array to find the largest/smallest element like most other sort algorithm do, bubble sort focuses on successive adjacent pairs of elements in the array, compares them, and either swaps them or not. In either case, after such a step, the larger of the two elements will be in the higher/lower index position. The focus then moves to the next higher position, and the process is repeated.
When the focus reaches the end of the effective array, the largest element will have ``bubbled'' from whatever its original position to the highest/lowest index position in the effective array. For example, consider the array with the data:
45, 67, 12, 34, 25, 39
In the first step, the focus is on the first two elements (in bold) which are compared and swapped, if necessary. In this case, since the element at index 1 is larger than the one at index 0, no swap takes place.
45, 67, 12, 34, 25, 39
Then the focus move to the elements at index 1 and 2 which are compared and swapped, if necessary. In our example, 67 is larger than 12 so the two elements are swapped. The result is that the largest of the first three elements is now at index 2.
45, 12, 67, 34, 25, 39
The process is repeated until the focus moves to the end of the array, at which point the largest of all the elements ends up at the highest possible index. The remaining steps and result are:
45, 12, 34, 67, 25, 39
45, 12, 34, 25, 67, 39
45, 12, 34, 25, 39, 67Thus, in this process the largest element has bubbled to the top index of the array.
In general, a bubble step is performed by the loop:
for (k = 0; k < arraySize - 1; k++) { if (x[k] > x[k + 1]) SwapArray(x, k, k + 1); }The loop compares all adjacent elements at index k and k + 1. If they are not in the correct order, they are swapped.
One complete bubble step moves the largest element to the last position, which is the correct position for that element in the final sorted array. The effective size of the array is reduced by one and the process repeated until the effective size becomes one. Each bubble step moves the largest element in the effective array to the highest/lowest index of the effective array.
Dodecahedron.java uses Bubble sort to sort the faces of the dodecahedron. The only major different in the algorithm presented in the demo is that it moves around a chunk of elements (faces/polygons in this case.) This is needed because we need to keep the information for each face togther.
| Back to the top of this page. | Back to main Index |
Dodecahedron.java
/* * Program: Dodecahedron.java * Purpose: Solid 3D Objects * Author: George Aroush * Date: 1/1/1998 * Change Log: None * * Full description of Program: * Use of "painter's algorithm" to display filled in dodecahedron */ import java.applet.*; import java.awt.*; public class Dodecahedron extends Applet { final int NP = 21; /* number of points */ final int NF = 12; /* number of faces */ final int MAX_V = 5; /* largest number of vertices in a face */ final int ARRAYSIZE = (5 + MAX_V); /* number of values in a face array */ final int CX = 320; /* center of screen */ final int CY = 200; /* edges of screen */ final int MAXX = 640; final int MAXY = 400; /* index into our 3D array */ final int X = 0; final int Y = 1; final int Z = 2; /* positions (or offsets) in face array */ final int QTY = 0; /* number of vertices in face */ final int COLOR_R = 1; /* color of face - Red */ final int COLOR_G = 2; /* color of face - Green */ final int COLOR_B = 3; /* color of face - Blue */ final int FAR_Z = 4; /* most distant vertex in face */ final int VERT = 5; /* start of vertex numbers */ public void paint(Graphics g) { /* coordinates of 20 vertices of dodecahedron */ float oCoord[][] = {{-30, 78, 0}, { 30, 78, 0}, {48, 48, 48}, { 0, 30, 78}, {-48, 48, 48}, { 48, 48, -48}, { 0, 30, -78}, {-48, 48, -48}, {-78, 0, 30}, {-78, 0, -30}, {78, 0, 30}, { 78, 0, -30}, {-48, -48, 48}, { 0, -30, 78}, {48, -48, 48}, {-48, -48, -48}, {-30, -78, 0}, { 48, -48, -48}, { 0, -30, -78}, { 30, -78, 0}, { 0, 0, 0}}; /* 21st vertex added for center of dodecahedron */ /* to hold temporary values of vertices */ float coord[][] = new float[NP][3]; /* The twelve faces */ int faces[][] = { {5, /* number of vertices in face */ 0, 0, 255, /* color of face */ 0, /* place for farthest z */ 0, 1, 5, 6, 7}, /* vertices */ {5, 0, 255, 255, 0, 1, 0, 4, 3, 2}, {5, 64, 64, 64, 0, 16, 15, 18, 17, 19}, {5, 128, 128, 128, 0, 16, 19, 14, 13, 12}, {5, 0, 255, 0, 0, 9, 8, 4, 0, 7}, {5, 192, 192, 192, 0, 10, 11, 5, 1, 2}, {5, 255, 0, 255, 0, 8, 9, 15, 16, 12}, {5, 255, 200, 0, 0, 11, 10, 14, 19, 17}, {5, 255, 175, 175, 0, 18, 6, 5, 11, 17}, {5, 255, 0, 0, 0, 7, 6, 18, 15, 9}, {5, 255, 255, 255, 0, 3, 4, 8, 12, 13}, {5, 255, 255, 0, 0, 3, 13, 14, 10, 2} }; /* the location of the object in 3D space */ float trans[] = {0, 0, 900}; /* velocity along X, Y, & Z axes*/ float vel[] = {20, 20, 20}; /* the size of the object */ float scal[] = {2, 2, 2}; /* current angles of rotation of object */ float angle[] = {0, 0, 0}; /* rates of rotation of object */ float ang_inc[] = {0.08f, 0.05f, 0.0722f}; /* minimum and maximum X Y & Z values for vertex 21 */ float limits[][] = { {-500, 500}, {-500, 500}, { 700, 5000} }; /* holds the projected (2D) object */ int proj[][] = new int[NP][2]; /* screen distance */ float sd = 300; /* for looping */ int i, j; /* * Copy dodecahedron from unchanging, original arrays, * scale and rotate around three axes move it, project * vertices, determine farthest Z-coordinate for each * face, sort the faces from back to front, & draw them * in that order */ for (j = 0; j < 10000; j++) { Copy3D(oCoord, coord, NP); Scale3D(coord, scal, NP); Rotate3D(coord, Y, Z, NP, angle[X]); Rotate3D(coord, Z, X, NP, angle[Y]); Rotate3D(coord, X, Y, NP, angle[Z]); Translate3D(coord, trans, NP); /* * Test center of icosahedron and reverse direction * of velocity if it has crossed a limit */ for (i = X; i <= Z; i++) { if (coord[NP - 1][i] < limits[i][0] || coord[NP - 1][i] > limits[i][1]) vel[i] *= -1.0; trans[i] += vel[i]; /* change location of object */ angle[i] += ang_inc[i]; /* change angles of rotation */ if (angle[i] > 2 * Math.PI) angle[i] -= 2 * Math.PI; } Project3D(coord, proj, NP, sd); /* Find farthest z of each face, store in FAR_Z position in its array */ FarthestZ(coord, faces, NF); /* Sort faces from back to front, using BubbleSort() algorithm */ BubbleSort(faces, NF, ARRAYSIZE); FDisplay3D(proj, faces, NF, g); Delay(100); g.clearRect(0, 0, 640, 480); } } /* * void FarthestZ() * * Determines farthest z-coordinate in each face */ void FarthestZ(float v[][], int f[][], int nf) { int i, j; for (i = 0; i < nf; i++) { f[i][FAR_Z] = 0; /* assume it's zero */ for (j = 0; j < f[i][QTY]; j++) { /* * Vertex numbers start at f[i][VERT], so j is added to * get desired vertex number. This vertex number is * plugged into v[][Z] to get the actual Z-coordinate */ /* * Compare each Z-coordinate to current far_z. If a * Z-coordinate is farther, use its value for far_z */ if (f[i][FAR_Z] < (int) v[f[i][VERT + j]][Z]) f[i][FAR_Z] = (int) v[f[i][VERT + j]][Z]; } } } /* * void FDisplay() * * Displays filled faces of object. Uses values in faces[][] to set * color and fill x[] and y[] with projected values to be filled with area(). */ void FDisplay3D(int proj[][], int faces[][], int nf, Graphics g) { boolean on; int x[] = new int[MAX_V]; int y[] = new int[MAX_V]; int f, v; /* faces should have been sorted from front to back */ for (f = 0; f < nf; f++) { on = true; /* * This loop continues while v is less than # of vertices, * and on = 1, meaning all the points are on the screen */ for (v = 0; v < faces[f][QTY]; v++) { /* * vertex numbers start at faces[f][VERT], so v is added * to get desired vertex number. This vertex number is * plugged into proj[][] to get projected X and Y-coord */ x[v] = proj[ faces[f][ VERT + v] ][X]; y[v] = proj[ faces[f][ VERT + v] ][Y]; /* make sure this point is on screen */ if (x[v] < 0 || x[v] > MAXX || y[v] < 0 || y[v] > MAXY) on = false; } if (on == true) { Color c = new Color(faces[f][COLOR_R], faces[f][COLOR_G], faces[f][COLOR_B]); g.setColor(c); /* get color from face array */ g.fillPolygon(x, y, faces[f][QTY]); /* fill face */ /* Delay(1000); */ /* uncomment this line to see the drawing in action */ } } } /* * void BubbleSort() * * Sorts an array using the Bubble Sort algorithm */ void BubbleSort(int faces[][], int nf, int faceSize) { int faceDataA[] = new int[faceSize], faceDataB[] = new int[faceSize]; int facesIndexA, facesIndexB; int nDiff; int i, j; while (nf > 1) { bIsDone = true; facesIndexA = 0; for (i = 0; i < nf - 1; i++) /* walk throuh faces and move things up/down as needed */ { /* get a face off the list */ for (j = 0; j < faceSize; j++) faceDataA[j] = faces[facesIndexA][j]; facesIndexB = facesIndexA + 1; /* get the second face */ for (j = 0; j < faceSize; j++) faceDataB[j] = faces[facesIndexB][j]; /* check the 'far-z' of those faces */ if (faceDataA[FAR_Z] == faceDataB[FAR_Z]) nDiff = 0; else { if (faceDataA[FAR_Z] > faceDataB[FAR_Z]) nDiff = 1; else nDiff = -1; } /* if they are not equal the we must swap them */ if (nDiff != 0) { if (nDiff < 0) { /* we will swap now */ for (j = 0; j < faceSize; j++) faces[facesIndexA][j] = faceDataB[j]; for (j = 0; j < faceSize; j++) faces[facesIndexB][j] = faceDataA[j]; } } facesIndexA++; /* get the next element in the array */ } nf--; } } /* * void Project3D() * * Projects coordinate array onto screen at given screen distance * storing result as x and y coordinates in proj[][2] array. */ void Project3D(float coord[][], int proj[][], int np, float sd) { int i; /* * scale each x and y by the ratio of the the screen * distance to the Z-coordinate -- add coordinates of * center of screen to shift origin to center of screen */ for (i = 0; i < np; i++) { if (coord[i][Z] != 0.0f) { proj[i][X] = CX + (int) (coord[i][X] * sd / coord[i][Z]); proj[i][Y] = CY + (int) (coord[i][Y] * sd / coord[i][Z]); } else proj[i][X] = proj[i][Y] = 0; } } /* * void Translate3D() * * Add three values of trans[3] to each vertex in coord[][3] thus * moving vertices along all three axes */ void Translate3D(float coord[][], float trans[], int np) { int i, j; for (i = 0; i < np; i++) /* loop in the array */ { for (j = 0; j < 3; j++) /* loop in the vertex */ coord[i][j] += trans[j]; } } /* * void Copy3D() * * Copy X, Y & Z coordinates from original arrays to temp arrays */ void Copy3D(float orig[][], float coord[][], int np) { int i, j; for (i = 0; i < np; i++) { for (j = 0; j < 3; j++) coord[i][j] = orig[i][j]; } } /* * void Scale3D() * * Multiplies each X, Y & Z coordinate by corresponding element in the array s[] */ void Scale3D(float coord[][], float s[], int np) { int i, j; for (i = 0; i < np; i++) { for (j = 0; j < 3; j++) coord[i][j] *= s[j]; } } /* * void Rotate3D() * * Rotate vertices around an axis by number of radians in angle: * for X axis rotation: c1 = Y and c2 = Z * for Y axis rotation: c1 = Z and c2 = X * for Z axis rotation: c1 = X and c2 = Y */ void Rotate3D(float coord[][], int c1, int c2, int np, float angle) { int i; float t, s, c; s = (float) Math.sin(angle); c = (float) Math.cos(angle); for (i = 0; i < np; i++) { /* temporarily store new value of coordinate 1 */ t = c * coord[i][c1] + s * coord[i][c2]; coord[i][c2] = c * coord[i][c2] - s * coord[i][c1]; coord[i][c1] = t; } } /* * void Display3D() * * Displays wire frame of object. Uses values in edge[][2] to find starting and * ending vertex for each edge */ void Display3D(int proj[][], int edge[][], int ne, Graphics g) { int e; int s, f; int x1, y1, x2, y2; for (e = 0; e < ne; e++) { s = edge[e][0]; /* s -- is the starting vertex */ f = edge[e][1]; /* f -- is the ending vertex */ x1 = proj[s][X]; /* stating point of a line */ y1 = proj[s][Y]; x2 = proj[f][X]; /* ending point of a line */ y2 = proj[f][Y]; g.drawLine(x1, y1, x2, y2); } } /* * void Delay() * * Simply pauses for some time */ public void Delay(int delayTime) { try { Thread.sleep(delayTime); /* call Java's sleep method */ } catch (InterruptedException e) { /* when the sleep() call above is over, Java will */ /* be interuppted and we fall into this block of code */ /* because our intention is simply slow down things */ /* wed do nothing in our exception code and just get out */ } } }Dodecahedron.htm
<html> <head> <title>Dodecahedron</title> </head> <body> <hr> <applet code=Dodecahedronwidth=640 height=480></applet> <hr> </body> </html>
| Back to the top of this page. | Back to main Index. |