Looking for a faster way to create a custom shape by compounding triangles

[Russell Kramer]

Hello, 

A little background:  

I have created a conic frustum object (cone with top cut off) by compounding triangles. The code works well, however I am tying to plot many hundreds of these to create a tree and it is slow. The slowness comes from creating the frusta.  Once they are created I compound them into one object so they display very fast when I orbit the the camera around the scene. 

How can I speed up object creation?

My general approach so far: 

1. Create vertices and normals based on a rotation around the x-axis. 
2. Store triangles based on these vertices in a list and compound them. 
   
3. Translate the shape to the origin
4. Rotate the shape around the z-axis, then rotation vertically around the normal axis to the shape's axis from the prior rotation and the z-axis
5. Translate the shape to its final location. 

Room for improvement:  If I plot the shapes as cylinders instead of conic frusta (line 192 in attached code as opposed to lines 184 or 188) the model I am building completes in a fraction of a second. Using my custom shape takes nearly a minute. 

Possible ways I am thinking to speed this up:

1. The conic frustum is stored as a function not a class as are other objects, I'm not sure but it may speed things up to make a class instead
2. Preform the rotations and translations of the vertices and normals before creating and compounding triangles.
3. Calculate vertices and normals "in-place" around an axis based on their final location so they don't need to be translated or rotated later. 
4. There is a step where I build a list of triangles out of vertices and normal that had a for loop, which I converted to list comprehension that could be a bottleneck, would the map() function be better here (line 90 in code)?

I've attached some code that should be stand-alone. I'm using vPython 7.3, python 3.6.3, spyder 3.1.4, and displaying in a Chrome Browser.

The key functions in the code are frustum, buildfaces, and everything below line 105 creates the scene, widgets,  and calls the functions above to make shapes. The end models will consist of hundreds of these shapes and I need to make a lot of them, the code only includes 4. 

Does anyone have much experience rapidly creating custom shapes? Do you have any advice to speed this up?

Thank you, 

Russell Kramer

[Bruce Sherwood]

It sounds like all you need to change is to make just one object and clone it instead of laboriously creating a large number of frustrums from vertex and triangle objects. Make a single compound located at the origin with simple axis, then make as many clones as you need, specifying their pos, axis, and size attributes:

fr = compound([.....[)

frustrums = []

for i in range(1000):

    frustrums.append(fr.clone(pos=..., axis=.....))

You can of course just append fr.clone() and then set pos and axis for individual objects later.

When you create the compound, its "mesh" (consisting of vertexes, normals, and triangles) is stored in GPU memory and from that moment forward has essentially the same status as a box or cylinder object, except that axis and size are not linked to each other.

Here is the documentation for clone:

http://www.glowscript.org/docs/VPythonDocs/clone.html

Note the last sentence in the compound documentation:

Also, a compound object can be cloned to make additional copies.

Bruce

[Russell Kramer]

Thank you Bruce, 

This make a lot of sense, except that to resize to radii on either end of the frustum as I have it now I think I need to recalculated the vertex positions. Perhaps it is faster to do this anyway because I already have the vertices created, I just need to alter the vertex coordinates in each clone. 

I also assume that I need to make a frustum class with pos, axis, and size attributes correct and methods to resize or else cloning will not have these attributes correct?

Someone contributed a frustum class in Vpython6, so I'll use that as a template and post here if I come up with a good solution. 

[Bruce Sherwood]

No, there's no reason to make a frustrum class. A compound object is a class, like the box class or sphere class, and clones of a compound object are instances of the compound object class. You could of course name your compound object "frustrum", so that any clone would be thisclone = frustrum.clone().

Bruce

[Russell Kramer]

Hello Bruce, 

I understand that a compound object is a class itself, the problem is that it doesn't inherit the specific properties I used to create the frustum (i.e. top radius and base radius).

Each frustum I create needs to have a unique base and top radius. A compound object as pos, size, axis, color etc. and I see how to translate and rotate using pos and axis attributes. Size seems like it will scale the overall object evenly across x,y, and z which I think means I can't specify a different base and top radius using inherent attributes of the compound object. 

I thought maybe aligning the compound object along the x-axis, then changing the size using size = vec (50,1,1) would lengthen the object and scale it evenly in the y-z dimension to 1, however it does't seem to do anything to blue object in the code below. 

To change the size of the base and top radius independently do I need to make a frustum class with base and top radius attributes before using the clone command? 

Code example below: 

bP and tP are lists of vectors for top positions and base positions, bR and tR are a list of base and top radii

full working code attached. 

testFrust = frustum(basePos = bP[0], topPos = tP[0], baseR = bR[0], topR = tR[0], color = color, visible = False)

testFrust1 = testFrust.clone(pos = bP[0], axis = tP[0]-bP[0], color = color.red, visible = True)  #make first frustum

testFrust2 = testFrust.clone(pos = bP[1], axis = tP[1]-bP[1], color = color.yellow, visible = True)  #test translation and rotation

testFrust2 = testFrust.clone(pos = bP[2], axis = tP[2]-bP[2], size = vec(50,1,1), color = color.blue, visible = True)  #test scaling (not working as expected, shifts but size is the same)

   

Thank you,

Russell

[Bruce Sherwood]

I can't work through your large program, but I don't understand your comment about size not having an effect on a compound. Here is a very simple example:

scene.range = 5

b = box(pos=vec(-.5,0,0), color=color.red)

s = sphere(pos=vec(.5,0,0), radius=0.5, color=color.green)

c = compound([b,s])

scene.pause()

c.size = vec(10,1,1)

The final statement makes the compound be very long in the x direction while keeping the object unchanged in the y and z directions.

Bruce

[Russell Kramer]

Sorry for not being more clear. This does clarify for me that the size attribute will scale the object evenly in each coordinate direction which is not what I am after. 

What I'm really after is a way to scale the base and top diameters of the compound frusta object. It seems like this is not possible, so I will attempt to make a frustum class that does have these attributes and can be cloned. I don't really see how this will be any faster however because I will still need to rebuild the vertices and normals after changing the base and top radii and length. 

[Bruce Sherwood]

It doesn't make sense to clone an object if that object will be used only once; you would be creating twice as many objects as are needed.

Bruce

[Bruce Sherwood]

You might consider using curve objects, since you can specify the radius of the object at the start of each segment of the curve, and you can also specify the color of each segment. Each segment of a curve is rendered as a (crude) hemisphere plus a (crude) cylinder. The cylinder has 16 sides and the hemisphere has 16 sections.

If you continue to make your segments out of triangles, because each frustrum is unique, then the efficient scheme is to have a function to which you pass the length, two radii, and an axis, and it creates the triangles with axis = <1,0,0>, makes a compound, then sets the axis of the compound to the requested value, and returns the compound (if further manipulation is called for). 

By the way, the shapes and paths libraries provide a simple way to generate the points that make up a circle: http://www.glowscript.org/docs/VPythonDocs/shapes.html

There are two reasons for making a compound for each frustrum. One is to simplify the establishing of the desired axis, and the other is to speed up display by the GPU. If you find that display speed is not adequate, for every 100th frustrum (say) you would compound those 100 frustrums. Without compounding the compounds, each individual frustrum counts as a unique object, and at render time each type of object (box, sphere, cylinder, your frustrum1, your frustrum2, your frustrum3,.....) requires its own special setup by the CPU before sending instances of that object type to the GPU. Having to do 500 setups for 500 individually different object types is costly.

Bruce

[Russell Kramer]

I though about using curves, however they cannot be compounded. Part of the program has a radio button to turn on and off the visibility of different types of frusta while rotating them, so I thought that compounding would be better for display speed etc...

Your second suggestion is what the program does now. I have a function that builds triangles, and normals and then outputs a compound object rotated and translated to its correct position. It's not too slow, but does take about 10 sec for 100 frusta. I can lower the number of sections (currently at 40) to make a cruder shape and try averaging the normals on the edges to smooth the appearance.  So far the display speed is great once the frusta are created, it is the creation that takes a while. 

I think it is good enough for now, I'll just run with it. Thanks for you help. 

[Bruce Sherwood]

I think it would be useful for you to try a curve. In the following little program 10,000 curve segments are connected, with varying colors and radii. The creation is nearly instantaneous, and there's nothing sluggish about the display.

from vpython import *

from random import random

N = 10000

p = []

last = vec(0,0,0)

for i in range(N):

    move = 0.1*vec.random()

    next = last+move

    if abs(next.x) > 1 or abs(next.y) > 1 or abs(next.z) > 1:

        next = last-move

    p.append({'pos':next, 'radius':0.001+0.03*random(),

              'color':vec(1,1,1)+vec.random()/2})

    last = p[-1]['pos']

c = curve(p)

[Bruce Sherwood]

Here's a version with the 10,000-segment curve rotating smoothly. Note that you can address individual segments of a curve, so your button could for example make a segment invisible or a different color, etc.

from vpython import *

from random import random

N = 10000

p = []

last = vec(0,0,0)

for i in range(N):

    move = 0.1*vec.random()

    next = last+move

    if abs(next.x) > 1 or abs(next.y) > 1 or abs(next.z) > 1:

        next = last-move

    p.append({'pos':next, 'radius':0.001+0.03*random(),

              'color':vec(1,1,1)+vec.random()/2})

    last = p[-1]['pos']

c = curve(p)

while True:

    rate(100)

    c.rotate(angle=0.01, axis=vec(0,1,0))

[Bruce Sherwood]

I made a mistake in the color arithmetic, and I made some small improvements. It's quite a pretty scene with the 10,000-point curve filling a spherical volume. On my computer it even works pretty well with 20,000 points on the curve.

from vpython import *

from random import random

scene.width = scene.height = 800

scene.background = color.white

scene.range = 1.3

N = 10000

p = []

last = vec(0,0,0)

for i in range(N):

    next = last+0.1*vec.random()

    while mag(next) > 1:

        next = last+0.1*vec.random()

    p.append({'pos':next, 'radius':0.001+0.03*random(), 'color':(vec(1,1,1)+vec.random())/2})

    last = p[-1]['pos']

c = curve(p)

while True:

    rate(100)

    c.rotate(angle=0.01, axis=vec(0,1,0))

Here's a 20,000-point version, in GlowScript:

http://www.glowscript.org/#/user/Bruce_Sherwood/folder/Pub/program/RotatingCurve

Bruce

[Bruce Sherwood]

This turned out to be so pretty that it has been added to the Example programs at glowscript.org:

http://www.glowscript.org/#/user/GlowScriptDemos/folder/Examples/program/RotatingCurve

Bruce

[Russell Kramer]

Thanks Bruce, this is really cool. In the future I will definitely consider curves.