Page 1 of 2

Q1 BSP tree

Posted: Thu Feb 05, 2015 6:41 pm
by Cobalt
Can anyone here explain this or add to my impression of it? I had chatted with LH about it and from what I understand its responsible for how Q1 detects collisions with respect to setsize in that, only point ,player and Shambler size hulls will perform a collision. As a side note, I have concluded that you CAN setsize to any size within reason and dont have to stay in those bouinds as long as the ent is NOT moving. The collision issues where objects start falling through walls haphazardly happen when they are spawned inside another bounding box of another ent or are moving with a non point, player or shambler size.

Lord Havoc says that the Q3 map tree has resolved this and it will detect any hull size collisions. Is there a way to "hack" this in the q1 engine so that all the sizes are collidable in the same way , or would the maps have to be converted to the q3 system?

Re: Q1 BSP tree

Posted: Thu Feb 05, 2015 7:19 pm
by Spike
Q2+Q3 don't actually use the bsp tree for collision, it only uses the tree to efficiently find convex brushes against which you might collide, this means that it can safely follow the wrong nodes and no actual harm comes from it.

Q1 uses pure bsp collision and as a result contains 3 separate bsp trees, not just one - point, player, shambler. the brushes that originally formed the map are expanded by the size of the hull before the tree is built. But the real pain is that the most precise tree - the point tree - has the clip brushes removed. clip brushes work by only existing in player+shambler hulls, thus allowing point-sized projectiles through but not monsters nor players.
this is the same problem you find with polygon collision methods too.
While its possible to convert a Q1 map into a Q2 one, doing so always looses the clip brushes, and that often makes the map not worth playing as you end up getting stuck on every corner.

For comparison, doom didn't use its bsp tree for collisions at all. Doom used a 2d blockmap thing that has lists of the various linedefs embedded in them. it just does 2d 'poly' collisions, and its players are cylinders.

Re: Q1 BSP tree

Posted: Fri Feb 06, 2015 12:36 am
by Cobalt
Thanks Spike.

So I guess its possible but with alot of work.

When you explained the 2d Doom collision thing, it reminded me of the funct in QC EntitiesTouching (), which is what the doors use to detect collisions with each other I believe. I recently modified that code to detect collision with absmin / absmax which seems to me more or less how a .touch field works , at least in my experience. Why couldnt we call a funct like that every frame as the ent moves and compare to world for example, and do collision that way?
Or is this really just the same problem again?

Re: Q1 BSP tree

Posted: Fri Feb 06, 2015 4:07 am
by frag.machine
You can split collision handling in Quake in two approachs:

a) entity versus entity - you can set any arbitrary AABB with setsize(), and the engine will use it (be aware though of details like MOVETYPE_FLYMISSILE adding 16 units to the AABB you specified, for example);

b) entity versus world - as Spike said, your AABB is rounded to point, player or shambler size, and collision is tested against the appropriate hull. The relevant hull info is retrieved walking thru the BSP tree.

BTW I never understood why Quake just dont always use the point size hull for collision. If I understand correctly Q2 and Q3 just work this way. Is there any real advantage in terms of performance or memory usage to use the point/player/shambler scheme ? Or was it just a weird idea that could not be ditched without screwing legacy maps ?

Re: Q1 BSP tree

Posted: Fri Feb 06, 2015 4:51 am
by Spike
frag.machine wrote:BTW I never understood why Quake just dont always use the point size hull for collision. If I understand correctly Q2 and Q3 just work this way.
> Q2+Q3 don't actually use the bsp tree for collision blah blah blah convex brushes blah blah.
Q1 doesn't store ANY information on the original brushes, ergo, you cannot collide against brushes in Q1 unlike Q2.
Changing the map format by adding that info defeats the entire point of sticking with Q1 bsp.
FTE is actually already able to add (additional) brush info into q1 bsps, but there's no qbsp that supports it right now, no vis or light tools that won't strip it, and its basically completely pointless because you might as well have just used q2/q3 bsps in the first place.

if you test to see if something is touching the world based upon its bounding box, you lose any support for rotated brushes. Also, technically EVERY entity is within the world's bounding box. Ergo, everything is touching the world. Ergo, nothing can move. Ergo, very broken game.
You could build a bounding box for each leaf, and test against that, sure... But remember that there is only one leaf that is marked as solid - ergo, everything in the world is contained within that solid leaf's bounding box. See start of paragraph.

Long story short, Q1 bsps DO NOT contain nice convex shapes (q2 inflates the world - the thing traced through the world is technically always a point, just with the walls pushed outwards). Q1 bsps CANNOT be 'inflated' outwards to cope with different player sizes/shapes. This is the same reason that decompilers for Q1 bsps are quite poo.
You COULD use polygon collision, but that will break clip brushes, so would just feel horribly buggy in the eyes of most users.
If an offline BSP decompiler can't cope with clip brushes, how the heck do you think an engine could do it on the fly?

Re: Q1 BSP tree

Posted: Fri Feb 06, 2015 5:31 am
by frag.machine
Spike wrote:
frag.machine wrote:BTW I never understood why Quake just dont always use the point size hull for collision. If I understand correctly Q2 and Q3 just work this way.
> Q2+Q3 don't actually use the bsp tree for collision blah blah blah convex brushes blah blah.
Q1 doesn't store ANY information on the original brushes, ergo, you cannot collide against brushes in Q1 unlike Q2.
Yes,of course, I can understand that no original brush info makes this impractical. What I have a hard time understanding is what drove Carmack to decide by this clumsy solution instead of just working with the actual brush info. Better performance or some memory saving maybe ? I can't see the reasoning, the "why" that led to what we have.

Re: Q1 BSP tree

Posted: Fri Feb 06, 2015 5:58 am
by Cobalt
If I were to guess I would say time factor - pressure to release the next greatest evolution in 3d gaming and get another Ferrari.
Says here he wound up with 4 and had to give one away.


http://floodyberry.com/carmack/johnc_pl ... #d19970506

But I think this stuff we are rehashing they already gave closer thought in q2 and 3 an as Spike described, they came up with those schemes....which also seem to have left the BSP format as obsolete more or less, except apparently the q3 maps dont have lightstyle capability or ot works very badly.

Also when you look at the other issue that winds up cloaely related to this are the AABB's. The boxes dont rotate as the model rotates, and if I learned this correctly, you can only shape the setsize boxes at perfectly square angles, IE: 0, 90, 180 and 360 degree positions. While you can point the model angles anywhere. So when you spawn a model its assumed to be at I guess one of those angles relative to world, or maybe its relative to itself only? Not sure, but that also is a factor on collision because when the model moves and is pointed say like a nail or rocket you could in the physics of a real world, shape the bounding boz to very closely meet the dimensions of your model. In fact LH has told me the engine originally did do that, and it was he reasoning behind setmodelrealbox gameplay fix cvar. So if you have that cvar active the engine will give you a very nicely shaped rectangle around your model , not obeying point, player or shablmer restrictions. However when its launched, you change its relative position to where it was originally spawned, but the bounding box does not adjust accordingly, so you have collision issues again.

frag.machine wrote: I can't see the reasoning, the "why" that led to what we have.

Re: Q1 BSP tree

Posted: Fri Feb 06, 2015 6:57 pm
by Cobalt
Hmm so I guess q1 maps more or less , at least the standard ID ones the artists were more or less allowed to 'freehand' , and draw slopes at very unusual angles and such, or am I completely off base in that summization? I have researched the format a little and seems its more or less based on triangles ?

Also interested with poly collisions. Would they be 100% reliable if not for clip brushes?
Spike wrote: Long story short, Q1 bsps DO NOT contain nice convex shapes (q2 inflates the world - the thing traced through the world is technically always a point, just with the walls pushed outwards). Q1 bsps CANNOT be 'inflated' outwards to cope with different player sizes/shapes. This is the same reason that decompilers for Q1 bsps are quite poo.
You COULD use polygon collision, but that will break clip brushes, so would just feel horribly buggy in the eyes of most users.
If an offline BSP decompiler can't cope with clip brushes, how the heck do you think an engine could do it on the fly?

Re: Q1 BSP tree

Posted: Sat Feb 07, 2015 2:01 pm
by Spiney
Q3 lightstyles are fairly usable, they're simply shaders generated by the compiler.
As such, they don't influence the lightgrid and take some perf hit (though should be fine on a modernized renderer, i suppose).
http://q3map2.robotrenegade.com/docs/sh ... tyles.html

Q3 bsp and Q1 toolchains/mapping culture don't mix that well though.

*upd: triggered shader...
http://www.simonoc.com/pages/articles/trigshaders1.htm
http://www.quake3world.com/forum/viewto ... 10&t=44384
tl:dr; globally triggerable shaders in Q3 = sure, triggerable lightstyles in Q3 = nope.

Re: Q1 BSP tree

Posted: Sat Feb 07, 2015 3:35 pm
by Spike
q3 lightstyles are perhaps usable, but they're still not switchable.
wads+textures is another issue for Q1 mappers trying to create Q3bsps instead, which is probably a bigger annoyance to anyone trying to make q3 bsps with a q1 .map tool.

Re: Q1 BSP tree

Posted: Sun Feb 08, 2015 5:40 am
by mankrip
Very informative thread. I always forget to think about the collision hulls stuff, even though they make it harder to create games with different gameplay.

Q2 BSP seems to be the way to go for original games. Still familiar to Q1 mappers, but without such gameplay limitations.

Re: Q1 BSP tree

Posted: Fri Feb 27, 2015 4:15 pm
by Cobalt
Hrm, thanks to those who replied. I guess there really is no upgrade or modification possible either via an engine hack or alteration of the BSP spec that would resolve the clipping issues or collision issues I was looking to overcome. Sounds like any attempt to do so would mean rewriting many things and simpler to use q2 or q3 map formats...however to my knowledge the original Quake ID maps have not been converted to any of those and I am guessing its just not possible to do so.

Re: Q1 BSP tree

Posted: Fri Feb 27, 2015 7:29 pm
by Dr. Shadowborg
Cobalt wrote:Sounds like any attempt to do so would mean rewriting many things and simpler to use q2 or q3 map formats...however to my knowledge the original Quake ID maps have not been converted to any of those and I am guessing its just not possible to do so.
It's actually quite possible. IIRC, OpenArena had a conversion of some Q1 DM maps to Q3BSP.

Also, I'm working on modifying jitspoe's version of the DeWan qbsp3 to read Valve220 / Jackhammer Q2 .map formats, in preparation for converting all of episode 1 to Q2BSP. (I intend to fix misaligned textures and rely on radiosity for lighting, should look pretty awesome...)

Dunno about the legality of converting (and releasing as .bsp) any of the other episodes though...

Re: Q1 BSP tree

Posted: Sat Feb 28, 2015 3:24 pm
by goldenboy
It is quite possible to convert q1 -> q3 and the Quake maps are GPL anyway.

Re: Q1 BSP tree

Posted: Sun Mar 01, 2015 12:16 am
by mankrip
Dr. Shadowborg: It's only a problem if you distribute the registered episode's textures with them.

Use some placeholder textures with the same names instead, and you're fine.