Exact boundary evaluation for curved solids

In this dissertation, I describe an algorithm for exact boundary evaluation for curved solids. I prove the thesis that accurate boundary evaluation for low-degree curved solids can be performed efficiently using exact computation.; Specifically, I propose exact representations for surfaces, patches, curves, and points. All of the common and standard CSG primitives can be modeled exactly by these representations. I describe kernel operations that provide efficient and exact basic operations on the representations. The kernel operations include new algorithms for curve-curve intersection, curve topology, point generation, and point location. The representations and kernel operations form the basis for the exact boundary evaluation algorithm. I describe each step of the boundary evaluation algorithm in detail.; I propose speedups that increase the efficiency of the boundary evaluation algorithm while maintaining exactness. Speedups fall into several categories, including methods based on lazy evaluation, quick rejection, simplified computation, and incorporation of hardware-supported floating-point methods. I also describe the types of degeneracies that can arise in boundary evaluation and perform a preliminary analysis of methods for eliminating degeneracies.; The representations, kernel operations, boundary evaluation algorithm, and speedups have been implemented in an exact boundary evaluation system, ESOLID, that exactly converts CSG models specified by the Army Research Lab's BRL-CAD system to B-rep models. ESOLID has been applied to a model of the Bradley Fighting Vehicle (provided courtesy of the Army Research Lab). I present results and analysis of ESOLID's performance on data from that model. ESOLID evaluates the exact boundary of Bradley data at speeds less than 1–2 orders of magnitude slower than a similar but inexact boundary evaluation system. ESOLID also correctly evaluates boundaries of objects on which this other system fails.