Method and apparatus for detecting and visualizing interferences between solids

A method for execution by a graphics processing system for detecting an interference between representations of solids, comprising the steps of:

• responsive to an input, positioning a cross-sectioning plane at an initial location with respect to representations of at least two solids;
• moving the cross-sectioning plane from the initial location through the representations of the least two solids;
• and
• during the step of moving, processing the representations of the solids by scan converting the representations to determine displayable faces of the solids and displaying the displayable faces of the solids, including portions of the solids that are exposed by a current location of the cross-sectioning plane;
• wherein
• the step of processing includes the steps of, detecting a region of interference between the representations of the at least two solids within a recursively sub-divided search interval that has a non-zero extent along a depth axis, the step of detecting operating in accordance with a result of a disjointness test performed on projections of the solids within the search interval;
• for a detected region of interference, displaying the detected region of interference in a manner that visually emphasizes the detected region of interference;
• and
• positioning the cross-sectioning plane with respect to the detected region of interference.

A method for execution by a graphics processing system for detecting an interference between representations of solids and for displaying the interference on display means having a screen comprised of a plurality of pixels, comprising the steps of:

• responsive to an input, activating a clipping plane C;
• for all pixels, initializing a depth buffer (z-buffer), a frame buffer, and a plurality of pixel mask buffers (Mu, Mi, Mp);
• for each solid S, performing the steps of,
• scanning S, toggling Mp and rendering into the frame buffer and z-buffer where Mu==0;
• disable writing into the z-buffer;
• rendering C where Mp==1 and Mu==0;
• for all pixels in R, where R is a projection of S onto the screen, performing the steps of,
• if (Mu==1 && Mp==1), then Mi=1;
• and
• if (Mp==1), then Mu=1 and Mp=0;
• enable writing into the z-buffer;
• deactivating the clipping plane C;
• disable writing into z-buffer;
• selecting a visually distinct manner for displaying an interference;
• for pixels where Mi==1, rendering into the frame buffer R' on C, where R' is a projection of S onto C, thereby displaying a region of interference in the visually distinct manner;
• enable writing into the z-buffer;
• disable writing into the frame buffer;
• and
• rendering R' on C for pixels where Mu==1, where == indicates a test for equality, and where && indicates a test for a logical AND.

A method for execution by a graphics processing system for detecting an interference between representations of solids and for displaying the interference on display means having a screen comprised of a plurality of pixels, comprising the steps of:

• determining a search interval having a dimension defined along a depth axis by Z.sub.start (Zs) and Z.sub.end (Ze) along a search direction D, the search interval defining a cross-sectioning slice c encompassing all or a portion of representations of two solids, the search direction D having a predetermined orientation with the cross-sectioning slice C;
• and
• recursively subdividing the dimension along the depth axis of the search interval until an interference between the two solids is detected, or until a predetermined minimum dimension of the search interval along the depth axis is obtained;
• the step of recursively subdividing including, for each of the recursive subdivisions, a step of determining if projections of the solids within the slice onto a cross-sectioning plane that defines a boundary of the slice are disjoint and, if so, determining that there is no interference between the solids within the slice, else, if projections of the solids within the slice onto the cross-sectioning plane that defines the boundary of the slice are not disjoint, detecting that there is a potential region of interference between the solids within a region contained within the slice.

A graphics processing system for displaying representations of solids on display means having a screen comprised of a plurality of pixels, comprising:

• means for determining a search interval having a dimension defined along a depth axis by Z.sub.start (Zs) and Z.sub.end (Ze) along a search direction D, the search interval defining a cross-sectioning slice C encompassing all or a portion of representations of two solids, the search direction D having a predetermined orientation with the cross-sectioning slice C;
• and
• means for recursively subdividing the dimension along the depth axis of the search interval until an interference between the two solids is detected, or until a predetermined minimum dimension of the search interval along the depth axis is obtained;
• said means for recursively subdividing including means, responsive to each of the recursive subdivisions, for determining if projections of the solids within the slice onto a cross-sectioning plane that defines a boundary of the slice are disjoint and, if so, for determining that there is no interference between the solids within the slice, else, if projections of the solids within the slice onto the cross-sectioning plane that defines the boundary of the slice are not disjoint, for detecting that there is a potential region of interference between the solids within a region contained within the slice.

In a graphics processing system for representing in two dimensions three dimensional objects that are orientated in space, a method for determining if the objects interfere with one another, comprising the steps of:

• sweeping a cross-sectioning slice having a predetermined non-zero thickness through the objects;
• responsive to the cross-sectioning slice sweeping through the objects, determining if a first one of the objects interferes with another one of the objects within a region bounded by the slice in accordance with a result of a disjointness test performed on projections of the solids within the cross-sectioning slice, and if so,
• displaying in a visually distinct manner a detected region of interference, and
• positioning a cross-sectioning plane at a boundary of the detected region of interference to aid an operator in evaluating the detected region of interference.

A method for execution by a graphics processing system for detecting and displaying an interference between representations of solids, wherein the graphics processing system displays the representations of solids as a plurality of pixels, the method comprising the steps of:

• defining a cross-sectioning plane within representations of at least two solids;
• for each of said plurality of pixels to be displayed,
• storing in a display memory data defining portions of the representations of the at least two solids that are exposed by the cross-sectioning plane;
• detecting a region of interference between the representations of the at least two solids within a recursively sub-divided search interval that has a non-zero extent along a depth axis, the step of detecting operating in accordance with a result of a disjointness test performed on projections of the solids within the search interval, and
• storing in a pixel mask buffer data defining the region of interference;
• displaying the portions of the representations of the at least two solids according to the data stored in the display memory;
• and
• displaying the detected region of interference in a manner that visually emphasizes the detected region of interference according to the data stored in the pixel mask buffer.