Questions tagged [algorithm]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
26 views

Efficient method of mapping any RGB tuple onto a list of RGB indices, is using some kind of partition plane viable?

Suppose we want to convert an RGB image into a paletted image. As an example, we may have a 1024x1024 image, and we want to map it onto 512 unique colors. All the colors are RGB. This is a problem of ...
2
votes
1answer
58 views

How is raytracing performed in anisotropic media?

I wish to determine the path taken by a light ray between two points, $a$ and $b$, through an anisotropic medium. More specifically, this medium has an index of refraction which varies as an ...
1
vote
1answer
40 views

wall clock using bresenhams circle drawing algo

I am new to CG and I need to draw a wall clock using bresenhams circle algo . I have drawn a circle using this algo but how do I add minute and hour needle in it basically how do i add lines inside a ...
0
votes
0answers
54 views

Fractal dimension of landscape generated with Fournier's midpoint algorithm (recursive subdivision) is 2.0 no matter what. Why?

I am using Fournier's midpoint algorithm (recursive subdivision) to construct a landscape of 1025 x 1025 gridpoints, then I am using an advanced version of box counting to find fractal dimension, D. ...
2
votes
3answers
885 views

How can I get a signed distance (SDF) from a mesh?

I am trying to use constructive solid geometry (CSG) and boolean operators to combine various shapes and get the outer (possibly concave) hull. This seems to work okay when using primitive shapes like ...
1
vote
1answer
52 views

getting the outline of an arbitrary set of shape unions

I hope this is the right forum to ask this question. I want to experiment with procedurally generating some buildings, and as a first step I want to generate a 2D shape to use as a foundation for the ...
2
votes
1answer
49 views

results of Curved PN-Triangles algorithm has visible edges

I implemented the curved PN triangles algorithm described in this paper to smooth geometry in real time. After the implementation was finished (in glsl) I realized, that this algorithm smooth the ...
3
votes
0answers
38 views

Is this way of transforming QMC samples into barycentric tri coordinates agnostic to mesh-topology?

While I'll try my best to give all relevant info in all possible brevity below, please refer to the spoiler and link at the bottom of the post for the (more lengthy) original description if needed. ...
2
votes
0answers
42 views

Divide mesh according to level of detail

Background I need to remesh by OpenVDB, like what Blender remesh does: Voxel Uses an OpenVDB to generate a new manifold mesh from the current geometry while trying to preserve the mesh’s original ...
5
votes
1answer
83 views

Existing method to automatically fill in this sort of concavity in meshes?

I am working with a PWP3D-like algorithm that renders silhouettes of a mesh in order to segment a frame of video and update an object's pose. Because it is only the silhouettes of the mesh that matter,...
0
votes
0answers
41 views

Under what conditions does a mesh operation cause the mesh become non-manifold and how to avoid it?

I'm implementing some mesh operations (e.g. edge collapse, edge split, edge flip etc) and need to ensure applying such operations does not cause the mesh to become non-manifold. However, I'm not sure ...
0
votes
0answers
18 views

What is the way to calculate NCC based template matching in linear time?

The complexity of the NCC based template matching is O(n x m x N x M) where N x M is the size of the image and n x m is the size of the template. The commercial machine vision libraries such as HALCON ...
0
votes
0answers
26 views

Using 2D point/polygon algorithms on polygons lying on a arbitrary plane

Is there an efficient method to apply 2D point/polygon algorithms on general planar points. For example, I need to triangulate a polygon where the input is a list of ordered points. The algorithm ...
0
votes
1answer
30 views

Differential or intersection of islands of 2D polygons in different layers

I have a 2D layer/section containing the 2D polygons colored in shades of green. I have another layer containing the 2D polygons colored in shades of blue. I intend to figure out how different are ...
0
votes
1answer
75 views

Rotate a Bitmap with Shearing

I am rotating a bitmap using the three shear algorithm documented in these articles [1][2]. From about 0-90°, the quality is acceptable, but beyond that it gets progressively more distorted until it's ...
0
votes
0answers
53 views

What is Filter Lite dithering, and how do I implement such an algorithm?

I've been researching online for fast dithering algorithms that could give my users a variety to choose from. I have implemented Floyd Steinberg's dithering algorithm before and I read Wikipedia and ...
1
vote
1answer
145 views

Rotating a Bitmap

I would like to rotate an bitmap image using math. I have two issues with my current implementation: the pixel-by-pixel rotation of the copied bitmap is extremely slow and it is leaving gaps between ...
1
vote
1answer
35 views

Subdivision scheme where the faces and edges have weights (not necessarily scalar weights)

Subdivision schemes work by considering the vertices and their connectivity information to calculate averaging weights. However, other than specifying which vertices are connected, and perhaps which ...
1
vote
1answer
87 views

Is There an algorithm to remove intersections between two tetrahedrons?

I have a mesh made up of several tetrahedrons, I know for sure that there are intersections between some of them: how can I remove these intersections, without generating others? In other terms: if ...
0
votes
2answers
90 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 ...
2
votes
1answer
139 views

How do I efficiently calculate the distance to the edge of a shape?

I'm trying to implement something like an "inner glow". That is, I have an image which defines the shape of an object, and then I want to create overlay that is a gradient that goes from the ...
1
vote
0answers
89 views

How can I pull up the whole area of the square? [closed]

What algorithm can i use to pull entere area? i have this image: are there many algorithms, which algorithm can you recommended me to implement? Edit 1: my square was builded with lines (bresenham), ...
1
vote
0answers
61 views

How can i stretch a line?

How can I remodel a line, i want to draw first a line then i want to remodel the line such as in paint software, which algorithm should I use? Are there several algorithms to achieve this? i am using ...
0
votes
0answers
31 views

How can i use bresemhan to any cases?

i have this bresenham's code, but actually this work only to some cases, how can i complete to any cases? ...
0
votes
1answer
233 views

What method is used for baking grayscale curvature maps

I'm looking for a way to generate curvature maps like this: The map stores the Convexity and Concavity of each pixel as a value from 0 to 1, where .5 is no curvature and 1 and 0 are the extremes. I ...
0
votes
0answers
65 views

How does on the fly LOD work?

In the Unreal Engine 5 tech demo, they mention, that there is no need to manually generate LOD levels for each model, because the on the fly LOD system will generate polygons from the original mesh, ...
4
votes
2answers
176 views

2D metaballs with marching squares and linear interpolation

I struggle do understand how linear interpolation works in the marching square rendering algorithm context. I created simple example in GDScript (Godot) of random floating metaballs to demonstrate ...
2
votes
1answer
336 views

Bresenham circle drawing algorithm, compute the distance?

In the Bresenham circle drawing algorithm, we have to choose between the top and bottom pixel, but what we always do is using the circle's equation ($f(x, y) = x^2 + y^2 = r^2$) to determine which of ...
1
vote
0answers
15 views

What algorithms are needed to map displacement to base mesh?

By given belows, Base mesh(vertices, faces, texture coordinates - UV map), Normal map(1024x1024 image), Displacement map(1024x1024 image), I want to make a mesh which reflects the displacement map. ...
0
votes
1answer
93 views

Perlin Noise implementation looks blocky in WebGL2

I'm trying to implement Perlin Noise. Earlier I implemented it using HTML Canvas and then converted it to WebGL2 since I wanted a faster implementation. But the WebGL2 code has obvious edge artifacts ...
1
vote
1answer
228 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 ...
2
votes
1answer
114 views

How do people come up with subdivision schemes?

Be it chaikin subdivision, loop subdivision, catmull-clark subdivision... How do people come up with the coefficients for an arbitrary subdivision scheme?
3
votes
1answer
318 views

Ray vs AABB algorithm that also gives which side was hit?

There are plenty of well-known algorithms for determining if a ray hit an Axis-Aligned Bounding Box (AABB), like Andrew Woo's covered in a response here. Using ...
1
vote
0answers
76 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
133 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 ...
0
votes
1answer
127 views

Deep Learning for 3D Point Clouds, volume detection and meshing

I'm working (as a Post-doc) on an archaeological excavation point cloud dataset with over 2.5 Billion points. This points come from a trench, a cuboid 10 x 10 x 3 m. Each point cloud is a layer, the ...
4
votes
2answers
154 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 ...
2
votes
1answer
101 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
33 views

How can I detect if an edge has flipped during the UV unfold process?

I'm writing my own UV Unfold operation (similar to Maya's Optimize UV tool or 3DS Max's Relax Tool). My code works great 90% of the time but in some instances, I'm getting faces and edges that flip ...
1
vote
2answers
95 views

Convert triangulated object to a polygonized object

Is there an efficient algorithm to convert a 3D object described with a set of triangles to a 3D object described with a set of polygons. Polygons can have an arbitrary number of points, more is ...
2
votes
0answers
338 views

Out of core rendering

Suppose there is a frame, which is larger that the device memory (I mean, dozens of Gb). And I would like to render to it from a set of textures, which is larger than the host memory (I mean, dozens ...
-1
votes
2answers
633 views

How can i wrap the earth image around a 3D Sphere using OpenGL, GLFW, GLAD, GLM?

Please help me out with this thing and currently i am a little more than a beginner so please tell me in that context. i don't need any obsolete methods for creating this like using GLUT or GLEW.can ...
1
vote
2answers
104 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
1answer
130 views

Non jagged line algorithm for javascript canvas

I'm trying to draw a line between two specified points, by updating values in an array which is heightxWidth with each element a set of four bytes (r,g,b,a). In my naive implementation I get the top ...
2
votes
1answer
103 views

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

I am using the Bresenham algorithm from wikipedia: ...
4
votes
0answers
179 views

Pre-filtered environment map, deriving the equation

I'm reading through this article, and more specifically I'm trying to derive the equation that would explain the implementation the following shader (still in the same article): ...
0
votes
1answer
83 views

How to scale primitive shapes [in Blender] so that they are within a [unit] sphere?

I wonder how is it possible to scale all shapes so that they are within boundaries of a [unit] sphere? I know how to do this for a cube: if radius of the sphere is S...
2
votes
0answers
417 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? ...
1
vote
2answers
2k 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
0answers
47 views

Help with efficient quadtree vertices indexing to avoid redundancy

I am creating a quad tree from ground zero, because I am going to collapse it from bottom up I am refining it with a certain LoD level. I am using glm for mathematics and opengl for rendering. ...