Voronoi-Based Real-Time Crowd Path Planning

YIN Bao-cai; XU Zhen-hua; KONG De-hui; XIAO Xiao-fang

Journal of Beijing University of Technology > 2009 > 35(8): 1115-1121.

YIN Bao-cai, XU Zhen-hua, KONG De-hui, XIAO Xiao-fang. Voronoi-Based Real-Time Crowd Path Planning[J]. Journal of Beijing University of Technology, 2009, 35(8): 1115-1121.

Citation:

YIN Bao-cai, XU Zhen-hua, KONG De-hui, XIAO Xiao-fang. Voronoi-Based Real-Time Crowd Path Planning[J]. Journal of Beijing University of Technology, 2009, 35(8): 1115-1121.

Citation:

YIN Bao-cai, XU Zhen-hua, KONG De-hui, XIAO Xiao-fang. Voronoi-Based Real-Time Crowd Path Planning[J]. Journal of Beijing University of Technology, 2009, 35(8): 1115-1121.

PDF (472 KB)

Voronoi-Based Real-Time Crowd Path Planning

Beijing Municipal Key Laboratory of Multimedia and Intelligent Software Technology, College of Computer Science, Beijing University of Technology, Beijing 100124, China

More Information

Received Date: February 25, 2008
Available Online: December 09, 2022

Graphical Abstract

Abstract

Abstract

In order to perform the collision avoidance, a new algorithm is introduced to make use of the high effectiveness of GPU to compute the discrete Voronoi diagram in real-time.And a solution for crowd path navigation based Voronoi diagram is presented.By making use of the ability that the Voronoi diagram partitions the space according to the Euclidean metric, the path planning with collision avoidance is achieved by forbidding agents to move outside their Voronoi regions.
- GPU,
- voronoi diagram,
- virtual agent,
- crowd path planning

FullText(HTML)

References (12)

References

[1]	REYNOLDS C.Flocks,herds,and schools:a distributed behavioral model[C]∥Computer Graphics(SIGGRAPH’87Proceedings).New York:ACM,1987,21:25-34.
[2]	TU X Y,TERZOPOULOS D.Artificial fishes:physics,locomotion,perception,behavior[C]∥Proc SIGGRAPH 94,Annual Conference Series.Orlando:ACM,1994:43-50.
[3]	BOUVIER E,COHEN E,NAJMAN L.From crowd simulation to airbag deployment:particle systems,a new paradigm ofsimulation[J].Journal of Electronic Imaging,1997,6(1):94-107.
[4]	HELBING D,FARKAS I,VICSEK T.Simulating dynamical features of escape panic[J].Letters to Nature,2000,407(6803):487-490.
[5]	MUSSE S,THALMANN D.A behavioral model for real time simulation of virtual human crowds[J].IEEE Transactions onVisualization and Computer Graphics,2001,7(2):152-164.
[6]	LOSCOS C,MARCHAL D,MEYER A.Intuitive crowd behaviour in dense urban environments using local laws[C]∥Theory and Practice of Computer Graphics(TPCG’03).Birmingham:IEEE Computer Society Press,2003.
[7]	MUSSE S,BABSKI C,CAPIN T,THALMANN D.Crowd modeling in collaborative virtual environments[C]∥Proceedings of the ACM Symposium on Virtual Reality Software and Technology.Washington:IEEE Computer Society,1998.
[8]	TECCHIA F,CHRYSANTHOU Y.Real-time visualization of densily populated urban environments:a simple and fastalgorithm for collision detection[C]∥Eurographics UK.Switzerland:Springer,2000.
[9]	AVNEESH S,ERIK A,SEAN C,LI M,DIENSH M.Real-time path planning for virtual agents in dynamic environments[C]∥IEEE Virtual Reality VR’07 Proceedings.Charlotte:IEEE Computer Society,2007.
[10]	KENNETH E,HOFF I,CULVER T,KEYSER J,LI M,MANOCHA D.Fast computation of generalized voronoidiagrams using graphics hardware[C]∥Proceedings of ACM SIGGRAPH.Los Angeles:ACM,1999.
[11]	DENNY M.Algorithmic geometry via graphics hardware[D].German:Universitat des Saarlandes,2003.
[12]	RONG G,TAN T.Jump flooding in GPU with applications to Voronoi diagram and distance transform[C]∥Proceedings ofthe Symposium on Interactive 3D Graphics.Boston:ACM,2006.

Cited By

Get Citation

PDF

XML

Article views (27) PDF downloads (9)

Turn off MathJax

Article Contents

Abstract

References

Voronoi-Based Real-Time Crowd Path Planning

Abstract

References

Catalog

Export File

Citation

Format

Content