#1
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
#2
That would be a useful one !
RE: Idea for an LDCad script
#3
(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
#4
(2022-01-03, 0:18)Owen Dive Wrote: 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.

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
#5
(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?

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 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
#6
(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
#7
(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
#8
(2022-01-07, 14:43)Stefan Frenz Wrote: 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.

I'm wondering if it would be fast enough to do real time calculations though.
RE: Idea for an LDCad script
#9
(2022-01-08, 20:57)Roland Melkert Wrote: 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.

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
#10
(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:

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

RE: Idea for an LDCad script
#11
(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
#12
(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:

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
#13
(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
#14
(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
#15
(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
#16
(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):

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
#17
(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
#18
(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
#19
(2022-01-10, 9:26)Roland Melkert Wrote: Render data inside LDCad is at the part level (flattened), and uses both triangles and quads.
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.

That will fit and I will try.   Thanks again!
RE: Idea for an LDCad script
#20
(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:

Checking in LDCad, the collision report seems to be correct:

Maybe this also can be fixed with shrinking...
RE: Idea for an LDCad script
#21
(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):

RE: Idea for an LDCad script
#22
(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
#23
(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
#24
(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
#25
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} function Part:new(orig, level)   o={}   setmetatable(o, self)   self.__index=self   self.orig=orig or {}   self.level=level or 0   self.pMinX=math.huge   self.pMinY=math.huge   self.pMinZ=math.huge   self.pMaxX=-math.huge   self.pMaxY=-math.huge   self.pMaxZ=-math.huge   return o end function Part:add(tri)   table.insert(self.triangles, tri)   if tri.pMinX<self.pMinX then     self.pMinX=tri.pMinX   end   if tri.pMinY<self.pMinY then     self.pMinY=tri.pMinY   end   if tri.pMinZ<self.pMinZ then     self.pMinZ=tri.pMinZ   end   if tri.pMaxX>self.pMaxX then     self.pMaxX=tri.pMaxX   end   if tri.pMaxY>self.pMaxY then     self.pMaxY=tri.pMaxY   end   if tri.pMaxZ>self.pMaxZ then     self.pMaxZ=tri.pMaxZ   end end function Part:info()   return self.orig:getFileName()..' ('..self.orig:getDescription()..'): '..self.pMinX..' '..self.pMinY..' '..self.pMinZ..' to '..self.pMaxX..' '..self.pMaxY..' '..self.pMaxZ end Triangle={p1={}, p2={}, p3={}, pMinX=math.huge,pMinY=math.huge,pMinZ=math.huge, pMaxX=-math.huge,pMaxY=-math.huge,pMaxZ=-math.huge} function Triangle:new(p1, p2, p3)   o={}   setmetatable(o, self)   self.__index=self   self.p1=p1   self.p2=p2   self.p3=p3   self.pMinX=math.huge   self.pMinY=math.huge   self.pMinZ=math.huge   self.pMaxX=-math.huge   self.pMaxY=-math.huge   self.pMaxZ=-math.huge   self:check(p1)   self:check(p2)   self:check(p3) --  print('vec: ', p1,' / ',p2,' / ',p3) --  print('min/max: ', self.pMinX,' ',self.pMinY,' ',self.pMinZ, ' to ', self.pMaxX,' ',self.pMaxY,' ',self.pMaxZ)   return o end function Triangle:check(p)   local pX,pY,pZ=p:get()   if pX<self.pMinX then     self.pMinX=pX   end   if pY<self.pMinY then     self.pMinY=pY   end   if pZ<self.pMinZ then     self.pMinZ=pZ   end   if pX>self.pMaxX then     self.pMaxX=pX   end   if pY>self.pMaxY then     self.pMaxY=pY   end   if pZ>self.pMaxZ then     self.pMaxZ=pZ   end end function colldet_walk(sf, ppos, level, parts)   local partCnt=sf:getRefCount()   for i=1,partCnt do     local part=sf:getRef(i):getSubfile() --    print('-- part ', part:getDescription())     local pos=sf:getRef(i):getPosOri()     pos:mulBA(ppos) --    print('-- pos ', pos)     local data=part:getRenderData()     if data:isLinked() then       local mpart=Part:new(part, level)       table.insert(parts, mpart)       for g=1,data:getGroupCount() do         local grp=data:getGroup(g)         if grp:isTriangle() then           local cnt=grp:getCount() --          print('triangle strip contains ', cnt, ' entries')           for j=1,cnt do             local a,b,c=grp:getPositionIndices(j) --            print('triPosRel: ', data:getPosition(a), '; ', data:getPosition(b), '; ', data:getPosition(c)) --            print('triPosAbs: ', data:getPosition(a):getTransformed(pos), '; ', data:getPosition(b):getTransformed(pos), '; ', data:getPosition(c):getTransformed(pos))             mpart:add(Triangle:new(data:getPosition(a):getTransformed(pos), data:getPosition(b):getTransformed(pos), data:getPosition(c):getTransformed(pos)))           end         elseif grp:isQuad() then           local cnt=grp:getCount() --          print('quad strip contains ', cnt, ' entries')           for j=1,cnt do             local a,b,c,d=grp:getPositionIndices(j) --            print('quadPosRel: ', data:getPosition(a), '; ', data:getPosition(b), '; ', data:getPosition(c), '; ', data:getPosition(d)) --            print('quadPosAbs: ', data:getPosition(a):getTransformed(pos), '; ', data:getPosition(b):getTransformed(pos), '; ', data:getPosition(c):getTransformed(pos), '; ', data:getPosition(d):getTransformed(pos))             mpart:add(Triangle:new(data:getPosition(a):getTransformed(pos), data:getPosition(b):getTransformed(pos), data:getPosition(c):getTransformed(pos)))             mpart:add(Triangle:new(data:getPosition(c):getTransformed(pos), data:getPosition(d):getTransformed(pos), data:getPosition(a):getTransformed(pos)))           end         end       end     else       colldet_walk(part, pos, level+1, parts)     end   end end function colldet_collect()   local sf=ldc.subfile()   local pos=ldc.matrix()   --identity is set by default: pos:setIdentity()   local parts={}   colldet_walk(sf, pos, 0, parts)   print('found ',#parts,' parts:')   for i=1,#parts do     print(i, ': ', parts[i]:info())   end end function colldet_floor()   local sf=ldc.subfile()   local pos=ldc.matrix()   pos:setIdentity()   local parts={}   colldet_walk(sf, pos, 0, parts)   if #parts==0 then     print('no part found')   else     local max=parts[1].pMaxY     for i=2,#parts do       if max<parts[i].pMaxY then         max=parts[i].pMaxY       end     end     local partCnt=sf:getRefCount()     for i=1,partCnt do       local ref=sf:getRef(i)       local x,y,z=ref:getPos():get()       ref:setPos(ldc.vector(x,y-max,z))     end   end end function colldet_check()   print('not implemented yet!')   local sf=ldc.subfile()   local pos=ldc.matrix()   pos:setIdentity()   local parts={}   colldet_walk(sf, pos, 0, parts)   for i=2,#parts do     for j=1,i-1 do       local p1=parts[i]       local p2=parts[j]       print('todo: checking ', i, ' (', p1:info(), ') against ', j, ' (', p2:info(), ')')       -- todo     end   end end function register()   local macro=ldc.macro('CD: 1 collect parts')   macro:setHint('Collision Detection: collect parts')   macro:setEvent('run', 'colldet_collect')   local macro=ldc.macro('CD: 2 move to floor')   macro:setHint('Collision Detection: move bottom point down/up to 0')   macro:setEvent('run', 'colldet_floor')   local macro=ldc.macro('CD: 3 check collision')   macro:setHint('Collision Detection: check part collision')   macro:setEvent('run', 'colldet_check') end register()```
RE: Idea for an LDCad script
#26
Thank you so much for your help, Roland. I created a new thread for discussing the collision detection macro.
« Next Oldest | Next Newest »

Forum Jump:

Users browsing this thread: 1 Guest(s)