Questions tagged [computational-geometry]
Computational geometry is the study of solving geometric problems using efficient algorithms and data structures, often in real time.
68 questions
0
votes
0
answers
18
views
Computing minimum polygon separation along specific axis
I need to efficiently compute minimum polygon separation along X or Y axis, i.e. the distance you can move a polygon along X or Y until it collides with another one. I know how to calculate it, but ...
- 101
0
votes
1
answer
69
views
Is an assumption of Welzl’s algorithm valid?
The stated assertion that a point outside some intermediate Minimum Enclosing Sphere is on the boundary of the final Minimum Enclosing Sphere seems unsupportable. It is true only for the first point ...
0
votes
1
answer
75
views
Difficulties for GPU rendering of a cone using parametric equation
I'm trying to render a cone at the gpu for some effects. I'm using the parametric equation provided here. I ended up with the shader below intended to work with an unorderedaccessview target (DX11). I'...
- 333
1
vote
0
answers
111
views
Page curl effect
I am trying to simulate a page curl effect in my custom OpenGL based rendering engine.
I initially implemented the version described in the paper "Turning pages of 3D electronic books" where ...
- 153
2
votes
1
answer
123
views
How would I implement the edge loop function from Blender (and how does it work)?
I'm a fairly new game developer, and I've been working on a custom mesh editing system. I've been able to implement edge bevelling (almost, stuck on a division by zero problem), Catmull-Clark ...
- 21
0
votes
0
answers
60
views
Shadow mapping frustum fitting based on Y=0 plane
I am trying to calculate tight fitting of shadow map texture based on camera frustum. Since the camera is always going to be looking down on the Y=0 plane, I ...
- 133
0
votes
1
answer
353
views
How to join skirt to LOD terrain mesh chunk to ensure it matches at seams?
I am exporting my Unity terrain to a mesh. Because the terrain is big, I also split it into multiple chunks.
Moreover, I also generate chunk LODs. I enable a certain chunk LOD in-game based on the ...
- 123
0
votes
1
answer
113
views
Variable subdivision creating artifacts
I'm currently implementing a method for subdividing an icosahedron found here that isn't quite working as expected due to the artifacts created (and the way the triangles are oriented)
The problem ...
- 47
1
vote
0
answers
126
views
How can I determine which parts of the skeletal mesh should be sliced?
I am currently trying to replicate skeletal mesh slicing, akin to something Metal Gear Rising: Revengeance did. So far I've managed to successfuly get some puzzle pieces of this whole thing together, ...
- 11
1
vote
2
answers
112
views
Missing faces at ends of voxel chunks
I'm having problems generating faces in a chunk in OpenGL C++. For example, when I generate faces, they are generated correctly but always at the end of the chunks some faces are not generated.
...
0
votes
2
answers
180
views
How does unity refer a to a normal when there are so many?
When an object collides with another object, does unity calculate the normal, or return it from the list of normals?
- 9
0
votes
0
answers
109
views
How to make a hole of N vertices in the face of a Cube
I want to make a hole of N vertices in the face of a Cube, I'm adding just four like a square in this post to be simple, but eventually I want to be able to add as many as I want and maybe in a ...
0
votes
1
answer
405
views
Sphere to plane collision
I could check for the distance of a vector from the sphere's center to the plane's center, but that would be inefficient, since there are multiple positions where they may not be intersecting but ...
- 9
2
votes
0
answers
406
views
Wrapping a mesh around another
I want to add LED strips to objects at runtime. The led strip is a very simple rectangular mesh that is generated at runtime. A shader then just draws LEDs down the length of the strip.
Here is an ...
- 77
0
votes
0
answers
324
views
Generating tris for concave polygon 2D
I have an arbitrary array of points that describe vertices of the polygon 2D, they ar in order. To generate plane mesh for that, I need to generate tris. For something like circle/hexagon/square it is ...
- 1
1
vote
0
answers
47
views
Move a non-convex polygon's outline inwards?
The polygons are small 3D parts of a quasi sphere centered in the origin and a solution that works in the plane can easily be made to work in this world.
I tried to move the outline inwards by using ...
- 11
1
vote
0
answers
110
views
How to render a block being carved by a milling machine?
I'm making a simulation of a milling machine - something a bit like this diagram:
At the top there is a cylinder mesh representing the milling tool. Below it is a cube mesh representing the material ...
- 131
0
votes
1
answer
122
views
How to improve performance of code for finding climbing annotations?
The goal is to be able to climb any ledge, even if the ledge is an odd shape. Therefore, I found a script that searches for viable "climb holds" along any mesh of any shape. You can then use ...
- 3
0
votes
0
answers
168
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 ...
1
vote
1
answer
122
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:
...
- 11
0
votes
3
answers
2k
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
1
answer
110
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 ...
- 11
1
vote
2
answers
1k
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.
- 298
0
votes
1
answer
277
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 ...
- 25
0
votes
1
answer
117
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. ...
- 173
0
votes
2
answers
192
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 ...
- 407
0
votes
0
answers
591
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 ...
- 161
3
votes
2
answers
13k
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:
...
- 2,084
1
vote
1
answer
159
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 ...
- 123
0
votes
0
answers
72
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 ...
- 123
2
votes
2
answers
998
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 ...
- 121
3
votes
4
answers
199
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 ...
- 49
7
votes
1
answer
161
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 ...
1
vote
1
answer
209
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 ...
- 165
0
votes
1
answer
51
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 ...
- 103
4
votes
4
answers
526
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 ...
- 55
5
votes
4
answers
601
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 ...
- 476
5
votes
2
answers
484
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...",...
- 4,927
0
votes
0
answers
154
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 ...
- 121
0
votes
1
answer
1k
views
Generate Mesh of Shadow Volume
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 ...
- 111
15
votes
6
answers
8k
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 ...
- 220
6
votes
2
answers
6k
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 ...
-1
votes
1
answer
292
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 ...
- 9
26
votes
8
answers
83k
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 ...
- 395
2
votes
1
answer
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 ...
- 45
7
votes
1
answer
16k
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 ...
- 253
3
votes
1
answer
366
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 ...
- 309
3
votes
2
answers
318
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 ...
- 10.6k
4
votes
1
answer
414
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 ...
- 141
13
votes
1
answer
18k
views
Quads Vs Triangles
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?
- 199