• (cs)

    A self-WTF! Is the Real WTF that you would willingly expose yourself as the writer of WTFy code ;)?

     It's interesting that you don't just split all solids into convex portions; lots of useful geometry tricks don't work with concave shapes and you'll probably end up with lots of similar WTFs to this one.

    (First?)
     

  • AndrewVos (unregistered)

    Err, doesn't directX have a nifty little function to do this for you?

  • (cs)

    I've wondered about the right way to do things like this before. Would it be better (not necessarily time-wise) to check the segment for collisions with all of the faces of the object, and if there are no intersections, a simple IsInside() of one should give the answer. Does anyone know how things like AutoCAD, SketchUp, or what have you do this kind of checking?

  • anonymous (unregistered) in reply to AndrewVos

    Since when is using a naive algorithm, which happens to work for your purpose, a WTF?

    And, you're doing this for a woodworking model, so I really wouldn't be to worried, if I were you, that you were going to need to an unbounded resolution. 

    Over engineering a solution, on the other hand, is a WTF, so, don't fix that "bug".  Or, if you do, you can post your "fix" here, and say, "I had a fine algorithm to solve my problem, but, it didn't demonstrate how much I know about computational geometry, so I came up with this POS, instead."

  • Joe (unregistered) in reply to HitScan

    I was thinking that using a simple line/surface intersection test against all faces of the solid would be the best approach.  It's a fairly standardized procedure and as far as I know would be the cheapest (cpu cycles) way to do this.  Of course this would be done after the PointInside calls for each end of the segment.  If the solid is partitioned or otherwise grouped, you could further reduce the computation overhead by using the partitions to cull out certain faces.

  • whatever (unregistered) in reply to HitScan

    "..check the segment for collisions with all of the faces of the object.." and how do you propose to define all the faces of a doughnut?

  • Anonymous Coward (unregistered)

    You could add some more checks that could speed this up.

    1.  Add a "centroid/radius" to each solid for a sphere that would encompass the entire solid.  With this, you could calculate the distance of closest approach that your given line makes to the centroid -- if this distance is greater than the radius, it's a non-match (if you're looking at many lines w/respect to this object, this'll cut out the bulk of the cases).

    2.  For those that failed #1, add in the  x/y/z limits of the solid, then you can check to see if both points are on the same side of the limits for any of the x/y/z coordinates -- if true, then the line doesn't match.

    3.  If neither of the above cases shows the segment is outside the solid, then a more careful analysis is needed -- see the other posts.



     

  • Araf (unregistered) in reply to Bob Janova

    Arguably, depending on how you've designed it, you could assume that a line is very easy to determine, and instead, make the /shape/ determine if the line is inside itself.

    If you have simple shapes, the solution is easy. If you have complex shapes, those shapes could very well define themselves in terms of concave shapes, and divide up the lines - if all segments are claimed to be inside the respective divided shapes, you're set.

    If you had a transparent bitmap, on the other hand, you could very easily define an isinside method that returns true if the area over which the line is drawn is not transparent.

    ALternatively, you could render all the shapes to a canvas, then manually draw the line, and observe if the pixels change.

  • Joe (unregistered) in reply to whatever

    Anonymous:
    "..check the segment for collisions with all of the faces of the object.." and how do you propose to define all the faces of a doughnut?

     Even donuts are typically stored as a series of triangles. That is, unless you're implementing Bezier curves, splines, NURBS, or the like.  If that's the case then the rules change anyway.  For a workworking app I doubt the necessity of implementing advanced curved surface geometry.

  • Anonymous Coward (unregistered) in reply to Anonymous Coward

    On second thought, skip the first test, just use the second one to filter out the obvious non-matches.

  • Angelo Plasty (unregistered) in reply to Joe

    Anonymous:
    I was thinking that using a simple line/surface intersection test against all faces of the solid would be the best approach.  It's a fairly standardized procedure and as far as I know would be the cheapest (cpu cycles) way to do this.  Of course this would be done after the PointInside calls for each end of the segment.  If the solid is partitioned or otherwise grouped, you could further reduce the computation overhead by using the partitions to cull out certain faces.

     

    why each end?  Wouldn't you only need to test one? 

  • Joe (unregistered) in reply to Angelo Plasty
    Anonymous:

    Anonymous:
    I was thinking that using a simple line/surface intersection test against all faces of the solid would be the best approach.  It's a fairly standardized procedure and as far as I know would be the cheapest (cpu cycles) way to do this.  Of course this would be done after the PointInside calls for each end of the segment.  If the solid is partitioned or otherwise grouped, you could further reduce the computation overhead by using the partitions to cull out certain faces.

     

    why each end?  Wouldn't you only need to test one? 

     Well you could, but if either end lies outside the bounds of the solid, then the rest of the tests are unnecessary.  I would test each end as a point first to reduce potential computation costs. 

  • suutar (unregistered) in reply to whatever

    Well, since you ask... a torus can be represented by a 4th order equation; it shouldn't be too terribly hard to figure out the intersection points between that surface and a line, and determining if the segment lies entirely between the appropriate intersection points should be easy.

    The fork would be harder; that would pretty much have to be done as a conglomeration of multiple shapes.

    I agree the original problem isn't a big WTF. Implementing the test by representing the object in povray, setting the light source at one segment end and the camera at the other, and seeing if you can see light... now that would be a WTF :)

  • Alan (unregistered)

    You should've used XML for this.

  • APAQ11 (unregistered) in reply to Bob Janova

    I don't like these New Fangled lines with all these points... Back in the old days all of our lines only had 10 points and we were happy with em!

  • (cs)

    You should never write code for yourself.  The customer becomes too aware if the internals of your software and starts making really absurd demands.  :)

  • (cs)
    Alex Papadimoulis:
      for (double t = 0.1; t <= 0.9; t += 0.1)

    Oh I get it, the WTF is the use of floating-point numbers without attention to roundoff errors.  He should have used "const int NUM_POINTS = 10; for(int i=1; i<NUM_POINTS; i++) {  double t = i/((double)NUM_POINTS);" or something.  Then he could just change NUM_POINTS for those future enhancements he's talking about!


    On my PC, this loop only goes through 0.8 if I use floats instead of doubles (i.e. on the 9th iteration t<=0.9f fails).

  • parkrrrr (unregistered)

     

    Another WTF in there: using a floating point type for a loop index.  Yeah, it won't be a really big deal in this case, but it's a bad habit to get into.

    And I suppose that pretesting p1 and p2 (vs. just running the loop from 0 to 1) might lead to a slight performance increase, but it seems like it'd be fairly minimal gain in exchange for the maintainability hit.

     

  • kwerle (unregistered)

    SegmentInside is just a bad method name.  It should be named SegmentMostlyInside, or perhaps SegmentOftenInside.


    CAPTCHA: perfection -- I love it.

  • Jethris (unregistered)

    I disagree that this is a WTF.  You had a reason for doing it this way, and you judged the good versus bad in the implementation scheme. 

    A WTF is some bad code written by someone who doesn't know what he/she is doing, using bad practices.  This was a design trade off, and is perfectly acceptable (even if the solution isn't precise)

  • Simplex Shapes Wizard (unregistered) in reply to kwerle

    I agree with the poster who commented that since this was woodworking the shapes would be simple, and so this solution is overengineered.

    Unless you're making something more complex than a block.

    Presumably you don't work on anything ornate like a table leg, a picture frame, anything involving carving, or nearly anything involving a lathe.

    So this function is fine. 

    <> 
  • Rob (unregistered) in reply to kwerle

    Anonymous:
    SegmentInside is just a bad method name.  It should be named SegmentMostlyInside, or perhaps SegmentOftenInside.

    You really don't know how to code, do you.  SegmentMightbeInside is the best name...

     Rob
     

  • (cs)

    When I needed to do something like this, I simply borrowed a chunk of the POV-Ray raytracing engine.

  • Twm (unregistered)

    Could you not store the goemetric structure in a normalised database and then use crystal reports to report if the shapes intersect?

  • David (unregistered)

    Is this a precise modeller using nurb surfaces? Or is this a facet modeller? The approach you take to "solve" this problem will be different.

    If facets: Doing an exhaustive facet to line check will not be bad unless you have a lot of facets. In this case you can sub-divide the rectangular-volume extents of the body into 8 smaller equal volumes (octet). each volume would be associated to any facets that are within/interesect the octet. If there are too many facets within any given octet, that octet can be further sub-divided into octets. In the end the initial intersection test will be done against any top level octets (a simple line-rectpoly intersect). And then against any sub-octets. In the end, only the facets within any "touched" octets need to be checked.

    There will be an initial over-head/memory usage to generate the octets. But once done, they will be static unless the object changes or the faceting precision is changed.

    This approach is used by the LightWorks rendering engine to optimize ray-casting performance. I am not sure about POV or other rendering engines.

    If nurbs: I am not a mathematician. Sorry. ;)

  • parkrrrr (unregistered) in reply to Carnildo

    Carnildo:
    When I needed to do something like this, I simply borrowed a chunk of the POV-Ray raytracing engine.

    You do understand that the license for POV-Ray forbids that, I assume.  Even for personal use.  (Of course we can't really enforce that, but if you can't be honest when nobody's watching, what's the point?)

     

     

  • El Jaybird (unregistered)

    Not TOO bad.  It's a simple heuristic algorithm that gets the job done (presumably) for the purposes of the application.  I can't imagine too many people wanting to make wooden donuts or other severely complex shapes where this algorithm would fail.

     Then again, there's a reason I'm a code monkey and not a mathematician...

    Klein bottle for rent - inquire within

  • (cs)

    WTF? Unit tests? Who needs those?

  • (cs)

    Not a WTF at all. Of course 10 steps is too small, but it can easily expanded to a number which will fit every possible solid that can really be made in woodworking technology. Assuming the largest tree is 100m tall, and the finest possible cut is 1/10 mm, you need to check only 10^6 points to be on the save side.

  • Joey (unregistered) in reply to MaGnA

    The question is... if you have a sphere, that is hollow, and your segment resides totally within the hollow portion... is it inside? or outside? of the solid?

     Is there a spoon?

    I know I should have picked the green pill.

     J.
     

  • (cs)
    Alex Papadimoulis:

    [Note: Today’s article is courtesy of Eric Sink, graciously covering for Alex while he is on vacation this week]

    Granted, it wouldn't be hard to create a unit test which causes this code to fail. In that case I would have to retaliate against myself by simply checking a much higher number of interior points on the line segment. Instead of 10 evenly spaced points, I would check 100 or a 1000. Then I would need another unit test.

    Eventually I would end up with an implementation of SegmentInside which is robust for any practical situation even though it would require essentially infinite time for any case which returns true.

    Anyway, from the perspective of someone who knows computational geometry, this snippet of code is shameful in the extreme, an obvious WTF. I've logged a bug to remind myself to fix it.

     

    Umm, yeah... you don't fix a WTF by extending how WTF'd up it is. You don't increase the number of checks, you use an alternate method. THAT's the true WTF! 

  • anonymous (unregistered) in reply to Simplex Shapes Wizard
    Anonymous:

    I agree with the poster who commented that since this was woodworking the shapes would be simple, and so this solution is overengineered.

    Unless you're making something more complex than a block.

    Presumably you don't work on anything ornate like a table leg, a picture frame, anything involving carving, or nearly anything involving a lathe.

    So this function is fine. 

    <> 

     

    Do I detect sarcasm?  I think I do.  But, the algorithm, even with just 10 cuts, IS fine for any of the shapes you mention, so, what's your point? 

     

  • (cs) in reply to El Jaybird

    I have 2 wooden baby rattles on my desk now that I made on a lathe that each has 2 captured 'donuts'. 

    I don't think the algorithm handles discontinous geometric shapes at all.

    Gonna try for 3 rings next time. 


    Anonymous:

    Not TOO bad.  It's a simple heuristic algorithm that gets the job done (presumably) for the purposes of the application.  I can't imagine too many people wanting to make wooden donuts or other severely complex shapes where this algorithm would fail.

     Then again, there's a reason I'm a code monkey and not a mathematician...

    Klein bottle for rent - inquire within

  • (cs) in reply to Carnildo
    Carnildo:
    When I needed to do something like this, I simply borrowed a chunk of the POV-Ray raytracing engine.

    He he, "borrowed"... I'm sure you spent a great amount of effort to make sure you are complying to the license terms, didn't you? :-)

    The main problem with computer geometry is that there are so many special cases. Let's say you need a function that checks whether two two-dimensional shapes intersect.

    • As long as your only type of shapes is, let's say, ellipses, that's reasonably simple.
    • Add polygons (for simplicity triangles) and now you need code to check: ellipse/ellipse intersection, ellipse/triangle intersection, triangle/triangle intersection
    • etc. - basically, you need something like double dispatch to keep your code reaonably maintainable, and the number of combinations grows quadratically in the number of different shape types.

    And even for a single operation, the code can be quite complex. let's say, for example, you are trying to figure out whether a triangle and a circle intersect (assuming both are on the same plane). Then you already have to distinguish several different cases, e.g.:

    • If the circle contains at least one of the triangle's corners, return true.
    • If all of the triangle's corners are outside the circle, but one of the triangle's edges intersects with the circle, return true.
    • If all of the corners are outside, and none of the edges intersect, it is still possible that the circle lies entirely within the triangle, this can be tested by checking whether the circle's midpoint is within the triangle.

    Now assume you have 4 different types of shapes (which means 4+3+2+1 = 10 different combinations of two) and 3 special cases per combination on average. That means you already have to implement a whopping 30 different geometric tests just to see whether two shapes intersect! Annoying, isn't it?

    So if someone only has to deal with relatively simple shapes and decides to cut corners (please excuse the pun :-) ), I can entirely understand that.

    That said, POV-Ray's handling of CSG (constructive solid geometry) is absolutely impressive. Union that cube and this sphere, intersect with that cone, subtract that paraboloid, add a lathe... it IS really powerful. Unfortunately, of course, I am under the impression that everyone uses triangle meshes these days anyway, so the beauty of CSG is underappreciated by the point-and-click-modelling masses. :-)

  • (cs) in reply to Alexis de Torquemada

    Wikipedia has a short article on CSG, for starters. The boolean union example, though, is not convincing, you can do essentially the same thing by simply using two different objects. Unions are however very useful if you are using (semi-)transparent surface textures. In this case, two separate objects would be rendered as having strange "inside surfaces", while these inside surfaces are eliminated if you use a union.

  • (cs)

    Would a BSP tree be in order here?

  • anonymous (unregistered) in reply to Alexis de Torquemada

    Anonymous:
    Basically, the code will fail for the basic shape used in all art classes:  the ashtray.

     

    No, it won't. He's coded around the concavity problem, he just hasn't done it in a very robust way.  The code will have problems with something like a sawtooth, but even then, he may get lucky.

  • Unklegwar (unregistered) in reply to whatever

    Anonymous:
    "..check the segment for collisions with all of the faces of the object.." and how do you propose to define all the faces of a doughnut?

     

    for purposes of modeling in 3d, as a toroid with a finite number of trangular faces. Like any 3d engine would.

     

  • (cs)

    Guys,

     two (2) things come to mind right away:

     1. perception that it's overengineered (some lollipop will melt in the middle and code it in a way they *think* it should be when it's fubar)

    2.  your definition of why you did it this way is ok, you looked at it, saw what you wanted, and implemented (even though it's a *woodworking* application and <b>overkill<b/> it works as expected.

    p.s. a wtf is a script kiddy induced terror

  • (cs)

    The real WTF here is that everybody here is trying to reinvent this wheel.

     

    Way, way back in 1984, Mac OS 1.0 had this nifty thing called "Regions", and as some people noticed, there are more modern solutionslike directX available.

  • (cs)

    If you're not going to do it the "right" way, it seems like it'd be better to check a random set of points along the line, and then set it up so that the confidence that it was contained would be above a certain threshold.

  • (cs) in reply to duke
    duke:

    If you're not going to do it the "right" way, it seems like it'd be better to check a random set of points along the line, and then set it up so that the confidence that it was contained would be above a certain threshold.

    Why is random better than 10 times like now? How can you with any confidence know how good your method is using random set of points?

  • xcor057 (unregistered)

    I always wondered how they got the jelly inside the donut.

  • (cs) in reply to parkrrrr
    Anonymous:

    Carnildo:
    When I needed to do something like this, I simply borrowed a chunk of the POV-Ray raytracing engine.

    You do understand that the license for POV-Ray forbids that, I assume.  Even for personal use.  (Of course we can't really enforce that, but if you can't be honest when nobody's watching, what's the point?)


    Since this was for personal use, I didn't worry about it.
  • I shall remain nameless (unregistered) in reply to xcor057

    Ladies and gentlemen, the REAL WTF here is that the entire discussion has wandered into a mix of debate over the intricacies of computational, hyperbolic, NURBolic and other geometry... and jelly donuts.


    Did I mention you should have done this in JavaScript?

    CAPTCHA: shizzle

    WTF?

  • (cs) in reply to Alexis de Torquemada
    Alexis de Torquemada:
    Carnildo:
    When I needed to do something like this, I simply borrowed a chunk of the POV-Ray raytracing engine.

    He he, "borrowed"... I'm sure you spent a great amount of effort to make sure you are complying to the license terms, didn't you? :-) 


    I probably could have coded it as a POV-Ray scene file, and been within a strict reading of the license, but this was faster to code and faster to run.

  • Lownewulf (unregistered) in reply to pjsson

    This isn't really a WTF at all.

     This is just sound engineering - a tradeoff between accuracy, computation time, and development time. In this case, the function works more than well enough for most scenarios the developer is concerned with (as demonstrated by his unit tests, another positive point), and the limitations in other scenarios are documented in a bug for future improvements.

     Sorry, you lose at guest editor.

     

  • Boojum (unregistered) in reply to pjsson
    pjsson:
    duke:

    If you're not going to do it the "right" way, it seems like it'd be better to check a random set of points along the line, and then set it up so that the confidence that it was contained would be above a certain threshold.

    Why is random better than 10 times like now? How can you with any confidence know how good your method is using random set of points?

  • Anonymous (unregistered) in reply to pjsson

    pjsson:
    Three little sentences that will get you through life: 1: I’m 90% done with that function! 2: Oh, good idea, Boss! 3: It always worked like that!

    One little sentence committing you to a life of doom:  I do. 

  • TheMoog (unregistered) in reply to DreamerFi
    DreamerFi:

    The real WTF here is that everybody here is trying to reinvent this wheel.

     

    Way, way back in 1984, Mac OS 1.0 had this nifty thing called "Regions", and as some people noticed, there are more modern solutionslike directX available.

    I can't speak for Mac OS, but since when has DirectX had any form of collision detection?

Leave a comment on “Eric Sink on EricSink()”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article