Exact Computation for Robust 3D Polyhedral Interactive Modeling

This article introduces how an exact computation library based on rational arithmetic has been used in a polyhedral modeler based on face shifts and topological event detection. The goal of the use of exact computation is to get rid of the imprecision in the geometrical predicates computations, and thus to avoid false positives and false negatives in the topological events detection. This article also presents two algorithms which transform a polyhedral mesh with an approximated geometry (a mesh with faces which does not co-intersect in one point) into a mesh with the same structure, but with a non-Approximate geometry. This is, to our knowledge, the first attempt to use rational arithmetic in a polyhedral modeler to manage the geometrical data. The reasons why rational arithmetic has not been used before are the memory consumption that it can generate, but also the fact that to keep an absolute precision, some operators and functions can not be used (square root, logarithm, trigonometric functions, etc.) and finally the fact that all data are produced using floating-point arithmetic, and so that data should be corrected before use. This article explains how all these issues have been handled.