I’m trying to combine two objects into one, but I need to add triangles and delete others to connect them. I don’t know how to handle it.
The road is created from Bézier curves with lots of triangles (about 2000), and the terrain is a low poly planar object (about 200 triangles).
What I want to do is to connect the terrain to the road, adding triangles between these two objects.
I have already thought of a way to do this:
Detects terrain vertices that lie within the (X, Z) coordinates of the road and removes them from the terrain vertices array.
Merge terrain’s vertices with the road’s vertices.
Create triangles to mesh the entire object:
For each vertex of the road, find the nearest vertices (on the (X, Z) axes) of the terrain, then create a triangle between the nearest points of the terrain and the current point of the road.
Here is a scheme of what I am thinking (vertices to be deleted are represented by a cross, triangles to be added are in grey):
Detecting unnecessary vertices for the future object and removing them from the vertex table is already done.
The problem is that I don’t know how to create these new triangles, how to add them in the right order, etc.
Is there a good way to do this? Or a simple way? How do I do it? Better yet, is there a known algorithm for doing this?
There are a lot of unknowns in your explanation of the problem. Try to reread it from a perspective of someone who has no idea what you’re trying to build and maybe you’ll try to amend or rephrase it.
Some questions that need clarifying:
what does that picture represent? I can tell it’s a mesh, but which is which exactly.
is the greyed out area an existing mesh?
is the “road” part of it a hole in the mesh?
how do you initially produce this area of the mesh? (whether it’s a hole or not.)
Seems a lot like what Blender calls the “bridge edge loops” operation.
Find the chain of connected vertices along the edge of your terrain. Find the chain of connected vertices on your road. You want to form triangles between those chains of vertices. As you go along, you look at whether it’s better to add a new edge (and thus a new triangle) to the next vertex on the left bank or the right bank of the gap. It’s a straightforward algorithm but thinking through the indices to get it right can be a pain in the tuchus.
So, this scheme represent what I want to achieve. The grid in the background represent my terrain. Above, there is the road.
The greyed out area is triangles I want to add between these two objects to link them smoothly.
The road is not a hole in the terrain’s mesh. They are distinct objects.
I have already compute the road on a side, and the terrain on the other.
I would also like to point out that this scheme represents objects in the way they are placed in the world. I want to merge them from these positions.
Bridge Edge Loops could be a thing, but the terrain is actualy a single part object. This method could be applied with a splitted terrain isn’t it ? In addition, the mesh of the terrain is much less detailed than that of the road, which could be a concern I guess…
I thought of doing a triangulation for example starting from the top left corner, and adding triangles by scanning to the bottom right corner… But I don’t even know if it works.
Speaking in Blender3D terminology, it sounds like you are wanting a knife project operation.
This would let you project the geometry of the road onto the terrain mesh, allowing you to remove the terrain parts that are directly under the road. After that you could optionally combine the two sets without z-fighting / overdraw.
I just took a grid, made a road and knife-projected it and it looks like this:
The road itself is hidden in the above image, but you can clearly see where it was knife-projected onto the grid.
As for HOW to do it in code, well, that’s a bit more involved. The good news is technically you could study the Blender3D source and see what they are doing, or else go find your own favorite knife project algorithm online.
I chopped out the terrain within the road, slapped a follow-active-quad texture on the road and a grass texture on and here is my programmer art road on terrain via Blender3D, no overdraw:
The thing is that the generated road is not at the same height all the way:
In fact I could affect height to the road vertices after process the projection but I don’t know if it is the right way to achieve that.
I would have seen more a kind of triangulation based on the combined mesh (I already combined them, the two entities are one object). But I have trouble seeing how to do that, it looks complex. Maybe use a Euclidean distance to choose the points forming the triangles and mark the vertices already used (as a kind of scan)?
I wonder if a Delaunay triangulation or Ear Clipping would work…
If you look at my linked example above in MakeGeo, it goes along raycasting to the terrain in order to “shrink wrap” the road segment vertices onto the surface.
In other news, Blender3D has a Shrinkwrap Modifier that does largely the same thing, although it requires also a Lattice Modifier (to which you apply the Shrinkwrap) in order to preserve mesh volume and “wrap” it over the target object.
Yeah, I started by doing this way; raycasting is a good method if your mesh resolution is quiet the same on both objects. Here the terrain is a low poly object and the road have a lot of triangles. This mean I have to upscale my vertices number on the terrain if I want to do this way, but that is something I don’t want :/. That is why i want to merge mesh.
I automates the generation of route and environment on the fly. So I can’t use Blender to model it; only Unity by scripting.
As long as the road is reasonably higher resolution stepping than the terrain, you simply raycast at the terrain and get the height of the road from that.
If you need more error “lift” fudge to it, then put it in. If you need to smooth the road out more, use lowpass filtering or some sort of point relaxation technique.
I understand you can’t use Blender. I am using Blender to illustrate the concept of high-level things like Knife Project and Lattice and Shrink Wrap and to verify that’s what you’re doing. Once you know what you are doing you can begin to implement a solution, which could even involve studying how Blender does it, although this is a fairly-involved process.
Procedural generation is hard. That’s why I made MakeGeo to give myself (and others) a leg up getting the basics done. I just dropped a lowpoly terrain into the MakeGeo testmakeroads and the roads will wrap smoothly over the lowpoly terrain. You can even do more inter-Transform steps if you like.
I don’t understand a word of what you’re saying. I mean I understand the words themselves, but words have no meaning.
No, raycasting is perfect to get EXACTLY what the mesh is doing, PLUS you get to space out the vertices exactly to a resolution (triangle density) that you find acceptable. You can ideally produce a perfect ribbon that fits the original mesh, but has uniformity between segments to allow for smoother angles. You can then, as Kurt suggested, apply something like Laplacian smoothing, which is the simplest relaxation I can think of.
In fact, I wouldn’t even attempt to cut into the mesh, you can always move the road slightly upward or fix z-fighting with the render order in the shader itself.
The raycasting problem arose when we tried to modify the height of the terrain. Sometimes the vertices of the road don’t match the shape/vertices of the terrain and cut into it.
I want to avoid this by placing the road perfectly on the terrain, even if the vertices don’t match. That’s why I was thinking of merging the two objects.
Perhaps the solution is to have the terrain shader render the entire road so that the road is set on the terrain?
Games regularly exploit this cross-section to circumvent the issues you’re having. That’s the easiest and frequently the most natural-looking solution. There is no such thing as terrain paving, like it’s a stripe of paint. (And you’d have to use decals if you were to paint terrain like that.)
This will help you elevate the roadway part above ground. Make sure your banks are deep enough so that you can pull it up until you’re satisfied with the look.
Btw your road, in general, looks great (apart from the bumpiness in places, that could use some work).
And how would you then UV paint such a terrain? Do a terrain with a splat map? No, that doesn’t work.
As I said, one could do decals, but this wouldn’t look too good on the ground level (you can see the local perturbances in terrain which is not how roads look like; roads have this uncanny straight look to them) and that introduces a fair amount of other technical problems, i.e. if you intend to apply physics later on.
First you don’t know how it’s going to be used. You’re right if this is just for cosmetics or for a flight simulator.
But if not, then yes, roads intended for actual cars to drive on are most typically created on top the existing terrain geometry. You do not paint such roads over. A proper generator is built to create the road mesh on top of everything. Also a trapezoid cross-section is a must, and the generator is made in such a way to basically sweep-extrude this cross-section along a delicately formulated spline.
Basically, I duplicate the road to create a new, identical but wider one, which I position below the original. Then I mesh the road edges connecting the two roads to create a single trapezoidal road.
I reassemble everything into a single object, which makes it possible to deal with cases where the road crosses the terrain
The good news is technically you could study the Blender3D source and see what they are doing, or else go find your own favorite knife project algorithm online.
