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 
Reporter  stgatilov  Assigned To  stgatilov  
Priority  normal  Severity  feature  Reproducibility  N/A 
Status  resolved  Resolution  fixed  
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) ingame, 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 axisaligned 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... 

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 