- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
he.. I once coded similar functions. I was working on a half-life-mod, and there where no predefined functions for the checks I needed, so I approximated what I wanted by multiple calls of TraceLine() or something. (It's been years, don't ask me for details, I don't remember)
not a WTF if you don't have a choice.
Admin
#define DONUT_FACES powdered
mmm...
Admin
Quantam duality people. Two functions: 1. SegmentIsInside() and SegmentIsOutside() - both of which return true. :)
Admin
I've read about 15 comments on this thread and let me just say that the next person that calls [me] a nerd is in trouble!
Admin
Admin
So, is the real WTF that he didn't do:
if (!PointInside(s,p1) || !(PointInside(s,p2)) { return false; }or for that matter:
public bool SegmentInside(Solid s, xyz p1, xyz p2) { xyz v = p2 - p1; for (double t = 0; t <= 1; t += 0.1) { xyz p = p1 + t * v; if (!PointInside(s, p)) { return false; } } return true; }?
Admin
The real WTF is that he didn't render the shape in solid blue and the line in solid red on a solid white background from 10 view points.
Then it's a matter of printing out the rendered images, placing them on a wooden table, taking a photographs, printing the photographs, scanning them and searching the scanned images for red pixels. If none are found, return true, otherwise return false.
The only problem is making the wooden table before you have working woodworking software.
Admin
and for the rest of us the WTF is that you're making a software project for woodwork in your spare time...
Admin
A simple heuristic would be to make the number of checks of the line segment dependant on the length of the line. That would give you a fixed distance between each point which could be fine tuned to whatever level of accuracy is required.
Admin
On "borrowing" code from a raytracer: there are GPLed ones around - no need to breach the POV-Ray license. E.g. http://sourceforge.net/projects/panorama/ - this one is even abandoned.
Admin
Take it from me, donuts do not a good construction material make. I should know, I sat on a 12 pack by mistake once.
Admin
IMHO, that's really the right approach for a solid modeling application. Eric should improve his pattern to make use of these "optimizations." The function prototype is currently:
public bool SegmentInside(Solid s, xyz p1, xyz p2);
But (in C++ syntax) it should be more like:
public:
virtual bool Solid::SegmentInside( xyz p1, xyz p2 );
Then your cylinders, rectangular prisms, sphers, NURBS, etc... they each have their own optimized routine for that particular geometry. That's why CSG modelers are so efficient at these sorts of operations. I don't know about PovRay, but I know that BRL-CAD uses this sort of approach. (Of course, CSG is not so efficient at providing surface data to a display device for fast, shaded viewing.)
Even better, using this OOP approach, the default (fallback) method can be this exact WTF code -- and it won't be such a WTF anymore. As you have time, you add overloaded functions for your ellipsoids, toroids, cones, lions, tigers, bears...
Peace,
Gabriel
CAPTCHA: pizza
Admin
This is the worst WTF ever. Seriously.
Admin
I was going to post something but then I couldn't resist clicking on the Battlestar Galactica image, so there you have it.
Admin
This is an OK solution, but it could be improved to a point where the potential errors doesn't matter by introducing some knowledge of the real world problem we are actually trying to solve.
Why ten points? Why not some other number? The question quickly becomes "Which number?".
Well, we actually know that. We are working with wood and we (or at lest Eric Sink) know what precision we need. Wood only have a certain "resolution" due to grain size and methods used to work with it, and the application may not even need that much. We also have real world measurements somewhere in the system (at least I assume so). So, instead of a fixed number of points, set the points at a certain interval, maybe 1 mm, 0.1 mm or 5 mm, depending on what the application actually needs.
This way, we don't risk unnecessary errors, but still keep a simple and fast algorithm.
Remember, not everything is code, sometimes there are pieces of wood as well to consider.
Admin
Even Quake1 use this tecnicque to move the monsters (his "AI"), and the monsters never ever get stuck on geometry. Fit very well on a BSP based engine because Ispoinssolid is the root of BSP itself.
note to self: Humm... maybe SV_StepDirecction is a better example for this.
--Tei
Admin
I wasn't going to post something but couldn't resist clicking on the Battlestar Galactica image. These advertisements are getting better...
Admin
I like it - post a poor solution to a hard problem as a self wtf and then wait for all the clever readers to offer suggestions on how to solve said hard problem.
The real wtf is that so many people fell for it!
:)
Admin
Is this some kind of a joke where the posters are playing along by saying that the code is OK and shouldn't be "over-engineered"?
The code is horrible and a prime example of shooting yourself in the foot. As long as it's tagged as "to be implemented properly later", it's kinda OK, but what I read here is that many people think it's fine as it is. It's not! You'll get into trouble sooner or later, probably in some very obscure and hard-to-find way, especially if this kind of stuff tends to lurk around in your codebase.
Why is it so that whenever we enter the realm of floating point, dirty hacks and even obviously wrong solutions seem to suddenly become "practical"? I do understand that it's (often) impossible to make bullet-proof algorithms with floating-point arithmetic, but that doesn't mean you can throw in any kind of crap and claim that it's as good as anything.
With discrete stuff, I don't think many people would dare to suggest using similar approach. A string search algorithm that works in 99% of cases? May the wrath of Knuth be upon you! Memory allocator that fails in 0.001% of cases? Better avoid dark alleys if you're ever going to release that. Floating-point anything? What the heck, even a buggy algorithm is better than nothing!
In my view, the original post is not strictly a WTF because the author is going to fix it. The replies that encourage him to keep it that way are.
Admin
As the material is wood getting it wrong won't cause too much damage. If the material is something like titanium then thinking that a line is wholely outside the object when it isn't is likely to result in smashing $100,000s worth of cutting machine head into $10,000s worth of material.
However, in both cases you'll end up with sharp objects flying across a workroom at high speed.
Admin
At first I was went WTF at Carnildo's reply because I thought he was suggesting 10 points at random locations along the line would be superior to 10 evenly spaced points, but are you suggesting random number of evenly spaces points? If so then I completely agree... if not, then it reminds me of the time someone once said to me "It has been scientifically proven that some dogs believe in God", a complete WTF with no apparent basis whatsoever.
I think someone has already covered it, but here's my 2 cents worth: Construct a vector from your two points. If you've setup your engine in any sort of efficient way, it should be pretty simple to test polygon (probably triangle) intersections along a vector. So test your torus/whatever surface for intersections and then see if any of those intersections lie between your points. As for the "how do you test all the surfaces of a torus", you just do - it helps to have some nice trees set up to cut the number of tests down though...
Admin
Hmm. If that's the worst code you can publish for yourself, you're patting yourself on the back more than 'fessing up.
I think it's a bit ugly that you split off the endpoints as special cases. And that you use floats in your loop. And that you have a fixed number of sample points, independent of how long your segment is. But it's just not a WTF that deserves to be on these pages.
It's slightly ugly, but it got the job done.
Regarding a correct solution, that depends primarily on how you're storing solids. I agree with the people who've said use a combination of convex solids, or a combination of some base shapes. That probably fits your apparent model (boolean combination of solids) well. If it's in box A, but also intersects the box subtracted from A, it's not completely in A. But that all seems overkill for your app. (Even worse overkill, IMO, would be using the face-checking scheme proposed by some here, it probably wouldn't work for something like Swiss Cheese anyway). Collision detection isn't easy, especially if you want it to be both fast and exact. And then you almost always need some kind of augmenting data structure.
I'm disappointed with this WTF.
Admin
In the sprit of true Boolean logic, you will want SegmentInside(), SegmentNotInside(), and SegmentFileNotFoundInside().
Admin
Everything depends on what you define to be 'inside'...
Concerning the original WTF: I find it funny how some readers suggest 'solutions' while we don't even know in fact how the geometry is represented. Solids bounded by (polygonal, nurbs, bezier) faces? Parametric equations? Hell, maybe it's some kind of a voxel engine? Plain object soup or organised into some kind of hierarchy? Each of these cases would call for different colision detection algorithms. Luckily a few people seem to realize we don't have enough data to come up with the correct solution.
Admin
yeah, you're probably right. but in my defense... how many times do you want to rewrite a 3D engine? You might as well try and get it right first time round ;)
hmm.. I dunno. I work in the metrology industry which means loads of comparing measured data points to CAD drawings. This by no means makes me correct (I cant STAND people that use their job or its title to try and convince other people that they know what they are talking about - they all deserve slapping with a trout), BUT the method we use for finding the shortest distance between an arbitrary 3D point to the nearest point on an arbitrary NURB surface (i.e., the error in the measured part) involves this method. The reason being it has to work 100% of the time or jet engines that we measure the parts for start blowing up.
Having said that, I'm really beginning to agree with your overkill point of view. Like completely.
Admin
Not without prior knowledge of the objects you're using. If you have a big piece of wood with thin slots, and your line segments start and end inside the wood, there's a good chance it will fail.
Now, the real WTF is using decimals in floating point arithmetic. It would be better to go up in 1/16, if only because the loop increment is exact (or rather, more likely to be exact on a randomly selected platform that isn't a graphing calculator).
That said, the algorithm isn't a WTF at all if you're using polygon geometry anyway, which is generally going to be an approximation to a shape.
Admin
I think everyone missed the most accurate solution: Make the solid and line segment, out of wood of course, and see if they intersect. This way even accounts for the resolution of the wood. Of course you may to use some sort of woodworking software to help make the solid...
Maybe someone should write one.
Admin
Who tells you it is not implemented in this exact same way? :)
Well, he's validating wheter a line intersects a solid, and a solid is, by definition, solid. So it's only inside the solid if the line is inside a non-hollow part of the object. A line completely inside the hollow part would be "outside" of the solid. I think it's the kind of of anti-intuitive things you wind up with when stretching definitions.
What he says.
Admin
Mmh, this is the first time I see a 3d vector class/structure given the name "xyz".
Is that CAD lingo?
Admin
I'm suprised that no one mentionned the one letter variables? s, p1, p2, v, p now that's meaningul! If all the code is like that it must be a nightmare to understand.
And by the way I think it's one of the most non-WTF WTF. Come back giving us REAL WTF Alex!
Admin
That's bit is fair enough. If you read his notes, you'll see the first two tests handle convex shapes.The final loop is to handle concave shapes. It makes some sense to separate the two cases like that.
Ideally you'd have an "if (!IsConcave(s))" wrapped around the second loop, if shapes knew whether they were concave. (Or use a virtual function.)
Admin
One way is to check each face of the solid for wether it intersects with the line..
Quite easy too.
Admin
Amateur ! The right way to do this is of course recursively :
Admin
>>I think it's a bit ugly that you split off the endpoints as special cases.
>That's bit is fair enough. If you read his notes, you'll see the first two tests
>handle convex shapes.The final loop is to handle concave shapes. It makes
>some sense to separate the two cases like that.
The notes only *claim* that the endpoint test handles convex objects, while in reality it doesn't. If one of the points is outside, the result of the function will be false, regardless of the "convexity" of the object. If they both are inside the shape, the loop will be run, again regardless of the "convexity".
Other than that and the somewhat strange loop, the algorithm isn't really that bad. If you define a base class with a "default" virtual implementation like the following, it should be the robust and simple solution.
bool Solid::IsLineInside (Point p1, Point p2) {
Vector v=p2-p1;
int nsteps=2 * v.length() / MaterialConstantMinimumThickness();
v/=nsteps;
Point p = p1;
for (int i=0; i<=nsteps; ++i) {
if (!PointInside(p, p1)) return false;
p+=v;
}
return true;
}
Feel free to override whenever you need a more performant deterministic solution on a class derived from Solid. Chances are, that's never.
Admin
i meant
if (!PointInside(p)) return false;
in the above post, sorry :/
Admin
I think what the claim means is "if only convex shapes were allowed, then the endpoint test would be sufficient".
Admin
<font face="tahoma,arial,helvetica,sans-serif">Reading this gave me a weird feeling of déjà vu...
Reading this gave me a weird feeling of déjà vu...
...
</font>
Admin
I think people are getting a bit confused between graphics libraries and solid modelling problems. Generally graphics libs like DirextX and OpenGL really only model the surfaces of objects - there is no concept of "solidity". How those surfaces are represented - polys, NURBS, etc - is pretty irrelevent to whether they form a manifold solid object. Similarly, BSP trees are there to represent the partitioning of spaces, not the modelling of solids - their use is in quickly determining regions of space that are worthy of further computation based upon locality.
The thing I would ask here is how does "PointInside" work? From the parameter profile it looks like it takes a solid object "s" - whose actual representation is abstracted and therefore you can't infer anything about polygons vs nurbs, convex vs concave etc. I would assume that it does something like a raycast from the supplied point to a random direction and counts the number of boudaries crossed by that ray. If the ray intersects an odd number of boundaries, then the point must be inside the solid - irrespective of its representation. If it intersects zero or an even number of boundaries, then it must lie outside.
A raytesting function is fundamental to any solid modelling system.
There's a few edge conditions such as the point being exactly "on" a surface which complicates this in practice - bit that comes down to the classic Epsilon problem that anyone who regularly deals with floating point/double precision computations has to handle anyway. But, generally, as long as you have a epsilon-sensitive test for when two points are considered equal, then it should all work out.
So, in that function you have the building blocks already of solving the segment-inside problem. You fire a ray from one end of the line to the other, and discard all boundary intersections beyond the second point. If you have any intersections left then the segment will not be wholly enclosed within the solid.
Blimey - it's been a few years since I worked on solid modellers (both CSG & B-rep), so maybe my brain hasn't rusted as much as I thought! If that doesn't leave me wide open to a WTF of my own then nothing will :)