Accelerating Graph-based Path Planning Through Waypoint Clustering

Simple item page
dc.contributor.authorWardhana, Nicholas Marioen_US
dc.contributor.authorJohan, Henryen_US
dc.contributor.authorSeah, Hock-Soonen_US
dc.contributor.editorStam, Jos and Mitra, Niloy J. and Xu, Kunen_US
dc.date.accessioned2015-10-07T05:13:13Z
dc.date.available2015-10-07T05:13:13Z
dc.date.issued2015en_US
dc.description.abstractModern 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%.en_US
dc.description.sectionheadersShort Papersen_US
dc.description.seriesinformationPacific Graphics Short Papersen_US
dc.identifier.doi10.2312/pg.20151282en_US
dc.identifier.isbn978-3-905674-96-5en_US
dc.identifier.pages59-63en_US
dc.identifier.urihttps://doi.org/10.2312/pg.20151282en_US
dc.publisherThe Eurographics Associationen_US
dc.subjectI.3.5 [Computer Graphics]en_US
dc.subjectComputational Geometry and Object Modelingen_US
dc.subjectGeometric algorithmsen_US
dc.subjectlanguagesen_US
dc.subjectand systemsen_US
dc.subjectI.3.7 [Computer Graphics]en_US
dc.subjectThreeen_US
dc.subjectDimensional Graphics and Realismen_US
dc.subjectAnimationen_US
dc.titleAccelerating Graph-based Path Planning Through Waypoint Clusteringen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
059-063.pdf
Size:
947.32 KB
Format:
Adobe Portable Document Format
Download
Collections
PG2015short