1 Introduction
In image synthesis, as in many other fields, binary search trees are used to fulfil tasks that are often critical to applications. In image synthesis, examples of such operations are ray-tracing and frustum culling. A feature common to all these operations is that they consist in seeking information (the data set) contained in a certain volume (the search zone) of a k-dimension space (k ? N) and that they all use a binary search tree to perform this search as quickly as possible.

Assuming that the seeking information consist of points in space and that the search volume is a continuous and bounded interval, we shall see first of all that minimizing intra-class variance[sup]1[/sup] (i.e. solving the problem of the k-means) is the ideal construction heuristic for a binary search tree.

We shall then see that Lloyd's algorithm, which gives a local extremum to the k-means problem, is a very good heuristic, since it gives good results in practice, is very fast to compute, is robust, easy to implement and perfectly suited to animated data sets, common in image synthesis.


2 Related tasks
For a 1-dimensional space, the binary search tree is a classic case studied by every IT student. The k-means tree is an ideal generalization of this algorithm for spaces with k dimensions.

In image synthesis, the structures used are Kd-trees and BVHs (Bounding Volume Hierarchy). We should note that Kd-tree is a special case of BSP (Binary Space Partition). The most popular construction heuristic for these structures at the moment is called SAH (Surface Area Heuristic).


3 Ideal heuristic for search algorithm

3.1 Hypotheses and observations
Our purpose here is to visit the smallest possible number of nodes in the traversal algorithm, subject to the hypothesis that we can only act on the binary tree construction heuristic.

We shall further assume that the data set ? is finite, that this set is wholly contained in a convex region ? (continuous and bounded) and that the search zone is an interval of ?, continuous and bounded, denoted ? (convex or not). We note that on this hypothesis, a ray (used in ray tracing) bounded at ? is an acceptable search zone.

We shall make the hypothesis that, whatever the heuristic used for the construction of the tree, each node is associated with the whole of ? or a non-empty part of it (? is associated with the root node of the tree), and that each node possesses 0 or 2 child-nodes, depending on whether the node is associated with 1 or more than 1 of the points of ?. Thus each node which is not a leaf, splits its associated set of points into 2 non-empty subsets.

We shall observe that, if a node N possesses n points all contained in ? then, whatever the heuristic used, the sub-tree corresponding to N possesses 2n-1 nodes which are all likely to be visited (except in the case of ancillary optimizations that may be added to the traversal algorithm). Similarly, if ? contains a total of just n points, a minimum of 2n-1 nodes will be visited if n is the cardinal of ?, or a minimum of 2n nodes if it is not, irrespective of the heuristic used (except in the case of ancillary optimizations that may be added to the traversal algorithm).

Furthermore, if all the points of ? are contained in ?, then a total of exactly 2n-1 nodes will be visited, irrespective of the heuristic.

Every time that a part - non-empty, but not the entirety - of ? is sought, we can make the following observation: the ideal magic tree would be a tree which would immediately split the root node into two subsets: the set of points sought and the set of points not sought, whatever ? might be. In such a case, only the minimum number of nodes would be visited, i.e. 2n nodes.

From these observations, we can easily deduce the conditions to be fulfilled in order to minimize the number of nodes visited in the general case. We would have to:

• refrain from visiting nodes having no associated point in ? (i.e. 3.3)
• maximize the probability P[sub]ideal[/sub] so that each node N splits its associated set into two subsets, one set entirely sought and one set entirely non-sought (i.e. 3.2)
• If the set of points associated with a node is sought, then we shall visit the same number of nodes in the sub-tree, irrespective of the heuristic (except in the case of ancillary optimizations that may be added to the traversal algorithm). Thus, this case is not significant.

3.2 Maximizing P[sub]ideal[/sub]
The hypothesis here, then, is that a node N is visited as long as at least one point in the set of points associated with it is sought, but not all of them.

The original problem of the k-means is to minimize intra-class variance (the sum of variances of each set is minimal). For each node N, solving the k-means problem with k = 2 enables us to determine two subsets which are associated with the child-nodes of N.

Two observations must be made here. This first is that minimizing intra-class variance simultaneously maximizes inter-class variance, because the total variance of the set is equal to the sum of intra-class variance and inter-class variance [1].

The second observation is crucial to what follows. Taking two points P1 and P2: if P1 is in ?, then the probability that P2 is also in ? increases as the distance separating the two points diminishes. It is equal to 1 when the distance is zero, and to 0 when the distance separating the two points is greater than the maximum distance between P1 and any other point of ? [2]. This can easily be visualized for a convex region ?. It is sufficient to imagine a non-convex region as a convex region from which a piece has been removed, and it is clear that this also works for non-convex regions. Thus, from the general point of view, when nothing is known about ?, the probability that P2 is also in ? is maximized when the distance between P1 and P2 is minimized.

The idea behind the k-means is that minimizing intra-class variance enables us to ensure that the points within one class are as close to each other as possible, while maximizing inter-class variance enables us to ensure that the classes themselves are as far from each other as possible.

Thus with the k-means heuristic and these hypotheses, it can be clearly seen that when a node N is visited, there exist i and j ? {0,1}, i!=j such that ? = ?[sub]1[/sub][sup]Ki[/sup]?(Pik ? ? | ?m such that Pim ? ? )*(1 - ?[sub]1[/sub][sup]Kj[/sup]?(Pjk ? ? | ?m such that Pim ? ?)) is maximized, where Pi is the set of points associated with the child-node i of N, Pj is the set of points associated with child-node j of N, Pik is the k[sup]th[/sup] point of Pi, Pjk is the k[sup]th[/sup] point of Pj, Ki is the cardinal number of Pi and Kj is the cardinal number of Pj.

Now P = P[sub]ideal[/sub]; hence, tackling the k-means problem maximizes P[sub]ideal[/sub].


3.3 "Nodes visited where no associated point is sought", or the bounding volumes problem
A node visited that in reality possesses no point sought brings us straight to the problem of bounding volumes. It is possible to establish that a bounding volume intersects with ? although no point ? associated with this volume belongs to ?.

But here again, the k-means heuristic demonstrates its effectiveness. By definition, there cannot exist a bounding volume whose points are on average closer to the points of the set associated with it than the bounding volumes determined by sets of points determined by the k-means. Thus, the probability of the case arising where no point is in reality contained in ? is minimized.


4 Lloyd's algorithm and animations
The most popular algorithm for solving the k-means problem is Lloyd's algorithm. But it only enables the determination of a local extremum. This algorithm nevertheless offers many advantages: it gives good results in practice, is very easy to implement, it converges rapidly, it is robust and... it is iterative.

The fact that it is iterative is especially interesting for the animated data sets frequently used in image synthesis. This is because it is possible to perform only a limited number of iterations each frame, so that there is no effect on frame-rate.


5 Conclusion
It seems to us that the algorithms for solving the k-means problem ought to be employed in preference to very many heuristics used for the construction of binary search trees, because they correspond naturally to the problems of partition when seeking information in both bounded and continuous intervals.

In image synthesis, the most popular construction heuristic is SAH. Unfortunately, it is very slow to calculate, so that approximation methods are generally used. Although SAH acts on area-related information, in contrast to our k-means heuristic, we consider that it should be abandoned in favour of methods derived from our k-means heuristic, since although it is similar in principle, it does not possess all the theoretical and practical advantages of the latter.


References
[1] http://ljk.imag.fr/membres/Bernard.Ycart/smel/cours/ts/node14.html

[2] http://en.wikipedia.org/wiki/Distance

[3] http://en.wikipedia.org/wiki/K-means_algorithm

[4] State of the art in Ray Tracing Animated Scenes, Ingo Wald, William R. Mark, Johannes G?nther, Solomon Boulos, Thiago Ize, Warren Hunt, Steven G. Parker, Peter Shirley, EUROGRAPHICS 2007

[sup]1[/sup] A class is no more nor less than a set of points, and we shall use these terms interchangeably in this document.