# 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
Filter by
Sorted by
Tagged with
1 vote
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? ...
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. ...
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 ...
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 vote
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 ...
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: ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
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 vote
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 ...
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 ...
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/...
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 ...
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 ...
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
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
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 ...
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 ...
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 ...
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 ...
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 vote
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 ...
1 vote
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 ...
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 ...
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, ...
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: ...
1 vote
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: ...
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 ...
1 vote
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.
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 ...
1 vote
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 ...
1 vote
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, ...
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 ...
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 ...
1 vote
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 ...
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 vote
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 ...
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 ...
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,...
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: ...
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 vote
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]; <...
1 vote
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 vote
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 ...
1 vote