looking for an algorithm

[Galun]

This is an off-topic question which might get an on-topic one later in case I'm able to build a plugin.

I'm looking for ideas on the following problem:

Imagine there is a piece of flat cloth in space along x and z axis. Above there are several boxes and to keep it simple let's say there bottom surface is as well on x and z axis.
Now I want to stick the cloth to the bottom surface of the boxes - one after one so that the cloth surface is split and contains all the vertices of the bottom surfaces. The corners of the cloth should remain where they are so that it spans from its original corner points to the corner points of the bottom surfaces. That way a kind of terrain is built between the boxes and the former flat cloth (plane) gets a mesh (preferrably a trimesh).
I tried with splitting the triangle below the vertices but that way you end up with deep "canions" on some edges as in some cases you have to disregard one edge (i.e split an edge not a triangle) but I haven't found a way to programmatically find the correct one.

BTW: I would like to use such a function to pre-build a terrain inside a city and the boxes are the buildings and other items which should stick to the ground.
After that step it could be smoothed and altered.

Any ideas how to do that?

[lisa]

I *think* I follow you, but please call me out if I'm not understanding correctly. You have a random collection of objects at various random elevations ("buildings"). You have a quad definining a region that surrounds all of the objects; you want to turn this quad into a terrain patch. You may (or may not) have a heightfield representing the ground elevations that you want to combine with the buildings, the idea being that you have a terrain with flat spots where the buildings go.

If I were implementing this, instead of carving your mesh I might suggest a depth-buffer based approach followed by generating a regular mesh from the depth buffer. It's a little more straight-forward to calculate, and better yet, it can be accomplished in hardware if you are so inclined.

[I'm going to break the rest of my explanation up into multiple posts, since you can only have a couple of pictures per post, and this will make a lot more sense if I illustrate it.]

[lisa]

Step 1:
Generate an isometric projection from the bounds of your desired terrain patch at the minimum elevation of the ground. i.e. So the camera view frustum is pointing up from below at the ground.

[lisa]

Step 2:
Render your building elevations to a depth map. i.e. You want to save the z-buffer from your render to a texture.

If you google "shadow mapping" you can find lots of sample code to learn how to do that.

[lisa]

Step 3: (first image)
Blur the depth texture you created. You may need to add the texture to itself to increase the strength; the goal is to have an area outside each building also marked at the same depth.

Step 4: (second image)
Also render a mask texture representing the buildings. If you are doing this in hardware, render to the stencil buffer at the same time as you render your depth texture. Then render a black and white quad combining them with the stencil buffer to create the mask texture.

Using the same basic method as step 3, blur the mask texture also.

[lisa]

Step 5:
Using the mask texture you rendered, combine the blurred depth texture you rendered with your terrain heightmap.

first image: This shows the terrain heightmap you want to combine. These are randomly generated from a perlin noise function or whatever floats your boat.

second image: This is the terrain heightmap combined with the building depth texture using the mask texture.

Optionally, you can smooth the resulting image to make it look better or whatever you want to do after the images are merged.

[lisa]

Step 6:
Use your resulting image as a heightfield, sampling it at regular intervals to generate the terrain geometry.

If you want to, you can collapse faces based on angle to reduce the number of vertices, or any other optimizations you want to make.

There are surely many other ways to go about what you want to do, but this was the first one that came to mind. Hope this helps! :)

[Galun]

That's a very cool approach and I'm quite sure it would look very nice.

On the other hand I was thinking about a low-poly solution as a pre-processing step back into AC3D.
I found algorithms to triangulate a surface made from a point cloud e.g. a scanner result but that would be quite some overhead. This needs more regular distances between points so that won't work anyway.

I think I need some way to find neighbor vertices and build triangles. That way I would get a small amount of triangles - hopefully.

[lisa]

Have you tried looking at any of the convex hull algorithms? One of those might work.

[Galun]

I finally decided to go with a Delaunay triangulation using an external Java program.
This reads the .ac file, triangulates a surface that is marked as terrain and writes back to a new .ac file.

Now I think it would be cool to write a plugin that starts a JVM via JNI so that I can get the same result directly in AC3D .. ;)

[Andy]

Not wishing to negate your work but, AC3D already does Delaunay triangulation - menu Vertex->Create-2d-mesh.

[Galun]

Oops, sometimes it's so easy...