A three-sided polygon: Some characteristics
The triangle polygon possesses numerous characteristics that make it the perfect building block for more complex structures to be rendered.
Each triangle is inscribed in its own plane
The first and most important characteristic would be that the triangle is the only polygon that is inscribed in a plane. The three vertices that compose the triangle will occupy a common plane, no matter their distance or relative position. The assurance that a polygon is flat is a critical aspect of its usefulness. By finding the cross product of vectors implied by the polygons's vertices, we can find the normal to the polygon's plane. Once this normal becomes available, we can then apply any desired shading technique on the polygon's surface.
Polygons can share vertices and edges
Another advantage of polygons, not just triangles in this case, is that they can have common vertices or edges. This characteristic is used in one of the oldest 3 D modelling data structure, the polygon mesh. Since each polygon can possibly have edges of different lengths, this flexibility can allow for the creation of smooth appearing larger volumes. The illusion of smoothness in the curves of the object can be controlled by either augmenting the number of polygons involved in the mesh, or by other more computationally economical rendering techniques like normal manipulation or texture mapping, topics that, due to time limitations, will not be addressed in great detail in the present blog.
As the complexities inherent to creating polygon mesh are beyond the scope of this blog, we will now examine the ray polygon intersection:
The triangle polygon possesses numerous characteristics that make it the perfect building block for more complex structures to be rendered.
Each triangle is inscribed in its own plane
The first and most important characteristic would be that the triangle is the only polygon that is inscribed in a plane. The three vertices that compose the triangle will occupy a common plane, no matter their distance or relative position. The assurance that a polygon is flat is a critical aspect of its usefulness. By finding the cross product of vectors implied by the polygons's vertices, we can find the normal to the polygon's plane. Once this normal becomes available, we can then apply any desired shading technique on the polygon's surface.
Polygons can share vertices and edges
Another advantage of polygons, not just triangles in this case, is that they can have common vertices or edges. This characteristic is used in one of the oldest 3 D modelling data structure, the polygon mesh. Since each polygon can possibly have edges of different lengths, this flexibility can allow for the creation of smooth appearing larger volumes. The illusion of smoothness in the curves of the object can be controlled by either augmenting the number of polygons involved in the mesh, or by other more computationally economical rendering techniques like normal manipulation or texture mapping, topics that, due to time limitations, will not be addressed in great detail in the present blog.
 |
| Dolphin triangle polygon mesh. (Image courtesy of Wikipedia) |
First step in Ray Polygon intersection: Ray plane intersection
Glassner[1] suggests a three step approach into dealing with ray-polygon intersection:
- Find the plane the polygon is inscribed in
- Verify if the ray intersects with the plane
- If the intersection is positive, verify that the ray is within the polygon
Finding the polygon's plane
There are many way to find a specific plane that is related to a series of vertices: The method we chose involves creating two vectors from two pairs of points from our polygon, as those vertices are instantiated when the polygon object is created. We then find the normal of these vectors through the vector cross product operation.
Linear algebra concept: Cross Product
The cross product of 2 vectors will create a third vector perpendicular to both original vectors simultaneously. This cross product can be determined by the vertice's coordinates.
Cross product utility method
Since the cross product is a relatively simple formula, a java utility method can easily be implemented. It is a member method of the polygon class and is called every time a polygon object is created.
Linear algebra concept: Cross Product
The cross product of 2 vectors will create a third vector perpendicular to both original vectors simultaneously. This cross product can be determined by the vertice's coordinates.
Cross product utility method
Since the cross product is a relatively simple formula, a java utility method can easily be implemented. It is a member method of the polygon class and is called every time a polygon object is created.
public double[] get_normal(){
// we will find vector u and v and then find n with cross product
// create vectors u and v from vertices of triangle, save them in object members
for(int i = 0 ; i < 3 ;i++){
this.u[i] = vertice1[i] - vertice0[i];
this.v[i] = vertice2[i] - vertice0[i];
}
this.n[0] = (u[1] * v[2]) - (u[2] * v[1]);// x coordinate of normal
this.n[1] = (u[2] * v[0]) - (u[0] * v[2]);// y coordinate of normal
this.n[2] = (u[0] * v[1]) - (u[1] * v[0]);// z coordinate of normal
for(int i = 0 ; i < 3 ; i++)
if(this.n[i] == -0.0)
this.n[i] = 0.0;
// normalise n before sending it
this.n = this.normalise_vector(this.n);
// we can now find ABCD of plane to save them for later use for D, just use abc on one point from triangle
this.plane[0] = this.n[0]; //A
this.plane[1] = this.n[1]; //B
this.plane[2] = this.n[2]; //C
this.plane[3] = -1 * (this.n[0] * vertice0[0] + this.n[1] * vertice0[1]+ this.n[2] * vertice0[2]); //D
return n;
}
Defining the plane: Cross Product and a point
The implicit polygon's plane equation can then be derived from the polygon's normal and by choosing one vertice. Once again, the ray plane intersection can be expressed in terms of t distance units by substituting the ray equation into the plane's equation and solving for t. The complete details of those operations can be found in Glassner[1] (pp 50-51).
Finding if the ray intersects with the inside of the polygon
The author will mention that of all the algorithms used up to now, the one used to verify if the ray strikes the polygon on the inside is the most complicated. After evaluation, the author has chosen to steer away from Glassner's solution of firing in-plane rays from the ray plane intersection point [1] (pp 53 54) to a solution involving parametric equations, cross and dot products derived from those already acquired. The complete solution can be found here Ray polygon intersection
The author will readily admit that some elements of this solution involves linear algebra concepts that have not yet been fully understood, which made the implementation somehow time consuming, but still successful.
 |
| Success! Our first Phong shaded polygon |
Polygons and the Phong Reflection Model
One of the aspects of the polygon shading algorithm that remains clearly understood is the Phong model can readily be applied to polygons once their normal have been found. One important characteristic of in-plane polygons is the polygon's normal remains constant on all the points of the surface of the polygon. Since the angle of the ray with the normal will change depending on which pixel is rendered, the Phong model will add nuances to the colours of the object, creating the illusion of three dimensions. In the other example below, a horizontal polygon is stretched to a large size to simulate a flat surface extending to the horizon.
 |
| Polygon stretched to simulate a horizontal plane |
Once the rendering of simple polygons has been achieved, it will be easy to notice the inherent complexity in creating larger shapes; Polygons, opposed to spheres, have no definite shape. This will create problems when wanting to build more complex elements as finding the appropriate vertice coordinates cannot easily be guessed. Even building a simple cube will require 12 polygons. If this cube is to be shifted as so to be visible in a perspective point of view, finding the vertice's coordinates will be daunting. The solution to this problem resides in the use of transformation formulas which will recompute the coordinates according to the nature of the transformations, be it rotation, shearing, stretching, etc... This topic will be investigated by the author in the future.
