According to the characteristics of datum axis measurement by using a Coordinate Measuring Machine (CMM), a method based on 3D convex hulls was proposed to realize the datum plane fitting. Firstly, the 3D convex hulls of discrete sampling points were rapidly constructed by using "gift encapsulated algorithm" based on the computational geometric theory. According to the definition of datum axis in Datum Reference Frames (DRF), the constrained degrees of freedom as well as the method to establish the datum axis were determine by the priority of datum axis and the features of other datum. Then, the mathematical equation of datum axis was used to resolve the constrained axis into a rotational vector and a translational vector and then to establish mathematical models with constrained datum axis rotation and constrained datum axis translation. Finally, the variable domain of datum axis was obtained by using 3D convex hulls based on material requirements. The experiment demonstrate that the results of datum axis determined by proposed method is the same as that of the CMM least square method in an unconstrained axis processing, however, it has more different as copared with that in a constrained axis processing. Fortunately, the method ensures the relative position relationship between the constrained axes, and it accords with the principle of establishing datum axes and meets the requirements of engineering applications.