Tile based edge generation

occluder.h

// Occluder edge extraction utility.
//
// Computes the union boundary of axis-aligned bounding boxes (AABBs), producing
// a set of merged edge segments. Handles overlapping/adjacent AABBs correctly
// by merging shared edges.
//
// Usage:
//   OccluderQuery q = occluder_begin();
//   occluder_add_aabb(&q, aabb);
//   ...
//   dyna Segment* edges = occluder_finish(&q);
//   // Use edges...
//   afree(edges);

//--------------------------------------------------------------------------------------------------
// Public API;

typedef struct Segment
{
	v2 a, b;
} Segment;

typedef struct OccluderEdge
{
	float pos;       // X for vertical edges, Y for horizontal
	float min, max;  // Interval along the perpendicular axis
	int dir;         // +1 = outward facing (right/up), -1 = inward facing (left/down)
} OccluderEdge;

typedef struct OccluderQuery
{
	dyna OccluderEdge* v_edges;  // Vertical edges (left/right sides of AABBs)
	dyna OccluderEdge* h_edges;  // Horizontal edges (top/bottom sides of AABBs)
} OccluderQuery;

OccluderQuery occluder_begin();
void occluder_add_aabb(OccluderQuery* q, CF_Aabb bb);
dyna Segment* occluder_finish(OccluderQuery* q);

//--------------------------------------------------------------------------------------------------
// Implementation details.

typedef struct OccluderEvent
{
	float t;
	int delta;
} OccluderEvent;

int occluder_compare_events(const void* a, const void* b)
{
	float ta = ((OccluderEvent*)a)->t;
	float tb = ((OccluderEvent*)b)->t;
	return (ta > tb) - (ta < tb);
}

int occluder_compare_edges_by_pos(const void* a, const void* b)
{
	float pa = ((OccluderEdge*)a)->pos;
	float pb = ((OccluderEdge*)b)->pos;
	return (pa > pb) - (pa < pb);
}

// Processes all edges at the same position using a sweep line algorithm.
// Merges overlapping intervals and emits only the union boundary.
void occluder_process_edge_group(OccluderEdge* group, int count, bool is_vertical, dyna Segment** out_segs)
{
	if (count == 0) return;

	float pos = group[0].pos;

	// Build events from all intervals.
	dyna OccluderEvent* events = atmp(OccluderEvent, 256);
	for (int i = 0; i < count; ++i) {
		OccluderEvent e1 = { .t = group[i].min, .delta = group[i].dir };
		OccluderEvent e2 = { .t = group[i].max, .delta = -group[i].dir };
		apush(events, e1);
		apush(events, e2);
	}

	qsort(events, asize(events), sizeof(OccluderEvent), occluder_compare_events);

	// Sweep and emit edges where coverage transitions to/from zero.
	int coverage = 0;
	float segment_start = 0;
	int segment_dir = 0;

	int i = 0;
	while (i < asize(events)) {
		float t = events[i].t;

		// Accumulate all deltas at this t (handles adjacent intervals).
		int delta_sum = 0;
		while (i < asize(events) && events[i].t == t) {
			delta_sum += events[i].delta;
			++i;
		}

		int prev_coverage = coverage;
		coverage += delta_sum;

		if (prev_coverage == 0 && coverage != 0) {
			// Entering boundary region.
			segment_start = t;
			segment_dir = coverage > 0 ? 1 : -1;
		} else if (prev_coverage != 0 && coverage == 0) {
			// Exiting boundary region - emit segment.
			// Winding convention: segment_normal() computes 90 CCW rotation of (b-a).
			// To get outward normal, we set winding so that rotation points outward.
			Segment seg = {0};
			if (is_vertical) {
				// Vertical edge at X = pos, spanning Y = [segment_start, t].
				// Right-facing (dir > 0): normal=(1,0), need d=(0,-), so a at top, b at bottom.
				// Left-facing (dir < 0): normal=(-1,0), need d=(0,+), so a at bottom, b at top.
				if (segment_dir > 0) {
					seg.a = V2(pos, t);
					seg.b = V2(pos, segment_start);
				} else {
					seg.a = V2(pos, segment_start);
					seg.b = V2(pos, t);
				}
			} else {
				// Horizontal edge at Y = pos, spanning X = [segment_start, t].
				// Up-facing (dir > 0): normal=(0,1), need d=(+,0), so a at left, b at right.
				// Down-facing (dir < 0): normal=(0,-1), need d=(-,0), so a at right, b at left.
				if (segment_dir > 0) {
					seg.a = V2(segment_start, pos);
					seg.b = V2(t, pos);
				} else {
					seg.a = V2(t, pos);
					seg.b = V2(segment_start, pos);
				}
			}
			apush(*out_segs, seg);
		}
	}

	afree(events);
}

OccluderQuery occluder_begin()
{
	OccluderQuery q = {0};
	return q;
}

void occluder_add_aabb(OccluderQuery* q, CF_Aabb bb)
{
	// Left edge: facing left (dir = -1)
	OccluderEdge left = { .pos = bb.min.x, .min = bb.min.y, .max = bb.max.y, .dir = -1 };
	apush(q->v_edges, left);

	// Right edge: facing right (dir = +1)
	OccluderEdge right = { .pos = bb.max.x, .min = bb.min.y, .max = bb.max.y, .dir = +1 };
	apush(q->v_edges, right);

	// Bottom edge: facing down (dir = -1)
	OccluderEdge bottom = { .pos = bb.min.y, .min = bb.min.x, .max = bb.max.x, .dir = -1 };
	apush(q->h_edges, bottom);

	// Top edge: facing up (dir = +1)
	OccluderEdge top = { .pos = bb.max.y, .min = bb.min.x, .max = bb.max.x, .dir = +1 };
	apush(q->h_edges, top);
}

dyna Segment* occluder_finish(OccluderQuery* q)
{
	dyna Segment* segs = atmp(Segment, 256);

	// Sort edges by position.
	if (asize(q->v_edges) > 0) {
		qsort(q->v_edges, asize(q->v_edges), sizeof(OccluderEdge), occluder_compare_edges_by_pos);
	}
	if (asize(q->h_edges) > 0) {
		qsort(q->h_edges, asize(q->h_edges), sizeof(OccluderEdge), occluder_compare_edges_by_pos);
	}

	// Process vertical edges grouped by X position.
	int group_start = 0;
	for (int i = 0; i <= asize(q->v_edges); ++i) {
		bool end_of_group = (i == asize(q->v_edges)) || (i > 0 && q->v_edges[i].pos != q->v_edges[group_start].pos);
		if (end_of_group && i > group_start) {
			occluder_process_edge_group(q->v_edges + group_start, i - group_start, true, &segs);
			group_start = i;
		}
	}

	// Process horizontal edges grouped by Y position.
	group_start = 0;
	for (int i = 0; i <= asize(q->h_edges); ++i) {
		bool end_of_group = (i == asize(q->h_edges)) || (i > 0 && q->h_edges[i].pos != q->h_edges[group_start].pos);
		if (end_of_group && i > group_start) {
			occluder_process_edge_group(q->h_edges + group_start, i - group_start, false, &segs);
			group_start = i;
		}
	}

	afree(q->v_edges);
	afree(q->h_edges);
	q->v_edges = NULL;
	q->h_edges = NULL;

	return segs;
}

v2 segment_normal(Segment seg)
{
	v2 d = sub(seg.b, seg.a);
	return norm(skew(d));
}