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

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

The keeper's note

Accelerated collision-detection simulation technique (ride/robotics-adjacent).

Abstract

A method for detecting collisions associated with a simulation includes generating a plurality of dual quaternion representations associated with a plurality of curved trajectories for a plurality of objects. The method also includes determining a semialgebraic domain associated with the plurality of dual quaternion 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 trajectories. 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 usin

Claims

1. A computer-implemented method for detecting collisions associated with a simulation, the method comprising: generating a plurality of dual quaternion representations associated with a plurality of curved trajectories for a plurality of objects; determining a semialgebraic domain associated with the plurality of dual quaternion 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 dual quaternion representations associated with a plurality of curved trajectories for a plurality of objects; determining a semialgebraic domain associated with the plurality of dual quaternion representations; 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 dual quaternion representations associated with a plurality of curved trajectories for a plurality of objects; determining a semialgebraic domain associated with the plurality of dual quaternion representations; 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.