74 votes
Accepted

I'm rotating an object on two axes, so why does it keep twisting around the third axis?

No this isn't an engine bug or an artifact of a particular rotation representation (those can happen too, but this effect applies to every system that represents rotations, quaternions included). You'...
user avatar
  • 114k
53 votes
Accepted

How can I quantify a drawn line's straightness?

A perfectly straight line would also be the shortest possible line with a total length of sqrt((x1-x2)² + (y1-y2)²). A more scribbly line will be a less ideal ...
user avatar
  • 112k
36 votes

If a 3D vector represents a point, how can it have a length?

Does that mean that the magnitude is simply it is distance from the origin point (0, 0, 0)? That's exactly that. Among other things, a vector can represent a point (a position), a direction and/or a ...
user avatar
  • 15.5k
33 votes
Accepted

How to compute the area of an irregular shape?

You can use Gauss' shoelace formula: You need to take the x coordinate of every point, multiply them by the next point's y coordinate, then subtract the current point's y coordinate multiplied by the ...
user avatar
  • 14.5k
32 votes

How can I quantify a drawn line's straightness?

This might not be the best way to implement this either, but I suggest a RMSD (root mean square deviation) could be better, than merely the distance method, in cases mentioned by Dancrumb (see first ...
user avatar
  • 421
28 votes
Accepted

How can I get the normal vector for a plane from a set of vertices?

You could easily find the normal by calculating two vectors, V1 = P2-P1, and V2 = P3-P1, and then find the cross product N = V1 x V2. Then you normalize N. Depending on the ordering of the vertices (...
user avatar
  • 507
24 votes

How can I quantify a drawn line's straightness?

Existing answers do not take into account that the end points are arbitrary (rather than given). Thus, when measuring the straightness of the curve, it does not make sense to use the end points (for ...
user avatar
20 votes
Accepted

If a 3D vector represents a point, how can it have a length?

Does that mean that the magnitude is simply it is distance from the origin point (0, 0, 0)? The tl;dr answer may be: Yes, you can imagine it like that. But I'm not sure whether this might not lead ...
user avatar
  • 673
18 votes
Accepted

Sphere-Sphere intersection and Circle-Sphere intersection

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 ...
user avatar
  • 114k
18 votes
Accepted

Algorithm for "healing" multiple rectangles into a smaller number of rectangles?

First, we can convert your source rectangles to cells in your underlying grid, to make the input more uniform. (Effectively rasterizing the problem) This will let us find optimizations that might not ...
user avatar
  • 114k
17 votes

How does a 4x4 matrix represent an object in space and matrix lore?

How is Matrix Multiplication a Transformation? A matrix is just a big grid of numbers with rules that define how we can multiply it with other grids or lists of numbers. In games, we usually want to ...
user avatar
  • 114k
16 votes
Accepted

How do I interpret the dot product of non-normalized vectors?

Others have pointed out how you can use the sign of the dot product to broadly determine the angle between two arbitrary vectors (positive: < 90, zero: = 90, negative: > 90), but there's another ...
user avatar
  • 114k
16 votes

Procedurally generating a building of specific area

A simple way to build a procedural generator is: Randomly build things Run a function that checks whether the output is good If the output is not good, go to step 1 Even if it takes thousands of ...
user avatar
  • 14.6k
15 votes
Accepted

Tessellation vs Geometry Shader

Actually no, the 'job' of the geometry shader (GS) is primative evaluation. Geometry shaders can tesselate, but they are limited by a) an in-process upper bounds on the number of output elements, ...
user avatar
14 votes
Accepted

How do I interpolate around a rectangle?

I'll assume your t goes from 0 to 1. (If not, just multiply to scale it appropriately.) Figure out what proportion (0–1) each side is of the perimeter. (side length / total perimeter) To find how ...
user avatar
  • 13.3k
13 votes
Accepted

Get water flow direction vector from water normal vector

One way to do it, considering you want a 90° angle, is to find the cross product of the normal and gravity, normalize it, then cross that with the normal again. In your diagram, the first cross ...
user avatar
  • 164
12 votes

Is there a 3D equivalent of hex tile maps?

2D hexagonal maps are a representation of spheres packed in a flat (2D) tray, with each hex centred on the equivalent sphere, and allow distances between cells to be determined to workable (for gaming ...
user avatar
  • 121
12 votes

How to calculate direction from initial point and another point?

If A and B are both 2D vectors, then... direction = normalize(B - A) any point on the line = direction * distance + A Or you can just take ...
user avatar
  • 1,237
12 votes

Why are spherical worlds so rare?

Because spherical maps, compared to rectangular ones, create a lot of additional complexities regarding the technical implementation and the UI design while usually offering very little gameplay ...
user avatar
  • 112k
10 votes

How do I translate a spherical coordinate to a Cartesian one?

r: radial distance θ: inclination φ: azimuth via Wikipedia ...
user avatar
  • 1,915
9 votes

How can I test whether points are within a polygon?

You will need to process all the points at least once so if this check is done only once there isn't much you can do to speed up the test other than brute-forcing it using parallelism. If the test is ...
user avatar
9 votes
Accepted

What's the fastest way checking if two moving AABBs intersect?

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 ...
user avatar
  • 3,855
9 votes
Accepted

Efficient minimum distance between two axis aligned squares?

By far the slowest part of this algorithm would be the square root. Try to avoid it if you can, and deal with the squared distance directly. For example, if you're comparing distances, the results ...
user avatar
  • 14.6k
8 votes

Is there an efficient way to identify in which run-time generated room a character is, in a non-grid 3D environment? How?

To test whether a point lies inside of polygon you have some options, best known crossing number algorithm or more "stable" winding algorithm(there is pretty fast implementation too). Alternatively, ...
user avatar
  • 4,880
8 votes

How do I efficiently check if a point is inside a rotated rectangle?

Edit: The OPs comment has been skeptical about the efficiency of the suggested negative circular bound check to improve the algorithm in order do checks whether an arbitrary 2D point lies within a ...
user avatar
  • 823
8 votes

If a 3D vector represents a point, how can it have a length?

Does that mean that the magnitude is simply it is distance from the origin point (0, 0, 0)? You can see it that way, but only seeing it that way may lead to a wrong understanding. First of all, a ...
user avatar
  • 803
8 votes
Accepted

Find ID from Spiral x, y positions. Hard programming formula

Let's add some colour coding to see if we can reveal some structure in the problem: Here I've colour-coded the spiral into concentric rings of alternating colours. You'll notice the tile just before ...
user avatar
  • 114k
7 votes

Decomposing a concave mesh into a set of convex meshes

Computing an exact convex decomposition of a surface S is an NP-hard problem and usually produces a high number of clusters. To overcome these limitations, the exact convexity constraint may be ...
user avatar
  • 71
7 votes
Accepted

In a TPS, how to aim bullets to the direction the camera is pointing, but make the shooting from the player?

Real-life gunsights have the exact same problem. There are several ways you can deal with it: Do nothing. Just have the bullets fly from the gun in the direction the player is facing, and accept ...
user avatar

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