Augury and Forerunner: Real‐Time Feedback Via Predictive Numerical Optimization and Input Prediction

Abstract In many interactive systems, user input initializes and launches an iterative optimization procedure. The goal is to provide assistive feedback to some creation/editing process. Examples include constraint‐based GUI layout and complex snapping scenarios. Many geometric problems, such as fitting a shape to data, involve optimizations which may take seconds to complete (or even longer), yet require human guidance. In order to make these optimization routines practical in interactive sessions, simplifications or sacrifices must be made. Canonically, non‐convex optimization problems are solved iteratively by taking a series of steps towards a solution. By their nature, there are many locally optimal solutions; which solution is found is highly dependent on an initial guess. There is a fundamental conflict between optimization and interactivity. Interrupting and restarting the optimization every time the user, e.g. moves the mouse prevents any solution from being computed until the user ceases interaction. Continuing to run the optimization procedure computes a perpetually outdated solution. This presents a particular unsolved challenge with respect to direct manipulation. Every time the user, e.g. moves the mouse, the entire optimization must be re‐started with the new user input, since returning a stale result associated with the previous user state is undesirable. We propose predictive short‐circuiting to reduce this fundamental tension. Our approach memoizes paths in the optimization's configuration space and predicts the trajectory of future optimization in real time, leveraging common continuity assumptions. This enables direct manipulation of formerly sluggish interactions. We demonstrate our approach on geometric fitting tasks. Additionally, we evaluate complementary mouse motion prediction algorithms as a means to discard or skip optimization problems that are irrelevant to the user's intended initial configuration for a targeted optimization procedure. Predicting where the mouse cursor will be located at the end of an operation, such as dragging a model of an engine component into scanned point cloud data to perform geometric alignment, allows us to pre‐emptively begin solving the targeted problem before the user finishes their movement. We take advantage of the fact that the prediction indicates the approximate energy basin the optimization procedure will need to explore.