Browse Prior Art Database

Determining Whether Two Algebraic Primitives Intersect in a Box

IP.com Disclosure Number: IPCOM000120372D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 104K

Publishing Venue

IBM

Related People

Woodwark, JR: AUTHOR

Abstract

Disclosed is a test, based on interval arithmetic, that determines approximately but conservatively whether two arbitrary algebraic primitives intersect in a given box. This offers the opportunity of identifying near-parallel primitives (e.g., concentric cylinders) at an early stage in the division of space during shape modelling processes of all kinds with potential for a significant speed increase by reducing the amount of work required deciding whether primitive intersection occurs.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Determining Whether Two Algebraic Primitives Intersect in a Box

      Disclosed is a test, based on interval arithmetic, that
determines approximately but conservatively whether two arbitrary
algebraic primitives intersect in a given box. This offers the
opportunity of identifying near-parallel primitives (e.g., concentric
cylinders) at an early stage in the division of space during shape
modelling processes of all kinds with potential for a significant
speed increase by reducing the amount of work required deciding
whether primitive intersection occurs.

      In the VOLE (*) precursor to WINSOM (The Winchester Solid
Modeller System) an increase in efficiency was obtained by not always
allowing recursion to descend to a pixel level, but stopping it where
it could be shown that there was a primitive that occluded all the
others in a sub-space;  VOLE had planar primitives only.
Description

      The technique is as follows.  Given two functions (i.e.,
surfaces in three dimensions) A = 0 and B = 0, the surface A +
mB = 0 meets A and B where they cross.  Suppose that the surfaces A
= 0 and B = 0 pass through a given box defined by intervals in
x, y and z.  If a value of m is found so that the surface
A + mB = 0 does not pass through that box, then A does not
intersect B within the box.

      Put another way, where A and B meet, they are both 0, therefore
A +  mB must also be 0.  By proving that A + mB is never
0 in the box, then A = 0 and B = 0 do not cross
in the box.

      It is unknown whether a surface A + mB which does not cut the
box can be found for all pairs of surfaces A and B which do not
intersect in the same box.  (There is the further possibility of
replacing m by an arbitrary function:  an unnecessary complication at
present.)  In any case, this test is certain to be approximate, as
the only way we know to determine whether A + mB cuts the box is
by interval arithmetic. Therefore, there will be times when A does
not intersect B, but the test tells us the reverse.  In this case,
the box is subdivided and the test repeated.  The test will not,
however, separate surfaces falsely;  this is what is meant by a
conservative test.

      In searching for a value of m that passes the test, it is
clearly inadequate to determine intervals on A and B, and then look
for a value of m.  Since the intervals on A and B must contain zero
(because A and B pass through the box), the interval on A + mB will
also contain zero.  It is necessary to rearrange the polynomial A +
mB by collecting terms together and adding their coefficients.  The
interval computed from this will then in gene...