Posted by mpweiher 5 hours ago
https://github.com/kshitijl/tinyrenderer-rs
if anyone is interested! The repo has lots and lots of in-progress screenshots so you can see the renderer come to life, plus all the hilarious visual bugs along the way.
I learned a lot! My biggest lesson, other than the specifics of how rendering works, was that modern CPUs are really fast: a single-threaded CPU renderer can definitely run an interactive 3D game with some fancy special effects.
(I originally wrote this a few years ago but other people maintain it now)
[1]: https://www.amazon.co.uk/Mathematics-Computer-Graphics-John-...
There are examples in the open source version of my rasterizer: OpenSWR.org.
> (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.
On the flip side, if a triangle is 'really big' we need a guard band to either reject or subdivide triangles. The first one is fairly cheap -- we're throwing away the triangle! -- the second one is a better user experience, but requires synthesizing primitives. (The worst case is that a single triangle becomes 5 triangles, I think.) Each of those triangles needs its Z and 1/Z calculated in fixed precision. The precision of that fixed precision (though) can be clamped to the local tile; so, even though the global precision might need to be 25.25 (or whatever), the tile-local precision is only 4.9 (or whatever), with an intermediate 24.24 that can be handled with a float-float patch-up. The computation should all occur in the triangle's barycentric space: that means you need the inverted barycentric mapping to invert the guard band into the triangle's barycentric space. You do that because it lets you control the fixed point calculations better. (You can leave off the inverted determinant multiplication until the last moment.)
When I say "deferred attribute synthesis" I mean that we don't calculate attributes in the vertex shader. Instead, we calculate the barycentric, Z, and 1/Z values and pass those along. When we fire up the tile walker for the triangle (in general we only need 1-3 tiles), we calculate the attributes "on the fly, as they're used" and then let the compiler do CSE to fold down the replicated constructions.
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
Personally I’d have gone with a teapot as my demo but I don’t see anything shocking about the model the author chose.
mbappe'?