X-Git-Url: http://deadsoftware.ru/gitweb?a=blobdiff_plain;f=src%2Fgame%2Fz_aabbtree.pas;h=5b3fa623d9b13dd14d4f8a6c695d5242f1b4ce50;hb=081ca9c0120de313aae7a94d1fe50b275cf2176d;hp=5ebc8851c5a087810ba212172b6c5cfbe9e44afb;hpb=02014eee2eeed9f9b8dfa8b69c2fead669b59a6d;p=d2df-sdl.git diff --git a/src/game/z_aabbtree.pas b/src/game/z_aabbtree.pas index 5ebc885..5b3fa62 100644 --- a/src/game/z_aabbtree.pas +++ b/src/game/z_aabbtree.pas @@ -21,13 +21,13 @@ unit z_aabbtree; interface -uses e_log; +uses + e_log, g_grid; // ////////////////////////////////////////////////////////////////////////// // type - {$IFDEF aabbtree_use_floats}Float = Single;{$ELSE}Float = Integer;{$ENDIF} - //PFloat = ^Float; + {$IFDEF aabbtree_use_floats}TreeNumber = Single;{$ELSE}TreeNumber = Integer;{$ENDIF} TTreeFlesh = TObject; @@ -42,9 +42,9 @@ type public constructor Create (ax, ay: Single; aangle: Single); overload; constructor Create (ax0, ay0, ax1, ay1: Single); overload; - constructor Create (const aray: Ray2D); overload; + constructor Create (var aray: Ray2D); overload; - procedure copyFrom (const aray: Ray2D); inline; + procedure copyFrom (var aray: Ray2D); inline; procedure normalizeDir (); inline; @@ -56,46 +56,46 @@ type type AABB2D = record public - minX, minY, maxX, maxY: Float; + minX, minY, maxX, maxY: TreeNumber; private function getvalid (): Boolean; inline; - function getcenterX (): Float; inline; - function getcenterY (): Float; inline; - function getextentX (): Float; inline; - function getextentY (): Float; inline; + function getcenterX (): TreeNumber; inline; + function getcenterY (): TreeNumber; inline; + function getextentX (): TreeNumber; inline; + function getextentY (): TreeNumber; inline; public - constructor Create (x0, y0, x1, y1: Float); overload; - constructor Create (const aabb: AABB2D); overload; - constructor Create (const aabb0, aabb1: AABB2D); overload; + constructor Create (x0, y0, x1, y1: TreeNumber); overload; + constructor Create (var aabb: AABB2D); overload; + constructor Create (var aabb0, aabb1: AABB2D); overload; - procedure copyFrom (const aabb: AABB2D); inline; - procedure setDims (x0, y0, x1, y1: Float); inline; + procedure copyFrom (var aabb: AABB2D); inline; + procedure setDims (x0, y0, x1, y1: TreeNumber); inline; - procedure setMergeTwo (const aabb0, aabb1: AABB2D); inline; + procedure setMergeTwo (var aabb0, aabb1: AABB2D); inline; - function volume (): Float; inline; + function volume (): TreeNumber; inline; - procedure merge (const aabb: AABB2D); inline; + procedure merge (var aabb: AABB2D); inline; // return true if the current AABB contains the AABB given in parameter - function contains (const aabb: AABB2D): Boolean; inline; overload; - function contains (ax, ay: Float): Boolean; inline; overload; + function contains (var aabb: AABB2D): Boolean; inline; overload; + function contains (ax, ay: TreeNumber): Boolean; inline; overload; // return true if the current AABB is overlapping with the AABB in parameter // two AABBs overlap if they overlap in the two axes at the same time - function overlaps (const aabb: AABB2D): Boolean; inline; overload; + function overlaps (var aabb: AABB2D): Boolean; inline; overload; // ray direction must be normalized - function intersects (const ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload; + function intersects (var 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; - property centerY: Float read getcenterY; - property extentX: Float read getextentX; - property extentY: Float read getextentY; + property centerX: TreeNumber read getcenterX; + property centerY: TreeNumber read getcenterY; + property extentX: TreeNumber read getextentX; + property extentY: TreeNumber read getextentY; end; @@ -169,7 +169,7 @@ type public // return `true` to stop - type TForEachLeafCB = function (abody: TTreeFlesh; const aabb: AABB2D): Boolean is nested; // WARNING! don't modify AABB here! + type TForEachLeafCB = function (abody: TTreeFlesh; var aabb: AABB2D): Boolean is nested; // WARNING! don't modify AABB here! public // in the broad-phase collision detection (dynamic AABB tree), the AABBs are @@ -190,7 +190,7 @@ type // 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 - mExtraGap: Float; + mExtraGap: TreeNumber; public // called when a overlapping node has been found during the call to forEachAABBOverlap() @@ -215,7 +215,7 @@ type function computeHeight (nodeId: Integer): Integer; function insertObjectInternal (var aabb: AABB2D; staticObject: Boolean): Integer; procedure setup (); - function visit (checker: TVisitCheckerCB; visitor: TQueryOverlapCB; tagmask: Integer=-1): Integer; + function visit (var caabb: AABB2D; mode: Integer; checker: TVisitCheckerCB; visitor: TQueryOverlapCB; tagmask: Integer=-1): Integer; public {$IFDEF aabbtree_query_count} @@ -223,7 +223,7 @@ type {$ENDIF} public - constructor Create (extraAABBGap: Float=0); + constructor Create (extraAABBGap: TreeNumber=0); destructor Destroy (); override; // clear all the nodes and reset the tree @@ -264,15 +264,15 @@ type * * return `true` if the tree was modified. *) - function updateObject (nodeId: Integer; dispX, dispY: Float; forceReinsert: Boolean=false): Boolean; + function updateObject (nodeId: Integer; dispX, dispY: TreeNumber; forceReinsert: Boolean=false): Boolean; - 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; + function aabbQuery (ax, ay, aw, ah: TreeNumber; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh; + function pointQuery (ax, ay: TreeNumber; cb: TQueryOverlapCB): TTreeFlesh; + function segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: TreeNumber; cb: TSegQueryCallback): Boolean; function computeTreeHeight (): Integer; // compute the height of the tree - property extraGap: Float read mExtraGap write mExtraGap; + property extraGap: TreeNumber read mExtraGap write mExtraGap; property nodeCount: Integer read mNodeCount; property nodeAlloced: Integer read mAllocCount; {$IFDEF aabbtree_query_count} @@ -295,17 +295,17 @@ uses function minI (a, b: Integer): Integer; inline; begin if (a < b) then result := a else result := b; end; function maxI (a, b: Integer): Integer; inline; begin if (a > b) then result := a else result := b; end; -function minF (a, b: Float): Float; inline; begin if (a < b) then result := a else result := b; end; -function maxF (a, b: Float): Float; inline; begin if (a > b) then result := a else result := b; end; +function minF (a, b: TreeNumber): TreeNumber; inline; begin if (a < b) then result := a else result := b; end; +function maxF (a, b: TreeNumber): TreeNumber; inline; begin if (a > b) then result := a else result := b; 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; +constructor Ray2D.Create (var aray: Ray2D); overload; begin copyFrom(aray); end; -procedure Ray2D.copyFrom (const aray: Ray2D); inline; +procedure Ray2D.copyFrom (var aray: Ray2D); inline; begin origX := aray.origX; origY := aray.origY; @@ -341,17 +341,17 @@ end; // ////////////////////////////////////////////////////////////////////////// // -constructor AABB2D.Create (x0, y0, x1, y1: Float); overload; +constructor AABB2D.Create (x0, y0, x1, y1: TreeNumber); overload; begin setDims(x0, y0, x1, y1); end; -constructor AABB2D.Create (const aabb: AABB2D); overload; +constructor AABB2D.Create (var aabb: AABB2D); overload; begin copyFrom(aabb); end; -constructor AABB2D.Create (const aabb0, aabb1: AABB2D); overload; +constructor AABB2D.Create (var aabb0, aabb1: AABB2D); overload; begin setMergeTwo(aabb0, aabb1); end; @@ -359,16 +359,16 @@ end; function AABB2D.getvalid (): Boolean; inline; begin result := (minX < maxX) and (minY < maxY); 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; +function AABB2D.getcenterX (): TreeNumber; inline; begin result := (minX+maxX)/2.0; end; +function AABB2D.getcenterY (): TreeNumber; 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; +function AABB2D.getcenterX (): TreeNumber; inline; begin result := (minX+maxX) div 2; end; +function AABB2D.getcenterY (): TreeNumber; 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; +function AABB2D.getextentX (): TreeNumber; inline; begin result := (maxX-minX); end; +function AABB2D.getextentY (): TreeNumber; inline; begin result := (maxY-minY); end; -procedure AABB2D.copyFrom (const aabb: AABB2D); inline; +procedure AABB2D.copyFrom (var aabb: AABB2D); inline; begin minX := aabb.minX; minY := aabb.minY; @@ -380,7 +380,7 @@ begin end; -procedure AABB2D.setDims (x0, y0, x1, y1: Float); inline; +procedure AABB2D.setDims (x0, y0, x1, y1: TreeNumber); inline; begin minX := minF(x0, x1); minY := minF(y0, y1); @@ -392,7 +392,7 @@ begin end; -procedure AABB2D.setMergeTwo (const aabb0, aabb1: AABB2D); inline; +procedure AABB2D.setMergeTwo (var aabb0, aabb1: AABB2D); inline; begin {$IF DEFINED(D2F_DEBUG)} if not aabb0.valid then raise Exception.Create('setMergeTwo: aabb0 is fucked'); @@ -408,13 +408,13 @@ begin end; -function AABB2D.volume (): Float; inline; +function AABB2D.volume (): TreeNumber; inline; begin result := (maxX-minX)*(maxY-minY); end; -procedure AABB2D.merge (const aabb: AABB2D); inline; +procedure AABB2D.merge (var aabb: AABB2D); inline; begin {$IF DEFINED(D2F_DEBUG)} if not aabb.valid then raise Exception.Create('merge: aabb is fucked'); @@ -429,7 +429,7 @@ begin end; -function AABB2D.contains (const aabb: AABB2D): Boolean; inline; overload; +function AABB2D.contains (var aabb: AABB2D): Boolean; inline; overload; begin result := (aabb.minX >= minX) and (aabb.minY >= minY) and @@ -437,13 +437,13 @@ begin end; -function AABB2D.contains (ax, ay: Float): Boolean; inline; overload; +function AABB2D.contains (ax, ay: TreeNumber): Boolean; inline; overload; begin result := (ax >= minX) and (ay >= minY) and (ax <= maxX) and (ay <= maxY); end; -function AABB2D.overlaps (const aabb: AABB2D): Boolean; inline; overload; +function AABB2D.overlaps (var aabb: AABB2D): Boolean; inline; overload; begin result := false; // exit with no intersection if found separated along any axis @@ -455,7 +455,7 @@ 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: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload; +function AABB2D.intersects (var ray: Ray2D; tmino: PSingle=nil; tmaxo: PSingle=nil): Boolean; overload; var dinv, t1, t2, tmp: Single; tmin, tmax: Single; @@ -602,8 +602,8 @@ var currentNodeId: Integer; leftChild, rightChild, siblingNode: Integer; oldParentNode, newParentNode: Integer; - volumeAABB, mergedVolume: Float; - costS, costI, costLeft, costRight: Float; + volumeAABB, mergedVolume: TreeNumber; + costS, costI, costLeft, costRight: TreeNumber; begin // if the tree is empty if (mRootNodeId = TTreeNode.NullTreeNode) then @@ -1124,9 +1124,12 @@ end; // 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: TQueryOverlapCB; tagmask: Integer=-1): Integer; +const ModeNoChecks = 0; +const ModeAABB = 1; +const ModePoint = 2; +function TDynAABBTree.visit (var caabb: AABB2D; mode: Integer; checker: TVisitCheckerCB; visitor: TQueryOverlapCB; tagmask: Integer=-1): Integer; var - stack: array [0..255] of Integer; // stack with the nodes to visit + stack: array [0..2048] of Integer; // stack with the nodes to visit bigstack: array of Integer = nil; sp: Integer = 0; @@ -1159,10 +1162,9 @@ var end; end; - (* function spop (): Integer; inline; begin - {$IFDEF aabbtree_many_asserts}assert(sp > 0);{$ENDIF} + //{$IFDEF aabbtree_many_asserts}assert(sp > 0);{$ENDIF} if (sp <= length(stack)) then begin // use "small stack" @@ -1176,15 +1178,16 @@ var result := bigstack[sp-length(stack)]; end; end; - *) var nodeId: Integer; node: PTreeNode; + doNode: Boolean = false; begin if not assigned(checker) then begin result := -1; exit; end; + if not assigned(visitor) then raise Exception.Create('dyntree: empty visitors aren''t supported'); //if not assigned(visitor) then begin result := -1; exit; end; - try + //try {$IFDEF aabbtree_query_count} mNodesVisited := 0; mNodesDeepVisited := 0; @@ -1197,37 +1200,56 @@ begin while (sp > 0) do begin // get the next node id to visit - //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; - + {$IF TRUE} + nodeId := spop(); + {$ELSE} + 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; + {$ENDIF} // skip it if it is a nil node if (nodeId = TTreeNode.NullTreeNode) then continue; {$IFDEF aabbtree_query_count}Inc(mNodesVisited);{$ENDIF} // get the corresponding node node := @mNodes[nodeId]; // should we investigate this node? - if (checker(node)) then + case mode of + ModeNoChecks: doNode := checker(node); + ModeAABB: + begin + //doNode := caabb.overlaps(node.aabb); + // this gives small speedup (or not...) + // exit with no intersection if found separated along any axis + if (caabb.maxX < node.aabb.minX) or (caabb.minX > node.aabb.maxX) then doNode := false + else if (caabb.maxY < node.aabb.minY) or (caabb.minY > node.aabb.maxY) then doNode := false + else doNode := true; + end; + ModePoint: + begin + //doNode := node.aabb.contains(caabb.minX, caabb.minY); + // this gives small speedup + doNode := (caabb.minX >= node.aabb.minX) and (caabb.minY >= node.aabb.minY) and (caabb.minX <= node.aabb.maxX) and (caabb.minY <= node.aabb.maxY); + end; + end; + if doNode then begin // if the node is a leaf if (node.leaf) then begin // call visitor on it {$IFDEF aabbtree_query_count}Inc(mNodesDeepVisited);{$ENDIF} - if ((node.tag and tagmask) <> 0) and assigned(visitor) then + if ((node.tag and tagmask) <> 0) then begin - if (visitor(node.flesh, node.tag)) then begin result := nodeId; exit; end; + if (visitor(node.flesh, node.tag)) then begin result := nodeId; bigstack := nil; exit; end; end; end else @@ -1240,15 +1262,16 @@ begin end; result := -1; // oops - finally bigstack := nil; - end; + //finally + // bigstack := nil; + //end; end; // 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); +constructor TDynAABBTree.Create (extraAABBGap: TreeNumber=0); begin mExtraGap := extraAABBGap; setup(); @@ -1353,7 +1376,7 @@ begin end; -function TDynAABBTree.updateObject (nodeId: Integer; dispX, dispY: Float; forceReinsert: Boolean=false): Boolean; +function TDynAABBTree.updateObject (nodeId: Integer; dispX, dispY: TreeNumber; forceReinsert: Boolean=false): Boolean; var newAABB: AABB2D; begin @@ -1406,7 +1429,7 @@ end; // report all shapes overlapping with the AABB given in parameter -function TDynAABBTree.aabbQuery (ax, ay, aw, ah: Float; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh; +function TDynAABBTree.aabbQuery (ax, ay, aw, ah: TreeNumber; cb: TQueryOverlapCB; tagmask: Integer=-1): TTreeFlesh; var caabb: AABB2D; function checker (node: PTreeNode): Boolean; @@ -1419,35 +1442,44 @@ begin result := nil; if not assigned(cb) then exit; if (aw < 1) or (ah < 1) then exit; - caabb := AABB2D.Create(ax, ay, ax+aw, ay+ah); - nid := visit(checker, cb, tagmask); + //caabb := AABB2D.Create(ax, ay, ax+aw, ay+ah); + caabb.minX := ax; + caabb.minY := ay; + caabb.maxX := ax+aw; + caabb.maxY := ay+ah; + nid := visit(caabb, ModeAABB, 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; +function TDynAABBTree.pointQuery (ax, ay: TreeNumber; cb: TQueryOverlapCB): TTreeFlesh; function checker (node: PTreeNode): Boolean; begin result := node.aabb.contains(ax, ay); end; + function dummycb (abody: TTreeFlesh; atag: Integer): Boolean; begin result := false; end; var nid: Integer; + caabb: AABB2D; begin - nid := visit(checker, cb); + if not assigned(cb) then cb := dummycb; + caabb := AABB2D.Create(ax, ay, ax+1, ay+1); + nid := visit(caabb, ModePoint, checker, cb); {$IFDEF aabbtree_many_asserts}assert((nid < 0) or ((nid >= 0) and (nid < mNodeCount) and (mNodes[nid].leaf)));{$ENDIF} if (nid >= 0) then result := mNodes[nid].flesh else result := nil; end; // segment querying method -function TDynAABBTree.segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: Float; cb: TSegQueryCallback): Boolean; +function TDynAABBTree.segmentQuery (var qr: TSegmentQueryResult; ax, ay, bx, by: TreeNumber; cb: TSegQueryCallback): Boolean; var maxFraction: Single = 1.0e100; // infinity curax, curay: Single; curbx, curby: Single; dirx, diry: Single; invlen: Single; + caabb: AABB2D; function checker (node: PTreeNode): Boolean; begin @@ -1502,7 +1534,8 @@ begin dirx *= invlen; diry *= invlen; - visit(checker, visitor); + caabb := AABB2D.Create(0, 0, 1, 1); + visit(caabb, ModeNoChecks, checker, visitor); result := qr.valid; end;