A scene I have been working on has a number of objects that lie randomly on an
uneven surface.  I created some SDL code, customized to the objects in question
to place them so that all points of the bottom surface of the object are on or
above the corresponding points of the surface.  After getting the code to work
fairly well, I went down a rabbit hole and decided to make it generic for all
objects and surfaces and add the code to my libraries.

The basic idea is to first generate a set of triangles that represent the bottom
(y axis pointing up) surface of the object.  With the current iteration, I
subdivide the bounding box for the object, (in the XZ plane only) a specified
number of times, (depending on how accurate you want the results to be and how
non-flat the bottom is), and then generate triangles using all subdivisions of
the bounding box.  I generate triangles from each combination of 3-corners of
the bounding boxes, and triangles from each combination of 2 corners and the
center of the box.

Since the shape does not have to be rectangular, when generating triangles, the
corners and center of the bounding box are used to scan the bottom of the object
to determine the "height" of the object at that point, or if it doesn't hit the
object at all.  If it doesn't hit the object, the corners are adjusted, (within
a given tolerance) until they do hit the object or you reach the center.
Triangles are only created if they are valid, (i.e. all 3 sides are non-zero and
result in a valid normal).

The triangles get generated in a breadth-first pattern based on the bounding box
levels.  This ensures the list of triangles starts with the largest ones that
span the whole object, and end with the smaller details.  I found that in my
initial tests, the placement algorithm converges more quickly and accurately
this way.

The placement algorithm then iterates over all of the triangles, testing to see
if any of their vertices would lie below the height of the surface.  If so, a
plane is calculated by lifting the vertex that is below the surface so it lies
at the height of the surface, along with the other two vertices of the triangle,
and a transform is created to orient the object on that plane.  As you continue
with the remaining vertices of the triangle and the remaining triangles, the
object-bottom points are transformed with this plane-transform first before
comparing to the surface.

Once you have gone through all of the triangles, if any transform has been
created, you go back and run through them again to ensure that later transforms
didn't push earlier triangles below the surface.  I added some logic to ensure
that the y-offset for new planes was monotonically increasing, which decreased
the flailing about immensely, and probably obviates running through the
triangles again.  However, this can leave the object hovering over the surface,
so I added one more check to ensure that at least one point touches the surface.

The result of all of this is a dictionary representation of a transform that I
have written, along with code for writing it to a file so you can generate all
of the transforms before you start rendering the scene.  Depending on the size
and complexity of your object and surface, and the level of detail, this can be
time-consuming, so I ensure I can run it once, generate the transforms, and then
just include them in the scene for rendering.

The code needs a lot more testing before I put documentation and official
examples into the GitHub repo with my libraries, but I thought I'd share the
idea in case there are comments, (like "someone has already done this...") :-)

-- Chris R

Post a reply to this message

Attachments:
Download 'libcollide_test.png' (142 KB)

Preview of image 'libcollide_test.png'

hi,

"Chris R" <car### [at] comcastnet> wrote:
> A scene I have been working on has a number of objects that lie randomly on an
> uneven surface.  I created some SDL code, customized to the objects in question
> to place them so that all points of the bottom surface of the object are on or
> above the corresponding points of the surface.  After getting the code to work
> fairly well, I went down a rabbit hole and decided to make it generic for all
> objects and surfaces and add the code to my libraries.
> ...
> The result of all of this is a dictionary representation of a transform that I
> have written, along with code for writing it to a file so you can generate all
> of the transforms before you start rendering the scene.  Depending on the size
> and complexity of your object and surface, and the level of detail, this can be
> time-consuming, so I ensure I can run it once, generate the transforms, and then
> just include them in the scene for rendering.
>
> The code needs a lot more testing before I put documentation and official
> examples into the GitHub repo with my libraries, but I thought I'd share the
> idea in case there are comments, (like "someone has already done this...") :-)

that does sound very nice and _useful_, I can think of two or three projects in
the past where I'd have liked having "supporting code" for planting (then
"vegetation") or placing objects.


> ... (in the XZ plane only) ...

I posted a usable quad-tree a few years back, fwiw.  no ref but will "dig it up"
if thought useful.


regards, jr.

Post a reply to this message

On 7/18/2025 7:07 AM, Chris R wrote:

> 
> The code needs a lot more testing before I put documentation and official
> examples into the GitHub repo with my libraries, but I thought I'd share the
> idea in case there are comments, (like "someone has already done this...") :-)
> 
> -- Chris R

I'm kind of reminded of my cloth simulation renders from way way back. 
It used a lot of trace commands and spring functions that could 
determine a bunch of normals, but trace would give that anyway.

The only other way I could think to do this is to sample a bunch of 
projections of the shape onto the surface until I was satisfied with the 
highest point of contact, then find the second highest point of contact 
and adjust the shape's orientation to touch those two points, then find
the next highest point and orient again.

I look forward to seeing what you've put together.

Josh

Post a reply to this message

Josh English <Jos### [at] joshuarenglishcom> wrote:

> The only other way I could think to do this

Way back, people were using Koppi's Bullet Physics to drop and place objects.
Presumably there is code one can look at to understand how object collision was
detected, and how objects were placed once finally coming to rest.

I'd probably bet money that Rune also came up with a robust algorithm for things
like this.

- BE

Post a reply to this message

On 21/07/2025 15:57, Bald Eagle wrote:
> Josh English <Jos### [at] joshuarenglishcom> wrote:
> 
>> The only other way I could think to do this
> 
> Way back, people were using Koppi's Bullet Physics to drop and place objects.
> Presumably there is code one can look at to understand how object collision was
> detected, and how objects were placed once finally coming to rest.
> 


Deep in my hard drive, in a 2001 archives, I found a Jonathan Rafael 
Ghiglia demo that stacks letters.


I'm attaching the archive to this message, in case it's of any use.




-- 
kurtz le pirate
compagnie de la banquise

Post a reply to this message

Attachments:
Download 'archive.zip' (11 KB)

hi,

kurtz le pirate <kur### [at] freefr> wrote:
> On 21/07/2025 15:57, Bald Eagle wrote:
> > Josh English <Jos### [at] joshuarenglishcom> wrote:
> >> The only other way I could think to do this
> > Way back, people were using Koppi's Bullet Physics to drop and place objects.
> > Presumably there is code one can look at to understand how object collision was
> > detected, and how objects were placed once finally coming to rest.
>
> Deep in my hard drive, in a 2001 archives, I found a Jonathan Rafael
> Ghiglia demo that stacks letters.
> I'm attaching the archive to this message, in case it's of any use.

interesting for sure, thanks.  (need to find time to explore beyond the demo)


regards, jr.

Post a reply to this message

Josh English <Jos### [at] joshuarenglishcom> wrote:
> On 7/18/2025 7:07 AM, Chris R wrote:
>
> >
> > The code needs a lot more testing before I put documentation and official
> > examples into the GitHub repo with my libraries, but I thought I'd share the
> > idea in case there are comments, (like "someone has already done this...") :-)
> >
> > -- Chris R
>
> I'm kind of reminded of my cloth simulation renders from way way back.
> It used a lot of trace commands and spring functions that could
> determine a bunch of normals, but trace would give that anyway.
>
> The only other way I could think to do this is to sample a bunch of
> projections of the shape onto the surface until I was satisfied with the
> highest point of contact, then find the second highest point of contact
> and adjust the shape's orientation to touch those two points, then find
> the next highest point and orient again.
>
> I look forward to seeing what you've put together.
>
> Josh

I'll be looking at all of the suggestions in this thread as improvements on the
algorithm.  What I am doing right now avoids non-stable looking placements when
you have small plateaus in the surface by examining point combinations at the
edge of the object first, rather than finding the 3 highest points.  This allows
the algorithm to tilt the object into a valley before making smaller adjustments
using closer point combinations.

BTW: the idea behind this was an aborted attempt at doing cloth simulation that
never worked really well.  I should see if I can find your code for doing it.
-- Chris R

Post a reply to this message

kurtz le pirate <kur### [at] freefr> wrote:
> On 21/07/2025 15:57, Bald Eagle wrote:
> > Josh English <Jos### [at] joshuarenglishcom> wrote:
> >
> >> The only other way I could think to do this
> >
> > Way back, people were using Koppi's Bullet Physics to drop and place objects.
> > Presumably there is code one can look at to understand how object collision was
> > detected, and how objects were placed once finally coming to rest.
> >
>
>
> Deep in my hard drive, in a 2001 archives, I found a Jonathan Rafael
> Ghiglia demo that stacks letters.
>
>
> I'm attaching the archive to this message, in case it's of any use.
>
>
>
>
> --
> kurtz le pirate
> compagnie de la banquise

Thanks for digging this up.  I am thinking I will try and implement this method
as an alternative using my own coding style, POV 3.8 features, and fitting into
my library code framework, and then compare the results with the triangle-based
version.  It appears there is some interesting code to deal with the problem of
local, small plateaus on the surface object to try out.

-- Chris R

Post a reply to this message

"Chris R" <car### [at] comcastnet> wrote:
> kurtz le pirate <kur### [at] freefr> wrote:
> > On 21/07/2025 15:57, Bald Eagle wrote:
> > > Josh English <Jos### [at] joshuarenglishcom> wrote:
> > >
> > >> The only other way I could think to do this
> > >
> > > Way back, people were using Koppi's Bullet Physics to drop and place objects.
> > > Presumably there is code one can look at to understand how object collision was
> > > detected, and how objects were placed once finally coming to rest.
> > >
> >
> >
> > Deep in my hard drive, in a 2001 archives, I found a Jonathan Rafael
> > Ghiglia demo that stacks letters.
> >
> >
> > I'm attaching the archive to this message, in case it's of any use.
> >
> >
> >
> >
> > --
> > kurtz le pirate
> > compagnie de la banquise
>
> Thanks for digging this up.  I am thinking I will try and implement this method
> as an alternative using my own coding style, POV 3.8 features, and fitting into
> my library code framework, and then compare the results with the triangle-based
> version.  It appears there is some interesting code to deal with the problem of
> local, small plateaus on the surface object to try out.
>
> -- Chris R
I wrote the code based on the letter stacking code in libcollide.inc and
debugged it, and added the grid generation piece to my libmesh.inc library.
Here are the results of repeatedly adding 20 discs to the same uneven surface
using the algorithm.  I think it does pretty well and it's actually quick enough
that you could run it during rendering, but I kept the option to write the
transforms to a file so you can pre-create them.

More testing to do...
-- Chris -R

Post a reply to this message

Attachments:
Download 'libcollide_test.png' (149 KB)

Preview of image 'libcollide_test.png'

"Chris R" <car### [at] comcastnet> wrote:

> I wrote the code based on the letter stacking code in libcollide.inc and
> debugged it, and added the grid generation piece to my libmesh.inc library.
> Here are the results of repeatedly adding 20 discs to the same uneven surface
> using the algorithm.  I think it does pretty well and it's actually quick enough
> that you could run it during rendering, but I kept the option to write the
> transforms to a file so you can pre-create them.

Damn, that is nice.

I'm hoping to see a pile of many more primitives on a much more uneven surface!

Nice work!

- BW

Post a reply to this message