Even older than that, Comanche: Maximum Overkill (1992) was voxel based. Amazing at the time, but I remember it'd fall apart pretty quickly as you got close to objects.

https://en.wikipedia.org/wiki/Comanche_(video_game_series)