Skip to main content
16 votes
Accepted

Visualizing the Lane-Riesenfeld Algorithm

The Lane-Riesenfeld algorithm subdivides the control polygon of a B-spline to create a new control polygon with the same limit spline. It's made up of two steps: first, duplicating all of the control ...
gilgamec's user avatar
  • 901
15 votes

Algorithm to find the center of a Bezier curve

Bézier curves are mathematical entities and have no clearly defined center. One can in fact define many different things as the center of the Bézier curve. I have tried to depict some of the possible ...
joojaa's user avatar
  • 8,437
11 votes
Accepted

How to modify Perlin (not simplex) noise to create continental like terrain generation

Perlin noise is just a base block, not very interesting by itself. You don't need to modify it, but to combine and filter it in interesting ways. Look at how to make fractal Brownian motion (fBm) with ...
Julien Guertault's user avatar
10 votes
Accepted

Seamless Textures

For these types of algorithms, you usually have to rely on multiple forms of texture synthesis. That doesn't mean you have to generate the whole texture from scratch. For example, you could regenerate ...
aces's user avatar
  • 1,353
9 votes
Accepted

What algorithm is used in the animation of the uTorrent 's "About window"?

As you discovered and mentioned in your self-answer, the pattern in the background appears to be a sum of sinusoidal gradients. However, the example linked to in your answer is more complicated than ...
trichoplax is on Codidact now's user avatar
9 votes

Why are oct trees so much more common than hash tables?

Lots of things here. "When reading papers". What papers? If the topic of the paper is about something other than the spatial partitioning structure, it could be fair to use whatever knowing that the ...
Angelo Pesce's user avatar
8 votes
Accepted

Understanding Jump Flooding Algorithm (JFA) for Voronoi Diagrams

I think that there is a bit of confusion in terminology. My understanding is that only the initially colored points, before step 1, are called seeds. Maybe this helps clarify the algorithm as well. ...
StinkySkunk's user avatar
8 votes

Algorithms to Remove High Frequency Noise from Path Tracing

There are, and I am looking forward to seeing the specifics of other answers, but one way to deal with this is to not have the noise (or as much noise) in the source data to begin with. The noise is ...
Alan Wolfe's user avatar
  • 7,801
8 votes
Accepted

How do people come up with subdivision schemes?

The subdivision schemes are not arbitrary. Catmull-Clark, arguably the most used subdivision scheme, generalizes bicubic B-splines to meshes of arbitrary topology. Most, other subdivision schemes ...
Reynolds's user avatar
  • 1,283
7 votes
Accepted

scan line algorithm is too slow?

One red flag is the use of new several times within the loop. Memory allocation doesn't belong in a rasterizer! :) Certainly you should not need to allocate a ...
Nathan Reed's user avatar
  • 25.1k
7 votes
Accepted

How does the Painter's Algorithm handle transparency?

The common way to render transparent polygons in a rasterizer is by use of Alpha Blending, which basically combines the colour of the supposedly transparent pixel with the colour of the background at ...
Christian Rau's user avatar
7 votes
Accepted

What algorithm is used in this animation from Tatami Galaxy?

It looks like a voronoi diagram with a non-Euclidean distance metric. Probably not Manhattan L1 but something close related, but maybe Mahalanobis with some kind of restriction on seed point ...
David's user avatar
  • 301
6 votes
Accepted

Is there a way to interpolate color across the line with only integer calculation ?`

Yes, it is possible to use only integer calculations. I will describe how, but bear in mind that the difference in speed between integer arithmetic and floating point arithmetic is not as great as it ...
trichoplax is on Codidact now's user avatar
6 votes
Accepted

How to generate OSX Flurry screensaver

Looking at the video you provided, I would tend to think it's something along those lines: A particle emitter, to which all threads are attached, is moving around. I haven't really figured what its ...
Julien Guertault's user avatar
6 votes
Accepted

Optimal memory access when using lookup tables on GPU?

The best place to put a look up table for a GPU compute shader depends on the size of the lookup table, and the frequency/coherency of access. In your case (you mentioned 4kb), shared local memory ...
GroverManheim's user avatar
6 votes

How to build a 3d model from 2d pictures

This is a bit different from a conventional photogrammetry problem. You're not trying to estimate a 3D world from 2D projections. You have actual 3D information - you have the imaging slices - and you ...
Jacob Panikulam's user avatar
6 votes
Accepted

results of Curved PN-Triangles algorithm has visible edges

As mentioned in the paper PN-triangles are only $C^0$ smooth with respect to adjacent triangles (although they are $G^1$ at vertices). This means that a PN triangle mesh is continuous in position, but ...
Reynolds's user avatar
  • 1,283
6 votes
Accepted

How to calculate volume of any given 3D mesh

The triangle form of the Shoelace Formula can be extended to 3D by using tetrahedrons instead of triangles. Pick a point, Any point can be used, even one of the original vertices of the mesh (...
lfgtm's user avatar
  • 456
5 votes

Improved Laplacian smoothing of noisy surface meshes

This is a quite common property of smoothing in 3D. When you have some data and you smooth it out you get some kind of average of the local variation. And this works fine, and stably, in one ...
joojaa's user avatar
  • 8,437
5 votes
Accepted

Image rescaling algorithm

Explanation With a non-linear scale, you apply different weights for each pixel (or whatever unit you are using). You can use Euclidean distance towards the closest pixels in both directions to ...
aces's user avatar
  • 1,353
5 votes

Move position in smooth gradient

What you want is linear interpolation like @Tim points out. However he uses a formula that is not so easily understandable form, we can refactor it differently. Basically linear interpolation is a ...
joojaa's user avatar
  • 8,437
5 votes
Accepted

Move position in smooth gradient

The math you need is linear interpolation. I think of a player sprite which moves from position X to position Y. Pseudocode: ...
Timm's user avatar
  • 548
5 votes

Unwinding an image on a spiral to make it long and flat

A quickly formulated method, read first one that popped in my brain (not best), could be. Find the closest points on a parametric spiral for each sample (read A Pixel Is Not A Little Square3). Then ...
joojaa's user avatar
  • 8,437
5 votes
Accepted

Explanation of the Marching Squares saddle points resolution

Imagine that a black dot represents a value of -1 whereas a white dot represents a value of +1. You are looking for the iso-line(s) where each point upon the line is 0. For this example you could ...
JustABit's user avatar
  • 176
5 votes

Z-Buffer algorithm vs Painter's algorithm?

In the painter's algorithm, you first sort all graphics elements on depth (deepest first) and then one-by-one fully paint them into the image on top of each other. That way, deeper elements are ...
Tom Verhoeff's user avatar
5 votes
Accepted

Why are oct trees so much more common than hash tables?

My 2 cents from writting the Chipmunk2D physics engine is that spatial hashing is great when you have a lot of objects that are all the same size. I had a demo 10 years ago that ran with 20k ...
slembcke's user avatar
  • 166
5 votes

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

A texture that stores distance from the edge of the shape, like you described, is called a "distance field" (you'll find lots of results if you google that phrase). Distance fields can be ...
Nathan Reed's user avatar
  • 25.1k
4 votes

Image rotation algorithm

It speed does not matter, I suggest to use a truncated sinc or a Lanczos isotropic kernel: to compute a target pixel, you back-rotate the filter and convolve it with the image. Since it is isotropic, ...
Fabrice NEYRET's user avatar
4 votes

exact down sampling and re-triangulation of mesh data(non-convex)

1. Method: Vertex Clustering This is more or less a low-quality method, but depending on your mesh it could work well. The basic idea is to partition the space into a regular grid, and then choose ...
Dragonseel's user avatar
  • 1,810
4 votes
Accepted

Main techniques to draw a point at non integer coordinates?

Instead of having a binary on/off per pixel you can instead make a heat map. The more points fall within the pixel the brighter the pixel is. Essentially create a 2D histogram which you then ...
ratchet freak's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible