ACCELERATED SUM-OF-SQUARES COLLISION DETECTION FOR TIME-VARYING CURVED SHAPES

Number: 20250022229
Published: 2025-01-16
Filed: 2023-07-12
Assignee: DISNEY ENTERPRISES, INC.
Inventors: TAMSTORF; Rasmus et al.
CPC: G06T19/00; G06F30/20
Verdict: Low Notable software
Source: Google Patents · FreePatentsOnline

The keeper's note

Accelerated collision-detection simulation technique (companion patent).

Abstract

A method for detecting collisions associated with a simulation includes generating a plurality of spline-based representations associated with a plurality of objects. The method also includes determining a semialgebraic domain associated with the plurality of spline-based representations and performing an optimization over the semialgebraic domain to determine one or more collision states associated with the plurality of objects. The method further includes causing the simulation to be performed based on the one or more collision states.

Background

BACKGROUND Field of the Various Embodiments

Embodiments of the present disclosure relate generally to graphics and simulations and, more specifically, to accelerated sum-of-squares collision detection for time-varying curved shapes. Description of the Related Art

Sum-of-Squares Programming (SOSP) refers to a mathematical optimization technique that can be used to solve problems with polynomial objective functions. SOSP involves relaxing a polynomial optimization problem to an optimization that is constrained to a set of polynomials that can be written as a sum of squares of polynomial functions.

SOSP can, in concept, be used in various types of simulations and/or models. For example, robotic and/or vehicular paths, optical cables, hair strands, hair bundles, and/or other types of curved geometries or trajectories could be modeled using splines that are represented using polynomials. These polynomials could then be used with SOSP to detect collisions, intersections, and/or other events related to the curved geometries.

However, existing SOSP techniques tend to be too slow and computationally complex to be used with problems involving curved geometries and/or other more complex representations. More specifically, the size and runtime of a typical SOSP optimization scales factorially with the degree of the polynomials in the corresponding SOSP problem. Consequently, a conventional SOSP formulation that represents objects and/or trajectories using cubi

Claims

1. A computer-implemented method for detecting collisions associated with a simulation, the method comprising: generating a plurality of tapered cubic cylinder representations associated with a plurality of objects; determining a semialgebraic domain associated with the plurality of tapered cubic cylinder representations; performing an optimization over the semialgebraic domain to determine one or more collision states associated with the plurality of objects; and causing the simulation to be performed based on the one or more collision states. || 11. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause the one or more processors to perform the steps of: generating a plurality of spline-based representations associated with a plurality of objects; determining a semialgebraic domain associated with the plurality of spline-based representations, wherein the semialgebraic domain comprises a quadratic module that includes a first degree associated with a first set of inequality constraints and a second degree associated with a first set of equality constraints; performing an optimization over the semialgebraic domain to determine one or more collision states associated with the plurality of objects; and causing a simulation to be performed based on the one or more collision states. || 1. || 20. A system, comprising: one or more memories that store instructions, and one or more processors that are coupled to the one or more memories and, when executing the instructions, are configured to perform the steps of: generating a plurality of spline-based representations associated with a plurality of objects; determining a semialgebraic domain associated with the plurality of spline-based representations, wherein determining the semialgebraic domain comprises replacing a plurality of elements included in the semialgebraic domain with a product of the plurality of elements; performing an optimization over the semialgebraic domain to determine one or more collision states associated with the plurality of objects; and causing a simulation to be performed based on the one or more collision states.