Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Incorrect size bounds checks in vehicle viewport hash scan in ViewportAddVehicles #6618

Open
DorpsGek opened this issue Aug 31, 2017 · 3 comments
Labels

Comments

@DorpsGek
Copy link

@DorpsGek DorpsGek commented Aug 31, 2017

JGR opened the ticket and wrote:

In ViewportAddVehicles in src/vehicle.cpp there are bounds checks:

if (dpi->width + (70 * ZOOM_LVL_BASE) < (1 << (7 + 6 + ZOOM_LVL_SHIFT))) {
if (dpi->height + (70 * ZOOM_LVL_BASE) < (1 << (6 + 6 + ZOOM_LVL_SHIFT))) {

These are to prevent the extent of the untruncated span from xl to xu and yl to yu from being unable to fit in the hash bit allocation (6 bits each).

In the case of width, in the case where the lower 9 bits of (l - (70 * ZOOM_LVL_BASE)) are greater than the lower 9 bits of r,
dpi->width + (70 * ZOOM_LVL_BASE) can be less than (1 << (7 + 6 + ZOOM_LVL_SHIFT)) even when the the untruncated hash values differ by 0x40, such that the truncated values are the same.
This has the effect that if the viewport re-draw area is the right size and offset, the iteration over the vehicle viewport hash only finds vehicles at the two edges but not in the middle.
This can visually manifest as flickering effects.

To give a concrete example:
Noting that: ZOOM_LVL_BASE = 4, ZOOM_LVL_SHIFT = 2
If: dpi->left = 0x317, dpi->width = 0x7CE9
Then:
dpi->width + (70 * ZOOM_LVL_BASE) = 0x7E01
(1 << (7 + 6 + ZOOM_LVL_SHIFT)) = 0x8000
dpi->width + (70 * ZOOM_LVL_BASE) < (1 << (7 + 6 + ZOOM_LVL_SHIFT)) evaluates to true
l - (70 * ZOOM_LVL_BASE) = 0x1FF, r = 0x8000
xl = 0, xu = 0
Consequently: only vehicles in hash row 0 will be drawn, even though the viewport redraw covers the whole width of the viewport hash

A possible solution for width/x would be to perform the bounds check after doing the shift-right by 9, but before truncating to 6 bits.

Height/y is the same except the shift is by 8 instead of 9.

Reported version: trunk
Operating system: All


This issue was imported from FlySpray: https://bugs.openttd.org/task/6618
@stale

This comment has been minimized.

Copy link

@stale stale bot commented Mar 25, 2019

This issue has been automatically marked as stale because it has not had any activity in the last two months.
If you believe the issue is still relevant, please test on the latest nightly and report back.
It will be closed if no further activity occurs within 7 days.
Thank you for your contributions.

@stale stale bot added the stale label Mar 25, 2019
@LordAro

This comment has been minimized.

Copy link
Member

@LordAro LordAro commented Mar 25, 2019

@JGRennison Is this something you'd care to PR?

@stale stale bot removed the stale label Mar 25, 2019
@JGRennison

This comment has been minimized.

Copy link
Contributor

@JGRennison JGRennison commented Mar 27, 2019

I'll see what I can do.

For reference the commit in my fork is JGRennison/OpenTTD-patches@d3a1e80

JGRennison added a commit to JGRennison/Upstream-OpenTTD that referenced this issue Apr 5, 2019
Fix incorrect bounds check in ViewportAddVehicles in the case where the
viewport width or height is less than the hash wraparound
distance, however the two bounds still map to the same hash bucket
due to discarding the lower coordinate bits, such that the intermediary
hash buckets are incorrectly not iterated.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
6 participants
You can’t perform that action at this time.