Pages: [1]
  Print  
Author Topic: Quake3 engine as an environment for Structure from Motion reconstruction  (Read 9115 times)
GrosBedo
Member


Cakes 20
Posts: 710


« on: March 05, 2012, 05:53:15 pm »

An interesting pre-thesis about indoor reconstruction of structure from motion, by using a Kalman filter on Quake3 indoor maps:
http://dip.sun.ac.za/~henri/recon.html

Quite interesting. Coupled with homothety (also used for 3D structure reconstruction, or more generally currently for automatic panorama stitching), this could maybe allow to create an artificial player of average level.

Also on a side-note, if kalman filter or a particle filter would be implement in ioquake3, it could be used to improve a LOT entities interpolation with a very low cost on the CPU (probably even less than the current implementation).
« Last Edit: March 09, 2012, 05:53:04 am by GrosBedo » Logged
GrosBedo
Member


Cakes 20
Posts: 710


« Reply #1 on: March 09, 2012, 05:50:25 am »

In fact I've just learned that Kalman filters can only work for linear systems, so although they can I'm sure pretty fit humans motions, it would sometimes be quite off. And also they are unimodal.

A better alternative would be Particle filter, which is quite easy to program and implement, and is multimodal and fits non-linear systems as well. The only problem here is that its complexity is exponential (Kalman is quadratic), but if it's used for max 4D, and it would be the case here (x location, y location, x velocity, y velocity, and for z position we could predict it using a fixed model with gravity, so in the end it would be 6D, but we would trick the particle filter to only consider 4D). Or we could just use 2 filters one after the other: one 4D, then one 2D for Z position, since Z position can be considered as independent, in practice, it could maybe work?
Logged
andrewj
Member


Cakes 23
Posts: 571



« Reply #2 on: March 09, 2012, 10:10:35 pm »

I see you fixed the spelling Wink

I don't really get how these things would improve interpolation of entities (i.e. players, as all other entities move in very predictable ways).
Logged
GrosBedo
Member


Cakes 20
Posts: 710


« Reply #3 on: March 10, 2012, 09:00:25 am »

Filters are based on probabilities and on physics models (that we can make to correspond to the physics of OA of course), so when predicting the next player's movements they take in account:

- ALL the previous positions of the player
- the physics model

I didn't look exactly how the current interpolation algorithm works, but seeing its inefficiency, I'm pretty sure it's based on a standard (and probably deprecated) interpolation algorithm.

Filters are relatively new (they were discovered some decades ago but are beginning to be implemented for real applications nowadays), and they proved to be highly effective (Google's self-driving cars are mainly based on filters to predict other cars and people movements).

So if filters can pretty accurately predict real life motions of cars and people, why wouldn't they be able to handle virtual players in a game ruled by a very simplistic physics model?

----

Concretely speaking, I am not exactly sure how much it will enhance (it may be under or exceed expectations), but it will sure enhance player's movements and actions predictions.

For example, this would allow to manage lagging players a LOT better, almost erase ping differences in gameplay, and allow for a very precise delagging for projectile weapons (currently only hitscan weapons are delagged because there is no good model to delag projectiles, but filters could be a good model for that purpose).
Logged
grey matter
Member


Cakes 8
Posts: 381

>9k


« Reply #4 on: March 10, 2012, 09:22:00 am »

I don't really see how this would improve player movement prediction in general. Human players are likely to change movement directions all the time, and due to things like rocketjumps, teleporters and jumppads the prediction errors can become rather large.
The timespan between movement commands is rather small (consider cl_maxPackets 125 for each player), so any advanced but just slightly slower algorithm might have the tendency to slow down the entire game (since it's single threaded for good reasons).

I think that better algorithms will certainly work on deterministic objects such as weapon projectiles, but they might not really be needed in that area.
The only problem I have with projectiles is that their visuals are off sometimes (compared to the server's view), such as being directly hit by a rocket that flew past a few meters. This might be due to the problem that in heated close-range matches it's crucial to recieve enough snaps from the server, otherwise client-side prediction is plain wrong, since it can not know that I've been knocked back by some enemy's rocket if the server didn't tell me.

I don't see how this would predict missing human input from lagging players any better. Prediction code can't know that the player sent a 180-flickshot in that missing packet, so it'll just continue where it left off. This is exactly what the current Unlagged code does (though only for a few frames).

Most problems that I've encountered with the current prediction code are due to network issues and as such not really the prediction's fault. I doubt that any other algorithm would handle them any better.
Logged

This space is for rent.
GrosBedo
Member


Cakes 20
Posts: 710


« Reply #5 on: March 12, 2012, 12:06:09 pm »

I don't really see how this would improve player movement prediction in general. Human players are likely to change movement directions all the time, and due to things like rocketjumps, teleporters and jumppads the prediction errors can become rather large.
The timespan between movement commands is rather small (consider cl_maxPackets 125 for each player), so any advanced but just slightly slower algorithm might have the tendency to slow down the entire game (since it's single threaded for good reasons).

(...)

Most problems that I've encountered with the current prediction code are due to network issues and as such not really the prediction's fault. I doubt that any other algorithm would handle them any better.

Thank you for those insights in the gamecode. Indeed, performance is necessary to process such necessary parts of the gameplay, and indeed that may be a problem in implementing a filter, but particle filters are known to be pretty spare on CPU usage, and at the same time pretty efficient (because the amount of computation is only relative to the most probable places, so there is space for optimization here).

When I say that those filters could enhance the interpolation, I mean the interpolation of positions, because this is pretty much the only thing we can predict. But potentially, filters, by using probabilities and continuous values, can be a lot more precise than the current interpolation engine, and could predict the movement of players for a lot more frames in case of a lag (of course, there are also limits here, but still I'm pretty sure it can be more effective than the current implementation).

And when I was talking about lagging players, I was talking about the other client-side, the players that are not lagging but are seeing another player lagging: instead of just seeing a player jerking around, such a filter could smooth a lot the movement with potentially a pretty good accuracy in its predictions, because it can model complex, non-linear movements.

What do you mean about the network issues affecting the prediction code? Have you got a precise example on hand?
Logged
Pages: [1]
  Print  
 
Jump to: