I have a QuadTree in which I store vehicles for an RTS, and I’d like to use the mouse to draw a rectangular area on the screen and select all of the vehicles underneath it. In order to traverse the tree, I need functions to check 1) if a quad is completely contained by the rectangle (pink area), 2) if the rectangle is completely contained by a quad (yellow area), and 3) if a quad intersects with the rectangle (green areas). I’m thinking if I can find a frustum culling algorithm I might be able to change it to suit my needs, but I’m not sure about that.
Any ideas would be much appreciated.
It depends on what you’ve got so far, how you’re representing the QuadTree, etc. I imagine you must have a method of getting the four corners of a quad, so checking if a rectangle is inside is just a matter of seeing if all four rectangle corners are within the quad boundary. Similarly, a rectangle fully contains a quad if all four corners of the quad are inside the rectangle. If one or more corners are outside (but not all four) then the quad intersects the rectangle.
I’d need to see how your QuadTree is implemented to be able to give you any specific code, however.
Thanks for the insight andeeee.
The selection rectangle is in screen space (XY), and the quadtree is in world space, on the Y=0 plane. So the quadtree coordinates are X and Z. The camera is always going to be above the quadtree plane.
The problem with simply comparing the corners is that they are on different planes, and not necessarily aligned. raycasting through a corner of the rectangle may not intersect the plane of the quadtree at all (look at the blue section of the picture above)
The option I’m considering at the moment is building a frustum out of 4 planes, going through the camera position and the sides of the selection object, and then testing the quadtree corners to see if they are on the inside or outside of this frustum.
Can i assume that the plane constructor
static function Plane (a : Vector3, b : Vector3, c : Vector3) : Plane
sets the plane’s normal based on whether you feed the coordinates in clockwise or counterclockwise?
Sorry, I didn’t read the diagram correctly!
The Camera class has a ScreenPointToRay method that converts a pixel to a ray extending into the scene. The Plane class has a Raycast method that can find where the ray intersects the plane. You can then get the four corners of the rectangle (which is an irregular quadrilateral on the ground plane, of course) and test them to see where they fall in the quadtree.
You are right that the winding order of the points determines the direction of the plane, but you might find it easier just to use:-
Plane ground = new Plane(Vector3.up, 0f);
(or you can replace the 0f with whatever height ground level is).
There will be a special case that it can be a 5-sided figure on the ground plane, if only one of the corners of the selection box doesn’t intersect the quadtree plane. But that’s beside the point. Thanks for your help, I should be able to wrap my head around it now.