# US 2008/0259078 A1 · Apparatus and Method for Determining Intersections

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0259078 A1
- Document ID: US20080259078A1
- Status: Published application
- Kind: A1
- Application number: 11/793,363
- Filed: 2005-12-08
- Published: 2008-10-23
- Earliest claimed: 2004-12-21
- Assignees: Sinvent AS
- Inventors: Tor Dokken; Vibeke Skytt; Trond Runar Hagen; Jens Olav Nygaard
- Web page: https://patentgrep.com/patent/US20080259078A1

## CPC

- G06F 30/10: Geometric CAD
- G06F 30/00: Computer-aided design [CAD]
- G06T 15/005: {General purpose rendering architectures}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

In a data processing system for determining intersections between geometric objects, the work is split between a CPU and a stream processor. The intersection determination is controlled by the CPU. Data processing intensive parts of intersection algorithms, such as checking possible overlap of objects, checking overlap of normal fields of objects, approximating the extent of an object, approximating the normal fields of an object, or making conjectures for intersection topology and/or geometry between objects, are run on the stream processor. The results of the algorithmic parts run on the stream processor are used by the part of the algorithms run on the CPU. In cases where conjectures for the computational result are processed on the stream processor, the conjectures are checked for correctness by algorithms run on the CPU. If the correctness check shows that the result found is incomplete or wrong, additional parts of the algorithm are run on the CPU and possibly on the stream processor.

## Claims

### Claim 1

Computer apparatus for determining and finding a geometric representation of intersection topology for geometric objects that are described using any of parametric representation, algebraic representation and tessellated representation, said computer apparatus comprising at least one central processor unit (CPU) operative to perform portions of an intersection algorithm, initialize sub-algorithms thereof, control said sub-algorithms and to process a conjecture for an intersection calculation result,
wherein
said computer apparatus further comprises at least one stream processor unit (SPU) operative to receive sub-algorithms of said intersection algorithm from said at least one CPU and to execute said sub-algorithms of said intersection algorithm, resulting in information necessary to establish said conjecture, and to return said information to said at least one CPU.

### Claim 2 (depends on 1)

The computer apparatus of claim 1,
wherein
said at least one SPU is constituted by at least one graphics processor unit (GPU).

### Claim 3 (depends on 1)

The computer apparatus of claim 1,
wherein
said at least one SPU is further operative to establish said conjecture and to return the conjecture to said at least one CPU.

### Claim 4 (depends on 1)

The computer apparatus of claim 1,
wherein
said at least one CPU is further operative to verify, if required by a geometry processing system, completeness and correctness of said conjecture.

### Claim 5 (depends on 1)

The computer apparatus of claim 1,
wherein said apparatus is for determining intersections between at least two different geometric objects.

### Claim 6 (depends on 1)

The computer apparatus of claim 1,
wherein said apparatus is for determining self-intersections in one and the same geometric object.

### Claim 7

A method for determining and finding, in a computer apparatus comprising at least one central processor unit (CPU), a geometric representation of intersection topology for geometric objects that are described using any of parametric representation, algebraic representation and tessellated representation, said method comprising
initializing, in said at least one CPU, sub-algorithms of an intersection algorithm,
controlling, in said at least one CPU, the sub-algorithms of said intersection algorithm,
executing, in said at least one CPU, the sub-algorithms of said intersection algorithm, and
processing a conjecture for an intersection calculation result,
wherein
said method further comprises
transmitting at least one of said sub-algorithms of said intersection algorithm to at least one stream processor unit (SPU) comprised by said computer apparatus,
said at least one SPU executing sub-algorithms of said intersection algorithm, resulting in information necessary to establish said conjecture, and
returning said information to said at least one CPU.

### Claim 8 (depends on 7)

The method of claim 7,
wherein
said at least one SPU establishes said conjecture and returns it to said at least one CPU.

### Claim 9 (depends on 7)

The method of claim 7.
wherein
said at least one CPU further verifies, if required by a geometry processing system, completeness and correctness of said conjecture.

### Claim 10 (depends on 7)

The method of claim 7,
wherein intersections between at least two geometric objects are determined, and wherein
said at least one SPU executes at least one of the following sub-processes:
processing of geometric objects to extract information to be used for determining whether two or more objects overlap,
processing of geometric objects to extract information to be used for determining whether specified subparts of the objects overlap,
processing of geometric objects to extract information to be used for determining whether normal vector fields of two geometric objects overlap,
processing of geometric objects to extract information to be used for determining whether normal vector fields of specified subparts of the objects overlap,
processing of geometric objects to calculate a hull that guaranteed to contain the hull of a geometric object,
processing of geometric objects to calculate a convex hull that is guaranteed to contain the convex hull of a geometric object,
processing of geometric objects to calculate a hull that is guaranteed to contain the normal field of a geometric object,
processing of geometric objects to calculate a convex hull that is guaranteed to contain the normal field of a geometric object,
tessellation of a geometric object,
calculation of partial derivatives of a geometric object, in points,
calculation of partial derivatives of a geometric object, as a closed expression,
calculation of normals of a geometric object, in points,
calculation of normals of a geometric object, as a closed expression.

### Claim 11 (depends on 10)

The method of claim 10,
wherein the task of determining intersections is shared between said at least one CPU and said at least one SPU in the following manner:
said at least one CPU initiates the intersection determination process,
said at least one SPU processes the geometric objects to extract information to determine whether object hulls overlap,
said at least one CPU uses said information from said at least one SPU to report if an intersection is possible or not.

### Claim 12 (depends on 11)

The method of claim 11,
further comprising the following process steps:
if an intersection is possible, the geometric objects are tessellated on any of said at least one CPU and said at least one SPU,
said at least one SPU calculates the intersections of the tessellated objects, also returning parameter tupples if such tupples are available,
said at least one CPU processes the intersections calculated by said at least one SPU and returns said calculated intersections as a conjecture for the complete intersection.

### Claim 13 (depends on 12)

The method of claim 12,
wherein
for tessellations representing parametric objects, the vertices of the tessellation are assigned a parameter tupple corresponding to a point location in the geometric object being tessellated.

### Claim 14 (depends on 12)

The method of claim 12,
further comprising the following step:
said at least one CPU processes the intersection conjecture to determine if it is topologically correct and within user specified tolerances, by using the conjecture as a guide in a subdivision type verification process.

### Claim 15 (depends on 14)

The method of claim 14,
wherein the processing of the intersection conjecture is implemented in any one of the following manners, depending on the needs of the user:
returning a simple yes/no/undetermined to the correctness question,
providing an indication of the problematic areas,
providing a correction of the intersection conjecture that satisfies user requirements.

### Claim 16 (depends on 7)

The method of claim 7,
wherein, for calculating the intersection of two geometric objects, the task is shared between said at least one CPU and said at least one SPU in the following manner:
said at least one CPU initiates the intersection calculation,
said at least one SPU processes the geometric object to extract information to determine if convex object hulls overlap,
if the geometric objects have a possible intersection, said at least one CPU or said at least one SPU extracts information to be used for determining whether normal vector fields of the two geometric objects overlap,
if the normal vector field overlap, it is reported that a correct intersection has not been identified,
if the convex hulls of normal vector fields do not overlap, meaning that all intersections touch the boundary of one of the geometric objects, then the boundaries of each object are intersected with the other object on any of said at least one CPU and said at least one SPU, and
the resulting intersection points are reported as representing all intersections.

### Claim 17 (depends on 16)

The method of claim 16,
further comprising any one of the following process steps:
using marching to connect corresponding boundary points while taking care of user specified accuracy regarding the intersection representation,
using bi-section to connect corresponding boundary points while taking care of user specified accuracy of the intersection representation.

### Claim 18 (depends on 16)

The method of claim 16,
wherein specified functionality is replaced in the following manner if the normal vector fields overlap:
if an intersection is possible, the geometric objects are tessellated on any of said at least one CPU and said at least one SPU,
said at least one SPU calculates an intersection conjecture based on the tessellated objects, and if parameter tupples are available in the tessellations, this information is utilized to provide parameter tupples for the intersection structure provided,
said at least one CPU processes said intersection conjecture provided by said at least one SPU to determine if it is topologically correct and within user specified tolerances, by using said conjecture as a guide in a subdivision type verification process.

### Claim 19 (depends on 18)

The method of claim 18,
wherein, for tessellations representing parametric objects, the vertices of the tessellations are assigned the parameter tupple corresponding to a point location in the geometric object being tessellated.

### Claim 20 (depends on 18)

The method of claim 18,
wherein the CPU processing of the intersection conjecture is implemented in any one of the following ways, dependent on the needs of the user:
returning a simple yes/no/undetermined to the correctness question,
providing an indication of problematic areas,
providing a correction of the intersection conjecture that satisfies the user requirements.

### Claim 21 (depends on 7)

The method of claim 7, wherein self-intersections in geometric objects are determined, and wherein said at least one SPU executes at least one of the following sub-processes:
processing of a geometric object to extract information to be used for determining whether the convex hulls of non-adjacent subparts of said object overlap,
processing of a geometric object or a subpart thereof to extract information to be used for determining whether a normal vector field spans an angle less than or equal to π,
processing of a geometric object or a subpart thereof to extract information to be used to determine an angle spanned by the normal vector field,
processing of a geometric object to calculate a convex hull that is guaranteed to contain the convex hull of said geometric object or subparts thereof,
processing of a geometric object to calculate a convex hull that is guaranteed to contain the normal vector field of said geometric object or subparts thereof,
tessellation of a geometric object,
calculation of partial derivatives of a geometric object, in points,
calculation of partial derivatives of a geometric object, as a closed expression,
calculation of normals of a geometric object, in points,
calculation of normals of a geometric object, as a closed expression.

### Claim 22 (depends on 21)

The method of claim 21,
wherein the determination task is shared between said at least one CPU and said at least one SPU in the following manner:
said at least one CPU initiates the intersection determination process,
said at least one SPU processes the geometric object to extract information to determine span of the object normal vector field,
said at least one CPU uses said information from said at least one SPU to report if a self-intersection is possible or not.

### Claim 23 (depends on 22)

The method of claim 22,
further comprising the following process steps:
if a self-intersection is possible, the geometric object is tessellated on any one of said at least one CPU and said at least one SPU,
said at least one SPU calculates the self-intersections of the tessellated objects, also returning parameter tupples if these are available, and
said at least one CPU processes the self-intersections calculated by said at least one SPU, and returns this as a conjecture for the complete intersection.

### Claim 24 (depends on 23)

The method of claim 23,
wherein, for tessellations representing parametric objects, the vertices of the tessellation are assigned the parameter tupple corresponding to a point location in the geometric object being tessellated.

### Claim 25 (depends on 23)

The method of claim 23,
further comprising the following steps:
said at least one CPU processes the intersection conjecture provided by said at least one SPU to determine if it is topologically correct and within user specified tolerances, by using the conjecture as a guide in a subdivision type verification process.

### Claim 26 (depends on 25)

The method of claim 25,
wherein the processing of the intersection conjecture is implemented in any one of the following manners, dependent on the needs of the user:
returning a simple yes/no/undetermined to the correctness question,
providing an indication of the problematic areas,
providing a correction of the self-intersection conjecture that satisfies user requirements.
