Brush-based interactive element packing

doi:10.11996/JG.j.2095-302X.2025010188

Abstract

Abstract:

Element packing is a visual art form that involves tightly packing elements within an area, often seen in logos and art-works, particularly in posters and advertisements. The traditional process of designing element packing requires manual adjustments to align elements to the appropriate size and orientation, which is repetitive and time-consuming. Existing algorithms can assist designers in quickly designing by dividing the design process into two steps: outlining the packing area then packing the elements. However, in actual creative workflows, these two steps occur simultaneously. Therefore, existing methods are incompatible with the real design process. To address this issue, an easy-to-use brush tool was introduced to achieve packing while outlining boundaries. A brush-based element packing technique was proposed, where each element was represented as a triangle mesh and applied to a spring mass system. During simulation, non-overlapping elements were attracted to each other, while overlapping elements repelled each other. Similar to traditional brushes used for color filling, the brush tool allows real-time element packing. By inviting multiple users to design using the system, the effectiveness of the proposed method was evaluated. Results indicated that the technique significantly reduced design time, improved compactness of packing results, and enhanced controllability of the process.

Key words: element packing, brush design, physical simulation, real-time deformation, graphics design

CLC Number:

TP391.41

LIANG Mu, XU Pengfei, HUANG Hui. Brush-based interactive element packing[J]. Journal of Graphics, 2025, 46(1): 188-199.

Figures/Tables 18

Fig. 1 Element packing design

Fig. 2 From left to right: giraffes turn into penguins after being rotated[10]

Fig. 3 Sketch map ((a) Path (J=5); (b) Color blocks (K=3))

Fig. 4 Triangle Mesh T (green solid line) and auxiliary (black dashed line)

Fig. 5 Force diagram ((a) Edge force and shape force; (b) Repulsive force; (c) Attractive force; (d) Boundary force)

Fig. 6 The two elements with the biggest shape difference before and after deformation of the same element ((a) Plant; (b) Flower; (c) Carrot; (d) Circle)

Fig. 7 Comparison ((a) Ours; (b) Fillinger; (c) RepulsionPak[14]; (d) AEF[13]+RepulsionPak[14])

Table 1 Computing time of each method in figure 7

方法	运算时间/ms
本文方法	210
Fillinger	8520
RepulsionPak^[14]	28460
AEF^[13]+RepulsionPak^[14]	4910

Fig. 8 Intersection area ((a) Ours; (b) Fillinger; (c) RepulsionPak[14]; (d) AEF[13]+RepulsionPak[14])

Fig. 9 Negative space and redraw after deleting ((a) Use negative space to measure the packing results (left: 0.726; right: 0.717); (b) Redraw after deleting)

Table 2 The calculated values of the filling factor d for Figures 8, 9(a), 11, and 12

图号	d
图8(a)	38.679
图8(b)	136.413
图8(c)	63.284
图8(d)	56.813
图9(a) (left)	58.587
图9(a) (right)	61.225
图11(a)	42.614
图11(b)	51.106
图11(c)	46.563
图11(d)	37.342
图11(e)	49.731
图12(a)	105.299
图12(b)	57.160
图12(c)	79.535
图12(d)	75.082
图12(e)	83.462

Fig. 10 Ablation experiment ((a) Result; (b) w/o edge force; (c) w/o boundary force; (d) w/o repulsive force; (e) w/o attractive force; (f) w/o shape force)

Fig. 11 User design ((a) Designer; (b) User 1; (c) User 2; (d) User 3; (e) User 4)

Fig. 12 User design ((a) Designer + AEF[13] + RepulsionPak[14]; (b) User 1 + AEF[13] + RepulsionPak[14]; (c) User 2 + RepulsionPak[14]; (d) User 3 + RepulsionPak[14]; (e) User 4 + RepulsionPak[14])

Fig. 13 Score results ((a) Similarity score of our method (solid line) and existed methods (dashed line); (b) Comprehensive scoring)

Fig. 14 Hand draw ((a) Font design; (b) Graphic design)

Fig. 15 Element packing ((a) Decoration design (left from designer, right from our method); (b) Stick figure packing)

Fig. 16 Real-time deformation ((a) Concave shape distortion and sacrificial boundary conditions; (b) Delete the element in the upper left corner of the left picture)

References 36

[1]	RAAD L, DAVY A, DESOLNEUX A, et al. A survey of exemplar-based texture synthesis[J]. Annals of Mathematical Sciences and Applications, 2018, 3(1): 89-148.
[2]	TU P H, WEI L Y, YATANI K, et al. Continuous curve textures[J]. ACM Transactions on Graphics (TOG), 2020, 39(6): 168.
[3]	TU P H, WEI L Y, ZWICKER M. Clustered vector textures[J]. ACM Transactions on Graphics (TOG), 2022, 41(4): 159.
[4]	BARLA P, BRESLAV S, THOLLOT J, et al. Stroke pattern analysis and synthesis[J]. Computer Graphics Forum, 2006, 25(3): 663-671.
[5]	LUKÁČ M, FIŠER J, ASENTE P, et al. Brushables: example‐based edge‐aware directional texture painting[J]. Computer Graphics Forum, 2015, 34(7): 257-267.
[6]	KAZI R H, IGARASHI T, ZHAO S D, et al. Vignette: interactive texture design and manipulation with freeform gestures for pen-and-ink illustration[C]// SIGCHI Conference on Human Factors in Computing Systems. New York: ACM, 2012: 1727-1736.
[7]	LI Y F, BREEN D E, MCCANN J, et al. Algorithmic quilting pattern generation for pieced quilts[C]// The 45th Graphics Interface Conference. New York: ACM, 2019: 13.
[8]	LU J W, BARNES C, WAN C, et al. DecoBrush: drawing structured decorative patterns by example[J]. ACM Transactions on Graphics (TOG), 2014, 33(4): 90.
[9]	ALBANO V, FANNI F A, GIACHETTI A, et al. FloralSurf: space-filling geodesic ornaments[EB/OL]. [2024-03-08]. https://diglib.eg.org/items/26dc8a7b-a842-4f33-b6be-a34c6e6a9575.
[10]	SAPUTRA R A, KAPLAN C S, ASENTE P. Improved deformation-driven element packing with RepulsionPak[J]. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(4): 2396-2408.
[11]	KWAN K C, SINN L T, HAN C, et al. Pyramid of arclength descriptor for generating collage of shapes[J]. ACM Transactions on Graphics (TOG), 2016, 35(6): 229.
[12]	HSU C Y, WEI L Y, YOU L H, et al. Brushing element fields[C]// The SIGGRAPH Asia 2018 Technical Briefs. New York: ACM, 2018: 6.
[13]	HSU C Y, WEI L Y, YOU L H, et al. Autocomplete element fields[C]// The 2020 CHI Conference on Human Factors in Computing Systems. New York: ACM, 2020: 1-13.
[14]	SAPUTRA R A, KAPLAN C S, ASENTE P, et al. RepulsionPak: deformation-driven element packing with repulsion forces[C]// The 44th Graphics Interface Conference. Waterloo: Canadian Human-Computer Communications Society, 2018: 10-17.
[15]	陈中贵, 欧阳永昇, 曹娟. 特征保持的马赛克图像生成方法[J]. 计算机辅助设计与图形学学报, 2014, 26(4): 520-527.
	CHEN Z G, OUYANG Y S, CAO J. Feature-preserving method for mosaic image generation[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(4): 520-527 (in Chinese).
[16]	XU P F, DING J Q, ZHANG H, et al. Discernible image mosaic with edge-aware adaptive tiles[J]. Computational Visual Media, 2019, 5(1): 45-58.
[17]	杨祖义, 张俊松. 融合主题和视觉特征的图片拼贴画合成方法[J]. 计算机辅助设计与图形学学报, 2019, 31(8): 1403-1409.
	YANG Z Y, ZHANG J S. Picture collage synthesis considering theme and visual features[J]. Journal of Computer-Aided Design & Computer Graphics, 2019, 31(8): 1403-1409 (in Chinese).
[18]	KIM J, PELLACINI F. Jigsaw image mosaics[J]. ACM Transactions on Graphics (TOG), 2002, 21(3): 657-664.
[19]	HAUSNER A. Simulating decorative mosaics[C]// The 28th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 2001: 573-580.
[20]	SMITH K, LIU Y J, KLEIN A. Animosaics[C]// The 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York: ACM, 2005: 201-208.
[21]	CHEN M H, XU F, LU L. Manufacturable pattern collage along a boundary[J]. Computational Visual Media, 2019, 5(3): 293-302.
[22]	余丽娟, 曹娟, 陈中贵. 改进区域划分的圆Packing变分算法[J]. 计算机辅助设计与图形学学报, 2018, 30(7): 1251-1257.
	YU L J, CAO J, CHEN Z G. Improved domain partitions for variational circle packing[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(7): 1251-1257 (in Chinese).
[23]	刘景发, 张国建, 刘文杰, 等. 正三角形容器内等圆Packing问题的启发式算法[J]. 计算机辅助设计与图形学学报, 2012, 24(6): 808-815.
	LIU J F, ZHANG G J, LIU W J, et al. Heuristic algorithm for the equal circles packing problem in equilateral triangle container[J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(6): 808-815 (in Chinese).
[24]	张凯, 柯颖, 曹娟, 等. 圆组填充算法驱动的平面马赛克模拟[J]. 计算机辅助设计与图形学学报, 2018, 30(7): 1216-1223.
	ZHANG K, KE Y, CAO J, et al. Circle group packing algorithm for mosaic synthesis[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(7): 1216-1223 (in Chinese).
[25]	GIESEKE L, ASENTE P, LU J W, et al. Organized order in ornamentation[C]// The Symposium on Computational Aesthetics. New York: ACM, 2017: 4.
[26]	REINERT B, RITSCHEL T, SEIDEL H P. Interactive by-example design of artistic packing layouts[J]. ACM Transactions on Graphics (TOG), 2013, 32(6): 218.
[27]	DAVISON T, SAMAVATI F, JACOB C. Interactive example-palettes for discrete element texture synthesis[J]. Computers & Graphics, 2019, 78: 23-36.
[28]	张驰, 张效娟, 赵洋, 等. 基于调色板的半交互式低照度唐卡图像增强[J]. 图学学报, 2023, 44(6): 1202-1211. DOI
	ZHANG C, ZHANG X J, ZHAO Y, et al. Palette-based semi-interactive low-light Thangka images enhancement[J]. Journal of Graphics, 2023, 44(6): 1202-1211 (in Chinese). DOI
[29]	王华, 李绅绅, 何晓宇, 等. 基于个性化定制的交互式蒙版擦除动画设计与实现[J]. 图学学报, 2019, 40(3): 473-480. DOI
	WANG H, LI S S, HE X Y, et al. Design and implementation of interactive mask erasing animation based on personalized customization[J]. Journal of Graphics, 2019, 40(3): 473-480 (in Chinese). DOI
[30]	BENES B, ZHOU X C, CHANG P, et al. Urban brush: intuitive and controllable urban layout editing[C]// The 34th Annual ACM Symposium on User Interface Software and Technology. New York: ACM, 2021: 796-814.
[31]	SAPUTRA R A, KAPLAN C S, ASENTE P, et al. FLOWPAK: flow-based ornamental element packing[C]// The 43rd Graphics Interface Conference. Waterloo: Canadian Human-Computer Communications Society, 2017: 8-15.
[32]	NICOLET B, ECORMIER-NOCCA P, MEMARI P, et al. Pair correlation functions with free-form boundaries for distribution inpainting and decomposition[EB/OL]. [2024-03-08]. https://inria.hal.science/hal-02500803/file/short1039_CRC.pdf.
[33]	NIETO J R, SUSÍN A. Cage based deformations: a survey[M]//HIDALGO M G, TORRES A M, GÓMEZ J V. Deformation Models: Tracking, Animation and Applications. Dordrecht: Springer, 2013: 75-99.
[34]	ZHANG J Y, DENG B L, LIU Z S, et al. Local barycentric coordinates[J]. ACM Transactions on Graphics (TOG), 2014, 33(6): 188.
[35]	JACOBSON A, BARAN I, POPOVIĆ J, et al. Bounded biharmonic weights for real-time deformation[J]. ACM Transactions on Graphics (TOG), 2011, 30(4): 78.
[36]	FLOATER M S. Mean value coordinates[J]. Computer Aided Geometric Design, 2003, 20(1): 19-27.