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
1answer
11 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
31 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
45 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
43 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
30 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
1answer
95 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
1answer
40 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
28 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
95 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 ...
2
votes
1answer
71 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
0answers
25 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 ...
1
vote
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
115 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
75 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
131 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
79 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
44 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
56 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
90 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
77 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
57 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
49 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
87 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
52 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
128 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
89 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 ...
1
vote
1answer
64 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
27 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
59 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
28 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
110 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
79 views

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

I am using the Bresenham algorithm from wikipedia: ...
3
votes
1answer
671 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
266 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? ...
3
votes
0answers
49 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-...
1
vote
2answers
1k views

Very efficient/fast marching cube implementation

I was wondering if there's any known technique/algorithm that would compute a mesh generated by the marching cubes but hierarchically (like a divide and conquer strategy), in the implementation I know ...
1
vote
1answer
63 views

Simple Two Point Perspective of a Cube

I know this question may be a little basic, but still I haven't found an answer for it anywhere. Let's say I have a normalized cube; vertices at (+-0.5, +-0.5, +-0.5) If I render it on screen (...
0
votes
2answers
236 views

transformation from cartesian coordinates to spherical coordinates without calculations

Given this graph in the 3d cartesian coordinates i should figure out the spherical coordinates representation but without the use of calculations . I've been trying to solve this the whole day but i ...