Anyway, to answer your question I haven't invented anything particularly groundbreaking, just still I need to do my job. Things like 3d collision detection, line-of-sight detection, etc.

As a more concrete example, in the days before broadband I had a problem with transmitting the positions of multiple players in a multi-user game environment. Say you have hundreds of users on dial-up, some with 10ms ping time and others with 100ms. The 10ms users will be able to transmit their position 100 times a second, but the 100ms users can only transmit 10 times a second (assuming they wait for a reply). It doesn't make sense to transmit 100 movement updates to the slow clients, as you'll just overload their connection with unnecessary data. So what is the best solution? The algorithm I came up with is this:

- server maintains "last position" coords plus timestamp for each client - whenever server receives a position update from a client x, it sends the positions of any clients who have sent updates since client x last sent an update

Not groundbreaking, but it took quite a lot of thought to come up with it. The beauty is that it only transmits the data that is needed - the fast clients get fast updates (but without sending any duplicated data), and the slow clients get slow updates. It's simple, elegant and efficient, which is the best type of algorithm.

PS, I don't work in the games industry or with 3d graphics - all that stuff was really just my hobby. I'm pretty sure I've had to come up with some algorithms for the stuff that pays the rent (which is also pretty interesting), although I can't think of any off the top of my head. I did come up with a sound compression algorithm using FFTs, but abandoned it for an off-the-shelf one that worked much better. For the most part it is better to use algorithms that someone else has already figured out and turned into code rather than reinventing the wheel.