Rotation of General Triangle in a 3-D Space
Programming Project
Andrew Flores
December 2, 1997
Abstract
The presentation of a sequence of rotations of a triangle about a three dimensional space is the desired goal of this project. It incorporates many of the concepts covered in the ME24-384 class, Computational Geometry, such as linear algebra, geometric relationships, algorithms, C programming, and the VRML language. The user is given the opportunity to choose the initial position of the triangle and the number of rotations desired, rotate from seven difference types of rotations, and specify the rotation angle and direction of each. The algorithm of this project used a three dimensional rotational matrix, translation matrix, and a normal vector formula. The user is then allowed to view the rotation via a series of *.wrl files. However, the ultimate goal is to create one *.wrl file that animates the rotation of the triangle. Being a first version code, there are several obvious improvements that can be implemented into the code for a second version.
Table of Contents
Introduction
Motivation
Algorithm
| SeqQueue
|
| SeqVRML
|
| rotation
|
| | Case 1: Triangle Center
|
| | Case 2: 1st Corner
|
| | Case 3: 2nd Corner
|
| | Case 4: 3rd Corner
|
| | Case 5: X-axis
|
| | Case 6: Y-axis
|
| | Case 7: Z-axis
|
| VRMLfile
|
| | Goal 1: Step *.wrl files
|
| | Goal 2: Color-sequencing
|
| | Goal 3: Animation
|
Improvement
Conclusion
Introduction
The idea of rotating a triangle about a three dimensional space is a simple concept to imagine. Imagine a triangle of any shape in space rotating about its center, any one of its corners, or around an infinite line inside or outside this triangle. This series of rotations can be represented as three points in space that rotate about specific reference points in space. Mathematically vector algebra and geometric relationships can manipulate these points to undergo any type of rotational sequence. Visually, computer graphics codes, such as VRML v2.0, aid to illustrate the rotational pattern of these points through animation.
Motivation
Due to my strong interest as well as research focus on constructing geometries trough computer algorithms/programming, I desire to work on a "novel" project from beginning to end. Hence, I plan to reinforce the many topics covered in class by working on an idea (or series of ideas) that are, in part and in the whole, different from homeworks done in class and previously performed research. Due to, what I feel, are weak points in the mastery of some topics covered by this coarse, I hope to use this opportunity to strengthen my skills competency of each topic practiced. Therefore, I a plan to incorporate many of the topics covered in the Advanced Topics in Engineering: Computational Geometry ( ME24-384) class by using vector algebra, transformation matrices, algorithms, C programming, convex hull identification, and VRML language to present the general rotation of a triangle in three-dimensional space.
Algorithm
The code is broken into two subroutines which, in combination, present the rotation of a triangle about a three dimensional space. SeqQueue asks the user for the triangle corner coordinates as well as the rotational sequence desired. SeqVRML runs each point through "linear algebra" algorithms of any one of 7 cases of rotations and prints each new triangle-point coordinate onto a *.wrl file.
SeqQueue
SeqQueue acts as a collector of data from the user. First the user is prompted for the x, y, and z coordinates for all three triangle corners. Next the user is informed of the three classes of rotations: about the center of the triangle, about a corner of the triangle, and about any one of the reference axis. The user is prompted for the number of rotations desired (i.e. n rotations), and rotation class desired (in the order of first rotation, second rotation, ...., nth rotation). If the third class of rotation is picked, the user is prompted to specify the fixed references axis about which the rotation is to occur: x-axis, y-axis, and z-axis. If the second class of rotations is picked, the user is prompted to specify about which corner the triangle will rotate about : 1st user specified point, 2nd user specified point or 3rd user specified point. Once a rotation is picked, the degrees of rotation is asked of the user ( this angle is then converted to radians for the code to use in Atan, Sin & Cos calculations). Finally the direction of rotation is requested by the code : clockwise or counter-clockwise. If clockwise is desired, then the rotation angle is given as a negative value. Finally, the initial position of the triangle corners are written on a *.wrl file.
SeqVRML
This subroutine loops n-times the two subroutines: Rotation, VRMLfile.
Rotation
This subroutine calls up any one of the seven cases of rotation as well as the time between rotational pinpoints/frames that the *.wrl will show (i.e. the time span between rotations). In each case the points are rotated under a subroutine called ThreeDRot, which rotates every point about a specified "center point" under a three-dimensional rotational matrix.
Also in the first four cases, the position vector of the center about which each point is rotated does not necessarily make a right angle to the plane of rotation. Hence another subroutine, called "Ntranslate", finds the z-intercept of the center's position vector. Given an x and y coordinates of the normal vector z-intercept, the triangle is then translated so that this z-intercept lies on the origin of the fixed reference axis. This concludes the algorithm of Ntranslate. However after the Ntranslate subroutine, the rotation occurs and then the new triangle position is translated back to the x and y coordinates of the normal vector's z-intercept location.
case1: Rotation About the Center of the Triangle
By far the most difficult case to construct an algorithm for. Since the center of the triangle must first be found , an iterative process is performed as follows:
1. The initial setup (before the iteration)
The position of the center is initialized as the average of the three triangle corner positions. This position is not the desired position because it doesn't guarantee that all three position values lie on the same plane as the triangle does (i.e. solving in two dimension works, but in three dimensions it doesn't).
2. Linear Algebra /Geometry Logic
The shortest distance from the center of a triangle to each of the three sides of the triangle are equidistant. Therefore using the two linear algebra formulas (P = Po + tv & v(c - P) = 0 ) to find the points on each edge where the shortest distance from the edge to center is calculated, each distance can be compared to the other.
3. Algorithm
Step 1: Calculate each scalar position value (i.e. "t") for each edge point short to the center position,
| Step 2: If the scalar position value is greater than one, then set to one. If the value is less than zero, then set to zero (i.e. the "edge point" must be on the triangle edge segment),
| Step 3: Solve for the actual distance from the center point to the "edge point",
| Step 4: Check if all three distances values are the same: if so then end intersection; if not then adjust the center's x, y, and z values by using a simple one-point iteration.
case 2-4: Rotate About the Center of a Chosen Corner.
This method simply sets the center as one of the corners and then rotates the other two corners about the specified corner.
case 5-7: Rotate About the Principle Axis of Choice
This simple rotation requires that each corner has a different point of rotation . The position of each center is the principle-axis dimension of that point. for example a point with a value x=2, y=3 & z=4 will have a center at x=2 y=0 z=0 if the point rotates about the x-axis, x=0 y=3 z=0 if the point rotates about the y-axis, and x=0 y=0 z=4 if the point rotates about the z-axis.
VRMLfile
The desired sequences will then be made visible by the user via a *.wrl. There are three incremental goals desired for the VRML presentation of the triangular rotation:
1. Show each step in the sequence of separate *.wrl files in which the user will be instructed as to the sequence of *.wrl files to open,
2. Present each step as several "dynamic" *.wrl files that will show the "movement" of the rotation as a set of triangles with different colors as it rotates (i.e. from blue to red),
3. Present the full sequence as a "smooth dynamic" *.wrl file (a concept not covered in class).
In the main program, a variable named 'goal' actuates the subroutine, VRMLfile, to write a *.wrl file of type 1, 2, or 3. Therefor, the presentation of these rotational sequences is not controlled by the user, but rather the programmer. However, if the user knew the C programming language, changing the variable 'goal' could been done according to the user's discretion.
Goal 1: This file is written in VRML v1.0 because it only requires a *.wrl viewer that will draw three points and a reference axis. This one is by far the easiest, yet less impressive and most hard to follow when using on a VRML viewer.
Goal 2: Calculating the intermediate rotational steps from one desired position to the other is done in five frames (beginning position and ending position included). The beginning position will be in blue, and the ending position will be in red. The three frames in between will be a mix of red and blue, symbolizing the transition of position and making it easier for the viewer to follow the rotation. This is considered more dynamic than the first type of presentation, but will still be considered choppy since many *.wrl files will have to opened up to realize the complete rotational sequence. This file is also written in VRML version 1 language.
Goal 3: VRML version 2 has an animation function that creates an object and moves it to another specified position in a specified amount of time. To move an object from one position to another, a trigger, timer, engine, and target step must be performed in sequence. This chain of sequencing in VRML is called an event path. The timer creates and "event" to initialize the animation. The timer keeps track of the fraction of the animation sequence that has gone by and how much time the animation must take. The engine determines the exact parameters of the animation for a given time span or moment. The target sends the coordinates calculated by the engine the object to be animated.
I planned to rotate each step at 1/4 second per 10 degrees. However, since VRML version 2 only has a linear interpolator as an engine, I am currently trying to learn the Java language to create a script that would interpolate the motion in a curved path.
Improvements
There are several factors that this code hasn't taken into account or needs improvement on:
1. Rotations Greater than 360 degrees:
If a rotation is greater than 360 degrees, then the effective difference from beginning to end of the rotation will be the only rotation seen (this is especially relevant in an animated presentation format). For example, if the rotation desired was 560 degrees, the code will only calculate for and display a rotation of 180 degrees.
2. Solving for the Center Position of the Triangle:
There could be a better way to solve for the center of the triangle without an iteration process being necessary. However, since some values of the unknowns solved for have limited ranges (i.e. 0 < t < 1), the convergence to the final solution shouldn't take very long (this is of coarse a speculation and not proven mathematically).
Conclusion
The effect of constructing this code has allowed me to utilize all the knowledge of material covered in class, and more. Finding the center of the triangle and normal vector of the center to the triangle plane have given me practice in linear algebra. Translation of the triangle (cases 1-4) and the three dimensional rotation of each point allowed me to practice with transformation matrices. Conversion of vector algebra and transformation matrices challenged my skill of effective algorithm creation. C programming knowledge was reinforced, with a few new things learned (e.g. Switch-Case statement). Convex hull identification was never used, yet due to the simple geometry of the problem, this was unnecessary to use . Finally my understanding of the VRML language moved to the use of a higher and more complex version than I have used before. Hence this "simple" exercise of rotating a triangle about a three dimensional space has developed some very non-trivial results, skills, and knowledge at the end.
|