new collision code

Development directions, tasks, and features being actively implemented or pursued by the development team.
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

ace123 wrote:Was the problem then only with tri-strips?

I had a feeling it happened for every polygon at least in some models... it looked somehow more like an off-by-one or something to that effect.
the rapid collider treats every element > 3 verts as a tri strip. I'm not sure if that's valid unless we are guaranteed that the data in bsp_polygon is either a triangle, or a tri-strip. bsp_polygon and GL supports primitives of quad, tri, tri-strip, quad-strip, line-strip, tri-fan.

There is no way of determining whether or not a 6 vertex array element is two triangles, a tri strip, or a quad strip (i doubt it's a tri-fan). Unless we know one way or another by limiting our mesh files to what we want.

So i just decided that since treating it all as a tri-strip wasn't working right (and rapid collider's structure probably hid the fact that it wasn't working for it either somewhat) that i might as well try treating everything as distinct triangles. So far it's not so bad, but i have the feeling it's still not 100% correct. But at least we know where to look now. It's all in the reading in of bsp_polygon correctly.
ace123
Lead Network Developer
Lead Network Developer
Posts: 2560
Joined: Sun Jan 12, 2003 9:13 am
Location: Palo Alto CA
Contact:

Post by ace123 »

Would it be possible to change the format of bsp_polygon so it has that information? Especially if we don't need to use bsp any more.

For the most part things went well. I was able to go into the docking bay of the fighter barracks, and a lot of the collisions worked surprisingly well.

Unfortunately a few times it got mixed up which side of the wall I was supposed to be on, especially when rotating my ship, so I would hit the wall but as I rotated I would get pushed outside of the wrong side of it.

The mining base also worked well for the most part... however the first tile of the inner docking area above and below right after where you enter seems to not collide at all, but the middle areas do work. I have no idea why.

At one point I hit the bottom, bounced to the top quickly and exploded. I saw the star streaks across the screen everywhere which worries me that I encountered a NaN or something there.

After I respawned and launched the thing segfaulted, and I stupidly forgot to run it in a debugger ("I'll just test for a minute... how could it possibly crash?")

I'm really tired but I'll try to test some more tomorrow.
charlieg
Elite Mercenary
Elite Mercenary
Posts: 1329
Joined: Thu Mar 27, 2003 11:51 pm
Location: Manchester, UK
Contact:

Post by charlieg »

safemode: have you spoken to hellcatv about this? Perhaps he can shed some light on things.
Free Gamer - free software games compendium and commentary!
FreeGameDev forum - open source game development community
chuck_starchaser
Elite
Elite
Posts: 8014
Joined: Fri Sep 05, 2003 4:03 am
Location: Montreal
Contact:

Post by chuck_starchaser »

Indeed; hellcat should be able to figure this out; I can't believe the collider would even be able to change a fan, say, into a tri-strip.
(OT: Heck, if I was writing a collider from scratch I'd probably look into using face normals instead of geometry, and detect when the clouds of normals from two objects are interpenetrating each other's space by some kind of statistical analysis. This would reduce the size of the data and put some thickness safety into the algorithm. It's been a very common bug in a lot of games that vertices end up in the wrong side and you get glued to a wall or to another character...)
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

I speak with hellcat probably too much whenever he's online. Unfortunately, this area of VS has had such little activity that a lot of what goes on in loading up bsp_polygon and how it should be read is lost to everyone.

I think our problems with using the 6 vertex elements may be simply due to them not being a set of 2 triangles.

More info is needed and i'll have to make some changes today to see if indeed, all i'm dealing with is 3 vertex and 6 vertex elements. Then i can test and see if perhaps they are a tri-strip but they dont follow the : ABC BCD CDE DEF format. in mesh.cpp it says that the end of a tri-strip where the size of the element is odd, should end (n-1,n-2,n) rather than (n-2,n-1,n) like normally do. i dont know if that has anything to do with our problems, but it's details like that which we have to figure out ....

I just wish i had the "xmesh" file for a unit ... The xmesh files in the mesh directory are all perfect (they only consist of 3 vertex elements). I need one of a base (fighter barracks for instance) so i can see what data we're reading in and compare it to how it looks once it's being copied to our bsp_polygon
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

chuck_starchaser wrote:Indeed; hellcat should be able to figure this out; I can't believe the collider would even be able to change a fan, say, into a tri-strip.
(OT: Heck, if I was writing a collider from scratch I'd probably look into using face normals instead of geometry, and detect when the clouds of normals from two objects are interpenetrating each other's space by some kind of statistical analysis. This would reduce the size of the data and put some thickness safety into the algorithm. It's been a very common bug in a lot of games that vertices end up in the wrong side and you get glued to a wall or to another character...)
opcode has a planes collider that people say is better performing than most others for many situations. Unfortunately, i've yet to see an example of it in actual use.

We have all types of colliders at our disposal. We use the regular tree one because that's what example I had and that's what seemed the easiest and the most direct drop-in replacement for Rapid. If it's determined that one of the other colliders will be better, we can eventually move to it.
chuck_starchaser
Elite
Elite
Posts: 8014
Joined: Fri Sep 05, 2003 4:03 am
Location: Montreal
Contact:

Post by chuck_starchaser »

To get the xmesh of any bfxm just do
mesher <meshname>.bfxm <meshname>.xmesh bxc
That's assuming mesher works. I have an old mesher that works, somewhere, if you need.
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

i outputted the xmesh for fighter barracks. The triangle vertices make no sense to me. There is a list of Points. Then a list of Triangles, then a list of Quad's. The vertices that make up the triangles dont appear to be sorted at all.

This means that the makeup of bsp_polygon is computed in code, rather than built into the file.

Now i just gotta track down what format it writes the Points in.

I would think it would be a series of tri-strips only. But obviously that's not the case, or we wouldn't get multiple instances of the same point in the same triangle.
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

I've verified that vertexlist is populated with tri's and quads. No tri-strips, No quad-strips.

What happens is GetPolys(vector<bsp_polygon>) calls GetPolys(GFXVertex **,int numPoly,int numTris). In the second GetPolys function, the vertex list is populated based on a configuration variable designating the valid types (this is set to GFXTRIS and GFXQUADS). All xmesh's have only these polygon types.

Optimizing of the list is done in GL land, but it's not done to our vertex list. Our vertex list remains as a list of tri's then a list of Quads.

So this is returned to the first GetPoly's function. The values are copied because the first Vertex list has the data in an object that we dont use in our bsp_polygon struct. So we copy the x y z of the Vertex to the i j k of our Vector in bsp_polygon.

It's copied so that the first part of the bsp_polygon is all tri's, then the second part should all be Quads.

This copied list is what gets written to the argument of the first GetPoly's function.

My problem is figuring out how to correctly translate the data of the quad section into correct info.

I think the bsp_polygon GetPolys function converts the Quad sections into two triangles for us. That's why a quad element is 6 vertices, rather than 4, which is what it is in the second GetPoly's function.

So my solution of making the 6 vertex elements in the vector<bsp_polygon> was correct. I think.

This leads me to believe that either A. I'm not setting the collider up correctly for the situation we have in VS (compared to the situation they have in CS) or B. our code we have that deals with the aftermath of a collision is in need of tweaking to deal with the new particulars of OPCODE, rather than how it was tuned for RAPID.




At least this is what i've come up with after viewing some of the suspected files.

anyone else willing to look should check out
mesh_poly.cpp for the first GetPolys function, then gl_vertex_list.cpp for the second.

I know for a fact that the input data has only Tri and Quad polygon data. No strips or lines or fans. So take it from there and see if i'm wrong in that respect.

I'll try and hammer out some more debugging to see why the collisions at slow speed result in undesired behavior.
ace123
Lead Network Developer
Lead Network Developer
Posts: 2560
Joined: Sun Jan 12, 2003 9:13 am
Location: Palo Alto CA
Contact:

Post by ace123 »

Why don't you just use the data directly from the mesh class rather than copying it into the bsp_polygon format that is causing so much trouble? I don't believe we will need to use the collider with anything other than a Vegastrike mesh.

Also, I thought there are tristrip, quadstrip and trifan types in the mesh format..
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

I'm using bsp_polygon because that's what the collide_array code sends. I'm not copying to bsp_polygon, VS is. The Rapid Collider can use bsp_polygon directly without making an additional copy. It does this by creating a triangle index to reference the bsp_polygon. From what i remember, the Vector format of the bsp_polygon matches what the Rapid Collider expects to use.

If we did this we'd have to create a Point from each Vector in our MeshCallback, a function in which we already spend time Creating a Vertex for each Point in the triangle. So that would slow down our Callback for the sake of saving memory ...which is not acceptable.

If we could change bsp_polygon to contain Point's, we could win both ways, save memory and keep the mesh callback fast....but i dont know if the rest of VS that uses bsp_polygon will be happy with that. Even though it stores the same info, the member functions are different. If the rest of VS only accesses the data members directly and doesn't use the member functions of Vector when dealing with bsp_polygon's members, we could do that. All we'd need to do is change the references to x y z to i j k, or add x y z in the Point class to reference tho i j k vars.


They're in the format, but we dont use them. that is to say, that the format supports them, but VS doesn't. We support it on the very low end of reading the xml data in, but we make assumptions higher up that there are just tri's and quads.


edit: if i use the GFXVertex array that is used to create the vector<bsp_polygon> I still dont think i'd be able to avoid copies, because the data types aren't the same. Plus, the rest of VS still wants to use bsp_polygon in places, and i'd have to get rid of those uses too in order to get rid of bsp_polygon altogether so i can avoid the use of that function....otherwise the copy happens whether i use bsp_polygon or not.
ace123
Lead Network Developer
Lead Network Developer
Posts: 2560
Joined: Sun Jan 12, 2003 9:13 am
Location: Palo Alto CA
Contact:

Post by ace123 »

What's the problem with adding another callback function to the Mesh class to create a different format? At least this would save one of the copies. And then leave the code be that uses bsp_polygon.

Then make a collide_polygon or something else that has a format you want. (with the Points as you were saying).
It's basically free to create another accessor function that is in your favorite format as well as leave the other bsp format for code that wants to use that.
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

I wouldn't need to alter the mesh class. No matter how i store or index the vertex array, i still need to give Opcode Ice Points. I'd still need to copy from GFXVertex to a Ice Point. Otherwise i wouldn't able to reference them in the callback. The Point class isn't just a container for 3 floats. IF GFXVertex was an Ice Point, then we'd be in business.

As it stands, it's better to convert at initialization than to convert on the fly whenever a lookup on a vertex is made.
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

I've been reading some really really old test papers comparing opcode to RAPID and various settings alter the performance of OPCODE based on the situation. Some settings make it perform very good in close proximity, some better during actual collision. etc. We have the ability with opcode to change some of it's behavior after the creation of the collider. For instance, we can turn Full BOX BOX testing on and off, temporal coherence on and off, return first contact only. That last one is important, especially with temporal coherence. The way RAPID worked was it returned all contacts, we have the option of returning only the first contacted vector we find. This is much faster, but also, we seem to have trouble making our force vectors to determine where to bounce the ships when this is enabled. We may want to enable first contact when a ship is moving over a certain speed, then turn on all contacts for any slow moving ships. Same goes for temporal coherence, we turn that on on fast moving ships, turn it off on anything going slow. Same for full box box testing.

Right now i have the settings mostly tuned for slow moving ships. Since this results in the least amount of bugginess when rubbing up on a base (though we still need to work on that). This does cause worse performance when you ship is moving at a decent speed. That is to say, we could make it go faster for those collisions by changing the settings on the fly.

Just an idea anyway.
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

Well, I think if we dont see any more users giving reports by friday, I'll remove the Rapid Collider from svn head. Paving the way for package maintainers to get things rolling again. The main reason for keeping the Rapid collider around was for performance comparisons anyway, and after I make a couple more tweaks the performance should be acceptable.

With that done. What is left to hold up 0.5? I'm currently trying to get our lower quality playing modes functional again, and having decent success with that. Multiplayer isn't going to be mature by 0.5 so i'm not sure what milestone we're looking at for that to get to before 0.5. Is that it? should we get a written explicit list going so we can finally deliver 0.5 and get working on the next one? I mean, the roadmap is totally out of date.
charlieg
Elite Mercenary
Elite Mercenary
Posts: 1329
Joined: Thu Mar 27, 2003 11:51 pm
Location: Manchester, UK
Contact:

Post by charlieg »

0.5 can be followed by 0.5.x releases that introduce more features.

Release early, release often. ;)
Free Gamer - free software games compendium and commentary!
FreeGameDev forum - open source game development community
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

all the releases falling under the 0.5 version should be intercompatible though. An update to vegastrike under 0.5 should not cause your data4.x to no longer be valid, and vice versa. They also shouldn't make save games made under 0.5 not longer make sense. So we're limited in what can go into a 0.5.x release. Features could be added, but they cannot break api. They should mostly be bug fixes or optimizations.

we hit a problem though, because we dont have enough people to do it the right way. nobody wants to maintain a stable branch. But I think we'd benefit a lot in the form of user-base if we made a serious effort to maintain a stable branch while working on a dev branch. This would allow Mods to have a stable code-base to work on while addressing bugs for users in a timely manner. Then we can be free to work on all our pet projects on the dev branch and not have to make mods go : "We'll wait until that version is released" forever and we wont push users away by continually adding instability to the latest release.

release early and release often is great, if those releases are bugfixes and optimizations only. Mods aren't going to like changin the features every few months, and users aren't going to like new unstable code patched alongside bugfixes for the previous unstable code.

I'd really like to see the show stoppers and why they're show stoppers. Multiplayer could be disabled if it's not ready for prime-time, we can release, and worry about fixing bugs and optimizing it later. But we've been almost ready to release for 9 months. We can get multiplayer polished as an "experimental" feature of 0.5 and make a 0.5.5 release with the polished version. Same with shaders if it's a major issue that we dont have a complete set of normal maps for 0.5.0

I'm just another minor dev, but looking at the mod forums is depressing to see the last post dates, and that's really important. Getting into distributions the sooner the better because it will bring VS into a much larger population. We need 0.5 for that. and i think we've all gotten sucked into that (just one more) change mental state. If it's not a change fixing something broken in a feature necessary to play the game, then it's not a show stopper in my book.
jackS
Minister of Information
Minister of Information
Posts: 1895
Joined: Fri Jan 31, 2003 9:40 pm
Location: The land of tenure (and diaper changes)

Post by jackS »

Wandering a bit off topic, but pertinent to the above comment -

Personally, I think the logical next steps are to proceed something along the following lines:
1) Go through all existing bug tracker reports
2) Create a KNOWN BUGS wiki page featuring all encountered bugs that can be readily replicated in a given SVN version (if it's not readily duplicable, even if it's a nasty bug, it's probably not the sort of thing we're looking for right now unless it permanently damages savegames, etc.)
2a) Partition the known bugs into those solvable without any engine side intervention (i.e. separate purely data-set bugs from engine/ mixed bugs).
3a) Ask ourselves if the engine, given the known bugs, is sufficiently stable and suitable for VS and other Datasets, Mods, and TCs to use as the basis version until a subsequent version is released
3b) Ask ourselves if the gamedata that will be bundled with the engine (VS the game) is sufficiently functional and playable, given the engine bugs, to not be a deterrent to interest in either of VS the engine and VS the game
3c) Ask ourselves if the gamedata is sufficiently functional and playable, given the data-only bugs, and a reasonable set of estimates for how long it would take to address them with patches, to remain a viable milestone in the event of non-backwards-compatible engine changes during further devolpment (i.e. branch rot).
pyramid
Expert Mercenary
Expert Mercenary
Posts: 988
Joined: Thu Jun 15, 2006 1:02 am
Location: Somewhere in the vastness of space
Contact:

Post by pyramid »

My proposal is to review the task list for the upcoming 0.5.0 release: http://vegastrike.sourceforge.net/wiki/ ... _Task_List
and supplement it with the owner and status. I've done a quick edit on this task list to exemplify the proposed approach. My proposal is that everybody of the devs lists the tasks he would like to accomplish before the 'go' for 0.5.0 release and then we could start a new 'roadmap' thread to discuss this priorities.
charlieg
Elite Mercenary
Elite Mercenary
Posts: 1329
Joined: Thu Mar 27, 2003 11:51 pm
Location: Manchester, UK
Contact:

Post by charlieg »

The economic system seems to need a review.
Free Gamer - free software games compendium and commentary!
FreeGameDev forum - open source game development community
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

after talking with hellcatv, it seems that the biggest issues are Sol system (bases are moving too fast), and graphics performance with nvidia cards when viewing planets/bases that fill the screen. Those seem to be showstoppers where everything else is not necessary for a release.
chuck_starchaser
Elite
Elite
Posts: 8014
Joined: Fri Sep 05, 2003 4:03 am
Location: Montreal
Contact:

Post by chuck_starchaser »

The rumors I've heard about Sol is that the problem is that the planets are moving in arcs, while the player's ship moves in a straight line, so the planet is always accelerating away. The simplest way to solve that problem, IMO, would be to introduce gravity, such that the star's attractional force makes the player's ship trajectory to curve and match planetary orbits' curves.

As for planets occupying the whole FOV slowing down the framerate, it would seem to me that ought to be due to overdraw. One way to solve it might be to use a subdivided cube for the environment cube, and programmatically, on the cpu side, bypass rendering of any tiles of the cube map that can be determined to be entirely covered by a planet.
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Post by safemode »

lowering the display resolution down to 800x600 seemed to fix the increased GPU use. anything higher caused it to flip out and framerate to drop to 1/2 of it's previous.
chuck_starchaser
Elite
Elite
Posts: 8014
Joined: Fri Sep 05, 2003 4:03 am
Location: Montreal
Contact:

Post by chuck_starchaser »

Good experiment! So, that settles it: It's definitely a fill-rate issue, which means it's overdraw. My question would be why? Certainly, writing every pixel on the screen with the galactic background and then overwriting every pixel on the screen with the planet texture ought to take more time than drawing every pixel on the screen only once. However, the traditional standard or rule of thumb for overdraw is that an average overdraw of 2 is okay, 3 is getting a bit high. Is FSAA turned on, in your experiment? That would be a serious factor.
Another question is in what order are things being displayed: In front-to-back order, the planet would be drawn first, then the painting of the background would be done per pixel but with z-test failing. This is still overdraw, but failing z-tests allow faster progress, so it works out to an overdraw equivalent of 1.5 or whereabouts. If for some reason the background is being drawn first, this would be a lot harder on the gpu.
Third question is, is backface-culling turned on? I would imagine so, but maybe for some reason the planetary mesh is flagged as two-sided or something. That would KILL the gpu... having to draw both the nearside AND the far-side of the planet.

Having said all that, I would stand by my earlier idea of making cube boxes using standard geometry and subdividing them, like 64 x 64 x 64, and then computing vis of each tile in the cpu. It's just an idea; I don't know how cube maps work. Probably cube maps are tied to hardware, but only for the sake of environment mapping, and so we could separate the background display from environment mapping algorithms: Use a standard cube map for EM, but then provide our own subdivided cube for the directly visible skybox.
chuck_starchaser
Elite
Elite
Posts: 8014
Joined: Fri Sep 05, 2003 4:03 am
Location: Montreal
Contact:

Post by chuck_starchaser »

Good experiment! So, that settles it: It's definitely a fill-rate issue, which means it's overdraw. My question would be why? Certainly, writing every pixel on the screen with the galactic background and then overwriting every pixel on the screen with the planet texture ought to take more time than drawing every pixel on the screen only once. However, the traditional standard or rule of thumb for overdraw is that an average overdraw of 2 is okay, 3 is getting a bit high. Is FSAA turned on, in your experiment? That would be a serious factor.
Another question is in what order are things being displayed: In front-to-back order, the planet would be drawn first, then the painting of the background would be done per pixel but with z-test failing. This is still overdraw, but failing z-tests allow faster progress, so it works out to an overdraw equivalent of 1.5 or whereabouts. If for some reason the background is being drawn first, this would be a lot harder on the gpu.
Third question is, is backface-culling turned on? I would imagine so, but maybe for some reason the planetary mesh is flagged as two-sided or something. That would KILL the gpu... having to draw both the nearside AND the far-side of the planet.

Having said all that, I would stand by my earlier idea of making cube boxes using standard geometry and subdividing them, like 64 x 64 x 64, and then computing vis of each tile in the cpu. It's just an idea; I don't know how cube maps work. Probably cube maps are tied to hardware, but only for the sake of environment mapping, and so we could separate the background display from environment mapping algorithms: Use a standard cube map for EM, but then provide our own subdivided cube for the directly visible skybox. The two sharing the same texture.
Post Reply