CS Paper Radar

Visibility on Terrains

Laura Toma

cs.CY ·submitted 2026-09-30 22:39 UTC · v1

Abstract

This chapter surveys terrain visibility models, algorithms, and applications. It introduces basic definitions, from line-of-sight, single-viewpoint viewsheds to cumulative and total viewsheds, on both Triangulated Irregular Network (TIN) and regular grid terrains. Reviews exact and approximate algorithms and highlights key application domains including archaeology, visual exposure to greenery, scenic route management, and land conservation.

Comment
10 pages, 2 figures, chapter invited to the Encyclopedia of GIS

Closest papers

Nearest neighbours by meaning across the whole index.

Best of Two Worlds: Combining High and Low Resolution to Compute Viewsheds on terrains

cs.DS ·2026-10-01 ·Laura Toma
published similarity 0.64
Abstract · 27 pages, 19 figures, short version appeared in Proc. ACM SIGSPATIAL GIS 2018

The viewshed of a point $v$ on a grid terrain $T$, viewshed$_T(v)$, is defined as the set of grid points in $T$ that are visible from $v$. We describe a novel algorithm for computing viewshed$_T(v)$ using a multi-resolution approach: Given a parameter $k >1$ that represents the block size, we create a grid $T'$ which is a lower-resolution version of $T$, such that each point in $T'$ corresponds to a block of $\lceil \sqrt k \rceil $-by-$\lceil \sqrt k \rceil$ points in $T$. The key of our approach is using $T'$ to speed up the computation of viewshed$_T(v)$ while not introducing approximation. We compute viewshed$_T(v)$ in two steps: First we compute the viewshed of $v$ on $T'$, while maintaining the invariant that any block in $T'$ that is labeled as invisible may not contain any visible points. Thus, the first step's role is to use $T'$ to filter out blocks in $T$ that are guaranteed to be invisible. The second step considers the blocks that were labeled as visible in $T'$ and computes the visibility of their points with full accuracy using the data in $T$. Overall the algorithm runs in $O(n + \frac nk \lg \frac nk + k \lg k + l \cdot \lg n)$, where $l$ is the total size of visible blocks in $T'$. When $k = Ω(1)$ and $l = o(n) $, the running time of our algorithm improves on the previous best bound of $O(n \lg n)$. Our experimental results show the performance of the new algorithm in practice and a speedup of more than an order of magnitude compared to previous algorithms.

0.46

Six Ways to Draw Vangers with WebGPU: Real-Time Rendering of Editable Multi-Layer Height Fields

cs.GR ·2026-08-18 ·Dzmitry Malyshau
unusual similarity 0.61
Abstract · 29 pages. Submitted to the Journal of Computer Graphics Techniques. Supplemental video as ancillary

Terrain level-of-detail is measured almost exclusively on digital elevation models: single-valued, smooth at the sampling scale, sampled from real topography. Game terrain is often none of these. We compare six rendering methods - height-field ray marching, voxel-accelerated ray marching, sliced proxy geometry, per-sample bar rasterization, compute scattering, and a fitted triangle mesh - implemented in a single engine over a single data path, on the hand-authored multi-layer terrain of Vangers (1998), scored against a CPU ray cast of the same source data. Every method must preserve the two solid intervals available at a ground sample, render at interactive rates, and reflect local terrain destruction without reloading the level. These constraints rule out treating caves as decoration or amortizing a static preprocessing step over an immutable map. From the original game's top-down camera the six methods look interchangeable. At eye-level horizons they do not: point scattering loses coverage, slicing bands, and an over-simplified mesh can miss a wall. At the selected quality settings a greedy triangulated irregular network (TIN) has the lowest mean frame time on every device we measured, but the fit cost is set by the second layer rather than by floor relief, and making that mesh editable retains 319 MiB of GPU geometry and 535 MiB of CPU triangulation. All six implementations use the same native wgpu / WebGPU API and canonical WGSL. We release the engine, the harness, and a one-command measurement protocol.

0.39

Visibility graphs of irregularly sampled two-dimensional fields via Voronoi tessellations

cs.CG math.DScond-mat.stat-mechphysics.data-an ·2026-11-12 ·Francisco J. Muñoz, Juan Carlos Nuño
similarity 0.60
Abstract · 10 pages, 5 figures

Visibility graphs map a time series into a network by linking two data whenever the straight line between them is not obstructed by intermediate data. Their extension to two-dimensional fields has so far been restricted to regular lattices, where visibility is checked along a finite number of lattice directions. We propose a definition for scalar data sampled at arbitrary, irregularly scattered points of the plane. Each point is assigned its Voronoi cell, so that the data become a landscape of prisms, and two points are linked when the line of sight between them clears the cells crossed by the connecting segment. This yields horizontal ($\HVGV$) and natural ($\NVGV$) Voronoi visibility graphs that reduce exactly to the classical horizontal and natural visibility graphs when the points are collinear, contain the Gabriel graph of the point set, and can be built by an exact walk through the Delaunay triangulation. For uncorrelated heights, the horizontal graph depends only on the ranks of the data, so its statistics are independent of the marginal distribution. The probability that two points see each other is $2/[(M+1)(M+2)]$, where $M$ is the number of Voronoi cells crossed, which reduces the problem to the geometry of the tessellation. For Poisson points this gives a degree distribution with a scale-free tail $P(k)\simeq(π^3/4)\,k^{-2}$ and a mean degree that grows as $(π^3/8)\ln N$, in contrast with the finite value $\langle k\rangle=4$ of one-dimensional series. Two dimensions are therefore the marginal case in which isotropic horizontal visibility ceases to be local. Numerical simulations with up to $N=1.28\times10^5$ points support these predictions.

0.28

Dungeon and Visibility World Generator

cs.RO ·2026-10-14 ·Edwin Mériaux, Antonio Loría, Gregory Dudek
code/data similarity 0.57
Abstract · This points to our git repo used in our many projects for standardization and reproduction of scientific work

Robotic exploration, coverage, and multi-agent deployment algorithms require reproducible environments with controllable geometry and visibility. This paper presents the Dungeon and Visibility World Generator, an open-source framework for constructing two- and three-dimensional environments and evaluating geometric line-of-sight. The framework supports orthogonal, polygonal or polyhedral, and curvilinear geometries, with six construction families covering scattered rooms, clusters, winding passages, caverns, branches, and loops. Room dimensions, passage structures, obstacles, and spatial placement can be controlled through configurable parameters and probability distributions. Each generated environment provides continuous free-space geometry and a corresponding discrete occupancy representation. A Rust-based visibility engine supports line-of-sight queries in both representations, enabling the evaluation of observable regions from arbitrary agent positions. The framework records configurations, generated geometries, occupancy grids, and visibility results to support reproducible experiments. We demonstrate the generator across all six geometry classes, examine how geometry and spatial resolution affect visibility, and evaluate generation time and reproducibility. The resulting framework provides a configurable foundation for evaluating robotic exploration, coverage, and multi-agent deployment algorithms in diverse environments.

0.49

Efficient K-Visibility Query in Polygons

cs.CG ·2026-09-01 ·Yeganeh Bahoo, Roni Sherman
publishedtheory similarity 0.56
Abstract · To appear in Proceedings of ALGOWIN 2026

This paper investigates $k$-visibility, where a line of sight can penetrate up to $k$ obstacles. While computing the $k$-visibility polygon from a single query point is well-studied, existing spatial preprocessing approaches rely on full $O(n^2)$ line arrangements through all vertex pairs without characterizing the minimal set of topological boundaries. We present a refined cell decomposition framework that isolates the exact geometric events governing $k$-visibility: primary vertex horizon lines and secondary mutually critical hinge lines. We prove that this minimal set of partition lines yields a spatial decomposition of $Θ(n^4)$ cells within which the combinatorial structure of the $k$-visibility polygon remains strictly invariant. By leveraging a combinatorial $δ$-compression scheme across cell boundaries, we achieve an overall storage complexity of $\mathcal{O}(n^4)$ while supporting optimal $\mathcal{O}(\log n + m)$ query time to reconstruct explicit $k$-visibility polygons of size $m$. Our framework naturally extends to polygons containing holes.

0.31

The hidden solar cost of urban unfamiliarity

cs.CY ·2026-11-11 ·Lijia Liu, Yimeng Song
similarity 0.50
Abstract · 75 pages, 5 main figures. Includes 63 pages of Supplementary Material

Unfamiliar walkers may follow the shortest route and miss nearby shade, indoor passages and multilevel connections. We define the resulting hidden solar cost as the direct-sun exposure avoidable through shade-informed routing without substantial detours. We developed a time-specific three-dimensional model of Hong Kong Island that combines indoor and outdoor walking networks with building geometry, vegetation mapped by light detection and ranging (LiDAR), and solar position. For 500 modelled journeys, we compared shortest and shade-informed routes at four daytime snapshots and five extra-distance limits. At noon, shade-informed routes reduced modelled direct-sun exposure by 13.5% relative to shortest routes under a 10% extra-distance limit. Route length increased by 2.85% on average. A 5% extra-distance limit delivered 77% of the reduction obtained at 10%. In a controlled comparison, outdoor shade information accounted for 86% of the reduction and indoor-protection information for 14%. Removing multilevel connections left only 191 of 500 journeys feasible within the original route-length limit. These route comparisons identify an avoidable solar cost when existing protection is missing from the information used to choose a route. Making protected routes visible and preserving their connections can reduce sun exposure without large detours.

0.41

Geometric Queries on Tessellation-Free Displaced Surfaces

cs.GR ·2026-10-15 ·Bing Xu, Yang Zhou, Brian Budge
similarity 0.48
Abstract

Displacement maps encode fine geometric detail in compact textures and simplify surface authoring, but using them typically requires pre-tessellating surfaces into dense triangle meshes, incurring a heavy memory cost. Recent tessellation-free methods enable direct ray tracing. However, broader geometric queries such as surface sampling, specular manifold search, and closest-point queries remain less explored. Supporting these operations requires surface enclosures, area estimates, and normal bounds, which scalar height intervals alone do not fully provide. We present a first-order texture-space hierarchy that unlocks these queries directly without pre-tessellation. Each node stores a local affine height plane and a conservative residual bound, retaining spatial height variation that scalar minimum--maximum bounds discard. The plane and residual provide surface enclosures for intersection and distance searches, while the plane's height and slopes supply area estimates for sampling. Additional slope bounds support specular light-path search. Building on this representation, we develop query-specific traversal, pruning, and sampling algorithms, and demonstrate them in caustics rendering, sampling displaced emitters, and surface partial differential equation (PDE) solvers. We demonstrate memory savings over pre-tessellation and performance improvements over query-specific baselines, while retaining efficient ray tracing.

0.17

ExcavaTwin: Training-Free Geometry-Guided Semantic Elevation Mapping for Autonomous Excavation

cs.RO ·2026-09-28 ·Yu Deng, Lingshan Zeng, Tong Hu, Rushi Dai
similarity 0.48
Abstract · 8 pages,5 figures

Autonomous excavation requires a spatial representation that jointly captures terrain geometry and task-relevant semantics. Existing excavation mapping is largely elevation-centric, while generic semantic models remain unstable in unstructured outdoor scenes. We present ExcavaTwin, a pure-vision geometry-guided semantic elevation mapping framework without excavation-specific training. Given multi-view RGB images, the framework: 1) reconstructs scene geometry and semantic observations using frozen vision models; 2) derives terrain and non-terrain geometric support; 3) performs geometry-constrained multi-view semantic fusion to suppress implausible predictions and recover incomplete observations; and 4) projects the fused state into a task-oriented semantic elevation map. Experiments on public datasets and real excavation scenes demonstrate reliable geometric and semantic perception. In real excavation, the system achieved an average update interval of approximately 1.4 s and a mean elevation error of 12.74cm in dynamically modified regions. Larger errors mainly occur during rapid terrain changes and transient visual disturbances caused by machine motion.

0.19