Horizon computation on a hierarchical triangulated terrain model

Hierarchical terrain models describe a topographic surface at different levels of detail, thus providing a multiresolution surface representation as well as a data compression mechanism. We consider the horizon computation problem on a hierarchical polyhedral terrain (in particular, on a hierarchical triangulated irregular network), which involves extracting the horizon of a viewpoint at a given resolution and updating it as the resolution increases. We present an overview of horizon computation algorithms on a nonhierarchical polyhedral terrain. We extend such algorithms to the hierarchical case by describing a method which extracts the terrain edges at a given resolution, and proposing a randomized algorithm for dynamically updating a horizon under insertions and deletions of terain edges     

Extracting contour lines from a hierarchical surface model

The Hierarchical Triangulated Irregular Network (HTIN) is a structure for representing 2½-dimensional surfaces at different levels of detail through piecewise-linear approximations based on triangulations of the surface domain. In this paper, we present two algorithms that allow extracting a representation of the surface and contour lines at a given level of detail, directly from the HTIN.     

Visibility analysis on a massively data-parallel computer

Visibility analysis algorithms use digital elevation models (DEMs), which represent terrain topography, to determine visibility at each point on the terrain from a given location in space. This analysis can be computationally very demanding, particularly when manipulating high resolution DEMs accurately at interactive response rates. Massively data-parallel computers offer high computing capabilities and are very well-suited to handling and processing large regular spatial data structures. In the paper, the authors present a new scanline-based data-parallel algorithm for visibility analysis. Results from an implementation onto a MasPar massively data-parallel SIMD computer are also presented.     

层次可见性与层次细节地表模型相结合的快速绘制

大规模地表模型的实时绘制是虚拟现实技术中重要的研究课题之一。为了加速地表模型的绘制，人们采用视点相关的动态多分辨率层次细节模型方法，但是算法效率依然有待提高。该文提出一种层次可见性与层次细节地表模型相结合的快速地形绘制方法。算法旨在利用地表模型所具有的horizon特性在预处理中为地表多分辨率块模型建立相应的层次“块”可见性结构，快速判定地形块相对于当前视点的可见性，以减少多分辨率模型中模型细节的处理和绘制三角形的数目。同时为消除地表模型层次变化所带来的可见性错误，算法提出一种层次结构可见性计算方法，以修正多分辨率模型所带来的可见性动态变化。实验结果表明算法有效地提高了绘制效率，是可行的。     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

Instant Visibility

We present an online occlusion culling system which computes visibility in parallel to the rendering pipeline. We show how to use point visibility algorithms to quickly calculate a tight potentially visible set (PVS) which is valid for several frames, by shrinking the occluders used in visibility calculations by an adequate amount. These visibility calculations can be performed on a visibility server, possibly a distinct computer communicating with the display host over a local network. The resulting system essentially combines the advantages of online visibility processing and region-based visibility calculations, allowing asynchronous processing of visibility and display operations. We analyze two different types of hardware-based point visibility algorithms and address the problem of bounded calculation time which is the basis for true real-time behavior. Our results show reliable, sustained 60 Hz performance in a walkthrough with an urban environment of nearly 2 million polygons, and a terrain flyover.     

Unified Hybrid Terrain Representation Based on Local Convexifications

Hybrid digital terrain models represent an effective framework to combine and integrate terrain data with different topology and resolution. Cartographic digital terrain models typically are constituted by regular grid data and can be refined by adding locally TINs that represent morphologically complex terrain parts. Direct rendering of both data sets to visualize the digital terrain model would generate geometric discontinuities as the meshes are disconnected. In this paper we present a new meshing scheme for hybrid terrain representations. High quality models without discontinuities are generated as the different representations are softly joined through an adaptive tessellation procedure. Due to the complexity of the algorithms involved in the tessellation procedure, we propose a mixed strategy where part of the information is pre-computed and efficiently encoded. This way, for rendering the model, the tessellation information has to be decoded and only additional simple operations have to be performed.     

HMPMR strategy for real-time tracking in aerial images,using direct methods

The vast majority of approaches make use of features to track objects. In this paper, we address the tracking problem with a tracking-by-registration strategy based on direct methods. We propose a hierarchical strategy in terms of image resolution and number of parameters estimated in each resolution, that allows direct methods to be applied in demanding real-time visual-tracking applications. We have called this strategy the Hierarchical Multi-Parametric and Multi-Resolution strategy (HMPMR). The Inverse Composition Image Alignment Algorithm (ICIA) is used as an image registration technique and is extended to an HMPMR-ICIA. The proposed strategy is tested with different datasets and also with image data from real flight tests using an Unmanned Aerial Vehicle, where the requirements of direct methods are easily unsatisfied (e.g. vehicle vibrations). Results show that using an HMPMR approach, it is possible to cope with the efficiency problem and with the small motion constraint of direct methods, conducting the tracking task at real-time frame rates and obtaining a performance that is comparable to, or even better than, the one obtained with the other algorithms that were analyzed.     

Visibility Equalizer Cutaway Visualization of Mesoscopic Biological Models

In scientific illustrations and visualization, cutaway views are often employed as an effective technique for occlusion management in densely packed scenes. We propose a novel method for authoring cutaway illustrations of mesoscopic biological models. In contrast to the existing cutaway algorithms, we take advantage of the specific nature of the biological models. These models consist of thousands of instances with a comparably smaller number of different types. Our method constitutes a two stage process. In the first step, clipping objects are placed in the scene, creating a cutaway visualization of the model. During this process, a hierarchical list of stacked bars inform the user about the instance visibility distribution of each individual molecular type in the scene. In the second step, the visibility of each molecular type is fine‐tuned through these bars, which at this point act as interactive visibility equalizers. An evaluation of our technique with domain experts confirmed that our equalizer‐based approach for visibility specification is valuable and effective for both, scientific and educational purposes.     

Managing contextual preferences

To handle the overwhelming amount of information currently available, personalization systems allow users to specify through preferences which pieces of data interest them. Most often, users have different preferences depending on context. In this paper, we introduce a model for expressing such contextual preferences. Context is modeled using a set of hierarchical attributes, thus allowing context specification at various levels of detail. We formulate the context resolution problem as the problem of selecting appropriate preferences based on context for personalizing a query. We also propose algorithms for context resolution based on data structures that index preferences by exploiting the hierarchical nature of the context attributes. Finally, we evaluate our approach from two perspectives: usability and performance. Usability evaluates the overheads imposed on users for specifying context-dependent preferences, as well as their satisfaction from the quality of the results. Our performance results focus on the context resolution using the proposed indexes.     

Fast horizon computation at all points of a terrain with visibilityand shading applications

A terrain is most often represented with a digital elevation map consisting of a set of sample points from the terrain surface. This paper presents a fast and practical algorithm to compute the horizon, or skyline, at all sample points of a terrain. The horizons are useful in a number of applications, including the rendering of self-shadowing displacement maps, visibility culling for faster flight simulation, and rendering of cartographic data. Experimental and theoretical results are presented which show that the algorithm is more accurate that previous algorithms and is faster than previous algorithms in terrains of more than 100,000 sample points     

基于视线的地形可视性分析研究

地形可视性分析在军事、电信、旅游等领域有着广泛的应用。各种复杂的、和应用有关的可视性分析大多数采用的是基于视线(LineofSight,LOS)的方法。文章在阐述视线方法的基础上,根据分析对象的不同对地形可视性分析问题进行了分类,并且从数学模型和实验仿真两方面对各种类型的可视性分析的联系和区别进行了研究,在此基础上提出了关于地形可视性分析的统一模型以及对可视性问题解决方法的一些展望。     

Hierarchical clustering based on ordinal consistency

Hierarchical clustering is the grouping of objects of interest according to their similarity into a hierarchy, with different levels reflecting the degree of inter-object resemblance. It is an important area in data analysis and pattern recognition. In this paper, we propose a new approach for robust hierarchical clustering based on possibly incomplete and noisy similarity data. Our approach uses a novel perspective in finding the object hierarchy by trying to optimize ordinal consistency between the available similarity data and the hierarchical structure. Using experiments we show that our approach is able to perform more effectively than similar algorithms when there are substantial noises in the data. Furthermore, when similarity-ordering information is only available in the form of incomplete pairwise similarity comparisons, our approach can still be applied directly. We illustrate this by applying our approach to randomly generated hierarchies and phylogenetic tree construction from quartets, an important area in computational biology.     

Region-to-region visibility analysis using data parallel machines

We propose an algorithm for solving region-to-region visibility problems on digital terrain models using data parallel machines. Since global communication is the bottleneck in this kind of algorithm, the algorithm we propose focuses on the reduction of global communication. The algorithm analyses a strip of the source region at a time and sweeps through the source strip by strip. At most four sweeps are needed for the analysis. By exploring the coherence properties in the processor structure, global communication is minimized and complexity is substantially improved. Furthermore, all global write operations are exclusive and concurrency in global read operations is minimized. Since the problem size is usually large, we also designed rules of decomposition to efficiently handle the cases where the required number of processors is greater than available. The algorithm has been implemented on a Connection Machine CM-2, and results of computational experiments are presented.     

Dense terrain stereoreconstruction using modified SGM

A technique for creating 3D terrain models based on digital aerial images, using an algorithm of semi-global matching, is presented. A method of hierarchical application of the algorithm is demonstrated. A number of modifications and improvements at all stages of algorithm operation are proposed. Among them the following ones are distinguished: due account of the gradient and color information of images, the interpolation of the pixel matching metric for increasing the algorithm resolution and improving the stability to small distortions of the input data, filtering the matching cost and post-processing of disparity map by a bilateral filter. Results of algorithm application and the advantages of the modification are demonstrated by an example of processing of pairs of high-resolution aerial images.     

A hierarchical cellular logic for pyramid computers

Hierarchical structure occurs in biological vision systems and there is good reason to incorporate it into a model of computation for processing binary images. A mathematical formalism is presented which can describe a wide variety of operations useful in image processing and graphics. The formalism allows for two kinds of simple transformations on the values (called pyramids) of a set of cells called a hierarchical domain: the first are binary operations on boolean values, and the second are neighborhood-matching operations. The implied model of computation is more structured than previously discussed pyramidal models, and is more readily realized in parallel hardware, while it remains sufficiently rich to provide efficient solutions to a wide variety of problems. The model has a simplicity which is due to the restricted nature of the operations and the implied synchronization across the hierarchical domain. A corresponding algebraic simplicity in the logic makes possible the concise representation of many cellular-data operations.