Archived

This topic is now archived and is closed to further replies.

More BSP collision stuff...

This topic is 4945 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, this is ridiculous... So i got "partially" working CD, wich of course is working really bad. But something that confuses me big time is that all the brushes seem to be moved! I am only using the trace for a ray, starting at the cameras old pos and it''s new pos. Now wouldn''t this let me pass exactly half way through a brush before i collide? Well, it dosn''t >=( It seems, as i started with, that the whole "map" of brushes is moved...or perhaps more correctly warped in some mad way... For example: I ram a wall. I hit it before i have reached it. Then i am heading over to the wall on the other side of the room. I pass the wall and collide with something a bit outside of it... And when i go through the floor, i can go far before any collision takes place, and often with the ceiling too...on some areas of the map the ceiling works, the floor dosn''t. I am thinking it might be something screwy with how i "flip" the map (making it go from XZY to XYZ). I am wondering, is there a vector i should NOT flip? Currently i flip all normals, min/maxs and vertices there is for planes, nodes, leafs and so on... Can it be this flipping that causes it or is there another, perhaps known, problem i have to pay attention to?

Share this post


Link to post
Share on other sites
I don''t really know, but it seems possible that flipping the map could screw up the plane definitions, inasmuch as the distances would no longer be correct. I never got that far with my .bsp renderer though, so I''m not sure. Could you try the whole thing without flipping the map?

Share this post


Link to post
Share on other sites
yeah, you have to be careful with flipping. dunno how your BSP tree is setup, but make sure the plane equations are consistent. It''s simply a matter of debugging your BSP collisions Make sure the floors get picked up, by say, rendering the polygons close to the character in highlights, drawing the normals and making they all go the right way, ect... Also, render the polygon you are colliding with, and see if by any chance you are colliding with a poly that seem to extend beyond their boundaries (like creating an invisible barrier). A third person perspective would be better, obviously.

also, I don''t know which algo you use for the actual coll det, I doubt you are using the Stan Melax method, but in any case, I''d recommend you have a read through his "BSP plane-shifting" docs. There can be some problems with BSP collisions, like sharp corners or sharp vertices sticking out, and basically making you collide with invisible walls. Hence his solution involving generating exta sets of virtual planes on edges and corners, to ''round'' the sharp features of the map.

The ''quake'' algo should not have to worry about those things, I think, so that should not be a problem, but in any case...

Share this post


Link to post
Share on other sites
also, you have to be careful with BSPs. they are suppose to model solid geometry, meaning, you should have all edges shared between only two triangles (not one, not three, two), and the space is well defined, with solid-empty areas. if you have big gaping holes, that can cause problems.

For things like at the edge of the map, you can be lenient, of course, but generally speaking, a BSP tree splits the world into convex empty-solid areas. If you have (black) holes (like ''singularities'' ), it''s bad. It''s like a leak from an empty area to a solid area.

Share this post


Link to post
Share on other sites
what I''d first try, is just a room with 6 walls, make sure it works, add slanted walls, a sharp edge, like a spike sticking through a wall, make sure all works, then start adding some potentially unsafe features in the map, and test the robustness. If you start straight up with a Q3 map, it''s gonna be a lot harder to debug.

Share this post


Link to post
Share on other sites
Thanks for the relplies!

Well, i tried to skip the flipping but that didn''t help much..
I still have these "invisible" walls i am colliding with...

quote:

Also, render the polygon you are colliding with, and see if by any chance you are colliding with a poly that seem to extend beyond their boundaries (like creating an invisible barrier).



Hmm, i might be wrong, but isn''t it the brush-planes i collide with, not the polygons itself?

quote:

also, I don''t know which algo you use for the actual coll det



Ahh, i should have told you at once, shouldn''t i

I am using Nathan Ostgard''s collision tutorial. I thought i would first do a copy-n-pase approach and see if i could get anything to work, and break the code down later so i can see what happens...
Much of the rendering algorithms i''ve got from GameTutorial''s BSP series so it should be fairly similar to their method...

I should point out that the algorithm used for BSP culling actually work, and that with the flipped faces. Considering what you said about the D value would be faulty i find this strange...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You might want to try to generate the plane equations yourself, instead of loading them from the bsp.
It has to be something that isn''t used by the renderer, since you apparently don''t see any problems with that.

Share this post


Link to post
Share on other sites
ok, I was just guessing stuff.

then I think I know what the problem is, in that case. And it''s a general problem of BSP collisions. Sharp features will look like extending too far. This is made worse by several factors, like the size of the object, or the angles of the walls/vertices. The sharper the angle is, the worse it becomes. So you''d end up colliding with spikes a lot, if you just use the standard BSP tree. For ray, it won''t matter, since a ray has no ''volume''.

here is an example



sphere
-------
-''''''-
/ ..... \
|.........| area where the sphere will collide, but it
|.........| | should not
\......./ | /
-....- | /
-v/--------------------------------------
|/ A
/ +------------plane a1------------
/| |................................
| |................................
| plane a0...........................
------------------ |................................
|................................
-----------------------+................................
........................................................
........................................................
........................................................
........................................................
........................................................



...it''s better explained here.

http://www.planetquake.com/qxx/bsp/

look down the bottom, and their use of "clipping hulls".

this is why I said you should not worry about this, since I thought the algo would be basically using a clipping hull BSP tree.

anyway, I think a better method is Stan melax''s dynamic plane shifting. Since it''s dynamic, there is no need for a pre-computed clipping hull, which only allow collisions with only one type of object, with a fixed, unique size.

Share this post


Link to post
Share on other sites
quote:

For ray, it won''t matter, since a ray has no ''volume''.



oliii, the thing is i am just using just that the ray test for now...
Perhaps i should look into that Stan melax shifting routine after all...

But right now i discovered something wierd. I am not flipping or anything, just drawing the map and test for collision. It seems now all planes are centered around the origo in some way.
Take Q3DM0 for example. When i''m inside the large part of the map i can hardly move at all. But when i went to the small stand-alone room, i didn''t collide with anything...

Why the vis-clip planes work is a mystery...

Is there some way i can spit our triangles representing the planes? I get a bit confused with the math...getting a triangle to align with the plane and move it along normal equal to distance...
I have a feeling it will be thick with tri''s around the origo...

...or is this just me beeing stupid?

Share this post


Link to post
Share on other sites
what you can do is when you find an intersection with a plane, get the intersection point and dot with the normal of the plane. if the plane is at the origin, then the dot product will be zero, or very close to it. That''s one simple way of checking if the plane is at the origin.

as for the stan melax thing, that should not be necessary. I mean, in the Q3 collision tutorial, they never mention ''beveling'' the planes, so it must work straight up with the their detection algorithm. The BSP must already be a clipping hull of some sort. That kind of problems would really stand out, and they would mention it in the tutorial.

"there must be something wrong somewhere"

Share this post


Link to post
Share on other sites
I had found great tutorials that cover indepth the bsp collisions in game tutorials code dump I mean tutorial 4-8

http://www.gametutorials.com/CodeDump/CodeDump_Pg1.htm

I hope it help if you haven''t checked already

Btw: how can I make an url be a link in this forum?

Share this post


Link to post
Share on other sites
< a h r e f = "http://www.gametutorials.com/CodeDump/CodeDump_Pg1.htm" >clicky< / a >

clicky


leave a space between 'a' and 'href'

[edited by - oliii on June 1, 2004 3:39:43 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by oliii
what you can do is when you find an intersection with a plane, get the intersection point and dot with the normal of the plane. if the plane is at the origin, then the dot product will be zero, or very close to it. That''s one simple way of checking if the plane is at the origin.

"there must be something wrong somewhere"


There must have been something i missed in Nathan''s tutorial, because that tutorial Cronos suggested worked nicely! Thanks Cronos
I''m now going to tear that code apart and examine it closely...try to learn exactly what happens and why, and find out what the hell i missed in Nathan''s tutorial!?

I have no problem to understand the node traversal, but it is the "simple" math i don''t quite catch...oh well i''ll guess it will come to me...

Thank you most kindliest for all replies! Oliii, you must either like this subject or have too much spare time. Thanks man!


Share this post


Link to post
Share on other sites