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
1 vote
1 answer
41 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 ...
user avatar
0 votes
0 answers
26 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 ...
user avatar
  • 1,447
1 vote
2 answers
46 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 ...
user avatar
  • 111
0 votes
0 answers
20 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 ...
user avatar
  • 101
0 votes
0 answers
23 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 ...
user avatar
  • 1,447
0 votes
0 answers
26 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 ...
user avatar
  • 1,447
0 votes
1 answer
42 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 ...
user avatar
  • 123
3 votes
0 answers
50 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,...
user avatar
  • 31
0 votes
0 answers
42 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: ...
user avatar
  • 1,447
0 votes
1 answer
70 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 ...
user avatar
  • 1,447
1 vote
0 answers
34 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]; <...
user avatar
  • 131
1 vote
0 answers
29 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 ...
user avatar
  • 1,447
1 vote
0 answers
20 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 ...
user avatar
  • 111
1 vote
0 answers
47 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 ...
user avatar
  • 111
1 vote
2 answers
200 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....
user avatar
  • 1,447
1 vote
1 answer
64 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 ...
user avatar
0 votes
0 answers
61 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 ...
user avatar
0 votes
1 answer
43 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 ...
user avatar
1 vote
0 answers
23 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. ...
user avatar
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 ...
user avatar
  • 1,447
2 votes
1 answer
91 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 ...
user avatar
  • 489
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. ...
user avatar
2 votes
0 answers
45 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 ...
user avatar
5 votes
1 answer
89 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,...
user avatar
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 ...
user avatar
0 votes
0 answers
60 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 ...
user avatar
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 ...
user avatar
2 votes
0 answers
95 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 ...
user avatar
  • 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 ...
user avatar
  • 1,447
1 vote
3 answers
122 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 ...
user avatar
0 votes
0 answers
45 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
93 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 ...
user avatar
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 ...
user avatar
  • 1,447
3 votes
1 answer
108 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 ...
user avatar
  • 1,447
2 votes
0 answers
71 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. ...
user avatar
2 votes
1 answer
116 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 ...
user avatar
  • 1,447
3 votes
1 answer
58 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 ...
user avatar
  • 1,447
4 votes
1 answer
100 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 ...
user avatar
  • 1,447
2 votes
1 answer
550 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 ...
user avatar
  • 121
1 vote
1 answer
377 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 ...
user avatar
  • 13
2 votes
2 answers
136 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 ...
user avatar
  • 1,447
1 vote
2 answers
187 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 ...
user avatar
  • 1,447
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 ...
user avatar
  • 1,447
0 votes
1 answer
83 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 ...
user avatar
  • 1,447
1 vote
0 answers
150 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. ...
user avatar
  • 260
1 vote
1 answer
87 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 ...
user avatar
  • 1,447
2 votes
1 answer
131 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 ...
user avatar
  • 183
0 votes
1 answer
56 views

Fast and exact Geodesics on meshes, Backtracking confusion

The following is an excerpt from a 2005 paper on geodesics on triangular meshes, taken from section 3.5 In this case $p$ is a point on some arbitrary face in a mesh, $p'$ is a point on one of the 3 ...
user avatar
  • 1,447
2 votes
1 answer
219 views

Dynamic Ray-Triangle Intersection

I am working on a small simulation software which has a 3D Renderer that is using OpenGL. I render objects to the screen as triangle meshes. To be able to select the triangles on the screen, I have ...
user avatar
  • 23
0 votes
0 answers
35 views

MMP Geodesic algorithm I need clarification

I am reading the 1987 paper on Geodesics on polyhedra and I am confused on something. The paper states: If $I1==NIL$, the channel is simply that part of $f’$ to the left of $\beta_2c_2$; and if $I2==...
user avatar
  • 1,447