Optimization of triangular networks with spatial constraints

Abstract

A common representation of a three dimensional object in computer applications, such as graphics and design, is in the form of a triangular mesh. In many instances, individual or groups of triangles in such representation need to satisfy spatial constraints that are imposed either by observation from the real world, or by concrete design specifications of the object. As these problems tend to be of large scale, choosing a mathematical optimization approach can be particularly challenging. In this paper, we model various geometric constraints as convex sets in Euclidean spaces, and find the corresponding projections in closed forms. We also present an interesting idea to successfully manoeuvre around some important non-convex constraints while still preserving the intrinsic nature of the original design problem. We then use these constructions in modern first-order splitting methods to find optimal solutions.

Keywords:

• Alignment constraint
• convex optimization
• Douglas–Rachford splitting
• maximum slope
• minimum slope
• oriented slope
• projection methods

AMS Subject Classifications:

• Primary: 26B25
• 65D17
• Secondary: 49M27
• 52A41
• 90C25

Acknowledgments

The authors are grateful to the Editors and two anonymous referees for their constructive suggestions that allow us to improve the original presentation.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 C is convex if for all $x,y\in C$ and $\lambda \in [0,1]$, we have $(1-\lambda )x+\lambda y\in C$.

2 See, e.g. [20] and [3] for relevant materials in convex analysis.

Additional information

Funding

This research is partially supported by Autodesk, Inc.