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.

Filter by
Sorted by
Tagged with
2 votes
0 answers
45 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 ...
Penguin1068's user avatar
1 vote
0 answers
22 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 ...
StefanoScolari's user avatar
0 votes
0 answers
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. ...
Miguel's user avatar
  • 1
2 votes
1 answer
150 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? ...
shawn_halayka's user avatar
-1 votes
1 answer
51 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. ...
MasterTJ123's user avatar
1 vote
1 answer
122 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 ...
lightxbulb's user avatar
  • 2,226
0 votes
1 answer
101 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 ...
Makogan's user avatar
  • 1,706
1 vote
0 answers
59 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 ...
Makogan's user avatar
  • 1,706
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: ...
Makogan's user avatar
  • 1,706
0 votes
1 answer
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 ...
Makogan's user avatar
  • 1,706
0 votes
0 answers
45 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 ...
Lady Be Good's user avatar
2 votes
1 answer
56 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 ...
ThisAccountIsForGameDev's user avatar
1 vote
0 answers
50 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 ...
oparisy's user avatar
  • 111
0 votes
1 answer
36 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 ...
Makogan's user avatar
  • 1,706
0 votes
0 answers
61 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 ...
Liam Kelly's user avatar
0 votes
2 answers
43 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 ...
Makogan's user avatar
  • 1,706
1 vote
2 answers
1k 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 ...
veggieg's user avatar
  • 31
0 votes
0 answers
258 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 ...
Thomas's user avatar
  • 1,265
0 votes
0 answers
73 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/...
Ian_L's user avatar
  • 101
0 votes
0 answers
111 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 ...
Magno C's user avatar
  • 101
2 votes
2 answers
274 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 ...
Makogan's user avatar
  • 1,706
0 votes
1 answer
155 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
Argha Chakraborty's user avatar
2 votes
0 answers
37 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 ...
Peter Marshall's user avatar
1 vote
1 answer
187 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 ...
veggieg's user avatar
  • 31
2 votes
0 answers
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 ...
Makogan's user avatar
  • 1,706
0 votes
2 answers
120 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 ...
Makogan's user avatar
  • 1,706
1 vote
1 answer
46 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 ...
Dave Fol's user avatar
  • 111
1 vote
2 answers
303 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 ...
Makogan's user avatar
  • 1,706
2 votes
1 answer
111 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 ...
Makogan's user avatar
  • 1,706
2 votes
0 answers
47 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, ...
Makogan's user avatar
  • 1,706
4 votes
2 answers
671 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: ...
sneaker's user avatar
  • 41
1 vote
0 answers
100 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: ...
Iron Attorney's user avatar
4 votes
1 answer
78 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 ...
Gangula's user avatar
  • 143
1 vote
0 answers
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.
Makogan's user avatar
  • 1,706
0 votes
0 answers
84 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 ...
wlad's user avatar
  • 101
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, ...
Jack's user avatar
  • 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 ...
johnw182's user avatar
  • 101
0 votes
0 answers
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 ...
Optimus's user avatar
  • 101
1 vote
1 answer
103 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 ...
Dan Wood's user avatar
0 votes
0 answers
51 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 ...
Makogan's user avatar
  • 1,706
1 vote
2 answers
88 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 ...
Vince W.'s user avatar
  • 111
0 votes
1 answer
134 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 ...
8cold8hot's user avatar
  • 123
3 votes
0 answers
162 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,...
Huy Le's user avatar
  • 31
0 votes
0 answers
96 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: ...
Makogan's user avatar
  • 1,706
0 votes
1 answer
611 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 ...
Makogan's user avatar
  • 1,706
1 vote
0 answers
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]; <...
Googlebot's user avatar
  • 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 ...
Makogan's user avatar
  • 1,706
1 vote
0 answers
25 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 ...
Stamatis's user avatar
  • 111
1 vote
0 answers
112 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 ...
kampta's user avatar
  • 111
1 vote
2 answers
444 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....
Makogan's user avatar
  • 1,706

1
2 3 4 5