Timeline for Finding a bounding volume (line segments) from a kDop definition.
Current License: CC BY-SA 2.5
87 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 3, 2010 at 18:07 | comment | added | feal87 | ok, i'll register right away. Yeah, i think the same. :D Let's rest for a while, I have the brain on fire ATM. Too much math is bad for health. :D | |
| Feb 3, 2010 at 17:59 | comment | added | fedja | Should we try to shave some more time off or it is already what you were looking for? Since 0.04*200=8 < 16, I think the job is done and we deserve some rest now but we can try the other algorithm later just for the fun of it if we both have time. One more thing: try www.artofproblemsolving.com computer science and informatics subforum next time. I go there too. MO is, striclty speaking, not for such discussions (though I liked working with you :lol:) | |
| Feb 3, 2010 at 17:52 | comment | added | feal87 | Yes works fine now on both DOP14 and DOP26. DOP14 : 0.01340 min 0.01850 max DOP26 : 0.03420 min 0.03930 max after i've corrected the loop as you said. | |
| Feb 3, 2010 at 17:45 | comment | added | feal87 | Yes they are symmetric and the axis will be always those. I'll try right away :D | |
| Feb 3, 2010 at 17:44 | comment | added | fedja | Because the table for DOP14 should be completely different. In particular, the rule for degenerate pairs is no longer the same. The general rule (for 0-1 vectors) is that the pair is degenerate if A+B is a multiple of some vector C in your set. It reduces to the simple rule I told you for the full set, but not for its proper subsets. As long as everything is symmetric and 0-1, you can just call A,B degenerate if Crossproduct(A+B,C)=0 for some C in the set (C can be taken A or B here). If you correct this step, it should work for DOP14 too. | |
| Feb 3, 2010 at 17:40 | comment | added | feal87 | (the old slow code takes 0.11 ms with DOP14 so tecnically i can leave that alone, but it would be nice to understand why its failing) | |
| Feb 3, 2010 at 17:38 | comment | added | feal87 | Basically the code miss all the connecting lines. img710.imageshack.us/img710/7236/wrongdop14.png | |
| Feb 3, 2010 at 17:28 | comment | added | feal87 | (obviously the code is adapted to generate a 14x14 table) | |
| Feb 3, 2010 at 17:28 | comment | added | feal87 | Mhn...I'm investigating on why the same code does not work properly with DOP14 (the first 7 planes). | |
| Feb 3, 2010 at 17:13 | comment | added | fedja | I'll try to see if I can make the main loop better. One improvement is obvious: the inner loop in j should go up to i-1, not up to 25 (50% reduction in time). Stay tuned for more! | |
| Feb 3, 2010 at 17:06 | comment | added | feal87 | A lot of thanks fedja for all the patience to take me through all this ordeal. I doubt i would ever do anything without your help. :) Thanks!!! | |
| Feb 3, 2010 at 17:05 | comment | added | feal87 | First Execution (create table) : 19 ms ||| Other executions : going from 0.03640 to 0.05750 ms ||| img683.imageshack.us/img683/3030/worksxi.jpg <--example (it works on all 34 test object i have) ||| pastebin.com/m7341fe2a <--here's the code for any people who is having the same problem. :) | |
| Feb 3, 2010 at 16:59 | comment | added | fedja | 1,2,3 - yes. Now, since the lines are wrong, check a few things. a) If you compute X as in 3, and take its scalar products with p[i],p[j],and p[i]$\times$p[j] you should get M[i],M[j], and 0. If you are not getting that, iProjector and jProjector are incorrect. If you are getting that, those are fine. b) If you take Y=X+SingleValue*Table[i][j].Normal, this point Y should lie on the plane Y$\cdot$p[S.k]=M[S.k]. If it's wrong, you have incorrect SingleValue. Confirm if these two tests work. | |
| Feb 3, 2010 at 16:56 | comment | added | feal87 | No reason to answer, i found out the problem. It was because i used Min instead of -Min. Now it works FLAWLESS!!! Fantastic. :D Now i'll go do 2-3 benchmark and screenshots for you :D | |
| Feb 3, 2010 at 16:47 | comment | added | feal87 | Ok, now it generate lines (totally wrong, but hey its a progress). As a sidenote, actually this algorithm take 0.04 ms so we are on the right track. :D Another series of questions. 1) "Single Value = (M[S.K] - M[i] * S.iScal - M[j] * S.jScal) / S.nScal;" for generating the Min/Max values is correct? 2) iScal = DotProduct(_table[i][j].iProjector, Planes[k].Normal); <--its right? 3) X = M[i] * Table[i][j].iProjector + M[j] * Table[i][j].jProjector; is right to calculate the X in the final part? | |
| Feb 3, 2010 at 16:39 | comment | added | feal87 | Ah that was the reason it was never Min < Max. XD | |
| Feb 3, 2010 at 16:28 | history | edited | fedja | CC BY-SA 2.5 |
fixed typos
|
| Feb 3, 2010 at 16:23 | comment | added | fedja | 2) Damn, one more stupid typo! The expression is the same but you should take the maximum over the entries with nscal<0 fot tmin and the minimum over the entries with nscal>0 for tmax. Those are two disjoint sets! | |
| Feb 3, 2010 at 16:19 | comment | added | fedja | iProjector: Almost. I had a misprint there. It should really be Planes[j].Normal. Terribly sorry for that. Then you get what I called v. It has the right direction but wrong length. You should now divide v by its scalar product with p[i]. For jProjector just reverse the roles of i and j. M: Yes, but I want all inequalities for the object vertices x to be of the form x$\cdot$p[i] < M[i], so the inequality x$\cdot$p[i] > Min[i] becomes x$\cdot$(-p[i]) < -Min[i] and should be associated with the vector -p[i], which has some other index. As I said, I do not want any casework in the main loop. | |
| Feb 3, 2010 at 16:05 | comment | added | feal87 | Another question. as M you intend the array with the Min/Max values right? (I have them in the order 0...(K/2-1) <--Min (K/2)...K-1 <--Max) | |
| Feb 3, 2010 at 16:02 | comment | added | feal87 | I don't understand the last part in fact. I have two question : 1) How to calculate iProjector (i've done CrossProduct(Table[i][j].Normal, Planes[i].Normal), but i'm not sure its the right way); 2) The tMin and tMax part, to me it seems that NEVER the condition will be true as you said to calculate tMin as the Maximum of an expression and tMax as the minimum of the SAME expression... Probably i'm getting something wrong... | |
| Feb 3, 2010 at 14:39 | comment | added | fedja | Yes, if you count only i<j. | |
| Feb 3, 2010 at 14:32 | comment | added | feal87 | I was calculating wrongly the determinant. Now i get 576 good indices. These values are the same as for you? If yes i'll start with the final part of the code. | |
| Feb 3, 2010 at 14:14 | comment | added | fedja | Ok, determinants. Take i,j. Take k If det=det(p[i],p[j],p[k])=0, skip k. Now take all m different from i,j,k (check that you indeed never take m equal to one of them and that you didn't put (0,0,0) somewhere in the array p; those were MY error yesterday). Test that at least one determinant det(p[m],p[j],p[k]),det(p[i],p[m],p[k]),det(p[i],p[j],p[m]) has an opposite sign to the sign of det. If it is true, go to the next m. If it is false, break the m loop and skip k. An instance of good vector for the pair (1,1,1),(1,1,0) is (0,1,-1). See where you lose it in your code. | |
| Feb 3, 2010 at 14:05 | comment | added | feal87 | (I was sure it was a problem with my code, our difference in experience with mathematics is really evident i think ATM. :P) | |
| Feb 3, 2010 at 14:01 | comment | added | fedja | Just to convince you that they are 144. Each 3 ones element (8 of those), say, (1,1,1), makes a nondegenerate pair with each 2 one element except (-1,-1,0),(0,-1,-1), and (0,-1,-1) (9 of those) and each 1 one element with +1 in it (3 of those), giving you 8*12 pairs (which is already greater than your 94). Each 2 one element (1,1,0) makes a non-degenerate pair with 4 2 one elements (1,0,1),(1,0,-1),(0,1,1), (0,1,-1) so we have 12*4/2=12*2 such pairs and 2 1 one elements (1,0,0) and (0,1,0), so 12*2 more pairs. Now 12*(8+2+2)=144 | |
| Feb 3, 2010 at 13:57 | comment | added | feal87 | ok, I was making a stupid error. (i was processing from (i/j=0 to planeslength/2) instead of from (i=0 to planeslength) and (j=i+1 to planeslength)) Now i have 144 nondegenerate pair. Let's go the the determinants. :D | |
| Feb 3, 2010 at 13:43 | comment | added | fedja | Yes, with these Maxs and Mins it should work fine. | |
| Feb 3, 2010 at 13:40 | comment | added | fedja | I implemented this table yesterday on my PC and it worked fine. Let's start with non-degenerate pairs. You should consider all 26 directions. You should find $C=A+B$ take the absolute value of every non-zero element of C and check that some two of them are not equal to claim that the pair is nondegenerate. So, if (1,1,1),(1,-1,0) is nondegenerate (2 in the first position, 1 in the third for the sum) but (1,1,1),(-1,-1,0) is not. Find all 144, and then we'll talk about the det check. | |
| Feb 3, 2010 at 13:32 | comment | added | feal87 | My maxes (and mins) are calculated doing ||||| Value = Vertex.X + Vertex.Y - Vertex.Z; ||||| (that is an example for the direction (1,1,-1)) and picking up the max/min value. (going through ALL the vertex in the object) | |
| Feb 3, 2010 at 13:30 | comment | added | fedja | Yes, if the test fails for just one m, k is skipped. | |
| Feb 3, 2010 at 13:23 | comment | added | fedja | 1) Yes 2) Does not matter, the determinant of the transpose is the same as the determinant of the matrix 3) Of course, that's the whole point. Now one thing: everything will work perfectly is your Maxes are true maxima of the scalar products with directions over the object (or some dense set of points in it). Otherwise we cannot guarantee that the vertex formed by three directions will be cut off by the plane corresponding to the direction in their cone and the whole table thing will fail dramatically. | |
| Feb 3, 2010 at 13:16 | comment | added | feal87 | If one these check on m fails, k is skipped. | |
| Feb 3, 2010 at 13:16 | comment | added | feal87 | My code find only 94 nondegenerate pairs... (following what i said just above) The check for the determinant fails too. (it doesn't find any good indices) Here's what i'm doing : for each i,j pair, check all the k different from i,j and if the determinant of (p[i],p[j],p[k]) is different from 0, do for EVERY m different from i,j,k the check for the determinant of (p[i],p[j],p[m]) (p[i],p[m],p[k]) (p[m],p[j],p[k]). If at least one of these 3 is of sign inverse to the first determinant. (if the first det is positive, one of the three det must be negative). | |
| Feb 3, 2010 at 12:01 | history | edited | fedja | CC BY-SA 2.5 |
small improvement
|
| Feb 3, 2010 at 11:33 | comment | added | feal87 | I just started to implement your optimized N^3 implementation and I have some doubts in the table. (almost completely implemented). Correct me if these assertion are false. 1) The pair (A,B) is DEGENERATE if EVERY absolute value of non-zero element (x,y,z) of the sum A+B are equal. 2) the matrix 3x3 that we need to check the determinants is [A.x,A.y,A.z][B.x,B.y,B.z][C.x,C.y,C.z]. (i mean each vector is a row and not a column) 3) I can safely cache this table to reuse in different executions of the algorithm (changing only the Distance values of the planes (Min/Max basically)) | |
| Feb 3, 2010 at 5:15 | comment | added | fedja | OK, I edited my post to describe the optimal N^3 realization. It should be very easy to implement. I want to know the running time of this version. | |
| Feb 3, 2010 at 5:13 | history | edited | fedja | CC BY-SA 2.5 |
added the full N^3 algorithm description
|
| Feb 3, 2010 at 0:00 | comment | added | feal87 | I tried to make a line from the minimum point found to the odd point and every line seems to be working now (at least in the sample). Well i don't know why :D | |
| Feb 2, 2010 at 23:40 | comment | added | feal87 | Now I have a question for the N^3 case for when you will be back tomorrow. (probably will be useful for the N^2 too) When i process each line against the planes to obtain the points of the segments, sometimes i get ODD number of points. In this situation what should i do? Actually I discard the extra point (in the mesh drawed 1-2 lines disappear for these frames (not a big problem for the result i want, but i'm interested on why it happens, and how to resolve)). | |
| Feb 2, 2010 at 23:22 | comment | added | feal87 | Ok, i found out the problem in the N^3 code i was reproducing again. At least now I have a working implementation, now let's work tomorrow to get the other working too. :D The N^3 code was not working cause I was searching not only the lower/upper bound of each segment, but every point possible. (I wrongly thought that the maximum number i can find of them is two, but that's wrong :P) In most case are only two, but in some case more causing the problem. :D Anyway I can give a confirmation, Yes, even in the N^3 implementation i get some segment long 0.00003, so your guess was correct. | |
| Feb 2, 2010 at 23:01 | comment | added | fedja | N^3: Intersect each pair of planes, get a line, find the interval on the line cut by all other half-spaces (if the line is parameterized as $x+mt$ where x is some point on the line and m is the direction, each half-space gives either an upper or a lower bound for t); if it is non-empty (the least upper bound for t is greater than the largest lower bound), find the endpoints and keep it as an edge to draw. Otherwise go to the next pair. | |
| Feb 2, 2010 at 22:31 | comment | added | feal87 | (in the first post there is a ditto. the axis of the AABB are (1,0,0)(0,1,0)(0,0,1). I typed them wrongly) | |
| Feb 2, 2010 at 22:30 | comment | added | feal87 | Ok, i'll wait for your post tomorrow. :) I'm actually thrilled, its fun to work on these things even if they aren't actually my field of work (i'm a 3D developer, but not really a mathematician :D) | |
| Feb 2, 2010 at 22:27 | comment | added | feal87 | 1) Pick all the planes (Min and Max) for a total of 26 planes 2) Intersect each plane with each other (NPlane * (NPlane-1) / 2) lines generated. 3) For each line, intersect with each planes and get a series of points. 4) For each point, check if it is part of the kDOP at this point I don't remember how I managed to get all the point linked together. | |
| Feb 2, 2010 at 22:26 | comment | added | feal87 | (without a visual aid, they don't know if the vertex they chooe to assign a kDot to make a good fit or not) I have to ask you a big favor in the meantime we find a solution for this problem. Can you tell me the steps to the N^3 solution so I can rebuild it for the modelist to work on while I can play on optimizing and learning a more advanced algorithm? (the one we are working to :D) (cause i deleted the code and I don't really remember all the steps i picked up to make it work in the past days xD) As far i remember | |
| Feb 2, 2010 at 22:25 | comment | added | feal87 | (Generally we use planes in the +1/0/-1 range because its faster to calculate in real time the Min/Max values (absolutely no need for multiplication, just addition and substraction)) This is important as in a scene can appear 300-400 kDot objects that needs updated (and then regenerated the kDOT) for 60 times a second. The draw of the edges of the kDot (what are we trying to do) are needed for modelist that needs to create complex hierarchy structure of kDot to deliminate more complex mesh/objects and give realistic feel to the collision. | |
| Feb 2, 2010 at 22:25 | comment | added | fedja | That also explains the duplication of vertices effect. It was, actually, a real thing, and a good one at that. You may really have such close pairs of vertices and should keep them. Perhaps, it is not so nice for drawing, but you can easily identify such pairs in the very end and discard them before producing the picture. I'll post the way I would do everything tomorrow (and try to run a few experiments myself). | |
| Feb 2, 2010 at 22:25 | comment | added | feal87 | Can change to whatever i want. The directions/axes/planes are the means for me to deliminate a complex mesh/object inside a kDOP for more precise collision detection while maintaining the speed of intersection check of a Axis Aligned Bounded Box (from which the kDot pick the features (and is almost the same speed to intesect)). In fact a kDOT can be an Axis aligned Bounded Box if the planes used are only the first 3. (1,0,0)(0,1,0)(1,1,0) Every plane would work actually even (142,102,841) (Numbers picked randomly). | |
| Feb 2, 2010 at 22:10 | comment | added | fedja | Ah, I see. (1,0,0),(0,1,0),and (1,1,0) are linearly dependent and so are many other triples, which screws everything up rather thoroughly in some cases. I'll try to think of some good and quick fix. No need to redo everything yet. By the way, are those directions sacred or you can change them to whatever you want? | |
| Feb 2, 2010 at 21:12 | comment | added | feal87 | I think i'll try to redo the algorithm implementation from scratch tomorrow. :P | |
| Feb 2, 2010 at 20:46 | comment | added | feal87 | Anyway as i further tested in the simulation. If i disable the draw of the edges when the number is odd (before draw i check), in the rest of the times the edges are drawn perfectly. So its probably some vertex that's falling somewhere causing the whole lines to slip (as the renderer pick the vertex in order, if one is missing, all goes crazy) | |
| Feb 2, 2010 at 20:39 | comment | added | feal87 | wait those are non normalized, if normalized probably nobody degenerate. :P | |
| Feb 2, 2010 at 20:38 | comment | added | feal87 | the one i posted above are the axis used (1,0,0)(0,1,0)(0,0,1) //AABB (Axis Aligned Bounding Box) (1,1,1)(1,-1,1)(1,1,-1)(1,-1,-1) // Corners (1,1,0)(1,0,1),(0,1,1),(1,-1,0),(1,0,-1),(0,1,-1) // Edges obviously the other 13 with inverse sign (26 normal in total) | |
| Feb 2, 2010 at 20:30 | comment | added | fedja | You mean, those are your real directions? Can you tell me all 13 then? I need to look at them to suggest a good and quick fix. If you have degeneracies like that, the algorithm as I described it is destined to have some issues. | |
| Feb 2, 2010 at 19:05 | comment | added | feal87 | Ok, good work. See you in an hour. Anyway tested with (1,0,1)(1,1,1)(1,0,0)(1,1,0) (four possible direction) maked them into [1,0,1,1],[1,1,1,1],[1,0,0,1],[1,1,0,1], the determinant is 0 and the matrix is singular (degenerate). | |
| Feb 2, 2010 at 18:57 | comment | added | fedja | With the first one: for example take (1,0,0),(1,1,0),(1,0,1) and make the 3 by 3 determinant. It is non-zero, so you are good Second one: take (1,0,1),(1,1,1),(1,0,0),(0,1,1) now make them into (1,0,1;1),(1,1,1;1),(1,0,0;1),(0,1,1;1) Take the 4 by 4 determinant. If it is non-zero, you are good. I'm going to teach my class now. Will be back in an hour. | |
| Feb 2, 2010 at 18:52 | comment | added | feal87 | because for example let's take the two direction (1,1,1) and (1,0,0) and make the matrix as you said (1,1,1)(1,0,1)(1,0,1). The determinant is 0. :P | |
| Feb 2, 2010 at 18:50 | comment | added | feal87 | Yes, they are linearly indipendent. Mhn...i'm a little confused, i'll make an example so you can confirm this is the thing you want from me. (let's consider the 2 directions (0,1,0)(1,0,0) [0,1,1] [1,0,1] [0,0,1] and find the determinant to know if is degenerate (singular) or not, that is -1 in this case. (If this is what you want then no, sometimes degenerate, sometimes not) | |
| Feb 2, 2010 at 18:34 | comment | added | fedja | Also "non-degenerate", not "degenerate" | |
| Feb 2, 2010 at 18:26 | comment | added | fedja | Sorry, I meant "every three of your directions are linearly independent" | |
| Feb 2, 2010 at 18:26 | comment | added | fedja | First of all, I need to know whether your directions are linearly independent (except trivial dependences between A and -A). Secondly, I need to know if, when you take any 4 directions without A,-A pair in them, treat them as rows, add 1 to the end of each row, and form a 4 by 4 matrix with this rows, it is always degenerate. If one of the answers is no, we have a problem (fixable, but irritating). | |
| Feb 2, 2010 at 17:49 | comment | added | feal87 | plane and then is out of the kDOP) I don't know why, changing this value depending on the rotation of the mesh the routine fail. >.< (Well, i'm not an expert mathematician so probably i'm doing some crazy error :D) | |
| Feb 2, 2010 at 17:48 | comment | added | feal87 | Mhn...i tried changing the number to discard a line/point and this mesh does not goes wrongly anymore. (Other instead still are a little wrong) I mean when i intersect plane with plane and plane with line, i test if the 2 planes are parallel by using the cross product and discard if the sum of XYZ is under a number (0.0001) actually. Same with planes vs Line, if there isn't a possible intersection (the dot product between normal of the plane and vector of the line is between -0.0001 and 0.0001) and same when testing each final point against the planes. (test if the point is behind the...... | |
| Feb 2, 2010 at 17:40 | comment | added | feal87 | mhn...basically it goes wrong depending on the rotation angle and the mesh. I'm investigating further. :P | |
| Feb 2, 2010 at 17:36 | comment | added | feal87 | Probably the problem is elsewhere and not in this routine. I'll investigate further and report here. All the vertex are saturated correctly if the mesh is not in continue rotation. If the mesh is in rotation it generate odd number of vertex. (but not always, like 1 time over 10 :P) I'll go take a look at the vertex blending/transformation routines. Something is terribly wrong. :P | |
| Feb 2, 2010 at 15:41 | comment | added | fedja | Educated guess: you just forget to saturate the other endpoint of a newly found edge or mark it fully saturated when it isn't. Each vertex has 3 positions to saturate and I feel like you are just missing some of them. Check that you are doing each vertex completely and do not move to the next one until it is fully saturated, i.e., until all 3 positions are filled with indices of other vertices in the list. | |
| Feb 2, 2010 at 15:31 | comment | added | fedja | I'm not sure what to make of those pictures (some of them are a bit weird and some of them are just too complicated). The number of vertices cannot be odd. Each vertex is formally a triple of planes and there is no way to saturate each vertex with an odd number of them. Run the algorithm, get the lists and do two things: a) check that all vertices satisfy the equations of their planes. b) check that each vertex is fully saturated (instead of pure Boolean marks, track 3 indices of adjacent vertices). b) should fail if the number of vertices is odd, and you'll be able to see what's wrong. | |
| Feb 2, 2010 at 15:06 | comment | added | feal87 | Do you think that the result is ok? I actually see some strange line that goes inside the mesh. I have to try to disable Z buffering when drawing these lines to see... | |
| Feb 2, 2010 at 15:05 | comment | added | feal87 | Now that i'm testing extensively the algorithm sometimes i get a number of vertices not even...(basically you can't make the last line). Probably i'm doing something wrong... img96.imageshack.us/img96/4426/skinningdemo.jpg img94.imageshack.us/img94/8758/spaceship2.jpg img687.imageshack.us/img687/1092/spaceship1.jpg These are two example of edges generated with my algorithm. The first is a skinned (vertex blend) hand animated in real time with multiple kDOP to divide its surface. The others are a spaceship static with only a SINGLE kDOP in different angulation | |
| Feb 2, 2010 at 14:01 | comment | added | fedja | The dangerous objects are degenerated ones. Try an interval object in random direction and see what the result is. If it works reasonably, everything is fine. If not, you should look into the precision issue. | |
| Feb 2, 2010 at 13:32 | comment | added | feal87 | I'll work to make the code to build this table when i'll be back home. P.S. (Regarding the precision problem, actually the edges are drawed correctly (and enclose the mesh perfectly) for each test object i have (10-15 types) so the vertex "should" be calculated correctly) | |
| Feb 2, 2010 at 13:09 | comment | added | fedja | No, you do not exclude pairs. You exclude triples. So you exclude (1,0,0) with respect to the pair (0,1,0),(0,0,1) if you have (1,1,1) somewhere. The table should be indexed by pairs of directions and for each pair you should have the list of non-excluded directions. I'm also a bit concerned about your remark on low precision in vertex computation. It shouldn't be this way. When you find a new vertex, check the plane equations for it and see if they hold with essentially machine precision. | |
| Feb 2, 2010 at 13:01 | comment | added | feal87 | Mhn...taking account of the first rule (easily doable without a PC) Taking ABC as base exclude each plane that has his own normal vector as A(-A)B I identified at a glance : Exclude (0,0,1) (0,0,-1) in respect of (0,1,0) (0,-1,0) Exclude (1,-1,1) (-1,1,-1) in respect of (1,1,1) (-1,-1,-1) Exclude (1,-1,0) (-1,1,0) in respect of (1,1,0) (-1,-1, 0) Am i right? Or am i doing strange random things? :D P.S. (I'm using the unnormalized vectors in this example, in the app I use them normalized obviously) | |
| Feb 2, 2010 at 12:22 | comment | added | fedja | The rule is the following: (I denote the unit direction vectors by capital letters) A(-A)B is useless, ABC is useless if there is D such that D=aA+bB+cC with positive a,b,c. Now, be careful. When you are doing the first randomization step, move all planes out by the same small random amount. Otherwise you may run into trouble when your object has sharp cones and you had 4-plane intersections in the beginning (if you do independent perturbations, the useless triple may easily become useful and everything will collapse). This also requires that your directions be generic. Can you tell them? | |
| Feb 2, 2010 at 12:12 | comment | added | feal87 | Yeah, resolved in that way. Thanks. Now i'm finding which plane to ignore it althogether to speed it up even more. (The AABB planes are useless right? I mean, even in a CUBE (no cut by the various corner/edges planes) situation the corner and edges planes are enough to find the extreme point. Or am i getting this wrong?) | |
| Feb 2, 2010 at 12:06 | comment | added | fedja | Don't keep vertices as coordinates, keep them as triples of planes (integers), so you do not have any rounding errors when comparing the vertices. | |
| Feb 2, 2010 at 8:35 | comment | added | feal87 | {X:-38.77622 Y:-0.9569161 Z:-5.700686} {X:-38.77622 Y:-0.9569183 Z:-5.700684} (Actually doubling the number of vertices, I'll work to find out why. :D} | |
| Feb 2, 2010 at 8:33 | comment | added | feal87 | It works fine and is very fast!!! Still some problem (i get one vertices extra different only for some 0.00002 like on each elaboration. I have to find a way to discard those useless data :P) | |
| Feb 1, 2010 at 21:03 | comment | added | feal87 | Thanks a lot for all the suggestions fedja. Tomorrow morning i'll work on it and try to get it working fast :) | |
| Feb 1, 2010 at 20:50 | comment | added | fedja | But, of course, you can do the precomputation to determine for each pair of directions which other directions have any chance to make a vertex with them, which may shave some extra time off in both algorithms. Just do not do it manually: the machine can easily determine if a given vector has positive coefficients with respect to 3 other vectors and construct the table for you. | |
| Feb 1, 2010 at 20:42 | comment | added | fedja | The whole point is that despite the directions of the planes stay fixed, the vertices are not always formed by the intersections of the same triples (in a striking contrast with $\mathbb R^2$ where you just go counterclockwise) though you are right that there are some triples that have no chance to form vertex (the ones that form a cone inside which you have another direction), so you do not know the combinatorial type in advance. | |
| Feb 1, 2010 at 20:24 | vote | accept | feal87 | ||
| Feb 1, 2010 at 20:24 | comment | added | feal87 | (yes its 26. 13 min and 13 max with the normals inverted) | |
| Feb 1, 2010 at 20:22 | comment | added | TonyK | N is 26, I think, not 52. So fedja's method should be fast enough. | |
| Feb 1, 2010 at 20:20 | comment | added | feal87 | Thanks a lot for the detailed and precise explanation!!! It should be easy to implement having such a good guide. (I'll do it anyway even if I can find another solution just as an educational project) A note, is it possible to do as I said in the last comment of the question and simply precalculate each vertex manually preknowing which planes to intersect (as i don't change EVER the planes) simply by doing a 3 planes intersect and linking the points one to one (it is really tedious to write every combination, but should VERY fast) What do you think? | |
| Feb 1, 2010 at 20:14 | history | answered | fedja | CC BY-SA 2.5 |
