Determinig object visiability

(just realized i have not explained this completely :) )

The process i described - i wasn't saying it AI would only function on image processing, but should only confirm weather culling algorithm was correct on some object to create a more realistic behavior.

You could do this, for sure.

You could easily write an 'object id' to a second buffer almost the same way you write a color to the screen buffer.

IIRC the radiosity method described at freespace.virgin.net/hugo.elias/ does something like this.

Will

I've investigated this option, but reading from video memory is slow, and there is no synchronisation between your visibility data and the current scene. You can't stop the video card, send it your "scene" and wait for it to return you the result like you would do with a simple ray cast. The data you'll get will be most likely ~100ms late, so it might be usable, but if your game is fast paced, it might not be acceptable.

If you find a decent way to implement it, I'd like to see your results!

Good luck

Eric

Well actualy i this is an experiment of mine, not anyithing practica (at the moment at least) ...

The fact that reading from video memory is slow, can be adressed by using "small" RT resolutions, buth this woud probably bring in the problems of accuracy ...
I will make some tests and check this ...
Another optimisation is not to check the entire image, instead you can project active objects AABBox to screen cordinates and lock only that area (to be searched for selected color).

As I said, I will make a test app, and post the results soon since i got some free time now.

Also, gameplay wise, I wouldn't use such visibility test AGAINST the player, at least not for a first person shooter, as the only position the player knows about, is the camera position. If you allow any part of the mesh to be seen, you need to provide the player information on wether or not he's well hidden.

Quote:

Original post by RedDrake Basically I was thinking of rendering a simplified scene version without textures, only using diffuse colors and per vertex lighting to represent AI scene. All AI important object (characters, trigger items, weapons ...) would be rendered in a specific color and static objects would be in different - "neutral" color . Also the scene would be rendered using scene light's so if a dynamic object isn't receiving any light (or weary little) it would be rendered darker and ignored by AI ... This is just a basic idea, but I am interested in hearing what you think about it, is this done, or is this inefficient, any feedback would be nice ..

If you're going to render a scene, no matter how simple, for each character to test if they can see something, and then analyse it at the end to see what is visible, then yes, that is going to be very, very inefficient. It would be better to just perform the ray-intersections from the character to any relevant points of interest.

Quote:

Original post by Kylotan If you're going to render a scene, no matter how simple, for each character to test if they can see something, and then analyse it at the end to see what is visible, then yes, that is going to be very, very inefficient. It would be better to just perform the ray-intersections from the character to any relevant points of interest.

Well actually, the image processing would be just a test, if the ray cast terms are satisfied, image processing is used to check the if the character is acutely visible (and this would not have to be a high frame rate 3-5fps would be sufficient for realistic AI updates ?). The if the character is spotted, the AI is in alert state, and is looking after the player, so standard ray-cast would do fine hear. As i said, this would not replace the ray casts, but would add an improvement to the accuracy/realistic behavior of AI when it comes to determining weather character can be spoted or not. This sort of thing would be useful in games where you need to sneak past enemy, stay in the shadows - like metal gear solid, or splinter cell and similar ...

hmmm too bad i don't have any actual game source with what i could test this AI approach, any opensource FPS that coud be potentialy moded to use this AI aproach ?

I think you can get the source to Quake 3 from id's website.

As the 3-5 fps thing, keep in mind that you'll multiply this frame rate by the number of bots / agents using this system, it will get time consuming pretty fast.

As an experimentation, that's an awesome project. Good luck!

Quote:

Original post by RedDrake Well actually, the image processing would be just a test, if the ray cast terms are satisfied, image processing is used to check the if the character is acutely visible (and this would not have to be a high frame rate 3-5fps would be sufficient for realistic AI updates ?).

That's still a lot of work to be done. It would make the game slow down significantly when a few characters were in the same area.

Also, I don't think you can get around the slowness of reading from video memory. It's not just slow, it's SLOOOOOOOOOW. The speed of rendering comes from the pipeline and the fact that while you're plotting one pixel, the card is doing texturing/lighting/blending on previous ones. As far as I know, when you ask to read the data, all this has to stop so that you get accurate values. I expect that's going to have a massive impact.

If it's light and shadow you're primarily concerned with, as opposed to pixel-perfect vision, then I'd probably look into trying to do real-time radiosity instead. I think you could simplify that enough to make it usable.

Is there a delay in reading off a rendered scene, or a complete stall of the GPU?

From my thinking, the latency isnt important at all, but the bandwidth... is the bandwidth enough to keep reading frames off the video card in realtime?

Fraps does it.

Its not a big deal if its 200ms late - typical human reaction time is in that ballpark anyways.

I'd be more suspect of the overall idea .. its certainly not a 'general' solution to visibility testing as it requires the act of rendering.

Seems more complicated than its worth. A novel idea with narrow practical value.

As far as I know, it's a complete stall of the pipeline (or one of the pipelines, if there are several independent ones... I don't keep up with the details of how cards are made these days). I suppose there might be some way of getting the card to copy it to a secondary buffer and trickle that back to the CPU asynchronously with minimal effect on rendering speed, but obviously the reduced read bandwidth would mean you couldn't do that as often as once per frame.

I don't know how Fraps does its work, though. It appears to only operate with DirectX and OpenGL applications so I wouldn't be surprised if it's doing something at the driver level that lets it do something that application code can't usually do.

You could write a bot client that does nothing else than BOT ai & visibility determination

I would render each object with another color(RGB) combination and turn off all effects that affect the color values

Lets choose (R,G) as the object identifier 256*256 probabilities(maybe add a bias between objects and let the B be some blended component that stores the brightness(caused by lights)

now render everything that is visible at a lower resolution 640*480 maybe,
read back the buffer, examine the content.

you have a 640*480 pixel sized buffer and a list of visible objects you rendered
now don t examine each pixel, instead place a grid of 16x16 sized cells and examine the corners of these cells, once you found a object in the image, remove it from the visible list and go on until you have checked everything

if there a still a lot of objects left you could perform a second lookup:
this time only the centers of the foremention cells .

You don t need to do a by pixel test since no human would realize this in a fast paced fps shooter

OK now i am beginning to wonder if I should even put the word FPS in the post.
This approach is not suited for fast paced FPS, and it's not necessary ether. You won't notice these tings in Quake3 for example.

This sort of visibility determination is suited for games where player mustn't be spotted by the AI, and needs to sneak by them.

In that sort of games, ignoring the light amount on the character and ignoring things such as transparency, or precision is tenably ruining the game play (it gets quite annoying when the enemy can see you in full dark (you can't see him but he can see you :) )

@Basiror
256*256 color can't be implemented, if it gets implemented - AI would ignore the lighting - witch is pretty much the mayor benefit of this approach. Instead my idea was to :

- Do frustum culling, determine the enemy characters inside
- Request render of boot frustum
- Render the low poly enemy characters with diffuse color red, and per vertex lights
- Project AABox of each character to the image, and scan the area for red color.
- If enough color was found on the scanned area, the character is visible, otherwise the character is not visible

256*256 probabilities is relay not necessary. In games that need this level of precision, enemies only need to check if they see you (or your companion).

This isn't supposed to be done each frame, not even nearly that much. 6fps for all the boots would be enough. If you are in frustum of multiple enemies - the FPS is split - ex. 2 enemies = 3 FPS each, 3 enemies = 2 FPS ...
If the frames need to be rounded, the closer enemy gets extra frame ...

Multiple optimizations can be done, unfortunately I don't have the time i thought i have, so I don't think i will be able to test this any time soon :(

As for FRAPS i think i read it uses GDI ? not shure tough :-\

I think a simpler and more efficient approach might be to do CPU raycasts, but do many of them to random spots on the char's bounding box, and blend the results in over time, so the visibility value changes smoothly.

In other words, on one frame cast from the enemy's head to a spot the player's left shoulder, if visible, count as 1, otherwise zero.

visibility *= 0.95f;
visibility += this_visibility;

Next frame, do another raycast to a different spot on the character, etc.

And repeat each frame. That way you get a smoothly changing idea of visibility ( similar to what you'd get by averaging spatially in a single frame ).

The idea is to do temporal averaging rather than spatial, because it's cheaper, and at times looks better.

We use a similar approach for entity lighting in AG.

Really, no matter what optimisation you can make, it comes down to a simple question - can you read from video memory without stalling the pipeline? If so, it's practical, and an interesting idea. If not, you can't, no matter how infrequently you do it, as it will make the game jerky and unplayable. That question can probably be better answered in one of the graphics API forums.

I think you might benefit most by using some method of software occlusion culling. Yann L used a software renderer that would only render a Z buffer that was used to test if something should be drawn, and it gave a speed boost because it could work at the same time as the GPU (and of course it used low-poly models, no textures, etc). You could add to such a thing two more layers - an "ObjectID" field that is set to 0 for level geometry, 1 for first character, 2 for second, etc; and a "Brightness" that is a grayscale representation of everything. Since you don't need high resolution, you could probably do fine with a 16-bit Z buffer and 8 bits for the other two channels at a resolution of maybe 320*200. If, in addition, you use grossly simplified models for anything complicated, you could easily run several characters at a time with a decent framerate.
Since this could be done while waiting for the GPU to finish the frame (for the human players), etc, it'd probably be far faster than trying to use the GPU for it. It would also allow for far more customization, and could make use of the multi-core CPUs that are becoming somewhat common.

Quote:

Original post by Kylotan Really, no matter what optimisation you can make, it comes down to a simple question - can you read from video memory without stalling the pipeline? If so, it's practical, and an interesting idea. If not, you can't, no matter how infrequently you do it, as it will make the game jerky and unplayable. That question can probably be better answered in one of the graphics API forums.

Stall the pipeline in what way ?

Are you speaking of the cost of reading from video memory ?
I think this is an AGP related issue, and with PCI Express cards this should not be a problem.

You should be aware (probably you are) the fact that modern physics can be GPU accelerated. How do they do that ??? they also need to read from Video Memory, and a lot frequent. This is solved by PCIe. Anyway PCIe is a standard for the new cards and is replacing the AGP.
And not to mention the benefit of using this viability tests on dual GPU systems ...

@Extrarius
As I said before. The idea i proposed isn't supposed to take advantage of hardware z-buffer for occlusion culling. That would be the benefit, but the primary gain of my approach would be realistic lightning impact on AI determination of visibility. I doubt that it could be achieved in better performance on CPU than GPU.

Quote:

Original post by RedDrake Stall the pipeline in what way ? Are you speaking of the cost of reading from video memory ? I think this is an AGP related issue, and with PCI Express cards this should not be a problem.

No, it's not about the lack of bandwidth, it's about how rendering pipelines work. When you are sending pixel 200 to the gfx card, pixel 1 might not even have been rendered yet, never mind pixels 2-199. That's what makes the cards so fast - while one thing is being transformed, the next is being lit, the next is being projected, blended, checked against a z-buffer, etc. They incur a little bit of latency in return for maximum output bandwidth. If you then want to take a snapshot, but want an accurate depiction, you have to wait for everything in that pipeline to make its way to the end. Then the whole pipeline has to stop while you copy data from the render surface back to main memory, because you don't want new data overwriting what you're reading. So you start incurring that latency once per read, rather than potentially just once per program.

If you're interested in how many pixel of an object/character are visible from an AI's point of view, you could do a hardware occlusion query ( IDirect3DQuery9 interface in Direct3D, not sure about OpenGL ). If you're using shadow mapping, you could also see if the character is visible from a light when your rendering the shadowmap by also doing an occlusion query. If you're using stencil shadows, I'm not sure but the occlusion query might take into account pixels rejected due to failing the stencil test as well, might be worth looking into.
As for the idea in general, the idea of AI being able to spot a player realistically is hard to translate into behavior that will be at all noticable to the player. I'm sure it would be fun to program though. :)
Daniel