Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [geometry]

A branch of mathematics concerned with questions of shape, size, relative position of figures, and the properties of space.

39
votes
6answers
5k views

Hexagon collision detection for fast moving objects?

A object has a position and a speed vector. Usually only the position is used to check if two objects collide, this is problematic for very fast moving objects as it can happen that the object moves ...
36
votes
9answers
9k views

How can I quantify a drawn line's straightness?

I'm working on a game which requires players to draw a line from a point A(x1,y1) to the other point B(x2,y2) on the screen of an Android device. I want to find how well that drawing fits to a ...
34
votes
2answers
10k views

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

I see questions come up quite often that have this underlying issue, but they're all caught up in the particulars of a given feature or tool. Here's an attempt to create a canonical answer we can ...
32
votes
4answers
4k views

Why does my object move faster at 45 degrees than at 90 degrees?

I have objects in my game that move faster at 45 degrees then at 90 degrees. Each object has Point (x,y) position Vector2D (x,y) direction Int speed And what I do during a update is that new ...
31
votes
1answer
8k views

How do you turn a cube into a sphere?

I'm trying to make a quad sphere based on an article, which shows results like this: I can generate a cube correctly: But when I convert all the points according to this formula (from the page ...
27
votes
6answers
7k views

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

I am trying to understand vector arithmetic (and specifically its use in the Unity engine). I am not able to figure out how a vector can have a length (magnitude) even though it only represents a ...
27
votes
6answers
15k views

How do I calculate distance between a point and an axis-aligned rectangle?

I have a 2D rectangle with x, y position, height and width, and a randomly positioned point nearby. Is there a way to check if this point might collide with the rectangle if it is closer than a ...
26
votes
4answers
6k views

Is there a 3D equivalent of hex tile maps?

Probably the biggest advantage of a hex-based versus square-based map tiling is that the center of each hex has the same distance to all its neighboring hexes. Is there a similar shape that tiles this ...
25
votes
4answers
7k views

Is the Manhattan distance monotonic when used as heuristic function?

I have a square-based map. Only horizontal and vertical movement is allowed (no diagonals). Movement cost is always 1. I'm implementing an A* algorithm on that map, using the Manhattan distance as a ...
24
votes
3answers
32k views

How do you programmatically generate a sphere?

Could someone please explain how it would be possible to create a sphere vertices, indices and texture coordinates? There is a surprising lack of documentation on how to do so and it is something that ...
19
votes
5answers
2k views

How can I tell whether an object is moving CW or CCW around a connected path?

Lets say we have a jagged shape: And two creatures moving along it's outline. Then we smooth the shape completely by pulling the corners out. We get this: It is easy to see now that Orange is ...
18
votes
2answers
21k views

How can I convert a mouse click to a ray?

I have a perspective projection. When the user clicks on the screen, I want to compute the ray between the near and far planes that projects from the mouse point, so I can do some ray intersection ...
17
votes
3answers
3k views

How to compute the area of an irregular shape?

I have a room object defined by a collection of looping line segments that I need to calculate the area for. The classes can be described as follows (in pseudo-code): ...
17
votes
2answers
19k views

How can I project a 3D point onto a 3D line?

Let's say I have a line defined by two points, A and B, both in the form (x, y, z). These ...
15
votes
4answers
3k views

Procedurally generating a building of specific area

Myself and a team are working on a factory builder game that gives the player a random factory at the start of the game. To try to make sure there is a sense of "fairness," ideally the randomly ...
15
votes
4answers
1k views

How do you calculate the nearest point on 2 curves?

Given the points of a line and a quadratic bezier curve, how do you calculate their nearest point? .... Similarly, given the points of 2 curves, how do you get the nearest point?
14
votes
2answers
25k views

How do I use the dot product to get an angle between two vectors?

I am learning to use normalized vectors in my games. I've learned that in order to know the angle between two vectors, I can use the dot product. This gives me a value between -1 and 1, where 1 ...
14
votes
4answers
1k views

Algorithm for creating adjacent triangles

I have a system where you can click once to place a node in a scene. When you place 3 nodes, it forms a triangle. When you place any future nodes, it creates a new triangle by joining that node to the ...
13
votes
3answers
911 views

Are the first three values that describe a 3D plane actually a 3D vector?

A 3d plane is typically defined as a,b,c,d. Are a,b,c actually the x,y,z coordinates of a 3d ...
12
votes
3answers
5k views

Are the Minecraft animations hardcoded into the game? [closed]

I would like to know how the animation system works in minecraft. I get a feeling that all the mobs are hardcoded into the game. Did notch really sit there and create the matrices for all the ...
12
votes
6answers
4k views

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

I have two AABBs that are moving, what's the fastest way to check if they will intersect under a frame? By moving I mean not just to check with the usual rectangle intersection method, I mean some ...
12
votes
1answer
2k views

How do I make a curved surface out of rectangular blocks?

For a Peggle-like game, I want to make blocks that follow a curve, like this: The blocks would then disappear as the ball hits them. I managed to draw some horizontally, but I'm having trouble ...
12
votes
2answers
5k views

Arbitrary Rotation about a Sphere

I'm coding a mechanic which allows a user to move around the surface of a sphere. The position on the sphere is currently stored as theta and ...
11
votes
5answers
3k views

How would one determine the length of a path?

I have a game that requires each player to move along one specified path. I draw the path using Bézier curves. How can I determine the total real (not linear) length of the path and the distance that ...
11
votes
4answers
433 views

How do I interpolate around a rectangle?

I want to make a fancy animation where a point travels around a rectangle. I want to find the point's position at a time t. The rectangle is given by ...
11
votes
2answers
2k views

How to limit click'n'drag movement to an area?

I apologize for the somewhat generic title. I'm really don't have much clue about how to accomplish what I'm trying to do, which is making it harder even to research a possible solution. I'm trying ...
11
votes
4answers
1k views

How can I find the largest sphere that fits inside a frustum?

How do you find the largest sphere that you can draw in perspective? Viewed from the top, it'd be this: Added: on the frustum on the right, I've marked four points I think we know something about. ...
11
votes
1answer
1k views

Algorithm for “healing” multiple rectangles into a smaller number of rectangles?

Say I have a grid of rectangles of different shapes and colors and I want to reduce (reasonably close to optimal is fine, optimal is not necessary) the number of rectangles to represent the same ...
10
votes
2answers
481 views

World Bounds - (0, Size) or (-HalfSize, HalfSize)?

When creating a game space in which to move, draw and collide objects, is it better to have the (0,0) point, or the (0,0,0) point, be in the very center of your space, such that the bounds of the ...
10
votes
1answer
7k views

Circle-Line Collision Detection Problem

I am currently developing a breakout clone and I have hit a roadblock in getting collision detection between a ball (circle) and a brick (convex polygon) working correctly. I am using a Circle-Line ...
10
votes
1answer
1k views

Algorithm for constructing the corners of a regular, n-sided polygon

I've googled this using a lot of keyword combinations, but to my great surprise I could not find an algorithm for constructing a regular, n-sided polygon into a given circle, i.e., finding the ...
10
votes
3answers
4k views

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

Could someone point me in the right direction as to how this might be achieved? 3D math / geometry often throws me. I'm looking for something like this (ideally in C#): ...
10
votes
1answer
4k views

Tessellation vs Geometry Shader

Correct me if I'm wrong, but both the Geometry Shader and the Tessellation Shader jobs are to generate vertices in the Graphic Pipeline. What I would like to know is how they are different and when ...
10
votes
2answers
359 views

How do you calculate if 2 lines are facing toward or away?

Given the 4 points describing 2 line segments, how do you calculate if line A is towards or away from line B? The 2 lines have a fixed length, and can be measured as distance from x1/y1 to x2/y2.
10
votes
1answer
4k views

Procedural Geometry Generation

I have recently been looking into SceneKit for OS X and noticed that there are several factory methods to create geometric shapes such as: Box, Capsule, Cone, Cylinder, Plane, Pyramid, Sphere, Torus ...
9
votes
1answer
2k views

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

I'm working on a HLSL / C++ little project to going over my graphics work, and I am unsure how I am to get a facing vector from a vertex polygon. I can't seem to find the formula. The positions are ...
9
votes
2answers
3k views

Geometry System of Populous: The Beginning [closed]

I want to to develop a game like Populous: The Beginning with my friend. But we could not find out what type of geometry they have used for the world. We know that - all tiles have the same size - ...
9
votes
2answers
1k views

Get water flow direction vector from water normal vector

Im stuck developing an important detail of my game water: Making it flow downwards! Considering a typical 3D world in wich water tends to go towards gravity ...
9
votes
4answers
4k views

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

Part for the sake of optimization, part for learning purposes, I will dare to ask: How can I most efficiently check whether a 2D point P is inside a 2D rotated ...
9
votes
3answers
6k views

2D isometric: screen to tile coordinates

I'm writing an isometric 2D game and I'm having difficulty figuring precisely on which tile the cursor is. Here's a drawing: where xs and ys are screen coordinates (pixels), xt and yt are tile ...
9
votes
2answers
7k views

How do I determine if one polygon completely contains another?

I have 2 polygons. I know the vertex coordinates of both polygons. What's the best way to check if one is completely inside the other? For example, the algorithm should only recognize the black ...
9
votes
1answer
564 views

Dual Contouring - Finding the feature point, normals off

I am following this tutorial to implement Dual Contouring http://www.sandboxie.com/misc/isosurf/isosurfaces.html My data source is a grid 16x16x16; I traverse this grid bottom to top, left to right, ...
8
votes
3answers
10k views

Decomposing a concave mesh into a set of convex meshes

I'd like to be able to decompose a concave mesh into a set of convex meshes for 2 reasons: Transparent rendering Physics shapes Is there an algorithm that takes a set of triangles (concave) as input ...
8
votes
4answers
3k views

Find the closest point along a rectangle, given an another point and direction

Given a rectangle, and a point with a vector direction towards the rectangle. How can I find the closest point on the outside of that rectangle to the point in question?
8
votes
1answer
24k views

How to calculate a 3x3 rotation matrix from 2 direction vectors?

I've got 2 direction vectors, for the X axis and the Y axis of the object. How do I calculate the rotation matrix of the object using these?
8
votes
4answers
7k views

Moving a particle around an Archimedean spiral at a constant speed

I want to move a particle in a spiral at a constant speed. Note that that is not a constant angular speed. This is proving rather difficult, and I'll go through my method so far below. The spiral in ...
8
votes
2answers
3k views

How does Unity3D lower an imported .obj vertex count?

I have a question regarding how Unity3D handles importing of .obj files. I'm importing this teapot: http://groups.csail.mit.edu/graphics/classes/6.837/F03/models/teapot.obj The number of vertices ...
8
votes
1answer
3k views

Am I going to regret using a color based collision detection system?

I'm just getting started build my first game with XNA (I'm experienced with C# but not games). I'm building a pretty simple top down 2d shooter. I read this tutorial on using a color based collision ...
8
votes
1answer
229 views

What are some ways to implement variable body shapes?

Games like Ryzom and the Sims allow players to have human bodies with different shapes: wide or thin, tall or short, big noses or small, etc. It seems to me that it'd be impractical to pre-generate ...
7
votes
3answers
982 views

Why is the depth test not done on geometry before rasterization?

It seems the only time depth is used to discard data is during rasterization, i.e. at the fragment level. In the geometry stage, I've only see culling and clipping of vertices. Is it not possible to ...