interpolating tree branches

[nabz32]

Hello, I wanted to create a new world engine, where the whole world is build out of paths.

I give each path point a certain thickness, so an actual area is created from branch to branch with a certain width
( the length of the area is the distance between two points of the path ),
like this:



In this shot each father point has only one son, so the points can easily be interpolated.

If a father has two sons, i need to put some sort of triangle between the tree, to make a nice transition between those.
How to calculate this triangle out of the 3 branches, so that none of these branches overlap each other?

Here is how it looks with 2 sons without interpolation or a triangular spacer between the 3:


( subdivision is also different between the 2 pics in case you wonder )

[Slydog]

A difficult question.

I checked through my bookmarks, but the simple answer wasn't there.

I found a mega site on general Procedural Content Generation:
http://pcg.wikidot.com/category-pcg-algorithms

I also found a (very mathy) paper about Delaunay Triangulation:
https://people.eecs.berkeley.edu/~jrs/papers/2dj.pdf

Basically you would have to create a list of points around the perimeter of your branches, ignoring the interior data.
This algo would take this enclosed path and fill in the triangles for you.
You could Google some code for this, if you want to go this route.
Maybe this code does this? I'm not sure, it does some type of triangulation:
https://github.com/greenm01/poly2tri

I thought the pattern matches road intersections.
Try Googling 'dynamic road intersections' or something similar.

[Slydog]

If you could detect the points where your branches (rectangles) intersect, this would create one triangle.
You would then need to figure out how to connect to this triangle and what points are affected or should be ignored.

[bigsofty]

I would just create a separate joint.  Move the rectangles away from the centre and then the corners closest to the joint are your polygon vertices.

[Slydog]

Something like this?

[EDIT] I subdivided the interior triangle into four triangles.

[bigsofty]

Yes, the amount of branches dictates the amount of sides to the joint though, 4 branches is a square poly, 5 a hexagon poly. Careful deformation rules for the polygon will be necessary if the joint needs to be animated too.

[nabz32]

Yeah I know the sides of the filling objects equals the number of intersections if the intersections are greater then 2.
I have trouble calculating the cut points right:
I have calculated the cutting points of the red outer lines which I called rows, however this works only on some occasions, like the one you showed in your screenshot slydog. The reason is the red lines are not always cutting each other.
Here it works:


I could also check for the intersection point of the green outer Lines ( collums ), but I think they only need to be taken into account if 2 rows don´t intersect.
Also in this case a smaller triangle than usual would be created, since 4 points are determined by the intersection of rows and 2 points are determined by the collum intersection, which basically is just the point all branches originally have met without interpolation.

I rewrite my code a bit to sort out the last errors.

Edit: thanks to you guys for your suggestions.

Edit2: Well filling with a second polygon is needed if only 2 set of lines intersect:

[nabz32]

I sorted all branches based on their angle to the center,
so lines of branches only check for intersection with branches next to them.

Also I rewrote the code so that any number of branches are possible from one point:


Now I need to fill the void spaces, preferable with objects of a triangle class which can be subdivided.
When there are three cut points one single triangle object will be created,
if there are four cut points two triangles.

Should there be more than 4 intersections and the number of intersections is even,
I could give each branchpair a triangle based on the intersection points the lines of the branch pair have ( should always be three with my algorythm ).
Then repeat this with the intersection of the lines of the new added triangles until the number of freshly created triangles equals three.
After this I just have to fit one last triangle in the remaining space.

But what to do if it is an uneven number of branches?

Edit: I have just noticed that i can simply fill all void spaces with more than 3 edges by using an additional vertex in the center of the intersection
( like someone would close a cylinders top ).
Edit2: Here is how it looks without subdivided triangle objects yet:

[nabz32]

And here it is with all my concerns removed:



I will post something in the Bonus section, when I have created 3D meshes out of this data
Edit: Thanks again, also a special thanks to Slydog with his picture of the subdivided triangle, now I know how to subdivide the triangles for my needs later on.

[Slydog]

Looking good! 

Now to turn this into a random road generator for a racing game, or racing puzzle game!