# US 2022/0277495 A1 · Method for determining collision range and related apparatus

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

- Number: US 2022/0277495 A1
- Document ID: US20220277495A1
- Status: Published application
- Kind: A1
- Application number: 17/749,120
- Filed: 2022-05-19
- Published: 2022-09-01
- Earliest claimed: 2020-05-20
- Assignees: Tencent Technology (Shenzhen) Company Limited
- Applicants: Tencent Technology (Shenzhen) Company Limited
- Inventors: Xiang ZHANG; Yi LIU
- Web page: https://patentgrep.com/patent/US20220277495A1

## CPC

- A63F 13/56: Computing the motion of game characters with respect to other game characters, game objects or elements of the game scene, e.g. for simulating the behaviour of a group of virtual soldiers or for path finding
- A63F 13/525: Changing parameters of virtual cameras
- A63F 13/577: using determination of contact between game characters or objects, e.g. to avoid collision between virtual racing cars
- G06T 7/60: Analysis of geometric attributes
- G06T 11/00: Two-dimensional [2D] image generation
- G06T 17/00: Three-dimensional [3D] modelling for computer graphics
- G06T 19/00: Manipulating three-dimensional [3D] models or images for computer graphics
- G06T 2207/20068: Projection on vertical or horizontal image axis
- G06T 2210/21: Collision detection, intersection
- G06T 2210/32: Image data format
- A63F: CARD, BOARD, OR ROULETTE GAMES; INDOOR GAMES USING SMALL MOVING PLAYING BODIES; VIDEO GAMES; GAMES NOT OTHERWISE PROVIDED FOR
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A method for determining a collision range includes: determining a grid plane corresponding to a model, the grid plane including a plurality of grid regions; projecting the model to the grid plane and obtaining height information of the model with respect to the grid plane, the height information of the model including grid height information corresponding to a grid region that identifies a height of a sub-model in the model with respect to the grid plane, and the sub-model being a portion of the model in a projection space of the grid region; and obtaining a collision range of the model according to the grid plane and the height information.

## Claims

### Claim 1

A method for determining a collision range, performed by a computer device, the method comprising:
determining a grid plane corresponding to a model, the grid plane comprising a plurality of grid regions;
projecting the model to the grid plane and obtaining height information of the model with respect to the grid plane, the height information of the model including grid height information corresponding to a grid region that identifies a height of a sub-model in the model with respect to the grid plane, and the sub-model being a portion of the model in a projection space of the grid region; and
obtaining a collision range of the model according to the grid plane and the height information of the model.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the projecting the model to the grid plane and obtaining height information of the model with respect to the grid plane comprises:
acquiring a camera field of view comprising the model according to a virtual camera at a top view angle with respect to the grid plane; and
performing image rendering on the camera field of view on the grid plane and obtaining a two-dimensional model image carrying the height information.

### Claim 3 (depends on 2)

The method according to claim 2, wherein a size of the grid region is determined according to a sampling rate and one of the grid regions corresponds to one pixel in the two-dimensional model image.

### Claim 4 (depends on 2)

The method according to claim 2, wherein the performing image rendering on the camera field of view on the grid plane and obtaining a two-dimensional model image carrying the height information comprises:
determining height information corresponding to pixels in the two-dimensional model image according to a pixel shader during a process of the image rendering on the camera field of view.

### Claim 5 (depends on 1)

The method according to claim 1, wherein the grid height information corresponding to the grid region comprises a surface type identifier associated with each height included in the grid height information, the surface type identifier is either an upper surface identifier or a lower surface identifier, the upper surface identifier indicates that the associated height corresponds to a position belonging to an upper surface in the sub-model, and the lower surface identifier indicates that the associated height corresponds to a position belonging to a lower surface in the sub-model;
the obtaining a collision range of the model according to the grid plane and the height information comprises:
performing height layer division according to the surface type identifiers by traversing the grid height information corresponding to the grid region; and
obtaining a collision range of the model according to a one or more height layers obtained from the height layer division.

### Claim 6 (depends on 5)

The method according to claim 5, wherein the performing height layer division according to the surface type identifiers by traversing the grid height information corresponding to the grid region comprises:
dividing the grid height information corresponding to the grid region into a plurality of undetermined height layers according to the surface type identifiers;
determining a spacing between adjacent undetermined height layers;
combining adjacent undetermined height layers having a spacing less than a threshold into one height layer; and
determining adjacent undetermined height layers having a spacing greater than or equal to the threshold as different height layers.

### Claim 7 (depends on 6)

The method according to claim 6, wherein the threshold is determined according to a size of a controlled object in a game corresponding to the model.

### Claim 8 (depends on 5)

The method according to claim 5, wherein the obtaining a collision range of the model according to a one or more height layers obtained from the height layer division comprises:
generating a columnar structure conforming to the one or more height layers based on the grid region; and
obtaining the collision range of the model according to the columnar structures of the grid regions.

### Claim 9 (depends on 1)

The method according to claim 1, wherein before the obtaining a collision range of the model according to the grid plane and the height information, the method further comprises:
filtering the height information through a height range, and retaining height information of an identified height within the height range.

### Claim 10 (depends on 1)

The method according to claim 1, wherein the method is performed by a graphics processing unit (GPU) of the computer device.

### Claim 11

An apparatus for determining a collision range, deployed on a processing device having a memory and a processor coupled to the memory, the processor being configured to:
determine a grid plane corresponding to a model, the grid plane comprising a plurality of grid regions;
project the model to the grid plane and obtain height information of the model with respect to the grid plane, the height information of the model including grid height information corresponding to a grid region that identifies a height of a sub-model in the model with respect to the grid plane, and the sub-model being a portion of the model in a projection space of the grid region; and
obtain a collision range of the model according to the grid plane and the height information.

### Claim 12 (depends on 11)

The apparatus according to claim 11, wherein the processor is further configured to:
acquire a camera field of view comprising the model according to a virtual camera at a top view angle with respect to the grid plane; and
perform image rendering on the camera field of view on the grid plane so as to obtain a two-dimensional model image carrying the height information.

### Claim 13 (depends on 12)

The apparatus according to claim 12, wherein a size of the grid region is determined according to a sampling rate and one of the grid regions corresponds to one pixel in the two-dimensional model image.

### Claim 14 (depends on 12)

The apparatus according to claim 12, wherein the processor is further configured to:
determine height information corresponding to pixels in the two-dimensional model image according to a pixel shader during a process of the image rendering on the camera field of view.

### Claim 15 (depends on 11)

The apparatus according to claim 11, wherein the grid height information corresponding to the grid region comprises a surface type identifier for each height included in the grid height information, the surface type identifier is either an upper surface identifier or a lower surface identifier, the upper surface identifier indicates that the associated height corresponds to a position belonging to an upper surface in the sub-model, and the lower surface identifier indicates that the associated height corresponds to a position belonging to a lower surface in the sub-model;
the processor is further configured to:
perform height layer division according to the surface type identifiers by traversing the grid height information corresponding to the grid region; and
obtain a collision range of the model according to a one or more height layers obtained from the height layer division.

### Claim 16 (depends on 15)

The apparatus according to claim 15, wherein the processor is further configured to: for one grid region,
divide the grid height information corresponding to the grid region into a plurality of undetermined height layers according to the surface type identifiers;
determine a spacing between adjacent undetermined height layers;
combine adjacent undetermined height layers when the adjacent undetermined height layers have a spacing less than a threshold into one height layer; and
determine adjacent undetermined height layers as different height layers when the adjacent undetermined height layers have a spacing greater than or equal to the threshold.

### Claim 17 (depends on 16)

The apparatus according to claim 16, wherein the threshold is determined according to a size of a controlled object in a game corresponding to the model.

### Claim 18 (depends on 15)

The apparatus according to claim 15, wherein the processor is further configured to:
generate a columnar structure conforming to the one or more height layers based on the grid region; and
obtain the collision range of the model according to the columnar structures of the grid regions.

### Claim 19 (depends on 11)

The apparatus according to claim 11, wherein before obtaining the collision range of the model according to the grid plane and the height information, the processor is further configured to:
filter the height information through a height range, and retaining height information of an identified height within the height range.

### Claim 20

A non-transitory computer-readable storage medium storing a computer program that, when executed by a processor, cause the processor to perform:
determining a grid plane corresponding to a model, the grid plane comprising a plurality of grid regions;
projecting the model to the grid plane and obtaining height information of the model with respect to the grid plane, the height information of the model including grid height information corresponding to a grid region that identifies a height of a sub-model in the model with respect to the grid plane, and the sub-model being a portion of the model in a projection space of the grid region; and
obtaining a collision range of the model according to the grid plane and the height information of the model.
