Matlab Mesh Toolkit

Downloads: Source Code (Matlab) [ZIP]


What is this?

This toolkit is a sandbox for mesh and point set processing in Matlab.

Matlab is a mixed bag for geometry processing. The built-in libraries provide lots of great support if you want to do things like solve linear systems and minimize energies, and since Matlab is so ubiquitous in machine learning it is easy to get code for all sorts of complicated things. The interactive environment is also great for rapid prototyping and experimentation.

Unfortunately, matlab is not particularly suitable for working with large arbitrary graphs (ie meshes). Explicit loops and branching are ridiculously slow, so efficient code often takes the form of cryptic, "write-only" statements that only matlab gurus will be able to understand.

Even text parsing is abysmally slow. Perhaps the most useful feature of this package is that the OBJ loader automatically creates binary caches. The first time you load your OBJ will be slow, after that it will be instantaneous. The package
also supports useful basic mesh operations like:

  • extracting a submesh copy with a map back to the base mesh
  • plotting meshes in various ways
  • picking faces and vertices
  • interrogating meshes (one rings, areas, edges, boundary loops, etc)

I use this package for prototyping and experimentation, so my goal has been clarity over efficiency. To that end, I have written many convenience functions which, in my opinion, make the code vastly more readable. For example, you can compute the magnitude of vector X using:

rather than the more cryptic (and longer):
And vmag() automatically computes per-row magnitudes if X is a list.

Similarly, adding a vector v to one or more points X is:
instead of
X + repmat(v,size(X,1),1)

Where possible, the utility functions will automatically handle lists of elements, arbitrary dimension, and sometimes even ordering (for exmaple the matrix-vector multiply mulv produces the same output vector regardless of whether v is a row or column vector)

In terms of higher-order geometry processing, there are implementations of various algorithms presented in the literature, such as:

  • vertex weights (cotangent, authalic, mean-value, voronoi area-weighting, and my own unpublished techniques based on discrete exponential maps)
  • laplace-beltrami operators and analysis (based on above)
  • planar parameterization (MIPS, standard fixed-boundary linear techniques, natural conformal, spectral conformal, variants of dimensionality reduction techniques from machine learning, discrete exponential map, and my own combinations of these techniques)
  • mesh deformation (Laplacian, Poisson, Rotation-Invariant Coordinates)
  • mesh fairing (implicit laplacian, second-order mean curvature)

See the documentation below for specifics and references.

Various sample meshes and point sets are included in the \data subdirectory, and lots of sample code in the various test files and the misc\ subdirectory (which contains exploratory code that was the basis for some unpublished work).

There is mex used here and there, and some external dependencies used in some of the sample/testing code. You may have to jump through some hoops to get those to work on your computer. Good luck!


 - Installation / Setup
 - Data Structures
 - 2D/3D Geometry
 - Mesh and Point Set Support
 - Mesh Fairing
 - Planar Parameterization
 - Mesh Deformation
 - Miscellany
 - Sample Meshes and Point Sets
 - Mex
 - Credits, Copyright Notices, etc
 - Citations


This toolkit contains several subdirectories, and will not work
properly unless they are all in your paths. The best way to deal
with this is to have matlab automatically add the necessary paths
on startup. 

On windows, you can automatically add the paths by inserting
the following commands in the startup file stored at
\MATLAB\startup.m (create if it does not exist):


(where 'c:\path\to\matlab' is the path to the package root). 

If you do not have it already, I strongly recommend downloading
Tom Minka's excellent lightspeed package:


Matlab doesn't really do explicit data structures. I use a
struct for meshes (see below) but vectors are just arrays.
The code in this package assumes that:

	- Points and Vectors are (1xd) matrices
	- lists of points/vectors are (Mxd) matrices  (M rows x d columns)

So, stick with that.



	%% basic geometric computations

		- angular distance between two 2D points
		- return Nth returned argument of f(varargin)
		- cartesian/spherical-coords conversion consistent with Mathematica
		- cartesian/spherical-coords conversion consistent with mathworld, graphics papers, etc
		- clamp value to range [min,max]
		- 2D cross product x1*y2 - x2*y1
		- compute scaled error using p-norm
		- find k-nearest nbrs for each input point
		- generate random points in 2D using varions strategies:
			%       'grid_unit_square' - regular-grid in [0,1]^(dim==2)
			%       'stratified_unit_square' - jittered 'grid_unit_square'
			%       'uniform_unit_square' - uniform random samples in [0,1]^dim		
		- multiply row-vectors v by matrix M and return row-vector
		- compute normalized cross-product
		- compute numerical gradient approximation
		- normalize rows of M. If magnitude is 0, skip vector
		- compute 2D perpendicular vector (-y,x)
		- create orthogonal tangent vectors to normal
		- adds v to each row of M
		- compute angle between vectors A and B
		- compute cotan of angle between n-D vectors A and B
		- returns vector of dot products of rows of M and M2. If M2 is a 
		  single row, expands to # of rows in M
		- compute magnitude of rows in M
		- compute sqiared magnitude of rows in M
		- matrix/vector multiplication (produces same result whether vector
		  is row or column)

	%% triangle geometry
		- area of triangle defined by 3 points
		- signed area of triangle defined by 3 2D points
		- compute barycentric basis function gradients for a triangle
		- face normal of triangle
		- return 1 if any triangle angles are obtuse
		- pick [j,k] != i from face, preserving cw/ccw ordering
		- pick [k] != i,j from face
	%% transformations
		- construct 3x3 rotation matrix around arbitrary axis
		- generate matrix that rotates vector vfrom into vector vto

	%% matrix constraints (probably should go elsewhere)
		- test if matrix is symmetric with epsilon tolerance
		- add hard constraints to linear system via rewriting
		- solve linear system M.X-B with hard constraints
		- add soft constraints to linear system
     [*] matlab and mex implementations of Dijkstra's algorithm

	[draw*.m] convenience 2D drawing routines for circle, line, point, polyline
	[TESTS.m] testing code

	[circle2_2pr.m] find circle center from 2 points and radius
	[isect_line2_circle2.m] intersect 2D line with circle 
	[turningNumber.m] compute integer turning number of closed polygon
	[sphereNormCoords.m] compute analytic (u,v) normal coordinates on sphere

	[implicitPlane.m] signed distance to plane
	[implicitSphere.m] signed distance to sphere
	[thinPlateSpline.m] solve and evaluate 2D sqr(n)log(n) thin-plate spline interpolant
					    for sparse constraints (current code evaluates over grid)
	[test\*.m] testing code for above


	%% input/output/datastructure creation

		- Read OBJ meshes with optional binary caching (much faster on second read)
		- Read OBJ-style pointset with optional binary caching
		- write mesh datastructure in OBJ format
		- create mesh from vertex and face lists, optionally with normals and uv's. Output:
			% mesh.v = Nx3 list of vertices
			% mesh.n = Nx3 list of vertex normals
			% mesh.u = Nx2 list of vertex uv's
			% mesh.f = Mx3 list of triangles
			% mesh.fn = Mx3 list of triangle face normals
			% mesh.vidx = Nx1 list of vertex indices (useful for various things)
			% mesh.fidx = Nx1 list of face indices (useful for various things)
			% mesh.bounds = [min;max;center] bounding box
			% mesh.e = symmetric sparse array of edges
			%             mesh.e(i,j) = 1 if boundary edge, 2 if interior edge
			% mesh.te = sparse array of edge triangles
			%             mesh.e(i,j) = tri1, mesh.e(j,i) = tri2
			%             for boundary tri, one of these will be 0...
			% mesh.loops = boundary loops of mesh
			% mesh.valence = valence of each vertex of mesh
			% mesh.isboundaryv = 0/1 flags for boundary vertices
			% mesh.isboundaryt = 0/1 flags for boundary triangles
		- create point set from list of points, with optional normals, uvs, colors. Output:
			% pointset.v = Nx3 list of vertices
			% pointset.n = Nx3 list of vertex normals
			% pointset.u = Nx2 list of vertex uv's
			% pointset.vidx = Nx1 list of vertex indices (useful for various things)
			% pointset.bounds = [min;max;center] bounding box
			% pointset.e = symmetric sparse array of edges
			%             pointset.e(i,j) = |v_j-v_i| if connected, 0 otherwise
			% pointset.valence = valence of each vertex of pointset
		- create submesh from face roi (also returns vertex and face maps)
		- remove 'ear' triangles from mesh (ie tris with only 1 nbr)
		- generate consistent orientation for 2D mesh triangles	
		- compute integer hash code to identify mesh
				(this is a hack and probably not very good hash...)
	%% display
		- display mesh data in many ways based on flag set:
			%   'v' = draw vertex points
			%   'e' = draw triangle edges
			%   'b' = draw boundary edges
			%   'n' = draw normals
			%   'f' = draw filled faces
			%   'l' = apply lighting to faces
			%   'u' = use uv-values as vertices
			%   'U' = use uv-values as vertices, and try to consistently-orient/scale plots
			%   'i' = plot vertex indices (numbers)  ** WARNING: very slow 
			%   'O' = pretty-plot for output (thicker lines, etc)
		- display mesh using external viewer program view3D.exe (in external)
		- display pointset in various ways based on flag set:
			%   'v' = draw vertex points
			%   'n' = draw normals
			%   'u' = use uv-values as vertices
			%   'U' = use uv-values as vertices, and try to consistently-orient/scale plots
			%   'i' = plot vertex indices (numbers)  ** WARNING: very slow 
			%   'O' = pretty-plot for output (thicker lines, etc)	
		- display 2D/3D polyline
	%% selection/picking	   
		- select vertices or faces of mesh using implicit function
		- interactive selection of vertex of mesh
		- finds nearest vertex to input point

	%% interrogation

		- estimate normals using given strategy ( face average, area-weighted face avg )
		- compute face normals
		- compute area of mesh faces
		- compute face area of ROI of mesh
		- compute mapped color values for mesh faces
		- compute min/max/avg edge lengths for given connectivity graph
		- find vertex one-ring vertices and triangles (supports ccw sorting)
		- return indices of one-ring faces at nVertex
		- return indices of one-ring vertices at nVertex
		- extract set of boundary loops from estimated set of 
		  boundary vertices, using either 3D or UV coordinates (right?)

	%% approximate/differential properties

		- compute area for a vertex on mesh using various methods:
			%     'uniform' - area = 1   
			%     'onering' - sum of areas of one-ring triangles
			%     'voronoi' - voronoi areas from [Meyer02]  (invalid for obtuse triangles)
			%     'mixed'   - mixed voronoi/geometric areas from [Meyer02]		
		- estimate area for a point of a pointset using various methods:
			%     'uvVoronoi' - voronoi cell area in UV-space
			%     'uvDelArea' - full delaunay area in UV-space
			%     'uvDelAreaR' - delaunay area within radius
			%     'uvDelRing' - delaunay one-ring area in UV-space
		- one-ring cotangent weights, optinally compute authalic and/or
			triangle area-weighted [Desbrun02, Meyer02, Mullen08]
		- one-ring mean value weights [Floater04]
		- compute vertex laplacian vectors (using uniform or cotangent weights)
		- Mean Curvature estimation techniques, including [Moreton92] Mean Curvature Estimation 
		  w/ [Schneider01] improvement for low-valence vertices, and [Meyer02] discrete cotangent

		- implmentation of [Schneider01] intrinsic mesh fairing
		- implicit fairing by solving for zero-length Laplacian vectors
		    (ie minimal mean-curvature surface)
		- explicit Laplacian fairing (currently using uniform weights)
	    - tests for above functions

		 - solve for laplacian deformation problem [Lipman04], given dense 
		   per-vertex rotations and sparse soft vertex position constraints
		 - solve Poisson deformation problem, given dense per-vertex 
		   rotations and sparse *hard* vertex constraints
		 - solve Rotation-Invariant Coordinates deformation problem [Lipman05], 
		   given sparse soft vertex position and orientation constraints
		- [Lipman04] Laplacian mesh deformation (iterative rotation estimation)
		 - simple Laplacian deformation with soft vertex position constraints,
		   with optional postprocess to align to target normal field
		 - (partial, possibly incorrect) implementation of [Yu04] Poisson mesh deformation.
			input is mesh, boundary constraint points, and transformed versions
			of input triangles

		- testing/sample code for above deformations

	%% embeddings

		- parameterize mesh using MIPS iterative nonlinear technique [Hormann00]
		- compute natural conformal parameterization (DNCP) from [Desbrun02]
		- compute spectral parameterization using various techniques
		  (basically [Mullen02] with some variants...)
		- variant of [Mullen02] that can be applied to point sets
		- spectral parameterization based on Locally-Linear Embedding (LLE) [Roweis02]
		- spectral parameterization based on Laplacian Eigenmaps (LEM) [Belkin03]
		- embed boundary of mesh in 2D polygon (currently only circle via arc-length)
		- solve for parameterization given boundary constraints and weight matrix,
		  with optional additional position constraints
	 %% vertex weights
		- compute per-vertex weights based on euclidean ball nbrhoods
				(uniform, invdist, invdist2, gaussian heat-kernel)
		- compute per-vertex weights based on geodesic/DEM nbrhoods
			(uniform, uniform on connected tangent-space delaunay,
			 invdist, [Roweis02] optimal, optimal in UV,
			 heat-kernel gaussian, heat-kernel gaussian in UV)
		- compute per-vertex weights based on K-nbrhoods
			(uniform, invdist, invdist2, heat-kernel gaussian)
		- compute per-vertex weights based on mesh one-ring nbrhoods
			(uniform, invdist, invdist^2, [Desbrun02] discrete conformal,
			 [Desbrun02] discrete authalic, [Floater04] mean value,
			 [Roweis02] optimal, optimal in UV) with optional area-weighting
			 (uniform, one-ring area, [Meyer02] mixed voronoi)
	%% exponential-map tangent space coordinates
		- compute Discrete Exponential Map (DEM) [Schmidt06] with upwind-average
		  extension [Schmidt10]
		- compute DEM for each mesh vertex using external binary expmapCL.exe
		- compute tangent space coords for one-ring of mesh vertex based
		  on angle mapping
	%% distortion metrics
		- compute conformal, dirichlet energy of mesh+vtxweights
		- compute per-face dirichlet or quasi-conformal distortion
		- compute uv angle/area distortion for triangles
		- compute [Sander02] per-triangle uv stretch metrics L2,Linf
		- compute area, angle, L2, Linf metrics for mesh
		- compute conformal energy based on weightmatrix and paramtype params
	%% sample/testing code
	[TESTS\*.m] various testing code

	%% external algorithms (mainly machine-learing dimensionality reduction codes)
		[csdp.exe] constrained semidefinite problem solver
		[lle.m] code from [Roweis02] for LLE
		[ltsa.m] implementation of LTSA (Zhenyue Zhang & Hongyuan Zha, 2004)
		[mani.m] manifold learning demonstration GUI
				 by Todd Wittman, Department of Mathematics, University of Minnesota
		[LEigenmaps.m] function for Laplacian eigenmap
					   Written by Belkin & Niyogi, 2002
		[HessianLLE.m] implementation of HLLE
					   Written by David Donoho & Carrie Grimes, 2003
			[Isomap.m]   implementation of Isomap algorithm [Tenenbaum00]
				- uses Floyd's algorithm to estimate geodesics
			[IsomapII.m] implementation of sparse landmark-Isomap algorithm  
				- uses Dijkstra's algorithm if available (in util\external)
			[*] support files
			[mvu.m]  implementation of Maximum-Variance Unfolding (MVU)
			[*] support files
			- binary command-line DEM computation. supplied pre-compiled for win32,
			  if you need to rebuild or port, download source from:



     global settings for versions/paths/etc
	     'meshVersion': version for mesh cache format
		 'pointsetVersion': same, for pointset cache format
		 'cachePath': place cache files can be stored (current config\cache)
		 'enableMeshCaching': default 1
		 'enableWeightMatrixCaching': default 0

  [EG09_WeightTests.m] analysis of vertex weight distributions
  [EG10_LNLE.m] various techniques for spectral parameterization of meshes & point clouds
        ( most of the code used in [Schmidt09] )
  [SGP09.m] various embedding strategies using DEM-weights (precursor to files above)
  [SGP10.m] analysis of eigenspectrum of laplace-beltrami operators,
            comparison of DEM vs analytic normal coords on hemisphere
  [SGP10_expmap.m] more comparison of DEM vs analytic normal coords on hemisphere
  [SGP09_LBTests.m] analysis of various mesh/pointset laplace-beltrami operators on plane
  [SGP10_lb.m] analysis of various mesh/pointset laplace-beltrami operators on sphere
    **NOTE** above files contain analytic l-b functions for various functions on plane/sphere,
	         which I got via mathematica. Code for generating these solutions is in

  [figures\*.m] Code to generate the figures in the tech report [Schmidt09]


    [*.obj] misc OBJ files used in testing code, etc
	[armadilloman_tiny.obj] 75-vertex version of armadillo
	[bunny*.obj] various versions of bunny mesh
	[hemisphere_graphite_*.obj] various near-regular hemispheres (created in Graphite)
	[sphere_graphite_*.obj] various near-regular spheres (created in Graphite)
	[sphere_semireg_*.obj] various semi-regular spheres (created by smoothing marching cubes)
            various decimated/edited versions of surfel sample files from
   (in OBJ format)		
		    various perl scripts for converting from .surfel format, decimating point set, etc

You may need to re-mex some things to get this stuff
to run on your computer/version-of-matlab:

  mex dijkstra_maxdist.cpp -largeArrayDims



Isomap code    [parameterization\external\isomap\*]
   - Author: Josh Tenenbaum (
   - (c) 1998-2000 Josh Tenenbaum
   - Website for updates:\

Fibonacci heap   [util\external\dijkstra\(fibheap.h,dijkstra.cpp)]
   - Copyright (c) 1996 by John Boyer
   - updated by Ryan Schmidt, Feb 2009, to compile under Visual Studio 2005

Dijkstra's algorithm  [util\external\dijkstra\dijkstra.*]
   - Copyright (c) Mark Steyvers, Stanford University, 12/19/00

Dijkstra's algorithm  [util\external\dijkstra\dijk.m]
   - Copyright (c) 1998-2000 by Michael G. Kay
   - Modified by JBT, Dec 2000, to delete paths

MVU Code    [parameterization\external\mvu\*]
   - mvu.m copyright (c) 2004 by Kilian Q. Weinberger   ( )
   - mvu_writespda.m   copyright (c) 2006 Brian Borchers,
   - csdp.exe copyright (c) Brian Borchers ( )



	Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
	M. Belkin, P. Niyogi
	Neural Computation, June 2003; 15 (6):1373-1396.

	Mathieu Desbrun, Mark Meyer, Pierre Alliez
	Intrinsic Parameterizations of Surface Meshes. 
	Comput. Graph. Forum 21(3): (2002)

	M. S. Floater
	Mean value coordinates
	Comp. Aided Geom. Design 20 (2003), 19-27
	K. Hormann and G. Greiner
	mips: an efficient global parametrization method

	Yaron Lipman, Olga Sorkine, Daniel Cohen-Or, David Levin, Christian Roessl, Hans-Peter Seidel
	Differential Coordinates for Interactive Mesh Editing, SMI 2004
	Yaron Lipman, Olga Sorkine, Daniel Cohen-Or, David Levin
	Linear Rotation-Invariant Coordinates for Meshes, ACM SIGGRAPH 2005
	Discrete Differential-Geometry Operators for Triangulated 2-Manifolds.
	Henry Packard Moreton and Carlo H. Sequin
	Functional Optimization for Fair Surface Design

	Patrick Mullen, Yiying Tong, Pierre Alliez, Mathieu Desbrun
	Spectral Conformal Parameterization 
	Symposium of Geometry Processing, 2008

	Nonlinear dimensionality reduction by locally linear embedding.
	Sam Roweis & Lawrence Saul.
	Science, v.290 no.5500 , Dec.22, 2000. pp.2323--2326.
	Sander, Pedro V. and Snyder, John and Gortler, Steven J. and Hoppe, Hugues
	Texture mapping progressive meshes, SIGGRAPH 2001   

	Ryan Schmidt, Cindy Grimm, Brian Wyvill. 
	Interactive Decal Compositing with Discrete Exponential Maps (2006). 
	ACM Transactions on Graphics (SIGGRAPH 2006), 25(3), July 2006, pp. 605-613.
	Ryan Schmidt, Karan Singh 
	Approximate Conformal Parameterization of Point-Sampled Surfaces (2009)
	Technical Report CSRG-605, Department of Computer Science, University of Toronto
	Ryan Schmidt.
	Part-Based Representation and Editing of 3D Surface Models (2010). 
	PhD Thesis, University of Toronto
	Robert Schneider, Leif Kobbelt
	Geometric Fairing of Irregular Meshes for Free-Form Surface Design
	Computer Aided Geometric Design 18 (4): 359-379, 2001	
	J. B. Tenenbaum, V. de Silva, J. C. Langford (2000).  A global
	geometric framework for nonlinear dimensionality reduction.  
	Science 290 (5500): 2319-2323, 22 December 2000.  	
	Yu, Yizhou and Zhou, Kun and Xu, Dong and Shi, Xiaohan and Bao, Hujun and Guo, Baining and Shum, Heung-Yeung
	Mesh editing with poisson-based gradient field manipulation, SIGGRAPH 2004




Back To
DCS Logo
DGP Logo