A balanced octree based on morton code and mirror code
In contact analysis and animation simulation,there are massive and frequent re-mesh operations.A series of algorithms based on Morton code method have been established to carry out fast construction of BVH trees.Unfortunately,search efficiency of BVH trees constructed by these algorithms is unstable due to their unbalance.Therefore,an alternative algorithm of the balanced octree(BOT)based on Morton code,targeting both fast construction and stable search efficiency,is proposed in this paper.A mirror code method is designed to ensure that each upper node of BOT contains 8 branches and the amount difference of triangle units belonging to those nodes on the same tree level is no larger than one.Experiments showed that,the parallel construction of BOT achieved 1.29× speedup over that of the existing OIOT under the CUDA framework.In addition,construction efficiency of BOT increase with larger mesh size.Meanwhile,a BOT tree has a higher filter rate.In parallel contact searching,it has achieved 1.13× and 1.06× speedup over OIOT in convex-contact and edge-contact cases,respectively.
万方数据
维普
