Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

279 Neutral

About l0k0

  • Rank
  1. l0k0


    Linear Algebra
  2. 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.
  3. 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.
  4. l0k0

    Circle vs Line Segment collision

    Hi 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.
  5. l0k0

    Circle vs Line Segment collision

    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; }
  6. I have a blog post about a message passing system in a component-entity world that I wrote here: http://afloatingpoint.blogspot.com/2012/09/gameplay-architecture-part-2-message.html.  I'm not sure if I would call it simple (warning: custom memory allocation), but it definitely gets the job done when it comes to sending custom messages now and queuing them for later.  The short version is that I used a sorted heap, a map of message types to listeners, and a pool allocator.
  7. It might be easier to think of it this way:     Vector2 vertices[] =  {        Vector2(-1.0f, -1.0f),  // Index 0        Vector2(1.0f, -1.0f),   // Index 1        Vector2(-1.0f,  1.0f),  // Index 2        Vector2(1.0f,  1.0f),   // Index 3 };     Triangle indices[] =  {      Triangle(0, 3, 1),  // Bottom left to top right to bottom right triangle      Triangle(0, 2, 3),  // Bottom left to top left to top right triangle };   Each index is referencing a point on the quad.  You are ultimately drawing 2 triangles to achieve this.  For quads, index buffers don't help all that much, but for something like a cube the amount of data sent to the gpu can get a lot smaller (especially when encoding more than just positions in the vertices) when using index buffers of 16 bit offsets instead of 3 whole floats again.   Open GL takes things as flat arrays of floats and integral types.  As such, you have to think of the indices and vertices as groups inside these arrays.  Does that make more sense?
  8. l0k0

    Matrix LookAt problem

    The view matrix transforms from world to screen space.  It is the inverse of the camera's world matrix.     We know that the inverse of a rotation matrix is its transpose.  Since what you are calculating is the view matrix, you need to transpose the upper 3x3 portion of the matrix to get the desired result.  Notice if you do that with your results, that you get the same thing as the library's matrix (don't just negate that's silly).  You can either transpose the matrix after setting the 3 columns or just set it directly.   What you are doing now is right for the translation, but is giving the world space rotation (when really we want its inverse).  Use your left hand given your input, have it point from the "eye" to the "at".  Hopefully it then becomes clear how the properly calculated view matrix is undoing that transformation.
  9. l0k0

    Trouble implementing SAT collision

    I would test the intersection code in isolation.  Debug draw the returned normal and depth and if they are intersecting.  If that seems accurate, it is probably an issue with the response code.  Also, post some more of the response code here.  What you have there isn't really telling us much.  Got to see the nitty gritty math to help determine what's wrong.
  10. l0k0

    Trouble implementing SAT collision

    I'd do it like this:       void GetProjectionOnAxis(const Vector2 * pVertices, const int N, const Vector2& axisN, float &projMin, float &projMax) {     projMin = projMax = Dot(pVertices[0], axisN); // axisN assumed to be normalized     for (int i = 1; i < N; ++i) {         projMin = Min(projMin, pVertices[i]);         projMax = Max(projMax, pVertices[i]);     } }  float GetOverlapOnAxis(const float projMinA, const float projMaxA, const float projMinB, const float projMaxB) {     float minP = Min(projMinA, projMinB);     float maxP = Max(projMaxA, projMaxB);     float overlap = maxP - minP;    // negative if no intersection     return overlap; } struct SATResult {     Vector2 m_normal;     float m_depth;     bool m_intersect; }; bool TestPolygonPolygonSAT(const Vector2 * pVerts0, const int n0, const Vector2 * pVerts1, const int n1, SATResult& satOut) {     jlVector2 edge, edgePerp, edgePerpN;     float min0, max0, min1, max1;     float overlap, minOverlap = -F32_MAX;     jlVector4 minNormal;     satOut.m_intersect = false;      int j, i;     for (j = n0 - 1, i = 0; i < n0; j = i, ++i) {         // compute our orthogonal axis for each edge         edge = pVerts0[i] - pVerts0[j];         edgePerp = RightPerp(edge); // y, -x         edgePerpN = Normalize(edgePerp);         // get min/max projection on each axis         GetProjectionOnAxis(verts0, n0, edgePerpN, min0, max0);         GetProjectionOnAxis(verts1, n1, edgePerpN, min1, max1);         // if no overlap, no intersection         overlap = jlOverlapOnAxis(min0, max0, min1, max1);         // otherwise store minimum overlap value and the normal         if (overlap < 0.0f) {             return false; // have to intersect on every tested axis for SAT to return true         } else if (overlap < minOverlap) {             minOverlap = overlap;             minNormal = edgePerpN;         }     }     // now do the same thing, on pVerts1 axis     for (j = n0 - 1, i = 0; i < n0; j = i, ++i) {         // compute our orthogonal axis for each edge         edge = pVerts1[i] - pVerts1[j];         edgePerp = RightPerp(edge); // y, -x         edgePerpN = Normalize(edgePerp);         // get min/max projection on each axis         GetProjectionOnAxis(verts0, n0, edgePerpN, min0, max0);         GetProjectionOnAxis(verts1, n1, edgePerpN, min1, max1);         // if no overlap, no intersection         overlap = jlOverlapOnAxis(min0, max0, min1, max1);         // otherwise store minimum overlap value and the normal         if (overlap < 0.0f) {             return false; // have to intersect on every tested axis for SAT to return true         } else if (overlap < minOverlap) {             minOverlap = overlap;             minNormal = edgePerpN;         }     }     // if we get here they are intersecting     satOut.m_normal = minNormal;     satOut.m_depth = minOverlap;     satOut.m_intersect = true;     return true; }     You would probably want to break the TestPolygonPolygonSAT into a helper function you call twice.  Also, I was lazy and just did this on the spot.  Pretty sure it is right though .
  11. This can be done much simpler.  We know that we can project a vector a onto b with (dot(a, b) / dot(b, b)) * b.  We can apply this by subtracting the point by one of the points on the line, projecting onto the line vector using the above, clamping our t value if needed, and adding to that point on the line again.  Some code for you:     // p0 and p1 define the line segment, pt is an arbitrary point in space const Vector3 ClosestPointOnSegment(const Vector3& p0, const Vector3& p1, const Vector3& pt) {     const Vector3 lineSeg = p1 - p0; // seg vec     // saturate clamps from 0 to 1, which will get us a point between p0 and p1     // if we want the closest point on the infinite line defined by both points we would      // omit the saturate     const float t = Saturate(Dot((pt - p0), lineSeg) / Dot(lineSeg, lineSeg));       return p0 + lineSeg * t; }  
  12. Some general things, most of them independent of coding style:   - Have realistic and well defined goals that are clearly communicated to members on your team - Scope it down: your game idea is probably too damn big.  Polish takes time, things get cut, features don't exist in a bubble (unless the project fails that is). - Iteration time is everything: Fail early and fail often, prototype mechanics, and be prepared to cut something you invested a considerable amount of time in - Knowledge is power: profile your code, run tools that check for leaks, crank up compiler warnings, and use static analysis tools if possible - Interfaces are king: A well designed one is the root of a clear, maintainable, and productive workflow for others.  A poor one will cut into iteration time. - Understand that hard problems will inevitably contain immensely complex code: elegant systems rarely survive contact with real users - Embrace time estimates and embrace making time estimates that might be completely wrong.  Do this over and over and over again. - "Self Documenting Code" is probably only documented to you - It's (usually) not done until it's data driven      
  13. l0k0

    Rectangle Line collision problem

    That is correct.  Edited the original mishap.
  14. l0k0

    Rectangle Line collision problem

    It would be quite the feat if you could do this without vectors so not sure what you mean by "not vector based"   To keep this simple, albeit not the most efficient, I'd first make a system of equations between the line segment and the line in normal form (for each edge of the rectangle).  Ensure the t value is within 0 to 1 for the segment.  Then, find the scalar projection onto the edge of the rectangle.  It is possible that the segment resides completely in the rectangle, which means we need a point inside rectangle test.  If either point is inside the rectangle it is a positive intersection. It would look something like this:       const Vector2 RightPerp(const Vector2& v) { return Vector2(y, -x); } bool32 TestLineSegmentLineSegment(const Vector2& a0, const Vector2& a1, const Vector2& b0, const Vector2& b1) {     const Vector2 a = a1 - a0;     const Vector2 b = b1 - b0;     const Vector2 bPerp = RightPerp(b);     const Vector2 bPerpN = Normalize(bPerp);     const float bPerpNDist = -Dot(bPerpN, b0);     // dot(pn, x) = -pd     // pt = a0 + a * t     // dot(pn, a0 + a * t) = -pd     // t = (-pd - dot(pn, a0)) / dot(pn, a)     // intersects a if t is in zero to one range     const float t = (-bPerpNDist - Dot(bPerpN, a0)) / (Dot(bPerpN, a)); if (0.0f <= t && t <= 1.0f) { // this means the segment a is being intersected between a0 and a1 const Vector2 ptOnA = a0 + a * t; // this is the point on a of the intersection // find the scalar projection of the point onto b and if it is in range they intersect const float bt = Dot(ptOnA - b0, b) / (Dot(b, b)); if (0.0f <= bt && bt <= 1.0f) { return 1; } } return 0; } bool32 TestRectanglePoint(const Vector2& min, const Vector2& max, const Vector2& pt) {     return (pt.x >= min.x && pt.y >= min.y && pt.x <= max.x && pt.y <= max.y); } bool32 TestRectangleLineSegment(const Vector2& min, const Vector2& max, const Vector2& a, const Vector2& b) {     if (TestRectanglePoint(min, max, a) || TestRectanglePoint(min, max, b)) return 1;     const Vector2 maxXMinY = Vector2(max.x, min.y);     const Vector2 minXMaxY = Vector2(min.x, max.y);     return (TestLineSegmentLineSegment(min, maxXMinY, a, b) || TestLineSegmentLineSegment(maxXMinY, max, a, b) || TestLineSegmentLineSegment(max, minXMaxY, a, b) || TestLineSegmentLineSegment(minXMaxY, min, a, b)); }    Give this a try and let me know if you have any issues.
  15. If I had to guess it seems you might be reading/writing unaligned data.    Throw in some asserts that assure the data you are reading/writing to is aligned.  You can read more about this here: http://stackoverflow.com/questions/227897/solve-the-memory-alignment-in-c-interview-question-that-stumped-me.   2 Other Notes Here: 1) Usually with pools the free list nodes are stored inside the slots in the pool themselves (sometimes as unsigned 16 bit offsets from the start of the pool to conserve space).  By that I mean there is no need for the MemChunk and the Data itself to be stored next to eachother, but rather in the same location in memory (sort of like a union).  If you think about it, if there is no data there, there is no need to have seperate space for both.  If it is in the free list, it is by definition unused. 2) Why is memchunk doubly linked?  If deallocating, just add to the head of the free list (newChunk->next = freeListHead).  And when allocating take the node at the front of the linked list.  freeListHead = freeListHead->next.  Would simplify things no?   Point number 1 above might be the source of the unaligned data in the first place. :)
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!