A computer-implemented method of determining a relative velocity between a vehicle and an object. The method includes receiving sensor data generated by one or more sensors of the vehicle configured to sense an environment following a scan pattern. The method also includes obtaining, based on the sensor data, a point cloud frame. The point cloud frame comprises a plurality of points of depth data and a time at which the depth data was captured. Additionally, the method includes selecting two or more points of the scan pattern that overlap the object. The selected points are located on or near a two-dimensional surface corresponding to the object, and the depth data for two or more of the selected points are captured at different times. The method includes calculating the relative velocity between the vehicle and the object based on the depth data and capture times associated with the selected points.