[LDCad] Idea for an LDCad script - Printable Version +- LDraw.org Discussion Forums (https://forums.ldraw.org) +-- Forum: LDraw Programs (https://forums.ldraw.org/forum-7.html) +--- Forum: LDraw Editors and Viewers (https://forums.ldraw.org/forum-11.html) +--- Thread: [LDCad] Idea for an LDCad script (/thread-25817.html) |
Idea for an LDCad script - N. W. Perry - 2021-12-31 A simple idea, perhaps (and for all I know someone's already done this), but what about a "place on ground" script that would calculate the lowest point of a model and place that at Y=0? Better still, calculate the two lowest points—such as two wheels that are not quite in the same plane—and rotate the whole model so that they both rest at Y=0? RE: Idea for an LDCad script - Philippe Hurbain - 2021-12-31 That would be a useful one ! RE: Idea for an LDCad script - Owen Dive - 2022-01-03 (2021-12-31, 21:13)N. W. Perry Wrote: Better still, calculate the two lowest points—such as two wheels that are not quite in the same plane—and rotate the whole model so that they both rest at Y=0? You could even do that for three points! But depending on the geometry of the model it's possible that after such rotation, none of those three points will be the lowest, which might not be what you want. RE: Idea for an LDCad script - N. W. Perry - 2022-01-03 (2022-01-03, 0:18)Owen Dive Wrote: You could even do that for three points! True. I haven't yet found a case where I'd need three points to put a model on the ground. But, I'd love to be able to do that when, say, dumping apples into a crate, or pebbles into a flowerbed, when building a modular building or bonsai tree! RE: Idea for an LDCad script - Roland Melkert - 2022-01-06 (2021-12-31, 21:13)N. W. Perry Wrote: A simple idea, perhaps (and for all I know someone's already done this), but what about a "place on ground" script that would calculate the lowest point of a model and place that at Y=0? You would need access to vertex data for this, or manually process the type 3 lines in the current api. RE: Idea for an LDCad script - N. W. Perry - 2022-01-06 (2022-01-06, 18:40)Roland Melkert Wrote: You would need access to vertex data for this, or manually process the type 3 lines in the current api. Which I bet would also be the first step for any potential collision detection tool, no? I wonder if the same math could be used for a collision-aware rotation tool—now that would be powerful! RE: Idea for an LDCad script - Stefan Frenz - 2022-01-07 (2022-01-06, 19:57)N. W. Perry Wrote: Which I bet would also be the first step for any potential collision detection tool, no? I wonder if the same math could be used for a collision-aware rotation tool—now that would be powerful! I have implemented a collision detection in LDInspector which is working "in most cases". I already thought of integrating this into LDCad - but never started. RE: Idea for an LDCad script - Roland Melkert - 2022-01-08 (2022-01-07, 14:43)Stefan Frenz Wrote: I have implemented a collision detection in LDInspector which is working "in most cases". I will try to add access to the vertex data (position, normal and color). I'm wondering if it would be fast enough to do real time calculations though. RE: Idea for an LDCad script - Stefan Frenz - 2022-01-08 (2022-01-08, 20:57)Roland Melkert Wrote: I will try to add access to the vertex data (position, normal and color). Thank you, Roland. Please don't spend too much time in this for me - in fact, at the moment the checks are very sensitive to tolerances, i.e. trade-of between false-positives and false-negatives. Some cases are just not detected correctly even though clearly colliding, which is a known problem of the triangle-comparison approach I have chosen. The currently implemented checks help me in many cases, but they are far from deserving blind trust. I would love to implement this as LDCad extension, but I'm very uncertain about the result. If the basic idea of my current collision detection will sometimes make it into a LDCad script, it would need the triangle (not only vertex) information to check triangle intersection... I agree that it most probably will not be fast enough for real time use: at the moment, I check every triangle of a part against all triangles of all other parts, just after building some helping and very time saving bounding boxes. RE: Idea for an LDCad script - Stefan Frenz - 2022-01-09 (2022-01-08, 22:11)Stefan Frenz Wrote: at the moment the checks are very sensitive to tolerances, i.e. trade-of between false-positives and false-negatives Two examples of the LDInspector collision detection result: Everything ok with the 603 model: Screenshot_603.png (Size: 46.66 KB / Downloads: 135) For the 1972 model, each tire and its rim are reported to intersect (they don't), there is no special treatment of paths (they don't intersect with theirselves), but the intersection of the Technic Connector with the bottom Plate is mathematically correct (but not relevant in reality): Screenshot_1972.png (Size: 116.69 KB / Downloads: 138) RE: Idea for an LDCad script - Roland Melkert - 2022-01-09 (2022-01-09, 7:59)Stefan Frenz Wrote: Two examples of the LDInspector collision detection result: Very cool. Maybe 'fake seam shrinking' the parts before testing resolves some of those false positives? RE: Idea for an LDCad script - Stefan Frenz - 2022-01-09 (2022-01-09, 20:05)Roland Melkert Wrote: Maybe 'fake seam shrinking' the parts before testing resolves some of those false positives? Thank you for this hint! I was not aware of this thread and have to work through its background. I tried so many approaches to shrink parts because in LDInspector version 0.5 collisions of coplanar triangles are all filtered out. Example: Screenshot2.png (Size: 10.8 KB / Downloads: 127) If the parts are not perfectly aligned or moved by small steps, the current algorithm will detect the collision. But perfectly aligned in a static model (which should be some normal case in my understanding) they collide in reality, but they don't have (non-coplanar) triangle intersection, so the current implementation will not detect the collision. Shrinking would be a solution in some cases, but I could not find a general solution to the problem illustrated here: two non-colliding parts (green) do collide after shrinking (red, in this example both parts are shrinked by 5% at an unlucky part origin): Hmmmmm. Another thing on my ToDo-list. RE: Idea for an LDCad script - Roland Melkert - 2022-01-09 (2022-01-09, 21:36)Stefan Frenz Wrote: Hmmmmm. Another thing on my ToDo-list. You need to shrink them using their absolute center, as done in the povray snippet at the bottom of the thread you referenced. RE: Idea for an LDCad script - Roland Melkert - 2022-01-09 (2022-01-08, 22:11)Stefan Frenz Wrote: Thank you, Roland. Please don't spend too much time in this for me - in fact, at the moment the checks are very sensitive to tolerances, i.e. trade-of between false-positives and false-negatives. Some cases are just not detected correctly even though clearly colliding, which is a known problem of the triangle-comparison approach I have chosen. The currently implemented checks help me in many cases, but they are far from deserving blind trust. I would love to implement this as LDCad extension, but I'm very uncertain about the result. I have this working at the moment: The triangle is actually the first 3 positions of a quad I think as I need to add aa internal mapping for direct triangle/quad access (LDCad renders in groups by color/texture). Main question is this something that would be usable (seeing you''re the main end user at the moment ) RE: Idea for an LDCad script - N. W. Perry - 2022-01-10 (2022-01-09, 22:38)Roland Melkert Wrote: Main question is this something that would be usable (seeing you''re the main end user at the moment ) For myself, I'm not as interested in detecting unintended collisions as in detecting intended ones. Basically as another form of snapping, so that you can move or rotate one part towards another, and it will stop exactly where the two parts touch. This is why I thought of it like an extension of the "put on ground" shortcut, because that's essentially moving a part (or model) downwards until it "collides" with the y=0 plane. So for this idea of "collision snapping", or maybe better called "proximity snapping", you'd basically find the colliding surface of a nearby part and calculate from that a new "ground" plane. Then it would be the same mathematically as putting something on the ground—except that you might be moving the object on global axes while looking for the collision point on some non-normal plane. At least, I think it would. RE: Idea for an LDCad script - Stefan Frenz - 2022-01-10 (2022-01-10, 1:46)N. W. Perry Wrote: At least, I think it would. I could think of the collision detection as an indicator to end a directed move or directed rotation. This would allow something like "move/rotate in this direction until the first collision occurs, remember the colliding triangles and try to get (approximate? calculate?) the one-directional move/rotate value" as in the following examples: move green block to the right along the red line until it reaches the black block (becomes blue) or rotate the green block around the bottom left edge clockwise until it reaches the black block (becomes cyan). Doing one move and two rotations like this, I would guess a model could be set to ground (or aligned to any other part) automatically. The following would be much harder: move until there is no collision. Most of the time there will be at least a small overlap, so the target position will not be found (with my algorithm): Screenshot2.png (Size: 2.47 KB / Downloads: 120) Maybe the last one could be solvable by something that does volume intersection by trying to minimize the volume that intersects. As far as I understand LDraw, a volume model is not (directly) available as invisible boundaries are not included (like the bottom of a stud or the upper end of the two inner 3002 tubes). And so far my collision detection has only very little knowledge of volumes. RE: Idea for an LDCad script - Stefan Frenz - 2022-01-10 (2022-01-09, 22:38)Roland Melkert Wrote: I have this working at the moment:Thank you so much. If the vertices order is the same as it would be for rendering (i.e. after handling all part-subpart-whatever-invertions), this should allow a port of my collision detection. For the quads I use two triangles like "addTri(t1, t2, t3);addTri(t3, t4, t1);" (not inverted) or "addTri(t1, t3, t2);addTri(t3, t1, t4);" (inverted), so if your engine already splits the quad into two triangles, this would also match perfectly. RE: Idea for an LDCad script - Roland Melkert - 2022-01-10 (2022-01-10, 8:47)Stefan Frenz Wrote: Thank you so much. If the vertices order is the same as it would be for rendering (i.e. after handling all part-subpart-whatever-invertions), this should allow a port of my collision detection. For the quads I use two triangles like "addTri(t1, t2, t3);addTri(t3, t4, t1);" (not inverted) or "addTri(t1, t3, t2);addTri(t3, t1, t4);" (inverted), so if your engine already splits the quad into two triangles, this would also match perfectly. Render data inside LDCad is at the part level (flattened), and uses both triangles and quads. This stems from the age of the base code, the planned (but paused) 2.0 engine was going to be triangle exclusive so I thought it wouldn't hurt in the near future. OpenGL will convert it to triangles somewhere in the middle anyway though. All data has the same winding (think it's CW but have to check to be sure), unless the source .dat tree has no (complete) bfc information. RE: Idea for an LDCad script - Stefan Frenz - 2022-01-10 (2022-01-10, 9:26)Roland Melkert Wrote: Render data inside LDCad is at the part level (flattened), and uses both triangles and quads. That will fit and I will try. Thanks again! RE: Idea for an LDCad script - Stefan Frenz - 2022-01-10 (2022-01-09, 21:36)Stefan Frenz Wrote: in LDInspector version 0.5 collisions of coplanar triangles are all filtered out Motivated by this thread, I added some coplanar checks that seem to work in some cases. The given "1x1 with stud in 1x1 brick" example will be reported as collision, but now also the arm-in-body combination is reported as collision: Screenshot_603.png (Size: 48.22 KB / Downloads: 120) Checking in LDCad, the collision report seems to be correct: Screenshot_603zoom.png (Size: 70.96 KB / Downloads: 120) Maybe this also can be fixed with shrinking... RE: Idea for an LDCad script - Stefan Frenz - 2022-01-10 (2022-01-10, 10:23)Stefan Frenz Wrote: Maybe this also can be fixed with shrinking... Hm, shrinking at the appropriate absolute center seems to even make this undesired collision very robust (upper picture shows original valid lines, bottom picture is shrinked, last picture is zoomed with collision marker): Screenshot_Zoom.png (Size: 16.34 KB / Downloads: 121) RE: Idea for an LDCad script - Philippe Hurbain - 2022-01-10 (2022-01-10, 10:37)Stefan Frenz Wrote: Hm, shrinking at the appropriate absolute center seems to even make this undesired collision very robust (upper picture shows original valid lines, bottom picture is shrinked, last picture is zoomed with collision marker):Yeah, shrinking works only for convex shapes! RE: Idea for an LDCad script - N. W. Perry - 2022-01-10 (2022-01-10, 8:39)Stefan Frenz Wrote: I could think of the collision detection as an indicator to end a directed move or directed rotation. This would allow something like "move/rotate in this direction until the first collision occurs, remember the colliding triangles and try to get (approximate? calculate?) the one-directional move/rotate value" as in the following examples: move green block to the right along the red line until it reaches the black block (becomes blue) or rotate the green block around the bottom left edge clockwise until it reaches the black block (becomes cyan). Yes, that's exactly how I'd picture it working. And at least for the rotation example, the math already exists in this script. For the move example, if the movement vector is normal to the colliding plane then it's simple; otherwise I guess it's just some similar trigonometry. And if it's user-directed, it shouldn't consume any amount of processing power (unlike e.g. scanning a whole big model for collisions). The user could simply drag or rotate a part as normal until a collision occurs, and if the "proximity snapping" option is enabled, the program would automatically snap the movement back to the collision point. Best of all, if collisions can be detected between triangles and vertices, they can also be detected between snap objects, which could also allow for the long-desired "rotation snapping" feature! (Some tolerance would be required here, as not all real-world rotations give exact pythagorean ratios and rely somewhat on plasticity.) RE: Idea for an LDCad script - Stefan Frenz - 2022-01-19 (2022-01-10, 15:19)Philippe Hurbain Wrote: Yeah, shrinking works only for convex shapes! Yes, that's it. So I stopped the shrinking-approach and released LDInspector 0.6 with the current implementation of coplanar triangle checks (non-coplanar collisions are not changed and should be detected as before). RE: Idea for an LDCad script - Stefan Frenz - 2022-05-30 Thank you Roland for your help and LDCad 1.7-alpha-2. The discussed "place on ground" seems to work in a first version. Also porting the collision detection from Java to LUA will take more time... At the moment the script can: 1: collect all parts recursively and print their filename/description together with its bounding box 2: move all parts/submodel-references so that the lowest point has y==0 3: tbd: check collision of parts by comparing pairs of triangles of pairs of parts The current implementation collects all parts at first which would not be necessary for case 1 (just print instead of collect+print) and case 2 (just collect maxY instead of all bounding boxes of all parts), so this implementation is far from being optimal in regards to timing or memory usage. But it helps me porting my collision detection and maybe it is useful for others doing similar stuff. Code: Part={triangles={}, orig={}, level=0, pMinX=math.huge,pMinY=math.huge,pMinZ=math.huge, pMaxX=-math.huge,pMaxY=-math.huge,pMaxZ=-math.huge} RE: Idea for an LDCad script - Stefan Frenz - 2022-07-09 Thank you so much for your help, Roland. I created a new thread for discussing the collision detection macro. |