Pathfinding is critical to virtual simulation applications. One of the most prominent pathfinding challenges is the fast computation of path plans in large and realistic virtual terrain environments. To tackle this problem, this work proposes the exploration of a quadtree structure in the navigation map representation of large real-world virtual terrains. Exploring a hierarchical approach for virtual terrain representation, we detail how a global hierarchical pathfinding algorithm searches for a path in a coarse initial navigation map representation. Then, during execution time, the pathfinding algorithm refines regions of interest in this terrain representation in order to compute paths with a higher quality in areas where a large amount of navigation obstacles is found. The computational time of such hierarchical pathfinding algorithm is systematically measured in different hierarchical and non-hierarchical terrain representation structures that are instantiated in the modeling of a small real-world terrain scenario. Then, similar experiments are developed in a large real-world virtual terrain that is inserted in a real-life simulation system for the development of military tactical training exercises. The results show that the computational time required to generate pathfinding answers can be optimized when the proposed hierarchical pathfinding algorithm along with the easy and reliable implementation of the quadtree-based navigation map representation of the large virtual terrain are explored in the development of simulation systems.

Level of detail (LOD) systems has long been a central concept within the field of computer graphics. By selectively allocating detail only to where it is necessary, the cost of rendering virtual objects can be greatly decreased. The usefulness of an LOD system is closely tied to the metrics used to evaluate how to distribute detail, as getting these wrong can lead to visual artifacts or rendering detail which is not visible to an observer. To offset this, researchers have investigated how we can optimize these systems by leveraging human perception to allocate detail based on if the detail is perceivable. This paper explores the use of LOD systems in the context of virtual terrains, a common use case were LOD systems have seen much prior use, and delves into how such systems can be optimized further by leveraging human perception. The paper presents a method centered around the use of octrees, a data structure used to partition and compress volumetric data, alongside spatial frequency, a concept related to human perception which provides insight into where visual stimulus borders on being percievable, to dynamically generate transition distances for an LOD system. The presented method is evaluated using a terrain generator created in the Unity engine alongside Nvidia ꟻLIP, a tool for evaluating differences in images based on human perception metrics. Results indicate that the presented method did lead to a decrease in resource cost when generating terrain when compared to some other methods while the ability to optimize LOD transition distances based on silhouette-background contrast remains uncertain. / Nivå av detalj (LOD) system har länge varit ett centralt begrepp inom forskningsområdet för dator-grafik. Genom att selektivt allokera detalj så kan kostnaden för att rendera virituella föremål minskas drastiskt. Användbarheten av ett LOD-system är nära kopplat till de specifika värden som används för att utvärdera hur man fördelar detalj efterssom man annars riskerar att få virtuella artefakter eller renderar detaljer som inte är synliga för en observatör. För att motverka detta har forskare undersökt hur vi kan optimisera dessa system genom att utnyttja visuell uppfattning hos människor för att allokera detalj baserat på var den är synlig för användaren. Denna text utforskar användningen av LOD-system i samband med virtuella terränger, ett användningsområde där LOD-system har använts tidigare och går in på hur denna typ av system kan optimiseras bättre genom att utnyttja mänsklig perception. Texten presenterar en metod centrerad runt användandet av octrees, en datastruktur som används för att partitionera och komprimera volumetrisk data, tillsamans med spatiell frekvens, ett koncept relaterat till mänsklig synförmåga som ger inblick i var visuell stimulans gränsar till att vara synlig, för att dynamiskt generera övergångsavstånd för ett LOD-system. Den presenterade metoden utvärderas med en terränggenerator skapad i Unity spel-motorn tilsamans med Nvidia ꟻLIP, ett verktyg för att utvärdera skillnader i bilder baserat på mänskliga perceptionsmått. Resultaten indikerar att den presenterade metoden ledde till en minskning av resurskostnaden vid generation av terräng jämfört med vissa andra metoder medan möjligheten att optimera övergångsavstånd för LOD-systemet baserat på kontrast mellan bakgrunden och silouetten för terrängen kvarstår som osäker.