1 (* Copyright (C) DooM 2D:Forever Developers
2 *
3 * This program is free software: you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License as published by
5 * the Free Software Foundation, either version 3 of the License, or
6 * (at your option) any later version.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 *)
16 {$INCLUDE ../shared/a_modes.inc}
17 {.$DEFINE aabbtree_many_asserts}
18 {$DEFINE aabbtree_query_count}
19 {.$DEFINE aabbtree_use_floats}
22 interface
24 uses
28 // ////////////////////////////////////////////////////////////////////////// //
29 type
33 // ////////////////////////////////////////////////////////////////////////// //
34 type
36 public
40 public
53 // ////////////////////////////////////////////////////////////////////////// //
54 type
56 public
59 private
66 public
80 // return true if the current AABB contains the AABB given in parameter
84 // return true if the current AABB is overlapping with the AABB in parameter
85 // two AABBs overlap if they overlap in the two axes at the same time
88 // ray direction must be normalized
100 // ////////////////////////////////////////////////////////////////////////// //
101 (* Dynamic AABB tree (bounding volume hierarchy)
102 * based on the code from ReactPhysics3D physics library, http://www.reactphysics3d.com
103 * Copyright (c) 2010-2016 Daniel Chappuis
104 *
105 * This software is provided 'as-is', without any express or implied warranty.
106 * In no event will the authors be held liable for any damages arising from the
107 * use of this software.
108 *
109 * Permission is granted to anyone to use this software for any purpose,
110 * including commercial applications, and to alter it and redistribute it
111 * freely, subject to the following restrictions:
112 *
113 * 1. The origin of this software must not be misrepresented; you must not claim
114 * that you wrote the original software. If you use this software in a
115 * product, an acknowledgment in the product documentation would be
116 * appreciated but is not required.
117 *
118 * 2. Altered source versions must be plainly marked as such, and must not be
119 * misrepresented as being the original software.
120 *
121 * 3. This notice may not be removed or altered from any source distribution.
122 *)
123 // ////////////////////////////////////////////////////////////////////////// //
124 (*
125 * This class implements a dynamic AABB tree that is used for broad-phase
126 * collision detection. This data structure is inspired by Nathanael Presson's
127 * dynamic tree implementation in BulletPhysics. The following implementation is
128 * based on the one from Erin Catto in Box2D as described in the book
129 * "Introduction to Game Physics with Box2D" by Ian Parberry.
130 *)
131 // ////////////////////////////////////////////////////////////////////////// //
132 // Dynamic AABB Tree: can be used to speed up broad phase in various engines
133 type
135 public
138 private
139 type
142 public
146 public
147 // a node is either in the tree (has a parent) or in the free nodes list (has a next node)
149 //nextNodeId: Integer;
150 // a node is either a leaf (has data) or is an internal node (has children)
151 children: array [0..1] of Integer; // left and right child of the node (children[0] = left child)
152 // height of the node in the tree (-1 for free nodes)
154 // fat axis aligned bounding box (AABB) corresponding to the node
156 //TODO: `flesh` can be united with `children`
160 public
161 // return true if the node is a leaf of the tree
166 //property flesh: Integer read children[0] write children[0];
172 //TVisitVisitorCB = function (abody: TTreeFlesh; atag: Integer): Boolean is nested;
178 public
179 // return `true` to stop
180 type TForEachLeafCB = function (abody: TTreeFlesh; var aabb: AABB2D): Boolean is nested; // WARNING! don't modify AABB here!
182 public
183 // in the broad-phase collision detection (dynamic AABB tree), the AABBs are
184 // also inflated in direction of the linear motion of the body by mutliplying the
185 // followin constant with the linear velocity and the elapsed time between two frames
186 {$IFDEF aabbtree_use_floats}
188 {$ELSE}
190 {$ENDIF}
192 public
193 // called when a overlapping node has been found during the call to forEachAABBOverlap()
194 // return `true` to stop
196 type TSegQueryCallback = function (abody: TTreeFlesh; ax, ay, bx, by: Single): Single is nested; // return dist from (ax,ay) to abody
207 private
210 mFreeNodeId: Integer; // id of the first node of the list of free (allocated) nodes in the tree that we can use
214 // extra AABB Gap used to allow the collision shape to move a little bit
215 // without triggering a large modification of the tree which can be costly
220 // for segment query
234 private
243 function visit (var caabb: AABB2D; mode: Integer; checker: TVisitCheckerCB; visitor: TQueryOverlapCB; visdg: TQueryOverlapDg; tagmask: Integer): Integer;
247 public
248 {$IFDEF aabbtree_query_count}
250 {$ENDIF}
252 public
256 // clear all the nodes and reset the tree
266 // returns `false` if nodeid is not leaf
269 // return `false` for invalid flesh
270 function getFleshAABB (out aabb: AABB2D; flesh: TTreeFlesh; tag: Integer): Boolean; virtual; abstract;
272 // insert an object into the tree
273 // this method creates a new leaf node in the tree and returns the id of the corresponding node or -1 on error
274 // AABB for static object will not be "fat" (simple optimization)
275 // WARNING! inserting the same object several times *WILL* break everything!
278 // remove an object from the tree
279 // WARNING: ids of removed objects can be reused on later insertions!
282 (** update the dynamic tree after an object has moved.
283 *
284 * if the new AABB of the object that has moved is still inside its fat AABB, then nothing is done.
285 * otherwise, the corresponding node is removed and reinserted into the tree.
286 * the method returns true if the object has been reinserted into the tree.
287 * the `dispX` and `dispY` parameters are the linear velocity of the AABB multiplied by the elapsed time between two frames.
288 * if the `forceReinsert` parameter is `true`, we force a removal and reinsertion of the node
289 * (this can be useful if the shape AABB has become much smaller than the previous one for instance).
290 *
291 * note that you should call this method if body's AABB was modified, even if the body wasn't moved.
292 *
293 * if `forceReinsert` = `true` and both `dispX` and `dispY` are zeroes, convert object to "static" (don't extrude AABB).
294 *
295 * return `true` if the tree was modified.
296 *)
297 function updateObject (nodeId: Integer; dispX, dispY: TreeNumber; forceReinsert: Boolean=false): Boolean; overload;
300 function aabbQuery (ax, ay, aw, ah: TreeNumber; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh;
302 function segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: TreeNumber; cb: TSegQueryCallback; tagmask: Integer=-1): Boolean;
309 {$IFDEF aabbtree_query_count}
312 {$ELSE}
315 {$ENDIF}
326 implementation
328 uses
329 SysUtils;
332 // ////////////////////////////////////////////////////////////////////////// //
333 function dtMinI (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
334 function dtMaxI (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
336 function dtMinF (a, b: TreeNumber): TreeNumber; inline; begin if (a < b) then result := a else result := b; end;
337 function dtMaxF (a, b: TreeNumber): TreeNumber; inline; begin if (a > b) then result := a else result := b; end;
340 // ////////////////////////////////////////////////////////////////////////// //
341 constructor Ray2D.Create (ax, ay: Single; aangle: Single); begin setXYAngle(ax, ay, aangle); end;
342 constructor Ray2D.Create (ax0, ay0, ax1, ay1: Single); begin setX0Y0X1Y1(ax0, ay0, ax1, ay1); end;
347 begin
355 var
357 begin
364 begin
372 begin
381 // ////////////////////////////////////////////////////////////////////////// //
383 begin
388 begin
393 begin
397 function AABB2D.getvalid (): Boolean; inline; begin result := (minX <= maxX) and (minY <= maxY); end;
399 {$IFDEF aabbtree_use_floats}
402 {$ELSE}
405 {$ENDIF}
410 begin
415 {$IF DEFINED(D2F_DEBUG)}
417 {$ENDIF}
422 begin
427 {$IF DEFINED(D2F_DEBUG)}
429 {$ENDIF}
434 begin
435 {$IF DEFINED(D2F_DEBUG)}
438 {$ENDIF}
443 {$IF DEFINED(D2F_DEBUG)}
445 {$ENDIF}
450 begin
456 begin
457 {$IF DEFINED(D2F_DEBUG)}
459 {$ENDIF}
464 {$IF DEFINED(D2F_DEBUG)}
466 {$ENDIF}
471 begin
472 result :=
479 begin
485 begin
487 // exit with no intersection if found separated along any axis
494 // something to consider here is that 0 * inf =nan which occurs when the ray starts exactly on the edge of a box
495 // https://tavianator.com/fast-branchless-raybounding-box-intersections-part-2-nans/
496 function AABB2D.intersects (var ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload;
497 var
500 begin
501 // ok with coplanars
504 // do X
506 begin
513 // do Y
515 begin
519 // tmin
523 // tmax
530 begin
534 end
535 else
536 begin
542 var
545 begin
547 // it may be faster to first check if start or end point is inside AABB (this is sometimes enough for dyntree)
550 // nope, do it hard way
560 // ////////////////////////////////////////////////////////////////////////// //
561 procedure TDynAABBTreeBase.TSegmentQueryResult.reset (); inline; begin dist := -1; flesh := Default(ITP); end;
562 function TDynAABBTreeBase.TSegmentQueryResult.valid (): Boolean; inline; begin result := (dist >= 0) and (flesh <> Default(ITP)); end;
565 // ////////////////////////////////////////////////////////////////////////// //
566 function TDynAABBTreeBase.TTreeNode.leaf (): Boolean; inline; begin result := (height = 0); end;
567 function TDynAABBTreeBase.TTreeNode.isfree (): Boolean; inline; begin result := (height = -1); end;
570 begin
584 begin
585 e_WriteLog(Format('NODE: parentId=%d; children=[%d,%d]; height=%d; tag=%d; fleshX=%d; fleshY=%d; aabb=(%d,%d)-(%d,%d)',
586 [parentId, children[0], children[1], Integer(height), tag, fleshX, fleshY, aabb.minX, aabb.minY, aabb.maxX, aabb.maxY]),
587 MSG_NOTIFY);
591 // ////////////////////////////////////////////////////////////////////////// //
592 // allocate and return a node to use in the tree
594 var
597 begin
598 // if there is no more allocated node to use
600 begin
602 // allocate more nodes in the tree
606 // initialize the allocated nodes
608 begin
615 // get the next free node
626 //e_WriteLog(Format('tree: allocated node #%d', [result]), MSG_NOTIFY);
630 // release a node
632 begin
642 //e_WriteLog(Format('tree: released node #%d', [nodeId]), MSG_NOTIFY);
646 // insert a leaf node in the tree
647 // the process of inserting a new leaf node in the dynamic tree is described in the book "Introduction to Game Physics with Box2D" by Ian Parberry
649 var
656 begin
657 // if the tree is empty
659 begin
662 exit;
667 // find the best sibling node for the new node
671 begin
675 // compute the merged AABB
680 // compute the cost of making the current node the sibling of the new node
683 // compute the minimum cost of pushing the new node further down the tree (inheritance cost)
686 // compute the cost of descending into the left child
691 // compute the cost of descending into the right child
696 // if the cost of making the current node a sibling of the new node is smaller than the cost of going down into the left or right child
699 // it is cheaper to go down into a child of the current node, choose the best child
700 //currentNodeId = (costLeft < costRight ? leftChild : rightChild);
706 // create a new parent for the new node and the sibling node
714 // if the sibling node was not the root node
716 begin
719 begin
721 end
722 else
723 begin
730 end
731 else
732 begin
733 // if the sibling node was the root node
741 // move up in the tree to change the AABBs that have changed
745 begin
746 // balance the sub-tree of the current node if it is not balanced
756 // recompute the height of the node in the tree
760 // recompute the AABB of the node
770 // remove a leaf node from the tree
772 var
775 begin
779 // if we are removing the root node (root node is a leaf in this case)
786 begin
788 end
789 else
790 begin
794 // if the parent of the node to remove is not the root node
796 begin
797 // destroy the parent node
799 begin
801 end
802 else
803 begin
804 {$IFDEF aabbtree_many_asserts}assert(mNodes[grandParentNodeId].children[TTreeNode.Right] = parentNodeId);{$ENDIF}
810 // now, we need to recompute the AABBs of the node on the path back to the root and make sure that the tree is still balanced
813 begin
814 // balance the current sub-tree if necessary
819 // get the two children of the current node
823 // recompute the AABB and the height of the current node
825 mNodes[currentNodeId].height := dtMaxI(mNodes[leftChildId].height, mNodes[rightChildId].height)+1;
830 end
831 else
832 begin
833 // if the parent of the node to remove is the root node, the sibling node becomes the new root node
841 // balance the sub-tree of a given node using left or right rotations
842 // the rotation schemes are described in the book "Introduction to Game Physics with Box2D" by Ian Parberry
843 // this method returns the new root node id
845 var
849 begin
854 // if the node is a leaf or the height of A's sub-tree is less than 2
855 if (nodeA.leaf) or (nodeA.height < 2) then begin result := nodeId; exit; end; // do not perform any rotation
857 // get the two children nodes
865 // compute the factor of the left and right sub-trees
868 // if the right node C is 2 higher than left node B
870 begin
885 begin
887 begin
889 end
890 else
891 begin
892 {$IFDEF aabbtree_many_asserts}assert(mNodes[nodeC.parentId].children[TTreeNode.Right] = nodeId);{$ENDIF}
895 end
896 else
897 begin
904 // if the right node C was higher than left node B because of the F node
906 begin
911 // recompute the AABB of node A and C
915 // recompute the height of node A and C
920 end
921 else
922 begin
923 // if the right node C was higher than left node B because of node G
928 // recompute the AABB of node A and C
932 // recompute the height of node A and C
939 // return the new root of the sub-tree
941 exit;
944 // if the left node B is 2 higher than right node C
946 begin
961 begin
963 begin
965 end
966 else
967 begin
968 {$IFDEF aabbtree_many_asserts}assert(mNodes[nodeB.parentId].children[TTreeNode.Right] = nodeId);{$ENDIF}
971 end
972 else
973 begin
980 // if the left node B was higher than right node C because of the F node
982 begin
987 // recompute the AABB of node A and B
991 // recompute the height of node A and B
996 end
997 else
998 begin
999 // if the left node B was higher than right node C because of node G
1004 // recompute the AABB of node A and B
1008 // recompute the height of node A and B
1015 // return the new root of the sub-tree
1017 exit;
1020 // if the sub-tree is balanced, return the current root node
1025 // compute the height of a given node in the tree
1027 var
1030 begin
1034 // if the node is a leaf, its height is zero
1037 // compute the height of the left and right sub-tree
1041 // return the height of the node
1046 // internally add an object into the tree
1047 function TDynAABBTreeBase.insertObjectInternal (var aabb: AABB2D; staticObject: Boolean): Integer;
1048 var
1051 begin
1052 // get the next available node (or allocate new ones if necessary)
1057 // create the fat aabb to use in the tree
1060 begin
1067 // set the height of the node in the tree
1070 // insert the new leaf node in the tree
1076 // return the id of the node
1081 // initialize the tree
1083 var
1085 begin
1091 //memset(mNodes, 0, mAllocCount*TTreeNode.sizeof);
1094 // initialize the allocated nodes
1096 begin
1105 // also, checks if the tree structure is valid (for debugging purpose)
1107 var
1111 begin
1114 // if it is the root
1116 // get the children nodes
1120 begin
1121 {$IFDEF aabbtree_use_floats}
1122 e_WriteLog(Format('AABB:(%f,%f)-(%f,%f); volume=%f; valid=%d; height=%d; leaf=%d', [pNode.aabb.minX, pNode.aabb.minY, pNode.aabb.maxX, pNode.aabb.maxY, pNode.aabb.volume, Integer(pNode.aabb.valid), pNode.height, Integer(pNode.leaf)]), MSG_NOTIFY);
1123 {$ELSE}
1124 e_WriteLog(Format('AABB:(%d,%d)-(%d,%d); volume=%d; valid=%d; height=%d; leaf=%d', [pNode.aabb.minX, pNode.aabb.minY, pNode.aabb.maxX, pNode.aabb.maxY, pNode.aabb.volume, Integer(pNode.aabb.valid), pNode.height, Integer(pNode.leaf)]), MSG_NOTIFY);
1125 {$ENDIF}
1127 begin
1129 {$IFDEF aabbtree_use_floats}
1130 e_WriteLog(Format(' LEAF AABB:(%f,%f)-(%f,%f); valid=%d; volume=%f', [aabb.minX, aabb.minY, aabb.maxX, aabb.maxY, Integer(aabb.valid), aabb.volume]), MSG_NOTIFY);
1131 {$ELSE}
1132 e_WriteLog(Format(' LEAF AABB:(%d,%d)-(%d,%d); valid=%d; volume=%d', [aabb.minX, aabb.minY, aabb.maxX, aabb.maxY, Integer(aabb.valid), aabb.volume]), MSG_NOTIFY);
1133 {$ENDIF}
1138 // if the current node is a leaf
1140 begin
1143 end
1144 else
1145 begin
1148 // check that the children node Ids are valid
1151 // check that the children nodes have the correct parent node
1154 // check the height of node
1157 // check the AABB of the node
1163 // recursively check the children nodes
1170 // also, checks if the tree structure is valid (for debugging purpose)
1172 begin
1173 // recursively check each node
1178 // return `true` from visitor to stop immediately
1179 // checker should check if this node should be considered to further checking
1180 // returns tree node if visitor says stop or -1
1181 function TDynAABBTreeBase.visit (var caabb: AABB2D; mode: Integer; checker: TVisitCheckerCB; visitor: TQueryOverlapCB; visdg: TQueryOverlapDg; tagmask: Integer): Integer;
1182 var
1187 (*
1188 procedure spush (id: Integer); inline;
1189 var
1190 xsp: Integer;
1191 begin
1192 if (sp < length(stack)) then
1193 begin
1194 // use "small stack"
1195 stack[sp] := id;
1196 Inc(sp);
1197 end
1198 else
1199 begin
1200 // use "big stack"
1201 xsp := sp-length(stack);
1202 if (xsp < length(bigstack)) then
1203 begin
1204 // reuse
1205 bigstack[xsp] := id;
1206 end
1207 else
1208 begin
1209 // grow
1210 SetLength(bigstack, length(bigstack)+1);
1211 bigstack[high(bigstack)] := id;
1212 end;
1213 Inc(sp);
1214 end;
1215 end;
1217 function spop (): Integer; inline;
1218 begin
1219 //{$IFDEF aabbtree_many_asserts}assert(sp > 0);{$ENDIF}
1220 if (sp <= length(stack)) then
1221 begin
1222 // use "small stack"
1223 Dec(sp);
1224 result := stack[sp];
1225 end
1226 else
1227 begin
1228 // use "big stack"
1229 Dec(sp);
1230 result := bigstack[sp-length(stack)];
1231 end;
1232 end;
1233 *)
1235 var
1240 begin
1242 //if not assigned(visitor) and not assigned(visdg) then raise Exception.Create('dyntree: empty visitors aren''t supported');
1243 //try
1244 {$IFDEF aabbtree_query_count}
1247 {$ENDIF}
1249 // start from root node
1250 {$IF FALSE}
1252 {$ELSE}
1254 else begin xsp := sp-length(stack); if (xsp < length(bigstack)) then bigstack[xsp] := mRootNodeId
1255 else begin SetLength(bigstack, length(bigstack)+1); bigstack[high(bigstack)] := mRootNodeId; end;
1258 {$ENDIF}
1260 // while there are still nodes to visit
1262 begin
1263 // get the next node id to visit
1264 {$IF FALSE}
1266 {$ELSE}
1269 {$ENDIF}
1270 // skip it if it is a nil node
1273 // get the corresponding node
1275 // should we investigate this node?
1278 ModeAABB:
1279 begin
1280 //doNode := caabb.overlaps(node.aabb);
1281 // this gives small speedup (or not...)
1282 // exit with no intersection if found separated along any axis
1287 ModePoint:
1288 begin
1289 //doNode := node.aabb.contains(caabb.minX, caabb.minY);
1290 // this gives small speedup
1291 doNode := (caabb.minX >= node.aabb.minX) and (caabb.minY >= node.aabb.minY) and (caabb.minX <= node.aabb.maxX) and (caabb.minY <= node.aabb.maxY);
1295 begin
1296 // if the node is a leaf
1298 begin
1299 // call visitor on it
1302 begin
1304 begin
1308 begin
1312 end
1313 else
1314 begin
1315 // if the node is not a leaf, we need to visit its children
1316 {$IF FALSE}
1319 {$ELSE}
1321 else begin xsp := sp-length(stack); if (xsp < length(bigstack)) then bigstack[xsp] := node.children[TTreeNode.Left]
1322 else begin SetLength(bigstack, length(bigstack)+1); bigstack[high(bigstack)] := node.children[TTreeNode.Left]; end;
1327 else begin xsp := sp-length(stack); if (xsp < length(bigstack)) then bigstack[xsp] := node.children[TTreeNode.Right]
1328 else begin SetLength(bigstack, length(bigstack)+1); bigstack[high(bigstack)] := node.children[TTreeNode.Right]; end;
1332 {$ENDIF}
1339 //finally
1340 // bigstack := nil;
1341 //end;
1345 // add `extraAABBGap` to bounding boxes so slight object movement won't cause tree rebuilds
1346 // extra AABB Gap used to allow the collision shape to move a little bit without triggering a large modification of the tree which can be costly
1348 begin
1355 begin
1361 // clear all the nodes and reset the tree
1363 begin
1369 function TDynAABBTreeBase.computeTreeHeight (): Integer; begin result := computeHeight(mRootNodeId); end;
1372 // return the root AABB of the tree
1374 begin
1375 {$IFDEF aabbtree_many_asserts}assert((mRootNodeId >= 0) and (mRootNodeId < mAllocCount));{$ENDIF}
1380 // does the given id represents a valid object?
1381 // WARNING: ids of removed objects can be reused on later insertions!
1383 begin
1388 // get object by nodeid; can return nil for invalid ids
1390 begin
1391 if (nodeid >= 0) and (nodeid < mAllocCount) and (mNodes[nodeid].leaf) then result := mNodes[nodeid].flesh else result := Default(ITP);
1394 // get fat object AABB by nodeid; returns random shit for invalid ids
1396 begin
1397 if (nodeid >= 0) and (nodeid < mAllocCount) and (not mNodes[nodeid].isfree) then aabb.copyFrom(mNodes[nodeid].aabb) else aabb.setDims(0, 0, 0, 0);
1401 begin
1403 begin
1405 {$IFDEF aabbtree_use_floats}
1408 {$ELSE}
1411 {$ENDIF}
1412 end
1413 else
1414 begin
1418 //if (nodeid >= 0) and (nodeid < mAllocCount) then mNodes[nodeid].dumpToLog();
1423 // insert an object into the tree
1424 // this method creates a new leaf node in the tree and returns the id of the corresponding node or -1 on error
1425 // AABB for static object will not be "fat" (simple optimization)
1426 // WARNING! inserting the same object several times *WILL* break everything!
1427 function TDynAABBTreeBase.insertObject (flesh: TTreeFlesh; tag: Integer; staticObject: Boolean=false): Integer;
1428 var
1431 begin
1433 begin
1434 {$IFDEF aabbtree_use_floats}
1435 e_WriteLog(Format('trying to insert FUCKED FLESH:(%f,%f)-(%f,%f); volume=%f; valid=%d', [aabb.minX, aabb.minY, aabb.maxX, aabb.maxY, aabb.volume, Integer(aabb.valid)]), MSG_WARNING);
1436 {$ELSE}
1437 e_WriteLog(Format('trying to insert FUCKED FLESH:(%d,%d)-(%d,%d); volume=%d; valid=%d', [aabb.minX, aabb.minY, aabb.maxX, aabb.maxY, aabb.volume, Integer(aabb.valid)]), MSG_WARNING);
1438 {$ENDIF}
1439 //raise Exception.Create('trying to insert invalid flesh in dyntree');
1441 exit;
1444 begin
1445 {$IFDEF aabbtree_use_floats}
1446 e_WriteLog(Format('trying to insert FUCKED AABB:(%f,%f)-(%f,%f); volume=%f; valid=%d', [aabb.minX, aabb.minY, aabb.maxX, aabb.maxY, aabb.volume, Integer(aabb.valid)]), MSG_WARNING);
1447 {$ELSE}
1448 e_WriteLog(Format('trying to insert FUCKED AABB:(%d,%d)-(%d,%d); volume=%d; valid=%d', [aabb.minX, aabb.minY, aabb.maxX, aabb.maxY, aabb.volume, Integer(aabb.valid)]), MSG_WARNING);
1449 {$ENDIF}
1452 exit;
1454 //e_WriteLog(Format('inserting AABB:(%f,%f)-(%f,%f); volume=%f; valid=%d', [aabb.minX, aabb.minY, aabb.maxX, aabb.maxY, aabb.volume, Integer(aabb.valid)]), MSG_NOTIFY);
1467 // remove an object from the tree
1468 // WARNING: ids of removed objects can be reused on later insertions!
1470 begin
1471 if (nodeId < 0) or (nodeId >= mAllocCount) or (not mNodes[nodeId].leaf) then raise Exception.Create('invalid node id in TDynAABBTreeBase');
1472 // remove the node from the tree
1478 function TDynAABBTreeBase.updateObject (nodeId: Integer; forceReinsert: Boolean=false): Boolean; overload;
1479 var
1482 begin
1483 if (nodeId < 0) or (nodeId >= mAllocCount) or (not mNodes[nodeId].leaf) then raise Exception.Create('invalid node id in TDynAABBTreeBase.updateObject');
1485 if not getFleshAABB(newAABB, mNodes[nodeId].flesh, mNodes[nodeId].tag) then raise Exception.Create('invalid flesh dimensions in TDynAABBTreeBase.updateObject');
1486 if not newAABB.valid then raise Exception.Create('invalid flesh aabb in TDynAABBTreeBase.updateObject');
1497 function TDynAABBTreeBase.updateObject (nodeId: Integer; dispX, dispY: TreeNumber; forceReinsert: Boolean=false): Boolean; overload;
1498 var
1502 begin
1503 if (nodeId < 0) or (nodeId >= mAllocCount) or (not mNodes[nodeId].leaf) then raise Exception.Create('invalid node id in TDynAABBTreeBase.updateObject');
1505 if not getFleshAABB(newAABB, mNodes[nodeId].flesh, mNodes[nodeId].tag) then raise Exception.Create('invalid flesh dimensions in TDynAABBTreeBase.updateObject');
1506 if not newAABB.valid then raise Exception.Create('invalid flesh aabb in TDynAABBTreeBase.updateObject');
1511 // if the new AABB is still inside the fat AABB of the node
1513 begin
1518 exit;
1521 // if the new AABB is outside the fat AABB, we remove the corresponding node
1526 // compute the fat AABB by inflating the AABB with a constant gap
1532 begin
1539 // inflate the fat AABB in direction of the linear motion of the AABB
1541 begin
1542 node.aabb.minX += LinearMotionGapMultiplier*dispX {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1543 end
1544 else
1545 begin
1546 node.aabb.maxX += LinearMotionGapMultiplier*dispX {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1550 begin
1551 node.aabb.minY += LinearMotionGapMultiplier*dispY {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1552 end
1553 else
1554 begin
1555 node.aabb.maxY += LinearMotionGapMultiplier*dispY {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1560 // reinsert the node into the tree
1568 begin
1573 // report all shapes overlapping with the AABB given in parameter
1574 function TDynAABBTreeBase.aabbQuery (ax, ay, aw, ah: TreeNumber; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh;
1575 var
1578 begin
1582 //chkAABB := AABB2D.Create(ax, ay, ax+aw, ay+ah);
1595 begin
1600 // report body that contains the given point, or nil
1601 function TDynAABBTreeBase.pointQuery (ax, ay: TreeNumber; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh;
1602 var
1605 begin
1609 {$IFDEF aabbtree_many_asserts}assert((nid < 0) or ((nid >= 0) and (nid < mAllocCount) and (mNodes[nid].leaf)));{$ENDIF}
1616 begin
1621 var
1623 begin
1625 // if the user returned a hitFraction of zero, it means that the raycasting should stop here
1627 begin
1631 exit;
1633 // if the user returned a positive fraction
1635 begin
1636 // we update the maxFraction value and the ray AABB using the new maximum fraction
1638 begin
1642 // fix curb here
1643 //curb := cura+dir*hitFraction;
1652 // segment querying method
1653 function TDynAABBTreeBase.segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: TreeNumber; cb: TSegQueryCallback; tagmask: Integer=-1): Boolean;
1654 var
1662 begin
1683 // normalize
1688 //chkAABB := AABB2D.Create(0, 0, 1, 1);