[PATCH] Fixed-angle/huge bounding boxes cause unintuitive selection behaviour

[vts]

To determine which units are to be highlighted/selected when the mouse is at a certain position, a ray is cast from the camera to the point on the terrain pointed to by the mouse, and this ray is checked for intersections with the bounding boxes of all the Selectable entities in the scene. If multiple objects' bounding boxes are intersected, the one where the ray passes the closest by its center wins.

However, the bounding boxes ignore the rotation of the models. This can cause the visual outline of the object to differ greatly from the bounding boxes used for hit testing, which causes unintuitive selection/highlight behaviour: typically buildings or trees are selected even though the mouse is nowhere near them. Some trees have massive bounding boxes, which does not help.

Also, this prevents the user from setting the a building's rally point at many points in the terrain, because seemingly unrelated objects will be highlighted instead.

The example screenshots below are also attached:

​http://i.imgur.com/kmcaO.jpg

The red outline is the bounding box of the currently highlighted tree. Even though the mouse is halfway up the screen, some random tree is selected all the way down.

​http://i.imgur.com/Ggl6d.jpg

Again, the red outline is the bounding box, the blue is the actual floorplan. Any 2D mouse location within the red outlines will cause the building to be highlighted. This makes it impossible to set the rally point near the top of the outline under the metal mine, even though that location would otherwise be perfectly valid.

[vts]

local copies of the bounding boxes screenshots in case the imgur links stop working

[vts]

Currently working on this. I have a basic implementation of oriented bounding boxes that take the model rotation into account, and have the selection rays test against that instead of the axis-aligned bounding box. Seems to work ok at first sight, but more testing is needed to ensure it works in all cases. A patch will follow as soon as I'm convinced that I've covered all cases.

[Erik Johansson]

Sweet. Sounds like it will be a huge improvement over the way things work now :)

[vts]

Ok, so I've played with it more, and there are basically two options here. Ray-testing against rotated selection boxes is working; the issue now is what to include in the selection box. The in-game models are composed in a hierarchy of a base model and some props attached to it; currently either further submodels or decals and particle emitters. Depending on which you include, you get different sizes selection boxes, and hence different selection behaviour.

If you include everything, then the bounding boxes you end up with tend be huge, and much of the benefit of taking rotation into account is lost by the same account that's causing the original problem. Particularly particle emitters (like e.g. smoke) tend to take up large height spans, resulting in massive selection boxes.

If you don't include any props, you sometimes run into a problematic situation where props make up a large part of the full visual representation of a model. For instance, some of the large temples on Acropolis are really a base model of the roof plus a bunch of props for the pillars and the steps. The result is that the selection only "works" on the roof. Another example are the sails on merchant ships.

However, there is a fairly simple trick that seems effective at countering this, which is to clamp the selection box to touch the ground level. This is needed anyway, since some models are apparently partially embedded into the earth, and you don't want to be selecting something because your mouse is hovering over the bit that's underground.

Another option that might be even better is to include any submodels, but exclude any particle emitters and decals from the selection box. It doesn't really make sense to select a building by the smoke it emits or the dirt around it anyway. I'll be trying this out next to see how it works out.

[vts]

After a lot of further experimenting, here's the patch. It includes submodels in the selection box, but excludes decals and particle emitters to prevent it from getting huge and defeating the original purpose. As it turns out though, the original (fixed-orientation) bounding boxes did not include any submodels.

Since this code will probably be called many times each frame, performance is likely to be important. As of now, the selection box is cached to prevent excessive recomputation, at the cost of some extra memory per unit. I'm not positive where the trade-off balance should be at, but some quick tests without caching suggest that reducing calculation time seems the best way to go.

There are still many opportunities for improvement. As noted by Philip on IRC, the current scheme of iterating over all units and hittesting them individually might eventually (and ideally) be replaced by a much faster method, which should improve performance substantially. For now though, I hope this will do.

[vts]

Side note: this patch would also fix #295 for reasons explained above.

[vts]

Currently working on further improvements. With the currently-submitted patch (selection_bbox_26sep11.patch), there is still an issue where prop points are calculated incorrectly for skeletal models, and where the selection boxes are sometimes offset from the actual model. I have the first issue fixed locally, now working on the second.

[vts]

Both issues are now fixed. As a result, this patch will also fix #810. Trees remain an issue however; simply ignoring submodels for them will not do as they are sometimes composed of a single large model. Hence, the plan is to insert artificial cylinder selection boxes around the tree trunks and disregard its bounding box entirely for selection purposes.

[vts]

Alright, so here it is. This patch implements quite a few things:

1. Of course, selection hittesting is now performed against rotated selection boxes rather than fixed-axis bounding boxes.
2. By default, selection boxes are calculated starting from a model's object bounds, and recursively adding the bounds of its props (thus also fixing #295 and #810). However, this can be overridden by specifying an optional <SelectionShape /> entry in the template's VisualActor component, which can be one of:

• <SelectionShape type="bounds" />
  This is the default behaviour. It doesn't need to be explicitly declared; it is assumed you mean this if omitted.
• <SelectionShape type="footprint" />
  This uses the information from the Footprint component (if any) to construct a selection box around the object.
• <SelectionShape type="box" width=".." height=".." depth=".." />
  Allows for an entirely custom selection shape for an entity
  
  Specifically, this is used to set custom-shaped selection boxes for trees, which are known to otherwise create massive bounding boxes that disrupt selection. Currently, the selection boxes for trees are set to equal their footprint.

3. It adds a button to Atlas' ActorViewer to inspect the selection box of the viewed entity, as well as a button to display an RGB axes marker arrow (which I'm sure you're familiar with from any 3D modelling package). I used these while debugging, and thought they might come in useful.

4. It adds an option to the developer overlay menu to display outlines of the regular bounding boxes (in red) and the new and improved selection boxes (in green). These are useful when debugging issues with selecting units, or simply to inspect a unit's selection box.

5. Some helper code was added to render gimbals at arbitrary 3D locations, which I used to debug prop point transforms in the actor viewer by rendering very small point gimbals at the prop points. I've not included that code for Atlas in this patch, but I intend to in a future patch that builds on this one. This could arguably be taken out of this patch and moved into a separate one -- I leave that up to the discretion of the reviewer.

6. It adds a lot of documentation about the way the bounds, models and prop points work together, hopefully making it clearer to the next programmer to figure out what's going on.

Future improvement possibilities:

1. To further improve the selection behaviour, it might be nice to allow hittesting against the compound bounding box first, and then continue hittesting against individual submodels. This could help reduce "air selections", where the user's cursor is over the ground but still intersecting some model's bounds, causing a somewhat unexpected selection. However, this is definitely not the case for all models, and it's unclear at this time how worthwhile any effort towards this might be.

2. Currently, the selection works by enumerating all entities with the Selectable component, and hittesting each one individually. This is a rather brute-force-y solution; it'd be nice to have a faster method for these kinds of spatial queries that will directly return the models that are intersected by a ray instead of enumerating and testing.

3. The mechanism by which footprint data is made available to the models is kind of cumbersome; it copies footprint data and stores it in a potentially large amount of unit model instances, and it adds an order dependency between component initialization. A more elegant method might be nice, while at the same time taking care to preserve memory. It was unclear to me at the time of writing what the best approach is.

That's about it off the top of my head. If I think of any others, I'll update this ticket for reference.

[vts]

Updated version of the selection box patch (7 oct '11)

[Erik Johansson]

Sounds great, hopefully Philip should have time to review this soon :) Are a bunch of great additions/improvements you've added :)

[historic_bruno]

Here's what I noticed after applying the patch and testing:

• It looks great! Building selection especially is much more intuitive.
• Tree selection is improved simply by having smaller selection boxes. For instance, I could select almost any individual tree in a forest. But it would be even better if they could be tied to actors somehow, to allow for different variations. The same issue could appear with any entity comprising actors that have a wide variety of shapes and sizes. It doesn't sound easy to fix this in practice, however...
• There's some weirdness with the bounding box overlay (developer menu). Trying the Oasis II map and selecting a female, it won't update the overlay as expected when hovering other entities. Discussed this with vts in IRC and he has a fix for this (something to do with handling the rendering order). The idea is to leave that as a separate patch/ticket.
• The Celt Trader can now be selected in game but not in Atlas, so apparently all changes from this patch do not apply equally well in Atlas. That should be fixed but perhaps as a separate ticket.
• It would be nice to also view prop points in Actor Viewer, apparently the code for this is included in the patch but not the UI bits. This would be very useful for troubleshooting props and COLLADA issues :) Can also be a separate patch if it would make this one yuckier.
• Building selection boxes increase in height when the garrisoning flag is raised. I know this is "proper" with the new recursive bounds calculation, but it seems a little less than ideal, because no one will try to select the garrison flag in practice. Then again it may not be a serious issue to lose this amount of vertical space (I think it is most annoying when clicking behind a building with lower camera angles). The only solution I could think of would be a special tag somewhere in the entity template like <RecursiveSelectionBounds/>, which could be disabled when we know it's undesired, as on a civil centre. If we make flags or other props even taller then it will become more problematic.
• Boat selection has always been awful, and it's a bit improved with this patch, but not as drastically as it could be. There's a lot of empty selectable space around boats because they have tall skinny masts. I don't think people want to select a mast/sail, generally, so it would be no huge loss if we cut that off, if possible. That's just my opinion though.

[vts]

Replying to historic_bruno:

Thanks for testing, much appreciated :)

Tree selection is improved simply by having smaller selection boxes. For instance, I could select almost any individual tree in a forest. But it would be even better if they could be tied to actors somehow, to allow for different variations. The same issue could appear with any entity comprising actors that have a wide variety of shapes and sizes. It doesn't sound easy to fix this in practice, however...

Indeed; this requires the ability to define custom selection shapes at the actor level instead of at the entity level. There's one case where the custom tree box issue is especially evident, with the model of the fallen-over palm tree. With a custom selection box definition at the entity-level, its selection box will be for a standing-up model and hence completely wrong for the fallen-down model. (Note that this is only the case if a custom one is defined -- the standard box will be computed using the actual model).

Fixing this would be a huge patch in and of itself I think, and it's probably best not to attempt to mix it in with this one so that we don't end up with a single monsterpatch for Philip to review :P

The Celt Trader can now be selected in game but not in Atlas, so apparently all changes from this patch do not apply equally well in Atlas. That should be fixed but perhaps as a separate ticket.

I'm not sure what's causing this, will have to investigate what's causing the difference in behaviour.

Building selection boxes increase in height when the garrisoning flag is raised. I know this is "proper" with the new recursive bounds calculation, but it seems a little less than ideal, because no one will try to select the garrison flag in practice. Then again it may not be a serious issue to lose this amount of vertical space (I think it is most annoying when clicking behind a building with lower camera angles). The only solution I could think of would be a special tag somewhere in the entity template like <RecursiveSelectionBounds/>, which could be disabled when we know it's undesired, as on a civil centre. If we make flags or other props even taller then it will become more problematic.

Boat selection has always been awful, and it's a bit improved with this patch, but not as drastically as it could be. There's a lot of empty selectable space around boats because they have tall skinny masts. I don't think people want to select a mast/sail, generally, so it would be no huge loss if we cut that off, if possible. That's just my opinion though.

This can be achieved to a certain extent by specifying a custom selection box size using a <SelectionShape type="box" /> XML element in the entity description. This should be fine if it is known in advance that the selection box can stay at a fixed size; it won't account for changes in the actual model hierarchy or size, e.g. adding or removing props, or animations. The disadvantage is that it requires you to explicitly set the dimension in XML instead of having the engine autocalculate it from the model mesh and animations.

If there are cases where the selection box both needs to resize dynamically in response to added/removed props but should still selectively include/exclude certain props, we'd need a way to specify exactly which props are to be included/excluded. But if we're heading in that direction, and keeping in mind that we might already need to define selection shapes at the actor level, it sounds like the real issue is a need to rethink the selection box model thoroughly before making any large changes to the current model.

[Philip Taylor]

(Oops, didn't see historic_bruno's comments or the IRC discussion before writing this. Hopefully not too much duplication.)

Looks good, and documentation is nice :-)

ModelAbstract.cpp

• CalcSelectionBox: need some breaks in the switch.
• CalcSelectionBox: should use debug_warn instead of LOGWARNING for the default case, since it's an engine bug if that code ever runs. (The general idea is that engine bugs should be reported noisily (with debug_warn) and fixed by engine developers, since they might lead to arbitrarily wrong behaviour or out-of-syncs or crashes when the user continues past them. Errors/warnings that modders could trigger through invalid data files ought to generally be LOGERROR/LOGWARNING instead, and the engine should cope gracefully and continue running safely.)
• Spurious "//objBounds[0].Y = 0;"

ModelAbstract.h

• Constructor doesn't need to do SetEmpty since the default CBox constructor already does that.
• Destructor doesn't need to do "if" (it's always safe to do "delete NULL").
• "///< Type of shape. @see ESource" - there is no ESource. (If it's meant to be EType, I think Doxygen should autolinkify variable types so it shouldn't be necessary.)

Bound.cpp

• sideU = corner1 - corner0
        = T*(maxX,minY,minZ) - T*(minX,minY,minZ)
        = T*(maxX-minX,0,0)
  

so I think you could simplify the code by just applying the transform to (maxX-minX,0,0) and (0,maxY-minY,0) and (0,0,maxZ-minZ) to compute the new lengths and basis vectors, instead of worrying about all the corners and the non-trivial numbering.

Box.h

• CBox vs CBound doesn't seem to give a clear indication of their differences. Maybe it would be worth renaming them both, if there are better names? (CAABBox/COBBox, CBoundAA/CBoundO, CBoundAligned/CBoundOriented, or something, but those may be rubbish names.)
• Constructor comment refers to non-existent hU etc.
• "centered at @p centered" - should be "center".
• "returns the positive distances from the origin of the ray to the entry and exit points" - I don't think it's positive. If the ray originates inside the box, and (e.g.) dir is along the X axis, then t1 will be <0 and t2 will be >0, and tMin/tMax will be set to those values, so tMin will be negative when it returns true.
• Probably worth documenting that it counts as an intersection if the origin is inside the box.
• Same probably applies to documentation of CBound::RayIntersect.
• IsEmpty: would be cleaner to say "m_Center == CVector3D() && ..." etc.
• "#endif INCLUDED_BOX" needs to be "#endif // INCLUDED_BOX".

ICmpSelectable.h

• ms_EnableDebugOverlays is slightly yucky design, since global state is generally yucky and it breaks the usual pattern of interfaces being purely virtual methods. But I can't think of a better way to do it currently, so I think it's fine to leave it. (Might be nice to change the component system in the future to better support per-component-type data and methods.)

CCmpSelectable.cpp

• Since the SOverlayLines are static, and Submit just stores a pointer to the object, won't this break if multiple entities try to render overlays? (like it'll only render the last one, but will render it multiple times)
• In the schema, I think you want <attribute name='type'><value>box</value></attribute> etc (not <text/>) to constrain the values fully. But actually it might be nice to be consistent with the Footprint schema, with the type being encoded as an element name rather than as an attribute value - I think having attributes depend on other attributes is a bit more confusing (and less common in XML languages) than depending on the element.
• Probably better to make the SelectionShape non-optional, so the default will be explicit in the data files, for the same reasons I think I suggested elsewhere. (CCmpTemplateManager might need updating in that case to avoid validation errors, though.)
• In the LOGWARNING cases, it looks like shapeDescriptor will be used without being initialised, so it will contain garbage data. Ought to cope gracefully with that kind of error. (Also, it probably should be LOGERROR instead of LOGWARNING, because it indicates a bug in the data.)

[vts]

(In [10593]) Better selection boxes. Closes #914, #295, #810.

[vts]

Implemented in [10593]. Per Philip's suggestion, the XML schema has been slightly modified to better match the Footprint component. The <SelectionShape> options are now:

• <Bounds />: This is the default behaviour; it constructs the selection box by taking the bounds of the models and submodels, excluding decals (gravel, sand, ..) and particle emitters (fire, smoke, etc). It doesn't need to be explicitly declared; it is assumed you mean this if omitted.
  
  
• <Footprint />: Creates a selection box from the information in the Footprint component. The footprint shape dictates the selection box shape. These are currently used to override the tree bounding boxes (which can be huge), and also to get a workable bounding box for entities consisting only of decals (see #1030).
  
  
• <Box width=".." height=".." depth=".." />: Constructs a selection box of custom size.
  
  
• <Cylinder radius=".." height=".." />: Accepted as an option, but currently unimplemented; intended to be implemented in subsequent commits. Will generate warnings if used while not implemented.

Note that any of the options other than <Bounds /> will not account for changes in the model due to animations (e.g. spearman movement) and the addition or removal of props (e.g. garrison flags); in other words, they'll remain the same size at all times.

The <SelecionShape /> XML element is still optional currently, because I did not fully understand what Philip meant with the remark about CCmpTemplateManager. Because this patch seemed eagerly anticipated, I decided to go ahead and commit it while it's still optional, and change it in a later commit. Same goes for the transformation optimization in CBound.cpp; this requires verifying that nothing broke, which may take some time. Hence, for the same reason, I've decided to leave this for another commit.

Also, it's worth noting that CBound and CBox have now been renamed to CBoundingBoxAligned and CBoundingBoxOriented to better reflect the difference between them and their individual purpose.