The Daily WTF: Curious Perversions in Information Technology

2006-09-14 Reply 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.

2006-09-14 Reply Admin

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?

#define DONUT_FACES powdered

mmm...

2006-09-14 Reply Admin

Quantam duality people. Two functions: 1. SegmentIsInside() and SegmentIsOutside() - both of which return true. :)

2006-09-14 Reply 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!

Carnildo · 2006-09-14 Reply Admin

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?

There are statistical techniques that can tell you exactly how confident you should be that the result is correct, for a given number of points.

2006-09-14 Reply 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;
}

?

Some Idiot · 2006-09-14 Reply 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.

lomaxx · 2006-09-14 Reply Admin

Alex Papadimoulis:

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.

and for the rest of us the WTF is that you're making a software project for woodwork in your spare time...

2006-09-14 Reply 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.

felix · 2006-09-15 Reply 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.

2006-09-15 Reply Admin

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?

Take it from me, donuts do not a good construction material make. I should know, I sat on a 12 pack by mistake once.

2006-09-15 Reply Admin

Alexis de Torquemada:
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.

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

2006-09-15 Reply Admin

This is the worst WTF ever. Seriously.

deathkrush · 2006-09-15 Reply Admin

I was going to post something but then I couldn't resist clicking on the Battlestar Galactica image, so there you have it.

2006-09-15 Reply 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.

2006-09-15 Reply Admin

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

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.

/*
======================
SV_MoveToGoal

======================
*/
void
SV_MoveToGoal ( void )
{
	edict_t		*ent, *goal;
	float		dist;
#ifdef QUAKE2
	edict_t		*enemy;
#endif

	ent = PROG_TO_EDICT(pr_global_struct->self);
	goal = PROG_TO_EDICT(ent->v.goalentity);
	dist = G_FLOAT(OFS_PARM0);

	if ( !( (int)ent->v.flags & (FL_ONGROUND|FL_FLY|FL_SWIM) ) )
	{
		G_FLOAT(OFS_RETURN) = 0;
		return;
	}

// if the next step hits the enemy, return immediately
#ifdef QUAKE2
	enemy = PROG_TO_EDICT(ent->v.enemy);
	if (enemy != sv.edicts && SV_CloseEnough (ent, enemy, dist) )
#else
	if ( PROG_TO_EDICT(ent->v.enemy) != sv.edicts && SV_CloseEnough (ent, goal, dist) )
#endif
		return;

// bump around...
	if ( (rand()&3)==1 ||
	!SV_StepDirection (ent, ent->v.ideal_yaw, dist))
	{
		SV_NewChaseDir (ent, goal, dist);
	}
}

note to self: Humm... maybe SV_StepDirecction is a better example for this.

--Tei

2006-09-15 Reply Admin

deathkrush:
I was going to post something but then I couldn't resist clicking on the Battlestar Galactica image, so there you have it.

I wasn't going to post something but couldn't resist clicking on the Battlestar Galactica image. These advertisements are getting better...

2006-09-15 Reply 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!

:)

2006-09-15 Reply 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.

2006-09-15 Reply 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.

tlg · 2006-09-15 Reply Admin

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

There are statistical techniques that can tell you exactly how confident you should be that the result is correct, for a given number of points.

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

2006-09-15 Reply 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.

GeekMessage · 2006-09-15 Reply Admin

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

In the sprit of true Boolean logic, you will want SegmentInside(), SegmentNotInside(), and SegmentFileNotFoundInside().

2006-09-15 Reply Admin

Anonymous:
Quantam duality people. Two functions: 1. SegmentIsInside() and SegmentIsOutside() - both of which return true. :)

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.

tlg · 2006-09-15 Reply Admin

Anonymous:

Even worse overkill, IMO, would be using the face-checking scheme proposed by some here,

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

Anonymous:

it probably wouldn't work for something like Swiss Cheese anyway

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.

TeeSee · 2006-09-15 Reply Admin

Carnildo:
There are statistical techniques that can tell you exactly how confident you should be that the result is correct, for a given number of points.

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.

2006-09-15 Reply 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.

Enric Naval · 2006-09-15 Reply Admin

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

Who tells you it is not implemented in this exact same way? :)

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

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.

An apprentice:
Everything depends on what you define to be 'inside'...

What he says.

2006-09-15 Reply Admin

Mmh, this is the first time I see a 3d vector class/structure given the name "xyz".
Is that CAD lingo?

Monkeyget · 2006-09-15 Reply 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!

2006-09-15 Reply Admin

Anonymous:

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.

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

2006-09-15 Reply Admin

One way is to check each face of the solid for wether it intersects with the line..

Quite easy too.

2006-09-16 Reply Admin

Amateur ! The right way to do this is of course recursively :

public bool SegmentInside(Solid s, xyz p1, xyz p2)
{

  if (p1==p2 && PointInside(s, p1))
  {
    return true;
  }

  if (!PointInside(s, p1))
  {
    return false;
  }

  if (!PointInside(s, p2))
  {
    return false;
  }

  xyz m = (p1 + p2)/2;

  return  (SegmentInside(s, p1, m) && SegmentInside(s, m, p2));

2006-09-18 Reply 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.

2006-09-18 Reply Admin

i meant

if (!PointInside(p)) return false;

in the above post, sorry :/

iwpg · 2006-09-18 Reply Admin

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

I think what the claim means is "if only convex shapes were allowed, then the endpoint test would be sufficient".

xrT · 2006-09-18 Reply Admin

Anonymous:

Gosh Eric, I think the WTF here is we let you guest post.
Seems like it worked, was simple, and it passed all the required unit tests for that particular problem. "Where's the Beef??"
Until a bug was logged requiring a fix, this isn;t a big deal.
The other WTF is you assume all us old people remember geometry class, and WTF concave and covex are (damn, there I said it..) :
Definitions of concave on the Web:

...

Definitions of convex on the Web:
...

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

GregW · 2006-09-20 Reply 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 :)

2023-08-19

Comment held for moderation.

2023-08-19

Comment held for moderation.

2023-08-19

Comment held for moderation.

2023-08-19

Comment held for moderation.

2023-08-19

Comment held for moderation.

2023-08-19

Comment held for moderation.

2023-08-19 Reply Admin

Рентабельность производства туалетной бумаги – примерно 11% https://solyariswell.com/catalog/17-ru/oborudovanie-dlya-proizvodstva/netkannye-materialy/42-avtomaticheskij-stanok-pnm-1 Это значит, что начальные инвестиции не окупятся раньше, чем через 2 года https://solyariswell.com/catalog

Подведем итоги https://solyariswell.com/catalog/24-ru/oborudovanie-dlya-proizvodstva/stanki-dlya-proizvodstva/peremotochno-namotochnye-stanki/22-peremotochno-namotochnyj-stanok-pm-6m Можно с уверенностью сказать, что производство туалетной бумаги — это хороший бизнес для вложения средств https://solyariswell.com/catalog/17-ru/oborudovanie-dlya-proizvodstva/netkannye-materialy/88-avtomaticheskij-stanok-pnm Если подобрать надежных поставщиков оборудования, расширить ассортимент продукции и наладить сбыт, можно получать высокую прибыль https://solyariswell.com/en/20-en/equipment/rewinder-for-winding/57-pm-7m Конечно, понадобятся первоначальные вложения https://solyariswell.com При налаженном цикле производства можно выйти на чистую прибыль уже через год https://solyariswell.com/catalog

Омский бумажный завод https://solyariswell.com/catalog/17-ru/oborudovanie-dlya-proizvodstva/netkannye-materialy/88-avtomaticheskij-stanok-pnm

По технологии производство кухонных полотенец, гигиенических и столовых салфеток практически не отличается от технологии производства туалетной бумаги, и это позволяет сделать ассортимент еще шире https://solyariswell.com/catalog/24-ru/oborudovanie-dlya-proizvodstva/stanki-dlya-proizvodstva/peremotochno-namotochnye-stanki/22-peremotochno-namotochnyj-stanok-pm-6m

Исходное сырьё желательно загружать в ёмкость подготовки макулатуры и заливать водой (не обязательный этап, возможно сухое сырье сразу же погружать в гиброразбиватель) https://solyariswell.com/catalog/17-ru/oborudovanie-dlya-proizvodstva/netkannye-materialy/89-avtomaticheskij-stanok-pnm-2

оборудование для производства из готового сырья – наиболее доступный и простой вариант; мини-завод по переработке макулатуры – включа

2023-08-19 Reply Admin

Кофе – самый популярный напиток в мире, без которого невозможно представить свой день https://lobadincoffee.com/page10439803.html Неудивительно, что в Москве с каждым годом становится все больше заведений, где основу меню составляет кофе https://lobadincoffee.com/roasters Многие из них находятся вблизи достопримечательностей и людных мест, другие в уютных двориках и на живописных набережных, но все они привлекают гостей чудным ароматом заваренного кофе, который способен моментально взбодрить https://lobadincoffee.com/shop3/tproduct/187539009-485041065961-gvatemala-koban

(Страстной бульвар, 12 с5) Весной команда открывает второе место на Садовнической набережной https://lobadincoffee.com/america Обещают такую же широкую кофейную карту, много завтраков и вид на реку, который особенно хорош в теплое время https://lobadincoffee.com/page10839652.html

Если хотите попробовать тартар с маринованным тунцом, соусом кимчи и кремовым сыром или сорт кофе, о котором ранее никогда не слышали, то Вам следует заглянуть в уютный зал кондитерской Coffeemania https://lobadincoffee.com/espropress

Часы работы: будни с 8:00 до 21:00, выходные с 10:00 до 21:00 https://lobadincoffee.com/cupping-sets/tproduct/246201263-710875255361-da-vinci-4-po-200-gr

2023-08-19

Comment held for moderation.

2023-08-20

Comment held for moderation.

2023-08-20

Comment held for moderation.

2023-08-20

Comment held for moderation.

Eric Sink on EricSink()

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