The intersection of two ringed surfaces and some related problems

Abstract

We present an efficient and robust algorithm to compute the intersection curve of two ringed surfaces, each being the sweep UuCu generated by a moving circle. Given two ringed surfaces boolean ORuC1u and boolean ORvC2v we formulate the condition C-1(u) boolean AND C-2(v) not equal 0 (i.e., that the intersection of the two circles C-1(u) and C-2(v) is nonempty) as a bivariate equation lambda(u, v) = 0 of relatively low degree. Except for redundant solutions and degenerate cases, there is a rational map from each solution of lambda(u, v) = 0 to the intersection point C-1(u) boolean AND C-2(v). Thus it is trivial to construct the intersection curve once we have computed the zero-set of lambda(u, v) = 0. We also analyze exceptional cases and consider how to construct the corresponding intersection curves. A similar approach produces an efficient algorithm for the intersection of a ringed surface and a ruled surface. which can play an important role in accelerating the ray-tracing of ringed surfaces. Surfaces of linear extrusion and surfaces of revolution reduce their respective intersection algorithms to simpler forms than those for ringed surfaces and ruled surfaces. In particular. the bivariate equation Mu, v) = 0 is reduced to a decomposable form, f(u) = g(v) or parallel tof(u) - g(v)parallel to = \r(u)\, which can be solved more efficiently than the general case. (C) 2001 Elsevier Science (USA).