# Tag Info

26

there are two cases of this problem. First is the intersection and second that is overlaping (containing). First (intersection / polygon inside circle): Find closest point on every edge of the polygon to the circle's center. If any distance between closest point to the center is less than radius, you got intersection or overlap. Second (circle is whole in ...

18

Triangles, the reason is triangles' ratesrization algorithm is faster, and also natively supported in hardware. So it would be faster to convert one quad into two triangles and do the rasterization. Actually that is what happens when you draw a quad on modern graphics hardware. So the question is what makes it faster ? There are certain characteristics in ...

11

Sphere-Sphere Intersection Let's start with the more obvious one - sphere-sphere. It's almost identical to the circle-circle case in 2D. We can project down on any plane containing the line between the sphere's centers to get an identical 2D picture: Here the first sphere has center c_1 and radius r_1, the second c_2 and r_2, and their intersection has ...

9

The way to generate the edges and the faces of a primitive shape like a box, a cone and all those you cited is to generate them at the same time you create the vertices. In fact, you should create the vertices in a logical way that makes it easy to compute the edges and faces accordingly. There are algorithms that take as input a set of points in space and ...

9

X = x*cos(θ) - y*sin(θ) Y = x*sin(θ) + y*cos(θ) This will give you the location of a point rotated θ degrees around the origin. Since the corners of the square are rotated around the center of the square and not the origin, a couple of steps need to be added to be able to use this formula. First you need to set the point relative to the origin. Then you ...

7

I think you may be trying to fit a square key into a round hole by applying SAT in the way you are, here. Obviously, it's not designed for concave-concave collisions, and though I commend your effort to adapt it for that purpose, there are considerations that make this unlikely to work. Realism Angular impulse and it's knock-on effects are the name of the ...

6

Use the Minkowski sum A good way to solve this problem is to consider the intersection between a line of motion (v) translated to the origin (v') and the Minkowski sum of A rotated 180 degrees at the origin (A') and its obstacles (just B in this case): A' ⊕ B. In the following picture I place A smack-dab in the origin of an arbitrary coordinate system. ...

5

Depending on your needs there are different data structure that you can use for geometry representation, before I answer your question I need to point out that geometric representation are usually chosen based on two basic factors, Topological Requirements: this includes the types of meshes you are going to store, triangles only? n-polys ? regular, ...

5

Half-edges are usually used for many serious geometrical analysis and modification algorithms. You may find it more convenient to add a higher-level abstraction layer on top of this if you don't want to work with half-edges directly.

5

Here is an algorithm for intersection only (doesn't cover touching) that I believe is fast. if t0, t1 and t2 are all on the same side of line P0P1, return NOT INTERSECTING if P0 AND P1 are on the other side of line t0t1 as t2, return NOT INTERSECTING if P0 AND P1 are on the other side of line t1t2 as t0, return NOT INTERSECTING if P0 AND P1 are on the ...

5

You can generate your surface as height map (2D table of heights, regular grid). It might look like this http://mrdoob.github.com/three.js/examples/webgl_geometry_terrain.html You probably don't need physical simulation, so you just find the height at certain coordinate and check, if your model is above it /under it. That is only the basic idea and I am ...

5

OBB - Oriented bounding box. Here's a tutorial Effectively, a bounding box aligned with the Velocity vector of object A as the y-axis (up). It's width and height can be calculated by the starting and ending points of object A. You then compare this with the AABB of object B (treating it as an OOBB), and your golden. If you're just looking for a quick ...

4

You will need an active edge list, which contains a list of all polygon edges intersected by the current scanline. You will also need an in/out flag for each polygon on the scanline. The flags are toggled on/of as you cross an edge for a polygon. The rules are drawing for each pixel along a scanline are; no polygon flags are 'in', then draw background ...

4

You don't need OOBs and you don't need to use time-stepping collision detection. Just use the normal AABB swept test, see this link. In essense it does exactly what you have in your diagram: the moving AABB is "swept" from start point to end point and then that is used for collision detection against other, static AABBs. If you are worried that this swept ...

4

Each of your images describes a different algorithm. I would say the top two should not even be in the question. Bottom right is too angular to look good in-game, it looks like luggage in plastic cling-wrap. Let's focus on bottom left, the best looking approximation of the original mesh. I think you want the 3D Minkowski sum of the original mesh, either (1) ...

4

Sliced 2D Convex Hulls Slice through the mesh (polygon + axis-aligned plane intersection), getting the convex hull of each resultant 2D polygon, e.g. from tip to tail for a ship like that in your image, or from head to toe in a humanoid - as you'd slice a carrot :) These could be equidistant slices or spaced according to some heuristic, but will describe the ...

3

An axis-aligned bounding box is a simplified representation of some object's volume and position. In this case, I think an axis aligned integer bounding box would be a bounding box that can only have integral dimensions, and an integral position. If this definition is accurate, then a bounding box like this could be found if you found the highest vertex, ...

3

One solution is to create a navigation mesh which defines walkable surfaces. This mesh can also be used for pathfinding for AI. There is a C++ library to automatically create a navigation mesh called Recast & Detour. Recast has been integrated into Blender. Switch the renderer to "Blender Game". In the Scene properties panel you can then find a "Build ...

3

If your cubes overlap or they just touch, they have to overlap or touch in all three axis. In one axis it looks like this (for two intervals a and b): So what you have to test is: if ((min_a <= min_b && min_b <= max_a) || (min_b <= min_a && min_a <= max_b)) First part (before ||) is for case when min_a < min_b, ...

3

The bIg question here is what does your outer loop look like? I.e. Are you intersecting many lines with many triangles, one line to many triangles or many lines to one triangle? Or is it just N pairs of a triangle and a line? Only the last case (which sounds to be the most unlikely case) will best be accelerated by a faster segment to triangle intersection ...

3

You will need to first decompose the movement into smaller steps and use that information to calculate a high-level AABB. If the large AABB's intersect, you can then check the smaller steps to be more accurate. Estimating whether or not there may have been a collision by checking AABB (or OOBB) using just the starting and ending positions can miss ...

3

In the end, here it goes in detail the way I myself figured out to get what I've asked (also inspired by @snake5's comments): 1a) for each of the 12 edges (line-segments) of one box, we test first if it is entirely within the other box. If it is, we already save its both vertices in the final list of vertices that form the desired polyhedron. 1b) if it is ...

2

AFAIK you can check collision of each edge of triangle and even if one of the was true, the line segment collides the triangle. according to wikipage you can easily compute intersection point of two lines, in the rare case that you have divisor is zero it means two lines are parralel so they can't collide at all! then you have to check if the collision ...

2

What side of A is B on? Using this info (see Solution 3) you can determine which side of a line A point (or points) B, is on. For your particular scenario, you need to check which of four sides of the rectangle, the circle is in. In this case, you can treat your circle as just it's centre/origin point. Now you need to look at the rectangle like this: \ ...

2

Typically the process is something like this... Determine the object's motion vector Mass-project the object's vertices onto a line (2D) or plane (3D) along the motion vector to see whether they intersect the obstacles. (There may be cheaper ways to rapidly reduce the object's vertices to two points which represent the maximal profile of the polygon, but ...

2

In some ways, rasterisation is the opposite problem to raytracing. In raytracing, you know which pixel you are testing, and you have to find the triangles that are hit by the ray through it. In rasterisation, you have information about a triangle and you need to find which pixels it covers. Basically, the vertices describing the triangle are projected into ...

2

I also had exactly the same thoughts as you. For my final university project I studied different methods of voxel mesh smoothing. The best method I found was Surface Nets. It produces a result that looks very similar to March Cubes but without all that lookup table hassle. You can also choose how smooth you want the object by performing more passes of the ...

2

You will have to decompose the movement into smaller steps of movement. For example: You want to decompose the movement using the greater componen (in this case, X-axis), and then check for collision in each step. This might look too expensive, but take into account that an object moving faster than it's own width each cycle will be EXTREMELLY fast, so ...

2

You should also use relative speeds for the collision check so one AABB is "static" and the other move at a speed of its own speed minus the speed of the "static" one. The fastest way to see if they may intersect is to just expand the moving AABB with the speed. for example the AABB is moving right with 0.1 x/frame, then you extend it so the left edge ...

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