Line of sight (Field of view) algorithm

import io.data2viz.color.* import io.data2viz.geom.* import io.data2viz.math.* import io.data2viz.viz.* import io.data2viz.geom.Point import io.data2viz.geom.Polygon import io.data2viz.geom.contains import io.data2viz.geom.polygonHull import io.data2viz.math.Angle import io.data2viz.math.PI import io.data2viz.math.deg import kotlin.math.atan2 import kotlin.math.cos import kotlin.math.sin import kotlin.math.sqrt import kotlin.random.Random internal var vizWidth = 800.0 internal var vizHeight = 800.0 lateinit var model: LineOfSightModel fun main() { lineOfSightViz().bindRendererOnNewCanvas() } fun lineOfSightViz(): Viz = viz { width = vizWidth height = vizHeight val backgroundLayer = activeLayer val polygonsLayer = layer() val lineOfSightLayer = layer() model = LineOfSightModel(LineOfSightConfig(width, height)) fun buildBackground() { backgroundLayer.clear() backgroundLayer.rect { fill = 0x232c3b.col x = .0 y = .0 width = vizWidth height = vizHeight } } fun buildPolygons(polygons: List<Polygon>) { polygonsLayer.clear() with(polygonsLayer) { polygons.forEach { polygon -> path { fill = Colors.Web.black stroke = null moveTo(polygon.points.first().x, polygon.points.first().y) (1 until polygon.points.size).forEach { lineTo(polygon.points[it].x, polygon.points[it].y) } closePath() } } } } buildBackground() buildPolygons(model.polygons) val radialGradient = lightGradient() animation { lineOfSightLayer.clear() model.moveLight() radialGradient.center = model.lightPos val points = model.getSightPolygon().points lineOfSightLayer.path { moveTo(points.first().x, points.first().y) fill = radialGradient stroke = null points.forEach { point -> lineTo(point.x, point.y) } closePath() } } onResize { newWidth, newHeight -> vizWidth = newWidth vizHeight = newHeight width = vizWidth height = vizHeight model = LineOfSightModel(LineOfSightConfig(width, height)) buildBackground() buildPolygons(model.polygons) } } private fun lightGradient(): RadialGradient { val lightColor = 0xFFFFFF.col val fromColor = 0xFFFF00.col val endColor = Colors.rgb(0xFFFF00, 0.pct) return Colors.Gradient.radial(model.lightPos, .7 * vizWidth) .withColor(lightColor, 0.pct) .andColor(lightColor, 1.pct) .andColor(fromColor, 2.pct) .andColor(endColor, 100.pct) } data class LineOfSightConfig( val width: Double, val height: Double, val polygonNb: Int = 20, val polygonSize: Double = 0.15, val randomPointsNb: Int = 8 ) class LineOfSightModel(config: LineOfSightConfig) { var lightPos: Point /** * Randomly created polygons */ val polygons: List<Polygon> /** * All corners: view corners + polygons corners */ private val corners: List<Point> /** * All segments: view segments + polygons segments */ private val segments: List<Segment> private var xSpeed: Double = .0 private var ySpeed: Double = .0 private val viewAsPolygon: Polygon init { polygons = createPolygons(config.polygonNb, config.polygonSize, config.randomPointsNb) viewAsPolygon = Polygon( listOf( Point(.0, .0), Point(vizWidth, .0), Point( vizWidth, vizHeight ), Point(.0, vizHeight) ) ) corners = viewAsPolygon.points + polygons.flatMap { it.points } segments = viewAsPolygon.segments() + polygons.flatMap { it.segments() } lightPos = findInitialRandomPointOutsideOf(polygons) newSpeed(Random.nextDouble() * PI * 2) } private fun createPolygons(polygonNb: Int, polygonSize: Double, randomPointsNb: Int): List<Polygon> { // build random polygons val polygons = (1..polygonNb).map { val center = Point( Random.nextDouble() * vizWidth * (1.0 - polygonSize), Random.nextDouble() * vizHeight * (1.0 - polygonSize) ) val points = (1..randomPointsNb).map { _ -> Point( center.x + (Random.nextDouble() * (vizWidth * polygonSize)).coerceIn(.0, vizWidth), center.y + (Random.nextDouble() * (vizHeight * polygonSize)).coerceIn(.0, vizHeight) ) } polygonHull(points) }.toMutableList() // if a polygon touch another one, fuse the two polygons mergeAdjacentPolygons(polygons) return polygons } private fun mergeAdjacentPolygons(polygons: MutableList<Polygon>) { polygons.forEachIndexed { index, polygon -> polygons.forEachIndexed { otherIndex, otherPolygon -> if (index != otherIndex) { polygon.points.forEach { point -> if (otherPolygon.contains(point)) { polygons[index] = polygonHull(listOf(polygon.points, otherPolygon.points).flatMap { it }) polygons.removeAt(otherIndex) mergeAdjacentPolygons(polygons) return } } } } } } fun getSightPolygon(): Polygon { val allAngles = corners.flatMap { val rad = atan2(it.y - lightPos.y, it.x - lightPos.x) listOf( Angle(rad), Angle(rad + .00001), Angle(rad - .00001) ) } val intersections = mutableListOf<Intersection>() allAngles.forEach { angle -> val dx = angle.cos val dy = angle.sin val ray = Segment(lightPos, Point(lightPos.x + dx, lightPos.y + dy)) // Find CLOSEST intersection var closestIntersection: Intersection? = null segments .mapNotNull { segment -> ray.intersect(segment) } .forEach { intersection -> if (closestIntersection == null || (intersection.param < closestIntersection!!.param)) { closestIntersection = intersection } } // Intersect angle closestIntersection?.let { it.angle = angle // Add to list of intersections intersections.add(it) } } intersections.sortBy { it.angle.rad } // Polygon is intersects, in order of angle return Polygon(intersections.map { it.point }) } private tailrec fun findInitialRandomPointOutsideOf(polygons: List<Polygon>): Point { val pos = Point( Random.nextDouble() * vizWidth, Random.nextDouble() * vizHeight ) val insidePolygon = polygons.any { it.contains(pos) } return if (insidePolygon) findInitialRandomPointOutsideOf(polygons) else pos } internal fun moveLight() { var newPos = Point(lightPos.x + xSpeed, lightPos.y + ySpeed) // check for polygon collision for next position (on the extent or one of the polygons on screen) val collidedPolygon = if (viewAsPolygon.contains(newPos)) polygons.find { it.contains(newPos) } else viewAsPolygon // if collision is detected, compute rebound and recompute next position if (collidedPolygon != null) { // compute movement vector val movement = Segment(lightPos, newPos) val collidedSegment = collidedPolygon.segments().find { movement.isIntersection(it) } if (collidedSegment != null) { // find intersection and compute normal vector of collided segment val dx = collidedSegment.to.x - collidedSegment.from.x val dy = collidedSegment.to.y - collidedSegment.from.y val intersection = movement.intersect(collidedSegment)!!.point val normal = Segment(intersection, Point(intersection.x - dy, intersection.y + dx)) val dx1 = movement.from.x - movement.to.x val dx2 = normal.from.x - normal.to.x val dy1 = movement.from.y - movement.to.y val dy2 = normal.from.y - normal.to.y val movementAngle = atan2(dy1, dx1) val normalAngle = atan2(dy2, dx2) newSpeed(normalAngle + (normalAngle - movementAngle)) newPos = Point(lightPos.x + xSpeed, lightPos.y + ySpeed) } } lightPos = newPos } private fun newSpeed(currentDirection:Double) { xSpeed = cos(currentDirection) * 0.004 * vizWidth ySpeed = sin(currentDirection) * 0.004 * vizHeight } } private fun Polygon.segments(): List<Segment> = List(points.size) { i -> Segment( points[i], if (i == points.size - 1) points[0] else points[i + 1] ) } /** * Todo move to core? */ data class Segment(val from: Point, val to: Point) { /** * @return the point of intersection or null if rays are parallel. */ fun intersect(other: Segment): Intersection? { val px1 = from.x val py1 = from.y val dx1 = to.x - from.x val dy1 = to.y - from.y val px2 = other.from.x val py2 = other.from.y val dx2 = other.to.x - other.from.x val dy2 = other.to.y - other.from.y // Are they parallel? If so, no intersect val l1 = sqrt(dx1 * dx1 + dy1 * dy1) val l2 = sqrt(dx2 * dx2 + dy2 * dy2) if (((dx1 / l1) == (dx2 / l2)) && ((dy1 / l1) == (dy2 / l2))) return null // SOLVE FOR T1 & T2 val t2 = (dx1 * (py2 - py1) + dy1 * (px1 - px2)) / (dx2 * dy1 - dy2 * dx1) val t1 = (px2 + dx2 * t2 - px1) / dx1 //todo dx1 can be 0 => division by 0 !! // Must be within parametic whatevers for RAY/SEGMENT if (t1 < 0) return null if (t2 < 0 || t2 > 1) return null return Intersection(Point(px1 + dx1 * t1, py1 + dy1 * t1), t1) } fun isIntersection(other: Segment): Boolean { val dx1 = to.x - from.x val dy1 = to.y - from.y val dx2 = other.to.x - other.from.x val dy2 = other.to.y - other.from.y val denom = (dx1 * dy2) - (dx2 * dy1) if (denom == .0) return false // colinear val denomPositive = denom > 0 val s02x = from.x - other.from.x val s02y = from.y - other.from.y val sNumer = dx1 * s02y - dy1 * s02x if ((sNumer < 0) == denomPositive) return false // No collision val tNumer = dx2 * s02y - dy2 * s02x if ((tNumer < 0) == denomPositive) return false // No collision if (((sNumer > denom) == denomPositive) || ((tNumer > denom) == denomPositive)) return false // No collision // Collision detected return true } } data class Intersection(val point: Point, val param: Double) { var angle: Angle = 0.deg }
pierre avatar

Sketch created by

pierre

A 2D "line of sight" of "field of view" algorithm: a white ball emits light that is propagated in straight lines in all directions and stops when touching an object. The "light" is a simple yellow gradient, to draw its path, we compute every segments between the center of emission and every corner of every object in the scene. These objects are polygons, generated randomly at the beginning, if 2 polygons are touching they are merged into a bigger "contour" polygon. Then the ball is randmoly placed on screen (anywhere that is not inside a polygon) and starts moving, it rebounds on every segment it encounters. For more info on this algorithm check: https://legends2k.github.io/2d-fov/design.html

comments