flipcode - 3D Geometry Primer: Chapter 2

3D Geometry Primer: Chapter 2 - Issue 01 - Appendix
by (26 August 2002)

Introduction, Vector3D and Point3D

Hi there,

Parallel to chapter II (Primitives In 3D Space) of this primer, I will release some example code to show you how an implementation of all these rather theoretical things can be done. Each time a subject is finished, I'll release the according files and explain some details about it. Today, you'll get a bonus packet since I give you both Vector3D and Point3D.

"Life is funny", Bram "Bramz" de Greve (1980-...) Belgian weirdo and author of the 3D Geometry Primer

Listen Very Carefully, I'll Say This Only Once ...

All code that will be discussed here is written for educational purposes only! It's not written for fast performance. Well, sometimes it is, like there are inlined functions all over the place, but fast performance is not the main goal here. According to some people, doing it fast and furious is not really necessary anyway. See it the one way, or see it the other, but I've tried to write them in a way so that you can see how the class works, how it is built, what elements you can find in it. If it is too slow, I'll leave it to you as an exercise :)

Many people will disagree with my choice of implementation. And it's their good right. It's my belief that the way I've done it, is the good way. But everyone may have his own conviction, the one more justified than mine, the other less ... I've tried to explain every choice I've made, so that you could see why I think it's better than the other ways. But it's up to you to decide if I'm correct. If you say "wtf, I know better", then you should make your own choice. I'm only trying to give you a guide here, not the bible. But at least, make sure you have a reason why you choose that specific way ...

Also, all example code is released under the GNU Lesser General Public License (LGPL). That might sound a bit heavy for this, but it's my way to cover myself. Anyway, it's free example code you can use freely in your projects or change if you want to. See LGPL for more details if you want.

On To The First Structure: Vector3D

Structures and Contructures

The first example consists of one file Vector3D.h and contains the structure Vector3D. It's the basic of all further arithmetic that will come here. Any math needed be done on points, lines and planes will be done by using vectors. If you want to learn more about vectors, I refer to chapter I of the geometry primer.

I've chosen to use a struct and not a class to implement Vector3D. This is according to a rule of thumb by Bjärne Stroustrup who uses struct for classes with all their data public, and class for classes with private data. Vector3D has three member variables: float x, y, z. I've kept these public so you can access them very easily. That I don't hide these members is not a problem, since the structure doesn't "control" the variables. I mean, you can freely change the coordinate values without making the vector invalid. So there's no reason why it should be private. All higher stuff will keep their member data private and thus will be implemented as a class.

You'll find two constructors Vector3D() and Vector3D(const float x_, const float y_, const float z_) which is all you need. The default contructor initializes the vector to the null vector (0, 0, 0). Copy constructors and assignment operators are implemented automatically by the compiler. Since the member data is public you don't need accessors, but I still provided two methods void set(const float x_, const float y_, const float z_) and setNull(). The first to set the three values at once, the second because it's nicer than calling Set(0.0f, 0.0f, 0.0f).

Operation Operator Overload

All operators +, -, *, /, +=, -=, *= and /= have got their implementation. * is used to do the scalar multiplication of a scalar and a vector, and it's overloaded in two versions f * V and V * f. Notice that both result in the same vector:


Vector3D operator*(const Vector3D &v, const float f);
Vector3D operator*(const float f, const Vector3D &v);

Many times I've seen people overloading operator* to take the dot product too: float operator*(const Vector3D &v1, const Vector3D &v2). And I've done it too in the past. Now, I've decided to not do it anymore for the following reasons:

You get the danger of confusing the scalar multiplication with the dot product. In code, it may be sometimes very hard to see what * is used for.
You could also choose to overload operator* for doing the cross product or the componentwise product taking two vectors. It may be not clear to other people what product you've choosen, while it is clear when you multiply a scalar and a vector. There's only one way to multiply a scalar and a vector, there are many to multiply two vectors. Instead I've created other functions for these multiplications.

Operator overloading is something needed to be done with care! According to Jesse Liberty :Operator overloading is one of the aspects of C++ most overused and abused by new programmers. It is tempting to create new and interesting uses for some of the more obscure operators, but these invariably lead to code that is confusing and difficult to read. Of course, making the + operator subract and the * operator add can be fun, but no professional programmer would do that."

I've seen people overloading operator% to take the cross product, because the % reminds to the cross ×. I've seen people using operator^ to do that and I've seen them overloading operator| to scale a vector down to a certain length. In fact, I've been doing the very same things back in the days I hardly knew the difference between a class and struct. Anyway, these are all examples of abused operator overloading and shouldn't be done.

You should always keep in mind that other people will read your code. Maybe you think it will never happen, but what if you're in trouble and you need to post a piece of code in the forums? If you use operators in exotic ways, they won't understand what you're doing unless they've seen your headers. And that's mostly not the case.

Dots and Crosses, and other stuff

Instead you should use well named functions like dot and cross to do that. In that way, people will immediately recognize what they stand for. I've also implemented a third product triple doing the triple product. You can see that I've implemented it by using the dot and cross product instead of writing it out. And then we also have the pointwiseMul and pointwiseDiv. They do the pointwise multiplication and division of two vectors.

After some rumblings on the subject cross product, I've added this alinea here. The definition of a cross product is rather ambiguous. You can define it in two ways:

Cross products always form right-handed triads, even in left-handed coordinate systems. Mostly definied with the right-hand rule.
Cross products always form positive triads. i.e. right-handed triads in right-handed coordinate systems, and left-handed triads in left-handed coordinate systems. Mostly defined with some kind of determinant of a matrix

In most resources like MathWorld, ... You'll find both definitions without it clearly mentioning that they are different. It makes it somehow ... confusing because both definitions you'll find give the same result in right-handed coordinate systems, but the exact opposite result in left-handed coordinate systems.

What definition you take, depends on your needs. But I've choosen for the latter (2nd definition) for simple reasons:

I always believed (until now) that the second one was the only correct definition of the cross product.
Because I didn't know about this ambigiousity when I was writing chapter I of the 3D Geometry Primer, so until now I've used the second definition all over the place.
The second definition uses the same numerical formula for both left-handed and right-handed coordinate systems. i.e. you can use the same code ...

Especially the last reason is very interesting, because that way, we'll be able to use the same vector class in both right-handed and left-handed coordinate systems. So this Vector3D will be multi-handed :)

Equal or Not Equal

I've also overloaded operator== and operator!= to check if two vectors are equal or not. However, it's a bit tricky because the you can't feed any tolerance in it. Both vectors must be *exactly* equal. No single bit may be different! At least, you can't feed a tolerance in an easy way. There are always workarounds (e.g. setting a static variable that holds the tolerance for all operations that need it), but I've choosen not to do it to keep it simple. And tolerances shouldn't be standard anyway! There was also a big rumble on this. Anyway, if you need tolerances, help yourself :)

Many people would also overload operators <, >, <= and >= to order vectors in some way. But they shouldn't. Why? The only logic way of sorting vectors would be comparing there norm: e.g. U < V if ||U|| < ||V||. But that would lead to an ambigous meaning of operators == and !=. If the others test on the norm, you may expect that these two also check on it: U == V if ||U|| == ||V||. That's of course nonsens! Two vectors are only equal if their three component values x, y and z are equal, not if their norms are equal! So, to avoid this ambigous fact, you shouldn't overload this operators. You can always use getNorm() or getSquaredNorm() if you want to test on the norm of the vector.

And Furthermore

Further, I've written some extra methods:
normalize(): scales the vector to unit length: V /= ||V||
getNorm(): returns the length ||V|| of the vector.
getSquaredNorm(): returns the squared length ||V||². This can be handy in avoiding the square root of GetNorm(). So actually, this is an optimization trick :)
isNull(): checks if a vector is the null vector <0, 0, 0>. It's overloaded in two versions: one that checks if it is exactly <0, 0, 0> and the other that is feeded with some tolerance. The latter already returns true if ||V|| < tolerance.
isNormalized(): checks if a vector is a unit vector, i.e. if it's norm == 1. Again, it's overloaded in two versions: one without and one with a tolerance.

Points Taken As A Different Class

This is where most people disagree with me (thank you Max and Nick for not being most people :) Almost everyone says I should just use the Vector3D class to store a point. Well, call me crazy, call me dumb, call me stubborn as a mule or anything you like, but something in my undersized dead brain says I shouldn't do that! Something says I need to implement vectors and points in two different classes: Vector3D and Point3D. You can of course do what you like, but at least, give this Point3D class one chance!

First the reasons why it's appropriate to use two different classes:

The OOP reason: Vectors are one class of objects and you can do all sorts of stuff on it: addition, scaling, normalizing, cross products, dot products, etc., etc. ... Points are another class of objects. You can't scale points, you can't normalize them, nor you can calculate the cross or dot product of two points. But you can calculate the distance between two points, and that's something vectors don't have. A vector has properties a point doesn't have, and a point has properties a vector doesn't have. That means they can't be one and the same thing. You even can't use public inheritance to implement a point, because you can't say a point IS-A vector.

But you can say that a point IS-IMPLEMENTED-IN-TERMS-OF a vector! This is true because a point actually USES a position vector to do what it needs to do. This means that we can choose between private inheritance or containment. I've choosen for containment, and the most logical choice is to let a point contain a vector, it's position vector. I've choosen this because it clearly shows that a point USES a position vector. And this way, you would be able to let a point contain more than one position vector (in case you need its position vectors in more than one coordinate systems), but we don't care about this right now.
The function overloading reason: by using two different classes, you can overload functions so that they act differently on points and vectors. A good example is a transformation function: points will also be translated, vectors won't. Another is the contructor of a line. You can overload it to take a point and a direction vector or to take two points.
The performance cost that isn't the reason: most people argue that this kind of implementation asks more clock cycles than only using the vector class. Not true, since everything can be done by inlining. Since a point contains a vector, you can simply implement the subtraction of two points by inlining the subtraction of their two position vectors.

And why one shouldn't do it? Laziness. It takes some time to implement another class. And why should you implement a class while you can do the same job without?

But what the heck, we implement so many classes! And considered that this is only a small one, you can easily do it "between the soup and the potatoes" (OK Jaap, I admit it. It took me a little longer than 15 minutes :).

And now the real stuff. What's in it?

Structures and Constructors

Again, I've choose to use a struct for Point3D because of the same reasons as for Vector3D. I've tried to go fancy with the data structure. There's actually only one member variable, and that's the position vector Vector3D position. You can easily access this vector by typing somePoint.position. However, I've putted this position vector in a union with a nameless structure of three floats x, y and z. This lets you to access the component values of the position vector by bypassing the position name. e.g. somePoint.x = 1.0f will have the same effect as somePoint.position.x = 1.0f. Cool!

Again, there are two constructors: a default one and one that takes three coordinate values. Nothing more to say about that.

Overloading and Forwarding

Again a bunch of operators are overloaded. However, this time they do not implement the operations themselves, but they use appropriate operations of their position vectors. That way, we avoid reimplementing common stuff.

Some operations were not intended to be overloaded - like operator+(point, point), operator* and operator/ - because that's stuff that you usually can't do on points. You can't simply add two points, that doesn't make sense. If you don't understand this, then you should read again issue 8 of chapter I.

However, these operations are used in barycentric combinations of points. e.g. P = (A + B + C) / 3 is a valid statement because it's a barycentric combination, while Q = A + B + C is not valid. See issue 9 of chapter I for more info on this.

Anyway, Nick and I have tried to think of a "barycentrical safe" way to implement these operators. We wanted something that would allow P = (A + B + C) / 3 and give a compile-time error if you tried to do Q = A + B. Unfortunately, we couldn't think of an easy one that didn't use homogenous coordinates. Hence, I've implemented these operators as is ... You still can write P = (A + B + C) / 3 but Q = A + B won't give any compile-time nor run-time error although it's absolutely not valid math.

So, it's your responsibility to use these three operations operator+(point, point), operator* and operator/ in a correct way. If you use them, make sure you use them in a barycentric way!

REMARK: This does not count for the operator+ that adds a point and a vector! This operation is very legal! :)

Other stuff ...

Since we don't normalize, dot or cross points, we have only a few methods left to implement. These are isNull(), again with and without tolerance, set() and setNull().

That's it folks! We've survived our first round of coding. At least, I hope so :) Many appreciations to Altair for helping me fine tune the C++ thing of all this :)

Greetz from Belgium,
Bramz de Greve

Article Series:

3D Geometry Primer: Chapter 2 - Issue 01 - Appendix
3D Geometry Primer: Chapter 2 - Issue 01 - Points And Lines
3D Geometry Primer: Chapter 2 - Issue 02 - Appendix
3D Geometry Primer: Chapter 2 - Issue 02 - More About Lines
3D Geometry Primer: Chapter 2 - Issue 03 - Planes and Parametric Equations
3D Geometry Primer: Chapter 2 - Issue 04 - Cartesian Equations and Normal Vectors