Jump to content

  • Log In with Google      Sign In   
  • Create Account

Christer Ericson

Member Since 05 Sep 2004
Offline Last Active Aug 11 2016 09:09 PM

Posts I've Made

In Topic: Plane equation, + or - D

04 August 2016 - 01:45 PM


Hi guys, quick question on the plane equation and finding if a point is on a plane or not.


Given a plane defined by a normal (ABC) and a distance from origin (D). I've read articles describing that a point is on the plane if it satisfies the plane equation:

Ax + By + Cz + D = 0

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


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.

In Topic: Need Explanation With Distance Between Two Segments

04 August 2016 - 01:29 PM


The code below is from book Real-Time Collection Detection ch5.cpp file

Some of them I don't know where it come from.


float denom = a*e-b*b;




(b*f - c*e) / denom


what does this mean?I know a is square length of d1,e is square length of d2,b is d1 projection on d2,

but what does a*e-b*b means?where this guy come from,for what reason?any rule or fomular related??

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).


I have no idea. I consider half that book "black magic". I consider it a major accomplishment any time I understand any of it. To say that it is "math intensive" is an understatement. He specifically says right before that code "Alternatively, Gaussian elimination can be used on the 2 x 2 system of linear equations to solve for the one unknown in terms of the other." Yep, over my head.

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 don't recommend Christer's formula: (b*- c*e) / denom


In practice I have recieved negative squared distance from very small line segments, which resulted in NaNs being passed around if the result is given to a sqrt function. I wrote an article about the details here: http://www.randygaul.net/2014/07/23/distance-point-to-line-segment/. Usually drawings of vectors and deriving equations piece by piece helps to make sense of formulas.

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.



Christer's code had no such safety mechanism or even an explanation of potential problems. Edit: Which is unfortunate since all the rest of his code I've ever used seems totally robust.

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.

In Topic: Per pixel point light: interpolating vertex world pos

29 December 2011 - 11:44 PM

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.

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).

In Topic: Does anyone know how to prove this algorithm for Collision Detection

29 December 2011 - 11:32 PM

So my Question is : How can I get the Mathematical proof?

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.

In Topic: Fixed Point Arithmetic in architectures wit FPU

25 September 2010 - 03:39 AM

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".