# US 2008/0186312 A1 · Method, medium and apparatus detecting model collisions

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

- Number: US 2008/0186312 A1
- Document ID: US20080186312A1
- Status: Published application
- Kind: A1
- Application number: 12/003,771
- Filed: 2007-12-31
- Published: 2008-08-07
- Earliest claimed: 2007-02-02
- Assignees: Samsung Electronics Co., Ltd.
- Inventors: Jeong-hwan Ahn; Kee-chang Lee
- Web page: https://patentgrep.com/patent/US20080186312A1

## CPC

- G06T 17/00: Three-dimensional [3D] modelling for computer graphics
- G06T 2210/21: Collision detection, intersection
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A method, medium and apparatus determining whether models collide with each other. In the model collision detecting method, medium and apparatus, it is possible to quickly examine whether models collide, and to recognize the collision generated at an arbitrary time, which is not a predetermined collision check time of the models, without missing the recognition of the collision generated at the arbitrary time, by determining whether paths reflecting movement of the model primitives between the current time and a previous time overlap when the model primitives do not collide at the current time, determining whether the model primitives collide with each other at an arbitrary time between the current time and the previous time when the path primitives overlap each other, and recognizing that the models collide with each other at the arbitrary time when the model primitives collide with each other at the arbitrary time.

## Claims

### Claim 1

A method of determining whether models enveloped by model primitives collide with each other, the method comprising:
determining whether the model primitives collide with each other at a current time;
determining whether paths reflecting movement of the model primitives between the current time and a previous time overlap each other when the model primitives do not collide with each other at the current time;
determining whether the model primitives collide with each other at an arbitrary time between the current time and the previous time when the path primitives overlap each other; and
recognizing that the models collide with each other at the arbitrary time when the model primitives collide with each other at the arbitrary time.

### Claim 2 (depends on 1)

The method of claim 1, wherein the determining of the whether the paths overlap each other further comprises:
determining whether path primitives each of which envelop the paths of the model primitives overlap each other, if the model primitives do not collide with each other at the current time.

### Claim 3 (depends on 2)

The method of claim 2, wherein each of the model primitives and the path primitives have a shape of at least one of an axis aligned bounding box (AABB), an oriented bounding box (OBB), a capsule, and a sphere.

### Claim 4 (depends on 1)

The method of claim 1, wherein locations of the models are simultaneously updated.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
if the model primitives do not collide with each other at the arbitrary time, changing a value of the arbitrary time to a different value, and then, determining whether the model primitives collide with each other at the different value of the arbitrary time; and
repeating the determining of whether the model primitives collide using new different values of the arbitrary time until it is recognized that the models collide with each other.

### Claim 6 (depends on 5)

The method of claim 5, wherein the determining of whether the model primitives collide is performed repeatedly using the new different values until either it is determined that the model primitives collide or until the number of times the repetition is performed reaches a predetermined threshold value.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
recognizing that the models collide with each other at the current time when the model primitives collide with each other at the current time.

### Claim 8 (depends on 1)

The method of claim 1, wherein each model is one of an object or a background.

### Claim 9 (depends on 1)

At least one medium comprising computer readable code to control at least one processing element in a computer to implement the method of claim 1.

### Claim 10

An apparatus for determining whether models enveloped by model primitives collide with each other, the apparatus comprising:
a first examination unit to determine whether the model primitives each collide with each other at a current time and to generate a first control signal corresponding to a result of the determination of whether the model primitives collide with each other at the current time;
a second examination unit to determine whether paths reflecting movement of the model primitives between the current time and a previous time overlap each other in response to the first control signal and generating a second control signal corresponding to a result of the determination of whether the paths overlap each other;
the first examination unit determining whether the model primitives collide with each other at an arbitrary time between the current time and the previous time in response to the second control signal and generating a third control signal corresponding to a result of the determination of whether the model primitives collide with each other at the arbitrary time; and
a collision recognizing unit to recognize that the models collide with each other in response to at least one of the first control signal and the third control signal.

### Claim 11 (depends on 10)

The apparatus of claim 10, wherein the second examination unit determines whether path primitives each of which envelop the paths of the model primitives overlap each other in response to the first control signal, and generating the second control signal corresponding to a result of the determination of whether the paths overlap each other.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein each of the model primitives and the path primitives have a shape of at least one of an axis aligned bounding box (AABB), an oriented bounding box (OBB), a capsule, and a sphere.

### Claim 13 (depends on 10)

The apparatus of claim 10, wherein locations of the models are simultaneously updated.

### Claim 14 (depends on 10)

The apparatus of claim 10, wherein the first examination unit repeatedly determines for a quantity of repetitions whether the model primitives collide with each other at the arbitrary time, while changing a value of the arbitrary time for each repetition.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein the first examination unit repeatedly performs the determination of whether the model primitives collide with each other at an arbitrary time while changing a value of the arbitrary time for each repetition, until either it is determined that the model primitives collide with each other or until the quantity of repetitions reaches a predetermined threshold value.

### Claim 16 (depends on 10)

The apparatus of claim 10, wherein each model is one of an object or a background.

### Claim 17

A method of determining whether models enveloped by model primitives collide with each other, the method comprising:
determining whether the model primitives collide with each other at a current time;
generating path primitives that envelop paths of the model primitives when the model primitives do not collide with each other at the current time, the paths reflecting movement of the model primitives between the current time and a previous time;
determining whether the model primitives collide with each other at an arbitrary time between the current time and the previous time when the path primitives overlap each other; and
recognizing that the models collide with each other at the current time when the model primitives collide with each other at the current time and recognizing that the models collide with each other at the arbitrary time when the model primitives collide with each other at the arbitrary time.

### Claim 18 (depends on 17)

The method of claim 17, further comprising repeating the determining of whether the model primitives collide with each other using a second arbitrary time, between the current time and the previous time, but different than the arbitrary time, and continuing to repeat the determining for different arbitrary times until a quantity of completed determinations meets a threshold value.

### Claim 19 (depends on 17)

At least one medium comprising computer readable code to control at least one processing element in a computer to implement the method of claim 17.

### Claim 20

An apparatus for determining whether models enveloped by model primitives collide with each other, the apparatus comprising:
a first examination unit to determine whether the model primitives each collide with each other at a current time and to generate a first control signal corresponding to a result of the determination of whether the model primitives collide with each other at the current time;
a path primitive generating unit to generate path primitives that envelop paths of the model primitives when the model primitives do not collide with each other at the current time, the paths reflecting movement of the model primitives between the current time and a previous time;
a second examination unit to determine whether the path primitives overlap each other in response to the first control signal and generating a second control signal corresponding to a result of the determination of whether the path primitives overlap each other;
the first examination unit to determine whether the model primitives collide with each other at an arbitrary time between the current time and a previous time in response to the second control signal and generating a third control signal corresponding to a result of the determination of whether the model primitives collide with each other at the arbitrary time; and
a collision recognizing unit to recognize that the models collide with each other in response to at least one of the first control signal and the third control signal.
