• Login
    View Item 
    •   Eurographics DL Home
    • Eurographics Partner Events
    • PG: Pacific Graphics Short Papers
    • PG2015short
    • View Item
    •   Eurographics DL Home
    • Eurographics Partner Events
    • PG: Pacific Graphics Short Papers
    • PG2015short
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Accelerating Graph-based Path Planning Through Waypoint Clustering

    Thumbnail
    View/Open
    059-063.pdf (947.3Kb)
    Date
    2015
    Author
    Wardhana, Nicholas Mario
    Johan, Henry
    Seah, Hock-Soon
    Pay-Per-View via TIB Hannover:

    Try if this item/paper is available.

    Metadata
    Show full item record
    Abstract
    Modern Computer Graphics applications commonly feature very large virtual environments and diverse characters which perform different kinds of motions. To accelerate path planning in such scenario, we propose subregion graph data structure. It consists of subregions, which are clusters of locally connected waypoints inside a region, as well as their connectivities. We also present a fast algorithm to automatically generate subregion graph from enhanced waypoint graph map representation, which also supports various motion types and can be created from large virtual environments. Nevertheless, subregion graph can also be generated from any graph-based map representation. Our experiments showed that subregion graph is very compact relative to the input waypoint graph. By firstly planning subregion path, and then limiting waypoint-level planning to the subregion path, up to 8 times average speedup can be achieved, while average length ratios are maintained at as low as 102.5%.
    BibTeX
    @inproceedings {pg.20151282,
    booktitle = {Pacific Graphics Short Papers},
    editor = {Stam, Jos and Mitra, Niloy J. and Xu, Kun},
    title = {{Accelerating Graph-based Path Planning Through Waypoint Clustering}},
    author = {Wardhana, Nicholas Mario and Johan, Henry and Seah, Hock-Soon},
    year = {2015},
    publisher = {The Eurographics Association},
    ISBN = {978-3-905674-96-5},
    DOI = {10.2312/pg.20151282}
    }
    URI
    http://dx.doi.org/10.2312/pg.20151282
    Collections
    • PG2015short

    Eurographics Association copyright © 2013 - 2020 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA
     

     

    Browse

    All of Eurographics DLCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    BibTeX | TOC

    Create BibTeX Create Table of Contents

    Eurographics Association copyright © 2013 - 2020 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA