Wardhana, Nicholas MarioJohan, HenrySeah, Hock-SoonStam, Jos and Mitra, Niloy J. and Xu, Kun2015-10-072015-10-072015978-3-905674-96-5https://doi.org/10.2312/pg.20151282Modern 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%.I.3.5 [Computer Graphics]Computational Geometry and Object ModelingGeometric algorithmslanguagesand systemsI.3.7 [Computer Graphics]ThreeDimensional Graphics and RealismAnimation10.2312/pg.2015128259-63