Articles

Introduction

Hi, I feel I should start this tutorial with a short introduction to who I am. My name is Chris Gilbert and I have been programming for around the past 5 years. My ventures into programming started in the days of DOS with nothing more complex than batch file writing and dabbling in QBasic. Then I got a copy of Visual Basic and stuck to VB for a few years when about 2 years ago I came across C++ for the first time. I now develop almost entirely in C++.

This Article

If you have ever worked on a 3D app/game, you will know the importance of the 3D polygon structure. If you have never worked on a 3D app or game, then you might been having a few worries about how to organise such an important structure. This tutorial will describe how a polygon structure should work, what to do and not, and will provide a base for other more advanced tutorials.

Step 1: Planning

That's right we're not jumping right into code but I promise we will eventually. Before we start programming our camera class we should figure out what sort of stuff we want it to do. When I started writing this class I came up with a list something like this...

First off we have a triangle below with a point in it.

We all see that the point is in the plane but how do we make the computer realize this?

At this point we only use the x and y coordinates to determine if the point is in the plane.
We can create three new triangles using the point as in the picture below.
I have given each corner of the original triangle coordinates as have I given the point one.
The triangle could have z coordinates too but we ignore these right now.
I have named the sides of our first sub triangle to a, b, c as have I named the angle between b and c to A.

This could be called the XY plane.
As we all know a complete circle is 360 degrees or 2p.
The angle A is represented by the segment of the dotted circle that’s inside the sub triangle.
The goal is to calculate the angle A for each sub triangle and if the point actually is in the triangle plane the sum of all the angles A should be 360 degrees or 2p

But how to calculate the length of the sides a, b, c?

To calculate the distance between two point you use the formula

So to determine the length of side a it would go like this

and side b

side c

And now how to finally determine the angle A we use the formula

We have the length of all the sides in the sub triangle so we just put them in there.

So now we have the angle of the first sub triangle and we just repeat the calculations for all the sub triangles.
If we add them all together the result should be 360 degrees if the point actually is in the triangle plane.

Now you may ask, but I wanna test in 3D so what about the z axis? Look at the picture below. It is the same triangle as before but now where looking at it from above.

We use the same calculations but now we put in the z coordinate instead of the y coordinate.

This could be called the XZ plane and calculate it just like the XY plane.

The same goes for the ZY plane that could look like this “looking at the triangle from the side” as you may suspect we use the z and y coordinates to make up our triangle.

Finally

If you calculate all of the angles in each plane and if the sum off the angles in each plane is 360 degrees then the point is actually in the triangle plane.
Remember: treat each plane as a simple triangle.

I beleive the author's aim is to determine if the point is in "triangle's plane", while it can be both "inside and outside of the triangle". In this case, I don't think there is a need to use such time-consuming operations as: sqr() sqrt() and cos(), which are actually used.

Using the notation used in the article, let me introduce the slightly different method, that is used in analytical geometry. It is pretty simple and deals only with some multiplications: Say, the triangle is given by the three points:

A ( xA, yA, zA)
B ( xB, yB, zB)
C ( xC, yC, zC)

and we want to determine if the point

M ( x, y, z)

is inside that triangle.

It is necessary (and more than enough) for the three vectors "MA", "MB" and "MC" to be co-planar. That is - one of them is a certain linear combination of others.

From analytical geometry we know, that 3 vectors are co-planar if:

|x-xA     y-yA     z-zA|
|x-xB     y-yB     z-zB| = 0
|x-xC     y-yC     z-zC|

(that is: det((MA)...,(MB)...,(MC)...)=0)

But to calculate a 3x3 determinant very few calculations are needed! Something like 12 multiplications and 6 sumations. After that we have to calculate the deviation of the result from 0 (like in the article we calculate the deviation of the total angle from 360 deg) to find out if the point is inside the triangle plane!

That's all about it! So instead of calculating the unnecessary information about triangles, sides, lengths, angle sizes, etc for 4 triangles, we only calculate a 3x3 determinant!

This can also be used to determine if the point is "inside" the triangle and so on...

- Christian Westman