We propose a new data structure, called Fan-Meshes (FM), for reconstructing 3D models and scenes represented by dense scanning point clouds. It is a local piecewise linear approximation to the data geometry, and can serve as primitives in reconstruction with a good balance between computational loads and reconstruction quality. In our algorithm, local remeshing is performed in preprocessing to obtain regular FMs, and a three-level-point data structure called Triangle Selection Record (TSR) is then used to reduce redundancies in the raw data and overlapping in the original FMs. Furthermore, to apply the method to raw 3D scanning data, we use a smoothing operator to the point cloud in order to eliminate some sensor noises. Experimental results demonstrate that our scheme is effective even for large-scale scenes with real data.