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 ...
- 966
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 ...
- 4,460
9
votes
Accepted
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 ...
- 106
9
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 ...
- 1,347
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 ...
- 1,645
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 ...
- 301
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 ...
- 1,347
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 (...
- 456
5
votes
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 ...
- 151
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 ...
- 151
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 ...
- 25.5k
4
votes
Accepted
Z-Buffer algorithm vs Painter's algorithm?
In short painter's algorithm can't deal with intersecting geometry.
Suppose that you draw a plane angled away from the camera, and a plane angled towards the camera. The planes intersect in an 'X' ...
- 506
4
votes
Accepted
How to shift color values of a single RGB channel
I don't have any direct experience doing this so I might be missing an obvious solution or tool. That said, what you describe is in programming terms comparatively easy to achieve. The basic structure ...
- 820
4
votes
Accepted
Creating a Smooth 3D Mesh from a 2D Outline
One algorithm that's pretty good for this, but very difficult to implement is to find the Medial Axis of the shape and then have various profiles that are based on the signed distance from the medial ...
- 3,481
4
votes
Existing method to automatically fill in this sort of concavity in meshes?
After a fair bit of reading and skimming through papers, I have yet to find a good definition other than "indent" for what I want to remove, but I have found answers to pretty much ...
- 101
3
votes
How does the Painter's Algorithm handle transparency?
I would like to add that Painters' algorithm can be run from front to back with transparency provided your blending operations are associative. I would recommend reading Jim Blinn's "Compositing, Part ...
- 4,450
3
votes
Can someone explain this formula for parse RGB to HSL?
First it converts the red, green, and blue values from the 8-bit unsigned integer range to floating point values between 0 and 1. It then figures out which component is the maximum, which is the ...
- 3,481
3
votes
How to generate OSX Flurry screensaver
The Flurry screensaver written by Calum Robinson is available as a part of the XScreenSaver package. You can download its source code from https://www.jwz.org/xscreensaver/download.html
The flurry* ...
- 31
3
votes
Accepted
Help understanding Perlin Noise
Yep, you've got that right. In Perlin's reference implementation of "improved noise", the noise will be periodic, repeating after 256 units along each axis. It's usually not very noticeable even if ...
- 25.5k
3
votes
Accepted
Make a texture a clickable Button
In games and other 3D scenes, generally when the user clicks the mouse, a ray is cast into the scene in the direction the camera is facing, and a check is done to see what geometry in the scene it ...
- 3,481
3
votes
2D metaballs with marching squares and linear interpolation
as promised, here my answer to your question.
As I can't follow your code completely (I spend most of my time implementing my code :D ) I can only explain to you what the last step is.
So why do we ...
- 195
3
votes
Accepted
Subdivision scheme where the faces and edges have weights (not necessarily scalar weights)
What you are looking for is semi-sharp creases. You can find it in section 3 of this paper: https://graphics.pixar.com/library/Geri/paper.pdf
Basically, each edge is given a sharpness value $s$. This ...
- 1,347
3
votes
How can I get a signed distance (SDF) from a mesh?
EDIT
I was able to get a simple algorithm working for this purpose, though it's not highly optimized.
In my implementation, I use sheer brute force, accelerated by GPU. By this, I mean that I get the ...
- 201
3
votes
Accepted
Having trouble implementing distance transform with jump flood
I took a few minutes and hacked this to life for you. The bugs were all pretty basic things like using floating point math where it should have been using interger math. All those little fractions add ...
- 3,764
3
votes
Can you explain to me the Bresenham's line algorithm in simple terms?
The first thing to make note of is that the algorithm listed in the question is the integer algorithm. So no floating point math and the plotting increments by +1 or -1 in the x and y directions.
The ...
- 3,764
2
votes
Accepted
Are there LOD Algorithms that work through removing objects?
Here's how I'd do it:
Assign an sequential id to each tree. This can be an implicit id like an index in an array if you have this structure. The important part is that you can create N stable groups ...
- 820
2
votes
Calculate set of rectangles covering pixel diffs?
I would say itβs a weighted set covering problem.
In specific, the cost for a set of points is the number of extra pixels in the bounding rectangle of this set.
If the number of diff points is small,...
- 46
2
votes
Explanation of the Vatti clipping algorithm
{π0,π8,π7,π6} and {π4,π3,π2} are called "left bounds" because if you look at both these bounds, the polygon interior is to the right of them:
Likewise, {π0,π1,π2} and {π4,π5,π6}...
- 121
2
votes
Parametrize set of unordered points in 3d space
You could try natural neighbour interpolation or Sibson coordinates for this. These coordinates are based on a Voronoi tessellation of the points.
The coordinates have been extended to an approach ...
- 1,347
2
votes
After a deformation operation on polygons, how can I check for and fix inverted polys?
If you have an oriented triangle mesh (a non oriented surface would be the Moebius Strip for instance), you can check the triangle inversion by looking at the signed area of triangles. The signed area ...
Only top scored, non community-wiki answers of a minimum length are eligible