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
2answers
65 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
20 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
46 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
vote
0answers
37 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
28 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
37 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
48 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
vote
1answer
51 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
38 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
110 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
61 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
67 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
29 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
98 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
7 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
73 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
37 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
38 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
116 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
25 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
48 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
78 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
143 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
87 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
45 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
67 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
92 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
84 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 ...
0
votes
0answers
58 views

Mesh boolean and amount of triangles

Inspired by BSP tree mesh operations, I've implemented an operation that takes a mesh X, a BSP tree/sequence of planes, and creates a new mesh, by iteratively slicing mesh X by these planes in some ...
2
votes
1answer
52 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
63 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
89 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
55 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
132 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....
0
votes
0answers
13 views

Mayavi installation code in Jupyter?

How can i install mayava in jupyter notebook. I tried this code but it doesn't work. $jupyter nbextension install --py mayavi --user Thanks
4
votes
2answers
94 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 ...
1
vote
1answer
44 views

Stecklov operator vs Laplacian operator

There's one paper published at siggraph that captured my attention : Steklov Spectral Geometry. I'm not an expert in geometry processing, but I'm trying to learn as much as I can. You can easily read ...
2
votes
1answer
77 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 ...
1
vote
0answers
28 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
1answer
61 views

Volume of Intersection of Cube and Sphere

Is there any way to compute the volume when a sphere intersects a AABB(cube), with different centers. Also i want to be able given a percentage of sphere's volume to to place the sphere's center in a ...
0
votes
0answers
29 views

How can I create multivariable function plotting software

I have finished Dennis Ritchie's C book, and I would like to create my own plotting software for enhancing my programming skill,I want sources,books or anything to reach this goal.Thanks for answers.
1
vote
2answers
96 views

Techniques for rendering high polycount models

I would like to know what common techniques are used for rendering large models, when using rasterisation within a graphics API, for example OpenGL or Vulkan. For example if I had a model with >10 ...
4
votes
1answer
113 views

What are affine covariant regions

I am trying to understand this seminal paper. I read this post on what affine transformations and my understanding is that affine transformations are transformations that preserve parallelism of lines ...
0
votes
0answers
51 views

RGB map into numerical data

the image below uses an RGB scale (the values of the scale are displayed on the image) to show the magnetic field strength at each point on the map. I've been struggling to find a way to convert this ...
1
vote
0answers
37 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 ...
2
votes
1answer
80 views

Why the Bresenham's algorithm does not work for those two points?

I am using the Bresenham algorithm from wikipedia: ...
3
votes
1answer
738 views

Calculating the gradient of a triangular mesh

This question is regarding a homework assignment (want to be upfront because many people on stack exchange don't like helping with homework questions). I have a triangular mesh, which is defined by a ...
0
votes
0answers
36 views

Cover a polygon with least amount of parallelograms

I am solving the task that is as follows: Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside. Goal: to cover it with 2 (at least) or ...
2
votes
0answers
274 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? ...