Abstract: We propose a novel region-based algorithm to quickly track time-varying facial expressions. Our algorithm takes a sequence of spacetime face meshes captured at video rate as input, and uses a template mesh to register each input face mesh to track facial dynamic expressions. In each mesh registration, we first automatically segment the template mesh into three initial regions with a metric, then for each initial region, segment it into different subregions and optimize a non-rigid affine transformation for each subregion with a variation of non-rigid ICP framework so as to approximate closely the input mesh. Region-wise non-rigid transformation decreases the unknowns in optimization significantly, and initial region segmentation decreases unnecessary optimizations and the template vertices involved in optimization greatly, so our algorithm has high speed. In addition, we introduce a new normal constraint in the non-rigid ICP framework to estimate more reasonable region-wise non-rigid transformation. The normal constraint makes our algorithm not only maintain good tracking accuracy while improving tracking speed, but also achieve automatic tracking without manual intervention. Experimental results show the efficiency of our algorithm.