More information about using 3D selection boxes?

Lethn

I'm currently working my way through this tutorial and learning the maths that goes into a 3D selection box, as you guys know I had already looked at a 2D selection box which is working fine and what's nice is it transferred over to my 3D project fine. What I'm surprised by and this is not an exaggeration, this seems to be one of the only videos out there nevermind posts on the topic throughout the internet that I can find so far. Does anyone have potentially more or up to date information on how to make a 3D selection box? I'll manage but it is going to be annoying transferring this to Godot 4.

MagickPanda

What you mean by 3D selectionbox？
The selection box's visual appearance is 3D or it's 2D visually but it selects objects in 3d frustrum?

Lethn

Yes, the 3D frustrum maths is something I'm trying to research, you use the points of the 2D selection box to convert to 3D and grab the units.

Lethn

Partially got it working but accuracy is of course a bit of an issue due to the way I've written it but this should give people an idea of what I'm going for, working through that video is frustrating to say the least, trying to get things neater and working with Godot 4.

extends Control

var isDragging = false

var dragStart = Vector2()
var dragEnd = Vector2()

var selectedRectangle = RectangleShape2D.new()

@onready var boxSelection3D = $"../BoxSelection3D"

func _physics_process(_delta):
	
	if isDragging:
		queue_redraw()

func _unhandled_input(event):
	if event is InputEventMouseButton and event.button_index == MOUSE_BUTTON_LEFT:
		
		if event.is_pressed():
				isDragging = true
				dragStart = get_global_mouse_position()
				
				boxSelection3D.BoxSelectionGetUnits()
				boxSelection3D.startPosition = dragStart
				boxSelection3D.endPosition = dragEnd
		
		elif isDragging == true:
			isDragging = false
			queue_redraw()
			dragEnd = get_global_mouse_position()
			selectedRectangle.size = (dragEnd - dragStart).abs()
			var space = get_world_2d().direct_space_state
			var query = PhysicsShapeQueryParameters2D.new()
			query.set_shape(selectedRectangle)
			query.transform = Transform2D (0, (dragEnd + dragStart) / 2)
			
			for selectedUnit in boxSelection3D.selectedUnits:
				selectedUnit.DisableSelectionRing()
		
func _draw():
	if isDragging == true:
		draw_rect(Rect2 (dragStart, get_global_mouse_position() - dragStart), Color.DARK_GREEN, false, 2.0)

extends Node3D

@onready var boxSelection2D = $"../BoxSelection2D"
@onready var playerCamera = $".."

var startPosition = Vector2()
var endPosition = Vector2()

var box = Rect2()

var selectedUnits = []

func BoxSelectionGetUnits ():
	if boxSelection2D.isDragging == true:
		if startPosition.x > endPosition.x:
			var tmp = startPosition.x
			startPosition.x = endPosition.x
			endPosition.x = tmp
		if startPosition.y > endPosition.y:
			var tmp = startPosition.y
			startPosition.y = endPosition.y
			endPosition.y = tmp
		box = Rect2(startPosition, endPosition - startPosition)
		for unit in get_tree().get_nodes_in_group("Selectable"):
			if box.has_point(playerCamera.unproject_position(unit.global_transform.origin)):
				selectedUnits.append(unit)
				unit.EnableSelectionRing()
				return selectedUnits

Lethn

Range is an issue with this code as well, will need to heavily tweak.

xyz

3d area-select is simple and straightforward, relatively speaking of course. There's nothing Godot specific needed to implement it, it's pretty much just vector math.

project 4 corners of the screen rectangle to the near plane
project 4 corners of the screen rectangle to the far plane
those 8 points now form a rectangular frustum (pyramid with chipped-off top), with 6 faces in total.
take normals of each of the 6 faces and use them to check if a selectable AABB is fully/partially inside. This is easy to do by simply comparing ranges and some dot products as shown here

Lethn

The main issue I'm having is trying to get a barebones example going, I understand the theory, the classic problem is the syntax.

xyz

Here's the implementation, for anyone who might be interested. It could be optimized a bit more, but this is the "learning edition" 😉
To make a query simply call aabb_intersects_rect(), passing it world space aabb to test, screen space rect, and the current camera.

func aabb_intersects_rect(aabb: AABB, rect: Rect2, cam: Camera3D) -> bool:
	var f = get_frustum(Rect2($rect.position, $rect.size), cam)
	return aabb_intersects_frustum(f, aabb)
	

func aabb_intersects_frustum(frustum: Array, box: AABB) -> bool:
	var mins = box.position
	var maxs = box.position + box.size
	
	var result = true # inside
	var vmin: Vector3
	var vmax: Vector3 
	var n: Vector3

	for i in frustum.size():
		if frustum[i].x > 0:
			vmin.x = mins.x
			vmax.x = maxs.x;
		else:
			vmin.x = maxs.x
			vmax.x = mins.x

		if frustum[i].y > 0: 
			vmin.y = mins.y
			vmax.y = maxs.y
		else:
			vmin.y = maxs.y
			vmax.y = mins.y

		if frustum[i].z > 0:
			vmin.z = mins.z
			vmax.z = maxs.z
		else:
			vmin.z = maxs.z
			vmax.z = mins.z
			
		n = Vector3(frustum[i].x, frustum[i].y, frustum[i].z)
		if n.dot(vmin) + frustum[i].w > 0:
			return false # outside; 
		if n.dot(vmax) + frustum[i].w >= 0: 
			result = true # intersects; 
		
	return result;


func get_frustum(rect: Rect2, cam: Camera3D) -> Array:
	var pnear = project_rect(rect, cam, cam.near+1)
	var pfar = project_rect(rect, cam, cam.far-1)
	var frustum = []
	frustum.resize(6)
	frustum[0] = plane(pnear[0], pnear[1], pnear[2]) # near
	frustum[1] = plane(pfar[2], pfar[1], pfar[0]) # far
	frustum[2] = plane(pfar[0], pnear[0], pnear[3]) # left
	frustum[3] = plane(pnear[2], pnear[1], pfar[1] ) # right
	frustum[4] = plane(pnear[1], pnear[0], pfar[0]) # top
	frustum[5] = plane(pnear[3], pnear[2], pfar[2]) # bottom
	return frustum
	

func project_rect(rect: Rect2, cam: Camera3D, z: float) -> PackedVector3Array:
	var p = PackedVector3Array()
	p.resize(4)
	p[0] = cam.project_position(rect.position, z)
	p[1] = cam.project_position(rect.position + Vector2(rect.size.x, 0.0), z)
	p[2] = cam.project_position(rect.position + Vector2(rect.size.x, rect.size.y), z)
	p[3] = cam.project_position(rect.position + Vector2(0.0, rect.size.y), z)
	return p


func plane(p1: Vector3, p2: Vector3, p3: Vector3) -> Vector4:
	var n = (p1-p2).cross((p3-p2)).normalized()
	var d = -p1.x * n.x - p1.y * n.y - p1.z * n.z 
	return Vector4(n.x, n.y, n.z, d)

Lethn

LOL oh for crying out loud xyz thanks as it so happens I also found this tutorial with some keyword tweaking in the search, will use both and study up. It even looks like this tutorial is properly up to date and the guy is using Godot 4, yep, I wouldn't have been able to work this out on my own, this maths is tricky for people who don't already know it.

xyz

Lethn The way it is done in this tutorial is rather weak. It un-projects a single centerpoint back into screen space and checks if it's inside the selection rectangle. Simple to implement but not good if you're zoomed in, have large units, or strong perspective. It would feel a bit annoying to the player as they'd never know how "deep" they must draw the rect into the unit for selection to take place. My example does universal 3d area-select, the proper way, using 3d bounding boxes. Can be used in rts or any other kind of game.

Lethn

It is fascinating though that a 3D selection box is such a common feature in software yet with game dev there aren't that many examples and tutorials out there for some reason, these two videos were the only ones I could find and there was little to no posts on the topic.

xyz

Lethn Yeah, area-select is commonly needed in games. It may even deserve a place in the core functionality, or at least a solid native plugin. It'd also fit nicely in the cookbook part of the documentation, alongside the recipe for ray-picking, as they typically go hand in hand.

Megalomaniak

xyz It'd also fit nicely in the cookbook part of the documentation,

Not to tell you what to do... 👉️ 👈️ but since I agree with the notion and seeing how you already have about half of it written/done in that previous post, might it be ok to point out that the docs repo does accept pull requests? 😉

xyz

Megalomaniak 👉️ 👈️

Somehow I just knew you'd come and pester me about it 😉
I'll see what I can do.

Lethn

xyz LOL it would be really helpful Xyz and probably help out a lot of people and really anything to avoid multiple topics around the internet with zero real answers, I think there's a debate to be had about the 'best' method though as it seems there are multiple calculations to be done with a 3D selection box from what I've seen posted by others on this topic.

xyz

Lethn All tutorials you posted so far are making half-assed non-general approaches to avoid doing "complicated" math. What I posted is a general solution that overarches all of the those special cases (e.g. testing only the centerpoints, doing it only on the ground plane etc) . It also discriminates between partial/full enclosure, so you can use it for a system that requires full enclosure to make a selection or a system where merely touching the object is enough. If you insist, it can also behave exactly like what is done in the last video. You just need to make the bounding boxes small. It is in fact the "best" solution, although a bit more computationally expensive than any special case, but not by much.

Lethn

I just wanted to know about 3D selection boxes and then I fell down the rabbit hole ;_;

Lethn

I think there's also potentially a debate on the multiple methods, but I'll be happy if I can just get a decent selection box that's accurate enough for gaming. As you've probably guessed, I got fed up with my 2D RTS idea because I was annoyed with the TileMap behaviour the most. I would rather deal with that level of maths if I know it's all going to work and I've already sorted out how I'm going to do all the other code for the 3D RTS in my head. I even wonder with RTS' in general if 2.5D is actually the better approach and using 3D sprites is the way to go when it comes to dealing with that thanks to modern software.

synthnostate

Hi, I've been following this over on Minds, guess it's time I joined this forum. My first thought was to use a frustum, but I suggested @Lethn try Camera3D.unproject_position(centerpoint) and do the math in 2D for simplicity because he's relatively new to gamedev (no offense lol). I've made my own 3D engine with broadphase-narrowphase bbox and precise raycast picking, I know how it's done, but it's important not to get carried away, just stick to simple solid code you can understand, and improve it later if you really need to.

Anyway, I thought of simpler method: compute a frustum using @xyz's method, plug the vertexes into a CollisionShape3D attached to an Area3D, and call Area3D.get_overlapping_bodies() to query for selected objects. This should be efficient and accurate. You will need collision meshes on your objects, or Area3Ds if you don't want any physics (use Area3D.get_overlapping_areas in that case).

xyz

synthnostate Not bad, but it's arguable if it's really simpler. I mean it's basically the same thing but you pile on extra convex mesh collision checks, and a need for additional selection collider setup on each selectable object. Although it may possibly even be faster because checks are done in native code, for a continuous update while dragging you'd need to rebuild the convex mesh collider every frame. If things were done in the same language I'd always go with aabb test rather than full blown convex mesh test. It's much less expensive. Someone should benchmark those two (GDScript aabb check vs native collider check, with frustum rebuild each frame), I'd be interested to see which one is actually faster.

synthnostate

xyz Exactly, let the engine's battle-tested native code core do the work and keep your code simple. It's probably optimized to skip the convex mesh test when the bboxes don't intersect, and no doubt it uses spatial partitioning to skip the bbox test for objects that aren't even close. And this is cheap compared to full-blown physics, which constantly tests ALL collision meshes against each other.

Remember, a bbox test alone isn't accurate. For example if you have a spherical object and you drag your selection box over the corner of its bbox, it'll be selected even though you're not actually touching the sphere. That's not necessarily better than a centerpoint test. You might as well use collision system and get partitioning and bbox optimizations "for free".