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.

Re: BSP file: a couple of question linked to geometry
 

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.

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.

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

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

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.

Re: BSP file: a couple of question linked to geometry
 

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.

Re: BSP file: a couple of question linked to geometry
 

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

Re: BSP file: a couple of question linked to geometry
 

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.

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

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.

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

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).

Re: BSP file: a couple of question linked to geometry
 

Pierre-Marie,

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

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 =)

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 :D

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 :'(

Re: BSP file: a couple of question linked to geometry
 

"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.

Re: BSP file: a couple of question linked to geometry
 

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.

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 8)

THANKS all for the help

-eric

Re: BSP file: a couple of question linked to geometry
 

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.

Re: BSP file: a couple of question linked to geometry
 

.

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