View Issue Details
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0006083||The Dark Mod||Coding||public||27.08.2022 11:36||27.08.2022 13:23|
|Product Version||TDM 2.10|
|Target Version||TDM 2.11||Fixed in Version||TDM 2.11|
|Summary||0006083: Find portal area by index|
|Description||The 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.
|Tags||No tags attached.|
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...
|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|