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/

Human brain ability on it peak .

thats true

Written in C++20

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

Винни Пух ты понял, зачем он ищет самую короткую сторону?

3D projection will be in part 2! Hope you will still watch this video :-)

@@Bisqwit Sure will.

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).

I am not in position to teach any Rust, having only ever written one program in that language.

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.

View anything from the demoscene from 1988 to ~1997 and amaze ;)

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. :)

Nice catch! Yeah, you can only use std::apply if you are going to iterate through _all_ values in the tuple/pair/array. It can not be used, at least not without much complication, if you only want to iterate through a subset.

That's because modern c++ is purely syntactic diabetes to overcomplicate existing concepts (functions, structs, loops)

lol. So do I

Yes, that’s why it is called _line_ ar interpolation. :)

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.

That is correct. The MB is Asrock TRX40 Creator.

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.

Nah. He’s got a good 30ish years head-start on me.

Yes on both accounts. My typical terminal window is about 100 characters wide so I tend to keep lines shorter than that, but I went for presentation purposes here.

If you use KZfaq 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 :)

Maybe, but none are planned right now. I tend to do those at a whim really, at most 2 days of planning.

Владосик, ты понял, зачем мы ищем короткую сторону?

Sorry, I don’t speak that language of yours, whichever it is.

Bisqwit, I had asked him why should we find the shortest side to rasterize triangle properly. I actually have 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). Thank you.

bisqwit.iki.fi/jkp/polytut/mesh.hh This is how I did it.

Slopes are used in my polygon blitter for anything that must be interpolated between two extremes. Mostly coordinates though. The X coordinates on both edges, from top to bottom, for instance.

@@Bisqwit ohhh cool, thanks!!

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.

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!

Doing a perspective projection on a bezier patch could be rather tricky. I can’t think of a practical way to do it.

@@Bisqwit Somehow, the hl2.exe program which is not only for Half-Life 2, but miraculously for every Valve game, can smoothen the edges on the polygons which are sharp, and they end up looking like bezier patches. How is that possible?

Maybe you mean something other than bezier. Your terminology is confusing. In any case, the smoothing of edges of polygons is called _antialiasing._ Modern GPUs have that feature. It works by _multisampling._ It renders the screen internally at a much higher resolution (for example, 4x the width and 4x the height, i.e. 16x samples for every pixel), and then resizes it down by averaging. The exact details vary depending on the method (SSAA/FSAA/MSAA) and include lots of performance optimizations, but the general gist is the same.

@@Bisqwit I see. I thought that Bezier curves could do the same thing. Someone told me that a game called Ecstatica used that trick.

What is "Linux hotkeys"?

@@Bisqwit ^A to beginning of line, ^E to end of line, etc... I'm sure that I'm calling it the wrong thing, lol.

Well yes, those, and ^U and ^V for pgup and pgdn, and ^D for delete… I don’t actually know where they originate. If I had to guess, probably GNU Emacs. And from there it has been incorporated into GNU Readline (used by bash and many other tools), PINE and PICO, and yes, JOE too. But the majority of inputs that JOE has is based on WordStar. JOE describes itself as a WordStar-Emacs hybrid. I have described why history and reason for editor choices in this video: kzfaq.info/get/bejne/kLNyhNCZtJ6voX0.html

Not quite, but it you remove enough special cases and optimizations from bresenham’s, you could end up with this.

en.cppreference.com/ - Reference manual on all things C++ (look for things that say C++20; Wiki, so it’s updated once in a while) en.wikipedia.org/wiki/C++20 - Summary; search for things that pique your interest or click the reference links gcc.gnu.org/projects/cxx-status.html - TODO/status list for GCC, including links to the proposals that describe the feature (quite technical) gcc.gnu.org/onlinedocs/libstdc++/manual/status.html#status.iso.2020 - TODO list for the standard library component of GCC, including links to the proposals that describe the feature (quite technical) These are my four main go-to resources on new things C++. Also for keeping up to date with C++ news, there are several subreddits, such as reddit.com/r/cpp

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 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.

What I meant is difficult to explain unless you are familiar with how machine code works or how to read assembly. Assuming that you do, I’ll explain. I meant this: for(...) { call_func(&a); } for(...) { call_func(&b); } For the above code, the compiler is likely to generate the functor as a separate function, and perform explicit calls to that functor. This involves spilling local variables into stack / callee-saves registers, in honor of the ABI. The functor has to be compiled verbatim, literally at face value, and saved like that in the binary. for(...) { call_func(situation_one ? &a : &b); } For the second piece, the compiler is likely to inline the functor because it is only used once. This means that the compiler can optimize the functor _and_ the surrounding function as one unit, taking advantage of known values of variables, potentially generating more optimal code, eliminating never-taken branches form the functor, and so on.

@@Bisqwit Yes I am familiar with the cost of stack frames that go along with function calls. I see, so it's just that the compiler is more likely to inline the functor if it only gets called once. So if it were possible to force certain functions to be inlined, one wouldn't need to be as careful about calling them more than once?

Indeed.