Icon Phase-Functioned Neural Networks for Character Control

 

Icon 17 Line Markov Chain

 

Icon 14 Character Random Number Generator

 

Icon Simple Two Joint IK

 

Icon Generating Icons with Pixel Sorting

 

Icon Neural Network Ambient Occlusion

 

Icon Three Short Stories about the East Coast Main Line

 

Icon The New Alphabet

 

Icon "The Color Munifni Exists"

 

Icon A Deep Learning Framework For Character Motion Synthesis and Editing

 

Icon The Halting Problem and The Moral Arbitrator

 

Icon The Witness

 

Icon Four Seasons Crisp Omelette

 

Icon At the Bottom of the Elevator

 

Icon Tracing Functions in Python

 

Icon Still Things and Moving Things

 

Icon water.cpp

 

Icon Making Poetry in Piet

 

Icon Learning Motion Manifolds with Convolutional Autoencoders

 

Icon Learning an Inverse Rig Mapping for Character Animation

 

Icon Infinity Doesn't Exist

 

Icon Polyconf

 

Icon Raleigh

 

Icon The Skagerrak

 

Icon Printing a Stack Trace with MinGW

 

Icon The Border Pines

 

Icon You could have invented Parser Combinators

 

Icon Ready for the Fight

 

Icon Earthbound

 

Icon Turing Drawings

 

Icon Lost Child Announcement

 

Icon Shelter

 

Icon Data Science, how hard can it be?

 

Icon Denki Furo

 

Icon In Defence of the Unitype

 

Icon Maya Velocity Node

 

Icon Sandy Denny

 

Icon What type of Machine is the C Preprocessor?

 

Icon Which AI is more human?

 

Icon Gone Home

 

Icon Thoughts on Japan

 

Icon Can Computers Think?

 

Icon Counting Sheep & Infinity

 

Icon How Nature Builds Computers

 

Icon Painkillers

 

Icon Correct Box Sphere Intersection

 

Icon Avoiding Shader Conditionals

 

Icon Writing Portable OpenGL

 

Icon The Only Cable Car in Ireland

 

Icon Is the C Preprocessor Turing Complete?

 

Icon The aesthetics of code

 

Icon Issues with SDL on iOS and Android

 

Icon How I learned to stop worrying and love statistics

 

Icon PyMark

 

Icon AutoC Tools

 

Icon Scripting xNormal with Python

 

Icon Six Myths About Ray Tracing

 

Icon The Web Giants Will Fall

 

Icon PyAutoC

 

Icon The Pirate Song

 

Icon Dear Esther

 

Icon Unsharp Anti Aliasing

 

Icon The First Boy

 

Icon Parallel programming isn't hard, optimisation is.

 

Icon Skyrim

 

Icon Recognizing a language is solving a problem

 

Icon Could an animal learn to program?

 

Icon RAGE

 

Icon Pure Depth SSAO

 

Icon Synchronized in Python

 

Icon 3d Printing

 

Icon Real Time Graphics is Virtual Reality

 

Icon Painting Style Renderer

 

Icon A very hard problem

 

Icon Indie Development vs Modding

 

Icon Corange

 

Icon 3ds Max PLY Exporter

 

Icon A Case for the Technical Artist

 

Icon Enums

 

Icon Scorpions have won evolution

 

Icon Dirt and Ashes

 

Icon Lazy Python

 

Icon Subdivision Modelling

 

Icon The Owl

 

Icon Mouse Traps

 

Icon Updated Art Reel

 

Icon Tech Reel

 

Icon Graphics Aren't the Enemy

 

Icon On Being A Games Artist

 

Icon The Bluebird

 

Icon Everything2

 

Icon Duck Engine

 

Icon Boarding Preview

 

Icon Sailing Preview

 

Icon Exodus Village Flyover

 

Icon Art Reel

 

Icon LOL I DREW THIS DRAGON

 

Icon One Cat Just Leads To Another

Correct Box Sphere Intersection

Created on April 2, 2013, 1:21 p.m.

Testing for intersection between a box and sphere is not as trivial as it may first seem.

I found many resources on the web explaining how to do it, but after struggling for a while I realized all of them listed an incorrect algorithm. What they stated was that you had to try for intersection against all face planes of the box. Some did mentioned briefly that this is flawed, but most didn't seem to even be aware. With a little bit of thought the reason this is incorrect becomes obvious.

Box Sphere Intersection

If you simply check for intersection with the face planes of the box you get a bunch of false positives where the planes extend past the ends of the box. While perhaps a few false positives may not be a big deal in some cases, when there are large spheres and acceleration structures such as quad trees, false positives can mean many, many more operations than usual. Actually doing the correct checks are not much more expensive and overall improve performance.

To start we need to write three tests for checking if a sphere is inside, outside or intersecting a plane. This can be done by taking the signed distance from the plane and comparing to the sphere radius.

If the distance is negative and greater than the radius we know it is inside. If the distance is positive and greater than the radius we know it is outside. Finally if the absolute distance is less than or equal to the radius we know there is an intersection.

float plane_distance(plane p, vec3 point) {
  return vec3_dot(vec3_sub(point, p.position), p.direction);
}

bool sphere_inside_plane(sphere s, plane p) {
  return -plane_distance(p, s.center) > s.radius;
}

bool sphere_outside_plane(sphere s, plane p) {
  return plane_distance(p, s.center) > s.radius;
}

bool sphere_intersects_plane(sphere s, plane p) {
  return fabs(plane_distance(p, s.center)) <= s.radius;
}

Using these we can test for if a sphere is inside, outside or intersecting a box (specified as 6 planes). The reasoning behind this representation of 6 planes is that we can use it with non axis-aligned boxes, and boxes of odd shapes such as view frustums (which was my original application). When constructing these planes it is important to ensure all the plane normals face outward.

The test for if a sphere is inside a box is easy. Just check that the sphere is inside all of the face planes.

bool sphere_inside_box(sphere s, box b) {
  
  if (!sphere_inside_plane(s, b.front))  { return false; }
  if (!sphere_inside_plane(s, b.back))   { return false; }
  if (!sphere_inside_plane(s, b.top))    { return false; }
  if (!sphere_inside_plane(s, b.bottom)) { return false; }
  if (!sphere_inside_plane(s, b.left))   { return false; }
  if (!sphere_inside_plane(s, b.right))  { return false; }
  
  return true;
  
}

The intersection test, our original goal, is a little harder. For each face we check if there is an intersection, and if there is an intersection we ensure it is within the region of the face. To do this we ensure it is inside (or at least intersecting) all the surrounding face planes.

bool sphere_intersects_box(sphere s, box b) {
  
  bool in_left   = !sphere_outside_plane(s, b.left);
  bool in_right  = !sphere_outside_plane(s, b.right);
  bool in_front  = !sphere_outside_plane(s, b.front);
  bool in_back   = !sphere_outside_plane(s, b.back);
  bool in_top    = !sphere_outside_plane(s, b.top);
  bool in_bottom = !sphere_outside_plane(s, b.bottom);
  
  if (sphere_intersects_plane(s, b.top) && 
    in_left && in_right && in_front && in_back) {
    return true;
  }
  
  if (sphere_intersects_plane(s, b.bottom) && 
    in_left && in_right && in_front && in_back) {
    return true;
  }
  
  if (sphere_intersects_plane(s, b.left) &&
    in_top && in_bottom && in_front && in_back) {
    return true;
  }
  
  if (sphere_intersects_plane(s, b.right) &&
    in_top && in_bottom && in_front && in_back) {
    return true;
  }
  
  if (sphere_intersects_plane(s, b.front) &&
    in_top && in_bottom && in_left && in_right) {
    return true;
  }
  
  if (sphere_intersects_plane(s, b.back) &&
    in_top && in_bottom && in_left && in_right) {
    return true;
  }
  
  return false;
}

Once we have these tests, checking if a box is outside is as simple as ensuring it is not inside or intersecting.

bool sphere_outside_box(sphere s, box b) {
  return !(sphere_inside_box(s, b) || sphere_intersects_box(s, b));
}

It may seem more expensive but really it is only a handful more dot products and conditionals which the compiler can hopefully optimize away nicely. I feel like capturing the logic and making it clear is more important. Hope this helps any of you who were in my situation!

github twitter rss