Vertical Decompositions of Triangles in 3D  Experiments
Improved OutputSensitive Construction of Vertical Decompositions of Triangles in 3D
Experiments
comparing the construction of the partial decomposition and the full decomposition
We tested both the partial and the full decomposition on eight input scenes, which are depicted in the following figures. All out tests were done on a computer with a Celeron 400Mhz CPU and 512 MByte RAM. Our experiments show that the partial decomposition proves itself more efficient in solving two problems we tested.
Test case 1 consists of two sets of n/2 triangles each.
The triangles are
laid in a grid so each triangle in one set intersects the n/2 triangles of the
other set, Thus the scene has
θ(n^2) intersections.
The partial decomposition should perform better in a scene which has a
lot of intersections. However, since the triangles are laid in a grid
the cells of the partial decomposition are much bigger
than the cells of the full decomposition.
Test case 2 consists of a ``ring'' of triangles.
The partial decomposition
creates a few large cells in the middle of the ring. The partial
decomposition is expected to perform better than the full decomposition
because of these large cells.
Test case 3 consists of two big triangles,
whose intersection is then
intersected by n2 triangles. The intersections of boundary edges
with the two big triangles creates floods in the partial decomposition
which do not exist in the full decomposition. These floods cause one
cell of the full decomposition to be divided among many cells in the
partial decomposition, although the number of cells will be smaller
in the partial decomposition
Test case 4 demonstrates the worst case complexity of the partial decomposition as suggested to us by Boris Aronov. Here n/3 triangles α = α_{1},...,α_{n/3} intersect each other to form a convex ceiling, n/3 triangles β = β_{1},...,β_{n/3} lie beneath the ceiling such that the projections of these triangles on the xyplane do not intersect, and n/3, long and skinny triangles γ = γ_{1},...,γ_{n/3} parallel to the xaxis that stab the triangles in β.
There are θ(n^2) intersections, each between a boundary edge of a triangle in β and a triangle in γ. We arrange the triangles in β such that all these intersection points have distinct xcoordinates. Each of these intersection points induces a flood wall with complexity θ(n), since it meets all the triangles in α. Thus the total complexity of all the flood wall is θ(n^3).
The full decomposition has a better
complexity, although it has more cells. Applications using a vertical decomposition
performed better with the partial decomposition.
Test case 5 consists of pyramids built recursively
inside pyramids.
Test case 6 consists of a scene where an
intersection of three triangles
is vertically visible with another intersection of other three triangles.
Test case 7 consists of a scene where quadruples of triangles are laid one above the other. None of the triangles are intersecting, but boundary edge are vertically visible. This scene shows that the partial decomposition is more economical than the full decomposition even in a scene with no intersections. The savings in this case would come from the way vertical visibility of boundary edges are handled. Recall that the full decomposition erects a wall W(p, T') from every event point p, in addition to walls erected from every boundary edge, every intersection edge and every triangle corner. The partial decomposition erects walls only from boundary edges, triangle corners and intersection points. This means that in an event where two boundary edges are vertically visible the full decomposition erects a wall which the partial decomposition does not, thus splitting a cell.
Test case 8 consists of a ``stack'' of triangles laid one above the other. None of the triangles are intersecting, and each boundary edge is vertically visible with only two other boundary edges, one from below and one from above. This scene shows that the partial decomposition is more economical than the full decomposition even in a scene with no intersections and little vertical visibility between edges. The savings in this case would come from the way middle corners of triangles are handled. In the full decomposition we erect a wall W(p, T') from every corner of each triangle, whereas in the partial decomposition we erect a wall W(p, T') from the first corner and the last corner of every triangle and half a wall W_l(p, T') or W_r(p, T') from the middle point of every triangle. The full decomposition adds half a wall at such event that the partial decomposition does not.
For each scene we computed the complexity of each decomposition. In the full decomposition we simply counted the number of cells. Since each cell in the full vertical decomposition has constant complexity it is sufficient to count the number of cells to know the complexity of the arrangement up to a small constant factor. In the partial vertical decomposition we counted the complexity of all the floors and ceilings and all the vertical walls. We counted the total complexity of all floors and ceilings by summing up the number of triangles in the floor and ceiling of all the cells. We write this as \sum_i ic_i where c_i is the number of cells that have a total of i triangles in their floor and ceiling.
Similarly we counted the total complexity of all vertical walls by counting the number of vertical walls in each cell, and then summing up these numbers. We write this as \sum_i iw_i where w_i is the number of cells that have a total of i vertical walls. Note that this notation is simply a compact way to write how many cells have a certain number of walls or ceilings.
The results in the following table (here).
indicate that the partial
decomposition is more
economical than the full decomposition. One may suspect that because we
invest less time in preprocessing, using the decomposition to solve problems
will be more costly. We next show by experiments on two different problems
that this is not the case. The opposite is true: the partial decomposition
proves itself more efficient in solving these problems.
Scene No.  Time to complete full decomp. (In sec.) 
Time to complete partial decomp. (In sec.) 
# of cells in full decomp.  # of cells in partial decomp.  Complx. of walls  Complx. of floors and ceilings 

1  452  346  2630  1210  1*174 + 2*615 + 3*348 + 4*71 + 5*2 
2*898 + 3*254 + 4*58 
2  42809  42426  230  131  0*4 + 1*19 + 2*63 + 3*34 + 4*9 + 5*2 
2*94 + 3*30 + 4*5 + 5*2 
3  7595  4985  6050  2803  0*196 + 1*472 + 2*1550 + 3*530 + 4*55 
2*1471 + 3*1064 + 4*268 
4  149069  127070  2356  1170  0*27 + 1*247 + 2*498 + 3*332 + 4*63 + 5*2 + 7*1 
2*753 + 3*347 + 4*50 + 5*4 + 6*4 + 7*12 
5  208259  144687  768  294  0*27 + 1*90 + 2*145 + 3*28 + 4*4 
2*126 + 3*106 + 4*47 + 5*14 + 6*1 
6  4350  3743  110  59  1*2 + 2*30 + 3*17 + 4*9 + 5*1 
2*53 + 3*5 + 4*1 
7  2068  942  7922  2971  2*322 + 3*881 + 4*1383 + 5*237 + 6*148 
2*2971 
8  1967  1963  2096  1199  2*601 + 3*300 + 4*298 
2*1199 
comparing volume calculation on the output of the two decompositions
We have computed the volume of the arrangement in order to see that the decomposition is correct. The time it took to calculate these volumes is given in the followin table (here).
In order to calculate the volume of a cell we defined some artificial floor.
We calculated the volume between the floor of the cell and the artificial floor,
and the volume of the ceiling of the cell and the artificial floor. The
volume of the cell is the difference between the two volumes. This way gives
advantage to the partial decomposition since we do not overlay the map of
the ceiling with the map of the floor. This overlay produces more complex
numbers. On the other hand the
partial decomposition, as opposed to the full decomposition, needs to
partition the ceiling (floor) to cylinders that have constant description.
This partitioning is very expensive since we need to find the corners and
edges that appear in the ceiling (floor). It is possible that adding more
information to the output representation, such as the event points at which
the cell's boundary was created, would improve the partial decomposition.
Notice that although all of the scenes had less cells in the partial
decomposition, most of them had a considerable amount of complex cells
(cells with a large number of triangles in the ceiling, floor or in the
walls) and indeed in most of the scenes computing the volumes took roughly the
same time using both decompositions (with the full
decomposition being even slightly superior).
The only exceptions are scenes 1 and 3 where the partial
decomposition was significantly faster. Indeed the cells in the partial
decomposition of scenes 1 and 3 are not very complex, in the sense that they do
not have many triangles in their ceiling, floor and walls.
Scene No.  Full Decomposition  Partial Decomposition 

1  7263  2720 
2  149242  144784 
3  346307  150133 
4  740395  754799 
5  308520  421512 
6  130904  182949 
7  347463  360315 
8  603  568 
finding a free path between a pair of points on the output of the two decompositions
We also performed a test in which we chose two points in \reals^3 and calculated a path between those two points that does not intersect any triangle.The points were chosen randomly from some bounding box that contain all the triangles in the scene. We searched for the starting node and the target node by checking for each cell if the points are contained in it.
Most of the computation time is spent on finding the nodes in the graph that contain the two points. We find these cells by checking every cell if it contains one of the points. Recall that the description of a cell actually consists of half spaces, when the cell is the intersection of them. Checking if a cell contains a a point is done by checking if the point is contained in each of these half spaces. Since the partial decomposition produces less cells, it is often the case that it takes less time to locate the relevant cells, although they are more complex.
In some cases, the full decomposition was faster than the partial decomposition. This is because the search terminates when the two cells are found. If the cells we search for are in the beginning of the full decomposition cell list, it would be found sooner.

Full Vertical Decomposition  Partial Vertical Decomposition  

Test No. 
Average # of cells in path 
Average time to calculate the path 
Average # of cells in path 
Average time to calculate the 
1  12.3  0.86  9  0.29 
2  4.4  0.012  3.7  0.012 
3  14.2  5.68  17.9  0.79 
4  6.3  1.00  4.8  0.392 
5  4.2  0.286  3  0.0065 
6  4.2  0.0125  3.4  0.0313 
7  7  12.39  4.9  3.471 
8  33.4  0.083  33.4  0.1021 