4 ms·

I wish we could have just one of these tutorials properly cover the concern of triangle clipping. This is the part that I struggle with the most in a software r

by bob1029 3mo ago

I wish we could have just one of these tutorials properly cover the concern of triangle clipping. This is the part that I struggle with the most in a software renderer. If you are going to be building a practical one, this is something you will eventually have to deal with, even for super basic scenes. Any time geometry intersects the view frustum you need to clip those triangles.

deleted 3mo ago
[deleted]
ggambetta 3mo ago
I have a whole chapter on that! https://gabrielgambetta.com/computer-graphics-from-scratch/11-clipping.html https://gabrielgambetta.com/computer-graphics-from-scratch/1...
- aninteger 3mo ago
  Sorta unrelated but I really enjoy (I don't want to use the past tense as I often refer back to it) your article on Emulator Backed Remakes (https://gabrielgambetta.com/remakes.html https://gabrielgambetta.com/remakes.html). Thanks!
  - ggambetta 3mo ago
    Thanks for saying that :) Have you built something based on that idea? I still haven't, but I'm thinking on throwing some Claude at it for the most mechanical parts.
- yunnpp 3mo ago
  I bought and I am reading through your book as I build a sw rasterizer. On the chapter of clipping, it was not entirely clear to me how many planes you clip against and how many triangles result. Presumably if you clip against all 6 planes, you get 3+6-2 = 7 triangles in the worst case, which is kind of annoying. However, if you're going to use the AAAB triangle raster method as described in this HN post, then it seems there's no need to clip against left/right/top/bottom planes of the frustum, since it is simpler to just clip the screen-space AABB of the triangle instead. So one just needs to clip against near/far. This is simpler and faster. I was curious if you had given any thought on that, or if you plan on working on a second book with more details on these nuances.
  - ggambetta 3mo ago
    My book tries to be as accessible as possible; a high schooler with little to no knowledge of linear algebra should be able to understand all of it. So in every case I've chosen simplicity (code and/or conceptually) over performance, but without sacrificing correctness. Not always an easy balancing act! I would not recommend anyone to write a production rasterizer using the algorithms in my book. This website seems more performance-focused (Bresenham is the obvious choice to draw lines, for example). Specifically about clipping, you can ignore all the planes except the near plane, and everything will be fine. You'll try to draw more pixels outside the canvas but that's just slow, not problematic. The near plane does protect you from divisions by zero and from points with negative Z, which project upside down and mess things up.
    - yunnpp 3mo ago
      Yeah, the book has a nice balance, it's precisely why I picked it up. It allowed me to get something up and running quickly, then iterate over it.
thechao 3mo ago
You only need to clip triangles is you're worried about attribute interpolation for very large triangles. There's two ways to handle this: (1) discard (fast but not a great user experience); or, (2) primitive synthesis. Just frustum clipping is enabled by point picking in the local tile. Primitive synthesis requires some FP kung fu; but, is easiest done in barycentric space against a reverse transformed clipping rectangle. This lets you carefully control clip rounding error using either doubles or (better) fixed point. Abrash likes to use integer fixed point, but that is historical — modern fixed point can be handled with careful control of the fp unit in the mantissa. The major issue is regenerating the Z and the 1/Z values for the new vertices of the synthesized primitives. Everything else should flow down the pipe naturally, assuming a deferred attribute synthesis rasterizer. There are examples in the open source version of my rasterizer: OpenSWR.org.
- delta_p_delta_x 3mo ago
  I'm clearly super old-school when it comes to rasterisation, and a lot of this has flown above my head. I have a ton of questions; I hope you can answer them. > (1) discard (fast but not a great user experience) What are we discarding here, and why is it fast but not a great user experience? > (2) primitive synthesis I assume this is retriangulating clipped triangles that are now no longer triangles? > reverse transformed clipping rectangle Which spaces does this reverse transformation map from and to? I assume the clipping rectangle here is the triangle's AABB in raster space (or as you say, barycentric space). > integer fixed point, but that is historical — modern fixed point can be handled with careful control of the fp unit in the mantissa So we are no longer doing 16.16 fixed point, but tweaking the FP representation itself? > The major issue is regenerating the Z and the 1/Z values for the new vertices Why is this a major issue? > deferred attribute synthesis rasterizer I assume this means attributes are perspective-correct interpolated in raster space.
  - ack_complete 3mo ago
    My own knowledge of GPU rasterization may be dated, but IIRC GPUs tend to rely on guard band clipping up to a guard band threshold before using geometric clipping. The guard band clipping involves rejecting 2D coarse rasterization blocks that are fully outside of the scissor rect. This is just a quick rectangle check, but the tradeoff is that a larger guard band means more GPU time lost in over-rasterization and potential higher precision requirements for rasterization values (which could be fixed point). Beyond the guard band, the triangles are clipped in floating point against the frustum clip planes.
Sharlin 3mo ago
My renderer attempts always got stuck on the "should implement clipping" phase too, until I finally bit the bullet and managed to write a working one without much effort, independently "rediscovering" the Sutherland–Hodgman algorithm [1] as I found out later (googling it beforehand would've been cheating, of course). The algorithm itself is fairly straightforward and intuitive, I think the biggest mental block is the weirdness of the projective space and working with homogeneous coordinates (actually the only frustum plane that you have to clip against in P₃(ℝ) is the front plane, the rest could be clipped after the perspective division, but no reason not to do it all at the same time while you're at it). The plane equations in the clip space are super simple, basically the six equations of the form ax + by + cz = w simplify to x = ±w y = ±w z = ±w. Meaning, for example, that if the x coordinate of your vertex is greater than the w coordinate, that vertex is outside the right clipping plane. The Sutherland–Hodgman itself goes something like this: # Returns true if point is inside the half-space defined by plane def point_inside_plane(point, plane) -> bool: # single dot product, can be further simplified # Returns t such that the edge (p1, p2) intersects plane at lerp(t, p1, p2) def edge_intersect_plane(edge: (Point, Point), plane) -> float: # single dot product, can be further simplified # Given the vertices of a simple polygon and a plane, # returns the part of the polygon fully inside the plane def clip_against_plane(poly: [Vertex], plane): let result: [Vertex] = [] let [(v_1, v_2), (v_2, v_3), ..., (v_n, v_1)] = poly.edges() for each (v_i, v_j) of the edges: let i_inside = point_inside_plane(v_i, plane) let j_inside = point_inside_plane(n_j, plane) if i_inside and j_inside: # v_j will be pushed on the next iteration! result.push(v_i) else if not i_inside and not j_inside: pass # Nothing to do! else: # One is inside, the other is not, we have to clip let t = edge_intersect_plane((v_i.pos, v_j.pos), plane) # Synthetize a new vertex straddling the plane let v_new = Vertex( pos = lerp(t, v_i.pos, v_j.pos), # For each vertex attribute attrib = lerp(t, v_i.attrib, v_j.attrib) ) if i_inside: result.push(v_i); result.push(v_new) # discard v_j else: result.push(v_new); result.push(v_j) # discard v_i return result Then you just call this for all the planes so that the output of one call becomes the input for the next call! The end result of this process is a convex polygon (of at most nine vertices for a triangle against six planes), which can be trivially triangulated. You can make the whole process faster by precomputing so-called outcodes which allow you to avoid clipping triangles known to be entirely outside at last one plane, or entirely inside every plane. [1]: I. Sutherland and G. Hodgman. 1974. "Reentrant polygon clipping." Communications of the ACM, Volume 17, Issue. Available: https://dl.acm.org/doi/10.1145/360767.360802 https://dl.acm.org/doi/10.1145/360767.360802

by bob1029 3mo ago

deleted 3mo ago

[deleted]

ggambetta 3mo ago

I have a whole chapter on that! https://gabrielgambetta.com/computer-graphics-from-scratch/11-clipping.html https://gabrielgambetta.com/computer-graphics-from-scratch/1...

aninteger 3mo ago
Sorta unrelated but I really enjoy (I don't want to use the past tense as I often refer back to it) your article on Emulator Backed Remakes (https://gabrielgambetta.com/remakes.html https://gabrielgambetta.com/remakes.html). Thanks!
- ggambetta 3mo ago
  Thanks for saying that :) Have you built something based on that idea? I still haven't, but I'm thinking on throwing some Claude at it for the most mechanical parts.
yunnpp 3mo ago
I bought and I am reading through your book as I build a sw rasterizer. On the chapter of clipping, it was not entirely clear to me how many planes you clip against and how many triangles result. Presumably if you clip against all 6 planes, you get 3+6-2 = 7 triangles in the worst case, which is kind of annoying. However, if you're going to use the AAAB triangle raster method as described in this HN post, then it seems there's no need to clip against left/right/top/bottom planes of the frustum, since it is simpler to just clip the screen-space AABB of the triangle instead. So one just needs to clip against near/far. This is simpler and faster. I was curious if you had given any thought on that, or if you plan on working on a second book with more details on these nuances.
- ggambetta 3mo ago
  My book tries to be as accessible as possible; a high schooler with little to no knowledge of linear algebra should be able to understand all of it. So in every case I've chosen simplicity (code and/or conceptually) over performance, but without sacrificing correctness. Not always an easy balancing act! I would not recommend anyone to write a production rasterizer using the algorithms in my book. This website seems more performance-focused (Bresenham is the obvious choice to draw lines, for example). Specifically about clipping, you can ignore all the planes except the near plane, and everything will be fine. You'll try to draw more pixels outside the canvas but that's just slow, not problematic. The near plane does protect you from divisions by zero and from points with negative Z, which project upside down and mess things up.
  - yunnpp 3mo ago
    Yeah, the book has a nice balance, it's precisely why I picked it up. It allowed me to get something up and running quickly, then iterate over it.

thechao 3mo ago

You only need to clip triangles is you're worried about attribute interpolation for very large triangles. There's two ways to handle this: (1) discard (fast but not a great user experience); or, (2) primitive synthesis. Just frustum clipping is enabled by point picking in the local tile. Primitive synthesis requires some FP kung fu; but, is easiest done in barycentric space against a reverse transformed clipping rectangle. This lets you carefully control clip rounding error using either doubles or (better) fixed point. Abrash likes to use integer fixed point, but that is historical — modern fixed point can be handled with careful control of the fp unit in the mantissa. The major issue is regenerating the Z and the 1/Z values for the new vertices of the synthesized primitives. Everything else should flow down the pipe naturally, assuming a deferred attribute synthesis rasterizer. There are examples in the open source version of my rasterizer: OpenSWR.org.

delta_p_delta_x 3mo ago
I'm clearly super old-school when it comes to rasterisation, and a lot of this has flown above my head. I have a ton of questions; I hope you can answer them. > (1) discard (fast but not a great user experience) What are we discarding here, and why is it fast but not a great user experience? > (2) primitive synthesis I assume this is retriangulating clipped triangles that are now no longer triangles? > reverse transformed clipping rectangle Which spaces does this reverse transformation map from and to? I assume the clipping rectangle here is the triangle's AABB in raster space (or as you say, barycentric space). > integer fixed point, but that is historical — modern fixed point can be handled with careful control of the fp unit in the mantissa So we are no longer doing 16.16 fixed point, but tweaking the FP representation itself? > The major issue is regenerating the Z and the 1/Z values for the new vertices Why is this a major issue? > deferred attribute synthesis rasterizer I assume this means attributes are perspective-correct interpolated in raster space.
- ack_complete 3mo ago
  My own knowledge of GPU rasterization may be dated, but IIRC GPUs tend to rely on guard band clipping up to a guard band threshold before using geometric clipping. The guard band clipping involves rejecting 2D coarse rasterization blocks that are fully outside of the scissor rect. This is just a quick rectangle check, but the tradeoff is that a larger guard band means more GPU time lost in over-rasterization and potential higher precision requirements for rasterization values (which could be fixed point). Beyond the guard band, the triangles are clipped in floating point against the frustum clip planes.

Sharlin 3mo ago

My renderer attempts always got stuck on the "should implement clipping" phase too, until I finally bit the bullet and managed to write a working one without much effort, independently "rediscovering" the Sutherland–Hodgman algorithm [1] as I found out later (googling it beforehand would've been cheating, of course). The algorithm itself is fairly straightforward and intuitive, I think the biggest mental block is the weirdness of the projective space and working with homogeneous coordinates (actually the only frustum plane that you have to clip against in P₃(ℝ) is the front plane, the rest could be clipped after the perspective division, but no reason not to do it all at the same time while you're at it). The plane equations in the clip space are super simple, basically the six equations of the form ax + by + cz = w simplify to x = ±w y = ±w z = ±w. Meaning, for example, that if the x coordinate of your vertex is greater than the w coordinate, that vertex is outside the right clipping plane. The Sutherland–Hodgman itself goes something like this: # Returns true if point is inside the half-space defined by plane def point_inside_plane(point, plane) -> bool: # single dot product, can be further simplified # Returns t such that the edge (p1, p2) intersects plane at lerp(t, p1, p2) def edge_intersect_plane(edge: (Point, Point), plane) -> float: # single dot product, can be further simplified # Given the vertices of a simple polygon and a plane, # returns the part of the polygon fully inside the plane def clip_against_plane(poly: [Vertex], plane): let result: [Vertex] = [] let [(v_1, v_2), (v_2, v_3), ..., (v_n, v_1)] = poly.edges() for each (v_i, v_j) of the edges: let i_inside = point_inside_plane(v_i, plane) let j_inside = point_inside_plane(n_j, plane) if i_inside and j_inside: # v_j will be pushed on the next iteration! result.push(v_i) else if not i_inside and not j_inside: pass # Nothing to do! else: # One is inside, the other is not, we have to clip let t = edge_intersect_plane((v_i.pos, v_j.pos), plane) # Synthetize a new vertex straddling the plane let v_new = Vertex( pos = lerp(t, v_i.pos, v_j.pos), # For each vertex attribute attrib = lerp(t, v_i.attrib, v_j.attrib) ) if i_inside: result.push(v_i); result.push(v_new) # discard v_j else: result.push(v_new); result.push(v_j) # discard v_i return result Then you just call this for all the planes so that the output of one call becomes the input for the next call! The end result of this process is a convex polygon (of at most nine vertices for a triangle against six planes), which can be trivially triangulated. You can make the whole process faster by precomputing so-called outcodes which allow you to avoid clipping triangles known to be entirely outside at last one plane, or entirely inside every plane. [1]: I. Sutherland and G. Hodgman. 1974. "Reentrant polygon clipping." Communications of the ACM, Volume 17, Issue. Available: https://dl.acm.org/doi/10.1145/360767.360802 https://dl.acm.org/doi/10.1145/360767.360802