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