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
0 votes
0 answers
27 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
1 answer
34 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
0 votes
0 answers
15 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
0 votes
0 answers
27 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
1 answer
95 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 ...
0 votes
0 answers
33 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,449
1 vote
2 answers
47 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
0 votes
0 answers
23 views

How to determine polygon vertices?

I have an image in two colors - black and white, no halftones or other colors. It is known, that the only thing this image contains is a single solid filled polygon of the black color, and the rest of ...
  • 101
0 votes
0 answers
24 views

Can you estimate the shadow in a plane of an SDF?

I have an SDF and a plane. I want to generate either a square or a circle on the plane such that the orthogonal projection of the sdf on the plane (i.e. its orthogonal shadow) is guaranteed to be ...
  • 1,449
0 votes
0 answers
33 views

Improving dual contouring convergence

I have my own implementation of dual contouring. Right now I am getting the following output: This is decent, but I am trying to get a better result (i.e. try to reduce the low level voxel noise as ...
  • 1,449
0 votes
1 answer
51 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
3 votes
0 answers
73 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
0 votes
0 answers
55 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,449
0 votes
1 answer
136 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,449
1 vote
0 answers
37 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
0 answers
30 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,449
1 vote
0 answers
21 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
0 answers
60 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
2 answers
208 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....
  • 1,449
1 vote
1 answer
68 views

Help understanding tangent from dot product and max distance from component wise vector multiplication

I am looking through this code and seeing two things which confuse me (well, the whole functions does) in the top functions. First, dir * p where ...
0 votes
0 answers
78 views

Methods to interpolate between 2 topologically identical 3D meshes

I have 2 3D surface meshes. These meshes have vertex-correspondence and have the same topology (same edges and triangles connecting the vertices). However, the vertex positions (3d coordinates) are ...
0 votes
1 answer
56 views

HalfEdge: How to get list of all faces from one face

I need to, starting from one face, iterate over the rest of the faces until I reach the first facet. For this I can use twin, start, end or other info of halfedges, faces, vertex. That is, I need to ...
1 vote
0 answers
26 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. ...
0 votes
1 answer
40 views

Computing heat diffusion creates weird results

I am trying to model heat diffusion on the surface of a mesh. I annexed the most important bits of theory about this topic as screenshots on the question see the bottom. The crux of the issue is we ...
  • 1,449
2 votes
1 answer
108 views

results of Curved PN-Triangles algorithm has visible edges

I implemented the curved PN triangles algorithm described in this paper to smooth geometry in real time. After the implementation was finished (in glsl) I realized, that this algorithm smooth the ...
  • 551
3 votes
0 answers
39 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. ...
2 votes
0 answers
48 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 ...
5 votes
1 answer
93 views

Existing method to automatically fill in this sort of concavity in meshes?

I am working with a PWP3D-like algorithm that renders silhouettes of a mesh in order to segment a frame of video and update an object's pose. Because it is only the silhouettes of the mesh that matter,...
0 votes
1 answer
36 views

Differential or intersection of islands of 2D polygons in different layers

I have a 2D layer/section containing the 2D polygons colored in shades of green. I have another layer containing the 2D polygons colored in shades of blue. I intend to figure out how different are ...
0 votes
0 answers
73 views

Changing Coordinate Frames with Affine Transformations

Stuck with this questions could I get some help. where uA and vA are two orthonormal vectors indicating the two axes, and oA is the origin. Suppose that all three frames of reference shown in ...
0 votes
0 answers
42 views

Pinhole Projection & Spheres [duplicate]

Would someone be able to explain why a sphere when projected with the pinhole projection model has its projected 2D image be an ellipsis. IN particular when the sphere is not directly in front of the ...
2 votes
0 answers
100 views

How to compute a bounding tetrahedron

I'm wondering how to compute a bounding tetrahedron from a set of points so i can initialize a delaunay triangulation My first approach was to find the bounding box to my set of points and then ...
  • 53
1 vote
1 answer
40 views

Subdivision scheme where the faces and edges have weights (not necessarily scalar weights)

Subdivision schemes work by considering the vertices and their connectivity information to calculate averaging weights. However, other than specifying which vertices are connected, and perhaps which ...
  • 1,449
1 vote
3 answers
129 views

Silhouette below 3D model

There are some 3D applications which can cast shadow or silhouette below 3D models. They render pretty fast and smooth. I wonder what kind of technology is the standard procedure to get 3D model ...
0 votes
0 answers
47 views

Algorithm to select regions based on curvature on a mesh

I'm trying to understand how to implement an algorithm similar to the one used by Magics' mark surface tool, you can see such behaviour on this video. Quoting the video: "Basically with this tool ...
user avatar
0 votes
2 answers
94 views

Rounding a 3D corner with Subdivisions

Following the instructions from this post on Stack Overflow, I have been able to find points A, B, and C from points V1, V2, and V3 and a radius value (code below). I would like to be able to find a ...
0 votes
1 answer
37 views

In place sorting of a half edge DS?

Cross posting from SO because I didn;t know where to put this question. I have an implementation of the half edge and I am trying to sort the edges such that edge n+1 is the pair of edge n. Setup I ...
  • 1,449
3 votes
1 answer
119 views

Why is the valence of regular vertices 6?

So I recently learnt that supposedly for any mesh, and pretty much any scheme, the valence of regular vertices must be 6. It seems to be related to the Euler-Poincare formula but I have not been able ...
  • 1,449
2 votes
0 answers
79 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
1 answer
119 views

Improve accuracy of mesh gradient?

So to make it simple. I currently use a method I found online to compute the gradient of a scalar field of a mesh. To test how accurate this is, I made a sphere and followed the gradient direction of ...
  • 1,449
3 votes
1 answer
60 views

Mis understanding of the Heat Method

I have been trying to understand a paper in CG for a while, called the Heat Method by Ken Many things have clicked but I don't fully understand it yet. In particular. In the following $u$ is a vector ...
  • 1,449
4 votes
1 answer
110 views

Gradient descent (Not ML) on arbitrary meshes

So I am doing a gradient descent like algorithm on the surface of a mesh and I just noticed something: The above is the geodesic gradient (the distance to a single vertex) Look at where the ear ...
  • 1,449
2 votes
1 answer
601 views

Detect collision for non axis-aligned bounding boxes

in my application, I needed to detect collision between 2 3D objects. To make it simple I can represent a object as a bounding box. So actually the task reduced to detect collision between 2 boxes in ...
  • 121
1 vote
1 answer
427 views

Calculating the gradient of a tetrahedral mesh

How can I compute the gradient for a tetrahedral mesh (3D)? For triangular mesh, I got an answer from the following post Calculating the gradient of a triangular mesh How can I get a similar formula ...
  • 13
2 votes
2 answers
138 views

Smart half edge iteration?

In my HE implementation, half edges are stored in an array. When I iterate over the edges, I color all the HE black, and when I do an operation on an edge (e.g edge splitting) I mark both the current ...
  • 1,449
1 vote
2 answers
216 views

Discrete Gradient?

I am trying to understand how to get the discrete gradient of a mesh that is being used as the input of some function $f$. In other words for every vertex $v$ there is a scalar quantity $s$ associated ...
  • 1,449
1 vote
2 answers
79 views

Heat Method (Crane et Al) How do we pick u?

The heat method is a very interesting paper for distance computation: https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/paperCACM.pdf The idea behind the paper is that, heat travels along the ...
  • 1,449
0 votes
1 answer
90 views

Is the laplacian operator for meshes just the sum of the differences of neighbouring vertices?

I am starting to learn about the laplacian operator $\Delta = \nabla \cdot \nabla\phi(p)$ Which can be described as the divergence of the gradient of a scalar function $\phi$. This is equivalent to ...
  • 1,449
1 vote
0 answers
156 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. ...
  • 260
1 vote
1 answer
88 views

Approximating Geodesics in a half edge DS, how can I refine my mesh to get good approximations

I implemented Djikstra's shortest path algorithm to approximate Geodesics on arbitrary meshes. Djikstra's works, but I noticed a problem inherent to the discretization of my meshes. Consider the ...
  • 1,449