Premium
Automatic Hierarchical Level of Detail Optimization in Computer Animation
Author(s) -
Mason Ashton E.W.,
Blake Edwin H.
Publication year - 1997
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/1467-8659.00156
Subject(s) - computer science , knapsack problem , rendering (computer graphics) , computer animation , animation , representation (politics) , theoretical computer science , algorithm , artificial intelligence , computer graphics (images) , politics , political science , law
We show that the hierarchical level of detail optimization problem is equivalent to a constrained version of the Multiple Choice Knapsack Problem, and present a new algorithm whose solution to it is at least half as good as the optimal one. The advantage of the hierarchical algorithm is that it allows the use of hierarchical level of detail descriptions in which shared representations may be provided for groups of objects. Rendering cost may then be saved to afford better renderings of more important objects, and the algorithm is capable of providing a complete representation of the visible scene even when the visible scene complexity is very high. Our algorithm has a worst case time complexity of O(nlogn), and is incremental so that it typically completes in only a few iterations. We introduce the use of perceptual evaluation to demonstrate the effectiveness of the use of representations for groups of objects that our algorithm allows.