2022 Developer Survey is open! Take survey.

Questions tagged [computational-geometry]

Computational geometry is the study of solving geometric problems using efficient algorithms and data structures, often in real time.

51 questions
Filter by
Sorted by
Tagged with
1 vote
73 views

Unprojeting a line on the screen

I have a line connecting two points of my model. I see a projection of this line on my screen and a want to map a point of that projection to the corresponding point in my model PoV. Let ...
406 views

Image-Space coherence of the z-buffer algorithm

I'm reading Hierarchical z-Buffer Visibility by Ned Greene et al. and they state that traditional Z buffering makes reasonably good use of image-space coherence in the course of scan conversion. I ...
76 views

Find optimal placement for label/sticker on a simple polygon with holes

I'm working on a real-time archviz renderer and I need to place a label/sticker/decal on walls, which have openings. So one way to think about this is a simple (possibly concave) polygon with holes. ...
134 views

Detect walls in geometry

Is it possible to automatically detect walls in polygon soup? Of course it's hard to strictly define what a wall is, my slightly vague definition would be: A wall is a largest possible box (not ...
1 vote
104 views

What are perimeter and aspect ratio, in the context of 3D mesh approximate convex decomposition?

I'm trying to understand the logic behind Mamou and Ghorbel's algorithm in their paper A Simple And Efficient Approach For 3D Mesh Approximate Convex Decomposition. I cannot understand what is the ...
177 views

Writing a sphere-sphere intersection function

I am writing a function where I have two 3d points with coordinates {x, y, z} both with a line segment of a given length. I am trying to find a common endpoint between the two line segments closest to ...
409 views

How to smooth a voxel mesh?

Currently I have refined voxels, I want to smooth it to achieve accurate projection. After some web search, I came across smoothing algorithms such as Catmull-Clark, Doo-Sabin etc. Along with this, I ...
1 vote
46 views

How can I remove unnecessary vertices from wall edges?

I've got a pretty simple tile based 2d top-down map with an array of walls. In order to figure where to cast light and shadows, I've generated an array of vertex coordinates along the walls like so: ...
43 views

Changing block shape to blend with adjacent blocks

I am in the process of programming a Minecraft like game in Unity. I am currently implementing the block mechanics. My goal is that when a block is placed, it has an effect on its neighboring blocks ...
8k views

How to calculate the surface area of a mesh

I am looking for a way to calculate surface area of a 3D mesh object and found this code from a Unity forum: ...
1 vote
406 views

How to calculate plane corner vertices from plane origin point and plane normal?

I have an origin point, and normal vector of a 3D plane. I want to calculate 4 vertices to use as the corners of a 2 triangle quad to render the plane.
1 vote
117 views

Intersection of two limited planes (stripes)

Have two limited planes. That means just squares or stripe in 3D space (or two connected triangles on the same plane). What I want to know is exactly how (and whether) they collide. My first approach ...
11k views

Sphere-Sphere intersection and Circle-Sphere intersection

I have code for circle-circle intersection. But I need to expand it to 3-D. How do I calculate: Radius and center of the intersection circle of two spheres Points of the intersection of a sphere and ...
183 views

Recalculating normals on a tesselated cubed sphere with heightmap applied

I'm learning about the graphics pipeline using C++, HLSL and DirectX 11 for my course. I'm currently tesselating a cubed sphere with an applied height map. My issue is figuring out how to recalculate ...
68k views

How to calculate corner positions/marks of a rotated/tilted rectangle?

I've got two elements, a 2D point and a rectangular area. The point represents the middle of that area. I also know the width and height of that area. And the area is tilted by 40° relative to the ...
106 views

Is there an algorithm to move vertices along a planar mesh to give an area more vertex without destroying the shape too much?

Currently, I am playing around with a terrain technique called Vector-Field terrain as created and used for the game Halo Wars. I have successfully recreated the technique. However, I'm having ...
202 views

Algorithm for Circle with fixed radius to cover most points

I'm in need of an algorithm to find the best spot for a circle with a fixed radius r to cover as many points as possible on a 2D grid, preferably O(n). Currently I tried 2 different approaches: The ...
586 views

Fastest visibility calculation towards all possible directions

I am searching for your advice. I have a massive voxelized model, like the one in the picture (but with a few million voxels more..). To reduce the total number of the model’s triangulations, I can ...
1 vote
2k views

Fast software color interpolating triangle rasterization technique

I'm implementing a software renderer with this rasterization method, however, I was wondering if there is a possibility to improve it, or if there exists an alternative technique that is much faster. ...
15k views

I'm curious to know which is better for games: quads or triangles? Wouldn't quads be better for rendering performances and smoothing out tessellation?
306 views

How can I move a polygon edge 1 unit away from the center?

Let's say I have a polygon class that is represented by a list of vector classes as vertices, like so: ...
2k views

Scan-Line Z-Buffering Dilemma

I have a set of vertices in 3D space, and for each I retain the following information: Its 3D coordinates (x, y, z). A list of pointers to some of the other vertices with which it's connected by ...
366 views

Scanline filling of polygons that share edges and vertices

In the image below (a perspective projection of an icosahedron), the scanline (red) intersects that vertex at the top. In an icosahedron each edge belongs to two triangles. From edge a, only one ...
45 views

Decompose a Mesh so that each piece can be watched by a Guard inside the piece

The title pretty much explains it but I'm gonna go into more details. We have 3D mesh object and we want to decompose it into separate objects so that each one of these objects can be seen completely ...
467 views

Creating force shields: the most efficient way of deforming/reshaping a simpler convex mesh so it envelopes a complex mesh?

So, the best way I can think of how to explain what I need is the following (images used here are just random images found trough google image search). What I am trying to create during run-time is ...
5k views

Easy way to project point onto triangle (or plane)

I have a mesh of triangles (navigation mesh), and a point in 3d space. This point should be "over" one of the triangles all the times. I'm trying to determine which triangle is the one the point is "...
139 views

Detecting single circle within multiple circles area

There are multiple circles with same radius, given another circle in different radius, how to detect the another circle is fully in multiple circles area. Image below shows left samples is in the ...
4k views

How to construct the marching cubes tables algorithmically?

I want to implement the marching cubes algorithm from scratch, but I'm stuck at the polygon generation phase (building edge loops with correct orientation and triangulating them). Obviously, I should ...
26 views

Lengthen Line (bidirectional) - crossing zero line

I'm trying to lengthen a line, by a certain amount. I want to apply the modification to both points on the line, expanding it in both directions. without moving it from it's current position (center ...
5k views

How to create a walkable 3D terrain

I want to make a terrain for a RPG game that I'm developing. I started modeling the surface and implementing it to my game, but now I realized that i might be doing everything wrong. So I would like ...
271 views

How to find out the vertices of the polyhedron formed by the overlapping area of two rotated boxes?

What is the most efficient way for finding out the vertices of the polyhedron formed by the overlapping area of two rotated 3D boxes? If it is still confusing what I mean by "polyhedron formed by...",...
113 views

Integer ops only 3D triangle-triangle collision detection

I've a need for 3D triangle-triangle collision detection using integer math only. Unfortunately, I'm not in a position where I can use 64-bit integers (only 32-bit) and my vertex values can be larger ...
686 views

Given a mesh, I want to generate another mesh that is effectively a shadow volume of this mesh. I am looking for an algorithm/solution/implementation/reference that can do this under the following ...
1 vote
2k views

Segment-Cylinder intersection

What is the complete code (C#, pseudo, does not matter) for calculating the resulting segment (or its absence) for the intersection of asegment and a cylinder? The segment is defined by ...
6k 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 ...
258 views

how to turn (or solidify) water or fuild into solid material (Renderring Effect)

i want to implement an effect like this. for example, let's assume the clay are made of particles. liquids of clay flows for a while, then it becomes dry and rest.finally those particles becomes only ...
5k views

OpenGL - have object follow mouse

I want to have an object follow around my mouse on the screen in OpenGL. (I am also using GLEW, GLFW, and GLM). The best idea I've come up with is: Get the coordinates within the window with ...
282 views

What is an axis aligned integer bounding box?

In this paper, in the Distance field computation section, it says that an axis aligned integer bounding box of a Prism has to be calculated. Can someone explain what an axis aligned integer bounding ...
226 views

Reconstructing mesh from topological skeleton?

I have a topological skeleton of a 3d maze-like level (think Descent[I]/II). It looks like a tree where each node is a vertex in 3d-space. If it were on a 2d plain, I would "simply" use this to ...
330 views

How can I test if an object will "fit" during pathfinding?

I'm tinkering around with a 2d game where obstacles are polygons of arbitrary shapes, sizes and locations, and movable entities (players/enemies) can also be of arbitrary sizes. What's a good general ...
1k views

a flexible data structure for geometries

What data structure would you use to represent meshes that are to be altered (e.g. adding or removing new faces, vertices and edges), and that have to be "studied" in different ways (e.g. finding all ...
279 views

Generate complex (non-convex) polyhedron UV mapping

I need to find an approach to the problem of generating texture maps for non-convex polyhedrons without using a design tool like Maya. Specifically, I am mapping simulation results data onto a 3D ...
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 ...
550 views

How scanline rendering finds an intersection with an object

I'm a newbie with graphics and after I read many articles on the web I still don't understand how in rasterizing from a pixel coordinate like (0;0) on the screen the intersection with an object (let's ...
4k views

Testing whether two cubes are touching in space

Does anyone have any clean ideas on testing whether two cubes in 3D space touch? By touch I mean, touch at corners or on a face or on an edge. Say that the cubes are axis aligned and there is no ...
1 vote
353 views

How do i calc what side the ball is of the rect?

I have this nice drawing: http://bildr.no/view/1085283 I know the ball's center and the rectangle's center, but how do I know (programming C#) what side of the rectangle the ball is? By my drawing, ...
8k views

What is an efficient 2D line-segment-versus-triangle intersection test?

In a 2D plane, I have a line segment (P0 and P1) and a triangle, defined by three points (t0, t1 and t2). My goal is to test, as efficiently as possible ( in terms of computational time), whether the ...
634 views

Determine the cut sections of a polygonal mesh

I have a polygonal mesh, defined by vertices $V$, edges $E$ and face $F$. One can view this as a real life 3D terrain. I want to obtain cut sections of this terrain, defined by vertical cut planes. ...