The editor used in this video is Joe, and it is being run in _That Terminal._ DOSBox was not used, neither was _That Editor._ The compiler used is GCC 10.0.1, and run in Debian GNU/Linux. The source code is now up at bisqwit.iki.fi/jkp/polytut/ . You will need GCC 10, but with small changes it can be compiled with as early as GCC 7. ERRATA: The compile-time for-loop is not C++11, but C++20. It depends on fold expressions (c++17), std::index_sequence (c++14), and lambda templates (c++20). *A reminder: Do not reply to **_this post_** if you want me to see your comment. Post your words as a new comment, not as a reply, unless you are addressing the contents of **_this comment_** specifically. TH-cam does not show creators new replies, it only shows new comments. If you reply here **_I will not see it_** unless I manually check for it.* If you are addressing a comment someone wrote, then you _should_ reply it, though.
Nice! I couldn't quite place it, but now you're triggering memories of a friend I had who was a big fan of Joe. It's nostalgic to see it again. I should go check it out again, and see how older-me feels about it!
@@pw1169 I don't get whats so bad it about it honestly, the common complaint I hear is from Go/Rust fanatics who just keep complaining about C++'s use of iterators vs theirs.
@@ducksoop.x I'm not really a Go/Rust fanatic, but I gotta admit C++ is getting pretty hard to read, I'd say more than Java even (yeah). constexpr __noexcept virtual auto fn(args) -> return_val {}, etc. (this is not correct code cuz I haven't coded in C++ in a loong time, but you get the point). It might be easy if you have been following it since a long time, but jumping in the middle, it is really overwhelming. Atleast its learning curve is much better than Rust's.
This brings back lots of late night memories writing my own software engines. Except it was usually in C and inline assembly. No one talks about this stuff anymore since 3d hardware took over. I look forward to the rest of this series.
Bisquit explained 10 books and my entire course of computer graphics with that intro and I understood better thia video than the other ones I mentioned. Thank you so much! Please take your time for explaining some SDL functions!
Man, I can't tell you how much I love these kinds of videos. I have tried to make a basic 3D engine just for fun, but could never figure it out, so I love stuff like this. Please make more of them. You have knowledge many of us don't.
As someone who knew most of the things in this video already and has developed simple rendering engines himself, I still very much enjoyed your video. This would've been tremendously helpful back when I first learned all of this, and still today it is a very nice presentation of the core aspects of computer graphics. Also, I like the way you casually use C++20 in your projects, few people really do that.
I loved the "inefficient way" section of the video haha. I was doing the same thing when I was learning to program a software renderer until I heard about scanline rendering. Then everything was so much easier hehe.
I was just wanting to make a 3d software renderer for bare metal x86, then I check TH-cam and see Bisqwit just did a video series on the subject? My project is saved!
Such a clear and informative video on a subject that can easily get confusing! Nothing redundant, just exactly what I needed to learn to do this stuff. The sign of a true master teacher.
... I had to learn this to program 3D graphics on the Game Boy Advance! Minecraft and Zelda. I added a raycaster tutorial which is like 2.5D. Very interesting.
Just skipping drawing eg. the rightmost pixels of the triangle is an easy way to avoid overlapping pixels of adjacent triangles. However, it doesn't give the nicest result for the right edge of the triangle when there's no adjacent triangle drawn there (eg. this is the visible right edge of an object). There's like an entire line of pixels missing there. In many cases (and with very high resolutions) it might not matter visually at all. In other cases it might (especially with certain textures with thin edge colors). The more "correct" way of deciding which edge pixels to draw is to see if the center of the pixel is inside the mathematical triangle or not (which can be done with a dot product). This is slightly more complicated and requires a few more operations (some multiplications and additions), but in principle gives a nicer result. Of course in this case there's still the problem of what happens if the pixel is _exactly_ on the edge of the mathematical triangle (which may well happen). In this case we need to decide whether to draw it or not, and change this decision for the other adjacent triangle. In this case we can use your simpler method: If it's on the right or the bottom, we don't draw it, else we do. But yeah, with a simpler renderer where it isn't crucial to draw triangles to the very edge, the simpler approach is viable. (I do not know what GPUs do, but I have the understanding that they use the better method I described.)
That's an interesting observation, and it did occur to me that just ignoring it would bring problems in some cases. However I would say that in most cases if your rendering resolution is low enough to for this kind of problem to be really obvious, then you're likely also dealing with a system that has performance constraints which make doing a dot product on every line of every polygon drawn an unjustifiable expense. Arguably in practice (for a software renderer) you'd probably be better off having a special case drawing routine and making the person using the graphics routines responsible for deciding which to use. Though, of course, it very much depends on why you're implementing these kind of graphics algorithms, and on what kind of hardware... For instance, bresenham's line algorithm, in typical implementation is full of divisions and multiplies. But you look through a book from the 80's or early 90's and you'll find variations of the routine that go out of their way to avoid having to do divides in particular, since those were really expensive for a lot of hardware of the time. (if you had such functionality in hardware at all it was often much slower than simple addition or subtraction. ) Context matters really. XD I guess I'm still stuck in the mindset of the era that led to the first Quake... Where you had a computer that was quite powerful relative to what was around before then, but where you had to optimise everything to death to even just stand a chance of getting decent performance out of it...
@@KuraIthys Even in modern hardware avoiding (or minimizing the number of) divisions can be beneficial because division usually takes like an order of magnitude more clock cycles than multiplication. (I think the fastest division implemented in modern CPUs takes something like 15-20 clock cycles. In slightly older CPUs it may take as long as 40 clock cycles. A multiplication, even a floating point multiplication, usually takes less than 5 clock cycles, the best implementations even taking just 1.)
Hmmh. I was not aware division was still that slow. I had thought both division and multiplication were largely single cycle operations these days. I mean, it was getting towards that (For multiplication definitely) even towards the mid 90's. In any event you can get away with using such instructions anyway without it killing you on a late 90's PC... But try it on an early 90's PC or any kind of 8 or 16 bit hardware and the performance penalty is pretty serious.
WarpRulez well, alrighty. I have made it by myself already in python with pygame. Not actually all of the code, only triangle rasterizer using three dots and interpolation algorithm. By the way, do you know how to create random mash of triangles (groups of three dots) on the screen? Idk.
What an amusing coincidence. I've just finished texture mapping in my latest software 3D renderer just a couple days ago :) My previous texture mapper only handled Build-engine style geometries (and the ceiling code was a mess), now I can do both, and with full blown (software) fragment, vertex and pixel shaders in 1080p, on one CPU core. Modern CPUs are mind bogglingly fast.
Luaan hello. Why do we need to find the shortest edge? I mean I get the idea of interpolation and all. We have three points in array or doesn’t matter where -> I need to sort all points by Y-value . OK. -> I find where is the shortest side: left or right. OK. -> but why I need to find short side? We got shortside Boolean variable - what is sides[shortside] = Makeslope(...) Where sides list has been defined? Where is the function? BTW I don’t know C++ language :(
@@Jackson-yr9ih Imagine the lines you have to render. You start at the top vertex, and go row by row, interpolating the left and right lines to form the left and right limits to the scanline rendering. At some point, you reach the Y of the _second_ vertex - now one of the lines you're following changes. You need to know whether that happens on the left or on the right - that's all. It's not necessarily the "short" side - for very oblique triangles, it can easily be the longest side. The only "short" thing about it is the Y coordinate.
Luaan, Oh dear, thank you, but I actually have already got it. And made this in python with pygame. Not ALL of the program. It can only rasterize a triangle from three dots with interpolation algorithm. But I really want to know how can I create a random triangles mash on the screen (groups of three dots). Do you know? Idk. :)
@@Jackson-yr9ih Don't try to randomly place triangles - just place the dots, and then connect them into triangles :) Or don't do it randomly at all; you're trying to see all the different kinds of triangles you have to deal with - list them, and put them on the screen. In my case, I just made a rotating 3D cube - that makes finding the broken edge cases pretty fast (though Bisqwit's version is much better for seeing how well everything works at a glance).
21:07 - "Note: A comma is not permitted here. It is a curious inconsistency, but the actual reason is: What I explained previously was a fold expression, while this is a pack expansion. These are two different features with slightly different rules. C++ is great, but it is not perfect..." What's also not perfect is when communities gloss over the strange syntax and kludges in modern languages, hoping not to scare away newcomers. This usually just causes novices to tear their hair out in frustration when they DO encounter such strangeness. I wish I had known at the start of my career that almost all language features are not the "right" way of doing things, but just clever hacks to force compilers to do things they were never designed to do, using a minimum of syntax changes and code rewrites. A forewarning (and apology) every now and then is a good thing. Thank goodness I don't do web development anymore. Modern Javascript makes my eyes bleed.
C++ itself is nothing compared to setting up a build system for C++. I don't know what that last paragraph has to do with anything, but JS is both simpler, easier to learn and build scripts are much much much easier to write.
Is 5-10 lines of CMake reeeeally hard enough to whine about? I think not. For simple projects, especially if you only want them to run on *Nixen easily, Makefile or even a shell script that glob's all cpp and c files in src/ is ok (albeit, since I actually try to write portable code, a major code smell right off the bat).
@@araarathisyomama787 That was an extreme example anyways. For most actual projects, there is a bit more (especially for setting C++ standards/things) but the point is that you don't need to start with huge flashy template projects which have at least 50% CMake and are multiple hundred kilobytes for the initial commit. Building things up as you need them is better anyways, because it lets you decide "Hey, do I really need ?" and it's a lot easier to get rid of it if you don't instead of having to chase around a bunch of code. CLion and VS's CMake tooling (which I consider the most flaming hot garbage after using CLion) pretty much do the rest (CLion even offers to give you boilerplate code to set C++ standards when creating a new project), and even offer to add files to any add_* commands (CLion and VS both do this at least, although CLion is a bit more respectful about formatting) and regenerate automatically. I still wouldn't complain profusely about CMake, mostly because the alternatives either aren't as good (do NOT tell me SCons is good) or fairly early in development (DDS has been on my eyes for a while, but it's still in development and there are some conventions DDS enforces I personally don't like all too much. I'd be willing to let it slide probably, but for right now CMake is something more people will have and I'd rather use it at the moment).
Please do more on videos about this! I really enjoy your videos about computer graphics. You make all those scientific articles about it much easier to understand
Polygon graphics in software? That'll be interesting to see how it works! I've only programmed a software ray tracer before and I'm currently working with making a rasterising rendering engine but with the help of the GPU
I remember making a 3d software rasterizer a good while ago. I found the projection matrix to be the hardest part to figure out. Can't wait to see your solution.
Bisqwit be honest, are you spying on me? I've just spent the past 2 weeks debugging someone else's code that had it's own custom C++ scanline renderer & rasterizer lol Thanks for the video, actually makes everything even clearer for me.
Interesting rasterisation function. It's not the most typical approach I've seen. Generally, to simplify the logic, the more typical approach is to make use of the fact that any of the other cases can be decomposed into a flat-top and flat-bottom triangle. Since both the flat-top and flat-bottom cases only require calculating two lines, and do not involve a change in direction, they are simpler to implement. The code for splitting a general triangle into a flat-top + flat-bottom pair is also trivial since it's simply dictated by the vertical location of the middle vertex of the triangle. Even a completely naive approach to this only requires comparing the Y value of each vertex and seeing which of these lies between the other two. (if two are at the same height you have a flat top or bottom triangle) Of course, dealing with that direction change in the middle isn't THAT difficult... But this still is not the approach I've seen taken very often...
7:08 this interpolating ecuation is actually the ecuation for the line you are trying to get data from is literally the f(x) that creates the line that crosses the two points A and C, but inverted so intead of f(x) is f(y)
@@Bisqwit He worked with id Software and wrote a bunch of columns on 3d graphics, which were later turned into books. His method IIRC was to use Bresenham, create an edge list from that, and then fill that in. I like the delta method though. My absolute favorite solution I've seen so far, though, splits the triangle in half (cut at the midpoint), then one routine draws the top half and another draws the bottom. IIRC it cuts down on if-then.
The thing is.. I almost never see anything but the edge list method mentioned online. That's why I'm happy that you are showing this technique. I think it's more straightforward.
Bresenham is just one very efficient way to do the “slope” with pure integer math. Another possible method is to used fixed point, but it sacrifices accuracy. Both of these are optimizations over floating point slopes, which were slow back then. Nowadays floating point math is pretty much exactly as fast as integer math, so there is no need for those hacks anymore. The edge list you are talking about is a different topic. It sounds like it is related to rasterization of arbitrary polygons (i.e. not triangles). The splitting of triangles into two halves is pretty much the fastest possible way. If you pay attention, you’ll notice my code does pretty much the same, except that it reuses the slope of the long side (p0-p2) along the way. At the midpoint (bend) it just recalculates the short slope (which was first calculated between p0-p1, but now between p1-p2) and carries on with the second half.
@@Bisqwit Yeah, it was definitely fixed-point (486/Pentium era) and extended to be able to draw N-point polygons. But I have seen people use it when only drawing triangles as well, probably because Abrash's book was so popular. So, it's really good that you're helping get this knowledge out there to the public IMO, to show people a different way of doing things than they might have known.
I can’t wait to watch! Thanks for making such great video content. Have you considered making any training videos on Rust as well? It’s a great language, too.
Thank you for an interesting video on an oldskool topic. However I think the use of c++ lies more on the m**turbation category. For the rest of the viewers: this is NOT how you're suppose to code in c++ this is only acceptable as an exercise to showcase c++ 20 features and not as an example of anything. Remember, kids p->x is faster to run, compile and far easier to read than std::get(GetXY(*p0)). If you need to parametrize your code there are other options besides templates (even duplicate code can be sometimes better than templates).
Raytracing and spheres are really just the same thing. When your eye looks at an object, it picks up on light. Games like doom take a similar approach in that there are rays casted out from the player that hit certain objects and render the color from there, which makes 3D very simple.
8:17 NO! You CANT use round() here! If you do, that's how you get the issues at 15:15 You MUST choose to either ALWAYS truncate down, or ALWAYS truncate up. It doesn't matter which one you choose, but it MUST be consistent. Round will NOT be consistent, and that's why you CAN NOT use it here.
In my tests, rounding seems to work just fine. After all, it is just adding 0.5 to *every* X coordinate and then truncating the result. It _is_ consistent.
@@Bisqwit Graphics APIs call this "shadow rules", or "rasterisation rules". A way of determining which of 2 triangles sharing an edge gets to draw a pixel that gets crossed by that edge. GL uses "bottom-right" (floor) while DX uses "top-left" (ceil). Rounding would mean that the rules change around the pixel center. I think that can lead to some artifacts like flickering or ant-crawling, when a mesh slides across the screen at sub-pixel speed, but I can't think of a proof for that a.t.m.
I think what Julian meant is that putting Raytracing in that list might be confusing for newcomers; Beside the "sphere/atoms" approach that was obviously illustrative, from that bit of the video it might seem that voxels, polygons and raytracing are mutually exclusive ways of representing geometries, but that's not true. Raytracing, as a way of displaying geometries, can be used on polygons as well as on voxels (and on atoms in real life :)), exactly as classic rasterization can be used to display both voxels and polygons (as you do in your amazing video). Thank you so much for sharing your experience and for spreading such neat modern C++ techniques, the world needs more quality C++ examples and on the edge of the C++20 release more than ever.
i figured out that you're finnish on the first video i watched, what price do i get? also, you're incredible dude! no matter what anyone says keep uploading videos!
I didn’t know about that game. Nonetheless, it seems to use matte for backgrounds, sprites for some details such as flames, and shaded single-color ellipsoids for moving objects. It also has a few other shapes, such as a quadrilateral for a cape. Pretty ingenious.
Hi Bisqwit, love your channel! Have you tried also some low-level programming language and build something interesting? Eg. channel like Ben Eater is making simple computer based on assembly and machine code
Objection: The half-space method can be optimized greatly. It then is highly efficient. Optimizing it is a lot of work though. The SwiftShader software renderer uses the half-space method, and it performs surprisingly well on multicore CPUs.
Are you referring to the bounding box method? Yes you can use all sorts of tricks there, progressively turning it into a scanline renderer. In this video I just skipped that part altogether. The point of my series is to show intuitive and understandable methods that do not require you to go guide-dangit to find out how to do things.
@@Bisqwit I wouldn't say that it turns into a scanline renderer. Optimization methods rather turn it into a tile based renderer. For example, you could break up the bounding box into 8x8 tiles, and check if the 4 corners of a tile are fully inside or fully outside a triangle. If so, you can skip the half-space checks altogether. I do agree that the other method is more intuitive though.
I am planning to publish the next episode in a few weeks. It is currently being edited, and I may still change its script depending on feedback I receive from this video. Generally speaking I try to maintain a video per month schedule, but let’s see.
@@Bisqwit Another question -- Is this rasterization algorithm comparable to some other well known algorithm? I'm curious how it compares to the one called "Parallel Algorithm for Polygon Rasterization", which seems to be the most commonly used.
I understand that this is intended to simplify/translate the process into laymen, but anyone who can understand your vocabulary doesn't need this video.
In response to your compile-time loop shown at 18:25. This is a huge example to me why a language having static foreach (and, unrelated to this, along with a real static if) is so helpful. This is the D equivalent of what you were showing: gist.github.com/TheGag96/f80a5a75a55122b54f1790ed41031046 Having to drum up a lambda function and hide the generated sequential code you want inside a comma expression is so much harder to understand than a static loop that just generates the code within it over the loop condition. I don't know if C++ can bear the weight of an addition like that or not, but I hope they take what Andrei Alexandrescu has said to heart lol...
7:50 ish, id just like to point out that this is "linear" interpolation, so you can interpolate anything thats linear with this formula. anything nonlinear requires something else
I ask for help, so that you provide an Indonesian translator, because of your TH-cam videos, it is very useful for us beginners, thanks in advance, and thanks back to you if you see my comments.
My videos have community translations enabled. Anyone can submit translations for video title, video description, and captions. _I_ don’t speak Indonesian, but many of my recent subscribers do, including, I suspect, you. Click the link in the video description for details.
Hey Bisqwit! Just curious what resources you've used in the past to learn all this stuff? I've been (casually) researching software rendering for a few years now, and there's a lot of stuff I still can't quite wrap my head around. As GPUs were invented rather quickly, eliminating the need to understand this stuff at a software level, there doesn't seem to be a lot of literature on the subject that isn't outdated/old or just plain academic and hard to read.
It took me 10 minutes to even figure out that this is c++. I don't know anything anymore... Edit: I now understand modern c++, this actually isn't that complicated
![Texture Mapping & Polygon Rasterizing Tutorial (2/2) [C++20]](http://i.ytimg.com/vi/hxOw_p0kLfI/mqdefault.jpg)
![Texture Mapping & Polygon Rasterizing Tutorial (2/2) [C++20]](/img/tr.png)
![[Watch Party] RoV Pro League 2024 Winter | ( Bacon Time Vs FS )](http://i.ytimg.com/vi/lD6z1BugdZw/mqdefault.jpg)
The editor used in this video is Joe, and it is being run in _That Terminal._ DOSBox was not used, neither was _That Editor._ The compiler used is GCC 10.0.1, and run in Debian GNU/Linux.
The source code is now up at bisqwit.iki.fi/jkp/polytut/ . You will need GCC 10, but with small changes it can be compiled with as early as GCC 7.
ERRATA: The compile-time for-loop is not C++11, but C++20. It depends on fold expressions (c++17), std::index_sequence (c++14), and lambda templates (c++20).
*A reminder: Do not reply to **_this post_** if you want me to see your comment. Post your words as a new comment, not as a reply, unless you are addressing the contents of **_this comment_** specifically. TH-cam does not show creators new replies, it only shows new comments. If you reply here **_I will not see it_** unless I manually check for it.* If you are addressing a comment someone wrote, then you _should_ reply it, though.
Nice! I couldn't quite place it, but now you're triggering memories of a friend I had who was a big fan of Joe. It's nostalgic to see it again. I should go check it out again, and see how older-me feels about it!
I love your naming conventions
I still use joe for all my coding. I learnt the wordstar key bindings back in the Turbo Pascal days!
hahaha I love how people still ask
This game seems like what your audience might be interested in store.steampowered.com/app/1024890/Sectors_Edge/
20 years of knowledge condensed into 20 minutes of video.
Human brain ability on it peak .
thats true
Written in C++20
I really appreciate that you are up-to-date with current C++.
absolutely, it's so much easier to read /s
@@pw1169 I don't get whats so bad it about it honestly, the common complaint I hear is from Go/Rust fanatics who just keep complaining about C++'s use of iterators vs theirs.
@@ducksoop.x I'm not really a Go/Rust fanatic, but I gotta admit C++ is getting pretty hard to read, I'd say more than Java even (yeah). constexpr __noexcept virtual auto fn(args) -> return_val {}, etc. (this is not correct code cuz I haven't coded in C++ in a loong time, but you get the point). It might be easy if you have been following it since a long time, but jumping in the middle, it is really overwhelming. Atleast its learning curve is much better than Rust's.
@@pw1169 found the redditor
when you think you know a bit of c++ comes this guy and teach you 20 new things that completly blow your mind
Bisqwit made me rethink my entire life in two minutes when he said circles do not exist and are merely cylinders.
The way you reduced the interpolation formula down to a constant increment is just genius.
14:41 my heart literally stopped beating for those 3 seconds
Винни Пух ты понял, зачем он ищет самую короткую сторону?
This brings back lots of late night memories writing my own software engines. Except it was usually in C and inline assembly.
No one talks about this stuff anymore since 3d hardware took over. I look forward to the rest of this series.
Bisquit explained 10 books and my entire course of computer graphics with that intro and I understood better thia video than the other ones I mentioned. Thank you so much! Please take your time for explaining some SDL functions!
“Ultramarine blue”, 10/10
Man, I can't tell you how much I love these kinds of videos. I have tried to make a basic 3D engine just for fun, but could never figure it out, so I love stuff like this. Please make more of them. You have knowledge many of us don't.
18:29
Years later and this still my go-to source for compile-time for loop.
I still remember 2 years ago when it was all just symbols to me :D
As someone who knew most of the things in this video already and has developed simple rendering engines himself, I still very much enjoyed your video. This would've been tremendously helpful back when I first learned all of this, and still today it is a very nice presentation of the core aspects of computer graphics. Also, I like the way you casually use C++20 in your projects, few people really do that.
I loved the "inefficient way" section of the video haha. I was doing the same thing when I was learning to program a software renderer until I heard about scanline rendering. Then everything was so much easier hehe.
That surely looks interesting! Looking forward to seeing more.
Great to see a new series start.
I'm excited for part 2.
Great video. Thanks for the idea of the compiletime for loop. Good work and kinda easy to follow.
I was just wanting to make a 3d software renderer for bare metal x86, then I check TH-cam and see Bisqwit just did a video series on the subject? My project is saved!
this video made me try C++ again, I'm amazed at all the crazy things you can do with modern C++
Polygon rasterization has always fascinated me. Nice Mystic Quest music.
Such a clear and informative video on a subject that can easily get confusing! Nothing redundant, just exactly what I needed to learn to do this stuff. The sign of a true master teacher.
... I had to learn this to program 3D graphics on the Game Boy Advance! Minecraft and Zelda. I added a raycaster tutorial which is like 2.5D. Very interesting.
God, so interesting I'm glad you take time to provide this kind of quality content. I thinks C++ beginner as me are lucky to have found your channel.
After the triangle everything was nonsense for me. Anyways good work and great video. Thank you again!
That's because modern c++ is purely syntactic diabetes to overcomplicate existing concepts (functions, structs, loops)
your graphics videos are the best you upload. please do more!
i thought i have a decent level of programming ... until this. I'm glad i find someone like you , now i want more knowledge :D
Excellent, I'd love to see a lot more videos like this one, graphics and sound coding. In its elements.
Just skipping drawing eg. the rightmost pixels of the triangle is an easy way to avoid overlapping pixels of adjacent triangles. However, it doesn't give the nicest result for the right edge of the triangle when there's no adjacent triangle drawn there (eg. this is the visible right edge of an object). There's like an entire line of pixels missing there. In many cases (and with very high resolutions) it might not matter visually at all. In other cases it might (especially with certain textures with thin edge colors).
The more "correct" way of deciding which edge pixels to draw is to see if the center of the pixel is inside the mathematical triangle or not (which can be done with a dot product). This is slightly more complicated and requires a few more operations (some multiplications and additions), but in principle gives a nicer result.
Of course in this case there's still the problem of what happens if the pixel is _exactly_ on the edge of the mathematical triangle (which may well happen). In this case we need to decide whether to draw it or not, and change this decision for the other adjacent triangle. In this case we can use your simpler method: If it's on the right or the bottom, we don't draw it, else we do.
But yeah, with a simpler renderer where it isn't crucial to draw triangles to the very edge, the simpler approach is viable.
(I do not know what GPUs do, but I have the understanding that they use the better method I described.)
That's an interesting observation, and it did occur to me that just ignoring it would bring problems in some cases.
However I would say that in most cases if your rendering resolution is low enough to for this kind of problem to be really obvious, then you're likely also dealing with a system that has performance constraints which make doing a dot product on every line of every polygon drawn an unjustifiable expense.
Arguably in practice (for a software renderer) you'd probably be better off having a special case drawing routine and making the person using the graphics routines responsible for deciding which to use.
Though, of course, it very much depends on why you're implementing these kind of graphics algorithms, and on what kind of hardware...
For instance, bresenham's line algorithm, in typical implementation is full of divisions and multiplies.
But you look through a book from the 80's or early 90's and you'll find variations of the routine that go out of their way to avoid having to do divides in particular, since those were really expensive for a lot of hardware of the time. (if you had such functionality in hardware at all it was often much slower than simple addition or subtraction. )
Context matters really. XD
I guess I'm still stuck in the mindset of the era that led to the first Quake...
Where you had a computer that was quite powerful relative to what was around before then, but where you had to optimise everything to death to even just stand a chance of getting decent performance out of it...
@@KuraIthys Even in modern hardware avoiding (or minimizing the number of) divisions can be beneficial because division usually takes like an order of magnitude more clock cycles than multiplication. (I think the fastest division implemented in modern CPUs takes something like 15-20 clock cycles. In slightly older CPUs it may take as long as 40 clock cycles. A multiplication, even a floating point multiplication, usually takes less than 5 clock cycles, the best implementations even taking just 1.)
Hmmh. I was not aware division was still that slow.
I had thought both division and multiplication were largely single cycle operations these days.
I mean, it was getting towards that (For multiplication definitely) even towards the mid 90's.
In any event you can get away with using such instructions anyway without it killing you on a late 90's PC...
But try it on an early 90's PC or any kind of 8 or 16 bit hardware and the performance penalty is pretty serious.
@@Jackson-yr9ih I don't really understand where you are getting that "shortest side" from.
WarpRulez well, alrighty. I have made it by myself already in python with pygame. Not actually all of the code, only triangle rasterizer using three dots and interpolation algorithm. By the way, do you know how to create random mash of triangles (groups of three dots) on the screen? Idk.
Really helpful and informative!
for Bisqwit to have such an amazing understanding of the polygon world, I think it's safe to say he is a polygon person too!
Loving your video already. This is the first one I have watched, I will watch a few more.
What an amusing coincidence. I've just finished texture mapping in my latest software 3D renderer just a couple days ago :) My previous texture mapper only handled Build-engine style geometries (and the ceiling code was a mess), now I can do both, and with full blown (software) fragment, vertex and pixel shaders in 1080p, on one CPU core. Modern CPUs are mind bogglingly fast.
Luaan hello. Why do we need to find the shortest edge? I mean I get the idea of interpolation and all. We have three points in array or doesn’t matter where -> I need to sort all points by Y-value . OK. -> I find where is the shortest side: left or right. OK. -> but why I need to find short side? We got shortside Boolean variable - what is sides[shortside] = Makeslope(...) Where sides list has been defined? Where is the function? BTW I don’t know C++ language :(
@@Jackson-yr9ih Imagine the lines you have to render. You start at the top vertex, and go row by row, interpolating the left and right lines to form the left and right limits to the scanline rendering. At some point, you reach the Y of the _second_ vertex - now one of the lines you're following changes. You need to know whether that happens on the left or on the right - that's all. It's not necessarily the "short" side - for very oblique triangles, it can easily be the longest side. The only "short" thing about it is the Y coordinate.
Luaan, Oh dear, thank you, but I actually have already got it. And made this in python with pygame. Not ALL of the program. It can only rasterize a triangle from three dots with interpolation algorithm. But I really want to know how can I create a random triangles mash on the screen (groups of three dots). Do you know? Idk. :)
@@Jackson-yr9ih Don't try to randomly place triangles - just place the dots, and then connect them into triangles :) Or don't do it randomly at all; you're trying to see all the different kinds of triangles you have to deal with - list them, and put them on the screen.
In my case, I just made a rotating 3D cube - that makes finding the broken edge cases pretty fast (though Bisqwit's version is much better for seeing how well everything works at a glance).
Luaan well, I would like to make the rotating cube too. I’m a newbie in all of this vector stuff. :)
Holy I was muttering random Japanese words and opened this video while being half-asleep. The intro was kinda surprising lmao
21:07 - "Note: A comma is not permitted here. It is a curious inconsistency, but the actual reason is: What I explained previously was a fold expression, while this is a pack expansion. These are two different features with slightly different rules. C++ is great, but it is not perfect..."
What's also not perfect is when communities gloss over the strange syntax and kludges in modern languages, hoping not to scare away newcomers. This usually just causes novices to tear their hair out in frustration when they DO encounter such strangeness. I wish I had known at the start of my career that almost all language features are not the "right" way of doing things, but just clever hacks to force compilers to do things they were never designed to do, using a minimum of syntax changes and code rewrites. A forewarning (and apology) every now and then is a good thing.
Thank goodness I don't do web development anymore. Modern Javascript makes my eyes bleed.
C++ itself is nothing compared to setting up a build system for C++.
I don't know what that last paragraph has to do with anything, but JS is both simpler, easier to learn and build scripts are much much much easier to write.
Is 5-10 lines of CMake reeeeally hard enough to whine about? I think not. For simple projects, especially if you only want them to run on *Nixen easily, Makefile or even a shell script that glob's all cpp and c files in src/ is ok (albeit, since I actually try to write portable code, a major code smell right off the bat).
@@modeco80 But, nobody is getting paid for projects that only require 5-10 lines of cmake
@@araarathisyomama787 That was an extreme example anyways.
For most actual projects, there is a bit more (especially for setting C++ standards/things) but the point is that you don't need to start with huge flashy template projects which have at least 50% CMake and are multiple hundred kilobytes for the initial commit. Building things up as you need them is better anyways, because it lets you decide "Hey, do I really need ?" and it's a lot easier to get rid of it if you don't instead of having to chase around a bunch of code.
CLion and VS's CMake tooling (which I consider the most flaming hot garbage after using CLion) pretty much do the rest (CLion even offers to give you boilerplate code to set C++ standards when creating a new project), and even offer to add files to any add_* commands (CLion and VS both do this at least, although CLion is a bit more respectful about formatting) and regenerate automatically.
I still wouldn't complain profusely about CMake, mostly because the alternatives either aren't as good (do NOT tell me SCons is good) or fairly early in development (DDS has been on my eyes for a while, but it's still in development and there are some conventions DDS enforces I personally don't like all too much. I'd be willing to let it slide probably, but for right now CMake is something more people will have and I'd rather use it at the moment).
Amazing thought process and explanation.
Please do more on videos about this! I really enjoy your videos about computer graphics. You make all those scientific articles about it much easier to understand
Polygon graphics in software? That'll be interesting to see how it works!
I've only programmed a software ray tracer before and I'm currently working with making a rasterising rendering engine but with the help of the GPU
View anything from the demoscene from 1988 to ~1997 and amaze ;)
Good god, your videos are so dense with information. I love watching your stuff.
Bisqwit is a beautiful soul
I remember making a 3d software rasterizer a good while ago. I found the projection matrix to be the hardest part to figure out. Can't wait to see your solution.
3D projection will be in part 2! Hope you will still watch this video :-)
@@Bisqwit Sure will.
Final Fantasy Mystic Quest is a nice touch.
Coincidentally, I was just trying to do this a few days ago.
I feel something hard in my pant every time i see a Bisqwit upload.
finally i know how the rendirng works thanks bisqwit
Worth noting that sotware rasterizers are still used in graphics engines today - not as renderers but intermediate steps for solving other problems.
This is why im subscribed to bisqwit
Bisqwit be honest, are you spying on me?
I've just spent the past 2 weeks debugging someone else's code that had it's own custom C++ scanline renderer & rasterizer lol
Thanks for the video, actually makes everything even clearer for me.
Great video! Can't wait for the next one.
amazing work, always look forward to your videos! keep at it! and keep safe!
Interesting rasterisation function.
It's not the most typical approach I've seen.
Generally, to simplify the logic, the more typical approach is to make use of the fact that any of the other cases can be decomposed into a flat-top and flat-bottom triangle.
Since both the flat-top and flat-bottom cases only require calculating two lines, and do not involve a change in direction, they are simpler to implement.
The code for splitting a general triangle into a flat-top + flat-bottom pair is also trivial since it's simply dictated by the vertical location of the middle vertex of the triangle.
Even a completely naive approach to this only requires comparing the Y value of each vertex and seeing which of these lies between the other two.
(if two are at the same height you have a flat top or bottom triangle)
Of course, dealing with that direction change in the middle isn't THAT difficult...
But this still is not the approach I've seen taken very often...
I’m not sure what that means, but I want to learn it so bad
lol. So do I
7:08 this interpolating ecuation is actually the ecuation for the line you are trying to get data from
is literally the f(x) that creates the line that crosses the two points A and C, but inverted so intead of f(x) is f(y)
Yes, that’s why it is called _line_ ar interpolation. :)
I absolutely love your videos. Keep it up!
Great video as usual, I missed your quality videos
You are the best bisqwit it the world!
It makes me happy that you went for deltas instead of using that method Abrash describes. Awesome!
Who is Abrash?
@@Bisqwit He worked with id Software and wrote a bunch of columns on 3d graphics, which were later turned into books. His method IIRC was to use Bresenham, create an edge list from that, and then fill that in. I like the delta method though. My absolute favorite solution I've seen so far, though, splits the triangle in half (cut at the midpoint), then one routine draws the top half and another draws the bottom. IIRC it cuts down on if-then.
The thing is.. I almost never see anything but the edge list method mentioned online. That's why I'm happy that you are showing this technique. I think it's more straightforward.
Bresenham is just one very efficient way to do the “slope” with pure integer math. Another possible method is to used fixed point, but it sacrifices accuracy. Both of these are optimizations over floating point slopes, which were slow back then. Nowadays floating point math is pretty much exactly as fast as integer math, so there is no need for those hacks anymore.
The edge list you are talking about is a different topic. It sounds like it is related to rasterization of arbitrary polygons (i.e. not triangles).
The splitting of triangles into two halves is pretty much the fastest possible way. If you pay attention, you’ll notice my code does pretty much the same, except that it reuses the slope of the long side (p0-p2) along the way. At the midpoint (bend) it just recalculates the short slope (which was first calculated between p0-p1, but now between p1-p2) and carries on with the second half.
@@Bisqwit Yeah, it was definitely fixed-point (486/Pentium era) and extended to be able to draw N-point polygons. But I have seen people use it when only drawing triangles as well, probably because Abrash's book was so popular. So, it's really good that you're helping get this knowledge out there to the public IMO, to show people a different way of doing things than they might have known.
Thanks!
I can’t wait to watch! Thanks for making such great video content. Have you considered making any training videos on Rust as well? It’s a great language, too.
I am not in position to teach any Rust, having only ever written one program in that language.
This is C++ on steroids. I love good old C.
you are the bob ross of c++
Love your videos!
Thank you for an interesting video on an oldskool topic. However I think the use of c++ lies more on the m**turbation category. For the rest of the viewers: this is NOT how you're suppose to code in c++ this is only acceptable as an exercise to showcase c++ 20 features and not as an example of anything. Remember, kids p->x is faster to run, compile and far easier to read than std::get(GetXY(*p0)). If you need to parametrize your code there are other options besides templates (even duplicate code can be sometimes better than templates).
Looks fun. Time to get my hands dirty!
Thumbs up for the Final Fantasy Mystic Quest music!
who needs school when you have Bisqwit...? l:p
Love that Mystic Quest music! ❤
21:07 that took me ages to find but finally i got it!
If you use TH-cam on a computer, you can pause the video and use comma and period keys to go backward/forward in the video frame by frame.
Bisqwit I am watching on my iPad and had to do x.25 and pause+play quickly and often and do -5s often since I kept failing :)
Awesome content.
2:00 thought the GPU fan on my phone was spinning up for a second 😂
I wish I was that good at programming!
So cool
I love you
Nice sir
You keep this stuff up and before long, you'll have John Carmack *quaking* in his boots. ;)
Nah. He’s got a good 30ish years head-start on me.
Raytracing and spheres are really just the same thing. When your eye looks at an object, it picks up on light. Games like doom take a similar approach in that there are rays casted out from the player that hit certain objects and render the color from there, which makes 3D very simple.
Doom absolutely does not do that. You are mixing up with Wolfenstein 3D, which does use ray casting.
@@Bisqwit you're right! I didn't know this two weeks ago, thanks for correcting me!
7:19 then include tick t for particle moving in triangle x(null) = 7, x(11) = 12, x(y) = 7 + ...
8:17 NO! You CANT use round() here! If you do, that's how you get the issues at 15:15
You MUST choose to either ALWAYS truncate down, or ALWAYS truncate up. It doesn't matter which one you choose, but it MUST be consistent. Round will NOT be consistent, and that's why you CAN NOT use it here.
In my tests, rounding seems to work just fine. After all, it is just adding 0.5 to *every* X coordinate and then truncating the result. It _is_ consistent.
@@Bisqwit Did you try it across time with movement? Or just a static image?
I modified the program to generate a new triangle mesh on every frame.
@@Bisqwit That is not the same thing. A good test would be to make the whole mesh move at sub pixel speed in some diagonal direction.
@@Bisqwit Graphics APIs call this "shadow rules", or "rasterisation rules". A way of determining which of 2 triangles sharing an edge gets to draw a pixel that gets crossed by that edge. GL uses "bottom-right" (floor) while DX uses "top-left" (ceil). Rounding would mean that the rules change around the pixel center. I think that can lead to some artifacts like flickering or ant-crawling, when a mesh slides across the screen at sub-pixel speed, but I can't think of a proof for that a.t.m.
1:48 voxels, polygons and spheres are ways of representing geometry. raytracing is an way to display such geometry.
That is true. Scanline rasterization is a way to display such geometry, and that’s what I am doing here.
I think what Julian meant is that putting Raytracing in that list might be confusing for newcomers; Beside the "sphere/atoms" approach that was obviously illustrative, from that bit of the video it might seem that voxels, polygons and raytracing are mutually exclusive ways of representing geometries, but that's not true. Raytracing, as a way of displaying geometries, can be used on polygons as well as on voxels (and on atoms in real life :)), exactly as classic rasterization can be used to display both voxels and polygons (as you do in your amazing video).
Thank you so much for sharing your experience and for spreading such neat modern C++ techniques, the world needs more quality C++ examples and on the edge of the C++20 release more than ever.
i figured out that you're finnish on the first video i watched, what price do i get? also, you're incredible dude! no matter what anyone says keep uploading videos!
Thanks for another good video Bisquit. It's like food for the brain :)
Also, polygon lives matter
The inefficient method shown at 4:07 is probably closer to what a GPU is doing under the hood, because it can be parallelized so easily.
nice video
Always cool to watch your videos. That lambda function though. #CodeGolf
There was a game made with spheres called Ecstatica, pity you didn't mention it
I didn’t know about that game. Nonetheless, it seems to use matte for backgrounds, sprites for some details such as flames, and shaded single-color ellipsoids for moving objects. It also has a few other shapes, such as a quadrilateral for a cape. Pretty ingenious.
Interesting thing
Hi
Bisqwit, love your channel! Have you tried also some low-level programming language and build something interesting? Eg. channel like Ben Eater is making simple computer based on assembly and machine code
Objection: The half-space method can be optimized greatly. It then is highly efficient. Optimizing it is a lot of work though. The SwiftShader software renderer uses the half-space method, and it performs surprisingly well on multicore CPUs.
Are you referring to the bounding box method? Yes you can use all sorts of tricks there, progressively turning it into a scanline renderer. In this video I just skipped that part altogether. The point of my series is to show intuitive and understandable methods that do not require you to go guide-dangit to find out how to do things.
@@Bisqwit I wouldn't say that it turns into a scanline renderer. Optimization methods rather turn it into a tile based renderer. For example, you could break up the bounding box into 8x8 tiles, and check if the 4 corners of a tile are fully inside or fully outside a triangle. If so, you can skip the half-space checks altogether.
I do agree that the other method is more intuitive though.
When do you plan on hosting the next video? This was amazing!
I am planning to publish the next episode in a few weeks. It is currently being edited, and I may still change its script depending on feedback I receive from this video. Generally speaking I try to maintain a video per month schedule, but let’s see.
@@Bisqwit Another question -- Is this rasterization algorithm comparable to some other well known algorithm? I'm curious how it compares to the one called "Parallel Algorithm for Polygon Rasterization", which seems to be the most commonly used.
It is very similar to the algorithm used by Fabrice Bellard’s TinyGL, except that to keep the code simple, I didn’t go for fixed-point.
1:46
Ahh yes you knew i was thinking of making a simple half life game after creating a graphics renderer
I understand that this is intended to simplify/translate the process into laymen, but anyone who can understand your vocabulary doesn't need this video.
that line rasterization algorithm smells a lot like brehensam's. is that indeed correct, mr. bisqwit?
Not quite, but it you remove enough special cases and optimizations from bresenham’s, you could end up with this.
こんにちは！！
nice
In response to your compile-time loop shown at 18:25. This is a huge example to me why a language having static foreach (and, unrelated to this, along with a real static if) is so helpful. This is the D equivalent of what you were showing:
gist.github.com/TheGag96/f80a5a75a55122b54f1790ed41031046
Having to drum up a lambda function and hide the generated sequential code you want inside a comma expression is so much harder to understand than a static loop that just generates the code within it over the loop condition. I don't know if C++ can bear the weight of an addition like that or not, but I hope they take what Andrei Alexandrescu has said to heart lol...
I completely agree with you here. To be honest I’m not sure if there is an easier way to do it in C++, but so far no expert has chipped in with ideas.
Is this real time typing? At least by watching the clock on the top right it doesn't look like a time lapse.
19:05 std::integer_sequence and std::index_sequence are only available from C++14 and on-wards. You mean sizeof... for C++11.
The whole thing I described is only C++20 onwards due to lambda template. My bad.
7:50 ish, id just like to point out that this is "linear" interpolation, so you can interpolate anything thats linear with this formula. anything nonlinear requires something else
That is true. I did call it with the “linear” specifier once in the video, right before “hold on, let me make it bigger”.
I ask for help, so that you provide an Indonesian translator, because of your TH-cam videos, it is very useful for us beginners, thanks in advance, and thanks back to you if you see my comments.
My videos have community translations enabled. Anyone can submit translations for video title, video description, and captions. _I_ don’t speak Indonesian, but many of my recent subscribers do, including, I suspect, you. Click the link in the video description for details.
Hey Bisqwit! Just curious what resources you've used in the past to learn all this stuff? I've been (casually) researching software rendering for a few years now, and there's a lot of stuff I still can't quite wrap my head around. As GPUs were invented rather quickly, eliminating the need to understand this stuff at a software level, there doesn't seem to be a lot of literature on the subject that isn't outdated/old or just plain academic and hard to read.
It took me 10 minutes to even figure out that this is c++. I don't know anything anymore...
Edit: I now understand modern c++, this actually isn't that complicated