View Issue Details

IDProjectCategoryView StatusLast Update
0006083The Dark ModCodingpublic27.08.2022 13:23
Reporterstgatilov Assigned Tostgatilov  
Status resolvedResolutionfixed 
Product VersionTDM 2.10 
Target VersionTDM 2.11Fixed in VersionTDM 2.11 
Summary0006083: Find portal area by index
DescriptionThe engine strongly depends on areas connected by portals, ad many internal information prints area indices.
However, there is no simple way to find an area by number:
  1) DarkRadiant has no information about areas yet.
  2) dmap knows about areas, but cannot display anything --- not suitable for debug tools.
  3) in-game, we can learn which area we are in (r_showPortals 2), but we can't teleport to specified area.

Looking deeper, it turns out that finding a point in area is actually a hard algorithmic problem.
There are two representations for areas available:
  1) Models (triangular meshes) generated by dmap, called "_areaN". Sometimes they are empty though.
  2) BSP tree in .proc file defines which parts of the space belong to which areas. But one has to cull windings in order to find even a bounding box of it.

There are functions to find which area given point is in, and to find all areas which possibly intersect with given box.
But in finding a point inside area (preferably at large distance) is not as easy as returning the center of bounding box.
TagsNo tags attached.




27.08.2022 13:23

administrator   ~0015214

A few preparational commits:
  r10095 Renamed idRenderWorld::PointInArea to GetAreaAtPoint.
  r10096 idRenderWorldLocal::BoundsInAreas renamed to FindAreasInBounds.
  r10097 Added Last method to all list containers.

And then the actual implementation:
  r10098 Implemented algorithm to find a point inside area, and teleportArea command.

The idea is to take the bounding box of the area, then cover this box with a regular grid of points.
Then check all these points: 1) is it inside the area? 2) how far from the closest obstacle is it?
Then select the point which is inside and at farthest distance.

Even if I could implement this exact algorithm, it is not reliable, because there is chance that all checked points are magically outside the area.
In fact, this can happen quite easily if used bounding box is very loose, i.e. much larger than a tight one.

First of all, I don't know of a way to find distance from point to closest obstacle in BSP tree.
Instead, I check distance in 6 axis-aligned direction (raytracing BSP works perfectly well), and get a total "score" out of these values, which I then try to maximize/minimize.
The score is sum(1 / dist^2) for all 6 distances, with distance by Z scaled down 10 times ==> this score is minimized.
This score is some kind of mix between "minimum distance" and "average distance".

The real algorithm is a bit more efficient.
Instead of tracing 6 N^3 rays, I trace 3 N^2 line segments, i.e. each different line is traced once, but with complete description of intersection returned.
That's what I added RecurseFullLineIntersectionBSP_r for.

The last problem is quite surprising: it is very hard to find bounding box of an area.
Yes, there is "_areaN" model/mesh, and its bounds can be used.
But these bounds not always contain the whole area, moreover sometimes they are simply empty (imagine empty space surrounded by 6 visportals).

To fix this problem, I added bounding box of all visportals too.
But this visportals are often much larger than area, which results in a loose bounding box.
Sometimes it even leads to a fail because all grid points are not in area =(

In the end, I try one grid of points with bounding box of the model only, then second grid of points with bounding box of model + portals.
It seems to work fine.
Of course, proper way of computing boxes is to take every BSP leaf of the area, collect all planes on path from root to the leaf, then turn this set of planes into a brush with all windings computed, then take their bbox.
This is quite some code to write, and basically the same thing that dmap does. Not sure I want to do that...

Issue History

Date Modified Username Field Change
27.08.2022 11:36 stgatilov New Issue
27.08.2022 11:36 stgatilov Status new => assigned
27.08.2022 11:36 stgatilov Assigned To => stgatilov
27.08.2022 13:23 stgatilov Note Added: 0015214
27.08.2022 13:23 stgatilov Status assigned => resolved
27.08.2022 13:23 stgatilov Resolution open => fixed
27.08.2022 13:23 stgatilov Fixed in Version => TDM 2.11