VIS scripts....possible?

Game Engine, Players & Web Plug-in, Virtual Reality, support for other engines

Moderators: jesterKing, stiv

Rotwang
Posts: 10
Joined: Wed Oct 23, 2002 11:00 pm

VIS scripts....possible?

Postby Rotwang » Sun Mar 23, 2003 10:30 am

Hi everybody!

I was just wondering, has anyone found a way to precompile a blender game using anything similar to a VIS program? i.e. creating a file to help avoid rendering all unnecessary polygons in any particular game location? If they have, can someone post me a link to it?

If it hasn't been done yet, I came up with a method that could possibly :? work the other night....I wont post it yet, because I'm still working on details of the basic method.

However, if it is viable, it will require some fairly invasive hacking of the realtime renderer, unless the renderer happens to have a couple of python commands that I don't know about. Here's the questions:

1. When you set an object to "invisible", it will presumably not show up on screen. Does this mean that the render engine is not making any calculations for rendering it (IE will it speed up render time significantly), or does it still do the calculations but not actually draw it? (It may seem a stupid question, as if the latter were true the "invisible" property would be pretty much useless except in special cases, but I just don't know)

2. *crucial, someone please answer this* It's possible to set objects to invisible. Is it possible to set individual polygons of a mesh to be invisible, and if so, will that significantly decrease render time, or would the very act of looking up visibility of each polygon actually take longer than just rendering the damn things? I would guess it's not possible, since one mesh can be used by any number of objects, but I suppose one might be able to create a chunk of data owned by each object using the mesh to say which polys currently need to be drawn for that particular object.

If this is possible, or if it would be possible for someone to make the necessary modifications in a future release, this would allow the precompilation of datablocks for each individual mesh object to determine which polygons were visible for every camera position relative to the object.

Any thoughts? Anyone?

Saluk
Posts: 166
Joined: Wed Oct 16, 2002 6:52 am

Postby Saluk » Sun Mar 23, 2003 9:10 pm

I spent a little while the other day and I narrowed down the functions that add objects to the display lists. In gameengine/Ketsji/KX_Scene.cpp, there is a function called CalculateVisibleMeshes. This bascially goes through all the objects in the scene and adds their polygons to the display list, as far as I can tell. It looks like it doesn't do a test of any kind. At the end, it executes KX_Gameobj->MarkVisible() but invisible objects are STILL on the display list?

That's what it looks like to me anyway. So to do any occlusion, I would recomend adding them using tests in the CalculateVisibleMeshes function. THe easiest addition would be to use gameobj->getVisible, and then add it to the display list only if that's true.

Not totally sure though, I can't get the source to compile still.

But other than physics, this is the most important thing the game engine needs, so good luck to you!

Rotwang
Posts: 10
Joined: Wed Oct 23, 2002 11:00 pm

Postby Rotwang » Wed Mar 26, 2003 11:53 am

Doesn't anyone else want to talk about this? :(

Saluk
Posts: 166
Joined: Wed Oct 16, 2002 6:52 am

Postby Saluk » Wed Mar 26, 2003 10:39 pm

There don't seem to be very many interested developers unfortunately:(

z3r0_d
Posts: 1522
Joined: Wed Oct 16, 2002 2:38 am
Contact:

Postby z3r0_d » Fri Mar 28, 2003 7:14 am

there aren't many people here in general.

Yes, it would be nice.

(when time allows I would like to help, but it appears it will not for a good while)


Look up octree culling
--- abstract
world is divided into octrees
each of which is divided into octrees
and so on

each object (that doesn't move) is placed as well as possible into one octant (if it is on an edge it is in the parent octant)

the render only does the rasterization and rendering of the objects in the octants that intersect the view frustrum (what the camera can see)

if you want to work hard, you can divide things like the ground into different objects that fit well into octants.

-------
also look at occlusion culling (would be nice for sound as well)
and sectors (older blender versions had them, can be useful)

Rotwang
Posts: 10
Joined: Wed Oct 23, 2002 11:00 pm

Postby Rotwang » Fri Mar 28, 2003 9:16 pm

z3r0_d

Thanks for replying. I think what you're describing is how ordinary BSP engines like Quake work, and that isn't what I had planned....

My plan is to precompile a file, one for each mesh, that would define which polygons on that object are visible, including the moving objects (as long as you could calculate their position relative to the camera, I see no problem doing that) and tell the renderer to ignore all polygons on that object for that particular frame.

The trouble is, as far as I know, the current release only allows the user to define which Objects are to be drawn. If the object is drawn, the entire object mesh is rendered, even the bits of the object you can't see.

I need a way to actually tell the renderer which faces of each instance of a mesh in each object are to be drawn. Once I can do that, writing a python script to pipe polygon draw/don't draw information to the render engine during gameplay should be relatively easy.

While I'm just about up to writing my own scripts to precompile a level and use the precompiled data during play, I'm nowhere near capable of making the necessary mods to the actual Blender source (in both the blender publisher and the playback engine in the binaries it will eventually generate) that will make Blender capable of reading and using a file generated by user-made VIS scripts.

I'm no expert programmer, and I haven't a clue how the renderer works, but I would expect it to cycle through all polygons of each mesh it draws in a specific order. If so, it would be very easy indeed to load a small file into memory at the necessary time (say when the object comes within vanishing point and needs to be rendered at all), work out camera position relative to the object origin, and read which polys are visible from that position, and cancel rendering of all others. I wouldn't expect this to be too processor-intensive....a couple of trig functions to work out position of camera, and the rest is just look-up tables.

So, assuming the renderer works the way I imagine it to (it may not, I'm going to try to read up on it when I get more time), the minimum necessary modifications to the realtime renderer are as follows:

1. A function to return which object the renderer is currently processing.

2. A function to return which face of the object the renderer is about to draw

3. A function to tell the renderer to skip processing the current face (presumably just returned in 2) and go on to the next one.

Needless to say, they'd need to be FAST functions.

Another handy function would be one that returned a list of all faces the renderer will process for a given object, and in what order it would deal with them.

I say this proposal is the bare minimum in terms of modification to the Blender source (just three little functions, guys. Can you do it?) Using the above three proposed functions, the user (ie me!) would have to write their own VIS precompiling script (including defining their own file format for the VIS lookup table to be generated), and a script to be run in real-time dring gameplay to monitor the positons of objects and interrupt the renderer whenever necessary. Of course, if no user-made script were running, the engine would function the way it does now. No interruption of rendering could occur unless the user made a script to do it.

What do you think?

By the way, if there really aren't many people here, should I consider switching to the Elysiun forums perhaps?

Thanks for your help.

Tom

z3r0_d
Posts: 1522
Joined: Wed Oct 16, 2002 2:38 am
Contact:

Postby z3r0_d » Fri Mar 28, 2003 9:39 pm

Can you explain what you mean by VIS

ok, that said.

I don't think the hit from rendering a few extra triangles will usually be as bad as looking them ALL up in a table. Currently the methods that divide a scene are more efficent because they have to test vewer situations. It would only be advantageous to test every face if each face took much longer to draw (think 256 passes per face or more).

oh, and python isn't as fast as c, where visiblity code would be better suited.

(you know faces are usually one-sided right?)

as far as 'the order faces are rendered in' for individual objects it can be canged.
see my post [about alpha faces] on elysiun:
http://www.elysiun.com/forum/viewtopic.php?t=10389

[I am not an expert programmer either, but opengl is cool]

Development questions I think are better suited for this website's forums, but there aren't many (4?) developers here.

Rotwang
Posts: 10
Joined: Wed Oct 23, 2002 11:00 pm

Postby Rotwang » Fri Mar 28, 2003 11:23 pm

Sorry, I probably haven't been using the right word. By "VIS" program, I meant a program to optimise realtime rendering by only drawing polygons which are visible from the camera's current position, speeded up dramatically by having done all the time-consuming calculations for this during precompilation of the level and using minimal on-the-fly computation during rendering. This is what they call the BSP based optimizing programs used in games like quake, and I was hoping that everyone would understand what I meant. If there is a better word for this process that will avoid future confusion, please tell me!

I'm sure you've a lot more experience than me, but I really do find what you're saying about speed hard to believe. Is it actually true that it's faster to draw a uv-mapped polygon with anything up to 128x128 texture resolution, possibly also with alpha channel and dynamic light falling on it, than to do a couple of linear interpolations & inequality tests of camera position and then skip to the next polygon if they match certain values?

Could you please explain what you mean by "Currently the methods that divide a scene are more efficent because they have to test vewer situations. It would only be advantageous to test every face if each face took much longer to draw (think 256 passes per face or more)."? I'm sorry if I'm being slow and ponderous tonight, but I just can't quite see what you're trying to say (I'm sure you're having the same problem with some of my posts!)

Oh, and I was already pretty sure that a routine added into the source in C would be much faster than the same routine in Python script. But that would mean much more work for those modifying the source (rarely a welcome prospect, in any open-source project!), and also less flexibility for the users to develop their own optimizer routines. But in an ideal world where there would be no limit to the amound of ripping-apart and rebuilding of the main renderer source code, doing any renderer optimizations would of course be better in C.

The fact that the order in which faces of a mesh are rendered can change on any given frame does present a problem, but as long as you can find out what that order is, you can adjust the way your lookup table is read accordingly.

Tom

z3r0_d
Posts: 1522
Joined: Wed Oct 16, 2002 2:38 am
Contact:

Postby z3r0_d » Sat Mar 29, 2003 12:41 am

What I mean
suppose for a 4000 triangle scene:
4000 simple tests reduces numbers of polygons drawn by 2500
or
15 simple tests reduces numbers of polygons drawn by 1500

which one would you think is faster? It depends how inefficent drawing every polygon really is.

The transformation of vertices to where they would appear on the screen is also has an effect on speed.

so, I doubt testing EVERY face will have a significant improvement in speed (over testing things more abstract), unless something changes which causes faces to be so much harder to draw.

the 15 tests I was thinking would be I guess (not having used them) like the sectors blender had before. Each sector (or whatever they may be called this month) contains more than one face...
--------------- that said ---------------
I may be better informed about the game engine (or just opengl) than you, but I am still seriously outdone by others here.

I would like to see something done beyond backface culling

I had something else to say, but I forgot

Rotwang
Posts: 10
Joined: Wed Oct 23, 2002 11:00 pm

Postby Rotwang » Sat Mar 29, 2003 12:47 pm

I think I can see what the problem you're referring to is, but it's rather difficult to tell whether it would work like that.

First, can you explain exactly what you mean by "test" please.

I think the best way to illustrate the problem is by example.

Let's consider that 4000 polygon scene. For simplicity, let's say that all those polygons are part of one mesh used by a single object, whose centre point is roughly at the centre of the mesh.

This next bit is very difficult to describe, please bear with me. If it isn't clear, let me know and I'll tyr again with diagrams.

During production of the level, you would create a multi dimensional matrix representing visibility of each polygon for each position of the camera, in polar form, relative to the centre of the object.

There would be pyramid (or pyramid section)-shaped regions radiating out from the centre of the object, defined by the coordinates of the 3 (if triangular based) or 4(if square based) vertices making up it's base, (3x4 dimensions of the matrix).

For each of these regions, there would be a list of polygons that would be obscured if the camera was within that region. Whether or not the camera was in one of these regions could be easily and quickly verified using simple inequalties and some linear interpolation, as the use of polar coordinates in this case greatly simplifies the amount of maths needed to be done per polygon, after the single instance of trig needed to determine relative camera location.

For increased speed, it could be possible to ignore all pyramidal regions that only affect polygons already accounted for by another region on any single frame, but this would mean a bigger matrix.

So, take the 4000 poly example. If only 2500 are visible, then the remaining 1500 are obscured by these. But, it's theoretically possible, depending on the shape of the mesh (say if 500 of the visible polys were bigger than the others, or if the obscured polys were placed such that many were behind the big 500 polys) that you could have something like 1000 invisible polygons be ignored in the render after checking as few as 500 visibility regions.

With opimisation of the matrix structure (such as combining overlapping regions into one) you could make it even faster....as few as 100 or so regions radiating from the 500 visible polys, which means theoretically you could avoid rendering the remaining 1000 after 100 visibility tests.

This is all a bit vague, but I think it illustrates the point.

z3r0_d
Posts: 1522
Joined: Wed Oct 16, 2002 2:38 am
Contact:

Postby z3r0_d » Sat Mar 29, 2003 7:46 pm

interesting...

by tests I meant "is the camera in this region" kind of questions

that may eat memory, but I guess it is worth a try. I [still] think it would usually do more harm than good because it is testing a significant number of situations, and eat memory.

Might it be possible to reduce the number of different tests you have to do by assuming multiple faces of your mesh are one, and are either all possibly visible, or none are, rathe than for each face (maybe visible, or definitely not)?

sounds like a lot of work.

later

Rotwang
Posts: 10
Joined: Wed Oct 23, 2002 11:00 pm

Postby Rotwang » Sat Mar 29, 2003 8:31 pm

Yeah, that could help. There are probably a whole bunch of other tweaks to the basic algorithm that would make it more efficient.

The trouble is, there's no way to test such a system without first making the modifications to the source code. Do you think there's any chance that could be done? I'll ask in the "next release" forums in a bit....

By the way, thanks for your encouraging and intelligent response to my idea. I've had some bad experiences in programming forums on other sites, and I really expected such a radical proposal to be instantly shot down in flames!

I don't think "eating memory" would be that big a problem, actually. All commercial games do that quite shamelessly anyway!

z3r0_d
Posts: 1522
Joined: Wed Oct 16, 2002 2:38 am
Contact:

Postby z3r0_d » Sun Mar 30, 2003 8:46 pm

you will have to change the blender source
(python in the game engine wouldn't be able to change the mesh without restarting the scene, and it is slower than c would be)

eating memory may be a problem if this stuff starts going to the swapfile. Imageine page-swapping on every frame.

Saluk
Posts: 166
Joined: Wed Oct 16, 2002 6:52 am

Postby Saluk » Mon Mar 31, 2003 6:43 am

Yeah, that sounds way too memory hungry to me. A good idea, but it's like copying your level 360 or more times over if I'm understanding you correctly. BSP's mostly deal with how things are laid out, and are a good way to organize the order faces are drawn and which faces are drawn. I've read some things on culling, and it seems really easy to me to make the culling process be more inefficient than just throwing the polygons at the card and letting it deal with them. This is because culling happens on the processor, while the graphics card is designed to handle many polygons.

The culling I hear about most often, are bsp's, which are great for indoor scenes and ineficient for outdoor scenes, and octrees, which work well for both types of scenes but maybe not as well as bsps for indoor. Bsps have to "compile" the level as you mentioned, and octrees happen in realtime. As soon as I get blender compiling, my first task is to make simple object-based frustrum culling, which only hides objects outside the cameras field of view. It will be a start. Hopefully after that, me or someone else can work on octrees or bsps, which are quite a bit more complicated than frustrum.

Rotwang
Posts: 10
Joined: Wed Oct 23, 2002 11:00 pm

Postby Rotwang » Tue Apr 01, 2003 7:50 pm

Saluk, I'm not sure if I've managed to get across exactly what I had in mind. You wouldn't have to copy your level 360 times.

You'd probably have a minimum of one region generated per polygon but, depending on shape and orientation, you could have anything down to only one single test to do per frame per object (at the minimum possible number of polys for an object, i.e. 1 face visible only, so only one region to account for all other polygons!)

It wouldn't eat memory anything like as much as copying the level 360 times, (though it would eat quite a bit)

If it were too slow to do all tests, of course, one could simply hard limit the number of tests per frame, say to two or three visibility regions. This would cause some increase in speed (for the polgons covered by the regions which did get tested) but, as long as the hard limited number of tests were fast enough to keep up to the frame rate, there would be no slow down.

I really think I should post a diagram, to illustrate what I mean properly, to avoid any other minsinterpretations. I'll put one up in a day or so, as soon as I get time.

The only real problem with this system is it would be unpredictable in its optimization...it could be very, very fast for some meshes viewed from some positions, and slower for others (though the hard limit I mentioned earlier would ensure it never became unacceptably slow. It would probably fluctuate between "normal" speed and high speed, which is still better than doing "normal" speed all the time).

Though I've been thinking, it really would be dumb to use the slow python scripts to do this when it could be incorporated into the Blender source...

I've never really worked on a serious, large scale, commercial quality C program such as this one before, though, so I'm going to need help if I try to do it myself. I'm not really a programmer, just a mathematician. I've done enough programming to make the algorithm itself, and optimize it a little, but I'd need someone else to help me integrate it into the main blender code.

Should I instead create a technical description of the system and propose it to be included in the next release, perhaps? Who would I need to talk to about that?


Return to “Interactive 3d”

Who is online

Users browsing this forum: No registered users and 2 guests