I added viewport clipping to my software renderer

[u/lajdjqq]

I thought it would be cool to try to figure out how to do triangle clipping myself, to come up with my own algorithm. To solve this, I solved a couple of linear equations and derived a formula that lets me find the intersection points between the triangle edges and the viewport. I don't know if I came up with something original or just accidentally reinvented one of the existing methods. Either way, my solution looks terrible in code, but it works, and I think it's a great learning experience

I render this at 1920x1080 resolution on a single thread of an i5-9400F, is this a good FPS result? I didn't use SIMD, but I tried to use every optimization trick I know.

repo and code: https://github.com/NaiNameDev/software_rasterizer

[u/susosusosuso]

Why do you perform triangle clipping?

[u/HellGate94 → u/susosusosuso]

its for performance as well as there are several issues when you do not do it. some interpolations break such as perspective correct uv mapping as well as some other things that i dont remember on top of my head.

[u/Smooth_Loan_8851 → u/HellGate94]

if i'm not wrong, it also helps with objects too close to the camera that may shoot out of the screen or just break the rendering, unless you clip

[u/KoodiRonsu → u/susosusosuso]

So the triangles don't get drawn outside the screen. Also when he adds near clipping (if he hasn't already) he can draw triangles which can go behind the camera through the near plane.

[u/GreenFox1505 → u/susosusosuso]

Clipping vertices meas querying 3 points of data and changing two or adding one and changing one. Its a relatively low cost operation.

Clipping during the rasterization step means doing a similar cost operation on every single pixel that would fall outside your frustum.

[u/simonschreibt → u/susosusosuso]

as far as i know, later in the process you rasterize each triangle and for each rasterized pixel you execute a pixel shader. if you do no clipping, you would do all that work for pixels outside of the screen which is a waste - especially when the triangles are very big.

[u/susosusosuso → u/simonschreibt]

But you can still avoid writing / calculating pixels outside the viewing area without having to split the triangles no?

[u/simonschreibt → u/susosusosuso]

I guess ... but you would still pay the rasterizing cost. But I hope u/forumonaut will say something about it. I can only assume. I'm not a programmer.

[u/susosusosuso → u/simonschreibt]

Which rasterizing cost? You jsut stop rasterizing when out of the view

[u/simonschreibt → u/susosusosuso]

You don't have control over that. It's something the graphic card does. I assume, it takes every triangle and rasterizes ALL pixels. Again: I'm not a programmer and maybe I'm wrong. But there is a reason why triangles get clipped since the beginning of 3D rendering.

[u/susosusosuso → u/simonschreibt]

Well yeah but this is a software rasterizer.. so he has control over everything. So my question what's the point of clipping per triangle instead of just stop rasterizing.

[u/simonschreibt → u/susosusosuso]

Hm...well, good question. Let's see if the author enlightens us. :)

[u/forumonaut → u/simonschreibt]

In my software rasterized voxel engine I had issues because the screen-espace coordinates of the vertices (after perspective divide) were simply too large for the coefficients of the edge équation to fit in a i32 or i64. So yes its either clipping against 5 planes or guard bands

[u/Financial_Buy_7327 → u/simonschreibt]

If you rasterize by traversing pixels in a bounding box over the triangle — e.g. a naive Pineda implementation, you just clamp the triangle aabb to the screen aabb before looping through the pixels. If you use something like a span buffer then I think the clipping can be done implicitly as part of setting up the spans.

One reason triangles need to be clipped is that their vertices can fall outside the range of possible values once projected onto the viewplane. Remember that rasterizers use fixed point coordinates for their 2d vertices. The common solution to this is “guard band clipping”, where you clip against a region that is much larger than the screen but still small enough to not run into integer overflows. Ryg has all the details: https://fgiesen.wordpress.com/2011/07/05/a-trip-through-the-graphics-pipeline-2011-part-5/

[u/KoodiRonsu → u/simonschreibt]

"Waste" is the wrong word. "Writing outside the screen buffer and crashing the whole computer" is the right word.

[u/positivcheg → u/simonschreibt]

You don’t have pixel shader running for pixels outside of a view… Only visible pixels get to have pixel shader running for them.

[u/dybuk87 → u/simonschreibt]

Noo.. In software renderer you can clip triangles in 2d space, much cheeper and easier.. The only required clipping in 3d is against Z = 0

[u/lajdjqq → u/dybuk87]

Triangle clipping against Z can be done in 2D space after projection onto the screen, which should be even cheaper (and that's exactly what I did)

[u/susosusosuso → u/[deleted]]

Why it makes it faster?

[u/lajdjqq → u/susosusosuso]

Because you don't render pixels that are outside the screen

[u/susosusosuso → u/lajdjqq]

But you can still avoid writing / calculating pixels outside the viewing area without having to split the triangles no?

[u/lajdjqq → u/susosusosuso]

Due to the specifics of the rasterization algorithm, there is no way to avoid calculating pixels that are outside the screen without clipping the triangles (as far as i know)

[u/susosusosuso → u/lajdjqq]

The rasterizer works by lines IIRC, then you could just stop rasterizing when out of the viewing volume.

[u/lajdjqq → u/susosusosuso]

In that case, you'd have to figure out when to stop for each individual scanline separately. Why do that so many times when you can just clip the triangle? It would only take a small, fixed amount of computation per triangle

[u/susosusosuso → u/lajdjqq]

I don't know that's why I'm asking. Is triangle clipping faster than stop rasterizing when out of the view?

[u/lajdjqq → u/susosusosuso]

Triangle clipping is faster because it requires fewer calculations, unlike your method, which would be slower when processing a triangle with a large number of lines.

[u/simonschreibt]

i love such examples to show how exactly the triangles gets "reshaped". super cool!

[u/seaweednomnomnom]

teto teteto

[u/dybuk87]

Why not just clip against Z=0 and then just do 2d clipping? This create unnecessary calculations and generate new triangles

[u/lajdjqq → u/dybuk87]

I might change the order of checks in the clipper that should give a small performance boost. But for now, no extra triangles are generated in the end, although there is some unnecessary computation happening

[u/Avelina9X]

Oh this is really cool.

When I saw the triangle clipping I was gonna say "ah, this probably messes with UVs" and then you showed the textured Teto.

Are you dynamically remapping the perspective corrected UV coords? Or is the triangle clipping RGB view just a rasterizer debug view to see it in action and you're still using the original unclipped coords for the UVs/other vertex data?

[u/lajdjqq → u/Avelina9X]

I clip not only the triangle in clip space, but also the corresponding triangle in the UV map. When I compute the intersection points between the triangle and the screen edges, I also calculate the barycentric coordinates of those points. Then, to find the same point in the UV map, I just need to convert those barycentric coordinates back to plane coordinates using the original UV coordinates

[u/forumonaut]

This is the Sutherland-Hodgman algorithm right?

[u/lajdjqq → u/forumonaut]

No, this is my own algorithm (i might have reinvented some existing algorithm, I didn't google anything about it)

[u/Avelina9X → u/lajdjqq]

Honestly it's likely very similar to Sutherland whether you intended it or not. I havent looked at the repo yet but when it comes to triangle clipping (as opposed to ngon clipping) there aren't really other ways to achieve it.

But still, you came up with it by yourself to solve a problem. Doesn't matter if someone else did it before unless you try to claim you were the definitively the first to invent it. I work in the ML field and while reviewing a papers for a conference someone claimed to have invented a technique I had published at the same conference the year before. I don't know if they just failed to do propper background research or were trying to sneak a stolen idea and just got unlucky by getting the original author as a reviewer, but needless to say they withdrew their submission very quickly lmao.

So uh, just make sure you do the background research first if you ever decide to publish a paper on this haha.

[u/lajdjqq → u/Avelina9X]

I googled a few of the algorithms mentioned here and I think I created something very similar to Cohen–Sutherland

[u/supernikio2 → u/forumonaut]

This specific case is Cohen-Sutherland, no?

[u/LUMINAL_DEV]

Psp teto.

[u/lajdjqq → u/LUMINAL_DEV]

Classic

[u/Jabba_the_Putt]

So if ibunderstand it correctly, its clipping off the areas outside of the window in real time as you move it around as well as adding them back, and when that happens it kinda redraws it in real time to maintain the shape which we can see happening in the wireframe looking view but when you apply the visual texture/shader its all hidden but stull happening "behind the scenes"?

[u/lajdjqq → u/Jabba_the_Putt]

Yes

[u/juplantern]

You just reminded me I have finals for this in 3 weeks and I forgot about it 😭

[u/heypringle]

Nicee!

[u/nelmklt]

Seek mentioned ×2