Recursive polygon subdivision. More...

Classes
struct	TexturedVertex
	A model-space vertex and its texture coordinates. More...

Enumerations
enum	Edge : unsigned { NoEdges = 0 , EdgeAB = 1 << 0 , EdgeBD = 1 << 1 , EdgeCD = 1 << 2 , EdgeAC = 1 << 3 , AllEdges = EdgeAB \| EdgeBD \| EdgeCD \| EdgeAC }
	Which edges of a quad lie on an outer boundary. More...

Functions
constexpr TexturedVertex	half (const TexturedVertex &a, const TexturedVertex &b)
	Midpoint of two vertices, in position and texture coordinates at once.

template<typename Decide , typename EmitQuad , typename EmitFill >
void	divideQuad (const TexturedVertex &a, const TexturedVertex &b, const TexturedVertex &c, const TexturedVertex &d, unsigned depth, unsigned edges, Decide &&decide, EmitQuad &&emitQuad, EmitFill &&emitFill)
	Recursively divide a quad, in three dimensions.

Detailed Description

Recursive polygon subdivision.

The GPU maps textures affinely, so the texture coordinates it interpolates across a primitive are linear in screen space rather than correct in perspective. On a large primitive with a lot of depth variation - a ground plane being the canonical case - that shows up as the texture visibly bending along the diagonal the GPU splits each quad on. Cutting the primitive into smaller ones before handing it over keeps each piece small enough that the error stays under a pixel.

The division happens in three dimensions here, on model-space vertices, before anything is projected. Halving screen coordinates instead is cheaper and does not work: the midpoint of a segment in screen space is not the image of the midpoint in world space, so the sub-vertices get texture coordinates that are wrong in exactly the way subdivision was supposed to fix. Because the model-view transform is affine, midpoints computed in model space survive it, and only the projection of each new vertex has to be paid for.

Two things follow from dividing adaptively, which is the only way to divide that is worth the cycles. First, a tile that gets divided while its neighbour does not leaves a T-junction: the new midpoint does not land exactly on the neighbour's straight edge once both have been rounded to integer screen coordinates, and a crack opens along the boundary. Second, the fix is to draw a triangle over the crack, spanning the two original endpoints and the midpoint that was inserted between them. This header emits those on request, on any edge you declare to be an outer boundary.

Within a single divided primitive there is never a crack, because every shared midpoint is computed once and handed to both children.

Enumeration Type Documentation

◆ Edge

enum psyqo::Subdivision::Edge : unsigned

Which edges of a quad lie on an outer boundary.

Vertices are in the GPU's order, so the four edges are AB and CD running one way and AC and BD running the other. An edge marked here is one whose neighbour may be at a different subdivision level, and is therefore an edge that needs a fill triangle when it gets split. Marking every edge is always safe; it costs one triangle per split edge and cannot produce a crack.

Enumerator
NoEdges
EdgeAB
EdgeBD
EdgeCD
EdgeAC
AllEdges

Function Documentation

◆ divideQuad()

template<typename Decide , typename EmitQuad , typename EmitFill >

void psyqo::Subdivision::divideQuad	(	const TexturedVertex &	a,
		const TexturedVertex &	b,
		const TexturedVertex &	c,
		const TexturedVertex &	d,
		unsigned	depth,
		unsigned	edges,
		Decide &&	decide,
		EmitQuad &&	emitQuad,
		EmitFill &&	emitFill
	)

Recursively divide a quad, in three dimensions.

Vertices are in the GPU's order: A and B are one edge, C and D the opposite one, so the quad reads as a Z rather than as a loop. Each level of recursion splits the quad into four.

Parameters

a	Quad vertex A.
b	Quad vertex B.
c	Quad vertex C.
d	Quad vertex D.
depth	Maximum remaining levels of division. Zero emits immediately. ⚠ This recurses four ways and is bounded only by `depth` and `decide`: the call stack reaches `depth` frames and a fully-divided quad produces `4^depth` leaves, so depth 8 is already 65536 emits. The PS1 stack is small and there is no guard here - pick `depth` from what the scene can afford, and prefer a `decide` that stops on screen size over a large fixed depth.
edges	Which of this quad's edges are outer boundaries, as an `Edge` mask. Pass `AllEdges` for a tile whose neighbours divide independently, and `NoEdges` if nothing next to it can ever be at a different level.
decide	Called as `decide(a, b, c, d, depth)` before each split, and returning false stops the recursion for that quad. This is where a distance or screen-size test goes.
emitQuad	Called as `emitQuad(a, b, c, d)` for every leaf quad.
emitFill	Called as `emitFill(v0, mid, v1)` for every fill triangle, with the two original endpoints and the midpoint inserted between them. Pass something that does nothing to see what the cracks look like without it.

◆ half()

constexpr TexturedVertex psyqo::Subdivision::half	(	const TexturedVertex &	a,
		const TexturedVertex &	b
	)

constexpr

Midpoint of two vertices, in position and texture coordinates at once.

Classes