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
Filter by
Sorted by
Tagged with
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 = ...
Walt Donovan's user avatar
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 ...
Ibraim Ganiev's user avatar
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 ...
Liordino Neto's user avatar
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 ...
Rob Perkins's user avatar
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,...
Huy Le's user avatar
  • 31
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. ...
Herbert Jensch's user avatar
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 ...
andygeers's user avatar
  • 193
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)...
Mike Zadeh's user avatar
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-...
Felipe Gutierrez's user avatar
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 ...
Makogan's user avatar
  • 1,696
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 ...
Peter Marshall's user avatar
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,696
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, ...
Makogan's user avatar
  • 1,696
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 ...
Megidd's user avatar
  • 133
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. ...
Lenny White's user avatar
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 ...
mike's user avatar
  • 121
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? ...
user8469759's user avatar
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 ...
Francesco's user avatar
  • 121
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 ...
Tahlil's user avatar
  • 81
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 ...
Nick's user avatar
  • 321
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 ...
StefanoScolari's user avatar
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 ...
lightxbulb's user avatar
  • 2,226
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,696
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
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 ...
veggieg's user avatar
  • 31
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
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,696
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]; <...
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,696
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
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. ...
tawfikboujeh's user avatar
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. ...
Bram's user avatar
  • 270
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 ...
Makogan's user avatar
  • 1,696
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 ...
John P's user avatar
  • 111
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....
Denisof's user avatar
  • 111
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 ...
Aalok_G's user avatar
  • 111
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 ...
Jacek Pudysz's user avatar
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 ...
AndréC's user avatar
  • 111
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 ...
Andre Ahmed's user avatar
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 ...
Makogan's user avatar
  • 1,696
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 ...
Test's user avatar
  • 31
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 ...
Marouane's user avatar
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 ...
Penguin1068's user avatar
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. ...
Miguel's user avatar
  • 1
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 ...
Makogan's user avatar
  • 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: ...
Makogan's user avatar
  • 1,696
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 ...
Lady Be Good's user avatar
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 ...
Liam Kelly's user avatar
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 ...
Thomas's user avatar
  • 1,245