   Halfspace test help please, need a good "howto"
  I don't have the benefit of any vector functions that I trust, and I'm (desperately) trying to eliminate complicated math functions (read: trig and sqrt) to make my program faster... I currently have a collision detection framework that is at least visually accurate, but it's horribly slow. I _was_ doing radius-based tests, calculating the distance between colliding radii using trig functions and sqrt()... and I used these values to determine how far to "back out" on the objects to undo the collision and just keep them "touching". This all _works_, but it's not very fast. In fact, when I get upwards of 30 objects on the screen (small compared to how many I plan on having), the whole thing slows down to a less-than-accptable 10-20 fps. The application is written in python, and I know that it's supposedly not as fast as c++, but I don't think I should be hitting such a bottleneck so early. So, in the interest of eliminating trig from my program, I converted the radius tests to axis-aligned square tests. Now I'm trying to eliminate trig from my halfspace test too.Currently, I take my two line points and (using trig) determine what angle the line is at. Then, I take the perpendicular angle and at that angle find the distance to crossing the line, and compare this to the radius and current location of my object. Can I do this without the square and the trig?Thanks.[Edited by - enigma_0Z on May 10, 2009 1:07:00 PM]
  I'll assume you're working in 2D, since otherwise finding the "angle of a line" wouldn't make much sense ;)Given a line segment with points A and B, the perpendicular line segment has points A and [A.y-B.y+A.x, B.x-A.x+A.y].  Also take a look at the perpendicular vector for more information.  You can eliminate the square-root by using squared distances instead, noting that a2 < b2 is equivalent to a < b when 'a' and 'b' are non-negative.  If the distance to the line is negative, then you know the circle has already crossed the line and don't need to do any further checks.   ;  A half-space test can be done without any trig, and usually without any square roots. Computationally, it's very inexpensive.Are the lines that you're testing against static? Assuming that they are, you can pre-compute the parameters of the supporting hyperplane as follows:vector2 normal = normalize(perp(p2 - p1));float distance = dot(p1, normal);The perpendicular distance from a point p to the hyperplane (line) can then be computed like this:float distance = dot(p, hplane.normal) - hplane.distance;By performing this test using the center of a circle and then evaluating the result with respect to the circle radius, you can easily determine if the circle lies fully in one or the other half-space, or overlaps both.I don't have enough experience with Python to comment on its performance characteristics, but in general, as the number of objects in a simulation increases, the brute-force approach to detecting intersections quickly becomes unworkable, regardless of programming language.The typical solution to this problem is to use broad-phase culling of some sort. Commonly used broad-phase culling algorithms/techniques include sort and sweep, grids, and quadtrees/octrees.   ;  Yeah, I suppose those are some crucial details:1. Yes, it is 2d2. Vectors vector vectors... AFAIK Python doesn't _come_ with a vector class...2a. I'm using python, btw.2b. I found this: http://code.google.com/p/pyeuclid/ ... maybe that would work2c. How do I use vectors? I've been doing this stuff by hand so far.2d. Some information on what vectors and the mysterious "dot product" is would be useful... I probably don't know how to use vectors because I don't know well enough what they are.3. About using squares vs. square roots... I know I can use this to test collisions, but how do I calculate the overlap distance? I want to move objects "back" so that they just touch and don't overlap... this is why I've been using sqrt's.About vectors... I may be right, I may not be, but here's what I know. A vector is defined by a length (magnitude?) and an angle. Basically, a vector tells you what direction and how far or how fast, depending on how you use it. A vector can define where an object moves and how far in a period of time...What I know I don't know is how vectors can be used to calculate colisions/intersections, etc. I don't know what on earth this mysterious "dot product" is, although I've heard of it... If someone can tell me or point me to a really simple intro into vector math, explaining at least the basics, that would be really cool."A half-space test can be done without any trig, and usually without any square roots. Computationally, it's very inexpensive."... I also know this from research, but I must be doing something wrong because mine "look" very expensive. Probably because, as anyone can probably tell, I know enough to make myself dangerous. I'm trying to learn with this project too.Thanks.[Edited by - enigma_0Z on May 9, 2009 10:08:56 PM];  Okay. I've found pyeuclid: http://code.google.com/p/pyeuclid/ . It seems to do what I want in terms of providing vectors and vector functions... Now how do I use it??So, here's an example. I have points: A(-4, 0), B(0, 2) P1(-2, 2), P2(-3, 3). I have line AB and want to check whether P1 and P2 are on the southeast or northwest side of AB... How can I do this? I understand that I need to use a dot-product (or two?) But I'm not sure how to do it or interpret the results. The only semi-good information that I've found so far is here: http://ubuntu-gamedev.wikispaces.com/2D+Collision+Detection ... but I don't quite understand the code examples and the terminology goes _just_ over my head. You don't have to do it in "python" or using the pyeuclid library I linked to above, but make the pseudo code either simple enough to understand or comment it heavily.Thanks.   ;Quote:So, here's an example. I have points: A(-4, 0), B(0, 2) P1(-2, 2), P2(-3, 3). I have line AB and want to check whether P1 and P2 are on the southeast or northwest side of AB... How can I do this? I understand that I need to use a dot-product (or two?) But I'm not sure how to do it or interpret the results.I provided an example in my previous reply. If there are parts you need help with, post back with any specific questions you have.   