tag:blogger.com,1999:blog-64677944282169675082024-02-06T18:46:24.169-08:00RoomBuilderRoomBuilderhttp://www.blogger.com/profile/02145138002932238239noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6467794428216967508.post-37645244135860094622008-09-11T13:57:00.000-07:002008-09-11T14:02:45.534-07:00External straight skeletonsOK, not much of a catchy title. However, if you've been reading about the issues I've been having with calculating <span style="font-weight: bold;font-family:arial;" >external</span><span style="font-family:arial;"> straight skeletons, you may know a little about what I'm talking about. After some time spent scratching my head, walking away from the problem and a fair bit of frustration (OK, a lot), it's time for an update.</span><br /><br /><span style="font-family:arial;">To recap, straight skeletons are useful data structures for calculating the offset path for a (simple) polygon. They are also used for calculating roof structures. Most of the material I've found on the web seems to be concerned with calculating internal skeletons, although no distinction is usually made between the two types.</span><br /><br /><span style="font-family:arial;">To be able to expand polygonal paths I need to be able to calculate external skeletons. Unfortunately, I've found that these are less frequently discussed and appear to have features that you don't encounter in internal skeletons. I've nicknamed these 'breakthrough vertexes'. These occur when a 'pointed' section of a path overtakes and punches through a different edge as the path is expanded. They produce skeleton arcs that have no parent node in the original path, and may be completely disconnected from the main skeleton.</span><br /><br /><span style="font-family:arial;">My original implementation of a straight skeleton algorithm had no concept of these features. While it handled a lot of external paths with no problems, it was unable to cope with paths with breakthrough </span>verticies<span style="font-family:arial;">, producing odd looking results (as covered in an earlier post). I have now managed to modify my original algorithm to cope with these.</span><br /><br /><span style="font-family:arial;">The first example uses the path that originally </span>alerted<span style="font-family:arial;"> me to the problem. It contains one breakthrough edge and is a relatively </span>trivial<span style="font-family:arial;"> test case. Note how the skeleton contains a group of arcs centred on the source of the breakthrough event and how these affect the offset path.</span><br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0r6uq5ZN7jpXvRcJ41YyF3EBc7S2IakHPVnkT9cBIG9CSy-vWCYIHkqOn6GokNgnwQsfXKqpmTHx2S4N6P-wp3xv56Wkt2-AmgXTbGDVTmznfRd_QFpmNuFjzxRGGto5jg2zD_wC5WO4/s1600-h/OriginalBreakthrough.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0r6uq5ZN7jpXvRcJ41YyF3EBc7S2IakHPVnkT9cBIG9CSy-vWCYIHkqOn6GokNgnwQsfXKqpmTHx2S4N6P-wp3xv56Wkt2-AmgXTbGDVTmznfRd_QFpmNuFjzxRGGto5jg2zD_wC5WO4/s400/OriginalBreakthrough.png" alt="" id="BLOGGER_PHOTO_ID_5244871687314386850" border="0" /></a><br />A more complex example of a breakthrough event is shown in the next example. In this case, the breakthrough location occurs at a point where an edge has already disappeared. The breakthrough arcs are also connected to the main skeleton.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhv8bJu5z-tZNuCFd9Ifn1yXvkFnhsf93fwLBr_m82que9Phv_1hv50g2LWZuGuf8TNFzPksUDIEoB0wIfcDgkdqweLwaXGjPU2MOWlA1XHtawAWBu4_hwGAZQQ6VKCOCjLyTv9HimNx2A/s1600-h/ComplexBreakthrough.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhv8bJu5z-tZNuCFd9Ifn1yXvkFnhsf93fwLBr_m82que9Phv_1hv50g2LWZuGuf8TNFzPksUDIEoB0wIfcDgkdqweLwaXGjPU2MOWlA1XHtawAWBu4_hwGAZQQ6VKCOCjLyTv9HimNx2A/s400/ComplexBreakthrough.png" alt="" id="BLOGGER_PHOTO_ID_5244871802095915202" border="0" /></a><br /><br />The final path shows another potential issue. In this case, two breakthrough edges coincide, producing several arcs centered on the breakthrough location.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyYY81QOiZNnEGDL5xPuXsT4AJKdZss7ry-4vMND1RSu2nhYCWlw7qmtijlEyIJAIFWG6GZupkiKXDzci2Pu0rv7J-k4xr8KKAEEfT4ybpsaMSUuj25Ds8hgHlxCio3rP30ra7Sxdg6kE/s1600-h/CoincidentBreakthrough.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiyYY81QOiZNnEGDL5xPuXsT4AJKdZss7ry-4vMND1RSu2nhYCWlw7qmtijlEyIJAIFWG6GZupkiKXDzci2Pu0rv7J-k4xr8KKAEEfT4ybpsaMSUuj25Ds8hgHlxCio3rP30ra7Sxdg6kE/s400/CoincidentBreakthrough.png" alt="" id="BLOGGER_PHOTO_ID_5244871911401623602" border="0" /></a><br />Hopefully, these examples illustrate some of the complexities you can encounter when it comes to external skeletons. In each case, I've had to refine my code, while testing that I haven't broken something else. Unit tests have been a great help here, and yes, altering my code caused simpler cases to break several times. Really frustrating! There's bound to be some path out there that I haven't considered yet, but at the moment I'm pleased with my results.<br /><br />Out of interest, breakthrough points occur more frequently than you might expect. However, if you're just calculating small offsets, you may not notice that your code doesn't cope with them. One of the paths in my earlier post actually has a more complex external skeleton that is shown, but this was not obvious at first. It was only when I went back and reran my previous tests (after adding some new code) that the skeleton changed to something that I thought looked odd, but it was correct.RoomBuilderhttp://www.blogger.com/profile/02145138002932238239noreply@blogger.com0tag:blogger.com,1999:blog-6467794428216967508.post-11642515354825593112008-09-11T13:06:00.000-07:002008-09-11T13:55:45.900-07:00Breakthrough - External Straight Skeleton Nodes<span class="blsp-spelling-corrected" id="SPELLING_ERROR_0">OK</span>, not much of a catchy title. However, if you've been reading about the issues I've been having with calculating <span style="font-weight: bold;">external</span> straight skeletons, you may know a little about what I'm talking about. After some time spent scratching my head, walking away from the problem and a fair bit of frustration (OK, a lot), it's time for an update.<br /><br />To recap, straight skeletons are useful data structures for calculating the offset path for a (simple) polygon. They are also used for calculating roof structures. Most of the material I've found on the web seems to be concerned with calculating internal skeletons, although no distinction is usually made between the two types.<br /><br />To be able to expand polygonal paths I need to be able to calculate external skeletons. Unfortunately, I've found that these are less frequently discussed and appear to have features that you don't encounter in internal skeletons. I've nicknamed these 'breakthrough <span class="blsp-spelling-error" id="SPELLING_ERROR_1">verticies</span>'. These occur when a 'pointed' section of a path overtakes and punches through a different edge as the path is expanded. They produce skeleton arcs that have no parent node in the original path, and may be completely disconnected from the main skeleton.<br /><br />My original implementation of a straight skeleton algorithm had no concept of these features. While it handled a lot of external paths with no problems, it was unable to cope with paths with breakthrough <span class="blsp-spelling-error" id="SPELLING_ERROR_2">verticies</span>, producing odd looking results (as covered in an earlier post). I have now managed to modify my original algorithm to cope with these.<br /><br />The first example uses the path that originally <span class="blsp-spelling-corrected" id="SPELLING_ERROR_3">alerted</span> me to the problem. It contains one breakthrough edge and is a relatively <span class="blsp-spelling-corrected" id="SPELLING_ERROR_4">trivial</span> test case. Note how the skeleton contains a group of arcs centred on the source of the breakthrough event and how these affect the offset path.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjHxMajy6EzjKZoqQjhOZuTD9pr5lYb9eGcosNZMKNiN-VwoKI4UR5f8EYeXDv6IWn6JYsKGQ8xGhfM63pNCHQ2AbiFIHdGYwnLJLQM2GDsfJksdPcxtmSGbB4X1T0O98mz47ivoYZ_nF4/s1600-h/OriginalBreakthrough.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjHxMajy6EzjKZoqQjhOZuTD9pr5lYb9eGcosNZMKNiN-VwoKI4UR5f8EYeXDv6IWn6JYsKGQ8xGhfM63pNCHQ2AbiFIHdGYwnLJLQM2GDsfJksdPcxtmSGbB4X1T0O98mz47ivoYZ_nF4/s320/OriginalBreakthrough.png" alt="" id="BLOGGER_PHOTO_ID_5244865619896874610" border="0" /></a><br />A more complex example of a breakthrough event is shown in the next example. In this case, the breakthrough location occurs at a point where an edge has already disappeared. The breakthrough arcs are also connected to the main skeleton.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_JDkLTnl1Y9afw_B8AOea2wYRT6dNc6h1M20cR-sMaMDzk_FCnaJloQyVYJkKJLIn_kGrECydUiNSgoUcK2lugBrWuRTEoypnbO5UkVVwW5MCM39i1UOpSmAWo-n5Imp1Un5tjLIKViQ/s1600-h/ComplexBreakthrough.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_JDkLTnl1Y9afw_B8AOea2wYRT6dNc6h1M20cR-sMaMDzk_FCnaJloQyVYJkKJLIn_kGrECydUiNSgoUcK2lugBrWuRTEoypnbO5UkVVwW5MCM39i1UOpSmAWo-n5Imp1Un5tjLIKViQ/s320/ComplexBreakthrough.png" alt="" id="BLOGGER_PHOTO_ID_5244866862238027586" border="0" /></a><br />The final path shows another potential issue. In this case, two breakthrough edges coincide, producing several arcs centered on the breakthrough location.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdRIqtELe53InKPg3BoG9jyjBL1J655d0SnJ9_TrrzvD6nNR_NCzmpcWhOx_SkOR8zIbkf713YpT932HHhyphenhyphenofsO2BDM38u_UXOuih_jp0Dm6IOn_0YX5YoiuicEdodaCJznuCCIRPIRos/s1600-h/CoincidentBreakthrough.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdRIqtELe53InKPg3BoG9jyjBL1J655d0SnJ9_TrrzvD6nNR_NCzmpcWhOx_SkOR8zIbkf713YpT932HHhyphenhyphenofsO2BDM38u_UXOuih_jp0Dm6IOn_0YX5YoiuicEdodaCJznuCCIRPIRos/s320/CoincidentBreakthrough.png" alt="" id="BLOGGER_PHOTO_ID_5244867360740434866" border="0" /></a><br />Hopefully, these examples illustrate some of the complexities you can encounter when it comes to external skeletons. In each case, I've had to refine my code, while testing that I haven't broken something else. Unit tests have been a great help here, and yes, altering my code caused simpler cases to break several times. Really frustrating! There's bound to be some path out there that I haven't considered yet, but at the moment I'm pleased with my results.<br /><br />Out of interest, breakthrough points occur more frequently than you might expect. However, if you're just calculating small offsets, you may not notice that your code doesn't cope with them. One of the paths in my earlier post actually has a more complex external skeleton that is shown, but this was not obvious at first. It was only when I went back and reran my previous tests (after adding some new code) that the skeleton changed to something that I thought looked odd, but it was correct.RoomBuilderhttp://www.blogger.com/profile/02145138002932238239noreply@blogger.com0tag:blogger.com,1999:blog-6467794428216967508.post-10922717450473880152007-03-06T11:41:00.001-08:002007-03-06T11:41:43.238-08:00Composite<div style="float: right; margin-left: 10px; margin-bottom: 10px;"> <a href="http://www.flickr.com/photos/7229688@N03/412850745/" title="photo sharing"><img src="http://farm1.static.flickr.com/129/412850745_80d2aa2c63_m.jpg" alt="" style="border: solid 2px #000000;" /></a> <br /> <span style="font-size: 0.9em; margin-top: 0px;"> <a href="http://www.flickr.com/photos/7229688@N03/412850745/">Composite</a> <br /> Originally uploaded by <a href="http://www.flickr.com/people/7229688@N03/">autumn_zero</a>. </span></div>Here's some snapshots of RoomBuilder V1 in output. Textured and rendered in CinemaXL 9.<br clear="all" />RoomBuilderhttp://www.blogger.com/profile/02145138002932238239noreply@blogger.com0