Here’s the video to go along with our paper, Smooth Shape-Aware Functions with Controlled Extrema, that we’ll present at SGP 2012.
Posts Tagged ‘geometry’
I put up a project page for our new paper that we’ll present at SGP (Symposium of Geometry Processing) this month. The paper’s called, “Smooth Shape-Aware Functions with Controlled Extrema” and it’s a collaboration between me, my advisor, Olga Sorkine and my ex- officemate at NYU Tino Weinkauf, who’s now at MPI in Saarbrucken.
Functions that optimize Laplacian-based energies have become popular in geometry processing, e.g. for shape deformation, smoothing, multi scale kernel construction and interpolation. Minimizers of Dirichlet energies, or solutions of Laplace equations, are harmonic functions that enjoy the maximum principle, ensuring no spurious local extrema in the interior of the solved domain occur. However, these functions are only C0 at the constrained points, which often causes smoothness problems. For this reason, many applications optimize higher-order Laplacian energies such as biharmonic or triharmonic. Their minimizers exhibit increasing orders of continuity but also increasing oscillation, immediately releasing the maximum principle. In this work, we identify characteristic artifacts caused by spurious local extrema, and provide a framework for minimizing quadratic energies on manifolds while constraining the solution to obey the maximum principle in the solved region. Our framework allows the user to specify locations and values of desired local maxima and minima, while preventing any other local extrema. We demonstrate our method on the smoothness energies corresponding to popular polyharmonic functions and show its usefulness for fast handle-based shape deformation, controllable color diffusion, and topologically-constrained data smoothing.
We decided to write up a quick, 2 page technical report about some ideas we’ve had in the last year.
By embedding images as surfaces in a high dimensional coordinate space defined by each pixel’s Cartesian coordinates and color values, we directly define and employ cotangent-based, discrete differential-geometry operators. These operators define discrete energies useful for image segmentation and colorization.
I’ve finally released the matlab prototyping codebase for Bounded Biharmonic Weights. The code base runs without any prerequisite libraries on MATLAB 2011a or greater. With earlier versions of matlab, users should install MOSEK (which is available for free to academic users).
This matlab package demos computing skinning weights automatically for a 2d shape. To start, add
bbw_demo/ to your matlab path and issue:
If you just want to start digging around in the weight computation code, look
bbw_demo.m file just shows basic weight computation and linear blend skinning deformation for point handles. The following features are supported in the codebase above, but are undocumented besides their file header comments:
- Bone handles
- Cage edges
- Dual quaternion skinning
- Automatic rotations at point handles via pseudo-edges
- 3D weight computation over tetrahedral meshes
- 2D/3D remeshing along bones and cage edges
- …and more
The following things are not supported and probably never will be in the MATLAB demo. If I release the C++ demo then of course they will be available:
I’m always re-deriving the matrix notation of common triangle mesh energies like the Dirichlet energy, Laplacian energy, or local rigidity energy. Here’s my usual strategy. I’ll assume that if your energy came from a continuous integral you can at least get it to a sum over mesh elements. Here I write my sums over vertices and their neighbors, but surely you could also sum over triangles.
Uglier plain text, unicode version:
∑i∑j∈N(i) vi = ∑i * #N(i) * v = VT * D * 1, where D is diagonal with Dii = #N(i) ∑i∑j∈N(i) vj = VT * A * 1, where A is the adjacency matrix ∑i∑j∈N(i) vi - vj = VT * D * 1 - VT * A * 1 = VT * (D-A) * 1 ∑i∑j∈N(i) wij = 1 * Aw * 1, where Aw adjacency with Awij = wij, if j∈N(i) ∑i∑j∈N(i) wij*vi = ∑i vi * ∑j∈N(i) wij = VT * Dw * 1, where Dw diagonal with Dwii = ∑j∈N(i) wij ∑i∑j∈N(i) wij*vj = VT * Aw * 1 ∑i mi * ∑j∈N(i) wij vi = ∑i mi * vi * ∑j∈N(i) wij = VT * M * Dw * 1, where M is diagonal with Mii = wi ∑i mi * ∑j∈N(i) wij vj = VT * Aw * M * 1 ∑i∑j∈N(i) vi² = VT * D * V ∑i∑j∈N(i) vivj = VT * A * V ∑i∑j∈N(i) vj² = VT * RD * V, where RD is diagonal, RDjj = ∑i 1 if j∈N(i) if j∈N(i) implies i∈N(j) then D = RD so ∑i∑j∈N(i) vj² = ∑i∑j∈N(i) vi² = VT * D * V ∑i∑j∈N(i) (vi - vj)² = ∑i∑j∈N(i) vi² - 2 * ∑i∑j∈N(i) vivj + ∑i∑j∈N(i) vj² = 2 * ∑i∑j∈N(i) vi² - 2 * ∑i∑j∈N(i) vivj = 2 * VT * D * V - 2 * VT * A * V = 2 * VT * (D - A) * V = 2 * VT * L * V ∑i∑j∈N(i) wij*vi² = ∑i vi² * ∑j∈N(i) wij = VT * Dw * V ∑i∑j∈N(i) wij*vivj = VT * Aw * V ∑i∑j∈N(i) wij*vj² = VT * RDw * V, where DW is diagonal, RDwjj = ∑i wij if j∈N(i) if j∈N(i) implies i∈N(j) and wij = wji then Dw = RDw so ∑i∑j∈N(i) wij*vj² = ∑i∑j∈N(i) wij*vi² = VT * Dw * V ∑i∑j∈N(i) wij(vi - vj)² = = ∑i∑j∈N(i) wij*vi² - 2 * ∑i∑j∈N(i) wij*vivj + ∑i∑j∈N(i) wij*vj² = 2 * ∑i∑j∈N(i) wij*vi² - 2 * ∑i∑j∈N(i) wij*vivj = 2 * VT * Dw * V - 2 * VT * Aw * V = 2 * VT * (Dw - Aw) * V = 2 * VT * Lw * V ∑i mi * ∑j∈N(i) wij vi² = ∑i mi * vi² * ∑j∈N(i) wij = VT * M * Dw * V ∑i mi * ∑j∈N(i) wij vj² = VT * RDw * M * V ∑i mi * ∑j∈N(i) wij vivj = VT * Aw * M * V ∑i mi * ∑j∈N(i) wij(vi - vj)² = = ∑i mi * ∑j∈N(i) wij*vi² - 2 * ∑i mi * ∑j∈N(i) wij*vivj + ∑i mi *∑j∈N(i) wij*vj² = 2 * ∑i mi * ∑j∈N(i) wij*vi² - 2 * ∑i mi * ∑j∈N(i) wij*vivj = 2 * VT * M * Dw * V - 2 * VT * Aw * M * V = 2 * VT * M * (Dw - Aw) * V = 2 * VT * M * Lw * V Note: let wij = cwij = cot(αij) + cot(βij) / mi and let mi = voronoi area at vi, then the familar cotangent form of the discrete Dirichlet energy is EDirichlet = 2 * VT * M * Lcw * V
Daniele Panozzo, Olga Sorkine, and I are beginning a new collaboration with Cédric Pradalier of the Autonomous Systems Lab here at ETH Zurich. We’re hosting a masters thesis project.
The project, entitled Design of a modular character animation tool is now available, and we are eagerly awaiting applications. In this thesis you will design and produce an innovative input device for interactive animation of virtual 3D characters. The device will consist of a skeleton that will imitate the structure of the character the user wants to animate. The device will be constructed of modular bones and joints which may be rearranged and repositioned on the fly. Movements of the device will be registered with the animation system and will result in corresponding movements of the virtual character. The project will present novel mechanical and electronic challenges, and will be developed in collaboration with the Interactive Geometry Lab. We will provide the required mesh processing software components. This innovative interface will improve the animation workflow used in the videogame and film industry, which by and large relies solely on keyboard and mouse interaction. A fully modular puppet, which could take the form of any character or shape, would not only present a novel interface but also provide a research instrument for evaluating human perception of 3D and 2D poses.
Please don’t hesitate to contact me for extra details.
Recently I began looking into tet-meshes again. Some colleagues and I were trying to wrap our heads around how many tetrahedra result from splitting up a triangular prism. we were trying to draw out the cases on the white board. Occasionally some one would say, “I’m sure it’s 3.” Then somebody else would draw another set of pictures and’d say “No, I’m sure it’s 4″.
Well, to have a definitive answer, a triangular prism may be split into three tetrahedra. If you don’t believe me, see the nice description (which actually lists all possible splits) in “How to Subdivide Pyramids, Prisms and Hexahedra into Tetrahedra” by J. Dompierre et al. in 1999. There is another interesting discussion in “Space-filling Tetrahedra in Euclidean Space” by D.M.Y. Sommerville in 1923, in which they consider the conditions under which these tetrahedra are congruent.
Ken recently posted about shapes that suggest math problems. At the end of his post he leaves a riddle:
Find a shape whose area is 1/2 the area of a square and whose perimeter is the same as the perimeter of the square.
Thinking about this riddle a little bit got me thinking about other similar riddles. Like what if I ask the same question but instead of a square use a circle.
Find a shape whose area is 1/2 the area of a circle and whose perimeter is the same as the perimeter of the circle.
My idea for a solution for this new riddle was to intersect to equal-size circles. Notice as long as the circles are equal size if I take the shape that’s one of the circles minus the other circle, the perimeter will be the same as a full circle.
So then I just need to find how far apart the circles should be. I know that if the distance between the circles’ centers is zero then the left over shape will have area zero. And if the distance is twice their radii then then the left over area will be equal to a full circle. So if I want the left over area to be half the area of a circle I need the distance to be somewhere between zero and twice the radii.
I wrote out the algebra blindly hoping that the equations would collapse leaving me with a beautiful, succinct expression for the necessary distance. The problem turns out to be fairly intangible. Leaving me with a gnarly expression for the distance that is not easily solved. Here’s a picture and the expression:
I can approximate d numerically, which reveals d ≈ 0.8079455066. I’m not the first person to try this, this problem also makes an appearance on the Wolfram circle-circle intersection page.
This leaves me wondering if there is a simpler answer to my riddle. Maybe the solution doesn’t involve circle-circle intersection at all!
My colleagues, Ilya Baran, Jovan Popović, Olga Sorkine, and I have just submitted the camera ready version of paper “Bounded Biharmonic Weights for Real-Time Deformation” to be presented at ACM SIGGRAPH 2011. I’ve put up a bounded biharmonic weights project page where you can find the preprint version of the article, videos and more to come.
Bounded biharmonic weights are featured in the official SIGGRAPH 2011 Technical Papers Advance Preview. The Technical Papers Chair, Hugues Hoppe, writes:
“An elegant UI framework that unifies cages, skeletons, and point constraints for 2D and 3D deformations.”
Object deformation with linear blending dominates practical use as the fastest approach for transforming raster images, vector graphics, geometric models and animated characters. Unfortunately, linear blending schemes for skeletons or cages are not always easy to use because they may require manual weight painting or modeling closed polyhedral envelopes around objects. Our goal is to make the design and control of deformations simpler by allowing the user to work freely with the most convenient combination of handle types. We develop linear blending weights that produce smooth and intuitive deformations for points, bones and cages of arbitrary topology. Our weights, called bounded biharmonic weights, minimize the Laplacian energy subject to bound constraints. Doing so spreads the influences of the controls in a shape-aware and localized manner, even for objects with complex and concave boundaries. The variational weight optimization also makes it possible to customize the weights so that they preserve the shape of specified essential object features. We demonstrate successful use of our blending weights for real-time deformation of 2D and 3D shapes.
Here’s a matlab function that takes a list of tetrahedron indices (4 indices to a row) and finds the triangles that are on the surface of the volume. It does this simply by finding all of the faces that only occur once.
function F = boundary_faces(T) % BOUNDARY_FACES % F = boundary_faces(T) % Determine boundary faces of tetrahedra stored in T % % Input: % T tetrahedron index list, m by 4, where m is the number of tetrahedra % % Output: % F list of boundary faces, n by 3, where n is the number of boundary faces % % get all faces allF = [ ... T(:,1) T(:,2) T(:,3); ... T(:,1) T(:,3) T(:,4); ... T(:,1) T(:,4) T(:,2); ... T(:,2) T(:,4) T(:,3)]; % sort rows so that faces are reorder in ascending order of indices sortedF = sort(allF,2); % determine uniqueness of faces [u,m,n] = unique(sortedF,'rows'); % determine counts for each unique face counts = accumarray(n(:), 1); % extract faces that only occurred once sorted_exteriorF = u(counts == 1,:); % find in original faces so that ordering of indices is correct F = allF(ismember(sortedF,sorted_exteriorF,'rows'),:); end
With this you can easily determine the vertices of a tetmesh that are on the boundary:
% V are your vertex positions, T are your tet indices % get boundary faces F = boundary_faces(T); % get boundary vertices b = unique(F(:)); subplot(1,2,1); % plot boundary positions plot3(V(b,1),V(b,2),V(b,3),'.'); subplot(1,2,2); % plot just boundary faces trisurf(F,V(:,1),V(:,2),V(:,3),'FaceAlpha',0.3)