Content of the main course

• Article 1: Bresenham algorithm
• Article 2: rasterization of the triangle + clipping of the rear faces
• Article 3: Removing invisible surfaces: z-buffer
• Article 4: Required Geometry: Matrix Festival
  
  • 4a: Construction of perspective distortion
  • 4b: we move the camera and what follows from this
  • 4c: a new rasterizer and perspective distortion correction
• Article 5: We write shaders for our library
• Article 6: A little more than just a shader: shadow rendering

Code enhancement

• Article 3.1: It’s time to refactor
• Article 3.14: Beautiful Matrix Class
• how does the new rasterizer work

Communication outside Habr

If you have questions and do not want to ask them in the comments, or simply do not have the opportunity to write in the comments, join the jabber conference 3d@conference.sudouser.ru

This article was written in close cooperation (thanks to the creators of XMPP) with haqreu , the author of this course. We began a massive code refactoring aimed at achieving maximum compactness and readability. We deliberately chose to abandon a number of possible and even obvious optimizations for obtaining the most accessible code for learning examples.
P. S haqreu just the other day will post an article about shaders!

UPD: ATTENTION! The section, starting with numbers 3.1, 3.14 and 3.141 and on, will be about the intricacies of the implementation of the basis of the basics of computer graphics - linear algebra and computational geometry. About the principles of graphics writes haqreu , but I will write about how it can be clearly programmed!
UPD2: I express special thanks to lemelisk for careful study of the article and the indicated inaccuracies.

1. General Provisions

The previous articles of the cycle show that to write a software renderer you need to implement a fair share of algorithms and mathematical objects related to linear algebra and geometry. First of all, we are talking about vectors and matrices, of course. We use vectors and matrices of small dimensions, so it is convenient for us to place them on the stack. We implemented them using the vec<size_t Dim, typename number_t> and mat<size_t size, typename number_t> . In the comments to one of the articles, I showed that (at least when in the role of the GCC compiler), the use of cycles even in such small cases gives a shorter and more compact machine code, and also insures against silly typos (note the important study - "Effect of the last line" ) when element-wisely typed, for example, matrix multiplication operations.
The code in this article is written for the standard version of C ++ 98, so scary (return me auto!). Perhaps I will prepare a separate article with the same code, but using the latest standard. Hold on, templates with a variable number of parameters, there will be a job for you!

2 What is interesting in the process of merging and refactoring?

2.1 Universal use of size_t for array indices

Recall that clause 18.1 of the C ++ standard, referring to clause 7.11 of the C standard , defines size_t as an unsigned integer type. For us, this is convenient, because, firstly, it directly corresponds to the meaning of the index in the array, and secondly, to verify the fact that i really is within the array, we only need to check one condition: (i < _) instead two: (i >= 0) && (i < _). Inappropriate int will be removed from all places.

2.2 Strange for loop

Here is a for loop, which some might find odd: for(size_t i=Dim;i--;) {}; This cycle will iterate over all values ​​of i from Dim-1 to 0. The enumeration will start from Dim-1, because before entering the cycle body, it will first be checked that i is non-zero, then decrement i, and only after that - the entrance to the cycle . After the final iteration, we get i = 0 (the cycle should end), but we still need (in the sense of the operation i--) to subtract the unit from the unsigned i. This action is well defined by the standard, so nothing bad will happen - we just get a value equal to std::numeric_limits<size_t>::max() . Why was this cycle made, and not the traditional for(size_t i=0;i<Dim;i++) ? Two reasons. First: to show an example of the correct passage along i to the decreasing direction with an unsigned variable. You can often find an error: for(size_t i=Dim-1;i>=0;i--) compiler, seeing the identically true expression [unsigned integer]> = 0, will simply replace it with true: for(size_t i=Dim-1;true;i--) , which will lead to infinite looping. The second: such a record is shorter by as many as three characters. We will return to the for loop (as well as to the question “Which is faster, ++ i or i ++”).

We can go further:

the fact is that most of our operations are very trivial, and the body of the loop that executes them consists of one line. haqreu suggested doing this:

 template<size_t Dim,typename Number>vec<Dim,Number > operator-(vec<Dim,Number > lhs, const vec<Dim,Number >& rhs) { for (size_t i=Dim; i--; lhs[i]-=rhs[i]); return lhs; } 

In fact, we put our operation inside the loop header, making the loop body empty.

2.3 Template code for the vector

In our template for a vector, five methods are currently defined, two of which are operators: these are operators of taking constant and non-constant references to the vector element []. Using the assert macro from <assert.h>, they check that the index passed to them remains within the array, which is very important for detecting completely stupid errors. In the release version, we will add -D NDEBUG to the compiler keys, which will remove the macro from the code. According to Murphy's law , after that everything will have to break, but we will overcome it.

The fill method (const number_t & val = 0) fills the vector with a constant. The default is zero.

The methods norm () and normalize () are designed to calculate the length of the vector and its normalization, respectively.

 number_t norm() const { return std::sqrt( (*this) * (*this) ); } 

To calculate the norm, we use the fact that this is just a square root of the scalar product of a vector with itself. Very briefly, capaciously, and at the same time closely connected with theory.
Now normalization of the vector:

 vec<Dim,number_t> normalize() const { return (*this)/norm(); } 

Again, everything is exactly by definition: taken themselves and divided by their own length. Please note that this function returns a normalized copy of the original vector, and does not change its coordinates so that it becomes single.
Also note the widespread use of const in this code. This, on the one hand, protects against stupid mistakes, even at the compilation stage. On the other hand, const gives the compiler more information for optimizations. Also note that there are no inline directives here. This is due to the fact that we will do all the optimization later. In addition, with -O3 GCC becomes so smart that it performs embedding itself. Whether it will automatically embed our functions without explicit inline, we will again be considered in subsequent articles.

2.4 Binary operations on vectors and scalars

Operators of binary operations are outside the class vec. They fully comply with the definitions of these operations in theory:

I draw your attention to the tactics of applying the left operand (lhs) in the last three implementations. We receive a copy of it at the entrance, after which we work on this copy and return it. If we received it via a constant link, we would have to do the copying on our own. Here, the properties of our vectors and C ++ language coincided very well, which we used. In the implementation of scalar multiplication, we don’t need to copy vectors at all - we do all the work with a constant link.

2.5 Separately - on the implementation of the division of a vector by a scalar

Since we all know mathematics, we can say with pleasure: “To divide a vector by a scalar, we can use multiplication by the amount opposite to this scalar.” And set up this:

 /////////////////////////////    template<size_t Dim,typename Number>vec<Dim,Number> operator/(vec<Dim,Number > lhs, const Number& rhs) { return(lhs*(static_cast<Number>(1)/rhs)); } 

The important point - as we did with the unit - we wrapped it in static_cast <> so that it always had the correct type when dividing. However, having a simple test:

 #include <iostream> using namespace std; int main() { const double a=100.8765; const double b=1.2345; cout.precision(100); cout << a/b <<'\n' << a*(1.0/b)<<'\n'; return 0; } 

We can see that the results did not agree:

 81.7144592952612 356384634040296077728271484375 81.7144592952612 498493181192316114902496337890625 

We obtain a more accurate value of the relationship using maxima:

 (%i5) fpprec:100; (%i6) bfloat(100.8765/1.2345); (%o6) 8.17144592952612 356384634040296077728271484375b1 

We see that the value obtained by direct division is more accurate. This is due to the accumulation of error in arithmetic operations. Therefore, we will not be greedy, but write a separate implementation of the division operator:

 template<size_t Dim,typename number_t>vec<Dim,number_t> operator/(vec<Dim,number_t> lhs, const number_t& rhs) { for (size_t i=Dim; i--; lhs[i]/=rhs); return lhs; } 

2.6 Operation of immersing a vector in a space of higher dimension

We need it in one of the versions of the rasterizer. The essence of the operation is that we form a vector of higher dimension, fill the method fill it with a constant, which we passed, and then we copy into it the coordinates of our vector of smaller dimension.

 template<size_t len,size_t Dim, typename number_t> vec<len,number_t> embed(const vec<Dim,number_t> &v,const number_t& fill=1) { //   vec<len,number_t> ret = vec<len,number_t>::fill(fill); for (size_t i=Dim; i--; ret[i]=v[i]); return ret; } 

2.7 Vector design operation

This operation, on the contrary, from a vector of higher dimension makes a vector of a smaller dimension, the extra coordinates are simply discarded:

 template<size_t len,size_t Dim, typename number_t> vec<len,number_t> proj(const vec<Dim,number_t> &v) { //  vec<len,number_t> ret; for (size_t i=len; i--; ret[i]=v[i]); return ret; } 

2.8 Redefining the operator << to output vectors into the ostream stream

For debugging it was necessary to implement the output of our vectors to the terminal. To do this, we have further defined the <‌< operator for the case when the left argument is a reference to ostream, and the right argument is our vector or matrix. Now we can simply and habitually write cout <‌ <myvec:

 template<size_t Dim,typename number_t> std::ostream& operator<<(std::ostream& out,const vec<Dim,number_t>& v) { out<<"{ "; for (size_t i=0; i<Dim; i++) { out<<std::setw(6)<<v[i]<<" "; } out<<"} "; return out; } 

3 Conclusion

In the subsequent clarifying articles of section 3.1 ... we will show the details of the implementation of working with matrices. There will even be recursion on the templates. See you soon article!
And yes, I remind you that soon haqreu will post an article about shaders!