BSP file: a couple of question linked to geometry

Hello,

In short, I'm helping Stefan with his Realbot. I'm specially working on a automatic translation of BSP map file into the waypoints file used by Realbot. It is a mixed approach between Navmesh (merci Pierre-Marie) and usual waypoint.

As I graduated a long time ago, a lot of my mathematics has disappeared from my brain Hence, a couple of questions:

1) how can we compute the area (in square unit) of a polygon (i.e. an area defined by multiple points in the same plane) ? Splitting the face into multiple triangles seems a little too much.

2) how can we check whether a point is inside a polygon ? I know about the mathematical fact that all egdes defines a 360 degree when inside, but, again looks heavy to compute

3) as my utility is running as standalone, it does not have access to the HL engine :'( , hence the TraceHull function is not available :'( I used Botman TraceLine but how can we emulate the TraceHull ?

3.1) what are the 'sizes' of point_hull, head_hull, human_hull ? It looks like the shape of a human player when standing is 16x16x76 and when duckinc 16x16x36, is it correct ?

3.2) how can we handle the de_aztec bridge, the utility cannot waypoint it probably because it cannot 'feel' the ground as the brigde has holes :'(

Thanks in advance for any piece of information

-eric

PS: for this interested, the utility is not rocket science and is based on Pierre-Marie's ideas of navmesh combined with a lot of algorithms & code from Botman. The code is in the realbot CVS repository under Bsp2Rbn directory.

[sfx1999]

Originally Posted by evy

1) how can we compute the area (in square unit) of a polygon (i.e. an area defined by multiple points in the same plane) ? Splitting the face into multiple triangles seems a little too much.

This is very problematic. You could probably use another equation for rectangles, but what if you end up getting a trapezoid? You might as well just split them into triangles.

2) how can we check whether a point is inside a polygon ? I know about the mathematical fact that all egdes defines a 360 degree when inside, but, again looks heavy to compute

Generate a plane for the polygon and then check to see if it is in that plane. after that you can check to see if it is within the polygon.

3) as my utility is running as standalone, it does not have access to the HL engine :'( , hence the TraceHull function is not available :'( I used Botman TraceLine but how can we emulate the TraceHull ?

What does TraceHull do? I might be able to help you if I knew.

3.1) what are the 'sizes' of point_hull, head_hull, human_hull ? It looks like the shape of a human player when standing is 16x16x76 and when duckinc 16x16x36, is it correct ?

I believe it is 32x72x32, 72 units tall, 32 units wide, and 32 units deep.
Crouching it is 32x36x32.

3.2) how can we handle the de_aztec bridge, the utility cannot waypoint it probably because it cannot 'feel' the ground as the brigde has holes :'(

My guess is you would get a simulated person to walk across it and see if they could. Also, the bridge may have a clip brush in between. You could also just put a point on anything the bot can stand on and test if they can get across it.

[Whistler]

Take a look at Quake1 engine source code for the TraceHull code.

It can be found at http://www.idsoftware.com, at the Technolody Download page.

Look at the SV_Move() function and what it called.

PS, I think the HL routine is identical as the Quake1 routine.

[sfx1999]

If you use Quake code you will have to comply with the terms of the GPL.

[Pierre-Marie Baty]

Originally Posted by evy

1) how can we compute the area (in square unit) of a polygon (i.e. an area defined by multiple points in the same plane) ? Splitting the face into multiple triangles seems a little too much.

I don't know any other solution than splitting it into triangles, indeed... that's not hard to do, enumerate the corners successively, take 3 successive ones, they form a triangle, compute the area, remove the middle corner of the 3 from the corners list and do it again and again until you end up with only 2 corners, that's when you've covered the face entirely.

2) how can we check whether a point is inside a polygon ? I know about the mathematical fact that all egdes defines a 360 degree when inside, but, again looks heavy to compute

I don't know any better method. That's the one I am using in my bot code.

3) as my utility is running as standalone, it does not have access to the HL engine :'( , hence the TraceHull function is not available :'( I used Botman TraceLine but how can we emulate the TraceHull ?

It *is* possible to use TraceHull without the HL engine because a TraceHull is a version of TraceLine that works in a "fattened" world. Since there are 3 hulls (or is it 4 ?) in this game, 3 chunks of the map geometry are stored in the BSP file. The first one corresponds to TraceLine (which is in fact TraceHull+point_hull), and the successive ones correspond to each of the TraceHulls.

3.1) what are the 'sizes' of point_hull, head_hull, human_hull ? It looks like the shape of a human player when standing is 16x16x76 and when duckinc 16x16x36, is it correct ?

point_hull == traceline
head_hull == ducking player
human_hull == standing player

3.2) how can we handle the de_aztec bridge, the utility cannot waypoint it probably because it cannot 'feel' the ground as the brigde has holes :'(

using a TraceHull
But if you don't want to do that (as I do), then you consider that the bridge is straight, and that there is a direct connection from one end of the bridge to the other. It's as if the bot was jumping off a cliff to land on another, except that here it won't fall but cross a bridge (even if the bot doesn't "feel" it that won't prevent it to cross it successfully).

Pierre-Marie,

First thanks for the information (as well as sfx1999, Whistler).

It *is* possible to use TraceHull without the HL engine because a TraceHull is a version of TraceLine that works in a "fattened" world.

Do you mean that there is a TraceHull function (or a similar one) in the HLDSK? I grepped through the HLDSK and it looked (but I can be wrong) that TraceHull is actually implemented in the HL engine itself (as it is called through a pointer of a function).

Did I miss something ? I would be delighted

Since there are 3 hulls (or is it 4 ?) in this game, 3 chunks of the map geometry are stored in the BSP file. The first one corresponds to TraceLine (which is in fact TraceHull+point_hull), and the successive ones correspond to each of the TraceHulls.

Not sure that I understand you correctly... Are there really three copies of the map in the BSP file? And one for each hull ? (assuming then that the blocks have been widened/fattened with ketchup & fries in order to have less space among them).

Thanks again

Merci beaucoup

-eric

PS: PM, funny that my brother in law has exactly the same first name as you

PS2: for de_aztec bridge, I made further test. It seems linked to the use of the Botman TraceLine: it never detects the bridge itself, I'm afraid that the bridge is not a worldspawn block but rather a func_wall entity... So, I'll need to extend TraceLine to handle func_wall entities :'(

[Whistler]

"If you use Quake code you will have to comply with the terms of the GPL."
...and if you use Metamod code (i.e., make the bot as a metamod plugin) or botman's BSP tools code you also will have to comply with the GNU GPL. (and is it so bad ?)

@evy: the bridge in de_aztec is func_illusionary. and it even does not block tracelines in the HL engine.
and there's no implemention of traceline/hull in HLSDK btw, I think what he means is to make one yourself in the code, and you just need to thicken the walls and use traceline.

Originally Posted by Whistler

"If you use Quake code you will have to comply with the terms of the GPL."
...and if you use Metamod code (i.e., make the bot as a metamod plugin) or botman's BSP tools code you also will have to comply with the GNU GPL. (and is it so bad ?).

Of course not It was always my intention to make the code public (which is already the case as everyone can access it in the realbot CVS repository).

I'll have to put the GPLize the comments in every source file (no clue how to do it -- I'll look in another GPL package) but this will be done.

Originally Posted by Whistler

@evy: the bridge in de_aztec is func_illusionary. and it even does not block tracelines in the HL engine.
and there's no implemention of traceline/hull in HLSDK btw, I think what he means is to make one yourself in the code, and you just need to thicken the walls and use traceline.

Found the func_illusionary last night as well Working now!

Thickening the walls looks more complex than shooting a couple of TraceLine even if less efficient. I do not really understand the node structure of a BSP file and I do not want to re-invent a MAP compiler

THANKS all for the help

-eric

[Pierre-Marie Baty]

Originally Posted by evy

Not sure that I understand you correctly... Are there really three copies of the map in the BSP file? And one for each hull ? (assuming then that the blocks have been widened/fattened with ketchup & fries in order to have less space among them).

Exactly. Given the amount of ketchup & fries (point_hull, head_hull and human_hull) you will trace a "bigger" line in the world, which is exactly the same thing as if you were tracing the same line in three "fatter" worlds. Storing 3 maps in one, that's the concept the ID programmers invented to find out easily the limits of where a player can move and where it can not.

TraceLine and TraceHull are the same thing, they call the same function in the engine: SV_RecursiveHullTrace(). Look in any of the Quake's source code to find out how this function works and how to make yours work with HL BSP files.

Exactly. Given the amount of ketchup & fries (point_hull, head_hull and human_hull) you will trace a "bigger" line in the world, which is exactly the same thing as if you were tracing the same line in three "fatter" worlds. Storing 3 maps in one, that's the concept the ID programmers invented to find out easily the limits of where a player can move and where it can not

.

Pierre-Marie,

You were right: by digging in the code and by using my crystal ball :

- BSP contains information about 4 hulls: visibility (=point_hull), human, head and large
- hull0 = pointhull starts on nodes 0 (i.e. the nodes 'lump') for worldspawn
- other hulls start on model->headnode[hullNumber] and use clipnodes (i.e. the clipnodes 'lump') instead of nodes

The algorithm to parse the node tree is the same (I used first Botman's TraceLine which is easier to understand).

Thanks for everyone's help

-eric