 |
The AAS build tool maintains a BSP tree as usual. The leaves of the tree represent subspaces (convex polyhedrons) of the whole space. Polygons between leaves are created and maintained as "portals". Now the idAASBuild::MergeLeafNodes function attempts to merge some subspaces into larger ones. MergeLeafNodes_r iterates over all BSP leaves and calls MergeWithAdjacentLeafNodes, which in turn merges the leaf with all leaves adjacent by portals, until no more such merges are doable. There is some complicated logic of what can be merged and what not. idBrushBSP::TryMergeLeafNodes is called to actually perform a merge. Let's denote the currently inspected leaf as A, and the adjacent leaf as B. When merge is possible, the TryMergeLeafNodes function updates the leaf node A and deletes the leaf node B. All portals and portal-leaf references are updated correctly right here. The problem is how to update the references to leaf B in the internal BSP nodes. In order to achieve it, UpdateTreeAfterMerge_r is called. It takes bounding box of the merged node, increases it by 2 lengths units, and traverse all BSP nodes which intersect this box. If everything is right, then all references to leaf B must be seen during such traversal. They are replaced, and merging continues. While this works most of the times, in some rare cases the code misses some references. I don't know how it happens: probably portal winding calculation goes wrong. Anyway, there is some reference to deleted leaf in internal node which does not intersect the enlarged box. It is not updated, and remains in the tree: a reference to deleted node. During future traversals things go terribly wrong with this node, resulting in various crashes like double free, access violation, heap corruption, whatever else. |
|
|
Initially I thought about using backlinks from leaves to internal nodes. Actually, there is already member idBrushBSPNode::parent which serves exactly as such backlink. The problem is that this member only stores one parent. But after leaves are merged, they can have arbitrary number of parent nodes, which is not captures in this member. And such fully merged nodes can still be merged into something else later, so the parent member does not solve the problem. Turning it into a list does not sound like a good idea... Eventually, I decided to delay deleting of the nodes. After leaf node B is merged into something, it is turned into a "zombie" node. It is not a real node, but it still occupies its memory region and saves its address, so all references to it are valid yet. In such a zombie, I save a link to the node it was merged into (in the parent member). So when traversal gets into a zombie, it can go through the chain of zombie nodes and find the larger node that should be referenced there instead of the zombie. Immediately following idAASBuild::MergeLeafNodes_r call, the function idBrushBSP::PruneMergedTree_r is called to simplify the tree: remove internal nodes which point to same merged leaf on both sides. I check for zombie nodes here, and replace any links to zombies to links to corresponding merged nodes. After full BSP tree traversal, all references to zombies are replaced. Finally, all the zombie nodes are deallocated in idAASBuild::MergeLeafNodes. I have checked that .aas files are exactly equal before and after my change on the Saint Lucia map. So I'm pretty sure the change does not affect the result, unless there were some problematic references. |
|
|
Adding 0004233 and 0005037, since they are probably related. |
|
|
Committed the fix in svn rev 8669. |
- Anonymous
