In what kinds of graphics problems does "energy minimization" come into play? And what about quadratic form makes it suited to these kinds of problems?
keenan
@phazan We'll talk about this a bit tomorrow (and in more detail later in the semester), but basically the idea is that any (smooth) multivariable function $f(\mathbf{x})$ you want to minimize can be locally approximated by a Taylor series whose first three terms are
where $\nabla f$ is the gradient and $\nabla^2 f$ is the Hessian. In other words, we approximate the objective function by a constant, a linear part, and a quadratic part (quadratic form). The reason we stop at the quadratic term is that now various optimization tasks can be framed in terms of linear systems involving the Hessian (which are easy to solve).
As for which graphics problems use energy minimization... there are a lot! A typical setting is that there are some constraints we want to satisfy, but we can't satisfy all of them exactly. So, one might minimize the deviation from satisfying the constraints, which becomes the "energy." This could be anything from, say, constraints in a rigging system (e.g., a character or robot wants to find a pose that satisfies several constraints), or fitting a model of light scattering to measured data.
ky
@phazan Here's a cool graphics paper that uses energy minimization and quadratic programming: "Procedural Modeling of Structurally-Sound Masonry Buildings" (http://www.cs.dartmouth.edu/~emily/resources/pubs/WhitingOchsendorfDurand-09.pdf)
They procedurally generate buildings that are stable using only masonry (that is, friction from stacking blocks). They could state "is this structure stable?" as a quadratic program of certain constraints. But that quadratic program might not be solvable. So this paper's contribution is to use a slightly different set of constraints to define a measure to quantify how unstable the structure is. Then they can define an energy function and use a gradient-descent-like method to find the parameters that maximize stability of the procedurally generated building.
(This explanation may not be 100% right because I didn't read the whole paper :))
rajas139
Is there also an important application of energy minimization, when we want find correspondence between two different geometric shapes? For example, we can minimize the distances between two corresponding points in the shape. This is a quadratic function which can be written as an energy functional, which can be minimized.
keenan
@rajas139 Yes, energy minimization is definitely an approach people use to compute geometric correspondence. Sadly, however, none of these energies are as simple as just a single quadratic form; they are all far more nonlinear, requiring sophisticated optimization techniques. But this is a very active area of research, with a lot of nice developments each year. See for instance this survey on shape correspondence (which is already six years old! Lots of developments even since then).
In what kinds of graphics problems does "energy minimization" come into play? And what about quadratic form makes it suited to these kinds of problems?
@phazan We'll talk about this a bit tomorrow (and in more detail later in the semester), but basically the idea is that any (smooth) multivariable function $f(\mathbf{x})$ you want to minimize can be locally approximated by a Taylor series whose first three terms are
$$ f(\mathbf{x}) = f(\mathbf{x}_0) + \langle \nabla f(\mathbf{x}_0), \mathbf{x} - \mathbf{x}_0 \rangle + \langle \nabla^2 f(\mathbf{x}_0) (\mathbf{x} - \mathbf{x}_0), (\mathbf{x} - \mathbf{x}_0) \rangle $$
where $\nabla f$ is the gradient and $\nabla^2 f$ is the Hessian. In other words, we approximate the objective function by a constant, a linear part, and a quadratic part (quadratic form). The reason we stop at the quadratic term is that now various optimization tasks can be framed in terms of linear systems involving the Hessian (which are easy to solve).
As for which graphics problems use energy minimization... there are a lot! A typical setting is that there are some constraints we want to satisfy, but we can't satisfy all of them exactly. So, one might minimize the deviation from satisfying the constraints, which becomes the "energy." This could be anything from, say, constraints in a rigging system (e.g., a character or robot wants to find a pose that satisfies several constraints), or fitting a model of light scattering to measured data.
@phazan Here's a cool graphics paper that uses energy minimization and quadratic programming: "Procedural Modeling of Structurally-Sound Masonry Buildings" (http://www.cs.dartmouth.edu/~emily/resources/pubs/WhitingOchsendorfDurand-09.pdf)
They procedurally generate buildings that are stable using only masonry (that is, friction from stacking blocks). They could state "is this structure stable?" as a quadratic program of certain constraints. But that quadratic program might not be solvable. So this paper's contribution is to use a slightly different set of constraints to define a measure to quantify how unstable the structure is. Then they can define an energy function and use a gradient-descent-like method to find the parameters that maximize stability of the procedurally generated building.
(This explanation may not be 100% right because I didn't read the whole paper :))
Is there also an important application of energy minimization, when we want find correspondence between two different geometric shapes? For example, we can minimize the distances between two corresponding points in the shape. This is a quadratic function which can be written as an energy functional, which can be minimized.
@rajas139 Yes, energy minimization is definitely an approach people use to compute geometric correspondence. Sadly, however, none of these energies are as simple as just a single quadratic form; they are all far more nonlinear, requiring sophisticated optimization techniques. But this is a very active area of research, with a lot of nice developments each year. See for instance this survey on shape correspondence (which is already six years old! Lots of developments even since then).