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.
69
questions with no upvoted or accepted answers
7
votes
0
answers
2k
views
Bump mapping a ray-traced sphere
I'm attempting to apply a height map to a ray-traced sphere. The height map is stored as a texture. I have the intersection point on the sphere $p$, and I compute the normal vector at that point $N = ...
5
votes
0
answers
135
views
Is there any open-source implementation of n*log(n) visibility graph construction algorithm?
Is there any open-source implementation of n*log(n) visibility graph construction algorithm?
I'm trying to understand S. K. GHOSH and D. M. MOUNT sweep line algorithm, but it's known for having very ...
4
votes
0
answers
564
views
Algorithm to remove inner faces of a triangulated mesh
I'm trying to figure out the surface area of a mesh that is the result of various CSG union operations between an arbitrary number of other meshes by summing up the same property of each one of it's ...
4
votes
0
answers
187
views
Generate complex (non-convex) polyhedron UV mapping
I need to find an approach to the problem of generating texture maps for non-convex polyhedrons without using a design tool like Maya. Specifically, I am mapping simulation results data onto a 3D ...
3
votes
0
answers
161
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,...
3
votes
0
answers
42
views
Is this way of transforming QMC samples into barycentric tri coordinates agnostic to mesh-topology?
While I'll try my best to give all relevant info in all possible brevity below, please refer to the spoiler and link at the bottom of the post for the (more lengthy) original description if needed.
...
3
votes
1
answer
227
views
Efficiently generating mesh for self-generated voxel grid
I'm working on an app that lets users construct a 3D house, with the ultimate goal of it being 3D printable. I use various materials in the form of a height map constructed from an image, like this ...
3
votes
3
answers
227
views
Estimating the position of vertexes in a 3D model
Introduction to my project:
We are machine learning scientists and working on a biomedical system for tracking tongue for speech pathology using a technology called EMA (Electromagnetic articulography)...
3
votes
0
answers
94
views
NURBS Weights De Boor's Algorithm
I am having trouble implementing an algorithm for 3rd degree NURBS.
I have been able to program 2nd degree ones from the equations described here but I am not able to derive an equation for Rational B-...
3
votes
0
answers
129
views
How can you avoid thin triangles in a parametric shape in a smart way?
I have created a closed 3D mesh using a parametric function. The shape is constructed by taking an arbitrary closed b-spline and scaling it based on one of the parameters (similar idea to a parametric ...
2
votes
0
answers
36
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 ...
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 ...
2
votes
0
answers
45
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, ...
2
votes
0
answers
54
views
Divide mesh according to level of detail
Background
I need to remesh by OpenVDB, like what Blender remesh does:
Voxel
Uses an OpenVDB to generate a new manifold mesh from the current geometry while trying to preserve the mesh’s original ...
2
votes
0
answers
183
views
Ear-clipping algorithm for non-planar polygons
I was looking into the ear-clipping algorithm for triangulating simple polygons. I have successfully implemented it on planar polygons. However if polygon is non-planar the algorithm breaks down. ...
2
votes
0
answers
196
views
Procedural Generation of 4D Shapes
I'm curious if anyone has any insight into how one might procedurally generate 4D objects, as showcased in Miegakure (or the developer's other game, 4D Toys ).
I built a program a while back to do ...
2
votes
0
answers
624
views
HalfEdge data structure in openmesh, create_face function explanation
Does anyone have experience with open-mesh or computational geometry and can kindly explain what exactly happens in the function below?
...
2
votes
0
answers
92
views
Intersecting Frusta
I am trying to determine whether two frusta intersect in 3D space and to quantify this intersection as a percentage of one frustum volume (eg. 100% intersection meaning that the two frusta occupy the ...
2
votes
0
answers
122
views
Algorithm for 3D mesh model segmentation to chart
I'm trying to implement a segmentation model which will divide a 3d mesh model into charts. But I'm having really hard time to find resources in the web. The papers and some other places these ...
2
votes
0
answers
206
views
Transform a centered isosceles trapezoid in a rectangle in 2-D
I must convert a isosceles trapezoid to a rectangle in 2-D with a shearing transformation (or with 2 shearing transformations). The isosceles trapezoid is centered in the origin of axes.
It is right ...
1
vote
0
answers
21
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 ...
1
vote
1
answer
115
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 ...
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 ...
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 ...
1
vote
1
answer
171
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 ...
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:
...
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.
1
vote
0
answers
45
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
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
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 ...
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 ...
1
vote
0
answers
65
views
How to extrude a face from a selected mesh in Babylon,js using the ExtrudeShape method?
I'm trying to extrude a face from a selected mesh in Babylon.js using the ExtrudeShape but can't figure out why I got flipped faces.
The bottom extrusions always comes flipped for a reason I ignore.
...
1
vote
0
answers
189
views
Isosurface with cracks between LODs
I have an octree containing different LODs of an isosurface that was extracted using Marching Cubes.
Neighbouring chunks show surfaces that do not line up if they have different LOD. See image below.
...
1
vote
0
answers
95
views
What other geometry processing data structures are there?
I essentially know of 2 geometry processing data structures. one is the half edge (which has some really nice properties, but can't represent non manifold meshes nor tet meshes).
The other is an ...
1
vote
0
answers
302
views
BSP tree rendering
As a little project, I'd like to implement a BSP merging algorithm for Boolean operations on solids. But to even tell whether it works, I need some way to render the BSP tree. In other words, I have a ...
1
vote
0
answers
37
views
Boundary Smoothing Algorithms
I have a 2-manifold with boundary, built with marching cubes. Are there any well-known algorithms for smoothing its boundary edges?
Most of the papers I found are concerned with smoothing the surface....
1
vote
0
answers
55
views
Algorithm for randomly generating polyhedrons?
I want to randomly generate polyhedrons which need not be convex. What is the most efficient way for doing so?
I can think of an algorithm for generating random convex polyhedrons, but am unable to ...
1
vote
0
answers
484
views
How to apply scale, translate, rotate with different origin and get new rectangle coordinates
I was reading other questions in this topic but I couldn't apply any viable solution to solve my use case.
I have a crop area described with two dimensions (cropWidth, cropHeight)
I can easly compute ...
1
vote
0
answers
92
views
What is the history of the bounding box concept?
A bounding box, if I understood correctly is a box that frames the box in which we work. It allows to align the box on the left, on the right, in the center.
Its ...
1
vote
0
answers
53
views
Ray tracing and mesh extraction
I have been reading this paper : 3D Surface Extraction using Incremental Tetrahedra Carving .pdf
I have already generated a tetrahedra for my mesh and I would like to create a surface mesh. I can't ...
1
vote
0
answers
40
views
Program to visualize geodesics and linear projection of an ellipsoid simultaneously
I am trying to solve a problem in computer graphics but to do it I need to be able to see a comparison of geodesic lines and straigth line projections on the ellipsoid.
I have not been able to ...
1
vote
0
answers
57
views
Rectangle bounds of isometric object to isometric bounds
This might sound confusing, but this is what I'm trying to achieve:
project to:
I already have an algorithm in my mind, where we simply detect the corners touching the Cartesian rectangle and ...
1
vote
0
answers
65
views
Pattern recognition on 3d geometry
How can I identify that an object is patterned (or symmetrical at least?). For example, I give to the algorithm a wall of red bricks. I want it to recognize that if it takes 1,2 or 4 bricks, it's ...
0
votes
0
answers
22
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 ...
0
votes
0
answers
17
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. ...
0
votes
1
answer
99
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 ...
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:
...
0
votes
0
answers
41
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 ...
0
votes
0
answers
59
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 ...
0
votes
0
answers
245
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 ...