next »

[fruitfly]

Hi there,
I am reading the Quake 2/3 source code's collision detection of the player against the world brushes. Basically, this post outlines it step by step: http://openzone.googlecode.com/git-history/f73bb8dfe8e6a16c13d39aba1c8f6537ee263d07/doc/Quake3BSP.html
I am not even talking about the spere or box testing; rather the simple trace of a point/line as describes in the first CheckBrush example and i am failing to understand why this code should work. I can see it working in some special cases but for line/traces like this, i cannot see how this should work:
https://www.dropbox.com/s/uu18bltkhsv26y7/Untitled.png?dl=0 I think we agree that the blue line should not be clipped as it is fully outside the brush; nevertheless, i would say the algorithm will clip it to one of the marked points because:
a)

Code:

if (startDistance > 0 && endDistance > 0)
{   // both are in front of the plane, its outside of this brush
    return;
}

does not apply for any of the planes

b) the code thereafther assumes that a face equals a plane. obviusly a face has some extent; a plane is infinite and thus if the start and end of the line line on different sides of the plane, it does not automatically mean the line is entering the brush.
Am i missing something or is the code not working as advertised in 100% of the cases? Maybe someone more familiar with id's source code can shed some light on it for me.

Thanks, Daniel

[Interface]

Tried to implement this once, but failed. Constantly got stuck in corners. Floor collision worked great though And at least I got the rendering of the BSP tree down. Ended up using Newton for physics and collision detection instead!

To your question though, I'm not sure what you mean by your (a) does not apply for any of the planes.

As for the planes issue, your brush is made up of several planes that intersect to make the brush's volume. You loop the planes of the brush and yes your plane is infinite so it may be a false positive, but in that case you'll just continue checking against the other planes until you have a definitive conclusion of true or false.

[fruitfly]

well what i mean with a) is that in my diagram none of the planes passes the test (// both are in front of the plane, its outside of this brush). So, like you say, it loops through all planes and will not do the "return".

The stuff you describe thereafter are very general. i know that it loops through the planes, please explain based on my example diagram how the algorithm comes to the point that it has the conclusion that start and end of the trace do not need to be clipped. the whole line should pass the trace.

[jgrams]

Am i missing something?

Yeah, you're missing what happens in that case (which actually happens quite a bit).



The red plane says "this part of the line is inside" and the green plane says "this part of the line is inside" and as you can see, there is no overlap between those two parts (the arrows point away from each other). So when you get to the end of the routine, the check for startFraction < endFraction will fail.

That's why you can just work with infinite planes instead of finite faces: effectively all the planes get clipped by all the other planes. Dunno if that's enough explanation...does it make sense to you?

Edit: I should probably say that what you're doing is clipping the line against each plane (half-space), keeping only the part which is on the "inner" side. If there's none of the line left, then it doesn't intersect the brush. So the if statement you mentioned in your OP is an optimization, an early exit. It's not the only way for the line to be outside the brush.

[fruitfly]

yes, it makes sense now. took ten minutes to wrap my head around it and then it was clear to me that this works in my described case. when i came back and read your final note i almost slammed my head on the table for not recognising that this is straight-forward line-clipping. it did not snap until this last note clarified that startfraction and endfraction really define the line-segment "within the brush".

Thanks,
daniel