Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 17 Aug 2009
Offline Last Active Jan 26 2014 12:29 PM

Posts I've Made

In Topic: Math?

31 December 2013 - 12:22 AM

Linear Algebra

In Topic: homogeneous pools accessed trough pointers-> still good?

30 November 2013 - 03:58 AM

Keep it simple - is there a reason your pool can't set/unset a flag for that index as part of your alloc/dealloc functions? So when iterating through we check this flag and return null if it is set? One separate bit array will be much more memory performant than a list of pointers.

In Topic: Suggestions for memory management classes?

02 November 2013 - 02:22 PM

Some popular ones that haven't been mentioned are Page Allocators, Slab Allocators, and Paged Pool Allocators.  Another really simple one that isn't a heap replacement but is handy on the stack is Alloca.  However, it should never be used in a loop, recursive function, or with an allocation request that will blow up the stack.  Some temporary memory allocators will use a statically sized array first, then alloca, and then go to the heap if needed for "scratch" memory.  One way of going about this is described here.


If the end goal is memory performance (and it should be if you're writing allocators) I cannot agree enough with what Hodgman is saying here.  malloc is a general purpose allocator that has to fulfill allocations of all different sizes and alignments.  It also has to do something called a context switch and these are ridiculously expensive.  However, it's still primarily about cache misses at the end of the day.  


The goal should be to make fewer allocations, with tightly packed data that is accessed contiguously.  Find out what a struct of arrays is, what prefetching does and how to use it responsibly, why casting a float to an int is expensive, what the restrict keyword is, and how this also applies to instructions.  Custom memory allocators are a small slice of a much bigger problem.

In Topic: Circle vs Line Segment collision

02 October 2013 - 09:42 PM

Thanks for the great replies! I0k0, your function is the only one doing a sweep test, which was my goal. I have a couple questions on some of your values.


d - Is this the diameter of the circle?

outT - I have no idea what this is, can you explain?

Saturate() - I've read that saturation arithmetic constrains the result of any mathematical operation to a range of values. Is this what you're doing? If so, what are you constraining the values to? 0-1?


d: d is the sweep vector.  So if your swept circle has a velocity of {2, 0} for the given frame, you'd pass that vector for d.

outT: The multiplier of d that gives you the point at the center of the circle when the circle first intersects the line: X = c + d * t.  It's useful for getting a percentage of your sweep that contact was made.  It's very useful for things like raycasts.  Perhaps for your needs at a higher level just a boolean test is needed, but the way I'm doing the test you have to calculate this t value anyways.

Saturate: saturate is equivalent to Clamp(someVal, 0.0, 1.0)


Hope that helps.

In Topic: Circle vs Line Segment collision

29 September 2013 - 10:53 PM

Treat it like a circle against an infinite line first.  Validate the t value of the intersection between the circle and the infinite line is valid first [0 - 1].  Then, take the scalar projection of this intersection pt onto p0p1 and validate that the scalar projection is also valid [0 - 1].  Give this a try:

bool TestSweptCircleLine(const Vector2& c, const float r, const Vector2& d, const Vector2& p0, const Vector2& p1, float &outT) {
    Vector2 p0p1 = p1 - p0;
    // we have this annoying case first, where the circle is *already* intersecting the line segment so check for that first.  In this case, t would be 0.0f.  As for intersection points technically you have 2, but your "solver" might just want to use c
    Vector2 closestPointOnLineSegment = p0 + p0p1 * Saturate(Dot(c - p0, p0p1) / Dot(p0p1, p0p1));
    if (DistSquared(closestPointOnLineSegment, c) <= r * r)
       outT = 0.0f;
       return true;
    Vector2 p0p1Perp = RightPerp(p0p1);
    // can avoid normalisation here, but lets keep this simpler for now
    Vector2 pn = Normalise(p0p1Perp);
    float   pd = -Dot(pn, p0);
    // system of equations is:
    // dot(pn, X) = -pd +- r (X is any point that is +r or -r distance away from the infinite line)
    // c + d * t = X (t is in the 0 to 1 range inclusive, X in this case is again the center of the circle when it intersects the infinite line (not necessarily the segment))
    // using substitution and solving for T
    float distanceLineToCenterOfCircle = Dot(pn, c) + pd; // just line signed plane distance
    float signSideOfLine = Sign(distanceLineToCenterOfCircle );
    // if our sign is positive, then our system of equations is + R
    // if not our system of equations is - R
    float modR = signSideOfLine * r;
    outT = (((-pd + modR) - Dot(pn, c)) / (Dot(pn, d)));
    // now validate t and s
    if (outT >= 0.0f && outT <= 1.0f)
        // alright, our swept circle is intersecting the infinite line
        // now validate that this intersection is in the line segment
        // range too
        Vector2 ptCenterOfCircleWhenIntersecting = c + d * outT;
        Vector2 ptOnLineWhenIntersecting = ptCenterOfCircleWhenIntersecting + pn * -modR;
        // find the scalar projection of ptOnLineWhenIntersecting.  If it is between 0 and 1 inclusive we have an intersection
        float s = Dot(ptOnLineWhenIntersecting - p0, p0p1) / Dot(p0p1, p0p1);
        if (s >= 0.0f && s <= 1.0f)
            return true;
    return false;