A Navigation mesh for dynamic Environmnts一種動(dòng)態(tài)的環(huán)境下的導(dǎo)航網(wǎng)格

1、a navigation mesh for dynamic environmentswouter g. van toll, atlas f. cook iv, roland geraertscasa 2012problem solved?2 / 163 / 16 path planning in games and simulations send virtual characters from start to goal increasing desire for efficiency and realism characters: smooth movement, collision av

2、oidance, environments: complex (2.5d), dynamic, foundation: a navigation mesh subdivision of the walkable space into 2d polygons allows smooth, flexible movement our framework: corridors based on the 2d medial axis contribution: dynamic updatesmotivation4 / 16preliminaries: 2d medial axis medial axi

3、s: pruned version ofthe voronoi diagram subdivision into cellswith 1 closest obstacle a useful roadmap maximum clearance to obstacles preserves connectivity the set of all points with at least two closest obstacle points5 / 16preliminaries: explicit corridor map ecm: annotated medial axis (geraerts,

4、 2010) bisector vertices storea closest obstacle pointon both sides exact subdivision of the walkable spacean efficient nav. mesh o(n) storage o(n log n) build time6 / 16preliminaries: explicit corridor map some features of the ecm clearance information supports all character sizes global planning o

5、n the ma result: path + corridor following indicative routes short paths with clearance local forces can be added collision avoidance group coherence multi-layered environments dynamic updates7 / 16contribution: local updates dynamic environments can change locally e.g. collapsing bridges, newly bui

6、lt roads, complete navmesh reconstruction is expensive! local operations: adding/removing obstacles update the mesh only where it is necessary recall: the ecm is an annotated medial axis we use voronoi algorithms; skip the annotations today1. inserting a point among points2. inserting a point among

7、polygons3. inserting a polygon among polygons4. deleting an obstacle8 / 161. inserting a point among points insertion = 1 step of incremental construction let cj be the voronoi cell of point pj let p be the point to add algorithm (green and sibson, 1978) find the cell ci in which p lies compute the

8、bisector of p and pi find the intersections of bisector and ci compute new neighbor + bisector iterate until the new cell is finished remove the old edges complexity: o(log n + k) n = number of points k = complexity of the new cell9 / 162. inserting a point among polygons what if the other obstacles

9、 are polygons? bisector edges are chains of line/parabola segments a bisector vertex (bv) marks a switch bv occurs when the edge intersects a surface normal adapted insertion algorithm in each iteration, choose the 1st of 2 intersections10 / 163. inserting polygon among polygons what if the inserted

10、 obstacle p is a line or polygon? p can also induce bisector vertices adapted insertion algorithm in each iteration, choose the 1st of 3 intersections with the voronoi cell with the neighbours normal vector with ps normal vector11 / 164. deleting an obstacle deleting p: the cell cp needs to be remov

11、ed its interior must be filled in with new edges these can only come from ps neighbors! deletion algorithm compute np, set of ps neighbors build the medial axis for np connect the old/new medial axes delete the boundary of cp complexity: o(m log m) m = number of neighbors for p12 / 16experimental re

12、sults 1. inserting random points into an empty scene incremental insertion local updates vs. global reconstruction local: always fast ( 1 ms) global: slower, depends on #points so far13 / 16experimental results (2) 2. inserting polygons into various scenes running times: 1.3ms to 2.5ms efficiency de

13、pends on the new cells complexity in practice, most updates will be very local fast enough for real-time updates!14 / 16experimental results (3) 3. deleting polygons from various scenes same polygons/scenes as before running times: 1.2ms to 5.4ms efficiency depends on the old cells complexity 4. mov

14、ing a polygon through various scenes re-insert the polygon into a static version running times below 1.5ms we can handle multiple moving obstacles in real-time15 / 16conclusions algorithms for updating a navigation mesh based on voronoi diagram techniques insertions of points and polygons deletions based on insertions implementation and experiments insertions: real-time performance deletions: slower, but still applicable movement: real-time insertions into a stat