Hervé Brönnimann

Marc Glisse

Cost-Optimal Trees for Ray Shooting

Predicting and optimizing the performance of ray shooting is a very important problem in computer graphics due to the severe computational demands of ray tracing and other applications, e.g., radio propagation simulation. Aronov and Fortune were the first to guarantee an overall performance within a constant factor of optimal in the following model of computation: build a triangulation compatible with the scene, and shoot rays by locating origin and traversing until hit is found. Triangulations are not a very popular model in computer graphics, but space decompositions like kd-trees and octrees are used routinely. Aronov et al.

[1] developed a cost measure for such decompositions, and proved it to reliably predict the average cost of ray shooting. In this paper, we address the corresponding optimization problem, and more generally d-dimensional trees with the cost measure as the optimizing criterion. We give a construction of quadtrees and octrees which yields cost O(M ), where M is the infimum of the cost measure on all trees, for points or for (d -1)-simplices. Sometimes, a balance condition is important. (Informally, balanced trees ensures that adjacent leaves have similar size.) We also show that rebalancing does not affect the cost by more than a constant multiplicative factor, for both points and (d -1)-simplices. To our knowledge, these are the only results that provide performance guarantees within approximation factor of optimality for 3-dimensional ray shooting with the octree model of computation.

Introduction

Given a set S of objects, called a scene, the ray-shooting problem asks, given a ray, what is the first object in S intersected by this ray. Solving this problem is essential in answering visibility queries. Such queries are used in computer graphics (e.g., ray tracing and radiosity techniques for photo-realistic 3D rendering), radio-and wave-propagation simulation, and a host of other practical problems.

A popular approach to speed up ray-shooting queries is to construct a space decomposition such as a quadtree in 2D and an octree in 3D. The query is then answered by traversing the leaves of the tree as they are intersected by the ray, and for each cell in turn, testing for an intersection between the ray and the subset of objects intersecting that cell. The performance of such an approach greatly depends on the quality of that space decomposition.

Unfortunately, not much is understood about how to measure this quality. The ultimate criterion is running time, which also involves many factors (among which hardware acceleration and memory hierarchy side effects) and in any case is not directly amenable to analysis. Practioners use a host of heuristics and parameters of the scene, of which the object count is not the most important; more important seems to be the size of the objects in the scene, and other properties of the object distribution (density, depth complexity, surface area of the subdivision). Those parameters are used to develop automatic termination criteria for recursively constructing the decompositions (see Section 3). While they perform acceptably well most of the time, none of these heuristics performs better than the brute-force method in the worst case. More importantly, occasionally the termination criteria will produce a bad decomposition, and in any case there is no way to know the quality of the decomposition because lower bounds are hard to come by.

In [START_REF] Aronov | Cost prediction for ray shooting[END_REF], we proposed a measure for bounded-degree space decompositions, based on the surface area heuristic, which is a simplification (for practicality) of a more complicated but theoretically sound cost measure: under certain assumptions on the ray distribution, the cost measure provably reflects the cost of shooting an average ray using the space decomposition. So far, we have focused on experimentally proving that all the assumptions we make are warranted and do not greatly affect the effectiveness of the cost measure. Thus the cost measure, introduced in the next section, which is simple to compute and accurate, can guide us in optimizing the data structure. The topic of this paper is to present new algorithms and analyses for constructing provably (near-)optimal decompositions with respect to this cost measure.

Related work There has been a lot of work on quadtrees and octrees in the mesh generation and graphics community (see the book by Samet [START_REF] Samet | Design and Analysis of Spatial Data Structures[END_REF], the thesis of Moore [START_REF] Moore | Simplicial Mesh Generation with Applications[END_REF], or the survey by Bern and Eppstein [START_REF] Bern | Mesh generation and optimal triangulation[END_REF] for references). Since they are used for discretizing the underlying space, usual considerations include the tradeoff between the size of the tree and their accuracy with respect to a certain measure (that usually evaluates a maximum approximation error with respect to some surface). These are not usually relevant for ray shooting.

There is a rich history of data-structure optimization for ray tracing and other ray-shooting-related problems in computer graphics. Cost measures have been proposed for ray shooting in octrees by McDonald and Booth [START_REF] Macdonald | Heuristics for ray tracing using space subdivision[END_REF], Reinhard and coll. [START_REF] Reinhard | Cost distribution prediction for parallel ray tracing[END_REF][START_REF] Reinhard | Cost prediction in ray tracing[END_REF], Whang and coll. [START_REF] Whang | Octree-R: An adaptive octree for efficient ray tracing[END_REF]. Similar optimizations have been tried for related data structures, such as bounding volume hierarchies (BVH) [START_REF] Goldsmith | Automatic creation of object hierarchies for ray tracing[END_REF][START_REF] Subramanian | Automatic termination criteria for ray tracing hierarchies[END_REF][START_REF] Weghorst | Improved computational methods for ray tracing[END_REF], BSP-trees [START_REF] Naylor | Constructing good partitioning trees[END_REF], uniform grids [START_REF] Cleary | Analysis of an algorithm for fast ray tracing using uniform space subdivision[END_REF], and hierarchical uniform grids (HUG) [START_REF] Cazals | Bucket-like space partitioning data structures with applications to ray tracing[END_REF]. We should also mention the work of Havran and coll. [START_REF] Havran | The Best Efficiency Scheme[END_REF], who propose a method to determine experimentally the most efficient space subdivision for a given scene, by picking a similar scene (according to certain characteristics such as size, number of objects, densities, etc.) in a database of scenes, for which the most efficient scheme has been determined. All of these approaches use heuristic criterion (sometimes very effectively) but none offer theoretical guarantees.

Our results

In [START_REF] Brönnimann | Cost-optimal quadtrees for ray shooting[END_REF] and in this paper, we are interested in constructing trees with cost as low as possible, with a guaranteed approximation ratio. The only objects we consider are simplices (points and segments inside the unit square [0, 1] 2 in R 2 , or points, segments and triangles inside the unit cube [0, 1] 3 in R 3 ). We however assume the Real-RAM model so as to avoid a discussion on the bit-length of the coordinates.

We give and analyze algorithms that produce trees with cost O(M), where M is a lower bound on the cost of any tree. The novelty from [START_REF] Brönnimann | Cost-optimal quadtrees for ray shooting[END_REF] is the extension to d=3 and higher of the results. we also examine the effect of rebalancing the tree on the cost measure, and prove that rebalancing only increases the cost by a constant multiplicative factor. While there are many subdivision criteria used by practitioners in computer graphics, our subdivision scheme is the first to our knowledge to guarantee an approximation ratio.

In a follow-up paper [START_REF] Aronov | Cost-driven octree construction schemes: an experimental study[END_REF] to [START_REF] Aronov | Cost prediction for ray shooting[END_REF], we evaluated several heuristics, including those presented here, to optimize the cost value of an octree for a given scene. Both our algorithm and a simpler heuristic (namely, greedy without lookahead in this paper's terminology) gave the best cost. The optimal guarantees we obtain here nicely strengthen the experimental results and helped identify a simplification which offers a performance similar to the guaranteed algorithm proposed in this paper.

General cost measure results

The following cost measure was introduced by Aronov et al. [START_REF] Aronov | Cost prediction for ray shooting[END_REF] for the purpose of predicting the traversal cost of shooting a ray in R d , while using a quadtree (for d = 2) or an octree (for d = 3) to store S:

c S (T ) = σ∈L(T ) (γ + |S ∩ σ|) × λ d-1 (σ), (1)
where L(T ) is the set of leaves of the quadtree, S ∩ σ is the set of scene objects meeting a leaf σ, and

λ d-1 (σ) is the perimeter length (if d = 2) or surface area (if d = 3) of σ.
This cost function provably models the cost of finding all the objects intersected by a random line, with respect to the rigid-motion invariant distribution of lines [START_REF] Aronov | Cost prediction for ray shooting[END_REF]. Here's an overly simplified explanation why: when shooting a ray, the octree is traversed and all the objects in a traversed leaf are tested against the ray to find the first hit. The cost in a leaf σ is thus O(γ + |S ∩ σ|). The coefficient γ depends on the implementation, and models the ratio of the cost of the tree traversal (per cell) to that of a ray-object intersection test (per test). 1But integral geometry tells us that a random ray will intersect σ with probability λ d-1 (σ) (this is not quite true; read [START_REF] Aronov | Cost prediction for ray shooting[END_REF] for the niceties). Hence the average cost of ray shooting is given by the weighted average, exactly what our cost measure computes.

Tree and object costs. Observe that the cost measure can be split into two terms: c t (T ) = γλ d-1 (T ) = γ σ∈L(T ) λ d-1 (σ) (the tree cost), and c o (T ) = s∈S λ d-1 (s ∩ T ) (the object cost), where s ∩ T denote the set of leaves of T crossed by s and λ d-1 is extended to sets of leaves by summation. It is useful to keep in mind the following simple observations: when subdividing a cell σ, the total tree cost of its children is twice the tree cost of σ, and the object cost of an object is multiplied by m/2 d-1 where m ∈ [1 . . . 2 d ] is the number of children intersected by the object. Note that m ≤ 3 for a segment in 2D and m ≤ 7 for a triangle in 3D (unless they pass through the center of the cell). As the tree grows finer, the tree cost increases while the object cost presumably decreases.

Lemma 1. For any set S of simplices in [0, 1] d , c(T ) ≥ 2dγ+d √ 2 s∈S λ d-1 (s), for any d ≥ 2.
Proof. The tree cost cannot be less than λ d-1 ([0, 1] d )γ = 2dγ, and the object cost cannot be less than s∈S λ d-1 (s)S. We can improve this lower bound further by noting that any leaf σ that is intersected by an object s has area at least d √ 2 times λ d-1 (s ∩ σ). Indeed, the smallest ratio λ d-1 (σ)/λ d-1 (s ∩ σ) happens when s maximizes λ d-1 (s ∩ σ); this happens for a diagonal segment of length √ 2 for the unit square (of perimeter 4), and for a maximal rectangular section of area √ 2 for the unit cube (of area 6). In fact, the maximal section of the unit d-cube is √ 2 [START_REF] Ball | Cube slicing in R n[END_REF], hence the ratio is at least 2d/ √ 2 = d √ 2 in any dimension.

Tree construction schemes

All we said so far was independent of the particular algorithm used to construct the tree. In this section, we introduce several construction schemes and explore their basic properties.

Terminology and notation. We follow the same terminology as [START_REF] Brönnimann | Cost-optimal quadtrees for ray shooting[END_REF], and generalize it to encompass any dimension. For the d-cube [0, 1] d and the cells of the decomposition, we borrow the usual terminology of polytopes (vertex, facet, hface, etc.). The square is a quadtree that has a single leaf (no subdivision), the cube is an octree with a single leaf, and the d-cube is a single-leaf tree (for any d). We call this tree the unit cell and denote it by T (empty) . If we subdivide this leaf recursively until depth k, we get a complete tree (of depth k), denoted by T (complete) k , and its leaves form a regular d-dimensional grid with 2 k cells on each side. In a quadtree, if only the cells incident to one facet (resp. d facets sharing a vertex, or touching any of the 2d facets) of a cell are subdivided, and this recursively until depth k, the subtree rooted at that cell is called a k-side (resp. k-corner and k-border ) tree, and denoted by T ); see Figure 1 for an illustration of the 2D case. In higher dimensions, there are other cases (one for each dimension between 1 and d -2). All this notation is extended to starting from a cell σ instead of a unit cell, by substituting σ for T : for instance, the complete subtree of depth k subdividing σ is denoted by σ

(complete) k .
The subdivision operation induces a partial ordering ≺ on trees, whose minimum is the unit cell. Again, this partial ordering is extended to subtrees of a fixed cell σ. We consider recursive algorithms for computing a tree of a given set S of objects, which subdivide each cell until some given termination criterion is satisfied. In particular, we may recursively subdivide the unit cell until each leaf meets at most one object. We call this the separation criterion, and the resulting tree the minimum separating tree, denoted T (sep) (S), with variants where the recursion stops at depth k, denoted T (sep) k (S). (Note that the depth of T (sep) is always infinite if any two simplices intersect.) In 3D, for non-intersecting triangles, a variant of [START_REF] Aronov | Approximating minimum weight triangulations in three dimensions[END_REF] stops the recursive subdivision also when no triangle edge intersects the leaf (but any number of non-intersecting triangle interiors may slice the leaf). We will not analyze this variant in this paper.

Dynamic programming and greedy strategies. As introduced in [START_REF] Brönnimann | Cost-optimal quadtrees for ray shooting[END_REF], the dynamic programming algorithm finds the tree that minimizes the cost over all trees with depth at most k, which we denote by T , and simply performs a bottom-up traversal of all the nodes, while maintaining the optimum cost of a tree rooted at that node. The decision whether to keep the subtree of a cell or prune it is based on the cost of the cell vs. the sum of the optimum costs of the subtrees rooted at its 2 d children.

Unfortunately, the memory requirements of this algorithm are huge for large values of k (although they remain polynomial if k = Θ(log n); see next section). Therefore we also propose a greedy strategy with bounded lookahead: the algorithm proceeds by recursively subdiving the nodes with a greedy termination criterion: when examining a cell σ, we run the dynamic programming within σ with depth k (k is a parameter called lookahead ). If the best subtree σ We call this the k-greedy strategy, and denote the resulting tree by T (k-greedy) (S) (or σ (k-greedy) (S) if we start from a cell σ instead of the unit cell). Note that unlike all the other quadtrees constructed up to now, that tree could be infinite. We use the notation T (k-greedy)

to denote the tree constructed with the k-greedy lookahead criterion combined with a maximum depth of .

With no lookahead (k = 1), the greedy strategy simply examines whether one subdivision decreases the cost measure. Below, we show that this does not yield good trees in general. We will analyze the greedy strategies without and with lookahead, first for points, then for simplices. But first, we must grapple with the issue of infinite depth.

Pruning beyond a given depth. The "optimal" tree may not have finite depth (it is conceivably possible to decrease the cost by subdividing ad infinitum), so we let M denote the infimum of c(T ) over all trees T for S. (As a consequence of Lemma 1, M ≥ 2dγ > 0.) In order to have an algorithm that terminates, we usually add an extra termination criterion such as a depth limit of k.

We now show that pruning a tree at a depth of k, for some choice of k = Θ(log n) (to ensure that the tree has a polynomial size), increases cost at most by a constant factor. We first show it for arbitrary convex obstacles (simplices in particular). Then we improve on the result for the case of points. The proofs are no difficult and omitted for space consideration. Nevertheless, these considerations of depths are necessary to ensure that the computation is meaningful. Lemma 2. Let T be a d-dimensional tree which stores a set S of n convex objects of dimensions not more than d -1. For k = log 2 n + C, let T k be the tree obtained from T by removing every cell of depth greater than k. Then c(T k ) = O(c(T )) and the constant does not depend on n nor S.

Remark A choice of k = log 2 n + C ensures that T k has at most (2 k ) d = O(n d )
leaves, for any fixed d. Hence the algorithm which computes the full subdivision at depth k and then applies the dynamic programming heuristic provably computes a tree whose cost is O(M ) in polynomial time, as a consequence of Lemma 2.

As a side note, with slightly more restrictive hypotheses on T , the depth k can be reduced for points so that T k has size at most O(n 1+ 1 d-1 ) = O(n 2 ) (for any d ≥ 2) and cost as close as desired to that of T . Lemma 3. Let T be a d-dimensional tree, which stores a set S of n simplices. Assume that T does not contain empty internal nodes (i.e. that are subdvided but do not contain any object). Let T k be the tree obtained from T by removing every cell of depth greater than k. Then, for every ε > 0 there exists a C (that depends only on ε and γ but not on n) such that, for k

= 1 d-1 log 2 n + C, we have c(T k ) ≤ (1 + ε)c(T ).
4 Cost-optimal trees

The following lemma was proven in [START_REF] Brönnimann | Cost-optimal quadtrees for ray shooting[END_REF] for the case d = 2. Its statement and proof extend straightforwardly to higher dimensions.

Lemma 4 ( [9]

). The lookahead greedy strategy does not always give a costoptimal tree. Specifically, for any k, there is a set S of n objects such that no tree of depth at most k has cost less than 2d(γ + n), but some quadtree of depth at least k + 1 has cost less than 2d(γ + n).

The counterexample for d = 2 consists of n copies of the segment pq, where p = (1 -2 -m-1 , 2 -m-1 ), and q = (2 -m-1 , 1 -2 -m-1 ), and considering the costoptimal quadtree

Q (2)
k,m of depth at most k. As long as k ≤ m + 1, the situation is similar to the case where pq is the whole diagonal and the cost-optimal quadtree of depth at most k is the square, as can easily be verified. When k becomes larger, however, it becomes interesting to subdivide the corners.

In this example, the ratio between the cost of the optimal tree and the cost of the initial tree is bounded below by a constant. Thus in that case the tree we obtained is a good approximation of the optimal solution. In fact, this can be proven for all sets of objects.

Lemma 5. Given a set S of flat objects in the unit cube, and let M be the infimum of c(T ) over all trees T . There is an integer p (for d = 2 or d = 3, p = 3) such that the tree T (p-greedy) constructed by the p-greedy strategy has cost c(T (p-greedy) ) = O(M ).

Proof. The intuition is that small objects behave well, and the cost of a big object is bounded below by a constant times its size so it cannot be reduced by very much. Let us look at a cell σ of the tree T (p-greedy) : we are going to show that, when the optimal decomposition of depth at most p of a cell σ does not improve on the cost of σ, then the cost of σ is O(M σ ) where M σ is the infimum cost of all the possible tree subdivisions of σ. If this holds true for every leaf σ of the p-greedy strategy, then c(Q (p-greedy) ) = O(M ) as well.

Assume there are a objects meeting at most C d (2 p ) cells, and b other objects. The cost of σ is (γ + a + b)λ 1 (σ). Since σ

(complete) p has cost at most 2 p γ + a C d (2 p ) 2 p(d-1) + 2 p b λ 1 (σ)
, which we assumed to be at least c(σ), we have

c(σ) = (γ + a + b) λ 1 (σ) ≤ 2 p γ + a C d (2 p ) 2 p(d-1) + 2 p b λ 1 (σ), which implies that a ≤ (γ + b)(2 p -1) 1 -C d (2 p ) 2 p(d-1)
-1

. We will need a technical lemma: Let p be the smallest integer such that

C d (2 p ) < (2 p ) d-1
. By lemma 6, an object which belongs to more than C d (2 p ) cells has measure at least S d (2 p ) so its contribution to the cost is at least (d

√ 2S d (2 p ))λ d-1 (σ). The optimal cost M σ is then greater than (γ + bd √ 2S d (2 p ))λ d-1 (σ).
We have then proved that M σ is at least a fixed fraction of the cost of σ, and the lemma follows.

Already in 2D, the separating quadtree strategy does not work as well for segments as for points, especially since it is not able to distinguish between a segment that barely intersects the corner of the square and the diagonal (in the first case it is usually good to subdivide, and in the second case it is not). The lookahead strategy is then a true improvement.

The case of points. Arguably, the case of points is of theoretical interest only, but has relevance since simplices are usually very small in a graphics scene (when they come from a subdivision surface), and can be thought of as points. This is lent credence by a recent trend: point cloud data (PCD) is becoming an important primitive in computer graphics, and several algorithms for rendering them have been given of late, which are amenable our cost measure. In addition, points are also produced by sampling, 3D scanners, etc.; even though ray shooting makes little sense for these applications the points can be in an octree and the cost may have other significance there.

We first examine the simple termination criteria. Take the example of n points in a corner, S n , described in our configuration 2. In 2D, with no subdivision, the cost is 4 (γ + n). With full subdivision to depth k, the cost is 2 k+2 γ + n2 2-k which is at least 8 √ γn for any value of k. Now the separation criterion stopped at depth k gives a cost of 12γ + (4n -3γ)2 -k (this is also what the greedy algorithm leads to). For large values of n, these are respectively Θ(n), Ω( √ n) and O(1). Thus no subdivision or a complete subdivision don't approximate the optimum very well.

In the plane, the 2-greedy strategy may produce a quadtree of cost Θ(n) times the optimal cost, as can be seen by placing n points in the center of the square: the cost after two subdivisions is 12 + 4(γ + n), more than the initial cost of 4(γ + n); hence the tree is not subdivided, yet the cost would tend to 24 if subdivided ad infinitum. In any dimension, the same example shows that the 1-greedy strategy also has a bad approximation ratio of Θ(n). Nevertheless, with one more level of lookahead, everything works near-optimally. We simply state the lemma and omit the proof, similar the the one given above for simplices.

Lemma 7. The 3-greedy strategy in the plane, and the 2-greedy strategy in d dimensions (d ≥ 3) produce near-optimal trees for points. Namely, if S be a set of n points in the unit d-cube, and M is the infimum of c(T ) over all trees T , then c(T (3-greedy) ) = O(M ) for all d ≥ 2, and c(T (2-greedy) ) = O(M ) for all d ≥ 3.

As for finding the optimal quadtree, the question is still open whether for given values of γ (and maybe of n) there exists a k such that the lookahead strategy yields the optimal result. All we know is that if n = 5 and γ < 1 tends to 1, the required k tends to infinity. We can also mention that if every point belongs to at most one cell, then k = 1 leads to the optimal tree.

Rebalancing quadtrees and octrees

Quadtrees are used in meshing for computer graphics, and octrees are used as a space subdivision method for ray casting and radiosity methods, for instance. Both quadtrees and octrees are used in scientific computing numerical simulations (e.g., finite element methods). These are but a few applications where quadtrees and octrees have appeared. In all these applications, it can be important to maintain aspect ratio (hence starting with a unit cell) and to ensure that two neighboring cells don't have wildly differing sizes. This has led several authors to propose balancing for trees. Also from our perspective, since the cost measure of [START_REF] Aronov | Cost prediction for ray shooting[END_REF] provably relates to the cost of traversal only for balanced trees, we are interested in balancing trees as well. In this section, we prove that rebalancing does not affect the cost by more than a multiplicative constant factor.

Definitions. Two leaves are k-adjacent if they intersect in a convex portion of dimension k. A tree is called k-balanced if the depths of any two k-adjacent leaves differ by at most one. Notice that when considering two k-balanced trees, their intersection, constructed from the unit cell by subdividing all and only cells that are subdivided in both trees, is k-balanced. Thus for a tree T , there is a unique balanced tree bal k (T ) = min{T T : T is k-balanced}, which is called the k-rebalancing of T .

For instance, 0-balanced quadtrees are what Moore called smooth quadtrees [START_REF] Moore | Simplicial Mesh Generation with Applications[END_REF], and 1-balanced what he called balanced and others called 1-irregular or restricted [START_REF] Bank | Refinement algorithms and data structures for regular local mesh refinement[END_REF][START_REF] Moore | Simplicial Mesh Generation with Applications[END_REF][START_REF] Herzen | Accurate triangulations of deformed intersecting surfaces[END_REF].

Cost analysis While the size of bal k (T ) is known to increase by at most a constant factor from the size of T , the final cost c(bal k (T )) is unknown, however. Our main result concerning cost analysis is the following, when objects in S are either points or segments. The following lemma was first proven by Weiser in 2D, and by Moore for any dimension d ≥ 2. Lemma 8 ( [18]). Let T be a tree. There is a 0-balanced tree T T such that c t (bal 0 (T )) ≤ 3 d c t (T ).

Since T must be a refinement of bal 0 (T ), which is itself a refinement of bal k (T ), for any k > 0, this implies that c t (bal k (T )) ≤ c t (bal 0 (T )) ≤ 3 d c t (T ). Note that the same construction also implies the factor 3 d on the number of leaves.

Next we prove in Lemma 9 that the object cost of bal k (T ) is at most twice (for points) and some constant B d < S d (for simplices) times that of T . The proof is omitted for lack of space. Lemma 9. Let T be a tree, and consider the object cost of a single object s ∈ S both in T and in bal k (T ). If s is a point, then

λ d-1 (s ∩ bal k (T )) ≤ 2λ d-1 (s ∩ T ). If s is a convex object of dimension at most d -1 (e.g. a (d -1)-simplex), then λ d-1 (s ∩ bal k (T )) ≤ B d λ d-1 (s ∩ T ).
Compounding all these costs together, we have c o (bal k (T )) ≤ 3 d c o (T ) for any 0 ≤ k < d, which ends the proof of the theorem.

Remark. It could also very well be that rebalancing actually decreases the cost. We don't know that, and we don't need it since we are mostly interested in trees for which c(T ) = O(M ). In any case, we can ask if there is a reverse theorem (lower bound on c(bal k (T )) in terms of c(T )).

Conclusion

In this paper we have proved that instead of considering the optimal octree, and without increasing the cost too much, we may consider the octree given by the lookahead strategy. Still, this may yield an infinite subdivision. In order to have an effective algorithm, we need to add a termination criteria such as a depth limit of log 2 n. As we have also proven, this increases again the cost at most by a constant factor. In practice, we find that greedy with or without lookahead yield near-optimal octrees, hence the approximation ratio seems close to one. 2All the results stated in this paper should extend easily to recursive grids and simplicial trees as well, in two and higher dimensions, with only small differences. However, the constants involved in the analysis would be even higher than they are here.

We conclude with a few open problems: first, is it true that by pruning at depth k = Θ(log n), we can approach the cost to within 1 + ε? Since the optimal tree might be infinite, there is little sense in asking for an algorithm that constructs the optimal tree. But if the answer to the first question were true, it would be nice to have a PTAS with respect to the cost measure. We don't know if the greedy strategy for high enough lookahead would fit the bill.

Lastly, the cost measure considered here is simple but does not model the average traversal cost during ray shooting. For this, the following cost measure should be considered [START_REF] Aronov | Cost prediction for ray shooting[END_REF]:

c * (T ) = σ (γ + |S ∩ σ|) × (λ d-1 (σ) + λ d-1 (S ∩ σ)), (2)
x where λ d-1 (S ∩ σ) measures the portion of the objects within σ. Our only result here is that the greedy strategy does not work.

B Pruning (Lemmas 2 and 3)

Lemma 10. Let T be a d-dimensional tree which stores a set S of n convex objects of dimensions not more than d -1. For k = log 2 n + C, let T k be the tree obtained from T by removing every cell of depth greater than k. Then c(T k ) = O(c(T )) and the constant does not depend on n nor S.

Proof. First, the tree cost will only increase while further subdividing, so that c t (T k ) ≤ c t (T ). The cells of depth less than k are the same in T and T k , hence the object cost of T is an upper bound for all the cells of T k with depth less than k. It remains to bound the object cost of the leaves of T k at depth k.

Let us consider an arbitrary object, and since we are only concerned with depth k, let us consider the full subdivision of depth k instead of T k . We let K be 2 k . This is a d-dimensional grid of side K, with K d cells. Our first purpose is to give an upper bound on the number of cells of this grid that the object can intersect. Since the dimension of the object is at most d -1, the object belongs to a hyperplane: consider the coordinate of largest absolute value of the normal vector to this hyperplane, and project both the object and the grid along the corresponding direction. By our choice of projection, each (d -1)-cell intersected by the projection of the object is the projection to at most d+1 d-cells intersected by the objects. The (d-2)-dimensional boundary of the projection is also convex, and may intersect at most K d-1 -(K -2) d-1 ≤ 2dK d-2 cells (by convexity, the worst case occurs when the boundary is largest possible, hence intersects all the border cells of the grid). The (d -1)-dimensional relative interior cannot contain more than K d-1 • λ d-1 (s) inner cells. The total number of cells met by the object is then at most (d + 1)

• 2dK d-2 + K d-1 λ d-1 (s) .
Now, the measure of a cell is 2dK 1-d . The cost of the object associated to depth k cells is then at most 2d(d + 1) (2d/K + λ d-1 (s)). Summing over all objects gives a total of at most 2d(d + 1) (2dn/K + s λ d-1 (s)). Substituting 2 log 2 n+C for K shows that the combined object costs of the leaves of T k at depth k is at most 2d(d + 1) d • 2 1-C + s λ d-1 (s) . By Lemma 1, this is at most max √ 2(d + 1), d(d + 1)2 1-C /γ times the cost of T . Putting everything together, c(T k ) ≤ 1 + √ 2(d + 1) + d(d + 1)2 1-C /γ c(T ).

Lemma 11. Let T be a d-dimensional tree, which stores a set S of n simplices. Assume that T does not contain empty internal nodes (i.e. that are subdvided but do not contain any object). Let T k be the tree obtained from T by removing every cell of depth greater than k. Then, for every ε > 0 there exists a C (that depends only on ε and γ but not on n) such that, for k

= 1 d-1 log 2 n + C, we have c(T k ) ≤ (1 + ε)c(T ).
Proof. The cost of a cell σ which contains n σ points and has depth k

= 1 d-1 (log 2 n + C) is c(σ) = (γ + n σ )2d • 2 -k(d-1) = 2d 2 C n (γ + n σ ).
The proof for points hinges on the fact that, unlike an arbitrary simplex, a point belongs to at most 2 d leaves, and that to be subdivided, a cell needs to contain at least one point. Hence, there are at most 2 d n leaves in T k which contain a point, and σ n σ ≤ 2 d n. Summing over all leaves at depth k which still contain points, one gets

σ∈L k (T ) c(σ) ≤ 2d n (γ + n σ ) • d2 d+1 (γ + 1) 2 C ,
which can be made as small as ε2dγ for an appropriate value of K. By Lemma 1, this implies that the cost of the non-empty leaves at depth k in T k is at most εc(T ). The leaves of T k at depth less than k also belong to T , and the same holds as well for the leaves at depth k which do not contain any point. Hence their total cost is at most c(T ) and the lemma follows for points.

C p-Greedy for points p∈S∩σ n p )λ d-1 (σ), where n p is the number of leaves of that subdivision that contain p. Since n p is at most 2 d , the latter cost is at most 8γ + |S ∩ σ|2 3-2d )λ d-1 (σ). If σ is a leaf of T (3-greedy) , this means that σ (opt) 3 is just the leaf σ, then certainly c(σ

(complete) 3 ) is greater than c(σ). Hence 8γ + |S ∩ σ|2 3-2d ≥ γ + |S ∩ σ|, i.e. |S ∩ σ| = 7 1-2 3-2d γ = C d .
The only case when the 3-greedy strategy fails, is when the lookahead says it is wrong to subdivide whereas it is not. In that case, the number of points is at most C d γ. Then the cost is at most (1 + C d )γλ d-1 (σ), and because of Lemma 1 this is O(M σ ), where M σ is the infimum cost of all the possible quadtree subdivisions of σ. Since lookahead only subdivides a cell if it has a subtree that actually improves the cost, necessarily T (3-greedy) ≺ T (opt) (where T (opt) is any optimal 4 tree). Thus every leaf σ of T (3-greedy) is a cell of T (opt) , and since c(σ) = O(M σ ) then c(T (3-greedy) ) = O(T (opt) ) = O(M ) as well. 4 The cost M is an infimum and may not be achieved by any finite-depth tree. But for this proof, T (opt) can be allowed to have infinite depth. Alternately, one may consider an increasing sequence of trees T (opt) k whose costs converge towards M .

Redoing the computation with lookahead k = 2 for d ≥ 3, we find that C d = 7 1-2 2-d , and the rest of the proof follows similarly. On the example given in that section, the separation criterion is near optimal. In fact, Aronov and Schiffenbauer (private communication) have also and independently proven that Q (AS-sep) (S) is near-optimal, where Q (AS-sep) uses a slightly different separation criterion: subdivide a cell whenever it covers more than one point of S, and also if any of its orthogonal (resp. diagonal) neighbors has depth which differs by more than 1 (resp. 2). Note that their construction is valid only if all the points in S are distinct.

Lemma 13. (Aronov,Schiffenbauer) Let S be a set of n points in the unit square, and let M be the infimum of c(Q) over all quadtrees Q. Then Q

(AS-sep) (S) is near-optimal, namely, c(Q (AS-sep) (S)) = O(M ).

D Rebalancing

The proof of the lemma 8 uses the concept of barrier [START_REF] Moore | Simplicial Mesh Generation with Applications[END_REF]. A barrier (depicted is a configuration of cells around a designated cell that guarantees that the designated cell never has to split to achieve balance. See Figure 2 for an example with a given quadtree. It is not hard to see that T contains the barrier of every leaf of T , and that the number of leaves of T is at most 3 d that of T . Proof. For a point, the worst case is when it falls exactly on the center of a cell: it then belongs to all the children of the subdivided cell, and thus its contribution to the object cost is at most doubled. Note that further subdivision will never increase that contribution.

The situation is more complicated for simplices, but we can prove that the contribution of an object within a leaf σ of T is never increased by more than a constant factor. The proof relies in that, when rebalancing, σ is only subdivided along its boundary, because only its neighbors can force it to subdivide. Thus, the subtree σ of σ in bal k (T ) must satisfy σ ≺ σ ∞ , where σ ∞ is the maximum subdivision of σ along its boundary (an infinite border). By the following lemma and appropriate scaling, the object cost λ d-1 (s ∩ bal k (T )) is at most B d λ d-1 (s ∩ T ). By construction, a k-side is made up of 2 d-1 half-scaled empty cells, 2 2(d-1) quarter-scale empty cells, and 2 2(d-1) quarter-scale (k -2)-sides. If the simplex intersects all the (k -2)-sides, then it cannot intersect the half-scaled empty cells, and it thus intersect only 2 d-1 half-scale (k -1)-sides, thus s k ≤ s k-1 (the factor 2 d-1 disappears because of scaling). On the other hand, if it misses any of the (k -2)-sides, then the object cost decreases geometrically (but it may intersect all the empty cells, of total measure 4d). More explicitly,

s k ≤ max s k-1 , 4d + 2 2d-2 -1 2 2d-2 s k-2 .
This recurrence shows that s k is bounded by S d = d4 d for all k.

We can then consider a border as the union of 2d2 d-1 half-scaled sides (the superpositions only increase the cost), so that the cost is at most d 2 2 2d-1 .

The constant B d thus obtained is larger than 3 d . A more careful case analysis of a depth three subdivision is too long to include here, but would show that B d can indeed be chosen less than 3 d , at least for d ≤ 3. The conjecture is

B d = 2 d-1 .
Remarks. 1 The constant 3 d in Lemma 8 is tight for the number of leaves, but not for the cost of 0-balanced trees. When considering k-balanced trees, k ≥ 1, it may be overly pessimistic. Indeed Moore shows that in the plane, 9 is tight for 0-balanced quadtrees, but 8 is tight for 1-balanced quadtrees.

2 Aronov and Schiffenbauer independently proved that for any quadtree Q (not necessarily balanced), there is a balanced quadtree Q such that c(Q ) = O(c(Q))Their construction may subdivide more than necessary.

Fig. 1 .

 1 Fig. 1. The k-side quadtree Q (side) k

  if we start from a cell σ instead of the unit cell): the algorithm starts with the complete tree T (complete) k

  does not improve the cost of the unsubdivided node σ, then the recursion terminates. Otherwise, we replace σ by the subtree σ (opt) k (S) and recursively evaluate the criterion for the leaves of σ (opt) k (S).

Lemma 6 .

 6 For every d and k, there exist constants C d (k) and S d (k) > 0 such that for any convex object s of dimension at most d -1, either s intersects at most C d (k) cells of the regular grid of side k, or else λ d-1 (s) ≥ S d (k). We may take C d (k) ≤ d 2 k d-2 and C 3 (k) = 7k -6.

Theorem 1 .

 1 Let T be a tree storing both points and/or simplices in the unit cube. Then for any k, 0 ≤ k < d, and d ≤ 3, c(bal k (T )) ≤ 3 d c(T ). The result becomes c(bal k (T )) = O(d 2 4 d )c(T ) in higher dimensions.

Lemma 12 . 3 .

 123 The 3-greedy strategy in the plane, and the 2-greedy strategy in d dimensions (d ≥ 3) produce near-optimal trees for points. Namely, if S be a set of n points in the unit d-cube, and M is the infimum of c(T ) over all trees T , then c(T (3-greedy) ) = O(M ) for all d ≥ 2, and c(T (2-greedy) ) = O(M ) for all d ≥ Proof. We prove that 3-greedy is near-optimal, for d ≥ 2. Then we indicate what changes for 2-greedy when d ≥ 3. The cost of a cell σ is (γ + |S ∩ σ|)λ 1 (σ). The cost of a complete subdivision σ

Fig. 2 .

 2 Fig. 2. Illustration of Lemma 8: A quadtree T (left) and its corresponding T (right).

Lemma 14 .

 14 Let T be a tree, and consider the object cost of a single object s ∈ S both in T and in balk (T ). If s is a point, then λ d-1 (s ∩ bal k (T )) ≤ 2λ d-1 (s ∩ T ). If s is a convex object of dimension at most d -1 (e.g. a (d -1)-simplex), then λ d-1 (s ∩ bal k (T )) ≤ B d λ d-1 (s ∩ T ).

Lemma 15 .

 15 The object cost of a flat object in any tree T ≺ T (border) ∞ is bounded by a constant 2dB d . Moreover, one can choose B d ≤ 3 d for d ≤ 3.Proof. We first prove the lemma for sides, then for borders. Let d be fixed, and let s k (resp. c k , b k ) be the maximum object cost of a simplex in T

In[START_REF] Aronov | Cost-driven octree construction schemes: an experimental study[END_REF], we show how to choose γ to reliably get the best cost possible.

Actually, they both yield octrees of same cost which are the lowest cost we observe with other heuristics; we find it hard to believe that they would all be c times optimal, for some constant c > 1.

Here, 'very close' means always within the cell incident to that vertex. It's then pointless to subdivide the other cells: since they do not contain points of S, their cost would be doubled.

Acknowledgments

This research was initiated at the McGill-INRIA Workshop on Computational Geometry in Computer Graphics, February 9-15, 2002, co-organized by H. Everett, S. Lazard, and S. Whitesides, and held at the Bellairs Research Institute of McGill University. We thank Robin Chapman of sci.math for providing reference [6]. Many thanks go to Boris Aronov for his very detailed comments, suggestions, and for interesting discussions.

Work on this paper has been supported by NSF ITR Grant CCR-0081964 and NSF CAREER Grant CCR-0133599. Work by the second author was performed while spending a semester at Polytechnic University, on leave from

Appendix

In this appendix, provided only for the reviewers, we include the missing proofs so that reviewers can examine the truths of our statements if they desire. We intend it only for the consideration of the reviewers and not as part of the submission.

A Examples of cost computation

As examples, we compute the cost of the same configurations as [START_REF] Brönnimann | Cost-optimal quadtrees for ray shooting[END_REF], but in any dimension d ≥ 2.

0. With no subdivision, the cost of the unit cell T (empty) is c(T (empty) ) = 2d(γ + n).

1. For points, the cost of a full subdivision at depth k,

) ) (this is the exact value if all the points fall in a single leaf of T (complete) k ; this happens if the binary expansions of all point coordinates always have at least k + 1 bits), and at most 2d(

2. As an exercise, the tree costs of the k-side, k-corner, and k-border, and more generally of the k-corner of order h can be computed readily by noting that a k-side is a half-scaled copy of 2 d-1 empty trees and 2 d-1 (k -1)-sides, that a corner is made of di half-scaled k-corners of order i, for every 0 ≤ i ≤ d -1, and that a k-border is made of 2 d half-scaled (k -1)-corners: 3. Let S n denote n distinct points very close to one corner of the unit cell, let's say the origin. After k levels of recursively subdividing the incident cell, 3 we obtain the tree

Whether this is an improvement over T (empty) for any value of k depends on n and γ. In particular, T

k (S n ) has cost lower than the unsubdivided tree for large values of k only if n > 2γ in 2D, and n > 4 3 γ in 3D (n

This example tells us that whether subdivision strategies based on the number of objects in a cell-like the separation criterion-produce optimal or nearoptimal trees, depends strongly on the value of γ.