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
0answers
7 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 ...
0
votes
0answers
20 views

What's a compeling use case for geodesic distance in a real world CG application

I'd like to find a concrete example of how geodesic distance can be useful in CG such as games or the movie industry. (An example I like for mean curvature is when it's used to fake ambient occlusion. ...
2
votes
1answer
26 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 ...
3
votes
0answers
36 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
0answers
38 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
1answer
80 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
0answers
23 views

Parametrising $\mathbb{R^3}$ coordinates using a mesh with barycentric coordinates, and signed distance to the mesh

I need to parametrise $\mathbb{R^3}$ coordinates relative to a mesh, which is a deformed $UV$ sphere with triangular faces. Every vertex on the mesh has a $UV$ coordinate, and I want to associate ...
0
votes
0answers
23 views

Using 2D point/polygon algorithms on polygons lying on a arbitrary plane

Is there an efficient method to apply 2D point/polygon algorithms on general planar points. For example, I need to triangulate a polygon where the input is a list of ordered points. The algorithm ...
0
votes
1answer
27 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
0answers
30 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
0answers
31 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
0answers
62 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 ...
1
vote
1answer
35 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
vote
3answers
91 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
0answers
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 ...
0
votes
2answers
88 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
1answer
35 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 ...
3
votes
1answer
57 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 ...
2
votes
0answers
46 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. ...
1
vote
1answer
53 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 ...
3
votes
1answer
47 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 ...
4
votes
1answer
57 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 ...
2
votes
1answer
233 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 ...
1
vote
1answer
125 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 ...
2
votes
2answers
114 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
vote
2answers
82 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
vote
2answers
70 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 ...
0
votes
1answer
34 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
vote
0answers
117 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. ...
0
votes
0answers
8 views

MMP algorithm, no metion of “in window” intersections

If you are familiar with the MMP algorithm for geodesic finding, you know an important part of the algorithm revolves around solving intersections of windows. I am running into a case that I don't see ...
1
vote
1answer
75 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
vote
1answer
59 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 ...
0
votes
1answer
42 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 ...
2
votes
1answer
132 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 ...
0
votes
0answers
27 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==...
1
vote
1answer
52 views

Finding geodesics on a mesh?

What are some state of the art methods/algorithms to find geodesics on arbitrary manifold meshes?
3
votes
1answer
95 views

Are some 3D objects “solid”? Do they have internal density? If so, when, and in which file formats?

I am more or less a complete novice in the field of 3D modeling. I understand the basics of a polygon mesh and a texture; however, it was always my understanding that 3D models were, effectively, &...
1
vote
2answers
297 views

Calculate normals from vertices

Assume you have a list of vertices and their connectivity information. (I.e you can find all the adjacent edges and faces to each vertex). What is a good approach to calculate a normal from this ...
1
vote
1answer
187 views

What is the reason that a boolean operation between two almost identical 3D triangular meshes fails?

I have been trying to detect defects on "before-and-after" meshes, by finding the boolean difference between them, to no avail. I tried these two Python libraries(algorithms run in C++) but their ...
0
votes
1answer
60 views

How do you compute the winding number of a closed poly curve?

Pretty much the title, given a closed curve in 2D, defined by a set of points, and a point. What's the algorithm to calculate the winding number of that curve, point pair?
0
votes
1answer
75 views

constant pixel width for any scale

I have a standard 3d camera/projection/model setup that renders rectangles with a WebGL shader. Users can zoom out and fly anywhere. I want to make sure that regardless of the scale, width of the ...
3
votes
0answers
110 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 ...
0
votes
1answer
50 views

Determining shortest vector between a ray and an axis-aligned 3D bounding box (correcting a near-miss)

I have a situation where (due to floating point error) a ray that is known to hit a bounding box fails due to floating point error. (1e-8 or so) Expanding the box is not an acceptable solution in my ...
1
vote
1answer
164 views

How to handle Half edge boundary edge iteration from vertex?

Ok so let's say we have a portion of a mesh that looks somewhat like this: A triangle fan with one of the triangles removed. If that triangles was not removed, we could get all the edges adjacent to ...
2
votes
1answer
69 views

How to subdivide faces with a half edge DS?

Assume we have a mesh represented as a half edge datastructure. We want to subdivide faces without introducing unnecessary vertices (i.e the new number of vertices must be exactly V + E where V is the ...
1
vote
0answers
70 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
0answers
110 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
1answer
93 views

Generating the end caps of a cylinder using triangle strips for use in a geometry shader

I know how to generate the walls of a cylinder with triangle strips and the caps with triangle fans, but since I am working inside a geometry shader, I can only output triangle strips, so I am kind of ...
1
vote
1answer
144 views

How to compute normal in quartic Walton-Meek's Gregory patch in tessellation shader?

I am programing a tessellation shader in OpenGL which computes the quartic Walton-Meek's Gregory patch. I am searching for a local G1 method with good shading/visual results. So I am trying this patch....
4
votes
2answers
130 views

Creating a Smooth 3D Mesh from a 2D Outline

I am trying to find (or maybe create) an algorithm for creating a smooth, rounded 3D mesh given a 2D outline. I'm trying to recreate a system from a Gamecube game called Amazing Island, and you can ...