Stack Exchange Network

Stack Exchange network consists of 175 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.

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

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

I am using the Bresenham algorithm from wikipedia: ...
3
votes
1answer
98 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
34 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
85 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
37 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
156 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
52 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
76 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 ...
2
votes
0answers
52 views

Intersecting Frusta

I am trying to determine whether two frusta intersect in 3D space and to quantify this intersection as a percentage of one frustum volume (eg. 100% intersection meaning that the two frusta occupy the ...
2
votes
2answers
143 views

Rotate a model or a view with mouse input to produce intuitive results

I am writing 3D graphics software in Java using the LibGDX framework (which is a front-end for OpenGL), and am baffled by a transformation problem. How do I rotate the orientation of the camera or ...
3
votes
0answers
86 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
40 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
174 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
56 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
125 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
1answer
84 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
79 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 ...
3
votes
1answer
140 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{...
6
votes
1answer
152 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
47 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
80 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
77 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
50 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
104 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
44 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
192 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
127 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
41 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
80 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 ...
7
votes
1answer
117 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 ...
3
votes
1answer
144 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
74 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
673 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
75 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 ...
3
votes
1answer
290 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 ...
6
votes
1answer
205 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
250 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
43 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
165 views

Convex non simple polygon?

Existence question: Can there exist a convex polygon witch is not a simple polygon?
1
vote
0answers
52 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
696 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
129 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
54 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
229 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
278 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 ...
4
votes
2answers
226 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 ...
5
votes
0answers
113 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 ...