Creating and Loading .OBJ Models

In order to have the ability to play around with OpenGL in a virtual environment other than a handful of randomly scattered polygons, I thought I better look into a bit of simple 3D model making.

A quick scour of the internet revealed that 3DS Max seems to be somewhat of an industry standard, however that requires a substantial investment so I looked for alternatives. Blender (http://www.blender.org/) seemed to be an open source favourite, matching much of what 3DS Max does so I decided to give it a go and download it.

The tutorials are pretty good on the website and get you going pretty quickly. Through the use of predefined meshes and the "snap" tool, I was able to knock up a curious looking little room fairly quickly, also defining vertex normals along the way. A particularly useful feature was being able to "triangulate" all the polygons in the model, thereby turning them all into a combination of triangles.

Once the model had been made, I chose to export the model as a .OBJ file. The .OBJ file is a file format defined by Wavefront, the group behind another 3D modelling tool, Maya. It defines information about the model in an ASCII text file. This has the downside of resulting in large file sizes but is apparently popular to use due to its ASCII format which is much simpler to read and load than a binary file such as the .3DS format. For this reason, I thought it'd be a good place to start with learning how to load and handle 3D models from files before moving on to more complex formats later.

Exporting a model to .OBJ format in Blender affords the option of including a lot of data describing the model in the output file. Since I'm just starting out, I've decided to only include vertex information and to exclude all the other information such as material and normal data which I will gradually introduce into my programs in future posts.

I quickly discovered the model information output to the .OBJ file isn't particularly object/program friendly. From various sources I was told that a lot of information is optional and quite often completely absent from the file. The information is typically given in sentences with a short code indicating the kind of information to follow. for Instance, a "v" at the beginning of a sentence indicates vertex data and is succeeded by three float values (x, y, z) separated by a space. Face information is presented in a similar fashion: prefixed by "f" and presenting a list of the indices of the vertices that make up the face with 1 being the first vertex defined and n being the last vertex defined in the file representing a model with a total number of n vertices.

With this file, one can read in the model information and reconstruct it in the OpenGL program. In order to do this I created a few classes that would store the model information so that the model can be passed around and accessed within the program with a single object. The method of reading in the file was pretty straight forward.

In terms of 3D modelling, the file was composed of the following elements:

• Vertices: prefixed by 'v' and containing 3 float values: the x, y and z coordinates of the vertex in the model relative to the model origin in Blender.
• Faces: A face refers to one polygon that makes up the model. Prefixed by 'f' and containing 3 integer values: the indices of the vertices that make up the face. The vertex index represents the nth vertex defined in the file, starting at 1, not 0.
• Object: An object is a smaller construction within the model. A model is made up of objects and an object is made up of faces. Objects are not represented within the file (an object name line can be added but is metadata) and a large model can be declared as just a single object. However, objects provide a logical structure to the model. They are represented by a vertex/faces block. E.g. the snippet of the .OBJ file above contains information for 2 objects.

After reading in a line from the file, the first character is checked and the corresponding method to handle that data type is called (vertex, face). Since faces can be defined anywhere in the file (in this case, after the vertex definitions for the vertices that make up the face), an object is processed after the final face declaration before a vertex definition. In order to do this, before a vertex is read and processed from the file, a check must be made to determine whether a face was just read and therefore we reached the end of an object. If so, the previously read information is stored in a modelObject class which is stored in the model object. By carrying on this process, the file is read in and a model object is obtained which is made up of modelObject objects which is comprised of faces which in turn store the vertices.

Displaying the model is simply a case of accessing the model object during frame drawing and looping through the objects and faces and drawing each face as a triangle.

Next I plan to include vertex normals to the model and describe how to use them to introduce lighting to a scene.

As an aside, I also learnt some interesting C++ tips from errors that I made. My C++ isn't good and my endeavour to learn OpenGL is also an endeavour to improve my C++ coding. The first thing I learnt is that declaring a new object within a code block without using the new operator, creates the object on the function stack and not the heap.

This means that as soon as the end of the function is reached, the entire stack for the function is deleted, including the new object i.e. it no longer exists. This means that if you were planning to use it in the future, the information will be lost and garbage will be used. In order to persist an object for further use in other parts of the program (e.g. via pointers), the object should be declared on the heap by using the new operator. Subsequently, the delete operator should be used when the object is no longer required otherwise a memory leak will be introduced.

This also lead on to the discovery of the Rule of Three, a C++ coding principle. This generally states that if within a class, you declare one of the following:

• Destructor
• Copy Constructor
• Assignment Operator

Then the other two should be implemented. This is particularly necessary for the case where a destructor is declared. This is because by declaring a destructor, you probably have non primitive data contained within the class that needs to be handled correctly (e.g. use of the delete operator). C++ generates a default copy constructor and assignment operator that only performs shallow copying. For most applications, this is insufficient. In order to fix memory related issues, a copy constructor and assignment operator function should be implemented which correctly control the copying of dynamic memory.

Within the OBJ loader program, I made this mistake and it caused object data that I had moved into the model object to be garbage once the temporary data I had used had been collected by the system. By implementing the copy constructor and assignment operator function within the necessary objects, logical copying of the data was performed and the integrity of the model data was maintained.

Sphere Intersecting a Polygon

It had become clear that being able to detect the collision of a sphere with a polygon was an important concept in terms of 3D graphics. Many Collisions are optimized by the use of a sphere or some other similar object to represent one of the colliding objects. This simplifies calculations greatly. Now to learn how!

Firstly, for a simple test case of this concept, I used a simple triangle and a wireframe sphere drawn using glut. The wireframe makes it easier to see any intersections.

The previous posts documented methods for checking for different forms of collision. These techniques can be used for the sphere intersection and modified if necessary. In order to check for the sphere intersecting with the polygon, three checks were necessary:

1. Check if the sphere lies completely outside the plane formed by the polygon
2. Check whether the projection of the centre of the sphere onto the plane formed by the polygon lies within bounds of the polygon itself.
3. If the projection of the centre of the sphere does not lay inside the polygon, check that the sphere does not intersect with the edges of the polygon.

Performing these checks is enough to determine if the sphere intersects with the triangle.

1. Check if the sphere lies out the plane formed by the polygon


If the sphere has a radius of 1 metre and the centre of the sphere is 100 metres away from the plane formed by the polygon, it is obvious that no collision can occur. To determine whether this is the case, we use a technique I described in an earlier post. Firstly we calculate the distance that the centre of the sphere lies from the plane by utilising the plane equation.

We then make one minor change to see if the sphere is intersecting the plane. If the distance of the sphere centre from the plane is less than that of the sphere's radius then we have an intersecting. For this reason, we take the absolute value of the distance (as the sphere can be either in front of or behind the plane) and compare it with the sphere radius. If it is smaller, we continue onto step 2 otherwise there is no collision and we can return false.

2. Projection of Sphere lies inside polygon

If the sphere does indeed intersect the plane, we need to perform more checks. We first need to find whether the point at which the sphere intersects with the plane is within the bounds of the polygon or not. How do we determine the point at which the sphere intersects the plane? Well if the sphere is indeed intersecting the plane, the number of points on the plane it intersects with is infinite. For this reason, we project the sphere's centre onto the plane as whether it lies within the polygon.

To do this, we use the distance that the sphere's centre lies from the plane, which we calculated in step 1. We then multiply this by the normal of the plane. Remember that geometrically speaking, by multiplying a vector by a scalar, we are moving along the vector by a distance determined by the scalar. Since we start at the plane and move along the normal a distance equal to the distance of the sphere from the plane, we obtain a vector that represents the offset of the sphere's centre from the plane.

Because this vector goes from the plane to the centre of the sphere, we subtract this vector from the sphere's centre vector to obtain a new vector that goes from the sphere centre to a point on the plane. This is the projection of the sphere's centre onto the plane and serves as our intersection point on the plane.

This technique is illustrated above. We know from test 1 that the sphere is intersecting the plane so we want to find whether the centre of the sphere is inside the bounds of the polygon. The normal of the plane N is multiplied by the distance of the sphere centre from the plane to obtain the offset vector N * d. We can then subtract this vector from the sphere's centre to obtain the same vector in the opposite direction, finding the intersection point with the plane, i.

Now that we know the sphere centre's intersection point with the plane, we need to know whether that point is inside or outside of the polygon. If outside, there is no collision and we must proceed to step 3. In order to determine whether the point is inside the polygon, we use the same trick as before, constructing vectors between the intersection point and the polygon's vertices and summing up the interior angles. If equal to 360 degrees, the point is inside the polygon and we can return true for the collision, otherwise it is outside. I discussed this technique in more detail in the previous post.

3. Detecting Sphere-Edge Collisions

So, we know that the sphere intersects the plane but that the projection of the centre of the sphere onto the plane lies outside the polygon. Surely there is no collision? Well actually, there remains one case where the sphere could still be colliding with the polygon. Take a look at the figure below.

Here we can see that the sphere intersects the polygon and yet our previous test would have found the intersection point of the sphere centre and the plane to be outside of the polygon and would have ruled that no collision would have occurred. For this reason, we need to perform a final test checking for collisions with the edges of the polygon.

In order to do this, we construct vectors between each pair of vertices, starting with the most bottom-left vertex and proceeding in a clockwise fashion. For each vector we find the point on the vector that is closest to the sphere's centre and check the distance between them. If the distance is less than the sphere's radius, the sphere must be intersecting the polygon and we can return a true collision.

How do we find the closest point on the edge vector to the sphere's centre? The following technique does just that.

Firstly, we construct the edge vector by subtracting the current vertex from the next vertex in the polygon. This provides us with a vector representing an edge of the polygon. We also normalize this vector as we only care about its direction, not its magnitude for reasons I'll explain soon. We then construct a vector from the current vertex to the sphere centre by subtracting the current vertex coordinates from the sphere's centre coordinates. This is what we now have:

The distance along the edge vector E of the closest point on the edge vector to the sphere's centre (c) is found by performing a dot product operation using the two vectors we just created. This is cd. Why is this? Well, remember that geometrically, the dot product means this:

That is, the dot product is equal to the product of the magnitudes of both vectors multiplied by the cosine of the angle between them. By performing a dot product between E and P we obtain the following:

However, remember that we normalized the edge vector, meaning that it's magnitude is 1, so it drops out of the equation, leaving:

Remembering simple trigonometry and observing that the P vector and the distance to the closest point on the edge vector forms a triangle, we can see that the dot product will give us cd since the hypotenuse of the triangle multiplied by the cosine of the angle gives us the adjacent edge, i.e. cd.

Now that we have the distance along the edge vector to the closest point, we can find the coordinates of the closest point on the edge by taking the coordinates of the current vertex of the edge and adding on the the edge vector multiplied by the distance to the closest point.

Now that we know the closest point on the edge to the sphere's centre, we simply use the euclidean distance formula to find the distance between the two points (d in the diagram). 

we then compare this with the radius of the sphere and if it is smaller, we must be colliding. If the distance is greater, there is no collision and we move on to check the next edge in the polygon. 

By performing these 3 checks, we are able to fully determine if a sphere is intersecting with an arbitrary convex polygon.