# US 10,311,544 B2 · Method for detecting collision between cylindrical collider and convex body in real-time virtual scenario, terminal, and storage medium > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,311,544 B2 - Document ID: US10311544B2 - Status: Granted - Kind: B2 - Application number: 15/785,186 - Filed: 2017-10-16 - Published: 2018-02-08 - Granted: 2019-06-04 - Earliest claimed: 2015-11-30 - Assignees: Tencent Technology (Shenzhen) Company Limited - Applicants: Tencent Technology (Shenzhen) Company Limited - Inventors: Xini Kuang - Web page: https://patentgrep.com/patent/US10311544B2 ## CPC - G06T 3/20: Linear translation of whole images or parts thereof, e.g. panning - G06F 30/00: Computer-aided design [CAD] - G06F 30/20: Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) - G06T 7/13: Edge detection - G06T 7/246: using feature-based methods, e.g. the tracking of corners or segments - G06T 7/60: Analysis of geometric attributes - G06T 7/70: Determining position or orientation of objects or cameras (camera calibration G06T7/80) - G06T 17/10: Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes - B25J 9/1666: {Avoiding collision or forbidden zones} - B25J 9/1676: {Avoiding collision or forbidden zones} - G06F 2111/10: Numerical modelling - G06T 13/20: Three-dimensional [3D] animation - G06T 13/80: Two-dimensional [2D] animation, e.g. using sprites - G06T 2207/20164: Salient point detection; Corner detection - G06T 2210/12: Bounding box - G06T 2210/21: Collision detection, intersection - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - B25J: MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES ({manipulators specially adapted for use in surgery A61B34/70; manipulators used in cleaning hollow articles B08B9/04}; manipulators associated with rolling mills B21B39/20; manipulators associated with forging machines B21J13/10; {manipulators associated with picking-up and placing mechanisms B23P19/007}; means for holding wheels or parts thereof B60B30/00; {vehicles with ground-engaging propulsion means, e.g. walking members B62D57/02, B62D57/032; devices for picking-up and depositing articles or materials between conveyors B65G47/90, B65G47/91; manipulators with gripping or holding means for transferring packages B65H67/065}; cranes B66C; {manipulators used in the protection or supervision of pipe-line installations F17D5/00; walking equipment adapted for nuclear steam-generators F22B37/006}; manipulators specially adapted for, or associated with, nuclear reactors G21C; {apparatus used for handling wafers during manufacture or treatment of semiconductor H10P72/50}) ## Abstract A method for detecting a collision between a cylindrical collider and a convex body in a real-time virtual scenario performed at a computer includes: converting a cylindrical collider into a preset polygonal prism concentric to the cylindrical collider; transforming the preset polygonal prism to a local coordinate system of the convex body; obtaining a projection of the cylindrical collider on one or more testing axes according to each testing axis and the location of the preset polygonal prism in the local coordinate system of the convex body, and obtaining a projection of the convex body on each testing axis; and in accordance with a determination that the projections of the cylindrical collider and the convex body intersect with each other on each testing axis, moving the cylindrical collider away from the convex body in the real-time virtual scenario to avoid the collision. ## Claims ### Claim 1 A method for detecting a collision between a cylindrical collider and a convex body in a real-time virtual scenario performed at a computer having one or more processors and memory storing one or more programs to be executed by the one or more processors, the method comprising: converting a cylindrical collider corresponding to a virtual object in a virtual scenario into a preset polygonal prism concentric to the cylindrical collider; transforming the preset polygonal prism to a local coordinate system of a convex body, to obtain a location of the preset polygonal prism in the local coordinate system of the convex body; obtaining, according to the location of the preset polygonal prism in the local coordinate system of the convex body, a normal direction of each face of the preset polygonal prism, an edge direction of a preset polygon, and an edge direction of a lateral edge of the prism; obtaining a normal direction of each face and each edge direction of the convex body; separately obtaining a vector product of each edge direction of the convex body and the edge direction of the preset polygon and a vector product of each edge direction of the convex body and the edge direction of the lateral edge of the prism; using one or more of a normal direction of each face of the preset polygonal prism, a normal direction of each face of the convex body, and the vector products as one or more testing axes; obtaining a projection of the cylindrical collider on the one or more testing axes according to each testing axis and the location of the preset polygonal prism in the local coordinate system of the convex body, and obtaining a projection of the convex body on each testing axis; and in accordance with a determination that the projections of the cylindrical collider and the convex body intersect with each other on each testing axis, determining that there is a collision between the cylindrical collider and the convex body and moving the cylindrical collider away from the convex body in the real-time virtual scenario to avoid the collision. ### Claim 2 (depends on 1) The method according to claim 1, wherein the operation of transforming the preset polygonal prism into a local coordinate system of a convex body, to obtain a location of the preset polygonal prism in the local coordinate system of the convex body comprises: transforming an X axis, a Y axis, a Z axis, and midpoints of the preset polygonal prism into the local coordinate system of the convex body, to obtain vectors corresponding to unit vectors of the X axis, the Y axis, and the Z axis of the preset polygonal prism in the local coordinate system of the convex body, and multiply the vector of the Z axis in the local coordinate system of the convex body by positive and negative half height values of the cylindrical collider, to obtain midpoint coordinates on two faces, namely, upper and lower bottom faces, of the polygonal prism; obtaining a radius of the cylindrical collider, obtain, according to the vectors corresponding to the radius, the X axis, the Y axis of the cylindrical collider in the local coordinate system of the convex body, offsets of vertexes of the preset polygonal prism relative to the midpoints of the faces which they are located, and obtain sums of the offsets and the midpoint coordinates to obtain coordinates of the corresponding vertexes; and reconstructing the preset polygonal prism in the local coordinate system of the convex body according to coordinates of each vertex. ### Claim 3 (depends on 2) The method according to claim 2, further comprising: after being transformed into the local coordinate system of the convex body, projecting each vertex of the preset polygonal prism in the local coordinate system of the convex body, and setting extreme values to obtain a difference, so as to obtain a projection length of the cylindrical collider. ### Claim 4 (depends on 2) The method according to claim 2, further comprising: after being transformed into the local coordinate system of the convex body, obtaining a radius and a half height of the cylindrical collider, coordinate base vectors corresponding to base vectors of three axes, namely, X, Y, and Z axes of the cylindrical collider transformed into the local coordinate system of the convex body, and a testing axis direction of each testing axis in the local coordinate system of the convex body to calculate a projection length of the cylindrical collider. ### Claim 5 (depends on 1) The method according to claim 1, further comprising: in accordance with a determination that a testing axis is parallel to the vertical axis of the cylindrical collider, obtaining a product of a length of a Z base vector of the coordinate base vectors corresponding to the base vectors of three axes, namely, the X, Y, and Z axes, of the cylindrical collider that are transformed into the local coordinate system of the convex body and the half height as a projection length of the cylindrical collider; and in accordance with a determination that a testing axis is vertical to the vertical axis of the cylindrical collider, obtaining a larger value of a length of an X base vector and a length of a Y base vector of the coordinate base vectors corresponding to the base vectors of three axes, namely, the X, Y, and Z axes, of the cylindrical collider that are transformed into the local coordinate system of the convex body, and further, using a product of the larger value and the radius of the cylindrical collider as the projection length of the cylindrical collider. ### Claim 6 (depends on 1) The method according to claim 1, wherein the preset polygon is a regular polygon inscribed to a bottom face of the cylindrical collider. ### Claim 7 (depends on 6) The method according to claim 6, wherein, the polygon is a regular polygon having an even number of edges, when an edge direction of the preset polygon is obtained, edge directions that are asymmetrical based on a center are selected from a preset polygon of two preset polygons on upper and lower bottom faces of the reset polygonal prism, and a side direction of one lateral edge is selected when obtaining a side direction of a lateral edge of the prism. ### Claim 8 A computer, comprising one or more processors, memory and one or more programs stored in the memory that, when being executed by the one or more processors, cause the computer to perform a plurality of operations including: converting a cylindrical collider corresponding to a virtual object in a virtual scenario into a preset polygonal prism concentric to the cylindrical collider; transforming the preset polygonal prism to a local coordinate system of a convex body, to obtain a location of the preset polygonal prism in the local coordinate system of the convex body; obtaining, according to the location of the preset polygonal prism in the local coordinate system of the convex body, a normal direction of each face of the preset polygonal prism, an edge direction of a preset polygon, and an edge direction of a lateral edge of the prism; obtaining a normal direction of each face and each edge direction of the convex body; separately obtaining a vector product of each edge direction of the convex body and the edge direction of the preset polygon and a vector product of each edge direction of the convex body and the edge direction of the lateral edge of the prism; using one or more of a normal direction of each face of the preset polygonal prism, a normal direction of each face of the convex body, and the vector products as one or more testing axes; obtaining a projection of the cylindrical collider on the one or more testing axes according to each testing axis and the location of the preset polygonal prism in the local coordinate system of the convex body, and obtaining a projection of the convex body on each testing axis; and in accordance with a determination that the projections of the cylindrical collider and the convex body intersect with each other on each testing axis, determining that there is a collision between the cylindrical collider and the convex body and moving the cylindrical collider away from the convex body in the real-time virtual scenario to avoid the collision. ### Claim 9 (depends on 8) The computer according to claim 8, wherein the operation of transforming the preset polygonal prism into a local coordinate system of a convex body, to obtain a location of the preset polygonal prism in the local coordinate system of the convex body comprises: transforming an X axis, a Y axis, a Z axis, and midpoints of the preset polygonal prism into the local coordinate system of the convex body, to obtain vectors corresponding to unit vectors of the X axis, the Y axis, and the Z axis of the preset polygonal prism in the local coordinate system of the convex body, and multiply the vector of the Z axis in the local coordinate system of the convex body by positive and negative half height values of the cylindrical collider, to obtain midpoint coordinates on two faces, namely, upper and lower bottom faces, of the polygonal prism; obtaining a radius of the cylindrical collider, obtain, according to the vectors corresponding to the radius, the X axis, the Y axis of the cylindrical collider in the local coordinate system of the convex body, offsets of vertexes of the preset polygonal prism relative to the midpoints of the faces which they are located, and obtain sums of the offsets and the midpoint coordinates to obtain coordinates of the corresponding vertexes; and reconstructing the preset polygonal prism in the local coordinate system of the convex body according to coordinates of each vertex. ### Claim 10 (depends on 9) The computer according to claim 9, wherein the plurality of operations further include: after being transformed into the local coordinate system of the convex body, projecting each vertex of the preset polygonal prism in the local coordinate system of the convex body, and setting extreme values to obtain a difference, so as to obtain a projection length of the cylindrical collider. ### Claim 11 (depends on 9) The computer according to claim 9, wherein the plurality of operations further include: after being transformed into the local coordinate system of the convex body, obtaining a radius and a half height of the cylindrical collider, coordinate base vectors corresponding to base vectors of three axes, namely, X, Y, and Z axes of the cylindrical collider transformed into the local coordinate system of the convex body, and a testing axis direction of each testing axis in the local coordinate system of the convex body to calculate a projection length of the cylindrical collider. ### Claim 12 (depends on 8) The computer according to claim 8, wherein the plurality of operations further include: in accordance with a determination that a testing axis is parallel to the vertical axis of the cylindrical collider, obtaining a product of a length of a Z base vector of the coordinate base vectors corresponding to the base vectors of three axes, namely, the X, Y, and Z axes, of the cylindrical collider that are transformed into the local coordinate system of the convex body and the half height as a projection length of the cylindrical collider; and in accordance with a determination that a testing axis is vertical to the vertical axis of the cylindrical collider, obtaining a larger value of a length of an X base vector and a length of a Y base vector of the coordinate base vectors corresponding to the base vectors of three axes, namely, the X, Y, and Z axes, of the cylindrical collider that are transformed into the local coordinate system of the convex body, and further, using a product of the larger value and the radius of the cylindrical collider as the projection length of the cylindrical collider. ### Claim 13 (depends on 8) The computer according to claim 8, wherein the preset polygon is a regular polygon inscribed to a bottom face of the cylindrical collider. ### Claim 14 (depends on 13) The computer according to claim 13, wherein, the polygon is a regular polygon having an even number of edges, when an edge direction of the preset polygon is obtained, edge directions that are asymmetrical based on a center are selected from a preset polygon of two preset polygons on upper and lower bottom faces of the reset polygonal prism, and a side direction of one lateral edge is selected when obtaining a side direction of a lateral edge of the prism. ### Claim 15 A non-transitory computer readable storage medium storing one or more computer readable instructions that, when being executed by one or more processors of a computer, cause the computer to perform a plurality of operations including: converting a cylindrical collider corresponding to a virtual object in a virtual scenario into a preset polygonal prism concentric to the cylindrical collider; transforming the preset polygonal prism to a local coordinate system of a convex body, to obtain a location of the preset polygonal prism in the local coordinate system of the convex body; obtaining, according to the location of the preset polygonal prism in the local coordinate system of the convex body, a normal direction of each face of the preset polygonal prism, an edge direction of a preset polygon, and an edge direction of a lateral edge of the prism; obtaining a normal direction of each face and each edge direction of the convex body; separately obtaining a vector product of each edge direction of the convex body and the edge direction of the preset polygon and a vector product of each edge direction of the convex body and the edge direction of the lateral edge of the prism; using one or more of a normal direction of each face of the preset polygonal prism, a normal direction of each face of the convex body, and the vector products as one or more testing axes; obtaining a projection of the cylindrical collider on the one or more testing axes according to each testing axis and the location of the preset polygonal prism in the local coordinate system of the convex body, and obtaining a projection of the convex body on each testing axis; and in accordance with a determination that the projections of the cylindrical collider and the convex body intersect with each other on each testing axis, determining that there is a collision between the cylindrical collider and the convex body and moving the cylindrical collider away from the convex body in the real-time virtual scenario to avoid the collision. ### Claim 16 (depends on 15) The non-transitory computer readable storage medium according to claim 15, wherein the operation of transforming the preset polygonal prism into a local coordinate system of a convex body, to obtain a location of the preset polygonal prism in the local coordinate system of the convex body comprises: transforming an X axis, a Y axis, a Z axis, and midpoints of the preset polygonal prism into the local coordinate system of the convex body, to obtain vectors corresponding to unit vectors of the X axis, the Y axis, and the Z axis of the preset polygonal prism in the local coordinate system of the convex body, and multiply the vector of the Z axis in the local coordinate system of the convex body by positive and negative half height values of the cylindrical collider, to obtain midpoint coordinates on two faces, namely, upper and lower bottom faces, of the polygonal prism; obtaining a radius of the cylindrical collider, obtain, according to the vectors corresponding to the radius, the X axis, the Y axis of the cylindrical collider in the local coordinate system of the convex body, offsets of vertexes of the preset polygonal prism relative to the midpoints of the faces which they are located, and obtain sums of the offsets and the midpoint coordinates to obtain coordinates of the corresponding vertexes; and reconstructing the preset polygonal prism in the local coordinate system of the convex body according to coordinates of each vertex. ### Claim 17 (depends on 16) The non-transitory computer readable storage medium according to claim 16, wherein the plurality of operations further include: after being transformed into the local coordinate system of the convex body, projecting each vertex of the preset polygonal prism in the local coordinate system of the convex body, and setting extreme values to obtain a difference, so as to obtain a projection length of the cylindrical collider. ### Claim 18 (depends on 16) The non-transitory computer readable storage medium according to claim 16, wherein the plurality of operations further include: after being transformed into the local coordinate system of the convex body, obtaining a radius and a half height of the cylindrical collider, coordinate base vectors corresponding to base vectors of three axes, namely, X, Y, and Z axes of the cylindrical collider transformed into the local coordinate system of the convex body, and a testing axis direction of each testing axis in the local coordinate system of the convex body to calculate a projection length of the cylindrical collider. ### Claim 19 (depends on 15) The non-transitory computer readable storage medium according to claim 15, wherein the plurality of operations further include: in accordance with a determination that a testing axis is parallel to the vertical axis of the cylindrical collider, obtaining a product of a length of a Z base vector of the coordinate base vectors corresponding to the base vectors of three axes, namely, the X, Y, and Z axes, of the cylindrical collider that are transformed into the local coordinate system of the convex body and the half height as a projection length of the cylindrical collider; and in accordance with a determination that a testing axis is vertical to the vertical axis of the cylindrical collider, obtaining a larger value of a length of an X base vector and a length of a Y base vector of the coordinate base vectors corresponding to the base vectors of three axes, namely, the X, Y, and Z axes, of the cylindrical collider that are transformed into the local coordinate system of the convex body, and further, using a product of the larger value and the radius of the cylindrical collider as the projection length of the cylindrical collider. ### Claim 20 (depends on 15) The non-transitory computer readable storage medium according to claim 15, wherein the preset polygon is a regular polygon inscribed to a bottom face of the cylindrical collider.