The continuous development of graphics hardware is contributing to the creation of 3D virtual worlds with high level of detail, from models of large urban areas, to complete infrastructures, such as residential buildings, stadiums, industrial settings or archaeological sites, to name just a few. Adding virtual humans or avatars adds an extra touch to the visualization providing an enhanced perception of the spaces, namely adding a sense of scale, and enabling simulations of crowds. Path planning for crowds in a meaningful way is still an open research field, particularly when it involves an unknown polygonal 3D world. Extracting the potential paths for navigation in a non automated fashion is no longer a feasible option due to the dimension and complexity of the virtual environments available nowadays. This implies that we must be able to automatically extract information from the geometry of the unknown virtual world to define potential paths, determine accessibilities, and prepare a navigation structure for real time path planning and path finding. A new image based method is proposed that deals with arbitrarily a priori unknown complex virtual worlds, namely those consisting of multilevel passages (e.g. over and below a bridge). The algorithm is capable of extracting all the information required for the actual navigation of avatars, creating a hierarchical data structure to help both high level path planning and low level path finding decisions. The algorithm is image based, hence it is tessellation independent, i.e. the algorithm does not use the underlying polygonal structure of the 3D world. Therefore, the number of polygons as well as the topology, do not affect the performance.


    Access

    Download


    Export, share and cite



    Title :

    Path planning for complex 3D multilevel environments



    Publication date :

    2008-01-01


    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629



    Path planning for complex 3D multilevel environments

    Deusdado, Leonel / Fernandes, António Ramires / Belo, Orlando | BASE | 2008

    Free access

    Path planning for complex 3D multilevel environments

    Deusdado, Leonel Domingues / Fernandes, António Ramires / Belo, Orlando | BASE | 2010

    Free access

    HRA*: Hybrid randomized path planning for complex 3D environments

    Teniente, Ernesto H. / Andrade-Cetto, Juan | BASE | 2013

    Free access

    Path Planning for Unmanned Aerial Vehicles in Complex Environments

    César Gómez Arnaldo / María Zamarreño Suárez / Francisco Pérez Moreno et al. | DOAJ | 2024

    Free access

    GNSS-aware Path Planning for UAV swarm in complex environments

    Causa, Flavia / Fasano, Giancarmine / Grassi, Michele | IEEE | 2019