Tag Info

Hot answers tagged

12

Tetrad covered general intersection in his post. Here I'll cover an algorithm that returns the specific points of intersection based on the formulae in this concise article. I'm matching my variable names to those in the article, so keep this diagram in mind - and probably in view too! The language is Python. You can verify your results in Wolfram Alpha ...


11

As your feared, you are oversimplifying. If you transform your scene so that the ellipse becomes a circle, you are using a non-isometric transformation and relative distance is not preserved. This can be best seen in the following diagram, where the point closest to the black point clearly changes: Finding the closest point on an ellipse is a non-trivial ...


10

Do you mean if the circles are overlapping? That's easy, just figure out the distance between the two and compare it to the r1 and r2. Or more specifically, calculate the squared distance between the two (it's faster) and compare it to (r1 + r2)^2. If you mean what the actual intersection points are of the two circles, then I don't know the math for that ...


8

Let C₁ and C₂ be the sphere centres, and R₁ and R₂ their radiuses. We pick a point A on the intersection circle and we want to find B, the centre of the intersection circle: Pythagoras gives us the following two equalities: AB² = AC₁² - BC₁² AB² = AC₂² - BC₂² Combining the two and replacing AC₁ with R₁ and AC₂ with R₂: BC₁² - BC₂² = R₁² - R₂² We ...


6

Calculate the three corners of your fov triangle, rotate them to be facing the correct way and such, and then do one of: 1) do a point-in-triangle test for all the potential targets 2) calculate the bounding box of the this triangle, and do a point-in-triangle test for all potential targets in cells in this bounding box - this will be very straightforward ...


6

The Sutherland-Hodgman polygon clipping algorithm should work just fine for triangle vs. rectangle clipping. You'll find some more information about clipping algorithms here. Or just search for "Sutherland Hodgman clipping".


6

How do you store the ellipsoid? If it has a position, orientation and the radius in local x- and y-axis, it might be easier to calculate the inverse transformation matrix, that transforms the ellipsoid to a circle. Transform the AABB into that space too using that matrix, then you can make simple triangle-circle collision tests. Edit: In the left image ...


5

Try the following method which relies on XNA's built in Math API to intersect a Ray and a Plane and get back the point of intersection: Vector3? GetRayPlaneIntersectionPoint(Ray ray, Plane plane) { float? distance = ray.Intersects(plane); return distance.HasValue ? ray.Position + ray.Direction * distance.Value : null; } The method returns null if ...


5

Given two parametric equations of lines; L=a+t.b // t is the paramerter, a & b are vectors M=c+u.d //u is parameter, c & d are vectors The the point of intersection is the one place in space where both these equations are equal(produce the same point). When the lines intersect at some value of t and some value of u, the equations are equal, ...


5

While Zhen's example code is perfectly fine, I'd use one big expression (might not be possible based on your actual language): bool pointInRectangle(Rectangle rect, Point point) { return p.x >= r.x && // point is right of the left edge p.y >= r.y && // point is below the top edge p.x <= r.x + r.w && ...


4

First, the value called denominator is something that you might call the "two-dimensional cross product" of the vectors b - a and d - c. You can see that it corresponds to what would be the z-component of the cross product if these were 3D vectors. The "2D cross product", like the 3D one, represents the (signed) area of the parallelogram spanned by the two ...


4

Following the half-plane method, you'll have found the line segments to every other point and the perpendicular bisectors of each of those which you then intersected to find potential vertices of the Voronoi cell. Now, you want to exclude the ones that intersect any of the "distant" half-planes formed by the bisectors. I coloured the "distant" ...


3

It's easier to think of this using vector maths. The plane equation is N.P = -D for all points on the plane. Therefore, the intersection point must satisfy this. If our point P is defined by the line equation P = P0 + tQ (where Q is the line's direction and t is the distance along the line) we can sub this in: N.(P0 + tQ) = -D The dot product is ...


3

linear systems of N variables can be solved if you have N equations. x = 10ɑ y = 20ɑ z = -10 + 40ɑ x = β y = 2β + μ z = 0 6 equations, 6 unknowns. You can solve for all 6. In fact, generally you can just combine the x/y/z parts and say 10ɑ = β 20ɑ = 2β + μ -10 + 40ɑ = 0 and get 3-variable system in ɑ,β,μ. Once you get a value for ɑ, you can plug back ...


3

I don't know what's the problem with your implementation, but I have used the method below (taken directly from this sample) on a raytracer and it worked correctly and performed well too. So you might consider swapping to this implementation: /// <summary> /// Checks whether a ray intersects a triangle. This uses the algorithm /// developed by Tomas ...


3

Your code seems to use quads and it seems that you don't use the two triangles from the quad but two overlapping ones (say the second one is wrong), try this instead (see the "v2, v3, v0" part) : if(rayTriangleIntersect(rayOrigin, rayDirection, v0, v1, v2, ref intersectPosition) || rayTriangleIntersect(rayOrigin, rayDirection, v2, v3, ...


3

The canonical solution in software renderers (which must do this exact algorithm every time they rasterize a triangle) is, I believe, to scan the triangle one row of pixels at a time. The left and right edges of each row and calculated by walking down the sides of the triangle using Bresenham, and then you fill in the row between them. I'm glossing over ...


3

To find the normal, you can use the cross product of three of the points in the polygon. Create two vectors from those three points and find the cross product of those. To find the intersection of the ray with the polygon, you will first need to ensure it intersects with the plane of the polygon. To do this, you will need to do some algebraic manipulation ...


3

In general, lines are a poor approximation of a user's movement because they don't account for the size of the player. You want "sweep sphere triangle intersection", also called "capsule triangle intersection". http://xania.org/Games has a good overview of this.


3

First bit is to get a model of the pyramid's bottom rectangle R. Define u = b - a = (b1 - a1, b2 - a2, b3 - a3) v = c - a = (c1 - a1, c2 - a2, c3 - a3) If the bottom is really flat then the equation d = u + v should hold (otherwise vector d is ignored). The rectangle R is defined by R = { y | y = a + α u + β v ∧ 0 ≤ α ≤ 1 ∧ 0 ≤ β ≤ 1 } To test for ...


3

Think of your frustum as a set of planes defined by three vectors each. In your case, 5 planes (left, right, top, bottom, far). A typical frustum has 6 (near, far, left, right, top, bottom) Take the dot product of each plane's normal with the point's location to get the distance of that point from that plane. If the distance is greater than zero, it's in ...


3

You may simply iterate over edges and filter out all vertices that are not in same half-plane with point of interest. As optimisation, iterate from nearest edges to farthest. I think you may even filter vertices while generating slices. It is like slicing pie with endless knife, until only small piece left with cherry on it. If you like analogies. Just cut ...


3

One major advantage is that many collision detection operations are more efficient when performed at the origin. A classic example is box vs sphere. When done in a box's local space the tests are very simple axis aligned distance point-plane tests instead of the more costly non-axis aligned planes. Furthermore objects moving through space may not actually ...


2

Try changing if (det > -0.00001f) return false; to, if (det > -0.00001f && det < 0.00001f) return false; Currently, your code only checks one side of the triangle


2

I don't know about Flash technology, nor how the game is updated. Presuming that there can be an Update() method like the one encountered in XNA that is called from within the game loop, would it not be possible to simply calculate: the coordinates of your enemy's center, that is, (x2, y2) based on its current location; than the coordinates of the ...


2

If cube is axis-aligned, then it's easy. You can compare each vertex of triangle with each face (plane) of cube. If it's out of cube (just compare apropriate coordinates), then find two new points, which lie on line connecting two other vertices with that one out of cube and which lie on plane (their coordinate is same as the plane). This is common linear ...


2

It's generally both easier and faster to convert rays into the object's local space and do the test. It's either 1 tranformation on the ray or N transformations of N vertices into world space, and for even a single triangle 1 will be less than N. For objects like OBBs it's also much easier to just treat it like an AABB in object space when doing ray ...


2

If you want to spawn particles on the surface of a mesh, it's relatively easy: pick a random triangle, then pick a random point on it. The choice of triangle should be weighted by area so that the particles don't clump into the denser areas of the mesh (unless that is a desirable effect). To spawn particles within the volume enclosed by a mesh is harder. ...


2

As the link suggests, a BVH is a data structure that is used to quickly compute collision queries for a set of polygons. It doesn't usually provide information about the underlying geometry itself other than possibly maintaining references to triangles in the leaves of the tree. In terms of your problem of finding out whether or not a point is within a set ...


2

For 2D, I don't think you can do much better than just intersecting the boundary edges. If you triangulate your polygon, you will end up with more edges to test against, making your test slower.



Only top voted, non community-wiki answers of a minimum length are eligible