Patent ID: 7075532

Claim:
A method for preventing spurious intersections in a tetrahedralization of a three-dimensional (3-D) solid object representation due to round-off effects, comprising the steps of: a) inputting the 3-D solid object representation with a first order precision with a given limit on the first order precision; b) performing the tetrahedralization of said 3-D solid object representation with a second order precision with a given limit, where in said limit on said second order precision being greater than said limit on said first order precision, said tetrahedralization generating a plurality of tetrahedra approximating said 3-D solid object representation; c) identifying from the plurality of tetrahedra the tetrahedra showing potential spurious intersections by means of a vertex vicinity region test; wherein said vertex vicinity test comprises identifying at least one vertex which when rounded to said first order precision intersects at least one face of said tetrahedralization; d) replacing the identified tetrahedra displaying the potential spurious intersections with other tetrahedra that are devoid of spurious intersections; e) converting all of said tetrahedra created by said tetrahedralization from said second order precision to said first order precision; f) identifying from the plurality of tetrahedra the tetrahedra showing potential spurious intersections between at least two tetrahedra from said plurality of tetrahedra by means of an edge vicinity region test, where, said edge vicinity test comprising of identifying at least two edges which when rounded to said first order precision intersects with each other; g) replacing the identified tetrahedra displaying the potential spurious intersections using said edge vicinity test with other tetrahedra that are devoid of spurious intersections; h) converting all of said tetrahedra created by said tetrahedralization from said second order precision to said first order precision; and i) outputting with said first order precision said 3-D solid object representation consisting of tetrahedra devoid of spurious intersections.