Abstract: Haptic-based tissue stiffness perception is essential for palpation training system, which can provide the surgeon haptic cues for improving the diagnostic abilities. However, current haptic devices, such as Geomagic Touch, fail to provide immersive and natural haptic interaction in virtual surgery due to the inherent mechanical friction, inertia, limited workspace and flawed haptic feedback. To tackle this issue, we design a novel magnetic levitation haptic device based on electromagnetic principles to augment the tissue stiffness perception in virtual environment. Users can naturally interact with the virtual tissue by tracking the motion of magnetic stylus using stereoscopic vision so that they can accurately sense the stiffness by the magnetic stylus, which moves in the magnetic field generated by our device. We propose the idea that the effective magnetic field (EMF) is closely related to the coil attitude for the first time. To fully harness the magnetic field and flexibly generate the specific magnetic field for obtaining required haptic perception, we adopt probability clouds to describe the requirement of interactive applications and put forward an algorithm to calculate the best coil attitude. Moreover, we design a control interface circuit and present a self-adaptive fuzzy proportion integration differentiation (PID) algorithm to precisely control the coil current. We evaluate our haptic device via a series of quantitative experiments which show the high consistency of the experimental and simulated magnetic flux density, the high accuracy (0.28 mm) of real-time 3D positioning and tracking of the magnetic stylus, the low power consumption of the adjustable coil configuration, and the tissue stiffness perception accuracy improvement by 2.38 percent with the self-adaptive fuzzy PID algorithm. We conduct a user study with 22 participants, and the results suggest most of the users can clearly and immersively perceive different tissue stiffness and easily detect the tissue abnormality. Experimental results demonstrate that our magnetic levitation haptic device can provide accurate tissue stiffness perception augmentation with natural and immersive haptic interaction.