Search
Close this search box.

Improved Output-Sensitive Construction of Vertical Decompositions of Triangles in 3D

Abstract

Improved Output-Sensitive Construction of Vertical Decompositions of Triangles in 3D

This work deals with vertical decompositions of n triangles in three-dimensional space. We describe a new decomposition scheme for triangles in three-dimensional space which in most cases produces less cells than the standard vertical decomposition. A cell in this decomposition might have complexity \(\theta (n)\), however each of the cells is convex. We show by experiments that in practice our new scheme is more favorable than the standard vertical decomposition.We give a deterministic output-sensitive algorithm for computing the standard decomposition that runs in \(O(n \log^2 n + V \log n)\), where \(V\) is the complexity of the decomposition. This is a significant improvement over the best previously known algorithm whose running time is \(O(n^2 \log n + V \log n)\). We also give a deterministic output-sensitive algorithm for computing the new decomposition we describe that runs in \(O(n \log^2 n + V \log n)\), where \(V\) is the complexity of the decomposition.

We implemented the two algorithms and ran them on a series of scenes. We ran programs that use decompositions for their calculations and tried them on the output of the two decompositions. Our results show that programs usually benefit from the new decomposition we propose here. Our algorithms make use of a dynamic point location data structure. By using a trivial point location in restricted number of places, the algorithms become very simple and effective (in particular they perform only a space sweep, and all the computations are done in two dimensions on the sweep plane).

We also show how to extend these algorithms to the case of a vertical decomposition of polyhedral surfaces. We implemented these extensions as well.

Additional Information & Links

 

Contacts

Hayim Shaul 
inproceedings{sh-icvdt-02, 
  author = {Haim Shaul and Dan Halperin},
  title = {Improved Construction of Vertical Decompositions of {3D} Arrangements},
  booktitle = {Proceedings of the 18th {ACM} Symposium on Computational Geometry ({SoCG}),
  year = {2002},
  pages = {283--292},
  doi = {10.1145/513400.513437}
} 

@masterthesis{s-ioscv-01},
  author       = {Haim Shaul}, 
  title        = {Improved Output-Sensitive Constructon of Vertical Decompositions of Triangles in three-Dimensional Space}, 
  type         = {{M}.{S}c. Thesis},
  school       = {The Blavatnik School of Computer Science, Tel-Aviv University},
  year         = {2023}
}

Vertical Decompositions of Triangles in 3D – Exact Computation

Improved Output-Sensitive Construction of Vertical Decompositions of Triangles in 3D
Exact computation considiration
We use the kernel layer of the CGAL library, which provides us with basic classes such as point, line, segment and triangle. The type of numbers we use was left as a parameter that can be decided in compilation time. We use the LEDA library which provides rational numbers, a class that represents an exact value of a rational number and allows operations on it.Exact Computation
LEDA’s rational numbers class represents a rational by maintaining a numerator and a denominator, which are multi-precision integers. Operations on LEDA’s rational might double the bit-length of the numerator and the denominator. Having a big numerator or denominator induces more processing time for the computation of operations. LEDA, therefore, introduced a “normalize” function which divides the numerator and denominator by the largest common denominator and by that reduces the bit-length of the numbers. In practice, however, division by the largest common denominator does not reduce the bit-length significantly. In theory, the worst case might be that every operation doubles the bit-length of the number. We can assume an adversary that perturbs the input to choose numbers so results of operations we perform cannot be “normalize”.The time it takes to calculate an operation on two LEDA rationals is proportional to the bit-length of the numerator and the denominator. This introduces a new consideration in analyzing the running time of an algorithm. More “complex” numbers take more time to calculate.

We say that a number is of depth 1 if it is a number that comes from the input of the algorithm. We say that a number is of depth-(n+m) if it is a result of an operation on two numbers of depths n and m. Notice that the bit length of the representation of a number of depth i is θ(2^i). The depth of an algorithm is the maximum depth of the numbers it uses. An algorithm with greater depth will generate numbers with higher bit-lengths, and thus will take more time compute.

The implementation of the partial decomposition uses 11 number types:

  • The coordinates of corners of triangles.
  • The coordinates of endpoints of intersection edges.
  • The coordinates of the event point where two boundary edges are vertically visible.
  • The coordinates of the event point where an intersection edge and a boundary edge are vertically visible.
  • The coordinates of the event point where three triangles intersect.
  • The coordinates of a feature of a vertical wall W(p, T’), where the feature comes from a boundary edge, and the point p is a corner of a triangle.
  • The coordinates of a feature of a vertical wall W(p, T’), where the feature comes from a boundary edge, and the point p is the event point where two boundary edges are vertically visible.
  • The coordinates of a feature of a vertical wall W(p, T’), where the feature comes from a boundary edge, and the point p is the event point where a boundary edge and an intersection edge are vertically visible.
  • The coordinates of a feature of a vertical wall W(p, T’), where the feature comes from a boundary edge, and the point p is the event point where three triangles intersect.
  • The coordinates of a feature of a vertical wall W(p, T’), where the feature comes from an intersection edge, and the point p is a corner of a triangle.
  • The coordinates of a feature of a vertical wall W(p, T’), where the feature comes from an intersection edge, and the point p is the event point where two boundary edges are vertically visible.
  • The coordinates of a feature of a vertical wall W(p, T’), where the feature comes from an intersection edge, and the point p is the event point where a boundary edge and an intersection edge are vertically visible.
  • The coordinates of a feature of a vertical wall W(p, T’), where the feature comes from an intersection edge, and the point p is the event point where three triangles intersect.

The implementation of the full decomposition uses 3 additional number types:

  • The coordinates of the event point where two intersection edges are vertically visible.
  • The coordinates of a feature of a vertical wall W(p, T’), where the feature comes from a boundary edge, and the point p is the event point where two intersection edges are vertically visible.
  • The coordinates of a feature of a vertical wall W(p, T’), where the feature comes from an intersection edge, and the point p is the event point where two intersection edges are vertically visible.The depth of calculation of points that are a result of events where two intersection edges are vertically visible is very large. Hence the full decomposition is more prone to robustness problems with imprecise arithmetic or to more time-consuming calculations when using exact arithmetic. Furthermore, programs that use the full decomposition suffer from the same problem.

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
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 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.

Average time in seconds to compute ten paths between ten pairs of point
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

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content