index 8260d9e82aea1122836db9da2e21624f4c312909..5ebc8851c5a087810ba212172b6c5cfbe9e44afb 100644 (file)
--- a/src/game/z_aabbtree.pas
+++ b/src/game/z_aabbtree.pas
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*)
{$INCLUDE ../shared/a_modes.inc}
-{$DEFINE aabbtree_many_asserts}
+{.$DEFINE aabbtree_many_asserts}
{$DEFINE aabbtree_query_count}
+{.$DEFINE aabbtree_use_floats}
unit z_aabbtree;
interface
// ////////////////////////////////////////////////////////////////////////// //
type
- Float = Single;
- PFloat = ^Float;
+ {$IFDEF aabbtree_use_floats}Float = Single;{$ELSE}Float = Integer;{$ENDIF}
+ //PFloat = ^Float;
TTreeFlesh = TObject;
type
Ray2D = record
public
- origX, origY: Float;
- dirX, dirY: Float;
+ origX, origY: Single;
+ dirX, dirY: Single;
public
- constructor Create (ax, ay: Float; aangle: Float); overload;
- constructor Create (ax0, ay0, ax1, ay1: Float); overload;
+ constructor Create (ax, ay: Single; aangle: Single); overload;
+ constructor Create (ax0, ay0, ax1, ay1: Single); overload;
constructor Create (const aray: Ray2D); overload;
procedure copyFrom (const aray: Ray2D); inline;
procedure normalizeDir (); inline;
- procedure setXYAngle (ax, ay: Float; aangle: Float); inline;
- procedure setX0Y0X1Y1 (ax0, ay0, ax1, ay1: Float); inline;
+ procedure setXYAngle (ax, ay: Single; aangle: Single); inline;
+ procedure setX0Y0X1Y1 (ax0, ay0, ax1, ay1: Single); inline;
end;
// ////////////////////////////////////////////////////////////////////////// //
function overlaps (const aabb: AABB2D): Boolean; inline; overload;
// ray direction must be normalized
- function intersects (const ray: Ray2D; tmino: PFloat=nil; tmaxo: PFloat=nil): Boolean; overload;
- function intersects (ax, ay, bx, by: Float): Boolean; inline; overload;
+ function intersects (const ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload;
+ function intersects (ax, ay, bx, by: Single): Boolean; inline; overload;
property valid: Boolean read getvalid;
property centerX: Float read getcenterX;
height: SmallInt;
// fat axis aligned bounding box (AABB) corresponding to the node
aabb: AABB2D;
+ tag: Integer; // just a user-defined tag
public
// return true if the node is a leaf of the tree
procedure clear (); inline;
function leaf (): Boolean; inline;
- function free (): Boolean; inline;
+ function isfree (): Boolean; inline;
property nextNodeId: Integer read parentId write parentId;
//property flesh: Integer read children[0] write children[0];
end;
TVisitCheckerCB = function (node: PTreeNode): Boolean is nested;
- TVisitVisitorCB = function (abody: TTreeFlesh): Boolean is nested;
+ //TVisitVisitorCB = function (abody: TTreeFlesh; atag: Integer): Boolean is nested;
public
// return `true` to stop
// in the broad-phase collision detection (dynamic AABB tree), the AABBs are
// also inflated in direction of the linear motion of the body by mutliplying the
// followin constant with the linear velocity and the elapsed time between two frames
+ {$IFDEF aabbtree_use_floats}
const LinearMotionGapMultiplier = 1.7;
+ {$ELSE}
+ const LinearMotionGapMultiplier = 17; // *10
+ {$ENDIF}
private
mNodes: array of TTreeNode; // nodes of the tree
// without triggering a large modification of the tree which can be costly
mExtraGap: Float;
+ public
+ // called when a overlapping node has been found during the call to forEachAABBOverlap()
+ // return `true` to stop
+ type TQueryOverlapCB = function (abody: TTreeFlesh; atag: Integer): Boolean is nested;
+ type TSegQueryCallback = function (abody: TTreeFlesh; ax, ay, bx, by: Single): Single is nested; // return dist from (ax,ay) to abody
+
+ TSegmentQueryResult = record
+ dist: Single; // <0: nothing was hit
+ flesh: TTreeFlesh;
+
+ procedure reset (); inline;
+ function valid (): Boolean; inline;
+ end;
+
private
function allocateNode (): Integer;
procedure releaseNode (nodeId: Integer);
function computeHeight (nodeId: Integer): Integer;
function insertObjectInternal (var aabb: AABB2D; staticObject: Boolean): Integer;
procedure setup ();
- function visit (checker: TVisitCheckerCB; visitor: TVisitVisitorCB): Integer;
+ function visit (checker: TVisitCheckerCB; visitor: TQueryOverlapCB; tagmask: Integer=-1): Integer;
public
{$IFDEF aabbtree_query_count}
- nodesVisited, nodesDeepVisited: Integer;
+ mNodesVisited, mNodesDeepVisited: Integer;
{$ENDIF}
public
- // called when a overlapping node has been found during the call to forEachAABBOverlap()
- // return `true` to stop
- type TQueryOverlapCB = function (abody: TTreeFlesh): Boolean is nested;
- type TSegQueryCallback = function (abody: TTreeFlesh; ax, ay, bx, by: Float): Float is nested; // return dist from (ax,ay) to abody
-
- TSegmentQueryResult = record
- dist: Float; // <0: nothing was hit
- flesh: TTreeFlesh;
-
- procedure reset (); inline;
- function valid (): Boolean; inline;
- end;
-
- public
- constructor Create (extraAABBGap: Float=0.0);
+ constructor Create (extraAABBGap: Float=0);
destructor Destroy (); override;
// clear all the nodes and reset the tree
// this method creates a new leaf node in the tree and returns the id of the corresponding node or -1 on error
// AABB for static object will not be "fat" (simple optimization)
// WARNING! inserting the same object several times *WILL* break everything!
- function insertObject (flesh: TTreeFlesh; staticObject: Boolean=false): Integer;
+ function insertObject (flesh: TTreeFlesh; tag: Integer; staticObject: Boolean=false): Integer;
// remove an object from the tree
// WARNING: ids of removed objects can be reused on later insertions!
*)
function updateObject (nodeId: Integer; dispX, dispY: Float; forceReinsert: Boolean=false): Boolean;
- procedure aabbQuery (ax, ay, aw, ah: Float; cb: TQueryOverlapCB);
+ function aabbQuery (ax, ay, aw, ah: Float; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh;
function pointQuery (ax, ay: Float; cb: TQueryOverlapCB): TTreeFlesh;
function segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: Float; cb: TSegQueryCallback): Boolean;
property extraGap: Float read mExtraGap write mExtraGap;
property nodeCount: Integer read mNodeCount;
property nodeAlloced: Integer read mAllocCount;
+ {$IFDEF aabbtree_query_count}
+ property nodesVisited: Integer read mNodesVisited;
+ property nodesDeepVisited: Integer read mNodesDeepVisited;
+ {$ELSE}
+ const nodesVisited = 0;
+ const nodesDeepVisited = 0;
+ {$ENDIF}
end;
@@ -287,8 +300,8 @@ function maxF (a, b: Float): Float; inline; begin if (a > b) then result := a el
// ////////////////////////////////////////////////////////////////////////// //
-constructor Ray2D.Create (ax, ay: Float; aangle: Float); begin setXYAngle(ax, ay, aangle); end;
-constructor Ray2D.Create (ax0, ay0, ax1, ay1: Float); begin setX0Y0X1Y1(ax0, ay0, ax1, ay1); end;
+constructor Ray2D.Create (ax, ay: Single; aangle: Single); begin setXYAngle(ax, ay, aangle); end;
+constructor Ray2D.Create (ax0, ay0, ax1, ay1: Single); begin setX0Y0X1Y1(ax0, ay0, ax1, ay1); end;
constructor Ray2D.Create (const aray: Ray2D); overload; begin copyFrom(aray); end;
procedure Ray2D.normalizeDir (); inline;
var
- invlen: Float;
+ invlen: Single;
begin
invlen := 1.0/sqrt(dirX*dirX+dirY*dirY);
dirX *= invlen;
dirY *= invlen;
end;
-procedure Ray2D.setXYAngle (ax, ay: Float; aangle: Float); inline;
+procedure Ray2D.setXYAngle (ax, ay: Single; aangle: Single); inline;
begin
origX := ax;
origY := ay;
dirY := sin(aangle);
end;
-procedure Ray2D.setX0Y0X1Y1 (ax0, ay0, ax1, ay1: Float); inline;
+procedure Ray2D.setX0Y0X1Y1 (ax0, ay0, ax1, ay1: Single); inline;
begin
origX := ax0;
origY := ay0;
function AABB2D.getvalid (): Boolean; inline; begin result := (minX < maxX) and (minY < maxY); end;
-function AABB2D.getcenterX (): Float; inline; begin result := (minX+maxX)/2; end;
-function AABB2D.getcenterY (): Float; inline; begin result := (minY+maxY)/2; end;
-function AABB2D.getextentX (): Float; inline; begin result := (maxX-minX)+1; end;
-function AABB2D.getextentY (): Float; inline; begin result := (maxY-minY)+1; end;
-
+{$IFDEF aabbtree_use_floats}
+function AABB2D.getcenterX (): Float; inline; begin result := (minX+maxX)/2.0; end;
+function AABB2D.getcenterY (): Float; inline; begin result := (minY+maxY)/2.0; end;
+{$ELSE}
+function AABB2D.getcenterX (): Float; inline; begin result := (minX+maxX) div 2; end;
+function AABB2D.getcenterY (): Float; inline; begin result := (minY+maxY) div 2; end;
+{$ENDIF}
+function AABB2D.getextentX (): Float; inline; begin result := (maxX-minX); end;
+function AABB2D.getextentY (): Float; inline; begin result := (maxY-minY); end;
procedure AABB2D.copyFrom (const aabb: AABB2D); inline;
begin
minY := aabb.minY;
maxX := aabb.maxX;
maxY := aabb.maxY;
+ {$IF DEFINED(D2F_DEBUG)}
+ if not valid then raise Exception.Create('copyFrom: result is fucked');
+ {$ENDIF}
end;
minY := minF(y0, y1);
maxX := maxF(x0, x1);
maxY := maxF(y0, y1);
+ {$IF DEFINED(D2F_DEBUG)}
+ if not valid then raise Exception.Create('setDims: result is fucked');
+ {$ENDIF}
end;
procedure AABB2D.setMergeTwo (const aabb0, aabb1: AABB2D); inline;
begin
+ {$IF DEFINED(D2F_DEBUG)}
+ if not aabb0.valid then raise Exception.Create('setMergeTwo: aabb0 is fucked');
+ if not aabb1.valid then raise Exception.Create('setMergeTwo: aabb0 is fucked');
+ {$ENDIF}
minX := minF(aabb0.minX, aabb1.minX);
minY := minF(aabb0.minY, aabb1.minY);
maxX := maxF(aabb0.maxX, aabb1.maxX);
maxY := maxF(aabb0.maxY, aabb1.maxY);
+ {$IF DEFINED(D2F_DEBUG)}
+ if not valid then raise Exception.Create('setMergeTwo: result is fucked');
+ {$ENDIF}
end;
procedure AABB2D.merge (const aabb: AABB2D); inline;
begin
+ {$IF DEFINED(D2F_DEBUG)}
+ if not aabb.valid then raise Exception.Create('merge: aabb is fucked');
+ {$ENDIF}
minX := minF(minX, aabb.minX);
minY := minF(minY, aabb.minY);
maxX := maxF(maxX, aabb.maxX);
maxY := maxF(maxY, aabb.maxY);
+ {$IF DEFINED(D2F_DEBUG)}
+ if not valid then raise Exception.Create('setMergeTwo: result is fucked');
+ {$ENDIF}
end;
// something to consider here is that 0 * inf =nan which occurs when the ray starts exactly on the edge of a box
// https://tavianator.com/fast-branchless-raybounding-box-intersections-part-2-nans/
-function AABB2D.intersects (const ray: Ray2D; tmino: PFloat=nil; tmaxo: PFloat=nil): Boolean; overload;
+function AABB2D.intersects (const ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload;
var
- dinv, t1, t2, tmp: Float;
- tmin, tmax: Float;
+ dinv, t1, t2, tmp: Single;
+ tmin, tmax: Single;
begin
// ok with coplanars
tmin := -1.0e100;
end;
end;
-function AABB2D.intersects (ax, ay, bx, by: Float): Boolean; inline; overload;
+function AABB2D.intersects (ax, ay, bx, by: Single): Boolean; inline; overload;
var
- tmin: Float;
+ tmin: Single;
ray: Ray2D;
begin
result := true;
@@ -490,7 +526,7 @@ function TDynAABBTree.TSegmentQueryResult.valid (): Boolean; inline; begin resul
// ////////////////////////////////////////////////////////////////////////// //
function TDynAABBTree.TTreeNode.leaf (): Boolean; inline; begin result := (height = 0); end;
-function TDynAABBTree.TTreeNode.free (): Boolean; inline; begin result := (height = -1); end;
+function TDynAABBTree.TTreeNode.isfree (): Boolean; inline; begin result := (height = -1); end;
procedure TDynAABBTree.TTreeNode.clear (); inline;
begin
children[0] := 0;
children[1] := 0;
flesh := nil;
+ tag := 0;
height := 0;
- //aabb.setX0Y0X1Y1(0, 0, 0, 0);
aabb.minX := 0;
aabb.minY := 0;
- aabb.maxX := -1;
- aabb.maxY := -1;
+ aabb.maxX := 0;
+ aabb.maxY := 0;
end;
begin
{$IFDEF aabbtree_many_asserts}assert(mNodeCount = mAllocCount);{$ENDIF}
// allocate more nodes in the tree
- if (mAllocCount < 8192) then newsz := mAllocCount*2 else newsz := mAllocCount+8192;
+ if (mAllocCount < 32768) then newsz := mAllocCount*2 else newsz := mAllocCount+16384;
SetLength(mNodes, newsz);
mAllocCount := newsz;
// initialize the allocated nodes
- for i := mNodeCount to mAllocCount-2 do
+ for i := mNodeCount to mAllocCount-1 do
begin
mNodes[i].nextNodeId := i+1;
mNodes[i].height := -1;
end;
mNodes[mAllocCount-1].nextNodeId := TTreeNode.NullTreeNode;
- mNodes[mAllocCount-1].height := -1;
mFreeNodeId := mNodeCount;
end;
// get the next free node
{$IFDEF aabbtree_many_asserts}assert(mNodes[nodeId].height >= 0);{$ENDIF}
mNodes[nodeId].nextNodeId := mFreeNodeId;
mNodes[nodeId].height := -1;
+ mNodes[nodeId].flesh := nil;
mFreeNodeId := nodeId;
Dec(mNodeCount);
end;
{$IFDEF aabbtree_many_asserts}assert(mRootNodeId <> TTreeNode.NullTreeNode);{$ENDIF}
// find the best sibling node for the new node
- newNodeAABB := mNodes[nodeId].aabb;
+ newNodeAABB := AABB2D.Create(mNodes[nodeId].aabb);
currentNodeId := mRootNodeId;
while not mNodes[currentNodeId].leaf do
begin
mergedVolume := mergedAABBs.volume;
// compute the cost of making the current node the sibling of the new node
- costS := 2.0*mergedVolume;
+ costS := 2*mergedVolume;
// compute the minimum cost of pushing the new node further down the tree (inheritance cost)
- costI := 2.0*(mergedVolume-volumeAABB);
+ costI := 2*(mergedVolume-volumeAABB);
// compute the cost of descending into the left child
currentAndLeftAABB := AABB2D.Create(newNodeAABB, mNodes[leftChild].aabb);
costLeft := currentAndLeftAABB.volume+costI;
- if not mNodes[leftChild].leaf then costLeft := costLeft-mNodes[leftChild].aabb.volume;
+ if not mNodes[leftChild].leaf then costLeft -= mNodes[leftChild].aabb.volume;
// compute the cost of descending into the right child
currentAndRightAABB := AABB2D.Create(newNodeAABB, mNodes[rightChild].aabb);
costRight := currentAndRightAABB.volume+costI;
- if not mNodes[rightChild].leaf then costRight := costRight-mNodes[rightChild].aabb.volume;
+ if not mNodes[rightChild].leaf then costRight -= mNodes[rightChild].aabb.volume;
// 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
if (costS < costLeft) and (costS < costRight) then break;
balanceFactor := nodeC.height-nodeB.height;
// if the right node C is 2 higher than left node B
- if (balanceFactor > 1.0) then
+ if (balanceFactor > 1) then
begin
{$IFDEF aabbtree_many_asserts}assert(not nodeC.leaf);{$ENDIF}
nodeId := allocateNode();
// create the fat aabb to use in the tree
- mNodes[nodeId].aabb := aabb;
+ mNodes[nodeId].aabb := AABB2D.Create(aabb);
if (not staticObject) then
begin
mNodes[nodeId].aabb.minX -= mExtraGap;
for i := 0 to mAllocCount-1 do mNodes[i].clear();
// initialize the allocated nodes
- for i := 0 to mAllocCount-2 do
+ for i := 0 to mAllocCount-1 do
begin
mNodes[i].nextNodeId := i+1;
mNodes[i].height := -1;
end;
mNodes[mAllocCount-1].nextNodeId := TTreeNode.NullTreeNode;
- mNodes[mAllocCount-1].height := -1;
mFreeNodeId := 0;
end;
// get the children nodes
pNode := @mNodes[nodeId];
assert(pNode.height >= 0);
- e_WriteLog(Format('AABB:(%f,%f)-(%f,%f); volume=%f; valid=%d', [pNode.aabb.minX, pNode.aabb.minY, pNode.aabb.maxX, pNode.aabb.maxY, pNode.aabb.volume, Integer(pNode.aabb.valid)]), MSG_NOTIFY);
+ if (not pNode.aabb.valid) then
+ begin
+ {$IFDEF aabbtree_use_floats}
+ 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);
+ {$ELSE}
+ 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);
+ {$ENDIF}
+ if pNode.leaf then
+ begin
+ getFleshAABB(aabb, pNode.flesh);
+ {$IFDEF aabbtree_use_floats}
+ 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);
+ {$ELSE}
+ 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);
+ {$ENDIF}
+ end;
+ end;
assert(pNode.aabb.valid);
assert(pNode.aabb.volume > 0);
// if the current node is a leaf
// return `true` from visitor to stop immediately
// checker should check if this node should be considered to further checking
// returns tree node if visitor says stop or -1
-function TDynAABBTree.visit (checker: TVisitCheckerCB; visitor: TVisitVisitorCB): Integer;
+function TDynAABBTree.visit (checker: TVisitCheckerCB; visitor: TQueryOverlapCB; tagmask: Integer=-1): Integer;
var
stack: array [0..255] of Integer; // stack with the nodes to visit
bigstack: array of Integer = nil;
sp: Integer = 0;
- procedure spush (id: Integer);
+ procedure spush (id: Integer); inline;
var
xsp: Integer;
begin
end;
end;
- function spop (): Integer;
+ (*
+ function spop (): Integer; inline;
begin
- assert(sp > 0);
+ {$IFDEF aabbtree_many_asserts}assert(sp > 0);{$ENDIF}
if (sp <= length(stack)) then
begin
// use "small stack"
result := bigstack[sp-length(stack)];
end;
end;
+ *)
var
nodeId: Integer;
//if not assigned(visitor) then begin result := -1; exit; end;
try
{$IFDEF aabbtree_query_count}
- nodesVisited := 0;
- nodesDeepVisited := 0;
+ mNodesVisited := 0;
+ mNodesDeepVisited := 0;
{$ENDIF}
// start from root node
while (sp > 0) do
begin
// get the next node id to visit
- nodeId := spop();
+ //nodeId := spop();
+ {$IFDEF aabbtree_many_asserts}assert(sp > 0);{$ENDIF}
+ if (sp <= length(stack)) then
+ begin
+ // use "small stack"
+ Dec(sp);
+ nodeId := stack[sp];
+ end
+ else
+ begin
+ // use "big stack"
+ Dec(sp);
+ nodeId := bigstack[sp-length(stack)];
+ end;
+
// skip it if it is a nil node
if (nodeId = TTreeNode.NullTreeNode) then continue;
- {$IFDEF aabbtree_query_count}Inc(nodesVisited);{$ENDIF}
+ {$IFDEF aabbtree_query_count}Inc(mNodesVisited);{$ENDIF}
// get the corresponding node
node := @mNodes[nodeId];
// should we investigate this node?
if (node.leaf) then
begin
// call visitor on it
- {$IFDEF aabbtree_query_count}Inc(nodesDeepVisited);{$ENDIF}
- if assigned(visitor) then
+ {$IFDEF aabbtree_query_count}Inc(mNodesDeepVisited);{$ENDIF}
+ if ((node.tag and tagmask) <> 0) and assigned(visitor) then
begin
- if (visitor(node.flesh)) then begin result := nodeId; exit; end;
+ if (visitor(node.flesh, node.tag)) then begin result := nodeId; exit; end;
end;
end
else
// add `extraAABBGap` to bounding boxes so slight object movement won't cause tree rebuilds
// 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
-constructor TDynAABBTree.Create (extraAABBGap: Float=0.0);
+constructor TDynAABBTree.Create (extraAABBGap: Float=0);
begin
mExtraGap := extraAABBGap;
setup();
// get fat object AABB by nodeid; returns random shit for invalid ids
procedure TDynAABBTree.getNodeFatAABB (var aabb: AABB2D; nodeid: Integer);
begin
- if (nodeid >= 0) and (nodeid < mNodeCount) and (not mNodes[nodeid].free) then aabb.copyFrom(mNodes[nodeid].aabb) else aabb.setDims(0, 0, 0, 0);
+ if (nodeid >= 0) and (nodeid < mNodeCount) and (not mNodes[nodeid].isfree) then aabb.copyFrom(mNodes[nodeid].aabb) else aabb.setDims(0, 0, 0, 0);
end;
// this method creates a new leaf node in the tree and returns the id of the corresponding node or -1 on error
// AABB for static object will not be "fat" (simple optimization)
// WARNING! inserting the same object several times *WILL* break everything!
-function TDynAABBTree.insertObject (flesh: TTreeFlesh; staticObject: Boolean=false): Integer;
+function TDynAABBTree.insertObject (flesh: TTreeFlesh; tag: Integer; staticObject: Boolean=false): Integer;
var
aabb: AABB2D;
nodeId: Integer;
begin
if not getFleshAABB(aabb, flesh) then
begin
+ {$IFDEF aabbtree_use_floats}
+ 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);
+ {$ELSE}
+ 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);
+ {$ENDIF}
+ //raise Exception.Create('trying to insert invalid flesh in dyntree');
+ result := -1;
+ exit;
+ end;
+ if not aabb.valid then
+ begin
+ {$IFDEF aabbtree_use_floats}
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);
+ {$ELSE}
+ 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);
+ {$ENDIF}
+ raise Exception.Create('trying to insert invalid aabb in dyntree');
result := -1;
exit;
end;
- 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);
+ //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);
nodeId := insertObjectInternal(aabb, staticObject);
{$IFDEF aabbtree_many_asserts}assert(mNodes[nodeId].leaf);{$ENDIF}
mNodes[nodeId].flesh := flesh;
+ mNodes[nodeId].tag := tag;
result := nodeId;
end;
@@ -1273,9 +1357,10 @@ function TDynAABBTree.updateObject (nodeId: Integer; dispX, dispY: Float; forceR
var
newAABB: AABB2D;
begin
- if (nodeId < 0) or (nodeId >= mNodeCount) or (not mNodes[nodeId].leaf) then raise Exception.Create('invalid node id in TDynAABBTree');
+ if (nodeId < 0) or (nodeId >= mNodeCount) or (not mNodes[nodeId].leaf) then raise Exception.Create('invalid node id in TDynAABBTree.updateObject');
- if not getFleshAABB(newAABB, mNodes[nodeId].flesh) then raise Exception.Create('invalid node id in TDynAABBTree');
+ if not getFleshAABB(newAABB, mNodes[nodeId].flesh) then raise Exception.Create('invalid node id in TDynAABBTree.updateObject');
+ if not newAABB.valid then raise Exception.Create('invalid flesh aabb in TDynAABBTree.updateObject');
// if the new AABB is still inside the fat AABB of the node
if (not forceReinsert) and (mNodes[nodeId].aabb.contains(newAABB)) then begin result := false; exit; end;
// compute the fat AABB by inflating the AABB with a constant gap
mNodes[nodeId].aabb := newAABB;
- if not forceReinsert and ((dispX <> 0) or (dispY <> 0)) then
+ if (not forceReinsert) and ((dispX <> 0) or (dispY <> 0)) then
begin
mNodes[nodeId].aabb.minX := mNodes[nodeId].aabb.minX-mExtraGap;
mNodes[nodeId].aabb.minY := mNodes[nodeId].aabb.minY-mExtraGap;
end;
// inflate the fat AABB in direction of the linear motion of the AABB
- if (dispX < 0.0) then
+ if (dispX < 0) then
begin
- mNodes[nodeId].aabb.minX := mNodes[nodeId].aabb.minX+LinearMotionGapMultiplier*dispX;
+ mNodes[nodeId].aabb.minX := mNodes[nodeId].aabb.minX+LinearMotionGapMultiplier*dispX {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
end
else
begin
- mNodes[nodeId].aabb.maxX := mNodes[nodeId].aabb.maxX+LinearMotionGapMultiplier*dispX;
+ mNodes[nodeId].aabb.maxX := mNodes[nodeId].aabb.maxX+LinearMotionGapMultiplier*dispX {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
end;
- if (dispY < 0.0) then
+ if (dispY < 0) then
begin
- mNodes[nodeId].aabb.minY := mNodes[nodeId].aabb.minY+LinearMotionGapMultiplier*dispY;
+ mNodes[nodeId].aabb.minY := mNodes[nodeId].aabb.minY+LinearMotionGapMultiplier*dispY {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
end
else
begin
- mNodes[nodeId].aabb.maxY := mNodes[nodeId].aabb.maxY+LinearMotionGapMultiplier*dispY;
+ mNodes[nodeId].aabb.maxY := mNodes[nodeId].aabb.maxY+LinearMotionGapMultiplier*dispY {$IFDEF aabbtree_use_floats}{$ELSE}div 10{$ENDIF};
end;
{$IFDEF aabbtree_many_asserts}assert(mNodes[nodeId].aabb.contains(newAABB));{$ENDIF}
// report all shapes overlapping with the AABB given in parameter
-procedure TDynAABBTree.aabbQuery (ax, ay, aw, ah: Float; cb: TQueryOverlapCB);
+function TDynAABBTree.aabbQuery (ax, ay, aw, ah: Float; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh;
var
caabb: AABB2D;
function checker (node: PTreeNode): Boolean;
begin
result := caabb.overlaps(node.aabb);
end;
+var
+ nid: Integer;
begin
+ result := nil;
if not assigned(cb) then exit;
if (aw < 1) or (ah < 1) then exit;
- caabb := AABB2D.Create(ax, ay, ax+aw-1, ay+ah-1);
- visit(checker, cb);
+ caabb := AABB2D.Create(ax, ay, ax+aw, ay+ah);
+ nid := visit(checker, cb, tagmask);
+ if (nid >= 0) then result := mNodes[nid].flesh else result := nil;
end;
// report body that contains the given point, or nil
function TDynAABBTree.pointQuery (ax, ay: Float; cb: TQueryOverlapCB): TTreeFlesh;
-var
- nid: Integer;
function checker (node: PTreeNode): Boolean;
begin
result := node.aabb.contains(ax, ay);
end;
+var
+ nid: Integer;
begin
nid := visit(checker, cb);
{$IFDEF aabbtree_many_asserts}assert((nid < 0) or ((nid >= 0) and (nid < mNodeCount) and (mNodes[nid].leaf)));{$ENDIF}
// segment querying method
function TDynAABBTree.segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: Float; cb: TSegQueryCallback): Boolean;
var
- maxFraction: Float = 1.0e100; // infinity
- curax, curay: Float;
- curbx, curby: Float;
- dirx, diry: Float;
- invlen: Float;
+ maxFraction: Single = 1.0e100; // infinity
+ curax, curay: Single;
+ curbx, curby: Single;
+ dirx, diry: Single;
+ invlen: Single;
function checker (node: PTreeNode): Boolean;
begin
result := node.aabb.intersects(curax, curay, curbx, curby);
end;
- function visitor (flesh: TTreeFlesh): Boolean;
+ function visitor (flesh: TTreeFlesh; tag: Integer): Boolean;
var
- hitFraction: Float;
+ hitFraction: Single;
begin
hitFraction := cb(flesh, curax, curay, curbx, curby);
// if the user returned a hitFraction of zero, it means that the raycasting should stop here