3d width and cross section - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T05:23:27Z http://mathoverflow.net/feeds/question/50561 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50561/3d-width-and-cross-section 3d width and cross section ojala 2010-12-28T14:05:28Z 2010-12-28T20:06:04Z <p>Greetings,</p> <p>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.</p> <p>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? </p> <p>Thank you </p> http://mathoverflow.net/questions/50561/3d-width-and-cross-section/50562#50562 Answer by optima for 3d width and cross section optima 2010-12-28T14:18:50Z 2010-12-28T14:18:50Z <p>These are applied computational geometry questions, not really mathematics research questions.</p> <p><a href="http://en.wikipedia.org/wiki/Computational_geometry" rel="nofollow">http://en.wikipedia.org/wiki/Computational_geometry</a></p> <p>Maybe try asking on stackoverflow or on a blender or CAD forum or something.</p> <p><a href="http://www.blender.org/" rel="nofollow">http://www.blender.org/</a></p> http://mathoverflow.net/questions/50561/3d-width-and-cross-section/50593#50593 Answer by Cristi Stoica for 3d width and cross section Cristi Stoica 2010-12-28T20:06:04Z 2010-12-28T20:06:04Z <blockquote> <p>how to find those cross-sections?</p> </blockquote> <ul> <li>Find/write a function which intersects a triangle and a plane (e.g. <a href="http://www.geometrictools.com/" rel="nofollow">Dave Eberly's wild magic library</a>). Provided that you need to intersect only with plane perpendicular to the Z axis, you may optimize it.</li> <li>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.</li> <li>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).</li> <li>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.</li> <li>You can try to optimize it by BSP.</li> </ul> <blockquote> <p>how to find (efficiently) the maximum width of the body</p> </blockquote> <ul> <li>It is enough to intersect with planes having Z=Z of the vertices in your mesh.</li> <li>To optimize, calculate just the AABB's for each Z, and make a list sorted descending by the diagonal of the AABB.</li> <li>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)</li> <li>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")</li> <li>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).</li> <li>Do this until you reach the end of the list (or the bookmark) </li> </ul>