Fractals/Computer graphic techniques/2D/algorithms: Difference between revisions
Appearance
[checked revision] | [checked revision] |
Content deleted Content added
→SDF = Signed Distance Function: https://iquilezles.org/www/articles/distgradfunctions2d/distgradfunctions2d.htm |
Tag: Reverted |
||
Line 42: | Line 42: | ||
* path finding<ref>[http://www.fractalforums.com/mandelbrot-and-julia-set/pathfinding-in-the-mandelbrot-set/ fractal forums : pathfinding-in-the-mandelbrot-set/]</ref> |
* path finding<ref>[http://www.fractalforums.com/mandelbrot-and-julia-set/pathfinding-in-the-mandelbrot-set/ fractal forums : pathfinding-in-the-mandelbrot-set/]</ref> |
||
* aliasing <ref>[https://www.overclockersclub.com/reviews/serious_statistics_aliasing/ serious_statistics_aliasing by Guest_Jim]</ref> |
* aliasing <ref>[https://www.overclockersclub.com/reviews/serious_statistics_aliasing/ serious_statistics_aliasing by Guest_Jim]</ref> |
||
* changing algorithm ( representation function) from discrete to continous, like from level set method of escape time to continous ( DEM ) |
* changing algorithm <ref>[https://www.scaler.com/topics/c/if-else-statement-in-c/]</ref> ( representation function) from discrete to continous, like from level set method of escape time to continous ( DEM ) |
||
"the denser the area, the more heavy the anti-aliasing have to be in order to make it look good." knighty<ref>[https://fractalforums.org/fractal-mathematics-and-new-theories/28/newton-raphson-zooming/ fractalforums.org : newton-raphson-zooming]</ref> |
"the denser the area, the more heavy the anti-aliasing have to be in order to make it look good." knighty<ref>[https://fractalforums.org/fractal-mathematics-and-new-theories/28/newton-raphson-zooming/ fractalforums.org : newton-raphson-zooming]</ref> |
Revision as of 12:07, 21 June 2022
- line
- circle [9]
- edge detection
- Filling_contour
- 2D Plane transformations
- curve fitting[13]
- Mending broken lines [14]
- Morphological operations on binary images[15][16]
- morphological closing = dilation followed by erosion
- morphological opening = erosion followed by dilation
Image processing
Postprocessing
- Two types of edge detection
- Pseudo-3D projections
- Star field generator
- Random dot stereograms (aka Magic Eye)
- Motion blur for animations
- Interlacing
- Embossing
- Antialiasing
- Palette emulation to allow color cycling on true-color displays
- True color emulation that provides dithering on 256-color display
dense image
Dense image[17][18][19][20][21]
- downscaling with gamma correction[22]
- path finding[23]
- aliasing [24]
- changing algorithm [25] ( representation function) from discrete to continous, like from level set method of escape time to continous ( DEM )
"the denser the area, the more heavy the anti-aliasing have to be in order to make it look good." knighty[26]
"the details are smaller than pixel spacing, so all that remains is the bands of colour shift from period-doubling of features making it even denser" claude[27]
path finding
path finding
- old fractal forums : pathfinding-in-the-mandelbrot-set/
- fractalforums.org : pathfinding-in-the-mandelbrot-set-revisited
- 5-ways-to-find-the-shortest-path-in-a-graph by Johannes Baum
- mathreference - graph
Algorithms[28]
- Depth-First Search (DFS) = the simplest algorithm
- Breadth-First Search (BFS)
- Bidirectional Search
- Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm)
- Bellman-Ford Algorithm
How to tell whether a point is to the right or left side of a line ?
/*
How to tell whether a point is to the right or left side of a line ?
http://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-to-the-right-or-left-side-of-a-line
a, b = points
line = ab
pont to check = z
position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
It is 0 on the line, and +1 on one side, -1 on the other side.
*/
double CheckSide(double Zx, double Zy, double Ax, double Ay, double Bx, double By)
{
return ((Bx - Ax) * (Zy - Ay) - (By - Ay) * (Zx - Ax));
}
Testing if point is inside triangle
/*
c console program
gcc t.c -Wall
./a.out
*/
# include <stdio.h>
// 3 points define triangle
double Zax = -0.250000000000000;
double Zay = 0.433012701892219;
// left when y
double Zlx = -0.112538773749444;
double Zly = 0.436719687479814 ;
double Zrx = -0.335875821657728;
double Zry = 0.316782798339332;
// points to test
// = inside triangle
double Zx = -0.209881783739630;
double Zy = +0.4;
// outside triangle
double Zxo = -0.193503885412548 ;
double Zyo = 0.521747636163664;
double Zxo2 = -0.338750000000000;
double Zyo2 = +0.440690927838329;
// ============ http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-2d-triangle
// In general, the simplest (and quite optimal) algorithm is checking on which side of the half-plane created by the edges the point is.
double sign (double x1, double y1, double x2, double y2, double x3, double y3)
{
return (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3);
}
int PointInTriangle (double x, double y, double x1, double y1, double x2, double y2, double x3, double y3)
{
double b1, b2, b3;
b1 = sign(x, y, x1, y1, x2, y2) < 0.0;
b2 = sign(x, y, x2, y2, x3, y3) < 0.0;
b3 = sign(x, y, x3, y3, x1, y1) < 0.0;
return ((b1 == b2) && (b2 == b3));
}
int Describe_Position(double Zx, double Zy){
if (PointInTriangle( Zx, Zy, Zax, Zay, Zlx, Zly, Zrx, Zry))
printf(" Z is inside \n");
else printf(" Z is outside \n");
return 0;
}
// ======================================
int main(void){
Describe_Position(Zx, Zy);
Describe_Position(Zxo, Zyo);
Describe_Position(Zxo2, Zyo2);
return 0;
}
Orientation and area of the triangle
Orientation and area of the triangle : how to do it ?
// gcc t.c -Wall
// ./a.out
# include <stdio.h>
// http://ncalculators.com/geometry/triangle-area-by-3-points.htm
double GiveTriangleArea(double xa, double ya, double xb, double yb, double xc, double yc)
{
return ((xb*ya-xa*yb)+(xc*yb-xb*yc)+(xa*yc-xc*ya))/2.0;
}
/*
wiki Curve_orientation
[http://mathoverflow.net/questions/44096/detecting-whether-directed-cycle-is-clockwise-or-counterclockwise]
The orientation of a triangle (clockwise/counterclockwise) is the sign of the determinant
matrix = { {1 , x1, y1}, {1 ,x2, y2} , {1, x3, y3}}
where
(x_1,y_1), (x_2,y_2), (x_3,y_3)$
are the Cartesian coordinates of the three vertices of the triangle.
:<math>\mathbf{O} = \begin{bmatrix}
1 & x_{A} & y_{A} \\
1 & x_{B} & y_{B} \\
1 & x_{C} & y_{C}\end{bmatrix}.</math>
A formula for its determinant may be obtained, e.g., using the method of [[cofactor expansion]]:
:<math>\begin{align}
\det(O) &= 1\begin{vmatrix}x_{B}&y_{B}\\x_{C}&y_{C}\end{vmatrix}
-x_{A}\begin{vmatrix}1&y_{B}\\1&y_{C}\end{vmatrix}
+y_{A}\begin{vmatrix}1&x_{B}\\1&x_{C}\end{vmatrix} \\
&= x_{B}y_{C}-y_{B}x_{C}-x_{A}y_{C}+x_{A}y_{B}+y_{A}x_{C}-y_{A}x_{B} \\
&= (x_{B}y_{C}+x_{A}y_{B}+y_{A}x_{C})-(y_{A}x_{B}+y_{B}x_{C}+x_{A}y_{C}).
\end{align}
</math>
If the determinant is negative, then the polygon is oriented clockwise. If the determinant is positive, the polygon is oriented counterclockwise. The determinant is non-zero if points A, B, and C are non-[[collinear]]. In the above example, with points ordered A, B, C, etc., the determinant is negative, and therefore the polygon is clockwise.
*/
double IsTriangleCounterclockwise(double xa, double ya, double xb, double yb, double xc, double yc)
{return ((xb*yc + xa*yb +ya*xc) - (ya*xb +yb*xc + xa*yc)); }
int DescribeTriangle(double xa, double ya, double xb, double yb, double xc, double yc)
{
double t = IsTriangleCounterclockwise( xa, ya, xb, yb, xc, yc);
double a = GiveTriangleArea( xa, ya, xb, yb, xc, yc);
if (t>0) printf("this triangle is oriented counterclockwise, determinent = %f ; area = %f\n", t,a);
if (t<0) printf("this triangle is oriented clockwise, determinent = %f; area = %f\n", t,a);
if (t==0) printf("this triangle is degenerate: colinear or identical points, determinent = %f; area = %f\n", t,a);
return 0;
}
int main()
{
// clockwise oriented triangles
DescribeTriangle(-94, 0, 92, 68, 400, 180); // https://www-sop.inria.fr/prisme/fiches/Arithmetique/index.html.en
DescribeTriangle(4.0, 1.0, 0.0, 9.0, 8.0, 3.0); // clockwise orientation https://people.sc.fsu.edu/~jburkardt/datasets/triangles/tex5.txt
// counterclockwise oriented triangles
DescribeTriangle(-50.00, 0.00, 50.00, 0.00, 0.00, 0.02); // a "cap" triangle. This example has an area of 1.
DescribeTriangle(0.0, 0.0, 3.0, 0.0, 0.0, 4.0); // a right triangle. This example has an area of (?? 3 ??) = 6
DescribeTriangle(4.0, 1.0, 8.0, 3.0, 0.0, 9.0); // https://people.sc.fsu.edu/~jburkardt/datasets/triangles/tex1.txt
DescribeTriangle(-0.5, 0.0, 0.5, 0.0, 0.0, 0.866025403784439); // an equilateral triangle. This triangle has an area of sqrt(3)/4.
// degenerate triangles
DescribeTriangle(1.0, 0.0, 2.0, 2.0, 3.0, 4.0); // This triangle is degenerate: 3 colinear points. https://people.sc.fsu.edu/~jburkardt/datasets/triangles/tex6.txt
DescribeTriangle(4.0, 1.0, 0.0, 9.0, 4.0, 1.0); //2 identical points
DescribeTriangle(2.0, 3.0, 2.0, 3.0, 2.0, 3.0); // 3 identical points
return 0;
}
Testing if point is inside polygon
/*
gcc p.c -Wall
./a.out
----------- git --------------------
cd existing_folder
git init
git remote add origin git@gitlab.com:adammajewski/PointInPolygonTest_c.git
git add .
git commit
git push -u origin master
*/
#include <stdio.h>
#define LENGTH 6
/*
Argument Meaning
nvert Number of vertices in the polygon. Whether to repeat the first vertex at the end is discussed below.
vertx, verty Arrays containing the x- and y-coordinates of the polygon's vertices.
testx, testy X- and y-coordinate of the test point.
https://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
PNPOLY - Point Inclusion in Polygon Test
W. Randolph Franklin (WRF)
I run a semi-infinite ray horizontally (increasing x, fixed y) out from the test point,
and count how many edges it crosses.
At each crossing, the ray switches between inside and outside.
This is called the Jordan curve theorem.
The case of the ray going thru a vertex is handled correctly via a careful selection of inequalities.
Don't mess with this code unless you're familiar with the idea of Simulation of Simplicity.
This pretends to shift the ray infinitesimally down so that it either clearly intersects, or clearly doesn't touch.
Since this is merely a conceptual, infinitesimal, shift, it never creates an intersection that didn't exist before,
and never destroys an intersection that clearly existed before.
The ray is tested against each edge thus:
Is the point in the half-plane to the left of the extended edge? and
Is the point's Y coordinate within the edge's Y-range?
Handling endpoints here is tricky.
I run a semi-infinite ray horizontally (increasing x, fixed y) out from the test point,
and count how many edges it crosses. At each crossing,
the ray switches between inside and outside. This is called the Jordan curve theorem.
The variable c is switching from 0 to 1 and 1 to 0 each time the horizontal ray crosses any edge.
So basically it's keeping track of whether the number of edges crossed are even or odd.
0 means even and 1 means odd.
*/
int pnpoly(int nvert, double *vertx, double *verty, double testx, double testy)
{
int i, j, c = 0;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
if ( ((verty[i]>testy) != (verty[j]>testy)) &&
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
c = !c;
}
return c;
}
void CheckPoint(int nvert, double *vertx, double *verty, double testx, double testy){
int flag;
flag = pnpoly(nvert, vertx, verty, testx, testy);
switch(flag){
case 0 : printf("outside\n"); break;
case 1 : printf("inside\n"); break;
default : printf(" ??? \n");
}
}
int main (){
// values from http://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon
// number from 0 to (LENGTH-1)
double zzx[LENGTH] = { 13.5, 6.0, 13.5, 42.5, 39.5, 42.5};
double zzy[LENGTH] = {100.0, 70.5, 41.5, 56.5, 69.5, 84.5};
CheckPoint(LENGTH, zzx, zzy, zzx[4]-0.001, zzy[4]);
CheckPoint(LENGTH, zzx, zzy, zzx[4]+0.001, zzy[4]);
return 0;
}
curve sampling
Border, bounday, contour
contour models
- snakes = active contour models[34]
border tracing
- Tracing Boundaries in 2D Images by V. Kovalevsky[35]
- wikipedia : Boundary tracing
SDF = Signed Distance Function
- Define 3 shapes via there Signed Distance Function
- Signed_distance_function in wikipedia
- dist functions 2d by I Quilez
- i quilez : dist grad functions 2d
clipping
test external tangency of 2 circles
/*
distance between 2 points
z1 = x1 + y1*I
z2 = x2 + y2*I
en.wikipedia.org/wiki/Distance#Geometry
*/
double GiveDistance(int x1, int y1, int x2, int y2){
return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
/*
mutually and externally tangent circles
mathworld.wolfram.com/TangentCircles.html
Two circles are mutually and externally tangent if distance between their centers is equal to the sum of their radii
*/
double TestTangency(int x1, int y1, int r1, int x2, int y2, int r2){
double distance;
distance = GiveDistance(x1, y1, x2, y2);
return ( distance - (r1+r2));
// return should be zero
}
References
- ↑ Michael Abrash's Graphics Programming Black Book Special Edition
- ↑ geometrictools Documentation
- ↑ The Beauty of Bresenham's Algorithm by Alois Zingl
- ↑ bresenhams-drawing-algorithms
- ↑ Bresenham’s Line Drawing Algorithm by Peter Occil
- ↑ Peter Occil
- ↑ Algorytm Bresenhama by Wojciech Muła
- ↑ Drawing Thick Lines
- ↑ wolfram : NumberTheoreticConstructionOfDigitalCircles
- ↑ Mitch Richling: 3D Mandelbrot Sets
- ↑ fractalforums : antialiasing-fractals-how-best-to-do-it/
- ↑ ultrafractal : slope
- ↑ Matlab examples : curvefitting
- ↑ Mending broken lines by Alan Gibson.
- ↑ Matlab : images/morphological-filtering
- ↑ Tim Warburton : morphology in matlab
- ↑ wikipedi : dense_set
- ↑ mathoverflow question : is-there-an-almost-dense-set-of-quadratic-polynomials-which-is-not-in-the-inte/254533#254533
- ↑ fractalforums : dense-image
- ↑ fractalforums.org : m andelbrot-set-various-structures
- ↑ fractalforums.org : technical-challenge-discussion-the-lichtenberg-figure
- ↑ A Cheritat wiki : see image showing gamma-correct downscale of dense part of Mandelbropt set
- ↑ fractal forums : pathfinding-in-the-mandelbrot-set/
- ↑ serious_statistics_aliasing by Guest_Jim
- ↑ [1]
- ↑ fractalforums.org : newton-raphson-zooming
- ↑ fractalforums : gerrit-images
- ↑ 5-ways-to-find-the-shortest-path-in-a-graph by Johannes Baum
- ↑ accurate-point-in-triangle-test by Cedric Jules
- ↑ stackoverflow question : how-to-determine-a-point-in-a-2d-triangle
- ↑ js code
- ↑ stackoverflow questions : How can I determine whether a 2D Point is within a Polygon?
- ↑ Punkt wewnątrz wielokąta - W Muła
- ↑ INSA : active-contour-models
- ↑ Tracing Boundaries in 2D Images by V. Kovalevsky