Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
0answers
58 views

How can you avoid thin triangles in a parametric shape in a smart way?

I have created a closed 3D mesh using a parametric function. The shape is constructed by taking an arbitrary closed b-spline and scaling it based on one of the parameters (similar idea to a parametric ...
2
votes
1answer
38 views

Remove orphaned geometry after Constructive Solid Geometry operation

I have used a library to perform a Constructive Solid Geometry difference operation, which has left me with orphaned geometry as well as imperfections. Is there an approach/algorithm that will allow ...
0
votes
3answers
132 views

Rotation of a random unit vector at a point in 3D space by an angle

I have a scenario where I need rotate a vector ( unit vector) at a point in space by an angle along Z-axis. Is it possible to help me to understand a procedure to achieve this. I'm using vb.net ...
1
vote
0answers
34 views

How to apply scale, translate, rotate with different origin and get new rectangle coordinates

I was reading other questions in this topic but I couldn't apply any viable solution to solve my use case. I have a crop area described with two dimensions (cropWidth, cropHeight) I can easly compute ...
5
votes
1answer
101 views

Radiative Transfer Equation for Photorealistic Rendering

I've recently become interested in photorealistic rendering, and I've been looking at the different rendering philosophies. I read this Disney Research bachelor's thesis, which states both the ...
0
votes
0answers
17 views

How to map a subdivided cube into an array

Assume we start with an axis aligned cube at known origin/corner Origin with known dimension Dim. This cube is divided into 8 equally big cubes with length Dim/2 and corners Origin, Origin + (0,0,...
0
votes
1answer
63 views

Projection of a Polyhedron on xy Plane with CGAL

I am trying to project a Polyhedron on the xy plane with CGAL, which should result in a (2D) polygon. I wonder, if there is an elegant way to achieve it? Of course, I can iterate over all surfaces ...
1
vote
0answers
72 views

What is the history of the bounding box concept?

A bounding box, if I understood correctly is a box that frames the box in which we work. It allows to align the box on the left, on the right, in the center. Its ...
4
votes
1answer
107 views

Triangulation of vertices of an ellipsoid

I have the parametric model of an ellipsoid like this: \begin{cases} x=a_1\,cos \,\eta \:cos\,\omega & -\pi\leq\omega\leq\pi \\𝑦 = 𝑎_2\,cos\,\eta\:sin\,\omega \\ z=a_3\,sin \,\eta & -\frac{...
7
votes
1answer
150 views

Topological Sweep

I need to identify certain topological entities (circular holes) in a given geometry, that is, given the boundary representation of a solid, I need to identify the exact coordinates of all holes in ...
1
vote
0answers
46 views

Tanget plane of an image

My problem is about tangent plane. I have an image (m by n). I obtain surface normal vector using machine learning methods. Then i would like to obtain tangent plane for this surface normal. To ...
2
votes
1answer
68 views

Camera rotation effect on pitch, yaw, roll

I'm trying to calculate what the effective pitch, yaw, and roll are for an image. I have the image's original pitch, yaw, and roll. Then the image (camera) is rolled at some arbitrary angle. I want ...
1
vote
0answers
71 views

Ray Tracer Shadowing

So I'm working on an assignment where we have to design a simple ray tracer. The program has two objects that it can use, sphere and cube. It can render the cube and spheres, it also does shading on ...
0
votes
1answer
47 views

How does image resolution change(process involved in calculation), when a screen on phone is rotated?

What is the process involved in calculating the resolution of image to be displayed when the screen of my phone(android) is rotated? My screen resolution is 1920x1080. It displays some videos only in ...
3
votes
1answer
99 views

Heirarchy in Euler rotations

Why is there necessarily a hierarchy in Euler rotations? For example I need to decide that I want x to affect y and z z to affect y y to affect nothing. What if ...
1
vote
0answers
39 views

Ray tracing and mesh extraction

I have been reading this paper : 3D Surface Extraction using Incremental Tetrahedra Carving .pdf I have already generated a tetrahedra for my mesh and I would like to create a surface mesh. I can't ...
3
votes
1answer
125 views

How to smooth out a voxel grid?

So I am facing the following issue. Say I have a minecraft like mesh (i.e I have a bunch of cubes on top of one another). I wish to smooth out this mesh in such a way that only the regions where ...
3
votes
1answer
95 views

Rounding a corner formed by Arc and Line

Given shapes like these, which contain just Arcs and lines, I want to round all its corners with certain radius. I know the vertices of the lines & arcs these shapes. I can round the corners of a ...
3
votes
2answers
39 views

How to get the length of paths in an given font/character

I wan't create some LED-rope text, using some script font, like the following: For this I need somewhat estimate the needed length of the LED-rope for the given letter (or combinations of letters). ...
4
votes
1answer
62 views

Vertices of a regular polygon given the incircle radius

How can I find the vertices of a polygon (specifically hexagon) given the radius of the incircle? I want to calculate the vertices of a polygon given the face-to-face distance (inscribed circle ...
8
votes
1answer
113 views

How can I check if a polygon can completely contain a circle of a certain radius?

How can I check if a polygon (can also be irregular) can completely contain a circle of a certain radius? I do not want to actually draw a circle inside the polygon but just a boolean outcome whether ...
1
vote
0answers
33 views

Program to visualize geodesics and linear projection of an ellipsoid simultaneously

I am trying to solve a problem in computer graphics but to do it I need to be able to see a comparison of geodesic lines and straigth line projections on the ellipsoid. I have not been able to ...
4
votes
1answer
114 views

Creating a vanishing point perspective shader

I have done my due hour of research before asking this question, it's a simple question, but I have found no hint at an answer online. I want the ability to extend an object infinitely in one ...
2
votes
0answers
56 views

Algorithm for 3D mesh model segmentation to chart

I'm trying to implement a segmentation model which will divide a 3d mesh model into charts. But I'm having really hard time to find resources in the web. The papers and some other places these ...
4
votes
1answer
501 views

What's the difference between geometric surface normal and shading surface normal?

In my opinion, geometric surface normal is the cross product of triangle edge vectors, and shading surface normal is the interpolation of the predefined normals at the three vertexes. I used Mitsuba ...
4
votes
1answer
66 views

human visual: relation of Distance and DPI

I was told that human's visual sharpness is 60 pixels per degree. As such, pixel per inch is approximately given by: PPI = 1/ (Distance * tg((1/60*pi/180) ) Is ...
4
votes
1answer
203 views

How to correct point cloud distortion

I am using Unreal Engine to export custom render passes for the scene depth in world units. Every pixel in the render pass has a value which is the distance from the camera to that pixel in standard ...
7
votes
1answer
137 views

List of triangles to minimum amount of convex polygons

I'm in search for an algorithm that takes the left side of the following graphic as an input and outputs a minimal amount of convex polygons as seen on the right side of the graphic. The input mesh ...
5
votes
2answers
234 views

How to describe a position of a point w.r.t the position and orientation of 3 other points

Is it possible to describe a position of a point $A$ (in 3D) w.r.t. the position and orientation of 3 other points? If so, how? FYI, the 3 other points lie on a plane, whereas the point $A$ is not on ...
1
vote
0answers
39 views

Rectangle bounds of isometric object to isometric bounds

This might sound confusing, but this is what I'm trying to achieve: project to: I already have an algorithm in my mind, where we simply detect the corners touching the Cartesian rectangle and ...
4
votes
1answer
134 views

Convex non simple polygon?

Existence question: Can there exist a convex polygon witch is not a simple polygon?
1
vote
0answers
46 views

Pattern recognition on 3d geometry

How can I identify that an object is patterned (or symmetrical at least?). For example, I give to the algorithm a wall of red bricks. I want it to recognize that if it takes 1,2 or 4 bricks, it's ...
2
votes
2answers
468 views

Extract visible vertices from a 3D geometry model

Let's assume we have a 3D model consisted of XYZ-formatted vertices (such as point cloud model). My problem is given the position and normal of camera or camera ...
2
votes
1answer
111 views

Compute area (not surface area) and perimeter of a mesh

I'm currently researching how to compute geometric properties of architectural shapes based on their 3D meshes, and am stuck for some time on the area and perimeter calculations. First, the area: ...
1
vote
0answers
43 views

3D sphere mesh with a predefined number of vertices and a given adjacency matrix of vertices

I need a 3D triangular sphere mesh with uniformly sampled vertices, say $V$, with a predefined adjacency. Is there a specific way to achieve that?
4
votes
2answers
221 views

Minimum requirements to uniquely represent a 3D object in space

Let's assume we have a 3D object (in 3D space). We get a single representation vertex from this whole 3D object. Given the fact that the object can be moved and rotated in the space in any direction, ...
4
votes
0answers
237 views

Algorithm to remove inner faces of a triangulated mesh

I'm trying to figure out the surface area of a mesh that is the result of various CSG union operations between an arbitrary number of other meshes by summing up the same property of each one of it's ...
5
votes
2answers
204 views

An algorithm to find the area of intersection between a convex polygon and a 3D polyhedron?

Suppose I have a set of points in 3D which are all co-planar, and which describe the vertices of a convex polygon. I know the coordinates of all of these vertices, I know the unit normal to the plane ...
6
votes
0answers
105 views

Is there any open-source implementation of n*log(n) visibility graph construction algorithm?

Is there any open-source implementation of n*log(n) visibility graph construction algorithm? I'm trying to understand S. K. GHOSH and D. M. MOUNT sweep line algorithm, but it's known for having very ...
3
votes
3answers
1k views

How to build a 3d model from 2d pictures

I have a series of MRI images. I want to build a 3D model out of it, which not only presents the surface, but also contains the inside structures. What kind of photogrammetry based method can realize ...
4
votes
1answer
112 views

The constructor of hyperboloid in pbrt-v3

The book omitted the explanation of the constructor of hyperboloid. Could someone give some explanations about: Why the arguments are two points? What are the meanings of ah and ch? Why is there a ...
4
votes
2answers
124 views

First steps towards CAD standard curve fitting

I am interested in building a program to accomodate the following workflow: A user begins with an arbitrary vector/CAD shape, which they wish to transfer onto paper without using a printer (there are ...
7
votes
0answers
803 views

Bump mapping a ray-traced sphere

I'm attempting to apply a height map to a ray-traced sphere. The height map is stored as a texture. I have the intersection point on the sphere $p$, and I compute the normal vector at that point $N = ...
4
votes
3answers
336 views

Fill the plane with pentagons as tightly as possible in a regular way

I wrote a small python script with recursion to create a "lattice" of non-overlapping pentagons. Below one can see the first stages of recursion. One can see that 5 small pentagons are missing in the ...
4
votes
1answer
513 views

Bevel/Chamfer algorithm for arbitrary 3D mesh

I can't find any paper about a bevel/chamfer algorithm for 3D mesh. Bevel has a lot of special cases (corners, different bevel profile, bevel larger than a face). I am looking for robustness. Do you ...
1
vote
1answer
154 views

Test if polygon edge is facing another polygon

How do I test to see if a polygon edge is facing another polygon? For the edge being tested to return true, the edge needs to be facing a polygon which has a different attribute than itself. In this ...
1
vote
1answer
43 views

Given two convex patches, how to find points/faces that have distance < x?

The title says it all, given two convex patches, how to find points/faces that have distance < x? Can I use GJK for this case? Convex patches are obtained from convex decomposition, see here. If ...
2
votes
2answers
210 views

Average point on sphere between 3 other points (spherical triangle)

I am trying to get a normal of a triangle on a sphere, however the normal equations (straight line) give the wrong answer. For the points: $$(-986.786743, -93.348259, -132.439041)\\ (210.731644, -...
2
votes
0answers
116 views

How does this function calculate normals of a mesh? [closed]

I have trouble understanding the following Javascript code. It calculates, given a mesh described by its vertices vs and indices ...
4
votes
2answers
479 views

Finding the nearest neighbor of polygons

I have a set of non-convex polygons and I want to merge them. I am able to find the connection between two polygons. If there are more than two polygons, one connection can intersect another polygon ...