Comment On Eric Sink on EricSink()

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?)
 

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

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?

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."

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.

"..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?

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.

 

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.

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.

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

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? 

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. 

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 :)

You should've used XML for this.

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!

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

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).

 

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.

 

I think this must be a specialised WTF as I agree with previous comments that this isn't so bad so long as it was intended for a later fix.

( although when I see myself type this I think of all those @TODO: comments that I have seen )

Is there any benefit to checking p1 first, when it could easily be made the first point checked in the loop.  ( Likewise p2, which could be the last point ).

I guess also that if you can divide vector v by 10, then the loop need not compare integers or multiply to get the test point.

All of these are optimisations though, rather than truly bad code

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

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)

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. 

<> 

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
 

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

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

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. ;)

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?)

 

 

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

WTF? Unit tests? Who needs those?

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.

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.
 

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:

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? 

 

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

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. :-)

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.

I have mentioned on several occasions that I am building a piece of woodworking software as a hobby project. Part of this effort required me to dig into the world of computational geometry and write a solid modeling library.

 

Why write your own? E.g.  http://www.cgal.org/

Would a BSP tree be in order here?

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.

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.

 

I suspect a snippet of spobliteratefsobject would've made a better DailyWTF

Anonymous:

I have mentioned on several occasions that I am building a piece of woodworking software as a hobby project. Part of this effort required me to dig into the world of computational geometry and write a solid modeling library.

 

Why write your own? E.g.  http://www.cgal.org/

 

because it's an execise you can learn something from. because he wanted to. 

 

site wtf: hitting ENTER on the CAPTCHA textbox launches the search.

 

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

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.

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.

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?

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

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?)

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.

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? :-)