“Minkowski Penalties: Robust Differentiable Constraint Enforcement for Vector Graphics”
Conference:
Type(s):
Title:
- Minkowski Penalties: Robust Differentiable Constraint Enforcement for Vector Graphics
Presenter(s)/Author(s):
Abstract:
We introduce a method for laying out complex arrangements of general, nonconvex 2D shapes in the context of vector graphics, illustration, and diagrams. Beyond simple “no-overlap” conditions, we introduce differentiable penalties for nested containment, tangency, precise padding, etc., which are robust even in the absence of problem-specific initialization strategies.
References:
[1]
Alon Baram. 2013. Polygonal Minkowski Sums Via Convolution: Theory and Practice. University of Tel-Aviv.
[2]
Mathieu Bastian, Sebastien Heymann, and Mathieu Jacomy. 2009. Gephi: An Open Source Software for Exploring and Manipulating Networks. Proceedings of the International AAAI Conference on Web and Social Media 3, 1 (Mar. 2009), 361?362. https://doi.org/10.1609/icwsm.v3i1.13937
[3]
Evan Behar and Jyh-Ming Lien. 2011. Fast and robust 2D Minkowski sum using reduced convolution. In 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. 1573?1578. https://doi.org/10.1109/IROS.2011.6094482
[4]
Michael A. Bekos, Benjamin Niedermann, and Martin N?llenburg. 2019. External Labeling Techniques: A Taxonomy and Survey. Comput. Graph. Forum 38, 3 (jun 2019), 833?860.
[5]
Robert Bridson, Sebastian Marino, and Ronald Fedkiw. 2005. Simulation of clothing with folds and wrinkles. In ACM SIGGRAPH 2005 Courses. 3?es.
[6]
Edwin Catmull and Raphael Rom. 1974. A class of local interpolating splines. In Computer Aided Geometric Design. Academic Press, 317?326. https://doi.org/10.1016/B978-0-12-079050-0.50020-5
[7]
He Chen, Elie Diaz, and Cem Yuksel. 2023. Shortest Path to Boundary for Self-Intersecting Meshes. arXiv preprint arXiv:2305.09778 (2023).
[8]
Jon Christensen, Joe Marks, and Stuart Merrill Shieber. 1992. Labeling point features on maps and diagrams. (1992).
[9]
Qiaodong Cui, Victor Rong, Desai Chen, and Wojciech Matusik. 2023. Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects. ACM Trans. Graph 42, 4 (2023).
[10]
David Dobkin, John Hershberger, David Kirkpatrick, and Subhash Suri. 1993. Computing the intersection-depth of polyhedra. Algorithmica 9, 6 (1993), 518?533.
[11]
Xingyi Du, Danny M Kaufman, Qingnan Zhou, Shahar Z Kovalsky, Yajie Yan, Noam Aigerman, and Tao Ju. 2021. Optimizing global injectivity for constrained parameterization.ACM Trans. Graph. 40, 6 (2021), 260?1.
[12]
Tim Dwyer. 2009. Scalable, Versatile and Simple Constrained Graph Layout. Comput. Graph. Forum 28, 3 (jun 2009), 991?998.
[13]
Sam Estep, Raven Rothkopf, Wode Ni, and Joshua Sunshine. 2024. Rose: Efficient and Extensible Autodiff on the Web. arxiv:2402.17743 [cs.PL]
[14]
Yu Fang, Minchen Li, Chenfanfu Jiang, and Danny M Kaufman. 2021. Guaranteed globally injective 3D deformation processing. ACM Transactions on Graphics 40, 4 (2021).
[15]
Guy Fargion and Ofir Weber. 2022. Globally Injective Flattening via a Reduced Harmonic Subspace. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1?17.
[16]
Erich Friedman. 2012. Packing unit squares in squares: A survey and new results. The Electronic Journal of Combinatorics (2012), DS7?Aug.
[17]
Shashidhara K Ganjugunte. 2007. A Survey on Techniques for Computing Penetration Depth. (2007).
[18]
Vladimir Garanzha, Igor Kaporin, Liudmila Kudryavtseva, Fran?ois Protais, Nicolas Ray, and Dmitry Sokolov. 2021. Foldover-free maps in 50 lines of code. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1?16.
[19]
Helen Gibson, Joe Faith, and Paul Vickers. 2013. A survey of two-dimensional graph layout techniques for information visualisation. Inf. Vis. 12, 3-4 (jul 2013), 324?357.
[20]
Leonidas Guibas and Raimund Seidel. 1986. Computing convolutions by reciprocal search. In Proceedings of the second annual symposium on Computational geometry. 90?99.
[21]
Hwei-Shin Harriman. 2021. Edgeworth: authoring diagrammatic math problems using program mutation. In Companion Proceedings of the 2021 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity. 22?24.
[22]
Stefan Hertel and Kurt Mehlhorn. 1983. Fast triangulation of simple polygons. In Foundations of Computation Theory, Marek Karpinski (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 207?218.
[23]
Markus Hohenwarter and Markus Hohenwarter. 2002. GeoGebra. Available on-line at http://www. geogebra. org/cms/en (2002).
[24]
Chen-Yuan Hsu, Li-Yi Wei, Lihua You, and Jian Jun Zhang. 2020. Autocomplete element fields. In Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems. 1?13.
[25]
Nathan Hurst, Wilmot Li, and Kim Marriott. 2009. Review of automatic document formatting. In Proceedings of the 9th ACM symposium on Document engineering. 99?108.
[26]
Eduard Imhof. 1975. Positioning names on maps. Am. Cartogr. 2, 2 (jan 1975), 128?144.
[27]
Mike Innes, Alan Edelman, Keno Fischer, Chris Rackauckas, Elliot Saba, Viral B Shah, and Will Tebbutt. 2019. A Differentiable Programming System to Bridge Machine Learning and Scientific Computing. arxiv:1907.07587 [cs.PL]
[28]
Alec Jacobson. 2021. personal communication.
[29]
Rijul Jain, Wode Ni, and Joshua Sunshine. 2023. Generating Domain-Specific Programs for Diagram Authoring with Large Language Models. In Companion Proceedings of the 2023 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity. 70?71.
[30]
Wenzel Jakob, S?bastien Speierer, Nicolas Roussel, and Delio Vicini. 2022. Dr. jit: A just-in-time compiler for differentiable rendering. ACM Transactions on Graphics (TOG) 41, 4 (2022), 1?19.
[31]
Paul A Jensen and Jonathan F Bard. 2002. Operations research models and methods. John Wiley & Sons.
[32]
Jill Phelps Kern and Cynthia A. Brewer. 2008. Automation and the map label placement problem: A comparison of two GIS implementations of label placement. Cartogr. Perspect.60 (2008), 22?45.
[33]
Young J Kim, Miguel A Otaduy, Ming C Lin, and Dinesh Manocha. 2002. Fast penetration depth computation for physically-based animation. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation. 23?31.
[34]
Sinan Kockara, Tansel Halic, Kamran Iqbal, Coskun Bayrak, and Richard Rowe. 2007. Collision detection: A survey. In 2007 IEEE International Conference on Systems, Man and Cybernetics. IEEE, 4046?4051.
[35]
Ulrich H Kortenkamp. 1999. Foundations of dynamic geometry. Ph. D. Dissertation. ETH Zurich.
[36]
In-Kwon Lee, Myung-Soo Kim, and Gershon Elber. 1998. Polynomial/rational approximation of Minkowski sum boundary curves. Graphical Models and Image Processing 60, 2 (1998), 136?165.
[37]
Wonyeol Lee, Hangyeol Yu, Xavier Rival, and Hongseok Yang. 2020. On correctness of automatic differentiation for non-differentiable functions. Advances in Neural Information Processing Systems 33 (2020), 6719?6730.
[38]
Raphael Linus Levien. 2009. From spiral to spline: Optimal techniques in interactive curve design. University of California, Berkeley.
[39]
Adrian Lewis and Michael L. Overton. 2009. Nonsmooth Optimization via BFGS. SIAM Journal on Optimization, 1?35.
[40]
Tzu-Mao Li, Michal Luk??, Gharbi Micha?l, and Jonathan Ragan-Kelley. 2020. Differentiable Vector Graphics Rasterization for Editing and Learning. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 39, 6 (2020), 193:1?193:15.
[41]
Yajuan Li, Meng Zhang, Wenbiao Jin, and Chongyang Deng. 2023. Approximating B?zier curves with least square polygons. The Visual Computer (2023), 1?10.
[42]
Dong C Liu and Jorge Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Mathematical programming 45, 1 (1989), 503?528.
[43]
Corie Lok. 2011. Biomedical illustration: From monsters to molecules. Nature 477, 7364 (2011), 359?361.
[44]
David G Luenberger, Yinyu Ye, 1984. Linear and nonlinear programming. Vol. 2. Springer.
[45]
Chongyang Ma, Li-Yi Wei, and Xin Tong. 2011. Discrete element textures. ACM Transactions on Graphics (TOG) 30, 4 (2011), 1?10.
[46]
Avraham Margalit and Gary D Knott. 1989. An algorithm for computing the union, intersection or difference of two polygons. Computers & Graphics 13, 2 (1989), 167?183.
[47]
Zo? Marschner, Silvia Sell?n, Hsueh-Ti Derek Liu, and Alec Jacobson. 2023. Constructive Solid Geometry on Neural Signed Distance Fields. In SIGGRAPH Asia 2023 Conference Papers(SA ?23). Association for Computing Machinery, New York, NY, USA, Article 121, 12 pages. https://doi.org/10.1145/3610548.3618170
[48]
Louis Montaut, Quentin Le Lidec, Antoine Bambade, Vladimir Petrik, Josef Sivic, and Justin Carpentier. 2023. Differentiable collision detection: a randomized smoothing approach. In 2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 3240?3246.
[49]
Louis Montaut, Quentin Le Lidec, Vladimir Petrik, Josef Sivic, and Justin Carpentier. 2022. Collision Detection Accelerated: An Optimization Perspective. In Robotics: Science and Systems.
[50]
William Moses and Valentin Churavy. 2020. Instead of Rewriting Foreign Code for Machine Learning, Automatically Synthesize Fast Gradients. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.). Vol. 33. Curran Associates, Inc., 12472?12485. https://proceedings.neurips.cc/paper/2020/file/9332c513ef44b682e9347822c2e457ac-Paper.pdf
[51]
Greg Nelson. 1985. Juno, a constraint-based graphics system. In Proceedings of the 12th annual conference on Computer Graphics and Interactive Techniques. 235?243.
[52]
Stanley Osher, Ronald Fedkiw, and K Piechor. 2004. Level set methods and dynamic implicit surfaces. Appl. Mech. Rev. 57, 3 (2004), B15?B15.
[53]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. d?Alch? Buc, E. Fox, and R. Garnett (Eds.). Curran Associates, Inc., 8024?8035. http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf
[54]
Hamid Rezatofighi, Nathan Tsoi, JunYoung Gwak, Amir Sadeghian, Ian Reid, and Silvio Savarese. 2019. Generalized Intersection Over Union: A Metric and a Loss for Bounding Box Regression. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). 658?666. https://doi.org/10.1109/CVPR.2019.00075
[55]
J?rgen Richter-Gebert, Ulrich H Kortenkamp, J?rgen Richter-Gebert, and Ulrich H Kortenkamp. 2012. Interactive Geometry with Cinderella. The Cinderella. 2 Manual: Working with The Interactive Geometry Software (2012), 67?152.
[56]
Leonardo Sacht, Etienne Vouga, and Alec Jacobson. 2015. Nested cages. ACM Transactions on Graphics (TOG) 34, 6 (2015), 1?14.
[57]
Reza Adhitya Saputra, Craig S Kaplan, and Paul Asente. 2018. RepulsionPak: Deformation-driven element packing with repulsion forces. In Proceedings of the 44th Graphics Interface Conference. 10?17.
[58]
Yury Semenov. 2020. Minkowski sum of convex polygons – Algorithms for Competitive Programming. https://cp-algorithms.com/geometry/minkowski.html
[59]
Jason Smith and Scott Schaefer. 2015. Bijective parameterization with free boundaries. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1?9.
[60]
Bert Speelpenning. 1980. Compiling fast partial derivatives of functions given by algorithms. University of Illinois at Urbana-Champaign.
[61]
Lavanya Subramaniam. 2003. Partition of a Non-Simple Polygon into Simple Polygons. Master?s thesis. University of South Alabama, Mobile, Alabama.
[62]
Guodao Sun, Zihao Zhu, Gefei Zhang, Chaoqing Xu, Yunchao Wang, Sujia Zhu, Baofeng Chang, and Ronghua Liang. 2023. Application of Mathematical Optimization in Data Visualization and Visual Analytics: A Survey. IEEE Trans. Big Data 9, 4 (aug 2023), 1018?1037.
[63]
Ivan E Sutherland. 1963. Sketchpad: A man-machine graphical communication system. In Proceedings of the May 21-23, 1963, spring joint computer conference. 329?346.
[64]
Roberto Tamassia. 2013. Handbook of graph drawing and visualization. CRC press.
[65]
Matthias Teschner, Bruno Heidelberger, Matthias M?ller, Danat Pomerantes, and Markus H Gross. 2003. Optimized spatial hashing for collision detection of deformable objects. In Vmv, Vol. 3. 47?54.
[66]
Kevin Tracy, Taylor A Howell, and Zachary Manchester. 2023. Differentiable collision detection for a set of convex primitives. In 2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 3663?3670.
[67]
Laurens van der Maaten and Geoffrey E. Hinton. 2008. Visualizing Data using t-SNE. Journal of Machine Learning Research 9 (2008), 2579?2605. https://api.semanticscholar.org/CorpusID:5855042
[68]
Marc van Kreveld and Tim Schlechter. 2005. Automated label placement for groups of islands. In Proc. of the 22nd International Cartographic Conference.
[69]
Delio Vicini, S?bastien Speierer, and Wenzel Jakob. 2022. Differentiable Signed Distance Function Rendering. Transactions on Graphics (Proceedings of SIGGRAPH) 41, 4 (July 2022), 125:1?125:18. https://doi.org/10.1145/3528223.3530139
[70]
Frank Wagner, Alexander Wolff, Vikas Kapoor, and Tycho Strijk. 2001. Three rules suffice for good label placement. Algorithmica 30 (2001), 334?349.
[71]
Ron Wein, Alon Baram, Efi Fogel, Eyal Flato, Michael Hemmer, and Sebastian Morr. 2023. CGAL 5.6 – 2D Minkowski Sums: User Manual. https://doc.cgal.org/5.6/Minkowski_sum_2/index.html
[72]
Lior Yariv, Jiatao Gu, Yoni Kasten, and Yaron Lipman. 2021. Volume rendering of neural implicit surfaces. In Thirty-Fifth Conference on Neural Information Processing Systems.
[73]
Lior Yariv, Peter Hedman, Christian Reiser, Dor Verbin, Pratul P. Srinivasan, Richard Szeliski, Jonathan T. Barron, and Ben Mildenhall. 2023. BakedSDF: Meshing Neural SDFs for Real-Time View Synthesis. arXiv (2023).
[74]
Katherine Ye, Wode Ni, Max Krieger, Dor Ma?ayan, Jenna Wise, Jonathan Aldrich, Jonathan Sunshine, and Keenan Crane. 2020. Penrose: From Mathematical Notation to Beautiful Diagrams. ACM Trans. Graph. 39, 4 (2020).
[75]
Chris Yu, Caleb Brakensiek, Henrik Schumacher, and Keenan Crane. 2021a. Repulsive Surfaces. ACM Trans. Graph. 40, 6 (2021).
[76]
Chris Yu, Henrik Schumacher, and Keenan Crane. 2021b. Repulsive curves. ACM Transactions on Graphics (TOG) 40, 2 (2021), 1?21.
[77]
Simon Zimmermann, Matthias Busenhart, Simon Huber, Roi Poranne, and Stelian Coros. 2022. Differentiable collision avoidance using collision primitives. In 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 8086?8093.
