fcb8f6801d20ea037a5e906b40cc2dcc9cb28c07
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
34 // ////////////////////////////////////////////////////////////////////////// //
35 type
37 public
41 public
54 // ////////////////////////////////////////////////////////////////////////// //
55 type
57 public
60 private
67 public
81 // return true if the current AABB contains the AABB given in parameter
85 // return true if the current AABB is overlapping with the AABB in parameter
86 // two AABBs overlap if they overlap in the two axes at the same time
89 // ray direction must be normalized
90 function intersects (const ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload;
101 // ////////////////////////////////////////////////////////////////////////// //
102 (* Dynamic AABB tree (bounding volume hierarchy)
103 * based on the code from ReactPhysics3D physics library, http://www.reactphysics3d.com
104 * Copyright (c) 2010-2016 Daniel Chappuis
105 *
106 * This software is provided 'as-is', without any express or implied warranty.
107 * In no event will the authors be held liable for any damages arising from the
108 * use of this software.
109 *
110 * Permission is granted to anyone to use this software for any purpose,
111 * including commercial applications, and to alter it and redistribute it
112 * freely, subject to the following restrictions:
113 *
114 * 1. The origin of this software must not be misrepresented; you must not claim
115 * that you wrote the original software. If you use this software in a
116 * product, an acknowledgment in the product documentation would be
117 * appreciated but is not required.
118 *
119 * 2. Altered source versions must be plainly marked as such, and must not be
120 * misrepresented as being the original software.
121 *
122 * 3. This notice may not be removed or altered from any source distribution.
123 *)
124 // ////////////////////////////////////////////////////////////////////////// //
125 (*
126 * This class implements a dynamic AABB tree that is used for broad-phase
127 * collision detection. This data structure is inspired by Nathanael Presson's
128 * dynamic tree implementation in BulletPhysics. The following implementation is
129 * based on the one from Erin Catto in Box2D as described in the book
130 * "Introduction to Game Physics with Box2D" by Ian Parberry.
131 *)
132 // ////////////////////////////////////////////////////////////////////////// //
133 // Dynamic AABB Tree: can be used to speed up broad phase in various engines
134 type
136 private
137 type
140 public
144 public
145 // a node is either in the tree (has a parent) or in the free nodes list (has a next node)
147 //nextNodeId: Integer;
148 // a node is either a leaf (has data) or is an internal node (has children)
149 children: array [0..1] of Integer; // left and right child of the node (children[0] = left child)
150 //TODO: `flesh` can be united with `children`
152 // height of the node in the tree (-1 for free nodes)
154 // fat axis aligned bounding box (AABB) corresponding to the node
157 public
158 // return true if the node is a leaf of the tree
163 //property flesh: Integer read children[0] write children[0];
167 //TVisitVisitorCB = function (abody: TTreeFlesh; atag: Integer): Boolean is nested;
169 public
170 // return `true` to stop
171 type TForEachLeafCB = function (abody: TTreeFlesh; const aabb: AABB2D): Boolean is nested; // WARNING! don't modify AABB here!
173 public
174 // in the broad-phase collision detection (dynamic AABB tree), the AABBs are
175 // also inflated in direction of the linear motion of the body by mutliplying the
176 // followin constant with the linear velocity and the elapsed time between two frames
177 {$IFDEF aabbtree_use_floats}
179 {$ELSE}
181 {$ENDIF}
183 private
186 mFreeNodeId: Integer; // id of the first node of the list of free (allocated) nodes in the tree that we can use
190 // extra AABB Gap used to allow the collision shape to move a little bit
191 // without triggering a large modification of the tree which can be costly
194 public
195 // called when a overlapping node has been found during the call to forEachAABBOverlap()
196 // return `true` to stop
198 type TSegQueryCallback = function (abody: TTreeFlesh; ax, ay, bx, by: Single): Single is nested; // return dist from (ax,ay) to abody
208 private
217 function visit (var caabb: AABB2D; mode: Integer; checker: TVisitCheckerCB; visitor: TQueryOverlapCB; tagmask: Integer=-1): Integer;
219 public
220 {$IFDEF aabbtree_query_count}
222 {$ENDIF}
224 public
228 // clear all the nodes and reset the tree
238 // return `false` for invalid flesh
241 // insert an object into the tree
242 // this method creates a new leaf node in the tree and returns the id of the corresponding node or -1 on error
243 // AABB for static object will not be "fat" (simple optimization)
244 // WARNING! inserting the same object several times *WILL* break everything!
247 // remove an object from the tree
248 // WARNING: ids of removed objects can be reused on later insertions!
251 (** update the dynamic tree after an object has moved.
252 *
253 * if the new AABB of the object that has moved is still inside its fat AABB, then nothing is done.
254 * otherwise, the corresponding node is removed and reinserted into the tree.
255 * the method returns true if the object has been reinserted into the tree.
256 * the `dispX` and `dispY` parameters are the linear velocity of the AABB multiplied by the elapsed time between two frames.
257 * if the `forceReinsert` parameter is `true`, we force a removal and reinsertion of the node
258 * (this can be useful if the shape AABB has become much smaller than the previous one for instance).
259 *
260 * note that you should call this method if body's AABB was modified, even if the body wasn't moved.
261 *
262 * if `forceReinsert` = `true` and both `dispX` and `dispY` are zeroes, convert object to "static" (don't extrude AABB).
263 *
264 * return `true` if the tree was modified.
265 *)
266 function updateObject (nodeId: Integer; dispX, dispY: TreeNumber; forceReinsert: Boolean=false): Boolean;
268 function aabbQuery (ax, ay, aw, ah: TreeNumber; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh;
270 function segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: TreeNumber; cb: TSegQueryCallback): Boolean;
277 {$IFDEF aabbtree_query_count}
280 {$ELSE}
283 {$ENDIF}
287 implementation
289 uses
290 SysUtils;
293 // ////////////////////////////////////////////////////////////////////////// //
294 function minI (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end;
295 function maxI (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end;
297 function minF (a, b: TreeNumber): TreeNumber; inline; begin if (a < b) then result := a else result := b; end;
298 function maxF (a, b: TreeNumber): TreeNumber; inline; begin if (a > b) then result := a else result := b; end;
301 // ////////////////////////////////////////////////////////////////////////// //
302 constructor Ray2D.Create (ax, ay: Single; aangle: Single); begin setXYAngle(ax, ay, aangle); end;
303 constructor Ray2D.Create (ax0, ay0, ax1, ay1: Single); begin setX0Y0X1Y1(ax0, ay0, ax1, ay1); end;
308 begin
316 var
318 begin
325 begin
333 begin
342 // ////////////////////////////////////////////////////////////////////////// //
344 begin
349 begin
354 begin
358 function AABB2D.getvalid (): Boolean; inline; begin result := (minX < maxX) and (minY < maxY); end;
360 {$IFDEF aabbtree_use_floats}
363 {$ELSE}
366 {$ENDIF}
371 begin
376 {$IF DEFINED(D2F_DEBUG)}
378 {$ENDIF}
383 begin
388 {$IF DEFINED(D2F_DEBUG)}
390 {$ENDIF}
395 begin
396 {$IF DEFINED(D2F_DEBUG)}
399 {$ENDIF}
404 {$IF DEFINED(D2F_DEBUG)}
406 {$ENDIF}
411 begin
417 begin
418 {$IF DEFINED(D2F_DEBUG)}
420 {$ENDIF}
425 {$IF DEFINED(D2F_DEBUG)}
427 {$ENDIF}
432 begin
433 result :=
440 begin
446 begin
448 // exit with no intersection if found separated along any axis
455 // something to consider here is that 0 * inf =nan which occurs when the ray starts exactly on the edge of a box
456 // https://tavianator.com/fast-branchless-raybounding-box-intersections-part-2-nans/
457 function AABB2D.intersects (const ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload;
458 var
461 begin
462 // ok with coplanars
465 // do X
467 begin
474 // do Y
476 begin
480 // tmin
484 // tmax
491 begin
495 end
496 else
497 begin
503 var
506 begin
508 // it may be faster to first check if start or end point is inside AABB (this is sometimes enough for dyntree)
511 // nope, do it hard way
521 // ////////////////////////////////////////////////////////////////////////// //
522 procedure TDynAABBTree.TSegmentQueryResult.reset (); inline; begin dist := -1; flesh := nil; end;
523 function TDynAABBTree.TSegmentQueryResult.valid (): Boolean; inline; begin result := (dist >= 0) and (flesh <> nil); end;
526 // ////////////////////////////////////////////////////////////////////////// //
531 begin
545 // ////////////////////////////////////////////////////////////////////////// //
546 // allocate and return a node to use in the tree
548 var
551 begin
552 // if there is no more allocated node to use
554 begin
556 // allocate more nodes in the tree
560 // initialize the allocated nodes
562 begin
569 // get the next free node
571 {$IFDEF aabbtree_many_asserts}assert((freeNodeId >= mNodeCount) and (freeNodeId < mAllocCount));{$ENDIF}
582 // release a node
584 begin
596 // insert a leaf node in the tree
597 // 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
599 var
606 begin
607 // if the tree is empty
609 begin
612 exit;
617 // find the best sibling node for the new node
621 begin
625 // compute the merged AABB
630 // compute the cost of making the current node the sibling of the new node
633 // compute the minimum cost of pushing the new node further down the tree (inheritance cost)
636 // compute the cost of descending into the left child
641 // compute the cost of descending into the right child
646 // 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
649 // it is cheaper to go down into a child of the current node, choose the best child
650 //currentNodeId = (costLeft < costRight ? leftChild : rightChild);
656 // create a new parent for the new node and the sibling node
664 // if the sibling node was not the root node
666 begin
669 begin
671 end
672 else
673 begin
680 end
681 else
682 begin
683 // if the sibling node was the root node
691 // move up in the tree to change the AABBs that have changed
695 begin
696 // balance the sub-tree of the current node if it is not balanced
706 // recompute the height of the node in the tree
710 // recompute the AABB of the node
720 // remove a leaf node from the tree
722 var
725 begin
729 // if we are removing the root node (root node is a leaf in this case)
736 begin
738 end
739 else
740 begin
744 // if the parent of the node to remove is not the root node
746 begin
747 // destroy the parent node
749 begin
751 end
752 else
753 begin
754 {$IFDEF aabbtree_many_asserts}assert(mNodes[grandParentNodeId].children[TTreeNode.Right] = parentNodeId);{$ENDIF}
760 // 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
763 begin
764 // balance the current sub-tree if necessary
769 // get the two children of the current node
773 // recompute the AABB and the height of the current node
775 mNodes[currentNodeId].height := maxI(mNodes[leftChildId].height, mNodes[rightChildId].height)+1;
780 end
781 else
782 begin
783 // if the parent of the node to remove is the root node, the sibling node becomes the new root node
791 // balance the sub-tree of a given node using left or right rotations
792 // the rotation schemes are described in the book "Introduction to Game Physics with Box2D" by Ian Parberry
793 // this method returns the new root node id
795 var
799 begin
804 // if the node is a leaf or the height of A's sub-tree is less than 2
805 if (nodeA.leaf) or (nodeA.height < 2) then begin result := nodeId; exit; end; // do not perform any rotation
807 // get the two children nodes
815 // compute the factor of the left and right sub-trees
818 // if the right node C is 2 higher than left node B
820 begin
835 begin
837 begin
839 end
840 else
841 begin
842 {$IFDEF aabbtree_many_asserts}assert(mNodes[nodeC.parentId].children[TTreeNode.Right] = nodeId);{$ENDIF}
845 end
846 else
847 begin
854 // if the right node C was higher than left node B because of the F node
856 begin
861 // recompute the AABB of node A and C
865 // recompute the height of node A and C
870 end
871 else
872 begin
873 // if the right node C was higher than left node B because of node G
878 // recompute the AABB of node A and C
882 // recompute the height of node A and C
889 // return the new root of the sub-tree
891 exit;
894 // if the left node B is 2 higher than right node C
896 begin
911 begin
913 begin
915 end
916 else
917 begin
918 {$IFDEF aabbtree_many_asserts}assert(mNodes[nodeB.parentId].children[TTreeNode.Right] = nodeId);{$ENDIF}
921 end
922 else
923 begin
930 // if the left node B was higher than right node C because of the F node
932 begin
937 // recompute the AABB of node A and B
941 // recompute the height of node A and B
946 end
947 else
948 begin
949 // if the left node B was higher than right node C because of node G
954 // recompute the AABB of node A and B
958 // recompute the height of node A and B
965 // return the new root of the sub-tree
967 exit;
970 // if the sub-tree is balanced, return the current root node
975 // compute the height of a given node in the tree
977 var
980 begin
984 // if the node is a leaf, its height is zero
987 // compute the height of the left and right sub-tree
991 // return the height of the node
996 // internally add an object into the tree
998 var
1000 begin
1001 // get the next available node (or allocate new ones if necessary)
1004 // create the fat aabb to use in the tree
1007 begin
1014 // set the height of the node in the tree
1017 // insert the new leaf node in the tree
1023 // return the id of the node
1028 // initialize the tree
1030 var
1032 begin
1038 //memset(mNodes, 0, mAllocCount*TTreeNode.sizeof);
1041 // initialize the allocated nodes
1043 begin
1052 // also, checks if the tree structure is valid (for debugging purpose)
1055 var
1059 begin
1062 // if it is the root
1064 // get the children nodes
1068 begin
1069 {$IFDEF aabbtree_use_floats}
1070 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);
1071 {$ELSE}
1072 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);
1073 {$ENDIF}
1075 begin
1077 {$IFDEF aabbtree_use_floats}
1078 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);
1079 {$ELSE}
1080 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);
1081 {$ENDIF}
1086 // if the current node is a leaf
1088 begin
1091 end
1092 else
1093 begin
1096 // check that the children node Ids are valid
1099 // check that the children nodes have the correct parent node
1102 // check the height of node
1105 // check the AABB of the node
1111 // recursively check the children nodes
1117 begin
1118 // recursively check each node
1123 // return `true` from visitor to stop immediately
1124 // checker should check if this node should be considered to further checking
1125 // returns tree node if visitor says stop or -1
1129 function TDynAABBTree.visit (var caabb: AABB2D; mode: Integer; checker: TVisitCheckerCB; visitor: TQueryOverlapCB; tagmask: Integer=-1): Integer;
1130 var
1136 var
1138 begin
1140 begin
1141 // use "small stack"
1144 end
1145 else
1146 begin
1147 // use "big stack"
1150 begin
1151 // reuse
1153 end
1154 else
1155 begin
1156 // grow
1165 begin
1168 begin
1169 // use "small stack"
1172 end
1173 else
1174 begin
1175 // use "big stack"
1181 var
1185 begin
1187 //if not assigned(visitor) then begin result := -1; exit; end;
1188 try
1189 {$IFDEF aabbtree_query_count}
1192 {$ENDIF}
1194 // start from root node
1197 // while there are still nodes to visit
1199 begin
1200 // get the next node id to visit
1202 // skip it if it is a nil node
1205 // get the corresponding node
1207 // should we investigate this node?
1214 begin
1215 // if the node is a leaf
1217 begin
1218 // call visitor on it
1221 begin
1224 end
1225 else
1226 begin
1227 // if the node is not a leaf, we need to visit its children
1235 finally
1241 // add `extraAABBGap` to bounding boxes so slight object movement won't cause tree rebuilds
1242 // 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
1244 begin
1251 begin
1257 // clear all the nodes and reset the tree
1259 begin
1265 function TDynAABBTree.computeTreeHeight (): Integer; begin result := computeHeight(mRootNodeId); end;
1268 // return the root AABB of the tree
1270 begin
1271 {$IFDEF aabbtree_many_asserts}assert((mRootNodeId >= 0) and (mRootNodeId < mNodeCount));{$ENDIF}
1276 // does the given id represents a valid object?
1277 // WARNING: ids of removed objects can be reused on later insertions!
1279 begin
1284 // get object by nodeid; can return nil for invalid ids
1286 begin
1287 if (nodeid >= 0) and (nodeid < mNodeCount) and (mNodes[nodeid].leaf) then result := mNodes[nodeid].flesh else result := nil;
1290 // get fat object AABB by nodeid; returns random shit for invalid ids
1292 begin
1293 if (nodeid >= 0) and (nodeid < mNodeCount) and (not mNodes[nodeid].isfree) then aabb.copyFrom(mNodes[nodeid].aabb) else aabb.setDims(0, 0, 0, 0);
1297 // insert an object into the tree
1298 // this method creates a new leaf node in the tree and returns the id of the corresponding node or -1 on error
1299 // AABB for static object will not be "fat" (simple optimization)
1300 // WARNING! inserting the same object several times *WILL* break everything!
1301 function TDynAABBTree.insertObject (flesh: TTreeFlesh; tag: Integer; staticObject: Boolean=false): Integer;
1302 var
1305 begin
1307 begin
1308 {$IFDEF aabbtree_use_floats}
1309 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);
1310 {$ELSE}
1311 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);
1312 {$ENDIF}
1313 //raise Exception.Create('trying to insert invalid flesh in dyntree');
1315 exit;
1318 begin
1319 {$IFDEF aabbtree_use_floats}
1320 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);
1321 {$ELSE}
1322 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);
1323 {$ENDIF}
1326 exit;
1328 //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);
1337 // remove an object from the tree
1338 // WARNING: ids of removed objects can be reused on later insertions!
1340 begin
1341 if (nodeId < 0) or (nodeId >= mNodeCount) or (not mNodes[nodeId].leaf) then raise Exception.Create('invalid node id in TDynAABBTree');
1342 // remove the node from the tree
1348 function TDynAABBTree.updateObject (nodeId: Integer; dispX, dispY: TreeNumber; forceReinsert: Boolean=false): Boolean;
1349 var
1351 begin
1352 if (nodeId < 0) or (nodeId >= mNodeCount) or (not mNodes[nodeId].leaf) then raise Exception.Create('invalid node id in TDynAABBTree.updateObject');
1354 if not getFleshAABB(newAABB, mNodes[nodeId].flesh) then raise Exception.Create('invalid node id in TDynAABBTree.updateObject');
1355 if not newAABB.valid then raise Exception.Create('invalid flesh aabb in TDynAABBTree.updateObject');
1357 // if the new AABB is still inside the fat AABB of the node
1358 if (not forceReinsert) and (mNodes[nodeId].aabb.contains(newAABB)) then begin result := false; exit; end;
1360 // if the new AABB is outside the fat AABB, we remove the corresponding node
1363 // compute the fat AABB by inflating the AABB with a constant gap
1366 begin
1373 // inflate the fat AABB in direction of the linear motion of the AABB
1375 begin
1376 mNodes[nodeId].aabb.minX := mNodes[nodeId].aabb.minX+LinearMotionGapMultiplier*dispX {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1377 end
1378 else
1379 begin
1380 mNodes[nodeId].aabb.maxX := mNodes[nodeId].aabb.maxX+LinearMotionGapMultiplier*dispX {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1383 begin
1384 mNodes[nodeId].aabb.minY := mNodes[nodeId].aabb.minY+LinearMotionGapMultiplier*dispY {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1385 end
1386 else
1387 begin
1388 mNodes[nodeId].aabb.maxY := mNodes[nodeId].aabb.maxY+LinearMotionGapMultiplier*dispY {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
1393 // reinsert the node into the tree
1400 // report all shapes overlapping with the AABB given in parameter
1401 function TDynAABBTree.aabbQuery (ax, ay, aw, ah: TreeNumber; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh;
1402 var
1405 begin
1408 var
1410 begin
1420 // report body that contains the given point, or nil
1423 begin
1426 var
1429 begin
1432 {$IFDEF aabbtree_many_asserts}assert((nid < 0) or ((nid >= 0) and (nid < mNodeCount) and (mNodes[nid].leaf)));{$ENDIF}
1437 // segment querying method
1438 function TDynAABBTree.segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: TreeNumber; cb: TSegQueryCallback): Boolean;
1439 var
1448 begin
1453 var
1455 begin
1457 // if the user returned a hitFraction of zero, it means that the raycasting should stop here
1459 begin
1463 exit;
1465 // if the user returned a positive fraction
1467 begin
1468 // we update the maxFraction value and the ray AABB using the new maximum fraction
1470 begin
1474 // fix curb here
1475 //curb := cura+dir*hitFraction;
1483 begin
1495 // normalize