TQuadTree

• add:
• add:depth:
• addSphere:
• boundSphere
• globalTransformUpdate
• outBox
• quadOn
• quadOn:

• handlesPointerDown:
• pointerDown:
• step
• wantsSteps

• initializeWithCorner:size:depth:
• initializeWithFrame:
• initializeWithSpace:frame:
• reinstall

• hasAlpha
• pickFloor:
• quadPickFloor:location:
• renderAlpha:
• renderFrame:parent:root:
• renderFrame:space:
• renderTree:root:
• renderTree:space:

• isComponent

" Adds the boundSphere to the octree/quadtree."

	self add: bdSph depth: depth.

" Adds the boundSphere to the octree/quadtree."

	| sphLoc |

	sphLoc _ bndSph globalPosition.
	inBox growVertex: sphLoc.
	outBox _ outBox unionBox: 
		(inBox unionSphere:bndSph globalPosition radius: bndSph radius).
	radius _ outBox diagonal/2.0.
	center _ outBox center.
"------ This is as deep as we go - add the sphere -------"
	dpth = 0 ifTrue:[ 
		self addSphere: bndSph.
 		^ true. 
		].

"------ Will the sphere fit into this quad? ------"
	bndSph radius > (quadSize/2.0) ifTrue:[ 
 		self addSphere: bndSph. 
		^ true.	
		].

"------ Then which quad should it go into? ------ "

	sphLoc x < center x ifTrue:[
		sphLoc z < center z ifTrue:[ 
			qtTL ifNil:[ qtTL _TQuadTree new initializeWithCorner: quadCorner size: quadSize depth: depth.].
			^ qtTL add: bndSph depth: (dpth-1).
			].
		qtBL ifNil:[ 
			qtBL _ TQuadTree new initializeWithCorner: (quadCorner+(B3DVector3 x:0 y:0 z:quadSize)) size: quadSize depth: depth.].
			^ qtBL add: bndSph depth: (dpth-1).
		].
	sphLoc z < center z ifTrue:[
		qtTR ifNil:[ 
			qtTR _TQuadTree new initializeWithCorner: (quadCorner+(B3DVector3 x:quadSize y:0 z:0)) size: quadSize depth: depth.].
		^ qtTR add: bndSph depth: (dpth-1).
		].
	qtBR ifNil:[
		qtBR _TQuadTree new initializeWithCorner: (quadCorner+(B3DVector3 x:quadSize y:0 z:quadSize)) size: quadSize depth: depth.].
	^ qtBR add: bndSph depth: (dpth-1).
	

	spheres ifNil:[spheres _ OrderedCollection new.].
	spheres add: bs.

	^ boundSphere.

	self reinstall.

	^ outBox.

	^ quadOn.

	"Turn the quadtree rendering on/off"
	quadOn _ bool.

	^ true.

	^ true.

"	angle ifNil:[angle _ 0.].
	angle _ angle + 1.
	self rotationAroundY: angle."

	^ true.

	|  cornerMax |

	self initialize.
	quadSize _ sz/2.0.
	quadCorner _ crnr clone.
	quadCorner y: Float infinity.
	cornerMax _ crnr + sz.
	cornerMax y: Float infinity negated.
	inBox _ TBox new. "min: corner max:cornerMax."
	outBox _ TBox new.
	quadCenter _ quadCorner + (quadSize/2.0).
	radius _ 0.
	self visible: false.
	depth _ dpth.
	self quadOn: true.
	^self

	self initialize.
	self addChild: frame.
	frame objectOwner: self.
	self visible: false.
	self quadOn: true.
	^self

	| ext rad |

	self initialize.
	space addChild: self.
	self addChild: frame.
	frame objectOwner: self.
	frameChildren do:[ :fc | fc frameChanged.].
	rad _ frame octreeRadius.
	inBox _ frame octreeBox.
	outBox _ TBox new.
	quadCenter _ inBox center.
"----- size is 1/2 of the length of a quadtree side. -----"
	ext _ inBox extent.
	quadSize _ ext x > ext z ifTrue:[ ext x ] ifFalse:[ext z].
	"size _ size > ext y ifTrue:[ size ] ifFalse:[ext y]. don't need for quadtrees"
	quadSize _ quadSize/2.0.
	quadSize < rad ifTrue:[ quadSize _ rad.].
	quadCorner _ quadCenter - quadSize.
	radius _ 0.0.
	depth _ 5.
	self visible: false.

	frameChildren do:[ :fc |
			fc octreeSieve: self.].
	boundSphere _ TBoundSphere localPosition: outBox center radius: outBox diagonal/2.0.
	boundSphere frame: self.
	self quadOn: true.
	^self

	| frame rad ext |

	frame _ frameChildren at: 1.
	rad _ frame octreeRadius.
	inBox _ frame octreeBox.
	outBox _ TBox new.
	quadCenter _ inBox center.
	qtTL_ nil.
	qtTR_ nil.
	qtBL_ nil.
	qtBR_ nil.
	spheres _ nil.
"----- size is 1/2 of the length of a quadtree side. -----"
	ext _ inBox extent.
	quadSize _ ext x > ext z ifTrue:[ ext x ] ifFalse:[ext z].
	"size _ size > ext y ifTrue:[ size ] ifFalse:[ext y]. don't need for quadtrees"
	quadSize _ quadSize/2.0.
	quadSize < rad ifTrue:[ quadSize _ rad.].
	quadCorner _ quadCenter - quadSize.
	radius _ 0.0.
	depth _ 5.
	self visible: false.

	frameChildren do:[ :fc |
			fc octreeSieve: self.].
	boundSphere _ TBoundSphere localPosition: outBox center radius: outBox diagonal/2.0.
	boundSphere frame: self.

	^ false.

	^ self quadPickFloor: pointer location: pointer framePosition.	

	| d rval |
	
	(outBox pointOverBox: location) ifFalse:[^ false.].
	rval _ false.
	spheres ifNotNil:[
		spheres do:[ : sp |
			sp frame isSolid ifTrue:[
				d _ (sp globalPosition - pointer globalPosition) abs.
				( d x < sp radius and: [d z < sp radius]) ifTrue:[
					(pointer pickDownSphere: sp) ifTrue:[
						(pointer pointerPickFloor: sp frame) ifTrue:[rval _ true].
						].
					].
				].
			].
		].
		
	qtTL ifNotNil:[(qtTL quadPickFloor: pointer location: location) ifTrue:[rval _ true].].
	qtBL ifNotNil:[(qtBL quadPickFloor: pointer location: location) ifTrue:[rval _ true].].
	qtTR ifNotNil:[(qtTR quadPickFloor: pointer location: location) ifTrue:[rval _ true].].
	qtBR ifNotNil:[(qtBR quadPickFloor: pointer location: location) ifTrue:[rval _ true].].
	^ rval.

"	| mat |

	ogl glDisable: GLCullFace.
	mat _ TMaterial initialize: cWorld.
	mat ambientColor: #(0.7  0.2 0.1 0.3)asFloatArray.
	mat diffuseColor: #(0.7  0.2 0.1 0.3)asFloatArray.
	mat enable: ogl.
	ogl renderBox: box.
	qtTL ifNotNil:[ qtTL renderAlpha: ogl.].
	qtTR ifNotNil:[ qtTR renderAlpha: ogl.].
	qtBL ifNotNil:[ qtBL renderAlpha: ogl.].
	qtBR ifNotNil:[ qtBR renderAlpha: ogl.].
	ogl setCull."

	| count |
	quadOn ifFalse:[^ super renderFrame: ogl parent: parent root: root.]. "Traditional rendering method - used for testing and picking"
	frameChanged ifTrue:[ 
		super renderFrame: ogl parent: parent root: root. 
		frameChanged ifTrue:[self reinstall.].
		frameChanged _ false.
		^0.
		].
	" something of a problem - Quadtrees do not lend themselves to standard picking using this method."
	root testRayFramesQuadTree: self. 

	ogl glPushMatrix.
	count _ self renderTree: ogl root: root.
	ogl glPopMatrix.
"------ This is just test code to see where the quads really are. ------"
"	self alpha ifTrue: [ 
		space addAlpha: 
		(TRenderAlpha object: self 
			transform: space currentTransform clone
			distance: (ogl activeCamera globalPosition - space currentTranslation ) squaredLength
			parent: space currentParent).]."

	^ count.

	| count |
	quadOn ifFalse:[^ super renderFrame: ogl space: space.]. "Traditional rendering method - used for testing and picking"
	frameChanged ifTrue:[ 
		super renderFrame: ogl space: space. 
		frameChanged ifTrue:[self reinstall.].
		frameChanged _ false.
		^0.
		].
	" something of a problem - Quadtrees do not lend themselves to standard picking using this method."
	space testRayFramesQuadTree: self.

	ogl glPushMatrix.
	count _ self renderTree: ogl space: space.
	ogl glPopMatrix.
"------ This is just test code to see where the quads really are. ------"
"	self alpha ifTrue: [ 
		space addAlpha: 
		(TRenderAlpha object: self 
			transform: space currentTransform clone
			distance: (ogl activeCamera globalPosition - space currentTranslation ) squaredLength
			parent: space currentParent).]."

	^ count.

	| count globalTrans ac |
	ac _ ogl camera.
	count _ 0.
	"is this inside the viewing pyramid?"
	(ac testSphere: center radius: radius) ifTrue:[
		spheres ifNotNil:[
			spheres do:[:sp | 
				(ac testBounds: sp) ifTrue:[
					ogl glPushMatrix.
					ogl glMultMatrixf: sp frame globalTransform transposed.
					sp frame render: ogl. 
					count _ count + 1.
					sp frame hasAlpha ifTrue: [ 
						globalTrans _ B3DMatrix4x4 new.
						ogl glGetFloatv: GLModelviewMatrix with: globalTrans.
						root addAlphaObject: sp frame 
							transform: globalTrans
							distance: (ac globalPosition - 
								sp globalPosition) squaredLength
							parent: sp frame parent.
						].
					ogl glPopMatrix.
					].
				].
			].
		qtTL ifNotNil:[ count _ count + (qtTL renderTree: ogl root: root).].
		qtTR ifNotNil:[ count _ count + (qtTR renderTree: ogl root: root).].
		qtBL ifNotNil:[ count _ count + (qtBL renderTree: ogl root: root).].
		qtBR ifNotNil:[ count _ count + (qtBR renderTree: ogl root: root).].
		].
	^ count.

	| count globalTrans ac |
	ac _ ogl camera.
	count _ 0.
	"is this inside the viewing pyramid?"
	(ac testSphere: center radius: radius) ifTrue:[
		spheres ifNotNil:[
			spheres do:[:sp | 
				(ac testBounds: sp) ifTrue:[
					ogl glPushMatrix.
					ogl glMultMatrixf: sp frame globalTransform transposed.
					sp frame render: ogl. 
					count _ count + 1.
					sp frame hasAlpha ifTrue: [ 
						globalTrans _ B3DMatrix4x4 new.
						ogl glGetFloatv: GLModelviewMatrix with: globalTrans.
						space addAlphaObject: sp frame 
							transform: globalTrans
							distance: (ac globalPosition - 
								sp globalPosition) squaredLength
							parent: sp frame parent.
						].
					ogl glPopMatrix.
					].
				].
			].
		qtTL ifNotNil:[ count _ count + (qtTL renderTree: ogl space: space).].
		qtTR ifNotNil:[ count _ count + (qtTR renderTree: ogl space: space).].
		qtBL ifNotNil:[ count _ count + (qtBL renderTree: ogl space: space).].
		qtBR ifNotNil:[ count _ count + (qtBR renderTree: ogl space: space).].
		].
	^ count.

	^ false.