Personal tools
You are here: Home Projects In-house Projects Vertical Decompositions of Triangles in 3D Vertical Decompositions of Triangles in 3D - Exact Computation
« December 2021 »
December
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
262728293031
Log in


Forgot your password?
 

Vertical Decompositions of Triangles in 3D - Exact Computation

[Vertical Decomposition]

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.

[Projects Page] [Vertical Decomposition] [Top]
Document Actions