Abstract: To shorten the preprocessing of the iso-surface extraction from volume datasets, we propose a new algorithm for building binary interval tree nodes.Our approach employs the span space subdivision of a binary interval tree, and reconstructs the binary interval tree nodes by means of the lattice partition.The new scheme effectively reduces the complexity of the interval sorting in the preprocessing stage, and consequently shortens the preprocessing time by 50%.Experimental results and analysis verify that our approach achieves the similar efficiency as the conventional active-cell searching algorithm, and is especially practical for real-time visualization applications.