Browse Prior Art Database

# Detecting and Rendering Intersections of Complex Surfaces

IP.com Disclosure Number: IPCOM000085385D
Original Publication Date: 1976-Mar-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 57K

IBM

Appel, A: AUTHOR

## Abstract

A frequent problem in computer graphics is to know whether and how do two objects or surfaces intersect. Complex surface intersection is also of interest for engineering design and naval architects. Intersection determination methods are explained that can be used for any surface described by surface rulings such as Coon's patches or Bezier polynominals, where the explicit solution is not known or is difficult.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

Detecting and Rendering Intersections of Complex Surfaces

A frequent problem in computer graphics is to know whether and how do two objects or surfaces intersect. Complex surface intersection is also of interest for engineering design and naval architects. Intersection determination methods are explained that can be used for any surface described by surface rulings such as Coon's patches or Bezier polynominals, where the explicit solution is not known or is difficult.

As shown in Fig. 1, a typical surface patch (P(I,J), P(I+1,J), P(I+1,J+1), P(I,J+1)) is broken up into triangles (P(I,J), P(I+1,J), P(I+1,J+1)) and (P(I,J), P(I,J+1), P(I+1,J+1)). The problem then is to find which triangles intersect other triangles, if any. When two triangles have a real intersection, the conditions shown in Fig. 2 occur.

Exactly two real piercing points occur. A real piercing point is a point that lies within the triangular boundary of one plane and within the finite length of a line of the other triangle. There can be as many as six virtual piercing points but only two real piercing points can exist. If these two exist, a real line of intersection can be drawn between them.

When all real lines of intersection are found for all triangles, the curve of intersection is approximated. The accuracy of this curve is of the same order as the grid approximation to the complex surfaces. For greater accuracy, a finer grid can be used or a polynomial fit to the real piercing points can be undertaken.

When no real piercing points are found, it may be assumed that a curve of intersection does not exist.

All triangles are dealt with in projection space rather than the original coordinate system.

As illustrated in Fig. 3, the maximum cell diagonal can be found. Any cell triangle further from another cell triangle than the dimension M:CD need not be considered as possibly intersecting.

It can be assumed that no triangle can interesct a neighboring triangle. No cell triangle of cell (I,J) can intersect a cell triangle of cell (K,L) if I(K-I)l<3 AND <(J-L)l<3.

It can be assumed that the depth in projection space of a cell triangle is the same as the first point of the cell. This is not essential...