Minkowski Penalties: Robust Differentiable Constraint Enforcement for Vector Graphics

Jiří Minarčík	Sam Estep	Wode Ni	Keenan Crane

ACM SIGGRAPH 2024 Conference Proceedings (2024)

This paper describes an optimization-based framework for finding arrangements of 2D shapes subject to pairwise constraints. Such arrangements naturally arise in tasks such as vector illustration and diagram generation, but enforcing these criteria robustly is surprisingly challenging. We approach this problem through the minimization of novel energetic penalties, derived from the signed distance function of the Minkowski difference between interacting shapes. This formulation provides useful gradients even when initialized from a wildly infeasible state, and, unlike many common collision penalties, can handle open curves that do not have a well-defined inside and outside. Moreover, it supports rich features beyond the basic no-overlap condition, such as tangency, containment, and precise padding, which are especially valuable in the vector illustration context. We develop closed-form expressions and efficient approximations of our penalty for standard vector graphics primitives, yielding efficient evaluation and easy implementation within existing automatic differentiation pipelines. The method has already been “battle-tested” as a component of public-facing open source software; we demonstrate the utility of the framework via examples from illustration, data visualization, diagram generation, and geometry processing.

Paper

Jiří Minarčík, Sam Estep, Wode Ni, Keenan Crane (2024). Minkowski Penalties: Robust Differentiable Constraint Enforcement for Vector Graphics. ACM SIGGRAPH 2024 Conference Proceedings, 43(4).

@article{Minarcik:2024:MPR,
author = {Jiří Minarčík and Sam Estep and Wode Ni and Keenan Crane},
title = {Minkowski Penalties: Robust Differentiable Constraint Enforcement for Vector Graphics},
journal = {ACM SIGGRAPH 2024 Conference Proceedings},
volume = {43},
number = {4},
year = {2024},
publisher = {ACM},
address = {New York, NY, USA},
}