Oh I see.. Well, I do also assume that your calculations are correct, but I would like to take a shot for the D = 3 case.
The equation is this, but I do not seem to get what k represents.
EDIT:
How do we call in English the d - i and k -i that lie into a parenthesis? You can see it in the link. I know how to calculate it.
The combination one can answer. Yes, that's true.
Assume we have the combination of n and k. In Greek, we can say n per k, can we say that in English too?
Last edited by std10093; 08-08-2013 at 01:30 PM.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
fi describes the number of i-dimensional features in the convex polytope, so k-1 is the number of dimensions in the feature we are interested in; for halfspaces, k-1 = D-1.Originally Posted by std10093
is the binomial coefficient n, k. Wikipedia says it is often read as "n choose k" in English.Code:⎛n⎞ ⎝k⎠
Maybe I am tired from the code. In regards with post #41, in order to find the intersecting halfspaces with the current box of the node, isn't enough to do something like this:
?Code:if ( halfspace.x >= node.box.minBox.x && halfspace.y >= node.box.minBox.y && halfspace.z >= node.box.minBox.z && halfspace.x < node.box.maxBox.x && halfspace.y < node.box.maxBox.y && halfspace.z < node.box.maxBox.z )
[IRRELEVANT]
PS: Remember the architecture assignment I had to do and we figured out a way to replace division by multiplication and shifting, unroll the loop, etc.?
Well, it seemed that I had no completely get our task and I was graded badly²! However, I learnt a lot from all this experience and the knowledge is far more precious than a grade, in my case (still my GPA is good).
For the history:
- I thought that every range would get 20 numbers, but that was not a must after all, with the input tests the PhD'es had, having 22 in some and 19 in others. As a result, when the code sensed that a range did not have 20 elements, it was programmed to assume that we are out of range.
// My confusion was justified, because of a tip the professor gave inside the class.- When the data was out of range, the code was able to find this situation, but did not break the loop, which was a secondary requirement.
// I knew that, but it was not something important I guess, the first one was the real penalty.
Thanks again for the great things you thought me at that project and sorry for messing up with the grade.
[/IRRELEVANT]
Last edited by std10093; 08-10-2013 at 06:41 PM.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
No, it is not enough.
The vector (halfspace.x, halfspace.y, halfspace.z) is only normal (perpendicular) to the halfspace plane; it does not by itself define the halfspace.
Consider a cube not at origin; say, at (2,3,4)-(3,4,5) instead. So, it'll have vertices at
but halfspacesCode:2 3 4 3 3 4 2 4 4 3 4 4 2 3 5 3 3 4 2 4 5 3 4 5
The initial bounding box is obviously x=[2,3], y=[3,4], z=[4,5], and none of the halfspace normal vectors are in it. But the same logic applies as to the previous cube we've discussed in this thread: all six halfspaces intersect the initial bounding box, and each of the eight subcubes will have three intersecting halfspaces.Code:-1 0 0 -2 0 -1 0 -3 0 0 -1 -4 0 0 +1 5 0 +1 0 4 +1 0 0 3
So, what you do have to do, is check whether each halfspace is inside or outside the vertex of the current box, i.e. at the eight corners of the current box:
(Of course, since floating point numbers are not exact, I personally use q<-ϵ, -ϵ<=q<=ϵ, and q>ϵ, instead.)Code:q = halfspace.x * x + halfspace.y * y + halfspace.z * z - halfspace.d q < 0: (x, y, z) is inside the halfspace q = 0: (x, y, z) is at the plane of the halfspace q > 0: (x, y, z) is outside the halfspace
The WinMIPS64 assembly one, this thread? The task basically being to compute a five-bin histogram of 100 inputs, each input being between 0 and 4999 inclusive (thus each bin being 1000 integers "wide").
(I think the most optimized -- quite insane -- version I sent you ran in 720 cycles per 100 inputs, using 12 bits per bin (five bins) in a 64-bit register; or quoting myself in a private message, "for any multiple of 8 Length, it runs in 18+6.75*Length cycles".)
So, your computation of the histogram was correct, but the conclusions your code made based on the histogram were incorrect?
Hm. If so, I would have graded differently. (I place much more emphasis on getting the logic and computation right, than having the exact expected result.)
I do recall we discussed input range checking at some point. To me, as the lecturer/grader, detecting invalid range would have been even more important than fast execution.
In any case, I do sincirely hope none of my advice caused you to veer off from the original assignment. Maybe, if we hadn't played with the different techniques and methods on how to implement a histogram calculation efficiently in 64-bit MIPS assembly, you might have concentrated more on the actual assignment, and not on the other stuff we discussed..
About the halfspaces, I was also thinking that this could not be enough, because of the minimum distance to origin of the halfspace! However, it is 6 in the morning here in Greece and I was playing football and going out all the days, so I am tired I guess, but that's how things go. Thanks for pushing me a bit.
[EDIT]
What are x, y and z?Code:q = halfspace.x * x + halfspace.y * y + halfspace.z * z - halfspace.d q < 0: (x, y, z) is inside the halfspace q = 0: (x, y, z) is at the plane of the halfspace q > 0: (x, y, z) is outside the halfspace
We have used the information from the halfspace, what about the information of the bounding box (which has min and max coords)?
[/EDIT]
Well, the code I sent was of 820 cycles, but still the team that took 10/10 had 1100 cycles....
The edition of 720 was too insane! haha -but fun to read.
>So, your computation of the histogram was correct, but the conclusions your code made based on the histogram were incorrect?
Not really. The professor had something in course and I thought he meant that we should take as granted that every range would get exactly 20 elements.
>I place much more emphasis on getting the logic and computation right, than having the exact expected result.
Damn right! However, after discussing with others, we concluded that they really just run the code and checked the results. They did not even have a look at our documentations!
>I do recall we discussed input range checking at some point. To me, as the lecturer/grader, detecting invalid range would have been even more important than fast execution.
Me too, but I can accept this penalty, the other one was really strict.
>In any case, I do sincirely hope none of my advice caused you to veer off from the original assignment. Maybe, if we hadn't played with the different techniques and methods on how to implement a histogram calculation efficiently in 64-bit MIPS assembly, you might have concentrated more on the actual assignment, and not on the other stuff we discussed..
My friend, I want to do more than just getting a good grade. I want to learn. I want to be a scientist in our field, just like you! If the trade-off we had to dealt with was what you thought me and my grade, I was for sure going for the knowledge you gifted me.
However, I am pretty sure, that it was my fault that I lost this requirements.
Last edited by std10093; 08-10-2013 at 09:01 PM.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
The coordinates you are going to test, so one corner of the bounding box in this case.
Remember, if you have halfspace (halfspace.x, halfspace.y, halfspace.z, halfspace.d), and point (point.x, point.y, point.z), thenIf you check the corners of the current bounding box, and at least one corner is inside, and one corner outside, then the plane of the halfspace must intersect the current bounding box, right?Code:halfspace.x * point.x + halfspace.y * point.y + halfspace.z * point.z < halfspace.d: point is inside halfspace halfspace.x * point.x + halfspace.y * point.y + halfspace.z * point.z = halfspace.d: point is on the plane of the halfspace halfspace.x * point.x + halfspace.y * point.y + halfspace.z * point.z > halfspace.d: point is outside the halfspace
If none of the corners of the current bounding box is outside the halfspace, then the entire box is inside that halfspace, and that halfspace is not relevant to testing whether any point in the current box is inside the convex polytope.
If all the corners of the current bounding box are outside, for any halfspace, then the entire box is outside the convex polytope.
(This is because it is enough for a point to be outside any halfspace for it to be outside the convex polytope. Conversely, a point must be inside (or on the plane of) all halfspaces for it to be inside the convex polytope.)
Pity that thread is closed, I would have liked to post that code. (I do think I have the file still.) The technique itself is pretty much insane -- constructing a five-bin histogram in a single 64-bit register, then using several of those registers in parallel to unroll a loop. It's one of the those things that are possible, but unless it is write-only code (and the speed is absolutely required), it is not sane (maintainable, readable) -- even a sane description of how it works is probably longer than the code itself.
That's a pity -- but really, that's how this world works.
Usually, it is better to answer the question that the asker believes they asked, instead of answering either the question they literally asked, or the question they should have asked. (The second gives you a reputation as a difficult smart-alec, and many people cannot handle "a student" doing the third to them. Especially professors who have already fallen off the tip of their field, and need crutches to maintain the illusion in their head. Beware of anyone who thinks that they've learned enough when they get their first full professorship; they're the worst.)
In other words, you need to learn to read what the asker attempted to ask. I treat it as a puzzle; I don't have the social skills to determine it directly.
I did no such thing!
I don't think knowledge can be given, or really even shared. A friend, tutor, teacher, mentor can help you discover it, but that's it.
(The best ones can help you discover stuff they don't know themselves; I've had the privilege to meet a few of those. I'm definitely not one of those, as I lack the social talent they have.)
I merely described some of the techniques possible, and gave you a bit of feedback on your implementation. In particular, I didn't show you my version until you had submitted yours (you didn't want me to, either). If I were the lecturer on that course, I'd hope the TAs were there to give you the assistance I did here. Answering theoretical questions and assessing particular details will help the students apply the course content in their assignments; heck, that's why TAs are needed!
(Of course, many professors use TAs to grade assignments, and don't care a bit whether the TAs help the students at all. Most students are too timid to complain about bad TAs to their lecturer, even if a TA spews utter incorrect bull instead of explaining the correct solution. The damage one bad apple can do in such a situation is surprisingly widespread, so stuff like that should be caught and avoided, even if handled quietly.)
In your case, I suspect the TAs did most of the grading, too.
Actually, I've had something very similar happen to me on a C course, well over a decade ago. (It was a basic sort command assignment; I discovered that I could significantly cut the wall clock time used if I read the entries into a tree, instead of using an array or a list and sorting when all data has been read.) I talked to the lecturer, specifically not to adjust the grade, but to ask if he understood why I made the choices I had.
I was much happier after the short chat, when I was sure the lecturer had understood me (and my work) correctly.
Perhaps you could do the same? It's best to mention first that you don't want them to adjust your grade, you just want to discuss your solution. (At least here, it's very common for students to try and whine a higher grade, even cry a little bit. Some are even proud of how good they are at it. Best make sure you're not one of those, in my opinion.)
Yes I remember when the point is inside a halfspace, because we had discussed it when we were up determining where a point lies inside a polytope.
Now, the question is, if a halfspace intersects a bounding box? I had in mind, that for a bounding box, it is enough to have a 3D point describing its min boundary and one for its max.
And I can't figure it out.
>I did no such thing!
>I don't think knowledge can be given, or really even shared. A friend, tutor, teacher, mentor can help you discover it, but that's it.
I phrase it badly, but that's what I meant. You show me the way in finding the path that leads to this knowledge.
>In your case, I suspect the TAs did most of the grading, too.
True, but every professor has 200-300 students at my university, so I pretty much understand this.
> Most students are too timid to complain about bad TAs to their lecturer
To be fair, there are really many students that complain about TAs, because they do not actually do their homework. This is really bad and TAs are gotten accused unfairly. I saw this, while I had my scholarship in Switzerland and the university was a private one.
I did talk to him, but he was not positive.
Last edited by std10093; 08-11-2013 at 09:54 AM.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
Yes.
You still have to test each of the eight corners of the box,
to know whether the halfspace plane intersects the box or not.Code:min.x min.y min.z max.x min.y min.z min.x max.y min.z max.x max.y min.z min.x min.y max.z max.x min.y max.z min.x max.y max.z max.x max.y max.z
If you were only to test the two points (first and last above), you'd only know if the halfspace intersected the diagonal of the box. Yet, there are many possible planes that do intersect the box but do not intersect the diagonal.
Pity.
Well, you did learn a very valuable lesson, though: always make sure you understand how your task will be evaluated, and direct your efforts accordingly.
It's a good rule to go by even if you do the evaluation yourself.
Oh you meant the corners of the bounding box! No idea why I could not get this earlier.
So, I have my function for testing if a halfspace intersects a bounding box like this:
Is it correct?Code:** * Increase counters if needed. * @param q - compare it with epsilon * @param in_at - counter for points inside, * or at the plane of the halfspace * @param out - counter for points outside * the halfspace */ void Guadtree::incCounters(const double& q, size_t& in_at, size_t& out) { /* * q < 0: (x, y, z) is inside the halfspace. * q = 0: (x, y, z) is at the plane of the halfspace. * q > 0: (x, y, z) is outside the halfspace. * Use epsilon, because of double variables. */ if(q < -epsilon || (-epsilon <= q && q <= epsilon)) in_at++; else out++; } /** * Test if a halfspace intersects a bounding box. * @param halfspace - the halfspace to be tested * @param minBox - the min of the bounding box * @param maxBox - the max of the bounding box * @return - answer of test */ bool Guadtree::halfspaceIntersectsBox(const Halfspace& halfspace, const Point3d*& minBox, const Point3d*& maxBox) { size_t in_at = 0; // Counter for corners inside, or at the plane, of the halfspace size_t out = 0; // Counter for corners outside of the halfspace const Point3d halfspaceCoords = halfspace.getCoords(); const double halfspaceD = halfspace.getD(); /* Check all the corners of the bounding box, eight in number. * The corners are: * min.x min.y min.z * max.x min.y min.z * min.x max.y min.z * max.x max.y min.z * min.x min.y max.z * max.x min.y max.z * min.x max.y max.z * max.x max.y max.z */ double q = halfspaceCoords * *minBox - halfspaceD; incCounters(q, in_at, out); q = halfspaceCoords.x() * maxBox->x() + halfspaceCoords.y() * minBox->y() + halfspaceCoords.z() * minBox->z() - halfspaceD; incCounters(q, in_at, out); /* If at least one corner is inside(or at the plane), and one corner outside, * then the plane of the halfspace intersects the bounding box. */ if(in_at >= 1 && out == 1) return true; q = halfspaceCoords.x() * minBox->x() + halfspaceCoords.y() * maxBox->y() + halfspaceCoords.z() * minBox->z() - halfspaceD; incCounters(q, in_at, out); if(in_at >= 1 && out == 1) return true; q = halfspaceCoords.x() * maxBox->x() + halfspaceCoords.y() * maxBox->y() + halfspaceCoords.z() * minBox->z() - halfspaceD; incCounters(q, in_at, out); if(in_at >= 1 && out == 1) return true; q = halfspaceCoords.x() * minBox->x() + halfspaceCoords.y() * minBox->y() + halfspaceCoords.z() * maxBox->z() - halfspaceD; incCounters(q, in_at, out); if(in_at >= 1 && out == 1) return true; q = halfspaceCoords.x() * maxBox->x() + halfspaceCoords.y() * minBox->y() + halfspaceCoords.z() * maxBox->z() - halfspaceD; incCounters(q, in_at, out); if(in_at >= 1 && out == 1) return true; q = halfspaceCoords.x() * minBox->x() + halfspaceCoords.y() * maxBox->y() + halfspaceCoords.z() * maxBox->z() - halfspaceD; incCounters(q, in_at, out); if(in_at >= 1 && out == 1) return true; q = halfspaceCoords * *maxBox - halfspaceD; incCounters(q, in_at, out); if(in_at >= 1 && out == 1) return true; }
What is your opinion about this code? It is C++.
>Well, you did learn a very valuable lesson, though: always make sure you understand how your task will be evaluated, and direct your efforts accordingly.
>It's a good rule to go by even if you do the evaluation yourself.
We learn and get better constantly!
//At 7.30 I am leaving for vacation, for a week and I decided not to take a computer/laptop with me. I have to work at my aunt's restaurant too.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
I am also very concerned on how to print the octree! What do you suggest? What should it be my approach?
// I am a travelling in two hours, so I must go to bed (of course, I will eat before going to bed). See you in one week!
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
A couple of notes:
- It's Quad, not Guad.
- To handle the cases efficiently, you probably should differentiate all three cases: inside, on the plane, and outside.
You see, if one or more of the corners of the bounding box are on the plane, but none are inside or outside, then that halfspace is irrelevant for the current box.- You check the results too early.
You need to check all corners first, and then determine whether the halfspace intersects the bounding box. You don't know the result before checking all eight corners.
As a comparison, here is the relevant bit of how I'd do it:
Note the differences to your code. The loop is over each halfspace.Code:halfspace_t *const h; /* Array of halfspaces */ int nh; /* Number of halfspaces in the array */ int i = 0; /* Loop over known halfspaces: */ while (i < nh) { const double d[8] = { min.x*h[i].x + min.y*h[i].y + min.z*h[i].z - h[i].d, max.x*h[i].x + min.y*h[i].y + min.z*h[i].z - h[i].d, min.x*h[i].x + max.y*h[i].y + min.z*h[i].z - h[i].d, max.x*h[i].x + max.y*h[i].y + min.z*h[i].z - h[i].d, min.x*h[i].x + min.y*h[i].y + max.z*h[i].z - h[i].d, max.x*h[i].x + min.y*h[i].y + max.z*h[i].z - h[i].d, min.x*h[i].x + max.y*h[i].y + max.z*h[i].z - h[i].d, max.x*h[i].x + max.y*h[i].y + max.z*h[i].z - h[i].d }; const int corners_inside = (d[0] < -eps) + (d[1] < -eps) + (d[2] < -eps) + (d[3] < -eps) + (d[4] < -eps) + (d[5] < -eps) + (d[6] < -eps) + (d[7] < -eps); const int corners_outside = (d[0] > eps) + (d[1] > eps) + (d[2] > eps) + (d[3] > eps) + (d[4] > eps) + (d[5] > eps) + (d[6] > eps) + (d[7] > eps); if (corners_outside >= 8) { /* * This sub-box is completely outside the polytope. * * I use NULL pointer to declare entire sub-box "outside", * i.e. NODE_OUTSIDE_POLYTOPE. */ return NULL; } if (corners_outside == 0 || corners_inside == 0) { /* * Either all corners are inside the halfspace, or * the plane of halfspace intersects a corner only. * * Since no part of the current sub-box is outside the polytope, * halfspace i is irrelevant to the current sub-box. * So, "remove" the halfspace (by moving it to the end of array). */ swap_halfspaces(&h[i], &h[--nh]); continue; } /* Keep this halfspace. */ i++; } /* If there are no halfspaces left, * this entire box is inside the polytope. */ if (nh < 1) { /* * Return a special "fully inside the polytope" node. */ return NODE_INSIDE_POLYTOPE; }
The corner tests exclude the plane of the halfspace itself. (Even if we needed it, we could just count it based on there being 8 corners, and every corner falling into one of the categories; i.e. corners_at_plane = 8 - corners_inside - corners_outside.)
The determination whether a halfspace intersects the current bounding box can only be made after all eight corners have been tested. (However, if a halfspace shows that the current bounding box is completely outside the polytope, i.e. all eight corners outside, we know that the current bounding box is completely outside the polytope.)
A halfspace is only relevant to the polytope inclusion test, if it intersects the current bounding box. (If the halfspace plane intersects corners only, it is irrelevant, because it does not affect the test for any point inside the current bounding box.)
Only those halfspaces where one or more corners are inside, and one or more corners are outside, are needed for the inclusion test. My code keeps those at the start of the h array, and moves the others to the end of the list.
(We've already discussed how this allows you to use a single array of halfspaces with a recursive function.)
Just remember that in C, (true) evaluates to 1, and it is quite okay to count the number of true values using summation like I do above. In C++, converting bool to int always yields 0 or 1 for false and true, respectively, so the same works in C++, too.
If you want to make it explicit (for other programmers), you can write it as ((condition) ? 1 : 0) instead. Given sufficient optimization flags, a C compiler should generate the exact same code anyway.. but some do not.
Have a nice vacation!
Tried to bypass some calculations, but I searched and finally I agree with you, so let's calculate data for all the corners.
Basically, I want a function that tells me if a halfspace intersects with the current sub-box or not, thus, I did actually use pretty much your code, well, except from the corners_outside >= 8, that I wrote it as corners_outside == 8, since we have exactly 8 corners, so the > check is redundant.
And here it is, hope this is ok.
Now I am going to write the print function and actually see, if my code works, because it executes successfully, but I am worried because, I had very few segmentation faults and relevant errors. Maybe I have some some logical errors!Code:/** * Test if a halfspace intersects a bounding box. * @param halfspace - the halfspace to be tested * @param minBox - the min of the bounding box * @param maxBox - the max of the bounding box * @return - result of test */ bool Quadtree::halfspaceIntersectsBox(const Halfspace& halfspace, const Point3d*& minBox, const Point3d*& maxBox) { const Point3d h = halfspace.getCoords(); // Coordinates of halfspace const double hD = halfspace.getD(); // Distance of halfspace /* Check all the corners of the bounding box, eight in number. * The corners are: * min.x min.y min.z * max.x min.y min.z * min.x max.y min.z * max.x max.y min.z * min.x min.y max.z * max.x min.y max.z * min.x max.y max.z * max.x max.y max.z */ const double d[8] = { h * *minBox - hD, h.x() * maxBox->x() + h.y() * minBox->y() + h.z() * minBox->z() - hD, h.x() * minBox->x() + h.y() * maxBox->y() + h.z() * minBox->z() - hD, h.x() * maxBox->x() + h.y() * maxBox->y() + h.z() * minBox->z() - hD, h.x() * minBox->x() + h.y() * minBox->y() + h.z() * maxBox->z() - hD, h.x() * maxBox->x() + h.y() * minBox->y() + h.z() * maxBox->z() - hD, h.x() * minBox->x() + h.y() * maxBox->y() + h.z() * maxBox->z() - hD, h * *maxBox - hD }; const int corners_inside = (d[0] < -epsilon) + (d[1] < -epsilon) + (d[2] < -epsilon) + (d[3] < -epsilon) + (d[4] < -epsilon) + (d[5] < -epsilon) + (d[6] < -epsilon) + (d[7] < -epsilon); const int corners_outside = (d[0] > epsilon) + (d[1] > epsilon) + (d[2] > epsilon) + (d[3] > epsilon) + (d[4] > epsilon) + (d[5] > epsilon) + (d[6] > epsilon) + (d[7] > epsilon); /* * A halfspace is only relevant to the polytope inclusion test, * if it intersects the current bounding box. (If the halfspace * plane intersects corners only, it is irrelevant, because it * does not affect the test for any point inside the current * bounding box). Only those halfspaces where one or more corners * are inside, and one or more corners are outside, are needed * for the inclusion test. */ if(corners_inside == 0 || corners_outside == 0 || corners_outside == 8) return false; return true; }
EDIT:
Here is the print function and now, let's start testing and... debugging of course!
Thanks for the wish for the vacations.Code:/** * Print the tree. */ void Quadtree::print() { print(root); } /** * Print the current node. * @param node - the node to be printed. */ void Quadtree::print(node*& node) { if(node) { print(node->child[0]); std::cout << node->split << std::endl; print(node->child[1]); std::cout << node->split << std::endl; print(node->child[2]); std::cout << node->split << std::endl; print(node->child[3]); std::cout << node->split << std::endl; print(node->child[4]); std::cout << node->split << std::endl; print(node->child[5]); std::cout << node->split << std::endl; print(node->child[6]); std::cout << node->split << std::endl; print(node->child[7]); std::cout << node->split << std::endl; } }
Last edited by std10093; 08-19-2013 at 07:41 PM.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
So, lets see:
- corners_inside == 0
None of the corners are inside the box.
Most of the box is therefore outside the halfspace; one to four corners, up to four edges, and possibly one face of the box may be on the plane of the halfspace, though.- corners_outside == 0
All corners are either inside or on the plane of the halfspace.
There are no points inside this box that are outside this halfspace.- corners_outside == 8
All eight corners are outside the halfspace, so the entire box is outside the halfspace.
Therefore, this box is completely outside the polytope.
The latter two are clearly okay, I'm only worried about the first one. It really depends on what do you use this test for?
(corners_inside == 0) can be true if one or more corners are on the plane of the halfspace. This means that even if corners_inside==0, the halfspace may be coplanar with one side of the box. Points exactly on the halfspace plane are usually considered inside.
Now that I think about it, I think the line 44 in the code I listed in post #56 is incorrect; it should only test for (corners_outside==0).
Consider the case where the halfspace is coplanar to a side of the box. Those four corners are on the plane (neither inside nor outside), and the other four are outside. So, corners_inside==0 and corners_outside==4.
I think that kind of a halfspace should be considered to intersect the box.
The same logic applies even if the halfspace plane intersects only two points (coplanar to an edge of the box) or one point (intersects at that corner only).
I'm not absolutely certain yet, though. It needs testing, something I think I neglected to do for the code I showed in #56. In particular, I think that the points that happen to sit exactly on the plane should be considered "inside" -- even if every other point within the box is considered outside. Hmm.. needs more thinking.
Yes, I do agree that this box is relevant, since it has its 4 corners on the plane. I am going to think of it more however.
>It really depends on what do you use this test for?
When we are building the tree, we want to split a node, only if the number of the intersecting halfspaces with the box of this node is larger than t (which is the desired query time, which we get from input).
So, for every halfspace of the polytope, when we are in the root, we check if the current halfspace intersects the current box and the answer to this question comes from the Quadtree::halfspaceIntersectsBox().
By the way, for the print of the tree, I modified the function into this:
However, I am not sure yet if this is correct. I am going to test it after my match tonight.Code:/** * Print the tree. */ void Quadtree::print() { std::cout << "Octree" << std::endl; print(root); } /** * Print the current node. * @param node - the node to be printed. */ void Quadtree::print(node*& node) { if(node) { print(node->child[0]); std::cout << node->split << std::endl; print(node->child[1]); print(node->child[2]); print(node->child[3]); print(node->child[4]); print(node->child[5]); print(node->child[6]); print(node->child[7]); } }
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
Yep. These corner cases (no pun intended) are tricky; they need hard thought to get right.
It's not like it's the first time I've gotten the corner cases wrong myself, even in this thread
For more or less the same purpose, then.
The reason I asked is that I do my test when deciding which halfspaces are relevant to this box, and which are not. The decision whether to split the node or not is only done later, after I've checked all the halfspaces. I only need the number of relevant halfspaces for that decision.
The difference is very subtle. If a halfspace intersects the box so that all points in the box are still inside the box, the halfspace is not interesting. If a halfspace intersects the box so that the rest of the box is outside the halfspace, the halfspace is interesting. So, it's not a plain intersects-or-not test.
Naming and commenting your functions in a way that makes it clear to the programmer what it does, is very important. I should know, because I just made that error in post #56 myself!
Aaaand since I cannot edit post #56 anymore, here's the fixed version of that code snippet:
If anyone else is wondering, my habit of using ">= 8" instead of "== 8" is perhaps silly, but it brings me comfort. I've seen too many bugs caused by using "==" when ">=" is the correct choice (for some rare or exceptional input), that going well and truly the other way gives me the warm fuzzy feeling.Code:halfspace_t *const h; /* Array of halfspaces */ int nh; /* Number of halfspaces in the array */ int i = 0; /* Loop over known halfspaces: */ while (i < nh) { const double d[8] = { min.x*h[i].x + min.y*h[i].y + min.z*h[i].z - h[i].d, max.x*h[i].x + min.y*h[i].y + min.z*h[i].z - h[i].d, min.x*h[i].x + max.y*h[i].y + min.z*h[i].z - h[i].d, max.x*h[i].x + max.y*h[i].y + min.z*h[i].z - h[i].d, min.x*h[i].x + min.y*h[i].y + max.z*h[i].z - h[i].d, max.x*h[i].x + min.y*h[i].y + max.z*h[i].z - h[i].d, min.x*h[i].x + max.y*h[i].y + max.z*h[i].z - h[i].d, max.x*h[i].x + max.y*h[i].y + max.z*h[i].z - h[i].d }; const int corners_inside = (d[0] < -eps) + (d[1] < -eps) + (d[2] < -eps) + (d[3] < -eps) + (d[4] < -eps) + (d[5] < -eps) + (d[6] < -eps) + (d[7] < -eps); const int corners_outside = (d[0] > eps) + (d[1] > eps) + (d[2] > eps) + (d[3] > eps) + (d[4] > eps) + (d[5] > eps) + (d[6] > eps) + (d[7] > eps); if (corners_outside >= 8) { /* * This sub-box is completely outside the polytope. * * I use NULL pointer to declare entire sub-box "outside", * i.e. NODE_OUTSIDE_POLYTOPE. */ return NULL; } if (corners_outside == 0) { /* * None of the corners are outside the halfspace, so * all points inside the box are inside this halfspace. * Therefore, this halfspace is irrelevant to this box. * So, "remove" the halfspace (by moving it to the end of array). */ swap_halfspaces(&h[i], &h[--nh]); continue; } /* Keep this halfspace. */ i++; } /* If there are no halfspaces left, * this entire box is inside the polytope. */ if (nh < 1) { /* * Return a special "fully inside the polytope" node. */ return NODE_INSIDE_POLYTOPE; }
In other words, it's just a mannerism I have. If you have a sharp eye, you'll notice many others in my code snippets.. but they all have a story behind them, and I like 'em.
