5ebc8851c5a087810ba212172b6c5cfbe9e44afb
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
27 // ////////////////////////////////////////////////////////////////////////// //
28 type
30 //PFloat = ^Float;
35 // ////////////////////////////////////////////////////////////////////////// //
36 type
38 public
42 public
55 // ////////////////////////////////////////////////////////////////////////// //
56 type
58 public
61 private
68 public
82 // return true if the current AABB contains the AABB given in parameter
86 // return true if the current AABB is overlapping with the AABB in parameter
87 // two AABBs overlap if they overlap in the two axes at the same time
90 // ray direction must be normalized
91 function intersects (const ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload;
102 // ////////////////////////////////////////////////////////////////////////// //
103 (* Dynamic AABB tree (bounding volume hierarchy)
104 * based on the code from ReactPhysics3D physics library, http://www.reactphysics3d.com
105 * Copyright (c) 2010-2016 Daniel Chappuis
106 *
107 * This software is provided 'as-is', without any express or implied warranty.
108 * In no event will the authors be held liable for any damages arising from the
109 * use of this software.
110 *
111 * Permission is granted to anyone to use this software for any purpose,
112 * including commercial applications, and to alter it and redistribute it
113 * freely, subject to the following restrictions:
114 *
115 * 1. The origin of this software must not be misrepresented; you must not claim
116 * that you wrote the original software. If you use this software in a
117 * product, an acknowledgment in the product documentation would be
118 * appreciated but is not required.
119 *
120 * 2. Altered source versions must be plainly marked as such, and must not be
121 * misrepresented as being the original software.
122 *
123 * 3. This notice may not be removed or altered from any source distribution.
124 *)
125 // ////////////////////////////////////////////////////////////////////////// //
126 (*
127 * This class implements a dynamic AABB tree that is used for broad-phase
128 * collision detection. This data structure is inspired by Nathanael Presson's
129 * dynamic tree implementation in BulletPhysics. The following implementation is
130 * based on the one from Erin Catto in Box2D as described in the book
131 * "Introduction to Game Physics with Box2D" by Ian Parberry.
132 *)
133 // ////////////////////////////////////////////////////////////////////////// //
134 // Dynamic AABB Tree: can be used to speed up broad phase in various engines
135 type
137 private
138 type
141 public
145 public
146 // a node is either in the tree (has a parent) or in the free nodes list (has a next node)
148 //nextNodeId: Integer;
149 // a node is either a leaf (has data) or is an internal node (has children)
150 children: array [0..1] of Integer; // left and right child of the node (children[0] = left child)
151 //TODO: `flesh` can be united with `children`
153 // height of the node in the tree (-1 for free nodes)
155 // fat axis aligned bounding box (AABB) corresponding to the node
158 public
159 // return true if the node is a leaf of the tree
164 //property flesh: Integer read children[0] write children[0];
168 //TVisitVisitorCB = function (abody: TTreeFlesh; atag: Integer): Boolean is nested;
170 public
171 // return `true` to stop
172 type TForEachLeafCB = function (abody: TTreeFlesh; const aabb: AABB2D): Boolean is nested; // WARNING! don't modify AABB here!
174 public
175 // in the broad-phase collision detection (dynamic AABB tree), the AABBs are
176 // also inflated in direction of the linear motion of the body by mutliplying the
177 // followin constant with the linear velocity and the elapsed time between two frames
178 {$IFDEF aabbtree_use_floats}
180 {$ELSE}
182 {$ENDIF}
184 private
187 mFreeNodeId: Integer; // id of the first node of the list of free (allocated) nodes in the tree that we can use
191 // extra AABB Gap used to allow the collision shape to move a little bit
192 // without triggering a large modification of the tree which can be costly
195 public
196 // called when a overlapping node has been found during the call to forEachAABBOverlap()
197 // return `true` to stop
199 type TSegQueryCallback = function (abody: TTreeFlesh; ax, ay, bx, by: Single): Single is nested; // return dist from (ax,ay) to abody
209 private
218 function visit (checker: TVisitCheckerCB; visitor: TQueryOverlapCB; tagmask: Integer=-1): Integer;
220 public
221 {$IFDEF aabbtree_query_count}
223 {$ENDIF}
225 public
229 // clear all the nodes and reset the tree
239 // return `false` for invalid flesh
242 // insert an object into the tree
243 // this method creates a new leaf node in the tree and returns the id of the corresponding node or -1 on error
244 // AABB for static object will not be "fat" (simple optimization)
245 // WARNING! inserting the same object several times *WILL* break everything!
248 // remove an object from the tree
249 // WARNING: ids of removed objects can be reused on later insertions!
252 (** update the dynamic tree after an object has moved.
253 *
254 * if the new AABB of the object that has moved is still inside its fat AABB, then nothing is done.
255 * otherwise, the corresponding node is removed and reinserted into the tree.
256 * the method returns true if the object has been reinserted into the tree.
257 * the `dispX` and `dispY` parameters are the linear velocity of the AABB multiplied by the elapsed time between two frames.
258 * if the `forceReinsert` parameter is `true`, we force a removal and reinsertion of the node
259 * (this can be useful if the shape AABB has become much smaller than the previous one for instance).
260 *
261 * note that you should call this method if body's AABB was modified, even if the body wasn't moved.
262 *
263 * if `forceReinsert` = `true` and both `dispX` and `dispY` are zeroes, convert object to "static" (don't extrude AABB).
264 *
265 * return `true` if the tree was modified.
266 *)
267 function updateObject (nodeId: Integer; dispX, dispY: Float; forceReinsert: Boolean=false): Boolean;
269 function aabbQuery (ax, ay, aw, ah: Float; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh;
271 function segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: Float; cb: TSegQueryCallback): Boolean;
278 {$IFDEF aabbtree_query_count}
281 {$ELSE}
284 {$ENDIF}
288 implementation
290 uses
291 SysUtils;
294 // ////////////////////////////////////////////////////////////////////////// //
295 function minI (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
296 function maxI (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
298 function minF (a, b: Float): Float; inline; begin if (a < b) then result := a else result := b; end;
299 function maxF (a, b: Float): Float; inline; begin if (a > b) then result := a else result := b; end;
302 // ////////////////////////////////////////////////////////////////////////// //
303 constructor Ray2D.Create (ax, ay: Single; aangle: Single); begin setXYAngle(ax, ay, aangle); end;
304 constructor Ray2D.Create (ax0, ay0, ax1, ay1: Single); begin setX0Y0X1Y1(ax0, ay0, ax1, ay1); end;
309 begin
317 var
319 begin
326 begin
334 begin
343 // ////////////////////////////////////////////////////////////////////////// //
345 begin
350 begin
355 begin
359 function AABB2D.getvalid (): Boolean; inline; begin result := (minX < maxX) and (minY < maxY); end;
361 {$IFDEF aabbtree_use_floats}
364 {$ELSE}
367 {$ENDIF}
372 begin
377 {$IF DEFINED(D2F_DEBUG)}
379 {$ENDIF}
384 begin
389 {$IF DEFINED(D2F_DEBUG)}
391 {$ENDIF}
396 begin
397 {$IF DEFINED(D2F_DEBUG)}
400 {$ENDIF}
405 {$IF DEFINED(D2F_DEBUG)}
407 {$ENDIF}
412 begin
418 begin
419 {$IF DEFINED(D2F_DEBUG)}
421 {$ENDIF}
426 {$IF DEFINED(D2F_DEBUG)}
428 {$ENDIF}
433 begin
434 result :=
441 begin
447 begin
449 // exit with no intersection if found separated along any axis
456 // something to consider here is that 0 * inf =nan which occurs when the ray starts exactly on the edge of a box
457 // https://tavianator.com/fast-branchless-raybounding-box-intersections-part-2-nans/
458 function AABB2D.intersects (const ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload;
459 var
462 begin
463 // ok with coplanars
466 // do X
468 begin
475 // do Y
477 begin
481 // tmin
485 // tmax
492 begin
496 end
497 else
498 begin
504 var
507 begin
509 // it may be faster to first check if start or end point is inside AABB (this is sometimes enough for dyntree)
512 // nope, do it hard way
522 // ////////////////////////////////////////////////////////////////////////// //
523 procedure TDynAABBTree.TSegmentQueryResult.reset (); inline; begin dist := -1; flesh := nil; end;
524 function TDynAABBTree.TSegmentQueryResult.valid (): Boolean; inline; begin result := (dist >= 0) and (flesh <> nil); end;
527 // ////////////////////////////////////////////////////////////////////////// //
532 begin
546 // ////////////////////////////////////////////////////////////////////////// //
547 // allocate and return a node to use in the tree
549 var
552 begin
553 // if there is no more allocated node to use
555 begin
557 // allocate more nodes in the tree
561 // initialize the allocated nodes
563 begin
570 // get the next free node
572 {$IFDEF aabbtree_many_asserts}assert((freeNodeId >= mNodeCount) and (freeNodeId < mAllocCount));{$ENDIF}
583 // release a node
585 begin
597 // insert a leaf node in the tree
598 // 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
600 var
607 begin
608 // if the tree is empty
610 begin
613 exit;
618 // find the best sibling node for the new node
622 begin
626 // compute the merged AABB
631 // compute the cost of making the current node the sibling of the new node
634 // compute the minimum cost of pushing the new node further down the tree (inheritance cost)
637 // compute the cost of descending into the left child
642 // compute the cost of descending into the right child
647 // 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
650 // it is cheaper to go down into a child of the current node, choose the best child
651 //currentNodeId = (costLeft < costRight ? leftChild : rightChild);
657 // create a new parent for the new node and the sibling node
665 // if the sibling node was not the root node
667 begin
670 begin
672 end
673 else
674 begin
681 end
682 else
683 begin
684 // if the sibling node was the root node
692 // move up in the tree to change the AABBs that have changed
696 begin
697 // balance the sub-tree of the current node if it is not balanced
707 // recompute the height of the node in the tree
711 // recompute the AABB of the node
721 // remove a leaf node from the tree
723 var
726 begin
730 // if we are removing the root node (root node is a leaf in this case)
737 begin
739 end
740 else
741 begin
745 // if the parent of the node to remove is not the root node
747 begin
748 // destroy the parent node
750 begin
752 end
753 else
754 begin
755 {$IFDEF aabbtree_many_asserts}assert(mNodes[grandParentNodeId].children[TTreeNode.Right] = parentNodeId);{$ENDIF}
761 // 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
764 begin
765 // balance the current sub-tree if necessary
770 // get the two children of the current node
774 // recompute the AABB and the height of the current node
776 mNodes[currentNodeId].height := maxI(mNodes[leftChildId].height, mNodes[rightChildId].height)+1;
781 end
782 else
783 begin
784 // if the parent of the node to remove is the root node, the sibling node becomes the new root node
792 // balance the sub-tree of a given node using left or right rotations
793 // the rotation schemes are described in the book "Introduction to Game Physics with Box2D" by Ian Parberry
794 // this method returns the new root node id
796 var
800 begin
805 // if the node is a leaf or the height of A's sub-tree is less than 2
806 if (nodeA.leaf) or (nodeA.height < 2) then begin result := nodeId; exit; end; // do not perform any rotation
808 // get the two children nodes
816 // compute the factor of the left and right sub-trees
819 // if the right node C is 2 higher than left node B
821 begin
836 begin
838 begin
840 end
841 else
842 begin
843 {$IFDEF aabbtree_many_asserts}assert(mNodes[nodeC.parentId].children[TTreeNode.Right] = nodeId);{$ENDIF}
846 end
847 else
848 begin
855 // if the right node C was higher than left node B because of the F node
857 begin
862 // recompute the AABB of node A and C
866 // recompute the height of node A and C
871 end
872 else
873 begin
874 // if the right node C was higher than left node B because of node G
879 // recompute the AABB of node A and C
883 // recompute the height of node A and C
890 // return the new root of the sub-tree
892 exit;
895 // if the left node B is 2 higher than right node C
897 begin
912 begin
914 begin
916 end
917 else
918 begin
919 {$IFDEF aabbtree_many_asserts}assert(mNodes[nodeB.parentId].children[TTreeNode.Right] = nodeId);{$ENDIF}
922 end
923 else
924 begin
931 // if the left node B was higher than right node C because of the F node
933 begin
938 // recompute the AABB of node A and B
942 // recompute the height of node A and B
947 end
948 else
949 begin
950 // if the left node B was higher than right node C because of node G
955 // recompute the AABB of node A and B
959 // recompute the height of node A and B
966 // return the new root of the sub-tree
968 exit;
971 // if the sub-tree is balanced, return the current root node
976 // compute the height of a given node in the tree
978 var
981 begin
985 // if the node is a leaf, its height is zero
988 // compute the height of the left and right sub-tree
992 // return the height of the node
997 // internally add an object into the tree
999 var
1001 begin
1002 // get the next available node (or allocate new ones if necessary)
1005 // create the fat aabb to use in the tree
1008 begin
1015 // set the height of the node in the tree
1018 // insert the new leaf node in the tree
1024 // return the id of the node
1029 // initialize the tree
1031 var
1033 begin
1039 //memset(mNodes, 0, mAllocCount*TTreeNode.sizeof);
1042 // initialize the allocated nodes
1044 begin
1053 // also, checks if the tree structure is valid (for debugging purpose)
1056 var
1060 begin
1063 // if it is the root
1065 // get the children nodes
1069 begin
1070 {$IFDEF aabbtree_use_floats}
1071 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);
1072 {$ELSE}
1073 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);
1074 {$ENDIF}
1076 begin
1078 {$IFDEF aabbtree_use_floats}
1079 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);
1080 {$ELSE}
1081 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);
1082 {$ENDIF}
1087 // if the current node is a leaf
1089 begin
1092 end
1093 else
1094 begin
1097 // check that the children node Ids are valid
1100 // check that the children nodes have the correct parent node
1103 // check the height of node
1106 // check the AABB of the node
1112 // recursively check the children nodes
1118 begin
1119 // recursively check each node
1124 // return `true` from visitor to stop immediately
1125 // checker should check if this node should be considered to further checking
1126 // returns tree node if visitor says stop or -1
1127 function TDynAABBTree.visit (checker: TVisitCheckerCB; visitor: TQueryOverlapCB; tagmask: Integer=-1): Integer;
1128 var
1134 var
1136 begin
1138 begin
1139 // use "small stack"
1142 end
1143 else
1144 begin
1145 // use "big stack"
1148 begin
1149 // reuse
1151 end
1152 else
1153 begin
1154 // grow
1162 (*
1163 function spop (): Integer; inline;
1164 begin
1165 {$IFDEF aabbtree_many_asserts}assert(sp > 0);{$ENDIF}
1166 if (sp <= length(stack)) then
1167 begin
1168 // use "small stack"
1169 Dec(sp);
1170 result := stack[sp];
1171 end
1172 else
1173 begin
1174 // use "big stack"
1175 Dec(sp);
1176 result := bigstack[sp-length(stack)];
1177 end;
1178 end;
1179 *)
1181 var
1184 begin
1186 //if not assigned(visitor) then begin result := -1; exit; end;
1187 try
1188 {$IFDEF aabbtree_query_count}
1191 {$ENDIF}
1193 // start from root node
1196 // while there are still nodes to visit
1198 begin
1199 // get the next node id to visit
1200 //nodeId := spop();
1203 begin
1204 // use "small stack"
1207 end
1208 else
1209 begin
1210 // use "big stack"
1215 // skip it if it is a nil node
1218 // get the corresponding node
1220 // should we investigate this node?
1222 begin
1223 // if the node is a leaf
1225 begin
1226 // call visitor on it
1229 begin
1232 end
1233 else
1234 begin
1235 // if the node is not a leaf, we need to visit its children
1243 finally
1249 // add `extraAABBGap` to bounding boxes so slight object movement won't cause tree rebuilds
1250 // 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
1252 begin
1259 begin
1265 // clear all the nodes and reset the tree
1267 begin
1273 function TDynAABBTree.computeTreeHeight (): Integer; begin result := computeHeight(mRootNodeId); end;
1276 // return the root AABB of the tree
1278 begin
1279 {$IFDEF aabbtree_many_asserts}assert((mRootNodeId >= 0) and (mRootNodeId < mNodeCount));{$ENDIF}
1284 // does the given id represents a valid object?
1285 // WARNING: ids of removed objects can be reused on later insertions!
1287 begin
1292 // get object by nodeid; can return nil for invalid ids
1294 begin
1295 if (nodeid >= 0) and (nodeid < mNodeCount) and (mNodes[nodeid].leaf) then result := mNodes[nodeid].flesh else result := nil;
1298 // get fat object AABB by nodeid; returns random shit for invalid ids
1300 begin
1301 if (nodeid >= 0) and (nodeid < mNodeCount) and (not mNodes[nodeid].isfree) then aabb.copyFrom(mNodes[nodeid].aabb) else aabb.setDims(0, 0, 0, 0);
1305 // insert an object into the tree
1306 // this method creates a new leaf node in the tree and returns the id of the corresponding node or -1 on error
1307 // AABB for static object will not be "fat" (simple optimization)
1308 // WARNING! inserting the same object several times *WILL* break everything!
1309 function TDynAABBTree.insertObject (flesh: TTreeFlesh; tag: Integer; staticObject: Boolean=false): Integer;
1310 var
1313 begin
1315 begin
1316 {$IFDEF aabbtree_use_floats}
1317 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);
1318 {$ELSE}
1319 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);
1320 {$ENDIF}
1321 //raise Exception.Create('trying to insert invalid flesh in dyntree');
1323 exit;
1326 begin
1327 {$IFDEF aabbtree_use_floats}
1328 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);
1329 {$ELSE}
1330 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);
1331 {$ENDIF}
1334 exit;
1336 //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);
1345 // remove an object from the tree
1346 // WARNING: ids of removed objects can be reused on later insertions!
1348 begin
1349 if (nodeId < 0) or (nodeId >= mNodeCount) or (not mNodes[nodeId].leaf) then raise Exception.Create('invalid node id in TDynAABBTree');
1350 // remove the node from the tree
1356 function TDynAABBTree.updateObject (nodeId: Integer; dispX, dispY: Float; forceReinsert: Boolean=false): Boolean;
1357 var
1359 begin
1360 if (nodeId < 0) or (nodeId >= mNodeCount) or (not mNodes[nodeId].leaf) then raise Exception.Create('invalid node id in TDynAABBTree.updateObject');
1362 if not getFleshAABB(newAABB, mNodes[nodeId].flesh) then raise Exception.Create('invalid node id in TDynAABBTree.updateObject');
1363 if not newAABB.valid then raise Exception.Create('invalid flesh aabb in TDynAABBTree.updateObject');
1365 // if the new AABB is still inside the fat AABB of the node
1366 if (not forceReinsert) and (mNodes[nodeId].aabb.contains(newAABB)) then begin result := false; exit; end;
1368 // if the new AABB is outside the fat AABB, we remove the corresponding node
1371 // compute the fat AABB by inflating the AABB with a constant gap
1374 begin
1381 // inflate the fat AABB in direction of the linear motion of the AABB
1383 begin
1384 mNodes[nodeId].aabb.minX := mNodes[nodeId].aabb.minX+LinearMotionGapMultiplier*dispX {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1385 end
1386 else
1387 begin
1388 mNodes[nodeId].aabb.maxX := mNodes[nodeId].aabb.maxX+LinearMotionGapMultiplier*dispX {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1391 begin
1392 mNodes[nodeId].aabb.minY := mNodes[nodeId].aabb.minY+LinearMotionGapMultiplier*dispY {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1393 end
1394 else
1395 begin
1396 mNodes[nodeId].aabb.maxY := mNodes[nodeId].aabb.maxY+LinearMotionGapMultiplier*dispY {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1401 // reinsert the node into the tree
1408 // report all shapes overlapping with the AABB given in parameter
1409 function TDynAABBTree.aabbQuery (ax, ay, aw, ah: Float; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh;
1410 var
1413 begin
1416 var
1418 begin
1428 // report body that contains the given point, or nil
1431 begin
1434 var
1436 begin
1438 {$IFDEF aabbtree_many_asserts}assert((nid < 0) or ((nid >= 0) and (nid < mNodeCount) and (mNodes[nid].leaf)));{$ENDIF}
1443 // segment querying method
1444 function TDynAABBTree.segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: Float; cb: TSegQueryCallback): Boolean;
1445 var
1453 begin
1458 var
1460 begin
1462 // if the user returned a hitFraction of zero, it means that the raycasting should stop here
1464 begin
1468 exit;
1470 // if the user returned a positive fraction
1472 begin
1473 // we update the maxFraction value and the ray AABB using the new maximum fraction
1475 begin
1479 // fix curb here
1480 //curb := cura+dir*hitFraction;
1488 begin
1500 // normalize