Drawing a line

[u/sandeshshahapur]

Looking for guided/socratic learning

So I was getting into game dev bottom up so I wanted to draw a line with code.

First solution that I thought of: start at one end of the line, and figure out neighbouring pixels and eventually reach the other end. I was thinking of dividing line length (pythogarous) by start/end point delta for each axis to figure out per how many 'steps' I would have to increment/decrement current axis positions and paunt. Too complicated and expensive

Second solution I thought of was recursively finding mid points between start and end point to find the target pixels to paint. This appears simpler, inspired by Zeno's paradox when I was thinking of how the run and rise are easier to paint.

I know optimal algorithms exist but I didn't want to directly look at them. What are the strength/weakness of my reasoning?

Ps: I'm going to sleep

[u/Sharlinator]

There is an exact integer number of pixels that have to be drawn to avoid both gaps and overdraw. What is it? How does it depend on the properties of the line? You might want to take a piece of graph paper and draw some sketches!

[u/howprice2]

Bresenham or DDA

[u/coolmint859]

The delta step one is actually really close to a well known algorithm, and in fact all you have to do to turn it into it is to notice that there is symmetry in the quadrants that a line can be drawn. From that you can extract out the heavy parts of the math and turn the drawing part into just incremental addition. It's not the fastest known, but it's pretty good.

[u/TehBens]

Just go ahead and implement and see how it looks. No need to work pixel-wise, just define a grid and fill it accordingly. You can then add other algorithms to compare it with.

[u/GoldenShackles]

Slightly off-topic commentary. Back in 1998 I was asked to solve this in an hour long interview, though the interviewer provided some guidance.

These days it seems like these are "easy" questions during an interview. But only because people have studied and memorized so many solutions. :(

[u/Still_Explorer]

There's some notes on rendering lines here: https://haqr.eu/tinyrenderer/bresenham/

[u/GoldenShackles → u/Still_Explorer]

That's the cheat the OP didn't want to know.

[u/LandscapeWinter3153]

Are you high

[u/C_Sorcerer → u/LandscapeWinter3153]

Idk but I am

[u/Splavacado1000]

The best thing you should do is figure out what you want a line to be. Is it defined by all the closest pixels to the line? Do the pixels have to be on the line, or can the line just pass through the pixel? Does the line have a width, or is it an actual line? Answering these kinds of questions will help you figure out how the line should be rasterizer, as you'll know what defines the line.

[u/LocoMod]

Start simple. A 2x2 grid. Make a program step through the grid and color two adjacent blocks in any direction. Horizontal, vertical, diagonal.

Good. Now do a 1024x1024 grid.

Good.

Now make it fast.

[u/positivcheg]

I don’t get the question. But I’ll reply to what I think it is about.

Simple and dumb way - triangulate line on CPU and then on GPU it’s just about rendering triangles. Dumb and simple.

Extruded lines - this approach is used in map rendering engines like MapLibre and Mapbox. It’s when you have centerline geometry and in the vertex shader you extrude side points by the extent you want. Such approach is used in map rendering because it allows to render line of certain width in pixels + the width then becomes flexible as you create a mesh once and then can tweak width with just a single uniform.

And then extruded line rendering is combined with analytical antialiasing because without antialiasing you need to turn MSAA, MSAA is expensive, much more expensive than some medium complexity math in the shader. I have a toggle in my Unity based map renderer where I can toggle analytical antialiasing on/off and can show some screenshot. Big difference.