Efficient method of adaptive sign detection for 4x4 determinants using a standard arithmetic processing unit
We propose an efficient and exact method for the adaptive sign detection of 4x4 determinants using a standard arithmetic unit. The entities of determinants are variable length integers (integers of arbitrary bit length). The integers are expressed in 16-bit data units, and the sign detection is reduced to the computation of 4x4 determinants of 16-bit integers. To accelerate the computation, the calculation is performed by using a standard arithmetic unit. We have implemented our method and confirmed that it significantly improves the computation time of 4x4 determinants. The method can be applicable to many geometric algorithms that need the exact sign evaluation of 4x4 determinants, especially to construct robust geometric algorithms.
geometric algorithm solid modeling boolean set operation exact integer arithmetic