# Questions tagged [computational-geometry]

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

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
344 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 ...
49 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 ...
33 views

### How to fill with empty space with retangles

I have a 'square' class with the representation of its limits from the variables x1, y1 and x2, y1 these variables define points 1 and 3 of the same, in this case the coordinates would be (0,0), (10, -...
139 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 ...
57 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. ...
110 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 ...
149 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 ...
79 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 ...
42 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 ...
102 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 ...