Sign in to follow this  
UnrealSolo

collision using planes in Binary tree

Recommended Posts

Hi, I came accros a quick way of doing polygon tests wich used binary tree containing the plane perpendicular to the polygon for each side, the result is a very quick test usualy excluding most points within a few Dot operations, (although at the expense of some memory and pre calculation) this works very well and ive extended it to solid models. although it is very fast it does not seem to work for some of my complex models - a simple test of the testing the center of each face sometimes fails to find the point inside or on the edge, and sometimes a point is found to be inside yet fails the simple bounds test. this doesnt happen with my simple test data, but some of the real models have convex angles, but I have reasoned it should work with convex models. before I spend ages examing the code and the complex models to see wich is wrong, id thought id check to make sure this technique is realy viable or if there are any pitfalls? out of about 50k real life models it fails consistently on about 20 of them, but they are very complex, so trying to trace the route through the tree by hand is a nightmare. basically the idea is this, to build the tree :- pick one surface as the root, then test all the other surfaces for being above or below (wich equals inside or outside depending on the type of model) placing them in the relevant branch , and continue untill all branches are empty. when testing simply test the point to see if it is above or below the root and follow the apropriate branch and subsequent nodes until it finds an empty branch. the result of the last test gives the final result. if there are small holes in the model it should cope with them, as long as the surfaces are converging quickly at the hole it will be effectiivly closed off within a short distance. if they are diverging wich is unlikly it will fail - ie such as an open top polystyrene cup. the code is quite long so before i could post it i would need to spend a while cutting it down to size as I added a fair bit of code to cope with small rounding errors wich removed some trivial errors close up, and to optimize the choice of the root node etc, coplaner surfaces, plus also handling points on edge situations. thanks Solo.

Share this post


Link to post
Share on other sites
update:-
ive found that if a plane divides a model such that a surface edge is very close to the plane, theres a small chance that the two adjoining surfaces might not both end up on the same branch.

to avoid this ive added a 4th state to my test for above or below, or inbetween, now ive got an unsure wich is where one edge sits close to the plane. I put those planes wich apear as unsure at the top of the tree. it works better however still some erros remain.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this