Created
January 31, 2026 23:53
-
-
Save RandyGaul/15fb3d77b1470012690b5cb51907f38b to your computer and use it in GitHub Desktop.
Tile based edge generation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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)); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment