Questions tagged [algorithm]

Questions about the rigorous usage of instructions used to solve a specific computer graphics problem.

Filter by
Sorted by
Tagged with
0 votes
1 answer
80 views

Constructing half-edges table from triangle list without hash

Motivation I am trying to refine a mesh such that each triangle gets subdivided into 4 triangles, but I want the vertices to be shared. For that purpose I need a half-edge data structure so I can ...
lightxbulb's user avatar
  • 2,083
0 votes
0 answers
23 views

Normal blend mode math

I have one question. How to calculate source color after blending operation. For example. I have 1 - Background color (r-115, g-94, b-67, a-1) 2 - Foreground color above background color, which ...
Alisher's user avatar
0 votes
1 answer
61 views

Extrapolating geometry across a triangle mesh?

Say you have 2 parametric cylinders represented as triangle meshes with very different geometries and you connect them together. Is there a method that allows you to join them together such that the ...
Makogan's user avatar
  • 1,696
1 vote
0 answers
58 views

Piecewise smoothing of a mesh?

Kobbelt et al. published a paper some 20 years ago where they specified how solving Poisson equations on the positions of a mesh lead to removing noise. This can be used for reconstructing mesh ...
Makogan's user avatar
  • 1,696
0 votes
0 answers
20 views

How is re projection usually implemented in remeshing?

I was reading "Polygon Mesh Processing" and in chapter 5 the authors present this little algorithm: ...
Makogan's user avatar
  • 1,696
2 votes
1 answer
37 views

What is a smart way to fill in the 'next' pointer of a opposite half-edge of a boundary?

I was reading this question regarding half edges from 3 years ago and the selected answer seemed pretty smart to me. However, while actually implementing it I'm confused at the part where I have to ...
ThisAccountIsForGameDev's user avatar
0 votes
0 answers
52 views

What algorithms are typically used for finding 'PCB Trace'-like paths?

I am analyzing a large amount of Layers 0-4 Network Data. I am trying to render diagrams dynamically showing the Network Devices involved in the data (Desktop, Switch, Router, Server, etc.) and how ...
Liam Kelly's user avatar
0 votes
1 answer
44 views

Why capsule box intersection algorithms not widely used

I have searched through a lot of libraries and sources, that include very diverse intersection algorithms, for computer graphics. And I've never found a capsule-box intersection algorithm. Despite ...
Lenny White's user avatar
0 votes
2 answers
172 views

Relative coordinates -- cumulative sum

I have a vertex shader happily producing all the vertices I want for a 2D plot. Now I want to also render a plot of the same data, but each point relative to the previous one, like SVG Paths using <...
Nick's user avatar
  • 11
1 vote
1 answer
45 views

Are systems like double pendulum used for generating terrain?

Looking at the output of the angle of this double pendulum made me think this was a good candidate for generating realistic looking terrain profiles. I can't be the first to notice this so I was ...
AJP's user avatar
  • 83
0 votes
0 answers
28 views

Measure the printing quality of an image

I have experienced a problem with managed presses when the printing quality of a particular image would vary -- a lot -- from printer-run to printer-run. I have tried to visit the presses and ...
TeX Apprentice's user avatar
4 votes
2 answers
446 views

Can you explain to me the Bresenham's line algorithm in simple terms?

I've been trying to wrap my head around this algorithm, and I need it for my drawing function. But I can't seem to understand it. The Wikipedia page gives this piece of code right at the end: ...
sneaker's user avatar
  • 41
4 votes
1 answer
223 views

How to find the nearest palette color when dithering in RGB

I maintain an image dithering library and command line tool. When I was initially developing the library, I was trying to figure out how to match dithered RGB values (containing quantization error or ...
makeworld's user avatar
  • 143
3 votes
1 answer
127 views

Algorithms for rendering overlapping (floating) windows in 2D

I'm trying to figure out a solution to a problem that looked simple at first: how to render overlapping windows in a 2D windowing system. Originally I was thinking about implementing a text-based UI ...
LittlePilgrim's user avatar
1 vote
0 answers
67 views

Temporal reprojection of specular reflection - finding previous frame color

In specular reflection result depends on view vector from camera to point. Because of that, when doing temporal reprojection and reprojecting position of current fragment while camera is translating, ...
mdkdy's user avatar
  • 2,119
0 votes
1 answer
108 views

Plot inverse of emulated double-precision floats

I need to accurately plot a line chart using WebGL. The numbers have a precision of around 33 bits - that's too many to fit into a single-precision float's mantissa. WebGL does not support the double-...
purefanatic's user avatar
1 vote
0 answers
45 views

How does the additively weighted Voronoi algorithm differs from the unweighted Voronoi algorithm?

I am trying to read Fortune's description of his additively weighted Voronoi algorithm but I am experiencing some difficulty in understanding it. I imagine the algorithm as being like that for regular ...
Stapton's user avatar
  • 11
4 votes
1 answer
1k views

How to calculate volume of any given 3D mesh

Given 3D mesh with a closed surface. (solid object without hole). I'm looking for an algorithm to calculate its volume. There are several ideas, Such as Voxelized and count voxels Point cloud and ...
kitta's user avatar
  • 143
1 vote
0 answers
123 views

Turning colorized comic-art into uncolorized monochrome (line-art-inks-only B&W), not just very-light-grayscale

I'm trying to figure out how to go about removing the "colorization" of comic/cartoon/manga/etc drawn-art inputs where the black-ink strokes ("the line-art") are to be retained ...
Phil S.'s user avatar
  • 11
1 vote
0 answers
41 views

Algorithm for transforming PNG anti-aliasing to smooth paths

I read the pixels of PNG files via libpng and creates an array of alpha channels (showing visible pixels for a monochromatic image). int pixels[height][width]; <...
Googlebot's user avatar
  • 131
1 vote
0 answers
114 views

Extrusion Algorithm For Bezier Curves

I just posted this to SO but the question got closed, so I hope it's OK if I try it again here. They say "we don’t allow questions seeking recommendations for books, tools, software libraries&...
fweth's user avatar
  • 127
1 vote
1 answer
157 views

What does an algorithm which handles mesh-based image morphing look like?

In recent years, the technology of Live2D has become particularly popular and I have been attempting to find any papers or articles which explain what the mathematics for the mesh-based image morphing ...
MadCreativity's user avatar
2 votes
1 answer
355 views

Having trouble implementing distance transform with jump flood

I'm attempting to use the jump flood algorithm to compute distance transforms of an arbitrary texture derived from a canvas2d context, roughly following the explanations detailed here/here. In the ...
Nico's user avatar
  • 23
1 vote
1 answer
53 views

How is the beam transmittance calculated in PBRT V3?

In pbrt v3, the book gives this description of beam transmittance, but I don't know how to solve the differential equation like it says to get Tr , can someone please tell me how to solve the ...
Wenjian Zhou's user avatar
0 votes
0 answers
37 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 ...
Water's user avatar
  • 101
2 votes
1 answer
110 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 ...
10GeV's user avatar
  • 123
1 vote
1 answer
118 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 ...
Nubcodes's user avatar
0 votes
0 answers
57 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. ...
user993563's user avatar
4 votes
3 answers
9k 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 ...
Sirius 5's user avatar
1 vote
1 answer
114 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 ...
munHunger's user avatar
  • 113
4 votes
2 answers
260 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 ...
Thomas's user avatar
  • 1,111
3 votes
0 answers
41 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. ...
Herbert Jensch's user avatar
2 votes
0 answers
54 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 ...
Megidd's user avatar
  • 133
6 votes
1 answer
101 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,...
FilmCoder's user avatar
0 votes
0 answers
46 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 ...
Amir's user avatar
  • 241
0 votes
1 answer
38 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 ...
Megidd's user avatar
  • 133
0 votes
1 answer
260 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 ...
Dr. Pontchartrain's user avatar
1 vote
1 answer
1k 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 ...
Dr. Pontchartrain's user avatar
1 vote
1 answer
61 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 ...
Makogan's user avatar
  • 1,696
1 vote
1 answer
91 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 ...
Davide's user avatar
  • 11
0 votes
2 answers
111 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 ...
Dr. Pontchartrain's user avatar
3 votes
1 answer
723 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 ...
Steinbitglis's user avatar
1 vote
0 answers
90 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), ...
hubman's user avatar
  • 121
1 vote
0 answers
75 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 ...
hubman's user avatar
  • 121
0 votes
0 answers
36 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? ...
hubman's user avatar
  • 121
0 votes
1 answer
515 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 ...
Jummit's user avatar
  • 101
0 votes
0 answers
106 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, ...
Iter Ator's user avatar
  • 278
4 votes
2 answers
636 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 ...
Arsenius's user avatar
  • 141
2 votes
1 answer
908 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 ...
Jojolatino's user avatar
1 vote
0 answers
28 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. ...
suwoong Heo's user avatar