Title

Topologically Exact Evaluation Of Polyhedra Defined In Csg With Loose Primitives

Keywords

Constructive solid geometry; Half-spaces; Loose primitives; Polyhedra; Robust boundary evaluation; Solid modelling

Abstract

Floating point round-off causes erroneous and inconsistent decisions in geometric modelling algorithms. These errors lead to the generation of topologically invalid boundary models for CSG objects and significantly reduce the reliability of CAD applications. Previously known methods that guarantee topological consistency by relying on arbitrary precision rational arithmetic or on symbol-manipulation techniques are too expensive for practical purposes. This paper presents a new solution which takes as input a "fixed precision" regularized Boolean combination of linear half-spaces and produces a polyhedral boundary model that has the exact topology of the corresponding solid. Each half-space is represented by four homogeneous coefficients in fixed precision format (La bits for the three direction cosines and Ld bits for the constant term, i.e. the distance from the origin). Exact answers to all topological and ordering questions are computed using a fixed length, 3 La, + Ld + 2 bits, integer format. This new guaranteed tight limit on the number of bits necessary for performing intermediate calculations is achieved by expressing all of the topological decisions based on geometric computations in terms of the signs of 4 by 4 determinants of the input coefficients. The coordinates of intersection vertices are not required for making the correct topological decisions and hence vertices and lines are represented implicitly in terms of planes.

Publication Date

1-1-1996

Publication Title

Computer Graphics Forum

Volume

15

Issue

4

Number of Pages

205-217

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1111/1467-8659.1540205

Socpus ID

0030257970 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0030257970

This document is currently not available here.

Share

COinS