Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 22 Jan 2011
Offline Last Active Jan 19 2013 06:39 AM

#4853323 AABB of spotlight

Posted by on 24 August 2011 - 12:25 PM


I'm looking for documention (or code) that calculates the AABB of a spotlight (for frustum culling purpose)

(OBB calculation could also fit to my needs, since I can convert it to AABB)

Thanks :)

Spotlights are usually defined by a frustum, so I'd just form all eight points of the frustum, then run over them in a loop keeping track of the min/max coordinate in each axis and the resulting two points will bound your AABB :)

Cheers, Paul.

#4848248 Speculative contacts and AABB vs AABB

Posted by on 12 August 2011 - 09:08 AM

The distance between two AABBs can be found by expanding one AABB by the half extents of the other, and shrinking the other to a point.

Then you can use the same maths I describe in the case of circle vs AABB on this page:


The AABB which was shrunk to a point becomes a circle of 0 radius. :)

Cheers, Paul.

#4825573 Physics: how to accomplish a "Hook" - something that pulls one object...

Posted by on 20 June 2011 - 11:58 AM

If its string you want, you just want to modify the distance constraint so it only acts in one direction - that should be the only change you need to make :)

#4825146 Physics: how to accomplish a "Hook" - something that pulls one object...

Posted by on 19 June 2011 - 11:28 AM

You want a simple distance constraint - not sure what they called that in bullet since i've never used it, but its one of the simplest constraints out there so it must be in bullet somewhere :)

Cheers, Paul.

#4815951 Constraint-Based Physics

Posted by on 26 May 2011 - 02:40 AM


I'm having a go at implementing a physics engine. I understand the force-based resolution method, but I do not understand constraint-based resolution on any practical level.

I have a sense that one sets up constraints (e.g., the box can't move through the plane, and, a second box stacked above can't move through the first, etc.). This leads to a system of equations (from Lagrange Multipliers?) that one can solve with matrix algebra (or, more practically, a sparse matrix solver).

I have no practical knowledge of how this works. I've been trying to reverse engineer some Physics libraries (ODE, mostly), but it would be really great to have some practical examples to go for--and to know if this approach is even right.


If its contact constraints you're talking about, you can't use a plain matrix solver because contacts are 'inequality' constraints which must only 'push' and never pull. You *can* solve a system of pin-joints with a matrix solver, though.

For contacts you'll need to look into linear programming methods, LCP and MLCP for solving on a force/acceleration level (David Baraff is a good reference) - or you can go the impulse route and use relaxation instead which is easier in my opinion (Erin Catto is a good reference there)...

Hope that helps,

Cheers, Paul.

#4808929 Managing a list of Contacts

Posted by on 10 May 2011 - 06:49 AM

Okay that clears things up, but wouldn't you add A to B's list the first frame also? Otherwise B could never reference that it was touching A later on.

You wouldn't add A to B's list because then you'd be duplicating information - it is true that B can never know it was touching A; this may be a problem for you depending on your application, for us it was ok because we we were generally dealing with collision pairs anyway which meant we can always do the index check and look up the lower indexed object's touching list.

I was still thinking in terms of the first post but because you're looping through your own contacts to check if it already exists, instead of a list of every one that has occurred, the process is much speedier. I'd still like to keep a master list of contacts that's occurred during the frame and clear it each time, but in addition to that, I'll have objects keep record of contacts. Without a master list wouldn't you have to check every object in the contact resolver other than simply contacts?

Yes you can probably want to keep a master list of contacts which you clear every frame, we did that as well... The touching objects stuff was actually used in our broad-phase collision system as well, so it was dual purpose.

Cheers, Paul.

#4808889 Managing a list of Contacts

Posted by on 10 May 2011 - 03:16 AM

I don't think I fully understand the post, but it did lead me to link into linked lists. If linked-lists can add on without allocating it would indeed be easier to embed the contact lists within the object, cutting out a great deal of looping.

Regardless of whether I understand it, thanks for the help! This was a very useful piece of info.

Heh heh - ok, let me try and simplify by example:

Suppose in one instance, your collision system returns a pair of objects A and B in that order:

ObjectsColliding(A, B);

and inside ObjectsColliding(), you add B to A's list of touching objects...

But then, on the next frame, the collision system reports objects B and A are colliding in that ordre

ObjectsColliding(B, A);

and inside you'd look at B's list of colliding objects, find A is not there yet and add it - but you've already added B to A's list above so it gets a bit messy...

If you always add the colliding object to object with the lower *index* of any two collision pairs, this problem goes away :)

Cheers, Paul.

#4808701 Why do objects interpenetrate in this simple collision solver?

Posted by on 09 May 2011 - 02:16 PM

I've been playing with that. With 10 iterations, the spheres interpenetrate if they are stacked and moving fast enough into each other (I think). It's hard to say exactly when they are interpenetrating because we're not damping velocity after collisions with that code anymore so everything is super bouncy.

Is it problematic at all that I do integration of velocity (and gravity), and then I resolve collision with the walls, and then I resolve collision with the spheres? Should the order of that change at all?

Ahhh, its worth mentioning that my example will only work for objects with zero velocity... It was just a suggestion to help you debug why it isn't converging for you...

I always do collision first and integration last, never modify position during the collision detection, only velocity. You can keep track of a penetration vector for each object and then during integration apply this vector to the positions (accounting for time-step). This is basically Erin Cattos split impulses system :)

Cheers, Paul.

#4808674 Why do objects interpenetrate in this simple collision solver?

Posted by on 09 May 2011 - 01:12 PM

So I read through the article, (it was great by the way), however it doesn't answer the question in the OP. As far as I can tell, this code *does* resolve the collisions (by forcing the positions to move apart by an amount equal to the intersection of the objects). It should be pretty unstable (jittery) without using a method of relaxing or a threshold or speculative contacts that you described. Before I move on to something like that, I want to understand why this simulation doesn't work properly though :/

Does the code correctly resolve the collision when there are only two spheres involved?

Have you tried iterating a few times to see if it converges in the case of multiple spheres?

Cheers, Paul.

#4808636 Managing a list of Contacts

Posted by on 09 May 2011 - 11:57 AM

I'm at a point where I want to recognize events that occur with contacts, and it's creating a bit of a problem.

Normally to generate contacts I'd clear the list each frame and then refill it with current contacts found, but because I'm not keeping any data, I can't keep record of any changes that occur.

It occurred to me, that I could avoid emptying the list everytime to track changes, but that would involve:
-A loop, checking to see if the contactpair exists already, everytime I generate a contact
-Looping over the final list of contacts, and removing contacts that aren't touching

I'm on the right track with this, or is there a better way?

What I did was to create a separate data structure which persists to handle this - I created an overlap pair when two objects first touch and then remove it when they finally separate again. You can store a linked list of overlaps on each object using an index to ensure uniqueness:

Objects a and b

if (a.index < b.index)

That way you can look up the overlaps between a pair of objects really quickly. Hope that helps!

Cheers, Paul.

#4808627 Why do objects interpenetrate in this simple collision solver?

Posted by on 09 May 2011 - 11:49 AM

I describe exactly this scenario in my blog post on physics, and how to solve it:


Hope it helps!

Cheers, Paul.

#4803955 3D collisions

Posted by on 28 April 2011 - 07:29 AM

I am still confused about how ray plane intersection works for 3D objects like a missile and building or walking into a solid object.
I am needed it for a computer game but i prefer to understand the mathmatics first.
I think the issue is that I need an example with real coodinates.

Its actually pretty simple:


Its all about finding the ratio of d0 to d1 in the diagram. That ratio tells you how much of d1 there is in d0 at the time of intersection, which also tells you the exact 'time' (from 0 to 1) of the intersection point I, along the ray A->B

ratio = d0 / d1

You can find d0 and d1 using the dot product of the ray against the plane :)

Cheers, Paul.

#4803450 finding MTD with SAT

Posted by on 27 April 2011 - 02:33 AM

Ok, you really need to use a vector library - there is no hope in hell of debugging that :)

I've never liked SAT; I just cannot visualise the thing - instead I use minkowski difference... The maths is the same anyway. Have a read though my article on collision detection step by step:


Cheers, Paul.

#4800766 Continuous collision detection for rotated bodies

Posted by on 20 April 2011 - 07:55 AM

Yeah, I've read your article, but I'm true dummy and I didn't understand a half. I hope I'll dig it someday. Thanks.

I've just published a new one on collision detection which covers continuous rotating bodies:


Hope its useful! :)

Cheers, Paul.

#4796013 Advice about character controller implementation

Posted by on 08 April 2011 - 10:08 AM

Okh I guess I got it. Basically it's used to limit the impulse generated from the controller constraint?

Exactly :)