Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 04 Feb 2011
Offline Last Active Mar 27 2014 12:55 PM

#5115911 [Solved]Deferred Rendering - Point lights only half shaded?

Posted by on 10 December 2013 - 09:09 AM

Scrath that, figured it out.  I was mapping my normals incorrectly and got it fixed now!

#5115779 DX11 - Disabling depth testing?

Posted by on 09 December 2013 - 07:22 PM

All of these replies have been very helpful and solved my problem.  Thanks everyone for the help!

#4880470 Minimal Sphere from 4 points?

Posted by on 04 November 2011 - 08:21 AM

Hi everyone,

I'm working on implementing Welzl's algorithm for finding the minimal bounding sphere of a set of vertices. I'm getting some pretty huge bounding spheres though, which can't be right. I'm thinking that something must be wrong with how I'm calculating my sphere from either 3 points or from 4 points (possibly both are wrong). As far as I can tell, there's 4 different ways to build a sphere:

sphere from 1 point: Center is point, radius is 0

sphere from 2 points: Center is midpoint, radius is half distance

sphere from 3 points: I use this method:

Sphere::Sphere( Vector& p1, Vector& p2, Vector& p3 )
	Vector v23 = p2 - p3;
	Vector v13 = p1 - p3;
	Vector v12 = p1 - p2;
	Vector v21 = p2 - p1;
	Vector v31 = p3 - p1;
	Vector v32 = p3 - p2;

	float denominator = ( 2 * ( v12.CrossProduct(v23).Length() * v12.CrossProduct(v23).Length() ) );
	float alpha = ( (v23.Length() * v23.Length()) * (v12.DotProduct(v13)) ) / denominator;
	float beta  = ( (v13.Length() * v13.Length()) * (v21.DotProduct(v23)) ) / denominator;
	float gamma = ( (v12.Length() * v12.Length()) * (v31.DotProduct(v32)) ) / denominator;

	center = alpha * p1 + beta * p2 + gamma * p3;

	radius = ( v12.Length() * v23.Length() * v31.Length() ) / ( 2 * v12.CrossProduct(v23).Length() );

I've tried several methods for the 4 point sphere, here's the one that I've settled on:
4 point sphere method

Now when I expand a sphere, I take the support set (all points currently used to define the sphere, always less than 5) and the new point and test all possible permutations of the support set and the new point to find the minimal sphere. For instance, if my support set has 4 vertices then I first try all two point combinations of the support set and the new point, then all 3 point combinations and finally all 4 point combinations. I then replace/remove any necessary points from the support set and add the newpoint to the support set. I'm 99% sure that the logical flow of my algorithm is right, I believe I just have some grievous math error somewhere in my Sphere calculation routine.

Are there any better ways to calculate a minimal bounding sphere from 3 or 4 points?

Thank you.

Edit: Also, on the off chance that anyone needs to see my sphere calculation functions in order to help:

Full Sphere Calculation Functions