shithub: libgraphics

Download patch

ref: 98978f5594cb28a60f8f3db8259922871992ce67
parent: 10d114ef7415da437bd27fc6d637db257bb27634
author: rodri <rgl@antares-labs.eu>
date: Fri Apr 11 15:21:55 EDT 2025 

incremental triangle rasterization part 1 (barycentric coordinates)

use the barycoords gradient over the triangle bbox to
step it, without the need to recompute the coordinates
at every pixel. this alleviates the hot loop a little,
and should be more noticeable when we do the same with
the vertex attributes.

part 2 incoming.


--- a/internal.h
+++ b/internal.h
@@ -8,6 +8,8 @@
 typedef struct Tilerparam Tilerparam;
 typedef struct Rasterparam Rasterparam;
 typedef struct Rastertask Rastertask;
+typedef struct pGradient pGradient;
+typedef struct vGradient vGradient;
 
 struct Polygon
 {
@@ -46,6 +48,20 @@
 	Primitive p;
 };
 
+struct pGradient
+{
+	Point3 p0;
+	Point3 dx;
+	Point3 dy;
+};
+
+struct vGradient
+{
+	Vertex v0;
+	Vertex dx;
+	Vertex dy;
+};
+
 /* alloc */
 void *_emalloc(ulong);
 void *_erealloc(void*, ulong);
@@ -74,7 +90,8 @@
 Vertex _dupvertex(Vertex*);
 void _lerpvertex(Vertex*, Vertex*, Vertex*, double);
 void _berpvertex(Vertex*, Vertex*, Vertex*, Vertex*, Point3);
-void _perspdiv(Vertex*, double);
+void _addvertex(Vertex*, Vertex*);
+void _mulvertex(Vertex*, double);
 void _delvattrs(Vertex*);
 void _fprintvattrs(int, Vertex*);
 void _addvattr(Vertexattrs*, char*, int, void*);
--- a/render.c
+++ b/render.c
@@ -86,14 +86,24 @@
 static int
 isfacingback(Primitive *p)
 {
-	double sa;	/* signed area */
+	double sa;	/* signed double area */
 
 	sa = p->v[0].p.x * p->v[1].p.y - p->v[0].p.y * p->v[1].p.x +
 	     p->v[1].p.x * p->v[2].p.y - p->v[1].p.y * p->v[2].p.x +
 	     p->v[2].p.x * p->v[0].p.y - p->v[2].p.y * p->v[0].p.x;
-	return sa <= 0;
+	return sa <= 0;	/* 0 - CCW, 1 - CW */
 }
 
+static int
+istoporleft(Point2 *e0, Point2 *e1)
+{
+	Point2 e01;
+
+	e01 = subpt2(*e1, *e0);
+	return e01.y > 0			/* left */
+		|| (e01.y == 0 && e01.x < 0);	/* top */
+}
+
 static void
 pushtoAbuf(Framebuf *fb, Point p, Color c, float z)
 {
@@ -149,21 +159,6 @@
 	}
 }
 
-static Point3
-_barycoords(Triangle2 t, Point2 p)
-{
-	Point2 p0p1 = subpt2(t.p1, t.p0);
-	Point2 p0p2 = subpt2(t.p2, t.p0);
-	Point2 pp0  = subpt2(t.p0, p);
-
-	Point3 v = crossvec3(Vec3(p0p2.x, p0p1.x, pp0.x), Vec3(p0p2.y, p0p1.y, pp0.y));
-
-	/* handle degenerate triangles—i.e. the ones where every point lies on the same line */
-	if(fabs(v.z) < ε1)
-		return Pt3(-1,-1,-1,1);
-	return Pt3(1 - (v.x + v.y)/v.z, v.y/v.z, v.x/v.z, 1);
-}
-
 static void
 rasterizept(Rastertask *task)
 {
@@ -306,6 +301,22 @@
 	}
 }
 
+static Point3
+_barycoords(Triangle2 t, Point2 p)
+{
+	Point2 p0p1 = subpt2(t.p1, t.p0);
+	Point2 p0p2 = subpt2(t.p2, t.p0);
+	Point2 pp0  = subpt2(t.p0, p);
+
+	Point3 v = crossvec3(Vec3(p0p2.x, p0p1.x, pp0.x), Vec3(p0p2.y, p0p1.y, pp0.y));
+
+	/* handle degenerate triangles—i.e. the ones where every point lies on the same line */
+	if(fabs(v.z) < ε1)
+		return Pt3(-1,-1,-1,1);
+	/* barycoords and signed double area */
+	return Pt3(1 - (v.x + v.y)/v.z, v.y/v.z, v.x/v.z, v.z);
+}
+
 static void
 rasterizetri(Rastertask *task)
 {
@@ -312,6 +323,7 @@
 	SUparams *params;
 	Raster *cr, *zr;
 	Primitive *prim;
+	pGradient ∇bc;
 	Triangle2 t;
 	Point p;
 	Point3 bc;
@@ -331,19 +343,41 @@
 	t.p1 = (Point2){prim->v[1].p.x, prim->v[1].p.y, 1};
 	t.p2 = (Point2){prim->v[2].p.x, prim->v[2].p.y, 1};
 
-	_perspdiv(prim->v+0, prim->v[0].p.w);
-	_perspdiv(prim->v+1, prim->v[1].p.w);
-	_perspdiv(prim->v+2, prim->v[2].p.w);
+	∇bc.p0 = _barycoords(t, (Point2){task->wr.min.x+0.5, task->wr.min.y+0.5, 1});
+	∇bc.dx = divpt3((Point3){t.p2.y - t.p1.y, t.p0.y - t.p2.y, t.p1.y - t.p0.y, 0}, ∇bc.p0.w);
+	∇bc.dy = divpt3((Point3){t.p1.x - t.p2.x, t.p2.x - t.p0.x, t.p0.x - t.p1.x, 0}, ∇bc.p0.w);
 
-	for(p.y = task->wr.min.y; p.y < task->wr.max.y; p.y++)
+	/* TODO find a good method to apply the fill rule */
+//	if(istoporleft(&t.p1, &t.p2)){
+//		∇bc.p0.x -= 1/∇bc.p0.w;
+//		∇bc.dx.x -= 1/∇bc.p0.w;
+//		∇bc.dy.x -= 1/∇bc.p0.w;
+//	}
+//	if(istoporleft(&t.p2, &t.p0)){
+//		∇bc.p0.y -= 1/∇bc.p0.w;
+//		∇bc.dx.y -= 1/∇bc.p0.w;
+//		∇bc.dy.y -= 1/∇bc.p0.w;
+//	}
+//	if(istoporleft(&t.p0, &t.p1)){
+//		∇bc.p0.z -= 1/∇bc.p0.w;
+//		∇bc.dx.z -= 1/∇bc.p0.w;
+//		∇bc.dy.z -= 1/∇bc.p0.w;
+//	}
+
+	/* perspective divide vertex attributes */
+	_mulvertex(prim->v+0, prim->v[0].p.w);
+	_mulvertex(prim->v+1, prim->v[1].p.w);
+	_mulvertex(prim->v+2, prim->v[2].p.w);
+
+	for(p.y = task->wr.min.y; p.y < task->wr.max.y; p.y++){
+		bc = ∇bc.p0;
 	for(p.x = task->wr.min.x; p.x < task->wr.max.x; p.x++){
-		bc = _barycoords(t, (Point2){p.x+0.5,p.y+0.5,1});
 		if(bc.x < 0 || bc.y < 0 || bc.z < 0)
-			continue;
+			goto discard;
 
 		z = fberp(prim->v[0].p.z, prim->v[1].p.z, prim->v[2].p.z, bc);
 		if((ropts & RODepth) && z <= getdepth(zr, p))
-			continue;
+			goto discard;
 
 		/* interpolate z⁻¹ and get actual z */
 		pcz = fberp(prim->v[0].p.w, prim->v[1].p.w, prim->v[2].p.w, bc);
@@ -350,13 +384,12 @@
 		pcz = 1.0/(pcz < ε1? ε1: pcz);
 
 		/* perspective-correct attribute interpolation  */
-		bc = mulpt3(bc, pcz);
-		_berpvertex(task->fsp->v, prim->v+0, prim->v+1, prim->v+2, bc);
+		_berpvertex(task->fsp->v, prim->v+0, prim->v+1, prim->v+2, mulpt3(bc, pcz));
 
 		task->fsp->p = p;
 		c = params->stab->fs(task->fsp);
 		if(c.a == 0)			/* discard non-colors */
-			continue;
+			goto discard;
 		if(ropts & RODepth)
 			putdepth(zr, p, z);
 		if(ropts & ROAbuff)
@@ -371,7 +404,11 @@
 			task->clipr->min = minpt(task->clipr->min, p);
 			task->clipr->max = maxpt(task->clipr->max, addpt(p, (Point){1,1}));
 		}
+discard:
+		bc = addpt3(bc, ∇bc.dx);
 	}
+		∇bc.p0 = addpt3(∇bc.p0, ∇bc.dy);
+	}
 }
 
 static void
@@ -619,8 +656,14 @@
 
 					/* culling */
 					switch(params->camera->cullmode){
-					case CullFront: if(!isfacingback(p)) goto skiptri; break;
-					case CullBack: if(isfacingback(p)) goto skiptri; break;
+					case CullFront:
+						if(!isfacingback(p))
+							goto skiptri;
+						break;
+					case CullBack:
+						if(isfacingback(p))
+							goto skiptri;
+						break;
 					}
 
 					p->v[0].p = ndc2viewport(params->fb, p->v[0].p);
--- a/vertex.c
+++ b/vertex.c
@@ -96,23 +96,38 @@
 	}
 }
 
-/*
- * perspective divide vertex attributes
- */
 void
-_perspdiv(Vertex *v, double z⁻¹)
+_addvertex(Vertex *a, Vertex *b)
 {
+	Vertexattr *va, *vb;
+
+	a->n = addpt3(a->n, b->n);
+	a->c = addpt3(a->c, b->c);
+	a->uv = addpt2(a->uv, b->uv);
+	a->tangent = addpt3(a->tangent, b->tangent);
+	for(va = a->attrs; va < a->attrs + a->nattrs; va++){
+		vb = b->attrs + (va - a->attrs);
+		if(va->type == VAPoint)
+			va->p = addpt3(va->p, vb->p);
+		else
+			va->n += vb->n;
+	}
+}
+
+void
+_mulvertex(Vertex *v, double s)
+{
 	Vertexattr *va;
 
-	v->n = mulpt3(v->n, z⁻¹);
-	v->c = mulpt3(v->c, z⁻¹);
-	v->uv = mulpt2(v->uv, z⁻¹);
-	v->tangent = mulpt3(v->tangent, z⁻¹);
+	v->n = mulpt3(v->n, s);
+	v->c = mulpt3(v->c, s);
+	v->uv = mulpt2(v->uv, s);
+	v->tangent = mulpt3(v->tangent, s);
 	for(va = v->attrs; va < v->attrs + v->nattrs; va++){
 		if(va->type == VAPoint)
-			va->p = mulpt3(va->p, z⁻¹);
+			va->p = mulpt3(va->p, s);
 		else
-			va->n *= z⁻¹;
+			va->n *= s;
 	}
 }