2
\$\begingroup\$

I'll try to be as clearer as I can.

I have a surface on a 3D space which is not flat, it has hills and depths.

My goal would be intersect it with a plane so that I can map the section of the surface on it.

this is just an example with a tetrahedron, my surface is more complex:

enter image description here

My surface has just a set of vertexes so I was thinking that the solution would be theorically to map the intersection points of line segments bounding each vertex just above the plane with its corresponding one just below. Then I could connect the points on the plane like if I was drawing triangles on a flat surface.

My concern is also on what structures can I use to achieve this result? Does XNA give anything that could be of help? I saw the Plane structure and its explaination was quite clear. So next step would be to find the point belonging to a line segment laying on the plane, but sincerly I have no idea on how to proceed.

More than that, I also would like to be able to compute areas of "solid ground" mapped on the plane. But better to face one problem at time.

Hoping I made myself clar, I look forward to any suggestion

\$\endgroup\$
2
\$\begingroup\$

It would be simple and cheap to check if a given vertex is above or under a plane [1], but I guess it wouldn't help you to create the mesh of your terrain section.

I think you should have your surface triangulated first [2] and then check the intersection of each triangle with the desired plane [3].

For each intersecting triangle you should generate 2 other triangles. You should also store the intersection points for later use (see below).

For each non-intersecting triangle you should check if it's above of below the plane (this can also be part of the result of your chosen triangle x plane intersection method), because you only want to use the triangles below the plane.

The top cap of the intersected areas could be computed from the previously stored intersection points. Compute the top cap polygons [4], triangulate them [5] and generate the top cap meshes.

This way you should end up with the mesh of the terrain under the plane and the top cap meshes.

I guess you could optimize this solution, specially with the computation of the top cap polygon...

References:

[1] Point direction from a Plane:

http://www.gamedev.net/topic/106765-determining-if-a-point-is-in-front-of-or-behind-a-plane/ (Math)

[2] Famous libraries for tetrahedralization:

http://doc.cgal.org/latest/Triangulation_3/index.html (C++)

http://wias-berlin.de/software/tetgen/ (C++)

[3] Triangle x Plane intersection algorithms:

https://stackoverflow.com/questions/3142469/determining-the-intersection-of-a-triangle-and-a-plane (Pseudo-code)

http://www.realtimerendering.com/intersections.html (C)

[4] Clustering + Convex Hull Algorithms:

http://www.alglib.net/dataanalysis/clustering.php (has a C# port)

https://stackoverflow.com/questions/16407533/translating-concave-hull-algorithm-to-c-sharp (another C# impl.)

[5] Ear-clipping triangulation:

http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf (Pseudo-code)

\$\endgroup\$
  • \$\begingroup\$ This sounds interesting, Pedro. Thank you. I will need some time to elaborate. I will tell you what will I sort out \$\endgroup\$ – Leggy7 Jan 23 '14 at 10:57
  • \$\begingroup\$ I was thinking... maybe you could just project the points "above" the plane into the plane and then triangulate 'em \$\endgroup\$ – Pedro Boechat Feb 21 '14 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.