METHOD AND APPARATUS FOR RAY TRACING USING ADAPTIVE MULTI-HIERARCHY KD-TREE ALGORITHM IN 3D RAY TRACING SYSTEM

摘要

A method and an apparatus for tracing a ray by using adaptive multi-hierarchy kd tree algorithm in a 3d ray tracing system are provided to reflect changed contents to the entire tree by updating only a sub tree which is affected due to a change of geographic information, thereby shortening an update time. An acceleration data structure generating unit(410) produces an adaptive multi-hierarchy acceleration data structure of binary space division like a kd-tree data structure. An acceleration data structure searcher(420) regards a group node as a primitive of one bounding type to perform a cross check with a ray if the acceleration data structure searcher meets the group node during a search process. If an acceleration data structure update unit(440) does not update the entire acceleration data structure which is generated, only data structure information to which an object having changed geographic information belongs is updated.