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
72 views

Is there a quicker way to draw a symmetric, scale-invariant (declining color) gradient around an ellipse?

The goal is to generate a picture like this: A symmetric color gradient around an ellipse which is rotated by $\theta$, has $(x_\circ,y_\circ)$ as center and and major and an minor axis $a,b$. The ...
• 13
1 vote
26 views

How to morph a enclosing mesh according to the enclosed mesh?

I am quite new to meshing and mesh manipulation. I am working on a problem consiting of meshes $A$, $B$, and $C$. The mesh $C$ completely encloses the meshes $A$ and $B$ as shown in the attached ...
• 11
71 views

How to find the major and minor axes of a convex hull?

I have a set of particles in a gravitationally bound system. The shape of the particles change with time, I have used a convex hull algorithm to "enclose" the particles of the cloud. I want ...
1 vote
24 views

Covering texture surface with ellipses

I am looking for an algorithm (also ideas on possible directions are appreciated) which is able to compute the distribution of ellipses on a 2D surface in order to reach a good degree of covering. I ...
19 views

How to extract points corresponding to faces from cube map projection (CMP) of panorama from point cloud data

I am working with the standford2d3d dataset http://buildingparser.stanford.edu/dataset.html which contains panoramas of various scenes and a .mat file of the point cloud information of all the scenes. ...
186 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? ...
59 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. ...
1 vote
141 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,226
114 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,736
1 vote
64 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,736
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,736
84 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,736
63 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
58 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
52 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
38 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,736
68 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
45 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,736
1 vote
2k 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
298 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,299
332 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,736
222 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
40 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
215 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
53 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,736
144 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,736
1 vote
49 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
394 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,736
146 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,736
53 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,736
847 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
109 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: ...
81 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
41 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,736
90 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
40 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
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
29 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
106 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
52 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,736
1 vote
110 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
152 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
173 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
98 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,736
712 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,736
1 vote
47 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
37 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,736
1 vote
26 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
118 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