Premium
DKD: a fast k ‐d tree update design for dynamic scenes
Author(s) -
Yang Xin,
Liu Qi,
Zhang Pengfei,
Xin Lutong,
Zhou Dongsheng,
Wang Yuxin,
Zhang Qiang,
Wei Xiaopeng
Publication year - 2016
Publication title -
computer animation and virtual worlds
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.225
H-Index - 49
eISSN - 1546-427X
pISSN - 1546-4261
DOI - 10.1002/cav.1717
Subject(s) - computer science , tree traversal , rendering (computer graphics) , tree (set theory) , reset (finance) , computer graphics (images) , artificial intelligence , algorithm , mathematics , mathematical analysis , financial economics , economics
We design dynamic k ‐d (DKD) tree based on classical k ‐d tree for animated scene rendering. Our method can inherit the benefit of efficient traversal of k ‐d tree and minimize time cost to update DKD tree, making it well suited for animated geometry. DKD employs primitive reset, redistribution to reflect the updated positions of geometry, and leaf node incremental growing to avoid the deterioration of hierarchy quality due to refitting. Our experiments show that DKD has a significant rendering performance improvement than selected existing methods. Copyright © 2016 John Wiley & Sons, Ltd.