new collision code

Development directions, tasks, and features being actively implemented or pursued by the development team.

Postby safemode » Tue Feb 12, 2008 12:43 pm

no, time is not a factor in opcode. You have to alter your scheduling for checking for a collision as you find two meshes getting close to eachother, this has to do with the whole sweep and prune method of reducing the number of meshes you need to check. such a thing is done internally in opcode for reducing the number of triangles checked, I believe.


I think the root of the problem lies with CollideArray not checking units that are basically resting on another unit/mesh. Movement may be close to 0 towads that other unit, but rotating could cause the one unit to penetrate the other. Whether we are using a bad radius to check if this is possible, or not checking at all, i dont know. That is a separate problem from the being "pushed into" the unit issue.

Being pushed into the unit should be solvable by making sure any correction to a collision does not have a positive net vector in the same direction that the unit is traveling. And when the velocity is already 0, we should probably apply a force that is perpendicular from the collided face towards the center of the unit doing the colliding.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Share On:

Share on Facebook Facebook Share on Twitter Twitter Share on Digg Digg

Postby jackS » Tue Feb 12, 2008 2:55 pm

safemode wrote:no, time is not a factor in opcode. You have to alter your scheduling for checking for a collision as you find two meshes getting close to eachother, this has to do with the whole sweep and prune method of reducing the number of meshes you need to check. such a thing is done internally in opcode for reducing the number of triangles checked, I believe.


We already check for collisions every physics frame that an object is simulated, and the player object is already simulated every physics frame. We can increase the frequency of physics frames, but that isn't an arbitrarily scalable solution. Fundamentally, if we're using a timeless collision detection algorithm, then there's going to be tunneling behavior due to the discretization of time. However, for a reasonable range of relative velocities, we can still expect to detect the collision at some point before the two entities have slipped entirely past or into each other (to compensate for potentially high relative velocities in the case of weaponsfire, one can, as a heuristic, augment the projectile's length based upon velocity relative to the firing ship, but I digress). One option that seems to present itself is, if we detect a collision, do a binary search over the time between the detected and previous physics frames, iterating the collision detection until there was some reason to believe that we had approached the initial point of contact, move both parties to that point in time and space and resolve the forces from there. Of course, this is still not fully general - a ship moving at sufficient velocity could still wind up fully inside another larger vessel (and hence have no collision detected in the first place) or, for vessels with arbitrarily non-convex geometry, the collision could be detected with an incorrect portion of the object (consider a sequence of rings, arranged somewhat like a giant dart-board but spaced out from each other with struts, and a vessel approaching from the side. It is not clear, given sufficient relative velocity, and hence sufficient relative error over a single time slice, that the correct ring would be collided with, etc.)

safemode wrote:I think the root of the problem lies with CollideArray not checking units that are basically resting on another unit/mesh. Movement may be close to 0 towads that other unit, but rotating could cause the one unit to penetrate the other. Whether we are using a bad radius to check if this is possible, or not checking at all, i dont know. That is a separate problem from the being "pushed into" the unit issue.


Units right next to each other are certainly checked, and rotations without change in position can trigger the collision resolution code (and are taken into account in resolving the collision). However, there is a configurable parameter that specifies a minimum time between applying collision forces to the same object which may muddy a given experiment if one is not aware of it. Whether or not a unit is checked (at mesh level) for collision is not a property of whether or not it is moving, but of position and size (i.e. isn't pruned by a sphere test).

safemode wrote:Being pushed into the unit should be solvable by making sure any correction to a collision does not have a positive net vector in the same direction that the unit is traveling.


This isn't a general solution, and I'm quite wary of attempting to special-case code in this direction. If an object is traveling along a given vector, and another object comes up behind it on the same vector, but with greater magnitude of velocity, then the resulting collision should indeed produce a positive net vector along the direction the first object was already traveling. I don't see a compelling reason to abandon the use of the conservation of momentum equations in order to special case something that's only occurring because parts of one object have already inappropriately found themselves inside another object.

safemode wrote: And when the velocity is already 0, we should probably apply a force that is perpendicular from the collided face towards the center of the unit doing the colliding.

I think this is very promising, but I'm not yet convinced it's entirely simple -- consider the case where, for example, a ship has wound up sufficiently inside a station that its centerpoint is already inside. I think something along these lines may work, but we'd need to enforce reasonable assumptions about the initial states of both objects.
User avatar
jackS
Minister of Information
Minister of Information
 
Posts: 1895
Topics: 56
Joined: Fri Jan 31, 2003 2:40 pm
Location: The center of Centre county

Postby safemode » Tue Feb 12, 2008 3:34 pm

jackS wrote:
safemode wrote:no, time is not a factor in opcode. You have to alter your scheduling for checking for a collision as you find two meshes getting close to eachother, this has to do with the whole sweep and prune method of reducing the number of meshes you need to check. such a thing is done internally in opcode for reducing the number of triangles checked, I believe.


We already check for collisions every physics frame that an object is simulated, and the player object is already simulated every physics frame. We can increase the frequency of physics frames, but that isn't an arbitrarily scalable solution. Fundamentally, if we're using a timeless collision detection algorithm, then there's going to be tunneling behavior due to the discretization of time. However, for a reasonable range of relative velocities, we can still expect to detect the collision at some point before the two entities have slipped entirely past or into each other (to compensate for potentially high relative velocities in the case of weaponsfire, one can, as a heuristic, augment the projectile's length based upon velocity relative to the firing ship, but I digress). One option that seems to present itself is, if we detect a collision, do a binary search over the time between the detected and previous physics frames, iterating the collision detection until there was some reason to believe that we had approached the initial point of contact, move both parties to that point in time and space and resolve the forces from there. Of course, this is still not fully general - a ship moving at sufficient velocity could still wind up fully inside another larger vessel (and hence have no collision detected in the first place) or, for vessels with arbitrarily non-convex geometry, the collision could be detected with an incorrect portion of the object (consider a sequence of rings, arranged somewhat like a giant dart-board but spaced out from each other with struts, and a vessel approaching from the side. It is not clear, given sufficient relative velocity, and hence sufficient relative error over a single time slice, that the correct ring would be collided with, etc.)

For velocities where the transformation of the vectors could put it in another collidable mesh we could either get another physics frame to run earlier than the next one would have, thus reducing the distance the mesh travels and check to see if we'll collide again. When the dt is sufficiently small we can just say they collided, and make them behave as such, without them actually colliding. This could be done by calling collide with a transformation of where we estimate the unit will be by the next physics frame.
safemode wrote:I think the root of the problem lies with CollideArray not checking units that are basically resting on another unit/mesh. Movement may be close to 0 towads that other unit, but rotating could cause the one unit to penetrate the other. Whether we are using a bad radius to check if this is possible, or not checking at all, i dont know. That is a separate problem from the being "pushed into" the unit issue.


Units right next to each other are certainly checked, and rotations without change in position can trigger the collision resolution code (and are taken into account in resolving the collision). However, there is a configurable parameter that specifies a minimum time between applying collision forces to the same object which may muddy a given experiment if one is not aware of it. Whether or not a unit is checked (at mesh level) for collision is not a property of whether or not it is moving, but of position and size (i.e. isn't pruned by a sphere test).

Hrmmm. Though I notice quite often the ability to penetrate a mesh especially when barely or not moving relative to it, then rotating and then accelerating while penetrated.

safemode wrote:Being pushed into the unit should be solvable by making sure any correction to a collision does not have a positive net vector in the same direction that the unit is traveling.


This isn't a general solution, and I'm quite wary of attempting to special-case code in this direction. If an object is traveling along a given vector, and another object comes up behind it on the same vector, but with greater magnitude of velocity, then the resulting collision should indeed produce a positive net vector along the direction the first object was already traveling. I don't see a compelling reason to abandon the use of the conservation of momentum equations in order to special case something that's only occurring because parts of one object have already inappropriately found themselves inside another object.


Maybe by net force i am confusing things. What I mean is that we should perform a transformation on the penetrating unit that is along a vector that is perpendicular to the face it penetrated towards the center of the penetrating unit, and then apply all the respective forces.

safemode wrote: And when the velocity is already 0, we should probably apply a force that is perpendicular from the collided face towards the center of the unit doing the colliding.

I think this is very promising, but I'm not yet convinced it's entirely simple -- consider the case where, for example, a ship has wound up sufficiently inside a station that its centerpoint is already inside. I think something along these lines may work, but we'd need to enforce reasonable assumptions about the initial states of both objects.

[/quote]

if the center is inside the base, we're screwed either way. the point is to prevent that by not allowing the situations that allow ships to fall inside a base mesh. The only ways i know of finding yourself that deep in a mesh is going really fast (my other suggestion addresses that) and by laying on the mesh and somehow falling into it after rotating around a bit. This addresses the second part.

So, when velocity is high enough such that we will travel outside of our "bounding box, search radius .. whatever" before the next frame, we call a pre-emptive collide on a transormation of where we think the unit will be by the next frame, see if it collides with anything and then either schedule the next frame earlier so it wont collide by the next frame or pretend it did collide in the current frame (since there is no distinction in that case between the frame before collision and the next, since it happens between).

When velocity is near 0 of unit A and we're close enough to a mesh B such that things start getting confusing, we transform the unit A in the direction towards the unit A's center perp from the face of mesh B that we are near. How far we push would be up to debate. We dont want it to be too visibly artificial, but if we're not registering a collide even though we're calling it, then we'll have to guess how far in we are. Though, I dont see how Collide would fail if we're penetrating and calling Collide in CollideArray. I think maybe we're being forgotten about until that push into the base after penetrating far enough.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby safemode » Tue Feb 12, 2008 10:22 pm

Well, i figured out why the opcode collider is acting up.

bsp_polygon is not an array of triangles. It's an array of sets of triangles, and they share vertices apparently. fun stuff. Working on a fix.

Though, I dont know why we send a polygon with vertices that dont divide by 3 and what such a polygon signifies in relation to the entire vector that's sent.


I thought a vector<bsp_polygon> was a "mesh" An array of triangles .

Now i find that it's an array of polyhedrons. That's really not cool.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby safemode » Wed Feb 13, 2008 12:00 am

Try out -r11836 It may be slow, but it should be accurate and not allow you to fall into a mesh.

Speedups will follow a lack of bug reports
Last edited by safemode on Wed Feb 13, 2008 8:40 am, edited 1 time in total.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby chuck_starchaser » Wed Feb 13, 2008 8:31 am

safemode wrote:What I mean is that we should perform a transformation on the penetrating unit that is along a vector that is perpendicular to the face it penetrated towards the center of the penetrating unit, and then apply all the respective forces.
I think collisions should be treated symmetrically. It doesn't matter which of the two colliding units hit which. It doesn't even matter which is bigger. Reaction force vectors should come from a formula that takes both units into account. Say, for instance, the line joining the centers of the two units, for a perfectly naive and wrong example. If using surface normals, which would be a lot less naive and more correct, the formula, non-the-less, should take the surface normals of both bodies where they come in contact, into consideration. Perhaps by computing an average of the normals. Well, I've read articles about collision detection in which the cases of a vertex hitting a facet and an edge hitting an edge are treated differently. Now, the dt can be a problem with such distinctions, as from one frame to another the situation could go from no interpenetration, to interpenetration where there's one or more vertices past one or more facets AND/or one or more edges past one or more other edges; and I think what's done to solve such problems is to subdivide the dt and backtrack to find the moment at which only one interpenetration is happening.
But in any case, I was just trying to make a case for the inherent symmetry of the collision paradigm.
User avatar
chuck_starchaser
Elite
Elite
 
Posts: 8014
Topics: 195
Joined: Thu Sep 04, 2003 9:03 pm
Location: Montreal

Postby safemode » Wed Feb 13, 2008 9:23 am

I'm not saying this is how it works, but this is how i would think it does given what i've seen in the code.

when you simulate a frame, I would think that everything has a set of vectors related to thier motion computed from the last physics frame they had. The magnitude of the vector would be directly related to the dt that that unit last had. The dt of the currently simulated unit would only be effective for the current unit, you cant apply it to the other units you're colliding with, because your dt (the time your physics frame covers) is only relevant to your current unit.

So You compute your force vectors based on your dt, _then_ you add them to the force vectors of anything that you're colliding with, The sum of those vectors then becomes your new vector for your next frame. You would also have to take the reverse of that sum and assign it to the object you're colliding with. You dont actually do any simulating of that unit, you're just setting it's force vectors to the new ones resulting from your collision (only opposite since you did (yours + others)).

This would happen for all units until eventually this unit you originally hit gets a turn. It does it's transform based on it's current force vectors and then checks for collisions and the loop continues.


In a perfect world, all collisions would be treated the same with the same equation and that would be that, because the laws of physics dont change just because you're hitting a corner rather than a face. But this is not the real world. We operate in a step by step turn based world, where things can happen in between steps that we dont see. So when those things happen, we have to make special case equations to handle them. One of these is penetrating a mesh. We should never be able to do it, BUT if we do, we need to Fudge physics so we can make sure they are no longer penetrating, but just contacting.

That's perfectly reasonable, it may never be executed given correct catching of those situations before they happen, but if it does, we need a routine to fix it.

Not that fixing this is totally important for 0.5 It's been the way it is forever. As long as we do everything the same or better than the rapid collider, we're good for 0.5. After that we can fix things.
Last edited by safemode on Wed Feb 13, 2008 9:58 am, edited 1 time in total.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby chuck_starchaser » Wed Feb 13, 2008 9:44 am

I'd take your statement a step further: Interpenetration is not an imperfect, special case in collision code; it is the standard. Collision detection IS interpenetration detection. And the degree of the interpenetration is treated as elastic deformation by the physics, although it is actual interpenetration at the geometry level. The other gottcha is that given the relative velocities and the dt, the amount of interpenetration can far exceed the assumed elastic limits. One way to solve that, when it happens, would be to make both units vaporize. Would increase the realism, too, IMO.
My argument was simply that in computing bounce vectors you can't use the surface normals of one of the objects but not the other, or any such things. Collisions are a symmetric paradigm.

Another thing that worries me now is what you say about one unit possibly being in a different simulation timeframe as another... I would think the timeframes of colliding units ought to be synchronized, as well as the frequency of the atoms maxed out ... --perhaps as soon as their bounding boxes or spheres begin to interpenetrate.
User avatar
chuck_starchaser
Elite
Elite
 
Posts: 8014
Topics: 195
Joined: Thu Sep 04, 2003 9:03 pm
Location: Montreal

Postby safemode » Wed Feb 13, 2008 10:11 am

I dont know the scheduling algo, and it may be that for every colliding object, we have the same dt across them, but i am pretty sure we prioritise simulations. Meaning, you as the player have a very high priority, Now say you're traveling fast enough so that you're now colliding with an object that had a significantly lower priority. the dt of the lower priority unit is going to be bigger than yours, at least initially. Plus, something may superscede it enough so that your unit is simulated again before that unit even has time to react once.

I dont know if that happens in practice, maybe we protect against it. I would just sooner not want to rely on dt for units that get simulated at another time. We cant guarantee the dt will be the same since some units take longer than others to simulate, and we cant preeempt anything.

I would think that most deep penatrations of meshes occur because of scheduling errors rather than the force of the ship just being so great that even our tiniest of dt's can't catch the penetration in time. So vaporizing them isn't fair. Just like i think that the rotational partial penetration of meshes when you are resting on it is due to simply VS not calling GetCollisions() because it's algo for thinking there might be a collision, doesn't work 100%.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby chuck_starchaser » Wed Feb 13, 2008 11:35 am

Well, I'm not familiar with any particular collision library; but I seem to glean from the language you use that there is asymmetry buried in it. Asymmetric collisions would be in a first person shooter when you run into a wall. Level geometry is static and considered immutable, in most cases. There's no such thing as wall physics or wall simulation atoms. The wall is a static object that a moving object runs into to the consternation of its insurer. This is a perfect example where asymmetry does work. But when an avatar or an AI runs into another such, moving objects, you need to treat the situation symmetrically.
In the case of VS, there are no walls in space. Well, maybe you could try and treat a large space station as an immutable; but even that will probably lead you to trouble in the sense that the station IS moving, and the force vectors you need to apply when considering such motion are very different from what they would be if the station was really stationary. And no, it's not enough to say that the motions of both objects are considered in collision detection. We're really talking about physics, here, which is a totally different animal. If you only consider surface normals and stuff, and use an asymmetric algorithm, what you'll end up with is forces as they would be if you assumed the object to be stationary. IOW, it will be as if during the brief instance of the collision, one of the objects had stopped moving, and your results might be spectacularly wrong. (Magical bounce ball effect to the Nth power type of thing.)
User avatar
chuck_starchaser
Elite
Elite
 
Posts: 8014
Topics: 195
Joined: Thu Sep 04, 2003 9:03 pm
Location: Montreal

Postby jackS » Wed Feb 13, 2008 12:09 pm

safemode wrote: Just like i think that the rotational partial penetration of meshes when you are resting on it is due to simply VS not calling GetCollisions() because it's algo for thinking there might be a collision, doesn't work 100%.


Setting a breakpoint a the reacttocollision function always triggered for me on rotation based collisions (when using Opcode - RAPID had more trouble detecting them), so I'm fairly certain it wasn't a case of them not being detected. As far as I could tell the above-quoted behavior was primarily due to a sign error that I fixed last night -- cross product for linearizing the angular velocity was backwards, and so the response on a purely rotational collision was correspondingly inverted.

re: vaporization of ships - I think any treatment of disintegrating vessels should be done along the lines of a damage model for non-uniform-acceleration induced structural failure (perhaps of both pilot and ship, but at least of the ship), rather than special-casing for vaporizing specifically. If the computed bounce involves 450g's of acceleration, the pilot should be raspberry jam and the ship should tear itself apart, no special-casing required :). However, at present, we don't present any ill effects to pilot or vessel as a result of acceleration, collision based or otherwise. We just apply damage as a function of the change in kinetic energy due to inelasticity of the collision (we also have the "inelastic" config variable set really low, at 0.5 instead of something in the 0.9x range, but that's a config var, so it's easy to change at leisure). If someone can come up with some reasonable (but simple) approximation for structural stresses due to non-uniform acceleration, I think this problem will solve itself. I'm tempted to think it may be sufficient to treat the deltaKE in a vector rather than scalar fashion(magnitude of initdir_normal*initKE-finadir_normal*finalKE vs. initKE-finalKE), but I haven't actually run example numbers yet.

Admittedly, it would still be possible to set the hull strength of a vessel high enough to survive, so there is a data-set element in ensuring whatever behavior is desired actually manifests, and the particular resistance of a given vessel to non-uniform accelerations may end up being a data-set issue as well, rather than a global constant, but I think those are fairly minor details with respect to coming up with a model for damage due to non-uniform acceleration.

re: asymmetry (and thanks for raising it, because I did find something) - we don't assume either object to be stationary. There is an element of asymmetry at present (and it can be fixed with a 1 line change), namely that only one of the two surface normals is currently used in determining the angle of impact relative to motion (from the look of the comment above it, I think we intended to combine it with the other vector, but forgot to actually do so after testing with using just one). However, the velocities and masses of both objects are taken into account when computing (using the point-mass momentum forms of the equations) the resultant velocities for both objects for both completely inelastic and completely elastic collision scenarios (the results of which are then combined in a linear fashion based on the inelastic scale factor in the config file). Forces are then applied to both objects, so, even if one of the objects was "stationary" before, one can rest assured (floating point roundoff error notwithstanding) that it would be moving, even if, for massive objects, only slightly.
User avatar
jackS
Minister of Information
Minister of Information
 
Posts: 1895
Topics: 56
Joined: Fri Jan 31, 2003 2:40 pm
Location: The center of Centre county

Postby safemode » Wed Feb 13, 2008 12:59 pm

Well i dont consider them not moving, you'd use the force vectors of what you collided with that were created the last time it was simulated. What i'm saying is, you may not be able to guarantee when that time was.



On another more on topic note though, it seems that initial testing of the 11837 revision of the opcode collider is good. If that keeps true (rather than talk about right or wrong, i'm focussing on regressions or not, compared to the rapid collider.) then I'll get into optimizing for memory use and speed.

The most troubling aspect of memory usage is that I can't share the Vector memory used in the bsp_polygon. Since, bsp_polygon uses Vectors to hold the points representing a vertex, and OPCODE uses Point's to hold the vertices.

I believe bsp_polygon encodes triangles that share vertices (polyhedrons > triangles) by adding vertexes on after the initial traingle, the second triangle thus shares the previous 2 vertexes + the new one. This is repeated for each additional vertex.

Unfortunately, there is no easy way to share the memory of the Vector's in the bsp_polygon with the code that uses Point's in opcode.

The way opcode would have us do it is a flat array of vertexes. No duplicates for adjacent triangles, similar to bsp_polygon doesn't duplicate. Only, since it's a flat array, to index you triangles correctly, a second class (csTriangle) hold the indexes into that flat array that make up the triangle. csTriangle is very low weight, we could even just use a simple struct of 3 ints. The flat array would be lower weight than the vector of vectors that we currently use for meshes (bsp_polygon is a vector of vectors and a mesh is a vector of bsp_polygons).

I'm interested to know why we use std::vector for this. We dont make use of iterators or all the extra features of the vector class, we just use it's auto growth feature. There are lighter weight ways of doing that, like in opcodegarray.h.


In the end, it may not even be worth all the effort at this point. We're talking maybe duplicating 32KB per mesh of 10,000 vertexes as far as copying the ints. I dont think there is a way to not have to generate separate classes to contain those because VS wants the Vector methods to do it's things, and Opcode expects me to send it Points and use those methods. So with even a Hundred separate meshes, that's not anywhere near significant when we're consuming 650MB even with the Rapid Collider.

I Guess I'll focus on speed, Worry about ram usage later.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby safemode » Wed Feb 13, 2008 2:57 pm

the bug forum had me remember a few choice defines that are hardcoded in opcodetypes.h that really will cause issues for people not using linux and not using a 64bit processor (in 64bit mode).

I really need to incorporate the VS config.h type file to import correct defines related to system info that is outputted by configure.

I guess i'll work on that next. Since that may be causing problems on computers that dont match mine.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby chuck_starchaser » Wed Feb 13, 2008 9:47 pm

@JackS+safemode: Thanks; I guess I was over-worrying about symmetry and the physics.

safemode wrote:I believe bsp_polygon encodes triangles that share vertices (polyhedrons > triangles) by adding vertexes on after the initial traingle, the second triangle thus shares the previous 2 vertexes + the new one. This is repeated for each additional vertex.
I know nothing about BSP, but that sounds to me like a text-book description of a "triangle strip", rather than a "polygon".
User avatar
chuck_starchaser
Elite
Elite
 
Posts: 8014
Topics: 195
Joined: Thu Sep 04, 2003 9:03 pm
Location: Montreal

Postby safemode » Thu Feb 14, 2008 6:26 am

well i treat them all like that, and i think the rapid collider did as well.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby safemode » Thu Feb 14, 2008 8:11 am

This is in reference to the opcode collider errata thread in the bug forum

if indeed we are seeing a1 == c1 a lot, then the index being looked at in vertexholder is off by one somehow.

I dont know how that could happen, but we can remove indexholder from the equation and just use it's indice as vertholder's. Since we flatten out verholder rather than share vertices, so the length of verholder should be the same as indexholder.


Ideally we would hold all the vertices the same way bsp_polygon does, only all in one array, and not an array of arrays.
then use indexholder to reference the vertices linearly triangle to triangle.

But when i did this, i would get segfaults. I'm not sure if the problem we're having is related to that, but it seems too coincidental to not mention. Perhaps doing it the old way, the indexholder was telling verholder to go out of bounds, or do some other nonsense.

It'd be interesting to output the values of a1 and c1 when they are equal to see if they're equal because they's both 0,0,0 or if they are really pointing at a real Point that is the same.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby jackS » Thu Feb 14, 2008 8:44 am

safemode wrote:It'd be interesting to output the values of a1 and c1 when they are equal to see if they're equal because they's both 0,0,0 or if they are really pointing at a real Point that is the same.


I'm reprinting here some of ace123's debug output from page 3 of the errata thread. It would seem to indicate that there are cases where a1==c1 and a1!=<0,0,0> (likewise for a2,c2)

(gdb) print mycollide[0]
$61 = {
a1 = {x = -5.48137808, y = -1.00708997, z = 14.3928394},
b1 = {x = -5.48137808, y = -1.94628, z = 10.8665895},
c1 = {x = -5.48137808, y = -1.00708997, z = 14.3928394},
a2 = {x = 379.748383, y = 371.284424, z = -32.9056396},
b2 = {x = 314.173096, y = 392.863007, z = -34.3534927},
c2 = {x = 379.748383, y = 371.284424, z = -32.9056396}}
User avatar
jackS
Minister of Information
Minister of Information
 
Posts: 1895
Topics: 56
Joined: Fri Jan 31, 2003 2:40 pm
Location: The center of Centre county

Postby safemode » Thu Feb 14, 2008 8:57 am

Well it's not memory corruption, it seems like somehow we're off by 1 in verholder. If it was memory corruption we'd see randomness or just a1 = 0,0,0. Here a1 has a real value, and it's the same as c1. This can only happen if we're offset by 1 in verholder.

Very troubling, i dont see how that can happen.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby safemode » Thu Feb 14, 2008 3:29 pm

so basically, bsp_polygon contains trianges and tri-strips. A mesh is made up of a series of these

I unstrip the triangle strips, for simplicity sake during this debugging phase. So the entire vertholder array is just a series of triangles. If we use a triangle-index *3 indice to vertholder, we should never be able to come up with a duplication of vertices in the same triangle. The only idea i'm coming up with is that indexholder is spitting out the wrong value (offset 1 from what it should be) or something in the pairs csCollisionPair object is gettting fubarred

Either that or perhaps I'm giving the wrong number of Triangles and Vertices to the Model object.

in svn i do index / 3 as the number of triangles. This should be true because index ends up being 3 * tri_count. Now for vertices, i send it vert_count, which should be the number of unique vertices. I assume that is correct since if it wanted the number of vertices repeating shared ones, they wouldn't need a function to tell it the number of vertices.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby chuck_starchaser » Thu Feb 14, 2008 6:58 pm

Not sure I understand; but in case it helps any... There's many cases when in a mesh vertices are duplicated or triplicated, and for good reasons:
  • Smoothing groups that the modeller defines --"here there be a sharp edge".
  • Material changes require splitting vertices. We shouldn't have material changes, but in many ships we do: One part of the ship uses one texture; another part another. Or perhaps some transparent thing uses a special material.
  • Contiguous polygons, even if of the same material, and even if in the same smoothing group, must non-the less be split if they fall in separate islands in the UV unwrap.

Morover, a modeller can set a whole section of a mesh to flat shading, and then every triangle is split from every other triangle; --e.g.: each point at which 5 or 6 triangles meet then actually has 5 or 6 vertices in the same location. So, the number of vertex locations is usually much less than the number of actual vertices.
User avatar
chuck_starchaser
Elite
Elite
 
Posts: 8014
Topics: 195
Joined: Thu Sep 04, 2003 9:03 pm
Location: Montreal

Postby safemode » Thu Feb 14, 2008 8:09 pm

i understand that tri-strips are good and all. I dont hold them in ram that way for the sake of debugging right now. the renderer still holds them that way for GL and such to use.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby safemode » Fri Feb 15, 2008 6:21 am

well, i had no time to commit anything yesterday. tonight should be better. we're so close to this bug it's aggrivating beyond words. it's gotta be something simple.

Edit:

reading up on some opcode (outdated) docs, if you set NbVertices to something that's not 3 * NbTriangles, it assumes a tri-strip setup, i believe. It changes how the tree is built. so this needs to be correct.

The actual layout of the vertices in vertholder and how they're indexed in indexholder doesn't matter. We use a callback that handles returning to opcode internals, the correct vertices. As long as we're indexing them corectly, and returning the correct indes for the requested triangle, opcode should be recieving the correct vectors.

Now, the other question we have to ask is, are we reading in bsp_polygon correctly. I'm fairly sure i am, since i'm mimicking the Rapid Collider's reading of it. Though, it doesn't copy the points, that shouldn't matter. And right now, i flatten things out so indexholder doesn't have to reference the same position multiple times (just for debugging purposes).

Then we have to ask, If geometry initialize is correct in setting up the bounding box for the radius measurement, and if vertholder and indexholder are correct, and the mesh callback function is working correctly, the what could be wrong? There are only two other possibilities.

1. Copy Collision Pairs function is not working correctly.

2. We are doing something as far as geometry that is different enough from the stock crsytalspace 3d setup, that the settings we use to give the modeller and tree builder that they're not valid for our setup.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby safemode » Fri Feb 15, 2008 9:29 pm

Update:


I had time to work on things a bit .... not a lot though.


The problem is definitely in reading in the bsp_polygon

bsp_polygon apparently has duplicate vertices in the tri-strip ... i dont know why. I dont know why the rapid Collider is immune to them either.

I am not. I'm attempting to try the collider by skipping duplicate vertices when tri-stripping.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania

Postby ace123 » Sat Feb 16, 2008 1:42 am

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.
ace123
Lead Network Developer
Lead Network Developer
 
Posts: 2560
Topics: 32
Joined: Sun Jan 12, 2003 2:13 am
Location: Palo Alto CA

Postby safemode » Sat Feb 16, 2008 1:51 am

OK, after much mulling over. I've found that it seems that every element in the bsp_polygon vector is either 3 vertices long or 6. So what i've decided to do for now is treat the 3 as a single triangle (obviously) and the 6 as two separate triangles. This may or may not be correct. But after some testing, the game is actually playable.

I've noticed some anomalies during testing however, but i think it's best to put the collider in this state, and allow some people to troubleshoot on it and maybe figure out what i'm doing wrong, Rather than the previous state of exploding on contact.

so try out -r11847 .... at the very least it should be a bit more useful.
safemode
Developer
Developer
 
Posts: 2150
Topics: 84
Joined: Sun Apr 22, 2007 6:17 pm
Location: Pennsylvania


PreviousNext

Return to Engine Development

Who is online

Users browsing this forum: No registered users and 4 guests

cron