# Christer Ericson

Member

375

840 Good

• Rank
Member
1. ## Plane equation, + or - D

mathematical, Dirk already gave a good answer to your question, but I wanted to stress that it is a good idea to try to work "coordinate free." I.e. where possible, avoid formulas that expose the x, y, z coordinates, like the above "plane equation" does. Instead, like Dirk said (and as I also discuss in my book), it's better to consider planes as being defined by the set of vectors that are perpendicular to the plane normal, and that have an "origin" defined by any point on the plane.   In other words, let N be the plane normal, let P be any point on the plane, and let X be all other points on the plane. Then we can express this relationship as:   Dot(N, X - P) = 0.   I.e. the vectors N and X - P need to be perpendicular.   You can expand that expression in two ways:   Dot(N, X - P) = Dot(N, X) - Dot(N, P) = ... = n.x * x.x + n.y * x.y + n.z * x.z - d or Dot(N, X - P) = Dot(N, X) + Dot(N, -P) = ... = n.x * x.x + n.y * x.y + n.z * x.z + d   Which is why you see the expanded explicit-coordinate plane equation sometimes with '-' and sometimes with '+'. Both are correct, and the difference is just that the 'd' constant is negated between the two expressions.   Hope that helps.
2. ## Need Explanation With Distance Between Two Segments

All of this is explained in section 5.1.9 of my book. The code uses the notation that the text uses, and the text contains both explanations and derivations of the math, that is then expressed in code. The expression (b*f - c*e) / denom is solving an equation, to determine where on the segments the closest points lie. In order to understand it, you need to invest time into understanding the math behind it (said math also being explained in the book).   The Chapter 3 math primer is there to help provide some math background, but is fundamentally not a replacement for the study of a proper elementary linear algebra (ELA) textbook. I described Cramer's rule for solving systems of linear equations because it is -- relatively -- very easy to describe and understand. The Gaussian elimination algorithm I deemed would take too much space and time to go through, and people would be better off looking it up online or consulting an ELA textbook. It's really not that hard though, I recommend looking it up!   I caveat all of this on pages 5-6. E.g. "To turn the presented code into real production code, some additions may be necessary. For example, tests for division by zero are not always performed to avoid going into details that would hamper the understanding of the overall approach. Similarly, some code tests may require tolerance values to be added for full robustness."   The code samples aren't intended to be used as-is, but as a starting point for someone to write their own version, that matches their own needs.     Again, see pages 5-6 that clarify this. Notably the reference to the reader to apply the practices of Chapter 11 to the code samples, if they want production-ready code.
3. ## Per pixel point light: interpolating vertex world pos

[quote name='MJP' timestamp='1324752019' post='4897124'] You will get the same results by interpolating the positing and then computing the light direction in the pixel shader...this is because vertex positions can be linearly interpolated. So you don't have anything to worry about. [/quote] I don't think you meant to say "same results", Matt. Interpolating the vertex positions and computing a light direction in the pixel shader will not give the same result as computing a light direction at each vertex and interpolating these vectors over the triangle. The former is correct while the latter is incorrect, in the sense of the resulting vector accurately pointing at the light source. You might say "similar results" in that interpolating the direction vectors isn't grossly inaccurate (for some definition of grossly).
4. ## Does anyone know how to prove this algorithm for Collision Detection

[quote name='legionalways' timestamp='1324367518' post='4895621'] So my Question is : How can I get the Mathematical proof? [/quote] You prove the separating axis test by a) looking at how many ways the two convex objects can come into contact, and then b) making sure you have tested for separating for all those possibilities. If, after you have performed all those tests, you have not found the objects separated, you must conclude they are intersecting. For two convex polygons in 2D, you will find that the polygons can come into contact with their vertices and along their edges, and that it is sufficient to test separation with planes that are parallel to the edges of the polygons (or, equivalently, along axes that are parallel with the edge normals). This means you perform at most M + N separating axis tests for a 2D intersection test of a convex M-gon and a convex N-gon.
5. ## Fixed Point Arithmetic in architectures wit FPU

Dave, that's not how I interpreted alvaro's statement. I think he's aware of the guarantees of IEEE-754. A real problem is that with floating-point you can well get different outcomes for the same configuration centered at (0,0) versus at (100000, 100000) for simple problems like "is point P left of line segment AB". With fixed-point you would get consistent answers, i.e. "reproducibility of results".
6. ## Fast Unique Vertex Determination

I wouldn't recommend sorting and pruning. The most elegant solution (which also happens to be the most efficient solution) is to insert the vertices one by one into a spatial hash table and remove duplicates as they are encountered. Basically what sebbit suggested, except properly detecting duplicates with respect to a floating-point comparison threshold. For detail, see: http://groups.google.com/group/comp.games.development.programming.algorithms/msg/d6d2a2b98209e013 If that's not enough detail, you can also see Chapter 12.1 of my book for a lengthy elaboration.

8. ## Detrmine if two segments on the same line overlaps

Quote:Original post by gianis6 I am developing a game in Actionscript 3, and I'd like to know if two segments, which lie on the same line, overlap.If you know they are on the same line, then the segments overlap iff the AABBs of the segments overlap.
9. ## Morphological Antialiasing

Quote:Original post by EsorU "Metro 2033" call it "Analytical Antialising" Analytical AA resolves coverage mathematically, without resorting to sampling. No game does analytical antialiasing, so whoever is making that claim doesn't know what they're talking about.
10. ## Realtime Collision Detection code producing wrong intersection result for 3 planes.

Quote:Original post by iMalc I don't think you can call it the wrong way of thinking about it. It's just a different way of thinking about it.I'm saying it's the wrong way, because -- as should be obvious from this very thread -- thinking about planes that way does not lead to proper understanding. You are not helping.
11. ## Realtime Collision Detection code producing wrong intersection result for 3 planes.

Quote:Original post by Spa8nky A plane is defined as a normal and a distance along that normal D.That's really the wrong way to think about planes. A better way is to see the plane as defined by a normal N to the plane and a point P on the plane. All points X on the plane then satisfy the equation Dot(N, X - P) = 0. This is saying that for a point X to lie in the plane, the vector PX must be perpendicular to N. This way of looking at planes provides an intuitive, geometric understanding. Quote:If in both cases the plane normals and D values are the same then they can not be defined differently in context of the calculation.Now take the equation Dot(N, X - P) = 0 again. The dot product is a linear operator so the equation is equivalent to Dot(N, X) - Dot(N, P) = 0. We can decide to write this expression in one of two ways:Dot(N, X) - A = 0, for A = Dot(N, P) Dot(N, X) + A = 0, for A = -Dot(N, P) While both can be used, the former is the superior choice for two reasons:In the former A is the projected distance of P along N (in units of N). In the latter A is the projected negative distance of P along N (in units of N). Do you usually think in terms of negative distances? No, didn't think so. The second way introduces a superfluous negation. How ugly! Note also how I explicitly stated "in units of N". That's important. Dot(N, P) only describes the projected distance of P along N when N is a unit vector. If N has e.g. ||N|| = 2, then the "distance" will be twice the actual/expected distance. So, in summary:Think of the plane equation as Dot(N, X - P) = 0. When you think of a plane as a 4-vector <N,d> it makes infinitely more sense to compute d as d = Dot(N, P) and not as d = -Dot(N, P). All of this is mentioned in my book BTW. Except the explicit belittling of d = -Dot(N, P)! ;)
12. ## Realtime Collision Detection Code

Just about every line of this code is explained in detail in the book, across several pages.
13. ## Real time collision detection book and Eberly

Quote:Original post by Spa8nky Christer's book, although a fantastic read and a comprehensive tome, missed out on a few elements such as your moving OBB and Triangle collision algorithm.Actually, section 5.5.2 for the moving separation axis test does cover moving OBB-triangle collision. In fact, the moving separation axis test handles continuous collision for any convex polyhedron against any other convex polyhedron, though realistically you want the polyhedra to be of limited complexity as the number of axes to test are O(e^2) in the number of polyhedra edges. In hindsight I wish I had expanded this section more, but it really is a very trivial extension of the separating axis test and it does handle just about any test you may want. The moving separating axis test is a superset (and a correction) of Dave's old article for a moving OBB vs. triangle test.
14. ## The Myth About STL

Quote:Original post by phantom The fact that people dismiss a MAJOR part of the language they claim to know for some voodoo reason with no founding in logic or reason and then continue to claim to know the language baffles the hell out of me. To say it's dumb doesnt even begin to cover it and it seems to be something which is purely in the realm of C++ users as other language users embrace their standard library with no fears. Frankly, I consider these people bad programmers and I hope to god I never have to work with anyone like that. Hell, if I was your lead and I caught you reinventing things then we'd be having words. Serious words. And if you didn't change well, chances are your contract wouldn't come up for renewal. I have no time for NIH syndrome and vague justifications, the kind which belong in a church and not in what should be an engineering and scientific discipline. Want to believe your code is better? FO and go become a priest; which should be dealing in hard facts, not hand wavy bullshit. And frankly, end of the day, most of those who abandon the language constructs only have hand wavy bullshit feelings to back up what they are saying.It saddens me that you are a moderator on these forums.
15. ## AI for mancala game

Quote:Original post by Mahfuzur Rahman How can I make a invincible computer mancala player? What are the properties that should be used as good evalution functions?Standard competitive tree search algorithms like minimax apply. The most commonly implemented variant of minimax is alpha-beta pruning; you should start there.