Skip to main content
edited body
Source Link
Sirisian
  • 584
  • 3
  • 8

If it helps I have a similar image from helping someone with this problem a long time ago. It better illustrates the constraints (you can ignore the near plane since your example doesn't have one):

enter image description here

As you can see you're trying to figure out which corners are inside of the region. You have to make sure they're within the circle which is a distance check. Say our camera is at cameraPosition represented by an (x, y) vector then for each point you're checking just do:

if ((point.x - cameraPosition.x) * (point.x - cameraPosition.x) + (point.y - cameraPosition.y) * (point.y - cameraPosition.y) < radius * radius)

Then you need to figure out if the points are inside of the two lines (3 in my example image, but we'll just use the two long lines). To do this you can use a dot product test. Generate your two vector using (cos(angle), sin(angle)) or however best works for you. Then for the left and right ray find it's left hand normal. (y, -x) or (-y, x) depending on your coordinate system. Then for each point we'll take the dot product between the (point - cameraPosition) and the normal. This will tell us which side of the ray our point is on. If it's on the wrong side we can discard it.

normalLeftX = -sin(angle1)
normalLeftY = cos(angle1)
normalRightX = sin(angle2)
normalRightY = -cos(angle2)
pointRayX = point.x - cameraPosition.x;
pointRayY = point.y - cameraPosition.y;
if (pointRayX * normalLeftX + pointRayY * normalLeftY > 0 &&
    pointRayX * normalRightX + pointRayY * normalRightY > 0)

(You might have to flip the normals between (y, -x) and (-xy, yx) if I made a mistake).

Combining all 3 checks will test if the point is inside. When a point is inside that means all 4 adjacent tiles are inside. (I'll let someone else expand it to code if they want).

I will point out that this algorithm is very closely related to an optimal vector processing algorithm for triangle rasterization. It would be completely overkill but you can use it if you have to test large amounts of tiles.

https://software.intel.com/en-us/articles/rasterization-on-larrabee

If it helps I have a similar image from helping someone with this problem a long time ago. It better illustrates the constraints (you can ignore the near plane since your example doesn't have one):

enter image description here

As you can see you're trying to figure out which corners are inside of the region. You have to make sure they're within the circle which is a distance check. Say our camera is at cameraPosition represented by an (x, y) vector then for each point you're checking just do:

if ((point.x - cameraPosition.x) * (point.x - cameraPosition.x) + (point.y - cameraPosition.y) * (point.y - cameraPosition.y) < radius * radius)

Then you need to figure out if the points are inside of the two lines (3 in my example image, but we'll just use the two long lines). To do this you can use a dot product test. Generate your two vector using (cos(angle), sin(angle)) or however best works for you. Then for the left and right ray find it's left hand normal. (y, -x) or (-y, x) depending on your coordinate system. Then for each point we'll take the dot product between the (point - cameraPosition) and the normal. This will tell us which side of the ray our point is on. If it's on the wrong side we can discard it.

normalLeftX = -sin(angle1)
normalLeftY = cos(angle1)
normalRightX = sin(angle2)
normalRightY = -cos(angle2)
pointRayX = point.x - cameraPosition.x;
pointRayY = point.y - cameraPosition.y;
if (pointRayX * normalLeftX + pointRayY * normalLeftY > 0 &&
    pointRayX * normalRightX + pointRayY * normalRightY > 0)

(You might have to flip the normals between (y, -x) and (-x, y) if I made a mistake).

Combining all 3 checks will test if the point is inside. When a point is inside that means all 4 adjacent tiles are inside. (I'll let someone else expand it to code if they want).

I will point out that this algorithm is very closely related to an optimal vector processing algorithm for triangle rasterization. It would be completely overkill but you can use it if you have to test large amounts of tiles.

https://software.intel.com/en-us/articles/rasterization-on-larrabee

If it helps I have a similar image from helping someone with this problem a long time ago. It better illustrates the constraints (you can ignore the near plane since your example doesn't have one):

enter image description here

As you can see you're trying to figure out which corners are inside of the region. You have to make sure they're within the circle which is a distance check. Say our camera is at cameraPosition represented by an (x, y) vector then for each point you're checking just do:

if ((point.x - cameraPosition.x) * (point.x - cameraPosition.x) + (point.y - cameraPosition.y) * (point.y - cameraPosition.y) < radius * radius)

Then you need to figure out if the points are inside of the two lines (3 in my example image, but we'll just use the two long lines). To do this you can use a dot product test. Generate your two vector using (cos(angle), sin(angle)) or however best works for you. Then for the left and right ray find it's left hand normal. (y, -x) or (-y, x) depending on your coordinate system. Then for each point we'll take the dot product between the (point - cameraPosition) and the normal. This will tell us which side of the ray our point is on. If it's on the wrong side we can discard it.

normalLeftX = -sin(angle1)
normalLeftY = cos(angle1)
normalRightX = sin(angle2)
normalRightY = -cos(angle2)
pointRayX = point.x - cameraPosition.x;
pointRayY = point.y - cameraPosition.y;
if (pointRayX * normalLeftX + pointRayY * normalLeftY > 0 &&
    pointRayX * normalRightX + pointRayY * normalRightY > 0)

(You might have to flip the normals between (y, -x) and (-y, x) if I made a mistake).

Combining all 3 checks will test if the point is inside. When a point is inside that means all 4 adjacent tiles are inside. (I'll let someone else expand it to code if they want).

I will point out that this algorithm is very closely related to an optimal vector processing algorithm for triangle rasterization. It would be completely overkill but you can use it if you have to test large amounts of tiles.

https://software.intel.com/en-us/articles/rasterization-on-larrabee

Source Link
Sirisian
  • 584
  • 3
  • 8

If it helps I have a similar image from helping someone with this problem a long time ago. It better illustrates the constraints (you can ignore the near plane since your example doesn't have one):

enter image description here

As you can see you're trying to figure out which corners are inside of the region. You have to make sure they're within the circle which is a distance check. Say our camera is at cameraPosition represented by an (x, y) vector then for each point you're checking just do:

if ((point.x - cameraPosition.x) * (point.x - cameraPosition.x) + (point.y - cameraPosition.y) * (point.y - cameraPosition.y) < radius * radius)

Then you need to figure out if the points are inside of the two lines (3 in my example image, but we'll just use the two long lines). To do this you can use a dot product test. Generate your two vector using (cos(angle), sin(angle)) or however best works for you. Then for the left and right ray find it's left hand normal. (y, -x) or (-y, x) depending on your coordinate system. Then for each point we'll take the dot product between the (point - cameraPosition) and the normal. This will tell us which side of the ray our point is on. If it's on the wrong side we can discard it.

normalLeftX = -sin(angle1)
normalLeftY = cos(angle1)
normalRightX = sin(angle2)
normalRightY = -cos(angle2)
pointRayX = point.x - cameraPosition.x;
pointRayY = point.y - cameraPosition.y;
if (pointRayX * normalLeftX + pointRayY * normalLeftY > 0 &&
    pointRayX * normalRightX + pointRayY * normalRightY > 0)

(You might have to flip the normals between (y, -x) and (-x, y) if I made a mistake).

Combining all 3 checks will test if the point is inside. When a point is inside that means all 4 adjacent tiles are inside. (I'll let someone else expand it to code if they want).

I will point out that this algorithm is very closely related to an optimal vector processing algorithm for triangle rasterization. It would be completely overkill but you can use it if you have to test large amounts of tiles.

https://software.intel.com/en-us/articles/rasterization-on-larrabee