Filling Objects with Balloons

Urs Bischoff Bas Schopman James Vanderhyde
urs@cc.gatech.edu gtg458t@mail.gatech.edu jamesv@cc.gatech.edu

Abstract

Many hierarchical data structures are based on spheres. They are especially useful for collision detection and visibility problems. We present an algorithm that fills a watertight object with spheres (we call them balloons). This sphere model should not only be seen as a data structure for the two previously mentioned applications, but also as a new representation of 3D objects. Our representation can be used for progressive transmission, because some big balloons can already convey useful information about the basic shape of the object. By adding smaller spheres we can progressively refine the model. By varying the balloon size, we can even extract some features of the model; for example, bigger balloons are only present in big hollow areas of the object. Our approach is based on a greedy algorithm that chooses a start position for a new balloon and then grows the balloon until it is blocked between the boundaries of the object. This process is continued until the whole object is filled with balloons. We chose a voxel space as an initial data structure of our model. In this data structure we chose a voxel that lies inside the boundaries as a start position for growing a balloon. Growing a balloon means growing a cube. Our algorithm is based on simple rules of how a balloon can be grown and blocked: a balloon can be grown into eight different directions (diagonal directions) and six different faces can be blocked. As soon as two opposite faces are blocked, the balloon is blocked and we start a new balloon. We tested several methods for choosing a start voxel and choosing growing directions. We found that sorting the voxels by distance to the boundary and choosing the voxel with largest distance as start voxel works best. We also show that choosing random growing directions works best for our requirements. We compare the different approaches with quality measure that counts the number of balloons needed to convey the same visual information.

1 Introduction

In this paper we present a method to fill a geometric object with spheres. Spheres are widely used in computer graphics in hierarchical data structures to organize smaller geometric primitives (e.g. points, triangles etc.). The advantage of spheres over other primitives or data structures is its simple representation. As opposed to other data structures such as octrees, which are fixed to the space, a sphere data structure that collects smaller primitives is fixed to the geometric objects; thus, spheres are very useful when we have transformation (e.g. in animations), because the data structure can be consistently and efficiently transformed with the geometric model. Spheres also allow cheap intersection tests, which makes it a popular tool for collision detection and visibility problems.

Besides the applicability for collision and visibility detection, we identified other important useful applications for our approach. The data structure we present can be used as a new representation of geometric models for progressive transmission and as a tool for feature extraction.

Our idea is to fill a geometric (watertight) object with spheres (or balloons as we call them); the size of the balloons should be maximized. Thus, big hollow areas should be filled with big balloons, while smaller features are filled with smaller balloons. Our approach is based on a greedy algorithm; it chooses a start position inside the objects and then grows the balloon until it is blocked by the boundary of the object. Then, it chooses the next start position and grows the next balloon. This process is repeated until the object is filled with balloons. Because we use a voxel representation of our object, the smallest balloon size is limited by the size of a single voxel.

In this paper we present our main algorithm. We describe how we choose a start position for a new balloon and how the balloon is grown. We implemented several slightly different methods of choosing a start position and growing a balloon. We implemented two different methods for choosing a start position: in one version we choose an initial position that is farthest away from the boundary, and in another version we just choose start positions in order of the voxels in the voxel space. We also present two different growing methods: a randomized and a non-randomized one.

2 Related Work

Our approach has some similarities to bounding sphere hierarchies, such as the one used in QSplat [1] for rendering at various resolutions and the sphere tree used by Gareth Bradshaw and Carol O’Sullivan for the purposes of collision detection [2]. Such approaches have a sequence of sphere sets, where each set progressively approximates the object more closely, and the union of the spheres in each set is a subset of the union in the previous set. Since we are considering spheres under the l-infinity norm, our spheres are really cubes, and so our technique also bears some resemblance to hierarchical linear partitions of space such as octrees [3]. The main difference between our approach and these others is that we have no hierarchy, even though the object is approximated first by large objects and then progressively by smaller object, so there is no extra overhead.

3 Approach

Our algorithm is based on growing balloons (in the shape of cubes, they are spheres in the l-infinity norm) in diagonal directions. There are 8 diagonal directions for a single balloon. Our data consists of voxels, which have two flags: inside and blocking. We first compute for each voxel the distance to the boundary of the object. The distance is positive outside the object and negative inside the object. We have two methods for choosing a start voxel for growing a balloon: we sort the voxels by the distance to the boundary of the object, or we traverse voxel space in a regular manner (by incrementing x, y, and z coordinates, where x grows the fastest). Before we start any growing we mark all the voxels that are outside as blocking.

First, we describe how we grow a balloon. Then, we show two methods for choice of start voxel and two methods for choice of a next free growing direction.

3.1 Growing

We grow our balloons in diagonal directions (8 possible diagonal directions in three dimensions). We do this because then only three faces of the balloon are affected by the growth, which makes checking and growing easier. For the current diagonal direction we check the x, y, and z face voxels. If they are all unblocked, we set the voxels in the faces as blocking and grow the balloon to that size. Thus the diameter of the balloon grows by one voxel width at a time. After each growth step we check whether the balloon can grow any further. If there is a blocking voxel in one of the faces, we record the direction of that face as blocked and find a new free diagonal direction. A balloon stops growing when it is completely blocked—when two opposite faces are blocked. This can occur after two or three faces are blocked, and must occur by the time four faces are blocked. In Figure 1 one growing step for the corresponding 2D case is depicted; the red squares mark the new voxels that belong to the balloon.

3.2 Sorted vs. Unsorted

In the case of unsorted voxels, the starting voxel is the first voxel that is not marked blocking in the original data. “Unsorted” means that we use the natural (scan line) order of voxels in the voxel space. The first voxel is always a voxel on the boundary of the object. When the balloon of the starting voxel is completely blocked, we go to next non-blocking voxel and start a new balloon.

In the case of sorted voxels, we sort them at the beginning by their distance to the boundary of the object. So the voxel with the lowest value will be our starting point (voxels that are inside the object have negative value). Again when the balloon of the starting voxel is completely blocked, we go to next non-blocking voxel and start a new balloon.

3.3 Random vs. Not Random

We implemented two methods for selecting the next free diagonal growing direction: a random and a deterministic method. The possible free growing directions are somewhat determined by which faces are blocked. Any time we have a choice, we either choose a new direction at random or in a predetermined fashion. In our coordinate system a direction is represented by a vector with three components. Because a growing direction is always diagonal, each component is either 1 or -1, but not 0. When we choose a new direction randomly, we randomly select 1 or -1 for the components of the new growing direction. When we do not employ the random method, we always select 1.

Figure 1: Growing in 2D

4 Results

Four different methods have been implemented; the changing parameters are whether we sort the voxels by distance to the boundary and whether we choose random or determined growing directions. Thus, we implemented the following: not sorted and not random, not sorted and random, sorted and not random, sorted and random. The charts and tables correspond to execution of the algorithm on the feline model.

Figure 2 shows a curve for each technique that represents how much information is sent over time. We use the number of balloons sent to indicate transmission time, since each balloon requires a constant number of bits. (A balloon consists of a center and a radius; since we are operating in a quantized space this is 4 integer values, quantization value B bits per integer. We use 16 in Table 2.) We use the number of voxels contained in the transmitted balloons as a measure of closeness to the original shape. Thus sending the voxel data directly would be a straight line on this graph. The goal is a steep curve that increases quickly at the beginning; therefore we conclude that the sorted random technique is the most effective.

Figure 3 shows the number of balloons of each diameter (measured in voxel widths) constructed by each technique. The not sorted, not random and the sorted, random techniques have the fewest balloons total. There are many balloons of diameter greater than 7, but the do not show up non-trivially on the graph. Table 1 shows execution times; note that the sorting takes considerable time, but the time also depends on the number of balloons constructed.

Figure 2: Transmission time vs. quality

Figure 3: Balloon Diameter Histogram

Method

Execution Time

Sorted Not Random

83.95s

Sorted Random

79.15 s

Unsorted Random

14.83 s

Unsorted Not Random

10.43 s

Table 1: Execution times for the Feline model

Method

Balloons

Bytes

Savings (x:1 compression)

Bits/voxel

ns, nr

433713

3469708

1.2272

0.8148

ns, r

915791

7326332

0.5812

1.7205

s, nr

1086674

8693396

0.4898

2.0416

s, r

543116

4344932

0.9800

1.0204

voxels

34065528

4258191

1

1

Table 2: Memory Requirements

eight_sr_4592_cube_pink eight_sr_24_inscr

Figure 4. A figure eight. The original voxel dataset and an early approximation using only 24 balloons (192 bytes).

feline_nsnr_37_cube feline_nsnr_114_cube feline_nsnr_674_cube feline_nsnr_154202_cube
feline_sr_30_cube feline_sr_117_cube feline_sr_683_cube feline_sr_37540_cube

Figure 5. Progressive transmission of the feline model using the unsorted, unrandomized procedure (top) and the sorted, randomized procedure (bottom). For the first three from left to right, the number of balloons in each is about 35, 115, and 680, and the far right picture for each is all but the diameter-1 balloons.

feline_sr_00092_circum_pink feline_sr_00340_circum_pink feline_sr_02615_circum_pink feline_sr_04998_circum_pink feline_sr_11795_circum_pink

Figure 6. Progressive transmission of the feline model, viewed using spheres circumscribing the balloons.

feline_sr_543116_cube

Figure 7. The feline model after transmission of all balloons.

5 Conclusions

Because we want to have a data structure that allows for progressive transmission, the overall memory requirements are not as important as being able to transmit a coarse model with as few bytes as possible. In Figure 2 you can see that we need, especially at the beginning, to transmit fewer balloons with our sorted random method. The reason for this can be seen in Figure 3: in the sorted random method we get many more bigger balloons than in the other methods. However, because we have some big balloons, a lot of really small balloons are needed to fill the gaps. That is the reason we need to transmit more balloons with the sorted random method than for example unsorted non-random method. In the unsorted non-random method the size of the balloons does not vary much, thus fewer balloons are needed to represent the whole object. Because an approximation of the object can be represented by fewer balloons with the sorted random method, we prefer this method for our requirements. In Figure 5 you can see a comparison between these two methods. Note that after only a few balloons we already have a good visual representation of the head and body. However, if only the time to transmit the whole object mattered, we would have to choose the non-sorted non-random method, because fewest balloons are needed; in Figure 2 you can see that the least number of balloons are needed to transmit the whole model when using the non-sorting non-random method.

Table 2 shows the memory requirements of the different methods. Only the non-sorting non-randomized method requires fewer bytes than the initial representation as voxels. Our choice, sorting and randomized, requires slightly more bytes; however with fewer bytes we represent more visual information about the model than the pure voxel representation. As stated above, fewer balloons convey more information than the same number of voxels do.

In Table 1 the execution time to compute our representation is shown. The sorting of the data adds significant execution time. However, it is also interesting to see that the non-random method performs better when the voxels are unsorted. We think this has to do with the fact that the balloons grow in the same direction as the direction we traverse the voxel space. For curved surfaces, some of the surface can fill in and leave room for more larger balloons. The randomized version leaves too many gaps when the voxels are not sorted.

6 Future Work

We have a couple of ideas for future work to improve or extend our approach: adding a skin to the balloons, choosing intelligent growing directions, updating and re-sorting the distance field, and comparison to an octree.

To improve the reconstructed surface of the object, we could try to attach a skin stretching along the balloons. Using this method we could reconstruct a smoother surface. In a progressive transmission, the first few balloons are generally disconnected (depending on the object); using a skin it could be even possible to connect the balloon surfaces to one connected surface. How to decide which balloons should be connected is not exactly clear, but it is an interesting question.

We implemented two different approaches for choosing a new unblocked growing direction, a randomized and a deterministic. As mentioned earlier, we got better results by using random directions. Instead of choosing the directions randomly, it may be better to choose the new direction in some way so that the balloons grow in the best directions first. As we can see from the results, how the direction is chosen is significant. So if in some way we could decide which one of the unblocked directions is better, the algorithm could improve.

Updating the distance field is the main idea to improve our algorithm. Currently we only sort the voxels at the beginning, based on the original distance field. Our start voxels are those voxels with the originally smallest values. However, when a balloon has been grown and cannot grow any further, the next best point to start is normally not the next non-blocking voxel from the original sorted data, because that voxel could be quite close to the previous balloon. So, if we recalculate the distance field after each balloon (by including the balloon as a new boundary), the algorithm could significantly improve.

We also would like to compare our representation to an octree representation. The advantage of our approach is that we are not limited to a regular structure, which we normally have in an octree, and we do not have the overhead of a hierarchy. However, it would be interesting to compare the quality of the progressive transmission of the two techniques.

7 References

[1] S. Rusinkiewicz and M. Levoy. “QSplat: A Multiresolution Point Rendering System for Large Meshes.” In Computer Graphics, SIGGRAPH 2000 Proceedings, pages 343–352. Los Angeles, CA, July 2000.

[2] G. Bradshaw and C. O’Sullivan. “Sphere-Tree Construction using Medial-Axis Approximation.” ACM SIGGRAPH Symposium on Computer Animation SCA 2002.

[3] H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990.

8 Files

The code

More screenshots

Sample .v file (byte order used by Intel processors)