Skip to content

Instantly share code, notes, and snippets.

@steveruizok
Created November 21, 2022 23:49
Show Gist options
  • Save steveruizok/a6900d9db1ed59179f218e0fcef66a6a to your computer and use it in GitHub Desktop.
Save steveruizok/a6900d9db1ed59179f218e0fcef66a6a to your computer and use it in GitHub Desktop.
Get a visibility polygon (for shadow casting).
// segments are all of the segments in all of the shapes in the scene
// point is light point
// viewport is top left, top right, bottom right, bottom left
function getVisibilityPolygon(segments: Segment[], point: Point, viewport: Point[]) {
const brokenSegments: Segment[] = []
const viewportMinCorner = viewport[0]
const viewportMaxCorner = viewport[2]
for (let i = 0; i < segments.length; ++i) {
if (segments[i][0][0] < viewportMinCorner[0] && segments[i][1][0] < viewportMinCorner[0])
continue
if (segments[i][0][1] < viewportMinCorner[1] && segments[i][1][1] < viewportMinCorner[1])
continue
if (segments[i][0][0] > viewportMaxCorner[0] && segments[i][1][0] > viewportMaxCorner[0])
continue
if (segments[i][0][1] > viewportMaxCorner[1] && segments[i][1][1] > viewportMaxCorner[1])
continue
const intersections: Point[] = []
for (let j = 0; j < viewport.length; ++j) {
let k = j + 1
if (k == viewport.length) k = 0
if (
doLineSegmentsIntersect(
segments[i][0][0],
segments[i][0][1],
segments[i][1][0],
segments[i][1][1],
viewport[j][0],
viewport[j][1],
viewport[k][0],
viewport[k][1]
)
) {
const intersect = intersectLines(segments[i][0], segments[i][1], viewport[j], viewport[k])
if (!intersect) continue
if (equal(intersect, segments[i][0]) || equal(intersect, segments[i][1])) continue
intersections.push(intersect)
}
}
const start: Point = [segments[i][0][0], segments[i][0][1]]
while (intersections.length > 0) {
let endIndex = 0
let endDis = distance(start, intersections[0])
for (let j = 1; j < intersections.length; ++j) {
const dis = distance(start, intersections[j])
if (dis < endDis) {
endDis = dis
endIndex = j
}
}
brokenSegments.push([
[start[0], start[1]],
[intersections[endIndex][0], intersections[endIndex][1]],
])
start[0] = intersections[endIndex][0]
start[1] = intersections[endIndex][1]
intersections.splice(endIndex, 1)
}
brokenSegments.push([start, [segments[i][1][0], segments[i][1][1]]])
}
const viewportSegments: Segment[] = []
for (let i = 0; i < brokenSegments.length; ++i) {
if (
inViewport(brokenSegments[i][0], viewportMinCorner, viewportMaxCorner) &&
inViewport(brokenSegments[i][1], viewportMinCorner, viewportMaxCorner)
) {
viewportSegments.push([
[brokenSegments[i][0][0], brokenSegments[i][0][1]],
[brokenSegments[i][1][0], brokenSegments[i][1][1]],
])
}
}
const eps = epsilon * 10
viewportSegments.push([
[viewportMinCorner[0] - eps, viewportMinCorner[1] - eps],
[viewportMaxCorner[0] + eps, viewportMinCorner[1] - eps],
])
viewportSegments.push([
[viewportMaxCorner[0] + eps, viewportMinCorner[1] - eps],
[viewportMaxCorner[0] + eps, viewportMaxCorner[1] + eps],
])
viewportSegments.push([
[viewportMaxCorner[0] + eps, viewportMaxCorner[1] + eps],
[viewportMinCorner[0] - eps, viewportMaxCorner[1] + eps],
])
viewportSegments.push([
[viewportMinCorner[0] - eps, viewportMaxCorner[1] + eps],
[viewportMinCorner[0] - eps, viewportMinCorner[1] - eps],
])
return compute(point, viewportSegments)
}
type Point = number[]
type Segment = number[][]
const epsilon = 0.0000001
function angle(a: Point, b: Point) {
return (Math.atan2(b[1] - a[1], b[0] - a[0]) * 180) / Math.PI
}
function angle2(a: Point, b: Point, c: Point) {
const a1 = angle(a, b)
const a2 = angle(b, c)
let a3 = a1 - a2
if (a3 < 0) a3 += 360
if (a3 > 360) a3 -= 360
return a3
}
function equal(a: Point, b: Point) {
if (Math.abs(a[0] - b[0]) < epsilon && Math.abs(a[1] - b[1]) < epsilon) return true
return false
}
function intersectLines(a1: Point, a2: Point, b1: Point, b2: Point) {
const dbx = b2[0] - b1[0]
const dby = b2[1] - b1[1]
const dax = a2[0] - a1[0]
const day = a2[1] - a1[1]
const u_b = dby * dax - dbx * day
if (u_b != 0) {
const ua = (dbx * (a1[1] - b1[1]) - dby * (a1[0] - b1[0])) / u_b
return [a1[0] - ua * -dax, a1[1] - ua * -day]
}
}
function distance(a: Point, b: Point) {
const dx = a[0] - b[0]
const dy = a[1] - b[1]
return dx * dx + dy * dy
}
function isOnSegment(xi: number, yi: number, xj: number, yj: number, xk: number, yk: number) {
return (
(xi <= xk || xj <= xk) &&
(xk <= xi || xk <= xj) &&
(yi <= yk || yj <= yk) &&
(yk <= yi || yk <= yj)
)
}
function computeDirection(xi: number, yi: number, xj: number, yj: number, xk: number, yk: number) {
const a = (xk - xi) * (yj - yi)
const b = (xj - xi) * (yk - yi)
return a < b ? -1 : a > b ? 1 : 0
}
function doLineSegmentsIntersect(
x1: number,
y1: number,
x2: number,
y2: number,
x3: number,
y3: number,
x4: number,
y4: number
) {
const d1 = computeDirection(x3, y3, x4, y4, x1, y1)
const d2 = computeDirection(x3, y3, x4, y4, x2, y2)
const d3 = computeDirection(x1, y1, x2, y2, x3, y3)
const d4 = computeDirection(x1, y1, x2, y2, x4, y4)
return (
(((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) ||
(d1 == 0 && isOnSegment(x3, y3, x4, y4, x1, y1)) ||
(d2 == 0 && isOnSegment(x3, y3, x4, y4, x2, y2)) ||
(d3 == 0 && isOnSegment(x1, y1, x2, y2, x3, y3)) ||
(d4 == 0 && isOnSegment(x1, y1, x2, y2, x4, y4))
)
}
function sortPoints(position: Point, segments: Segment[]) {
const points = new Array(segments.length * 2)
for (let i = 0; i < segments.length; ++i) {
for (let j = 0; j < 2; ++j) {
const a = angle(segments[i][j], position)
points[2 * i + j] = [i, j, a]
}
}
points.sort(function (a, b) {
return a[2] - b[2]
})
return points
}
function lessThan(
index1: number,
index2: number,
position: Point,
segments: Segment[],
destination: Point
) {
const inter1 = intersectLines(segments[index1][0], segments[index1][1], position, destination)
const inter2 = intersectLines(segments[index2][0], segments[index2][1], position, destination)
if (!inter1 || !inter2) {
return true
} else {
if (!equal(inter1, inter2)) {
const d1 = distance(inter1, position)
const d2 = distance(inter2, position)
return d1 < d2
}
let end1 = 0
let end2 = 0
if (equal(inter1, segments[index1][0])) end1 = 1
if (equal(inter2, segments[index2][0])) end2 = 1
const a1 = angle2(segments[index1][end1], inter1, position)
const a2 = angle2(segments[index2][end2], inter2, position)
if (a1 < 180) {
if (a2 > 180) return true
return a2 < a1
}
return a1 < a2
}
}
function parent(index: number) {
return Math.floor((index - 1) / 2)
}
function child(index: number) {
return 2 * index + 1
}
function insert(
index: number,
heap: any,
position: Point,
segments: Segment[],
destination: Point,
map: any
) {
const intersect = intersectLines(segments[index][0], segments[index][1], position, destination)
if (!intersect) return
let cur = heap.length
heap.push(index)
map[index] = cur
while (cur > 0) {
const par = parent(cur)
if (!lessThan(heap[cur], heap[par], position, segments, destination)) {
break
}
map[heap[par]] = cur
map[heap[cur]] = par
const temp = heap[cur]
heap[cur] = heap[par]
heap[par] = temp
cur = par
}
}
function remove(
index: number,
heap: any,
position: Point,
segments: Segment[],
destination: Point,
map: any
) {
map[heap[index]] = -1
if (index == heap.length - 1) {
heap.pop()
return
}
heap[index] = heap.pop()
map[heap[index]] = index
let cur = index
const par = parent(cur)
if (cur != 0 && lessThan(heap[cur], heap[par], position, segments, destination)) {
while (cur > 0) {
const par = parent(cur)
if (!lessThan(heap[cur], heap[par], position, segments, destination)) {
break
}
map[heap[par]] = cur
map[heap[cur]] = par
const temp = heap[cur]
heap[cur] = heap[par]
heap[par] = temp
cur = par
}
} else {
// eslint-disable-next-line no-constant-condition
while (true) {
const left = child(cur)
const right = left + 1
if (
left < heap.length &&
lessThan(heap[left], heap[cur], position, segments, destination) &&
(right == heap.length || lessThan(heap[left], heap[right], position, segments, destination))
) {
map[heap[left]] = cur
map[heap[cur]] = left
const temp = heap[left]
heap[left] = heap[cur]
heap[cur] = temp
cur = left
} else if (
right < heap.length &&
lessThan(heap[right], heap[cur], position, segments, destination)
) {
map[heap[right]] = cur
map[heap[cur]] = right
const temp = heap[right]
heap[right] = heap[cur]
heap[cur] = temp
cur = right
} else break
}
}
}
function compute(position: Point, segments: Segment[]) {
const bounded: Segment[] = []
let minX = position[0]
let minY = position[1]
let maxX = position[0]
let maxY = position[1]
for (let i = 0; i < segments.length; ++i) {
for (let j = 0; j < 2; ++j) {
minX = Math.min(minX, segments[i][j][0])
minY = Math.min(minY, segments[i][j][1])
maxX = Math.max(maxX, segments[i][j][0])
maxY = Math.max(maxY, segments[i][j][1])
}
bounded.push([
[segments[i][0][0], segments[i][0][1]],
[segments[i][1][0], segments[i][1][1]],
])
}
--minX
--minY
++maxX
++maxY
bounded.push([
[minX, minY],
[maxX, minY],
])
bounded.push([
[maxX, minY],
[maxX, maxY],
])
bounded.push([
[maxX, maxY],
[minX, maxY],
])
bounded.push([
[minX, maxY],
[minX, minY],
])
const polygon: number[][] = []
const sorted = sortPoints(position, bounded)
const map = new Array(bounded.length).fill(-1)
const heap: number[] = []
const start: Point = [position[0] + 1, position[1]]
for (let i = 0; i < bounded.length; ++i) {
const a1 = angle(bounded[i][0], position)
const a2 = angle(bounded[i][1], position)
let active = false
if (a1 > -180 && a1 <= 0 && a2 <= 180 && a2 >= 0 && a2 - a1 > 180) active = true
if (a2 > -180 && a2 <= 0 && a1 <= 180 && a1 >= 0 && a1 - a2 > 180) active = true
if (active) {
insert(i, heap, position, bounded, start, map)
}
}
for (let i = 0; i < sorted.length; ) {
let extend = false
let shorten = false
const orig = i
let vertex = bounded[sorted[i][0]][sorted[i][1]]
const old_segment = heap[0]
do {
if (map[sorted[i][0]] != -1) {
if (sorted[i][0] == old_segment) {
extend = true
vertex = bounded[sorted[i][0]][sorted[i][1]]
}
remove(map[sorted[i][0]], heap, position, bounded, vertex, map)
} else {
insert(sorted[i][0], heap, position, bounded, vertex, map)
if (heap[0] != old_segment) {
shorten = true
}
}
++i
if (i == sorted.length) break
} while (sorted[i][2] < sorted[orig][2] + epsilon)
if (extend) {
polygon.push(vertex)
const cur = intersectLines(bounded[heap[0]][0], bounded[heap[0]][1], position, vertex)
if (cur && !equal(cur, vertex)) {
polygon.push(cur)
}
} else if (shorten) {
const i1 = intersectLines(bounded[old_segment][0], bounded[old_segment][1], position, vertex)
if (i1) {
polygon.push(i1)
}
const i2 = intersectLines(bounded[heap[0]][0], bounded[heap[0]][1], position, vertex)
if (i2) {
polygon.push(i2)
}
}
}
return polygon
}
export function inViewport(position: Point, viewportMinCorner: Point, viewportMaxCorner: Point) {
if (position[0] < viewportMinCorner[0] - epsilon) return false
if (position[1] < viewportMinCorner[1] - epsilon) return false
if (position[0] > viewportMaxCorner[0] + epsilon) return false
if (position[1] > viewportMaxCorner[1] + epsilon) return false
return true
}
export function inPolygon(position: Point, polygon: Point[]) {
let val = polygon[0][0]
for (let i = 0; i < polygon.length; ++i) {
val = Math.min(polygon[i][0], val)
val = Math.min(polygon[i][1], val)
}
const edge: Point = [val - 1, val - 1]
let parity = 0
for (let i = 0; i < polygon.length; ++i) {
let j = i + 1
if (j == polygon.length) j = 0
if (
doLineSegmentsIntersect(
edge[0],
edge[1],
position[0],
position[1],
polygon[i][0],
polygon[i][1],
polygon[j][0],
polygon[j][1]
)
) {
const intersect = intersectLines(edge, position, polygon[i], polygon[j])
if (!intersect) {
++parity
} else {
if (equal(position, intersect)) return true
if (equal(intersect, polygon[i])) {
if (angle2(position, edge, polygon[j]) < 180) ++parity
} else if (equal(intersect, polygon[j])) {
if (angle2(position, edge, polygon[i]) < 180) ++parity
} else {
++parity
}
}
}
}
return parity % 2 != 0
}
function convertToSegments(polygons: Segment[]) {
const segments: Segment[] = []
for (let i = 0; i < polygons.length; ++i) {
for (let j = 0; j < polygons[i].length; ++j) {
let k = j + 1
if (k == polygons[i].length) k = 0
segments.push([
[polygons[i][j][0], polygons[i][j][1]],
[polygons[i][k][0], polygons[i][k][1]],
])
}
}
return segments
}
function breakIntersections(segments: Segment[]) {
const output = []
for (let i = 0; i < segments.length; ++i) {
const intersections = []
for (let j = 0; j < segments.length; ++j) {
if (i == j) continue
if (
doLineSegmentsIntersect(
segments[i][0][0],
segments[i][0][1],
segments[i][1][0],
segments[i][1][1],
segments[j][0][0],
segments[j][0][1],
segments[j][1][0],
segments[j][1][1]
)
) {
const intersect = intersectLines(
segments[i][0],
segments[i][1],
segments[j][0],
segments[j][1]
)
if (!intersect) continue
if (equal(intersect, segments[i][0]) || equal(intersect, segments[i][1])) continue
intersections.push(intersect)
}
}
const start: Point = [segments[i][0][0], segments[i][0][1]]
while (intersections.length > 0) {
let endIndex = 0
let endDis = distance(start, intersections[0])
for (let j = 1; j < intersections.length; ++j) {
const dis = distance(start, intersections[j])
if (dis < endDis) {
endDis = dis
endIndex = j
}
}
output.push([
[start[0], start[1]],
[intersections[endIndex][0], intersections[endIndex][1]],
])
start[0] = intersections[endIndex][0]
start[1] = intersections[endIndex][1]
intersections.splice(endIndex, 1)
}
output.push([start, [segments[i][1][0], segments[i][1][1]]])
}
return output
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment