##### Personal tools
You are here: Home Vertical Decompositions of Triangles in 3D - Experiments
« November 2021 »
November
SuMoTuWeThFrSa
123456
78910111213
14151617181920
21222324252627
282930

# Vertical Decompositions of Triangles in 3D - Experiments

### Improved Output-Sensitive 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 n-2 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 xy-plane do not intersect, and n/3, long and skinny triangles γ = γ1,...,γn/3 parallel to the x-axis 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 x-coordinates. 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.

Complexity of vertical decompositions, scenes 5 -- 8
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.

Time in seconds to compute the volume of all the cells in the decompositions
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 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