Filter Forge - The Need for Triangles

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

Triangulation Script, initial study.

The only problem is that some lines are crossing over others, need some code to select the better (non-overlapping) of the two possible connections.

Posted: May 27, 2014 7:29 am

Details E-Mail

Skybase

2D/3D Generalist

Posts: 4025
Filters: 76

Can you explain the magic in pseudo code?

Posted: May 27, 2014 8:02 am

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

Sure. (Actually, I'll just explain it in English.)

I start with a straight square grid, the white points are initially on the crossing points. The x- and y-offsets of the white points of the grid are derived fr om perlin noise values, but they still remain within their own squares, ie. no point can go past another one vertically or horizontally. Then I draw the connecting lines, and alternating diagonal connecting lines (every other line is flipped).

The clearest explanation would be this image wh ere I turned the perlin contrast down:

Posted: May 27, 2014 9:19 am

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

The basic reason for this approach: No need for tables, the points are all derived procedurally, so I can do this with no significant loss in speed:

Posted: May 27, 2014 9:25 am

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

Once I get the check-whether-a-point-is-inside-a-triangle part of the code working, I can get rid of the overlaps and start doing various fills between the lines.

Posted: May 27, 2014 9:27 am

Details E-Mail

Crapadilla

lvl 52 Filter Weaver and Official "Filter Forge Seer"

Posts: 4365
Filters: 65

Quote
Once I get the check-whether-a-point-is-inside-a-triangle part of the code working

http://totologic.blogspot.fr/2014/01/...-test.html

Would this be of any help?

I've used the barycentric method for a custom "Free Triangle" component. Worked like a charm. smile:)

--- Crapadilla says: "Damn you, stupid redundant feature requests!" ;)

Posted: May 27, 2014 4:39 pm

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

Hi Crapadilla,

Thanks. Yes, that's the method I'm using. For some reason didn't get it to work properly yet, probably just something simple I've missed.

TD

Posted: May 27, 2014 4:57 pm

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

Alright, some progress. Picking the color of the cell from image, average of the three corner values:

Posted: May 28, 2014 8:51 am

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

A plexus-like derivative thereof.

Posted: May 28, 2014 9:42 am

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

Tempted to do this with a table instead. Would give more freedom in placing the points. Probably be way faster too, especially when the point count is relatively low.

Posted: May 28, 2014 10:11 am

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

So -- started to construct the same with a table...

Getting it to wrap properly was tricky enough.

Posted: May 28, 2014 3:48 pm

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

One significant advantage in keeping the dots constrained inside their respective grid "cells" is that you know exactly what dot is in which area and don't have to iterate through all dots to find the closest one to a given point. This makes rendering pretty efficient. So far, at least.

Posted: May 28, 2014 3:53 pm

Details E-Mail

Crapadilla

lvl 52 Filter Weaver and Official "Filter Forge Seer"

Posts: 4365
Filters: 65

Quote
Picking the color of the cell from image, average of the three corner values

Nice!

Barycentric gradient shading in the works? smile;)

--- Crapadilla says: "Damn you, stupid redundant feature requests!" ;)

Posted: May 29, 2014 4:18 am

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

Quote
Barycentric gradient shading in the works?

Naturally

Posted: May 29, 2014 4:38 am

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

Speaking of "naturally", I just realized that the direction in which the rectangular shapes should be divided should be based on the Delaunay method, ie. splitting the rectangle into two triangles by cutting it between those two opposite corners the angles of which total more than 180 degrees. Naturally.

Resulting in a sort of semi-Delaunay triangulation.

Posted: May 29, 2014 4:44 am

Details E-Mail

Crapadilla

lvl 52 Filter Weaver and Official "Filter Forge Seer"

Posts: 4365
Filters: 65

To avoid those very long/thin triangles, I gather?

--- Crapadilla says: "Damn you, stupid redundant feature requests!" ;)

Posted: May 29, 2014 4:49 am

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

Come to think of it, the current version (before splitting the rectangles into triangles) is already a good basis for a new noise type of "Rectangulation". With suitable shading, it would be a new basic noise type that is different from the built-in noises.

Posted: May 29, 2014 4:52 am

Details E-Mail

ThreeDee

Lost in Space

Posts: 1672
Filters: 112

Quote
To avoid those very long/thin triangles, I gather?

Well, the method pretty much already takes care of that, since no point moves outside its own square domain, but essentially yes, it would always be the "fatter" triangulation of the two options. Also, the Delaunay condition ensures that no concave rectangles are split in the wrong direction -- the wrong direction results in lines outside the shape rather than two triangles, like those that can be seen in my first image.