Several constraints are developed which impose consistency between model edge and sensed edge fragment geometries in order to collapse the search space in matching 3D edge data to 3D edge models. The constraints have been demonstrated on error-prone synthetic edge data and on 3D edge data obtained by stereo processing. An important feature of the constraints is their ability to attach sign labels to the sensed edge fragments during matching, providing consistency of edge directions between the model and data. This feature progressively increases the power of the constraints and assists in finding the transformation between model and sensor spaces.