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
1
vote
0answers
19 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
0answers
18 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
23 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.
0
votes
0answers
13 views

how apply edge collapsing within selected surface

I'm using CGAL edge collapsing to remove edges on mesh and it's working successfully . But I want to run the edge collapsing process within selected surface on mesh viewer . I preview the Geomview (....
1
vote
2answers
75 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 ...
3
votes
0answers
23 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
30 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
63 views

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

I am using the Bresenham algorithm from wikipedia: ...
3
votes
1answer
118 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
35 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
101 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
40 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
329 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
53 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
97 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
165 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
88 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
41 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
185 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
62 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
136 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
89 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
80 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
142 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
95 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
51 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
45 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
216 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
137 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
85 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
119 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
34 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
154 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
79 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
726 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
81 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
311 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
216 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
253 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
44 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
171 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
741 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 ...