Tag Info

Hot answers tagged

21

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


14

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


7

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


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

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


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.


4

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


4

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


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

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


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


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

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


2

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


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


1

Disclaimer: I generally don't work in 3D, so possible inaccuracies, vague details, and untested thoughts may follow. When you say you want the object to "follow the mouse", what do you really mean? In another sense, you can interpret it like this: you want a certain point on the object to be "below" the mouse at all times. We'll call this point the "anchor ...


1

Build shell mesh around every segment, feed them to some CSG processor, smooth resulting mesh.


1

One approach would be to use voxels as an intermediate representation. Render the skeleton line segments into a volume Expand the volume belonging to the skeleton by iteratively filling voxels whose neighbours belong to the skeleton Extract the resulting surface using the marching cubes (or marching tetrahedra) algorithm


1

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


1

Mathematical explanation with readable symbols and LaTeX format - great for 1st or 2nd year undergrad students or skilled high-school people. Well, if you need to understand the maths behind it rather than copy-pasting some code that might not be the good one (it's not clear whether it will work or not judging from the SO code). Here are the steps: It's ...


1

You may find what you're looking for with this question from SO. The last answer seems to fit your request, remember to up-vote that if it helped you.


1

You certainly want to minimise the number of tests being performed. You can do the test using only three comparisons. Let (x1,y1,z1) and (x2,y2,z2) be the centres of the cubes. Let a1 and a2 be their respective extents (ie. half their edge length). The cubes touch by your definition if and only if the distances between the projections of their centres is ...


1

An alternate way to check for AABB collisions is to rule out all cases where you can't collide. if (min_x1 > max_x2) no collision if (max_x1 < min_x2) no collision if (min_y1 > max_y2) no collision if (max_y1 < min_y2) no collision if (min_z1 > max_z2) no collision if (max_z1 < min_z2) no collision otherwise, collision.


1

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


1

Since you have just an elevation map you can start by projecting everything on a 2D plane. So your elevation map will become 2D net and the cutting planes will become cutting lines. After finding all the intersecting points in 2D you can unproject them back to 3D points. This will dramatically simplify the algorithms and the processing time. To project in ...


1

I'm not sure I know exactly what you want to do, but I'm fairly sure you don't need a collision detection engine. You'll want to use some of the principles of a collision detection engine, but don't need a full blown engine. I assume that after you find these slopes they won't change? This terrain is going to be static? You've got a few problems here. ...


1

The first part seems reasonable, and your solution also seems reasonable. The second part can be avoided by finding the closest line that intersects the path. You can't create a new collision if there is nothing closer that will collide.


1

Well first off I'm assuming you're doing a kind of "trace" like described here: http://www.realtimerendering.com/intersections.html So for a given frame you have a certain amount of velocity you want to account for. For the sake of argument let's say you want to slide along surfaces instead of bouncing off of them. So let's say the user is pushing their ...



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