Point in vertex defined box algorithm?

How would I test if a point is within a 3D box that is defined by its 8 points only or by its 6 quads? (Dont have access to normal vectors)

The box is made up of triangles, but the two polygons on each side are aligned so could be considered a quad.

Answers


You can test that by forming 6 square pyramids with your point as head and 4 vertices of a each quad as base, then summing up volumes of square pyramids. If sum of volumes is equal to volume of your box, the point is in the box. If sum of volumes is greater than your box's volume, it's outside of the box (sum of volumes would never be less than box volume).

For calculating volume of each square pyramid, you can break it into two tetrahedrons where their volume could be easily calculated by a mix vector product. You can calculate volume of box with mix vector product as well.


Assuming the points have a known order, you could work out the normal vectors. There's no need to normalise them for this sort of test so the cost isn't prohibitive. If you already know it's a cuboid then you need work out only two normals as you can get the third with the cross product, then use the other points to get distances. Obviously you're cross-producting to get normals anyway, so that's more a question about what information you want to expose to whom.

If the points don't have a known order then you can probably apply a miniature version of QuickHull — starting from the initial triangle you should find either that you already have one of the real edge faces (in which case you can use that normal and find the relevant points at the other extreme of that normal plus the requirement of mutual orthogonality to get to all three normals) or that one step gives you at least two real edges, which you'll spot when their local sets of points in front go empty.


Need Your Help

How can I use date objects as tick labels for a linear axis?

javascript d3.js

I have tried using the d3 time axis and yes, this problem is resolved by using the d3 time axis but there are lots of other complications I am not able to handle. The linear axis on the other hand ...

Conchango Scrum for Team System 2008 to MSF Agile 2010

tfs2010 agile scrum tfs2008

We currently use Scrum for Team System on TFS 2008. As I'm about to start upgrading our TFS server to 2010 I'd like to also remove the need for any of the Conchango templates in favour of native a...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.