Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Greetings,

We have a horn-shaped 3d body, which is represented as a list of vertices and faces. Each face is a triangle represented by 3 vertices. The body is positioned along the Z-axis (height). We would like to make several cuts at certain heights. Each cut (a plane perpendicular to the Z- axis) may create one or more cross-sections with the body (the body may split to several branches). The question is how to find those cross-sections.

Another question: how to find (efficiently) the maximum width of the body, i.e. 2 points (not necessarily from the list of vertices) on the surface of the body with the same z-coordinate, and maximum distance between them?

Thank you

share|improve this question
1  
This isn't the right forum for this question. –  Peter Shor Dec 28 '10 at 14:27
add comment

2 Answers

up vote 0 down vote accepted

These are applied computational geometry questions, not really mathematics research questions.

http://en.wikipedia.org/wiki/Computational_geometry

Maybe try asking on stackoverflow or on a blender or CAD forum or something.

http://www.blender.org/

share|improve this answer
1  
The above should be a comment, not an answer. –  Daniel Moskovich Dec 28 '10 at 15:41
1  
But the poster didn't have enough reputation for a comment. –  Peter Shor Dec 28 '10 at 19:02
add comment

how to find those cross-sections?

  • Find/write a function which intersects a triangle and a plane (e.g. Dave Eberly's wild magic library). Provided that you need to intersect only with plane perpendicular to the Z axis, you may optimize it.
  • Intersect all triangles with the plane. You will obtain a list of segments (some of them may be of null length) - let's call it the raw list.
  • Make a list of lists (I will name them section-lists), like this: Take one segment. Search through the others which segment has a vertex in common with yours. Make sure to makle the comparison within a tolerance. Whenever you move one segment to a section-list, remove it from the raw list. When you complete section-list by adding to it a complete polygon, start a new section-list and fill it starting with the next segment (repeat).
  • Now you have a list of polygons which are the cross-section. The cross-section may be disconnected, that is, you have more elements in your list.
  • You can try to optimize it by BSP.

how to find (efficiently) the maximum width of the body

  • It is enough to intersect with planes having Z=Z of the vertices in your mesh.
  • To optimize, calculate just the AABB's for each Z, and make a list sorted descending by the diagonal of the AABB.
  • Take the first element, and find the maximum diameter (say "current_width") (it is enough to do this for the vertices of the cross-section polygon)
  • From the diagonal-sorted list, keep only those with the diagonal greater than the current_width (you just need an iterator, will call it "bookmark")
  • Move to the next element of the list, find the new current_width, and if it is greater, replace the old one and remove again from the list the elements with smaller diagonal (or update the bookmark).
  • Do this until you reach the end of the list (or the bookmark)
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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