Questions tagged [computational-geometry]
Problems involving meshes and other geometry representations, and manipulating, transforming, or extracting information from them; algorithms for solving geometrical problems such as computing intersections, filling holes, triangulating a shape, etc.
204
questions
1
vote
1
answer
113
views
k-torus code in C++
I've been trying to implement this k-torus code that I found, but all it does is return a cylinder (torus of outer radius infinity). Is there anything that I'm missing here?
...
-1
votes
1
answer
28
views
How to implement camera translation arround object using gluLookAt?
I'm trying to move my camera around the object, a house, using some keyboard keys and the gluLookAt() function.
...
0
votes
1
answer
78
views
Constructing half-edges table from triangle list without hash
Motivation
I am trying to refine a mesh such that each triangle gets subdivided into 4 triangles, but I want the vertices to be shared. For that purpose I need a half-edge data structure so I can ...
- 2,083
0
votes
1
answer
61
views
Extrapolating geometry across a triangle mesh?
Say you have 2 parametric cylinders represented as triangle meshes with very different geometries and you connect them together.
Is there a method that allows you to join them together such that the ...
- 1,696
1
vote
0
answers
58
views
Piecewise smoothing of a mesh?
Kobbelt et al. published a paper some 20 years ago where they specified how solving Poisson equations on the positions of a mesh lead to removing noise. This can be used for reconstructing mesh ...
- 1,696
0
votes
0
answers
20
views
How is re projection usually implemented in remeshing?
I was reading "Polygon Mesh Processing" and in chapter 5 the authors present this little algorithm:
...
- 1,696
0
votes
1
answer
83
views
Faring a region of a mesh connecting two curves
In the book Polygon Mesh Processing, there is a section dedicated to fairing. In particular page 59 has this lovely figure:
I am specially interested in the rightmost image. According to the text ...
- 1,696
0
votes
0
answers
19
views
How can I understand the logic of Fast Point Feature Histograms (FPFH) descriptor?
I have been using FPFH features quite a lot in global registration and key-point extraction a lot, I also looked pcl page that tries to explain what it is, but fails to give detail to reader in my ...
- 111
2
votes
1
answer
37
views
What is a smart way to fill in the 'next' pointer of a opposite half-edge of a boundary?
I was reading this question regarding half edges from 3 years ago and the selected answer seemed pretty smart to me. However, while actually implementing it I'm confused at the part where I have to ...
1
vote
0
answers
43
views
How to find point on mesh at a minimum distance from ray
I'm searching for an efficient data structure and algorithm to compute the minimum distance between a ray and a set of meshes in 3D.
What I expect as a result are the coordinates of the nearest point ...
- 111
0
votes
1
answer
28
views
How to measure distortion of a parametrization?
If you have a map from a mesh into the 2D plane. How do you measure its distortion? I know that theoretically what you do is express the differential map of the transformation then use SVD to figure ...
- 1,696
0
votes
0
answers
52
views
What algorithms are typically used for finding 'PCB Trace'-like paths?
I am analyzing a large amount of Layers 0-4 Network Data. I am trying to render diagrams dynamically showing the Network Devices involved in the data (Desktop, Switch, Router, Server, etc.) and how ...
- 101
0
votes
2
answers
40
views
Finding vertices of a polytope?
Assume that in 3D we have a polytope defined by the intersection of halfspaces.
A half space is the set of all solutions of a linear inequality $P = N \cdot x + c \leq 0$ Where $N$ is the normal to ...
- 1,696
1
vote
2
answers
516
views
fast algorithm to check if a point is inside/outside mesh
Usually a ray casting algorithm is used to determine whether a point is indide or outside a mesh. But this algorithm is slow.
Is there any fast algorithm to do this check?
My input mesh is a ...
- 31
0
votes
0
answers
147
views
looking for meshlet generation algorithms
I am looking for algorithms to create meshlets from triangulated meshes.
I searched for articles, but could not find any.
Maybe "meshlet" is not the right term?
I want to cluster the faces ...
- 1,111
0
votes
0
answers
54
views
Interpolate Gradients to Vertices of triangular mesh
A well known way of interpolating the gradient field of a scalar field onto faces of a triangular mesh uses the following formula
(source: https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/...
- 1
0
votes
0
answers
58
views
Calculating world coordinates of a pixel from a camera picture
Sorry for this question. I know there are many similar questions but I really know nothing about math that involves this case.
I have a picture taken from a camera. I know some information about this ...
- 101
2
votes
2
answers
190
views
3D triangle rasterization to voxels
Is there an algorithm to rasterize triangles into voxels (3D, not 2D) that is linear in the amount of voxels in the output?
I.e. given a triangle and a grid, generate the exact voxels that the ...
- 1,696
0
votes
1
answer
90
views
Parametric equation for Catenary curve between two Points
I have two points in 3D space, A and B. I need to have a parametric equation of the catenary curve such that:
Cat(0) = A,
Cat(1) = B,
Cat(t)= f(t, A, B)
How can I derive the function f
2
votes
0
answers
33
views
Optimized 3D rendering using dots and/or line segments of different sizes in Scratch
I'm developing a 3D rendering engine in Scratch, which is a block-based visual programming language. It does not have any support for bitmap rendering, but there is a "pen" plugin that lets ...
1
vote
1
answer
147
views
How to get the boundary of delaunay triangulation
I'm implementing tunnel detection algorithm in the paper "Computing Geometry-aware Handle and Tunnel Loops in 3D Models".
Before the actual tunnel detection, the input needs to be ...
- 31
0
votes
0
answers
22
views
Meshing a set of boundaries?
Say I have a set of closed curves in 3D. I want to connect them together into a 2D manifold mesh.
Something kinda like the drawing, where you are making a triangle mesh that is manifold an connects ...
- 1,696
0
votes
0
answers
42
views
Robust convex hull in 3D?
I implemented gift wrapping in 3D, but I am finding it's just AWFUL at handling anything with coplanarity.
I have spent the entire day trying to fix kinks. Naively I thought that if I detected ...
- 1,696
2
votes
0
answers
51
views
Stitching 2 boundaries together
Let us say we have 2 boundaries of 2 meshes that are roughly aligned, for example 2 generalized cylinders (sweeping surfaces) with a small gap in between. And let us say we want to connect them to ...
- 1,696
0
votes
2
answers
100
views
How do algorithmic botany algorithms generate their plant geometry from a skeleton?
I read the Algorithmic Beauty of plants.The resource goes in depth as to how to generate plant topology, but it does not talk about how to make the geometry except for the leaves.
I tried looking into ...
- 1,696
1
vote
1
answer
42
views
Are there any techniques or algorithms for marking regions of a 3D model with small cross sections
I'd like to identify transition points in an STL where the model goes from relatively large surface to a relatively small surface.
I think that if I had a function that showed me the minimal cross ...
- 111
1
vote
2
answers
192
views
Clever projection of point onto triangle?
I know of at leas tone way to project a point onto a triangle.
Project onto the plane, check barycentric coordinates, if outisde triangle, project onto the 3 segments, check distance, retain closest ...
- 1,696
2
votes
1
answer
74
views
How to create a mesh from a skeleton?
Say you have a topological skeleton, you want to fabricate a mesh out of it, what algorithms exist to accomplish this?
I know of at least one way, which is to represent each edge as an implicit ...
- 1,696
2
votes
0
answers
40
views
Double quaternion skinning artifacts
This is technically about PGA motors, but dual quaternions are a subalgebra of PGA so for all given purposes it's the same idea.
I have an animation in gltf, specified as inverse bind pose matrices, ...
- 1,696
4
votes
2
answers
439
views
Can you explain to me the Bresenham's line algorithm in simple terms?
I've been trying to wrap my head around this algorithm, and I need it for my drawing function. But I can't seem to understand it.
The Wikipedia page gives this piece of code right at the end:
...
- 41
1
vote
0
answers
83
views
Calculating ray intersection with two spheres (with smooth_blending between the two spheres to make them appear as one continuous geometry)
I have the following function to define the distance to the interesection between a ray and the surface of a sphere:
...
- 111
4
votes
1
answer
69
views
How to apply transformation matrices from multiple primitives on a mesh
I'm working on some code to convert a 3d geometry from IFC to gltf/glb. One of the challenges I'm facing with this is that - IFC provides transformations for each primitive separately i.e., if I have ...
- 143
1
vote
0
answers
40
views
Geodesic triangle strip algorithm
I think somewhere in the literature there is an algorithm that, given 2 points on a triangle mesh, finds the triangle strip through which the geodesic passes, but I cannot find it anywhere.
- 1,696
0
votes
0
answers
80
views
Algorithm for drawing generalised circles
A generalised circle is either a circle in the plane or a line. The general equation of one is:
$$A(x^2 + y^2) + Bx + Cy + D=0,$$
where $4AD - B^2 - C^2 \leq 0$. This can be checked by completing the ...
- 101
1
vote
0
answers
45
views
How does the additively weighted Voronoi algorithm differs from the unweighted Voronoi algorithm?
I am trying to read Fortune's description of his additively weighted Voronoi algorithm but I am experiencing some difficulty in understanding it.
I imagine the algorithm as being like that for regular ...
- 11
1
vote
1
answer
39
views
What is the proper term for 3D models which are similar but not necessarily the same size, orientation, face-count/tesselation, etc?
Sup[pose I have a model of a unit cube (12 faces) aligned to the three axes, and another model of a cube divided into thousands of faces and hard-coded in a random orientation. They are both cubes, ...
- 341
0
votes
0
answers
19
views
Automate Image resize, scale, position for best quality (size)
I have a process where a web user selects a photo for a profile image. User is then presented with a canvas to zoom, rotate and move their image within a square viewport. Once satisfied, the user ...
- 101
0
votes
0
answers
28
views
Simulating a moving catheter inside a human heart
I'm trying to simulate a moving catheter inside a human heart. I want to accurately model the behaviour of the catheter and I assume the heart to be solid. What I want is, when the catheter hits the ...
- 101
1
vote
1
answer
102
views
3D to view plane projection
I am trying to draw points of a 3D sphere onto my monitor as if I was looking out into space. Me, the viewer, is at (0, 0, 0). The plane of my monitor is at (x, y, 1) and I have a sphere out in ...
- 21
0
votes
0
answers
46
views
Getting something close to the convex full of SDFs using CSG operations
Inigo Quilez has an explanation of smooth operations to join sdfs.
I am trying to get something close to the convex hull of multiple sdfs. For starters let;s consider a simple case of 3 cubes int eh ...
- 1,696
1
vote
2
answers
66
views
Given two non-intersecting polygons, how to determine which one is in front
I have two 3D polygons, and in both of them all vertices are coplanar. I set a viewing direction and transform the polygons into the coordinate system of the viewing direction, such that the x, y ...
- 111
0
votes
1
answer
96
views
Why the Bowyer's version and Watson's version of computing the Delaunay tessellation are equivalent?
Bowyer–Watson algorithm might be the most famous method for computing the Delaunay triangulation of a finite set of points in any number of dimensions. Its Wikipedia page and most textbooks on ...
- 123
3
votes
0
answers
141
views
Generate polygons after marching squares in parallel
I've implemented the marching squares algorithm following Wikipedia's https://en.wikipedia.org/wiki/Marching_squares. The output I got is a set of edges, to which each contouring cell contributes 0, 1,...
- 31
0
votes
0
answers
91
views
How to delete a face using open mesh?
Pretty much the title I am trying to delete a few faces of a mesh using open mesh, like this:
...
- 1,696
0
votes
1
answer
497
views
What's a simple way to find connected components in a mesh?
As stated I have a triangle mesh I want to separate into connected components. One way I would assume would be to do a depth first search on a vertex and remove vertices, then repeat until the set is ...
- 1,696
1
vote
0
answers
41
views
Algorithm for transforming PNG anti-aliasing to smooth paths
I read the pixels of PNG files via libpng and creates an array of alpha channels (showing visible pixels for a monochromatic image).
int pixels[height][width];
<...
- 131
1
vote
0
answers
36
views
How to get a polyline from an image with consistent winding number
I am trying to find an algorithm for the following problem.
Assume we have a black and white image. The image contains a white region that encloses a space. This space may be concave but it has no ...
- 1,696
1
vote
0
answers
24
views
Geodesic approximation algorithms for minimal geodesic curvature
Introduction
I am building an application in which given a surface and a pair of points on it, an analytic expression of some geodesic arc (preferably the one with the shortest length), between them ...
- 111
1
vote
0
answers
98
views
Given a mesh, a point on the mesh, a direction and a distance, compute the face+barycentric coordinates of point at that geodesic distance
I am a beginner at graphics. I am given a triangular mesh (assume a manifold mesh). I want to sample a square on a mesh that is independent of the triangulation.
I am following these steps
Sample a ...
- 111
1
vote
2
answers
361
views
Half Edge criterion to check if an edge flip is illegal?
I am trying to determine if and when flipping an edge is topologically valid.
The current criterion I have is that it is only valid if there is no edge connecting the opposite vertices of the edge.
I....
- 1,696