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

graphene_box_intersection returns incorrect results #201

Closed
vanvugt opened this issue Dec 9, 2020 · 0 comments · Fixed by #202
Closed

graphene_box_intersection returns incorrect results #201

vanvugt opened this issue Dec 9, 2020 · 0 comments · Fixed by #202

Comments

@vanvugt
Copy link
Contributor

vanvugt commented Dec 9, 2020

I started trying to use graphene_box_intersection today, but found it returns true when it most definitely should return false.

This happens for non-intersecting boxes whose intersection returns a negative volume in one of the dimensions (min.[xyz] > max.[xyz]). So it's easy to work around and just ignore any intersection with higher min than max values. But of course, the function itself should ensure that never happens and returns false instead of true.

The source of the problem appears to be graphene_box_intersection's use of:

bool
(graphene_simd4f_cmp_ge) (const graphene_simd4f_t a,
                          const graphene_simd4f_t b)
{
  return a.x >= b.x &&
         a.y >= b.y &&
         a.z >= b.z &&
         a.w >= b.w;
}

Actually we need a.x >= b.x || a.y >= b.y || a.z >= b.z for correct operation of:

bool
graphene_box_intersection (const graphene_box_t *a,
                           const graphene_box_t *b,
                           graphene_box_t       *res)
{
  graphene_simd4f_t min, max;

  min = graphene_simd4f_max (a->min.value, b->min.value);
  max = graphene_simd4f_min (a->max.value, b->max.value);

  if (graphene_simd4f_cmp_ge (min, max))
    {
      if (res != NULL)
        graphene_box_init_from_box (res, graphene_box_empty ());
      
      return false;
    }
  
  if (res != NULL)
    graphene_box_init_from_simd4f (res, min, max);
  
  return true;
}
vanvugt added a commit to canonical/graphene that referenced this issue Dec 10, 2020
vanvugt added a commit to canonical/graphene that referenced this issue Dec 10, 2020
The old logic did essentially:

  (min.x >= max.x && min.y >= max.y && min.z >= max.z)

which for a pair of non-intersecting boxes that differ in only one or two
dimensions will return false when we need it to return true (meaning there
is no intersection). What we really need is:

  (min.x > max.x || min.y > max.y || min.z > max.z)

which can be rewritten as:

  !(min.x <= max.x && min.y <= max.y && min.z <= max.z)

Fixes: ebassi#201
ebassi pushed a commit that referenced this issue Dec 10, 2020
ebassi pushed a commit that referenced this issue Dec 10, 2020
The old logic did essentially:

  (min.x >= max.x && min.y >= max.y && min.z >= max.z)

which for a pair of non-intersecting boxes that differ in only one or two
dimensions will return false when we need it to return true (meaning there
is no intersection). What we really need is:

  (min.x > max.x || min.y > max.y || min.z > max.z)

which can be rewritten as:

  !(min.x <= max.x && min.y <= max.y && min.z <= max.z)

Fixes: #201
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant